Quantifying the Information Leakage in Timing Side Channels in Deterministic Work-Conserving Schedulers

Xun Gong, Negar Kiyavash

Research output: Contribution to journalArticlepeer-review


When multiple job processes are served by a single scheduler, the queueing delays of one process are often affected by the others, resulting in a timing side channel that leaks the arrival pattern of one process to the others. In this work, we study such a timing side channel between a regular user and a malicious attacker. Utilizing Shannon's mutual information as a measure of information leakage between the user and attacker, we analyze privacy-preserving behaviors of common work-conserving schedulers. We find that the attacker can always learn perfectly the user's arrival process in a longest-queue-first (LQF) scheduler. When the user's job arrival rate is very low (near zero), first-come-first-serve (FCFS) and round-robin schedulers both completely reveal the user's arrival pattern. The near-complete information leakage in the low-rate traffic region is proven to be reduced by half in a work-conserving version of TDMA (WC-TDMA) scheduler, which turns out to be privacy-optimal in the class of deterministic working-conserving (det-WC) schedulers, according to a universal lower bound on information leakage we derive for all det-WC schedulers.

Original languageEnglish (US)
Article number7128754
Pages (from-to)1841-1852
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number3
StatePublished - Jun 2016

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Quantifying the Information Leakage in Timing Side Channels in Deterministic Work-Conserving Schedulers'. Together they form a unique fingerprint.

Cite this