License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.534
URN: urn:nbn:de:0030-drops-38872
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3887/
Go to the corresponding LIPIcs Volume Portal

Chadha, Rohit ; Ummels, Michael

The Complexity of Quantitative Information Flow in Recursive Programs

pdf-format:
48.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chadha_et_al:LIPIcs:2012:3887,
  author =	{Rohit Chadha and Michael Ummels},
  title =	{{The Complexity of Quantitative Information Flow in Recursive Programs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{534--545},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3887},
  URN =		{urn:nbn:de:0030-drops-38872},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.534},
  annote =	{Keywords: quantitative information flow, recursive programs, program analysis, verification, computational complexity}
}

Keywords: quantitative information flow, recursive programs, program analysis, verification, computational complexity
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI