Scheduling with privacy constraints

Traditionally, scheduling policies have been optimized to perform well on metrics such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. 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 so on. We present a formal framework to study the information leakage in shared resource schedulers. 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. This raises the question: \emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), possibly randomized, scheduling policy that scores high on the privacy metric?} Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (a deterministic policy) is privacy optimal within the class of work-conserving policies. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Kadloor, Sachin

Contributors dc:contributor

• Kiyavash, Negar
• Hajek, Bruce
• Srikant, Rayadurgam
• Borisov, Nikita

• scheduling
• privacy
• timing channel
• side channel

Statement dc:rights

• Copyright 2013 Sachin Kadloor

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/46692

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/46692