Maximizing Entropy over Markov Processes
- Fabrizio Biondi,
- ,
- Axel Legay,
- Bo Friis Nielsen
- ,
- Aalborg Universitet,
- Danmarks Tekniske Universitet
Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-reviewResume
The channel capacity of a deterministic system with confidential data is an upper bound on the amount of bits of data an attacker can learn from the system. We encode all possible attacks to a system using a probabilistic specification, an Interval Markov Chain. Then the channel capacity computation reduces to finding a model of a specification with highest entropy.<br/><br/>Entropy maximization for probabilistic process specifications has not been studied before, even though it is well known in Bayesian inference for discrete distributions. We give a characterization of global entropy of a process as a reward function, a polynomial algorithm to verify the existence of a system maximizing entropy among those respecting a specification, a procedure for the maximization of reward functions over Interval Markov Chains and its application to synthesize an implementation maximizing entropy.<br/><br/>We show how to use Interval Markov Chains to model abstractions of deterministic systems with confidential data, and use the above results to compute their channel capacity. These results are a foundation for ongoing work on computing channel capacity for abstractions of programs derived from code.
Publikation information
Produktionstype
Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-reviewOriginalsprog
EngelskSider fra-til (Antal sider)
Sider 128-140Tidsskrift (Bind, Nummer)
Lecture Notes in Computer Science (Bind 7810)Publikationsmilepæle
- Udgivet - 2013
Publikationsstatus
Udgivet - 2013
ISSN
0302-9743Publikations IDer
- Scopus: 84875654273
Metrikker
PlumX
Antal citationer
6
