Tuesday, February 26, 2008
4:15 pm
B17 Upson Hall

Computer Science
Spring 2008

Stephen McCamant
Massachusetts Institute of Technology

Quantitative Information-flow Tracking as Maximum Network Flow

I'll describe a new technique for determining how much information about a program's secret inputs is revealed by its public outputs. In contrast to previous techniques based on reachability from secret inputs (tainting), it achieves a more precise quantitative result by computing a maximum flow of information between the inputs and outputs. The technique uses static control-flow regions to soundly account for implicit flows via branches and pointer operations, but operates dynamically by observing one or more program executions and giving numeric flow bounds specific to them (e.g., ``17 bits''). The results are a conservative estimate of channel capacity: the amount of information that could be transmitted by an adversary making an arbitrary choice of secret inputs. We've performed case studies on five real C, C++, and Objective C programs, 3 of which had more than 250K lines of code. The tool checked multiple security policies, including one that was violated by a previously unknown bug. (A paper describing this work will appear in PLDI 2008.) I'll also say a bit about how this work relates to themes in my previous research, and point out some future directions.

Stephen McCamant is a Ph.D. candidate in MIT's Electrical Engineering and Computer Science department, doing research in the Computer Science and AI Lab. His primary research interests lie in programming languages and program analysis, as applied to the problems of software engineering and security. He previously received an M.S. from MIT and a B.A. in Computer Science from the University of California, Berkeley. Home Page: http://people.csail.mit.edu/smcc/