PhD Proposal: Trace Oblivious Program Execution

Privacy preserving computation is attracting increasing attention in recent years, with applications to secure cloud computing and secure multi-party computations.
Encryption of data alone is insufficient for privacy. It is imperative that programs' execution behavior leaks no sensitive information about secret inputs. Recent research studies how to leverage a powerful cryptographic tool called Oblivious RAM (or ORAM for short) to obfuscate memory access traces. While achieving strong, provable security, existing ORAM techniques incur poly-logarithmic overhead for each memory access.
In preliminary work, I observed that, for certain programs (or portions of a program) whose access traces do not depend on secret inputs, their access traces need not be obfuscated, thus avoiding the ORAM overhead. Therefore, I formally defined the security notion of trace obliviousness that a program must satisfy to prevent information leakage through execution traces. In particular, for the secure cloud computing scenario, I defined the notion of memory trace obliviousness (or MTO), while for the secure multi-party computation scenario, I defined the notion of memory- and instruction- trace obliviousness. I developed programming analysis tools, i.e. security type systems, to formally enforce that a given program satisfies trace-obliviousness.
I propose three pieces of work. First, I propose a mechanized theory for trace oblivious program execution. Second, I will extend the current theory for sequential program semantics to handle parallel semantics. Finally, I would like to explore the possibility of weaker security notions, and more permissive type systems to support more efficient programs.
Examining Committee:
Committee Chair: - Dr. Elaine Shi
Dept's Representative - Dr. Jon Froehlich
Committee Member(s): - Dr. Michael Hicks