TY - GEN
T1 - Quantitative information flow as network flow capacity
AU - McCamant, Stephen
AU - Ernst, Michael D.
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Information-flow analysis
KW - dynamic analysis
KW - implicit flow
UR - http://www.scopus.com/inward/record.url?scp=57349180506&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57349180506&partnerID=8YFLogxK
U2 - 10.1145/1375581.1375606
DO - 10.1145/1375581.1375606
M3 - Conference contribution
AN - SCOPUS:57349180506
SN - 9781595938602
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
SP - 193
EP - 205
BT - PLDI'08
T2 - 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation 2008, PLDI'08
Y2 - 7 June 2007 through 13 June 2007
ER -