  Timing side channels in two-user schedulers are studied. When two users share
a scheduler, one user may learn the other user's behavior from patterns of
service timings. We measure the information leakage of the resulting timing
side channel in schedulers serving a legitimate user and a malicious attacker,
using a privacy metric defined as the Shannon equivocation of the user's job
density. We show that the commonly used first-come-first-serve (FCFS) scheduler
provides no privacy as the attacker is able to to learn the user's job pattern
completely. Furthermore, we introduce an scheduling policy,
accumulate-and-serve scheduler, which services jobs from the user and attacker
in batches after buffering them. The information leakage in this scheduler is
mitigated at the price of service delays, and the maximum privacy is achievable
when large delays are added.
