Approximation and Randomization for Quantitative Information-Flow Analysis
Approximation and Randomization for Quantitative Information-Flow Analysis
复制标题
DOI：
10.1109/csf.2010.8
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Boris Köpf;A. Rybalchenko
中科院分区：
文献类型：
--
作者：
Boris Köpf;A. Rybalchenko
定量信息流分析（QIF）是一种用于建立信息论机密性属性的新兴技术。 QIF 的自动化是确保其实际适用性的重要一步，因为有关程序安全性的手动推理已被证明是一项繁琐且昂贵的任务。现有的 QIF 自动化技术无法完全覆盖所有程序执行，尤其是在存在无限循环和数据结构的情况下，而众所周知，这些循环和数据结构很难自动分析。在本文中，我们提出了近似和随机化技术的结合，以应对定量信息流属性的足够精确且有效的计算的挑战。我们的方法依赖于采样方法来枚举大型或无界的秘密空间，并应用静态和动态程序分析技术来提供必要的信息论特征的过度和不足近似。
Quantitative information-flow analysis (QIF) is an emerging technique for establishing information-theoretic confidentiality properties. Automation of QIF is an important step towards ensuring its practical applicability, since manual reasoning about program security has been shown to be a tedious and expensive task. Existing automated techniques for QIF fall short of providing full coverage of all program executions, especially in the presence of unbounded loops and data structures, which are notoriously difficult to analyze automatically. In this paper we propose a blend of approximation and randomization techniques to bear on the challenge of sufficiently precise, yet efficient computation of quantitative information flow properties. Our approach relies on a sampling method to enumerate large or unbounded secret spaces, and applies both static and dynamic program analysis techniques to deliver necessary over- and under-approximations of information-theoretic characteristics.