Abstract Hidden Markov Models: a monadic account of quantitative information flow

Annabelle McIver, Carroll Morgan, Tahiry Rabehaja

Research output: Contribution to journalArticlepeer-review

35 Downloads (Pure)


Hidden Markov Models, HMM's, are mathematical models of Markov processes with state that is hidden, but from which information can leak. They are typically represented as 3-way joint-probability distributions. We use HMM's as denotations of probabilistic hidden-state sequential programs: for that, we recast them as "abstract" HMM's, computations in the Giry monad D, and we equip them with a partial order of increasing security. However to encode the monadic type with hiding over some state X we use DX→D2X rather than the conventional X→DX that suffices for Markov models whose state is not hidden. We illustrate the DX→D2X construction with a small Haskell prototype. We then present uncertainty measures as a generalisation of the extant diversity of probabilistic entropies, with characteristic analytic properties for them, and show how the new entropies interact with the order of increasing security. Furthermore, we give a "backwards" uncertainty-transformer semantics for HMM's that is dual to the "forwards" abstract HMM's - it is an analogue of the duality between forwards, relational semantics and backwards, predicate-transformer semantics for imperative programs with demonic choice. Finally, we argue that, from this new denotational-semantic viewpoint, one can see that the Dalenius desideratum for statistical databases is actually an issue in compositionality. We propose a means for taking it into account.
Original languageEnglish
Article number36
Pages (from-to)1-50
Number of pages50
JournalLogical Methods in Computer Science
Issue number1
Publication statusPublished - 29 Mar 2019

Bibliographical note

Copyright the Author(s). Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.


  • Abstract Hidden Markov Models
  • Giry Monad
  • Quantitative Information Flow


Dive into the research topics of 'Abstract Hidden Markov Models: a monadic account of quantitative information flow'. Together they form a unique fingerprint.

Cite this