Information Leakage of Non-Terminating Processes

Fabrizio Biondi (1) , Axel Legay (1) , Bo Friis Nielsen (2) , Pasquale Malacaria (3) , Andrzej Wasowski (4)

1 ESTASYS - Efficient STAtistical methods in SYstems of systems
2 DTU - Danmarks Tekniske Universitet = Technical University of Denmark
3 QMUL - Queen Mary University of London
4 ITU - IT University of Copenhagen

In recent years, quantitative security techniques have been providing effective measures of the security of a system against an attacker. Such techniques usually assume that the system produces a finite amount of observations based on a finite amount of secret bits and terminates, and the attack is based on these observations. By modeling systems with Markov chains, we are able to measure the effectiveness of attacks on non-terminating systems. Such systems do not necessarily produce a finite amount of output and are not necessarily based on a finite amount of secret bits. We provide characterizations and algorithms to define meaningful measures of security for non-terminating systems, and to compute them when possible. We also study the bounded versions of the problems, and show examples of non-terminating programs and how their effectiveness in protecting their secret can be measured.

Mots clés: Markov chain; infinite execution; information leakage; Quantitative information flow

Domaines: Cryptographie et sécurité [cs.CR]; Algorithme et structure de données [cs.DS]; Modélisation et simulation; Théorie de l'information [cs.IT]

Fabrizio Biondi, Axel Legay, Bo Friis Nielsen, Pasquale Malacaria, Andrzej Wasowski. Information Leakage of Non-Terminating Processes. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2014, Delhi, India. ⟨10.4230/LIPIcs.FSTTCS.2014.517⟩. ⟨hal-01086879⟩