Quantitative information flow as network flow capacity

Stephen McCamant, Michael D. Ernst

Research output: Contribution to journalArticlepeer-review

27 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. Copyright copy; 2008 ACM.

Original languageEnglish (US)
Pages (from-to)193-205
Number of pages13
JournalACM SIGPLAN Notices
Volume43
Issue number6
DOIs
StatePublished - Jun 2008
Externally publishedYes

Bibliographical note

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

  • Dynamic analysis
  • Implicit flow
  • Information-flow analysis

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

Cite this