  In this work, we study information leakage in timing side channels that arise
in the context of shared event schedulers. Consider two processes, one of them
an innocuous process (referred to as Alice) and the other a malicious one
(referred to as Bob), using a common scheduler to process their jobs. Based on
when his jobs get processed, Bob wishes to learn about the pattern (size and
timing) of jobs of Alice. Depending on the context, knowledge of this pattern
could have serious implications on Alice's privacy and security. For instance,
shared routers can reveal traffic patterns, shared memory access can reveal
cloud usage patterns, and suchlike. We present a formal framework to study the
information leakage in shared resource schedulers using the pattern estimation
error as a performance metric. The first-come-first-serve (FCFS) scheduling
policy and time-division-multiple-access (TDMA) are identified as two extreme
policies on the privacy metric, FCFS has the least, and TDMA has the highest.
However, on performance based metrics, such as throughput and delay, it is well
known that FCFS significantly outperforms TDMA. We then derive two parametrized
policies, accumulate and serve, and proportional TDMA, which take two different
approaches to offer a tunable trade-off between privacy and performance.
