TY - GEN
T1 - Quantitative information flow in Boolean programs
AU - Chadha, Rohit
AU - Kini, Dileep
AU - Viswanathan, Mahesh
PY - 2014
Y1 - 2014
N2 - The quantitative information flow bounding problem asks, given a program P and threshold q, whether the information leaked by P is bounded by q. When the amount of information is measured using mutual information, the problem is known to be PSPACE-hard and decidable in EXPTIME. We show that the problem is in fact decidable in PSPACE, thus establishing the exact complexity of the quantitative information flow bounding problem. Thus, the complexity of bounding quantitative information flow in programs has the same complexity as safety verification of programs. We also show that the same bounds apply when comparing information leaked by two programs.
AB - The quantitative information flow bounding problem asks, given a program P and threshold q, whether the information leaked by P is bounded by q. When the amount of information is measured using mutual information, the problem is known to be PSPACE-hard and decidable in EXPTIME. We show that the problem is in fact decidable in PSPACE, thus establishing the exact complexity of the quantitative information flow bounding problem. Thus, the complexity of bounding quantitative information flow in programs has the same complexity as safety verification of programs. We also show that the same bounds apply when comparing information leaked by two programs.
UR - http://www.scopus.com/inward/record.url?scp=84900534535&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84900534535&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-54792-8_6
DO - 10.1007/978-3-642-54792-8_6
M3 - Conference contribution
AN - SCOPUS:84900534535
SN - 9783642547911
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 103
EP - 119
BT - Principles of Security and Trust - Third International Conference, POST 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Proceedings
PB - Springer
T2 - 3rd International Conference on Principles of Security and Trust, POST 2014 - Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014
Y2 - 5 April 2014 through 13 April 2014
ER -