Team for Research in
Ubiquitous Secure Technology

Citation
Stephen McCamant, Michael D. Ernst. "Quantitative Information Flow as Network Flow Capacity". Talk or presentation, 12, November, 2008.

Abstract
We present a new technique for measuring information flow: the extent to which a program's outputs reveal information about or are influenced by its inputs. 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"). 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. In addition to the maximum flow technique for computing upper bounds, we'll also describe a decision-procedure technique for computing corresponding lower bounds.

Electronic downloads

• 21%20-%20McCamant.pdf · application/pdf · 954 kbytes

• HTML

  Stephen McCamant, Michael D. Ernst. <a
  href="http://www.truststc.org/pubs/492.html"
  ><i>Quantitative Information Flow as Network Flow
  Capacity</i></a>, Talk or presentation,  12,
  November, 2008.

• Plain text

  Stephen McCamant, Michael D. Ernst. "Quantitative
  Information Flow as Network Flow Capacity". Talk or
  presentation,  12, November, 2008.

• BibTeX

  @presentation{McCamantErnst08_QuantitativeInformationFlowAsNetworkFlowCapacity,
      author = {Stephen McCamant and Michael D. Ernst},
      title = {Quantitative Information Flow as Network Flow
                Capacity},
      day = {12},
      month = {November},
      year = {2008},
      abstract = {We present a new technique for measuring
                information flow: the extent to which a program's
                outputs reveal information about or are influenced
                by its inputs. 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"). 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. In addition to the
                maximum flow technique for computing upper bounds,
                we'll also describe a decision-procedure technique
                for computing corresponding lower bounds. },
      URL = {http://www.truststc.org/pubs/492.html}
  }
  

Posted by Jessica Gamble on 23 Jan 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.