2026-08-17T16:24:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3887 2024-03-06T10:34:36Z ddc:004 open_access

The Complexity of Quantitative Information Flow in Recursive Programs Chadha, Rohit Ummels, Michael quantitative information flow recursive programs program analysis verification computational complexity Information-theoretic measures based upon mutual information can be employed to quantify the information that an execution of a program reveals about its secret inputs. The information leakage bounding problem asks whether the information leaked by a program does not exceed a given threshold. We consider this problem for two scenarios: a) the outputs of the program are revealed, and b)the timing (measured in the number of execution steps) of the program is revealed. For both scenarios, we establish complexity results in the context of deterministic boolean programs, both for programs with and without recursion. In particular, we prove that for recursive programs the information leakage bounding problem is no harder than checking reachability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Chadha and Michael Ummels 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.534 urn:nbn:de:0030-drops-38872 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.534 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode