Visible to the public TWC: Small: Confidentiality Measurement of Complex Computations using Quantitative Information FlowConflict Detection Enabled

Project Details

Performance Period

Sep 01, 2015 - Aug 31, 2018


University of Minnesota-Twin Cities

Award Number

Concern about information privacy is a major obstacle to user adoption of new information technology applications, from smart phone applications to the deployment of automated workflows in the largest health-care and government enterprises. This project addresses privacy concerns caused by software through errors and malicious attacks. A major security concern about software revolves around whether computers reveal information that they should not. Much of the information we entrust to computers might be described as secret, private, or confidential, because we want to limit who has access to it. However many things can go wrong in computer systems to allow information to be revealed when it should not. In this project the focus is on the information that is present in the results of a computation. A computation might take information from several sources and combine it in a complex way to produce output. These outputs are usually not in a format that can easily be read directly by people, thus the output from a computation may be undesirably "leaking" information without our knowledge. The project tackles this problem using techniques called quantitative information flow analysis, which allow one computer program to automatically determine how much information another computer program is revealing. For instance, such an analysis system might report that one program always reveals 4 bits of secret information, while another program revealed 1000 bits of secret information in its most recent execution. By comparing these measurements to the expected behavior of a program, one can detect situations that might be causing a program to reveal information that it should not. Previous quantitative information flow analysis systems have demonstrated that the basic approach is sound, but they have been limited in the kinds and sizes of programs where they are effective, and they require guidance from software developers to obtain good results. This project will develop new techniques that eliminate these restrictions to make quantitative information flow analysis more widely applicable.

The quantitative information-flow techniques, which measure the number of bits of information about secret computation inputs that are revealed by computation outputs, give a measurement that can be evaluated separately without reference to the intended meaning of the computation results and without additional annotation or specification of the subject program. By combining a quantitative analysis with techniques from taint analysis and symbolic execution, the tools can track in a precise way where secret information flows, and the connection between input values and output values. Quantitative information-flow measurement has not yet seen practical adoption because existing approaches have too high overhead, do not naturally support multiple kinds of secret data, are limited in the software to which they apply, and/or require occasional developer annotations. The project seeks to overcome the limitations of previous approaches by generalizing the underlying techniques and improving their precision, while at the same time improving their performance and applicability via staged optimizations and complete automation. The research will demonstrate the approach by application to a number of realistic challenge problems in computer security and privacy.