Algebraic foundations for quantitative information flow
Algebraic foundations for quantitative information flow
复制标题
DOI：
10.1017/s0960129513000649
复制
发表时间：
2015-02-01
影响因子：
0.5
通讯作者：
Malacaria, Pasquale
中科院分区：
文献类型：
--
作者：
Malacaria, Pasquale
一些数学思想已经被研究用于定量信息流。信息论、概率、可猜测性是大多数提案的主要思想。他们的目标是分别量化有多少信息被泄露、猜测秘密的可能性有多大以及猜测秘密需要多长时间。在这项工作中，我们在确定性系统的定量分析背景下研究这些想法之间的关系。我们提出信息网格作为这些方法的宝贵基础；它不仅为这些想法提供了一个优雅的代数框架，而且还可以研究它们之间的关系。特别是，我们将使用这个格子来证明一些结果，建立不同定量方法之间的顺序关系对应关系。这些结果的含义还调查了社区最近的工作。虽然这项工作集中于信息网格的基本重要性，但其实际相关性最近已得到证明，特别是通过对 Linux 内核漏洞的定量分析。总的来说，我们相信这些工作为建立信息网格作为定量信息流的主要参考结构之一奠定了基础。
Several mathematical ideas have been investigated for quantitative information flow. Information theory, probability, guessability are the main ideas in most proposals. They aim to quantify how much information is leaked, how likely is to guess the secret and how long does it take to guess the secret respectively. In this work, we investigate the relationship between these ideas in the context of the quantitative analysis of deterministic systems. We propose the lattice of information as a valuable foundation for these approaches; not only it provides an elegant algebraic framework for the ideas, but also to investigate their relationship. In particular, we will use this lattice to prove some results establishing order relation correspondences between the different quantitative approaches. The implications of these results w.r.t. recent work in the community is also investigated. While this work concentrates on the foundational importance of the lattice of information its practical relevance has been recently proven, notably with the quantitative analysis of Linux kernel vulnerabilities. Overall, we believe these works set the case for establishing the lattice of information as one of the main reference structure for quantitative information flow.