Oct 16, 2012: Minh Tri Ngo: Confidentiality and Quantitative Analysis for Multi-threaded programs

October 16, 2012Confidentiality and Quantitative Analysis for Multi-threaded programs
Room: Zi 5126Minh Tri Ngo

Confidentiality is an important concern in today's information society: electronic payment and personal data should be protected appropriately. This holds in particular for multi-threaded applications, which are generally seen the future of high-performance computing. Multi-threading poses new challenges to data protection, in particular, data races may be exploited in security attacks. Also, the role of the scheduler is seminal in the multi-threaded context.

 We propose  new notions of confidentiality for probabilistic and non-probabilistic multi-threaded programs, formalized as scheduler-specific (probabilistic) observational determinism.  Essentially, our definitions  ensure that no information about the private data can be derived either from the public data, or from the probabilities of the public data being changed. Moreover, they explicitly depend on a given (class of) schedulers.

 If a program is not secure, we also discuss an approach to determine how much secret information is being leaked, i.e., to express the amount of leakage of secret information in quantitative terms. Quantitative theories of information flow gives us an approach to relax the absolute confidentiality definitions that are hardly satisfied by many practical applications. The classical information-theoretic approach for sequential programs, where the program is modeled as a communication channel with only the input and output, and the measure of leakage is based on the notions of entropy, is not suitable to the multi-threaded context. Reasoning about the exposed information flow of multi-threaded programs is more complicate, because the outcome of such programs depends on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program.