The Complexity of Quantitative Information Flow Problems
The Complexity of Quantitative Information Flow Problems
复制标题
定量信息流问题的复杂性
DOI：
10.1109/csf.2011.21
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
T. Henzinger
中科院分区：
文献类型：
--
作者：
Pavol Cerný;K. Chatterjee;T. Henzinger
在本文中，我们研究了定量信息流（QIF）问题的计算复杂性。信息理论的非干扰定量松弛（基于香农熵）已经被引入，以使更细粒度的推理程序的情况下，有限的信息流是可以接受的。QIF边界问题询问给定程序中的信息流是否由常数$d$限定。我们的第一个结果是QIF边界问题是PSPACE完全的。QIF无记忆合成问题问是否有可能解决不确定性的选择在一个给定的部分程序中，在这样一种方式，在所产生的确定性程序，定量信息流是有界的一个给定的常数$d$。我们的第二个结果是QIF无记忆综合问题也是EXPTIME完全的。QIF无记忆综合问题推广到QIF一般综合问题，它不强加无记忆的要求（即，通过允许合成的程序有更多的变量，然后原来的部分程序）。我们的第三个结果是QIF一般综合问题是EXPTIME困难的。
In this paper, we investigate the computational complexity of quantitative information flow (QIF) problems. Information-theoretic quantitative relaxations of noninterference (based on Shannon entropy)have been introduced to enable more fine-grained reasoning about programs in situations where limited information flow is acceptable. The QIF bounding problem asks whether the information flow in a given program is bounded by a constant $d$. Our first result is that the QIF bounding problem is PSPACE-complete. The QIF memoryless synthesis problem asks whether it is possible to resolve nondeterministic choices in a given partial program in such a way that in the resulting deterministic program, the quantitative information flow is bounded by a given constant $d$. Our second result is that the QIF memoryless synthesis problem is also EXPTIME-complete. The QIF memoryless synthesis problem generalizes to QIF general synthesis problem which does not impose the memoryless requirement (that is, by allowing the synthesized program to have more variables then the original partial program). Our third result is that the QIF general synthesis problem is EXPTIME-hard.
影响因子：
1.2
作者：
Clark, David;Hunt, Sebastian;Malacaria, Pasquale
通讯作者：
Malacaria, Pasquale