Quantitative information flow as network flow capacity

Download: PDF, Flowcheck implementation.

“Quantitative information flow as network flow capacity” by Stephen McCamant and Michael D. Ernst. In PLDI 2008: Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, (Tucson, AZ, USA), June 2008, pp. 193-205.
A previous version appeared as MIT Computer Science and Artificial Intelligence Laboratory technical report MIT-CSAIL-TR-2007-057, (Cambridge, MA), December 10, 2007.
A previous version appeared as “Quantitative information-flow tracking for C and related languages” by Stephen McCamant and Michael D. Ernst. MIT Computer Science and Artificial Intelligence Laboratory technical report MIT-CSAIL-TR-2006-076, (Cambridge, MA), November 17, 2006.

Abstract

We present 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 maximum flow in a network also gives a minimum cut (a set of edges that separate the secret input from the output), which can be used to efficiently check that the same policy is satisfied on future executions. We performed case studies on 5 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.

Download: PDF, Flowcheck implementation.

BibTeX entry:

@inproceedings{McCamantE2008,
   author = {Stephen McCamant and Michael D. Ernst},
   title = {Quantitative information flow as network flow capacity},
   booktitle = {PLDI 2008: Proceedings of the {ACM} {SIGPLAN} 2008
	Conference on Programming Language Design and Implementation},
   pages = {193--205},
   address = {Tucson, AZ, USA},
   month = jun,
   year = {2008}
}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.