Scheduling with privacy constraints

Kadloor, Sachin

Permalink

https://hdl.handle.net/2142/46692 Copy

Description

Title

Scheduling with privacy constraints

Author(s)

Kadloor, Sachin

Issue Date

2014-01-16T17:59:14Z

Director of Research (if dissertation) or Advisor (if thesis)

Kiyavash, Negar

Doctoral Committee Chair(s)

Kiyavash, Negar

Committee Member(s)

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

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• scheduling
• privacy
• timing channel
• side channel

Abstract

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.

Graduation Semester

2013-12

Permalink

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

Copyright and License Information

Copyright 2013 Sachin Kadloor

Owning Collections