Information theoretic analysis of side channel information leakage in FCFS schedulers
Xun Gong, Negar Kiyavash, Parv Venkitasubramaniam · 2011
The information leakage of a queuing side channel in two-user-shared scheduling system is studied from an information theoretic perspective. In the queueing side channel, a malicious attacker can learn the pattern of jobs from a legitimate user using the queuing delays experienced at the shared buffer. An analytical framework is proposed to quantify information leakage using Shannon's equivocation, and the information leakage of the standard First-come-First-serve scheduler is studied in a slotted system with geometric arrivals. The analysis of the FCFS scheduler demonstrates that the policy provides “good privacy” when arrival rates are very low; the leaked information increases with the rate of the attacker's jobs and approaches the maximum retrievable information as the sum-rate of arrivals approaches the boundary of the stability region of the queue.