Maximizing Entropy over Markov Processes

Fabrizio Biondi, Axel Legay, Bo Friis Nielsen, Andrzej Wąsowski

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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 an 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.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications : 7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings
PublisherSpringer
Publication date2013
Pages128-140
ISBN (Print)978-3-642-37063-2
ISBN (Electronic)978-3-642-37064-9
DOIs
Publication statusPublished - 2013
Event7th International Conference on Language and Automata Theory and Applications (LATA 2013) - Bilbao, Spain
Duration: 2 Apr 20135 Apr 2013
http://grammars.grlmc.com/lata2013/

Conference

Conference7th International Conference on Language and Automata Theory and Applications (LATA 2013)
CountrySpain
CityBilbao
Period02/04/201305/04/2013
Internet address
SeriesLecture Notes in Computer Science
Volume7810
ISSN0302-9743

Fingerprint Dive into the research topics of 'Maximizing Entropy over Markov Processes'. Together they form a unique fingerprint.

Cite this