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.
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.
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.
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.
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
