Article contents
Hidden-Markov program algebra with iteration
Published online by Cambridge University Press: 10 November 2014
Abstract
We use hidden Markov models to motivate a quantitative compositional semantics for noninterference-based security with iteration, including a refinement- or ‘implements’ relation that compares two programs with respect to their information leakage; and we propose a program algebra for source-level reasoning about such programs, in particular as a means of establishing that an ‘implementation’ program leaks no more than its ‘specification’ program.
This joins two themes: we extend our earlier work, having iteration but only qualitative (Morgan 2009), by making it quantitative; and we extend our earlier quantitative work (McIver et al. 2010) by including iteration.
We advocate stepwise refinement and source-level program algebra – both as conceptual reasoning tools and as targets for automated assistance. A selection of algebraic laws is given to support this view in the case of quantitative noninterference; and it is demonstrated on a simple iterated password-guessing attack.
- Type
- Special Issue: Quantitative Information Flow
- Information
- Mathematical Structures in Computer Science , Volume 25 , Issue 2: Quantitative Information Flow , February 2015 , pp. 320 - 360
- Copyright
- Copyright © Cambridge University Press 2014
References
- 10
- Cited by