Low-deterministic security for low-nondeterministic programs
Authors:
- 4 April 2018
- journal article
- research article
- Published by SAGE Publications in Journal of Computer Security
- Vol. 26 (3) , 335-366
Abstract
We present a new algorithm, together with a full soundness proof, which guarantees probabilistic noninterference (PN) for concurrent programs. The algorithm follows the “low-deterministic security” (LSOD) approach, but for the first time allows general low-nondeterminism as long as PN is not violated. The algorithm is based on the earlier observation by Giffhorn and Snelting that low-nondeterminism is secure as long as it is not influenced by high events [ International Journal of Information Security 14 ( 2015 ) 263–287]. It uses a new system of classification flow equations in multi-threaded programs, together with inter-thread/interprocedural dominators. Compared to LSOD, precision is boosted and false alarms are minimized. We explain details of the new algorithm and its soundness proof. The algorithm is integrated into the JOANA software security tool, and can handle full Java with arbitrary threads. We apply JOANA to a multi-threaded e-voting system, and show how the algorithm eliminates false alarms. We thus demonstrate that low-deterministic security is a highly precise and practically mature software security analysis method.Keywords
This publication has 38 references indexed in Scilit:
- Formalizing Probabilistic Noninterference2013
- Noninterfering SchedulersLecture Notes in Computer Science, 2013
- Advanced chopping of sequential and concurrent programsSoftware Quality Journal, 2010
- Flow-sensitive, context-sensitive, and object-sensitive information flow control based on program dependence graphsInternational Journal of Information Security, 2009
- A practical interprocedural dominance algorithmACM Transactions on Programming Languages and Systems, 2007
- Efficient path conditions in dependence graphs for software safety analysisACM Transactions on Software Engineering and Methodology, 2006
- Language-based information-flow securityIEEE Journal on Selected Areas in Communications, 2003
- A conservative data flow algorithm for detecting all pairs of statements that may happen in parallelACM SIGSOFT Software Engineering Notes, 1998
- Combining slicing and constraint solving for validation of measurement softwareLecture Notes in Computer Science, 1996
- Speeding up slicingACM SIGSOFT Software Engineering Notes, 1994