Quantitative information flow as network flow capacity

Stephen McCamant, Michael D. Ernst

Research output: Chapter in Book/Report/Conference proceedingConference contribution

92 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPLDI'08
Subtitle of host publicationProceedings of the 2008 SIGPLAN Conference on Programming Language Design and Implementation
Pages193-205
Number of pages13
DOIs
StatePublished - Dec 12 2008
Event2008 ACM SIGPLAN Conference on Programming Language Design and Implementation 2008, PLDI'08 - Tucson, AZ, United States
Duration: Jun 7 2007Jun 13 2007

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other2008 ACM SIGPLAN Conference on Programming Language Design and Implementation 2008, PLDI'08
CountryUnited States
CityTucson, AZ
Period6/7/076/13/07

Keywords

  • Information-flow analysis
  • dynamic analysis
  • implicit flow

Fingerprint Dive into the research topics of 'Quantitative information flow as network flow capacity'. Together they form a unique fingerprint.

  • Cite this

    McCamant, S., & Ernst, M. D. (2008). Quantitative information flow as network flow capacity. In PLDI'08: Proceedings of the 2008 SIGPLAN Conference on Programming Language Design and Implementation (pp. 193-205). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)). https://doi.org/10.1145/1375581.1375606