Maximizing Entropy over Markov Processes

Fabrizio Biondi 1 Axel Legay 1, * Bo Friis Nielsen 2 Andrzej Wasowski 3
* Auteur correspondant
1 ESTASYS - Efficient STAtistical methods in SYstems of systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
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.
Type de document :
Communication dans un congrès
7th International Conference on Language and Automata Theory and Applications, Apr 2013, Bilbao, Spain
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01242613
Contributeur : Fabrizio Biondi <>
Soumis le : dimanche 13 décembre 2015 - 14:35:17
Dernière modification le : mercredi 16 mai 2018 - 11:24:07
Document(s) archivé(s) le : samedi 29 avril 2017 - 13:01:32

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01242613, version 1

Collections

Citation

Fabrizio Biondi, Axel Legay, Bo Friis Nielsen, Andrzej Wasowski. Maximizing Entropy over Markov Processes. 7th International Conference on Language and Automata Theory and Applications, Apr 2013, Bilbao, Spain. 〈hal-01242613〉

Partager

Métriques

Consultations de la notice

471

Téléchargements de fichiers

54