This paper proposes a reconciliation of two different theories of information. The first, originally proposed in a lesser-known work by Claude Shannon, describes how the information content of channels can be described qualitatively, but still abstractly, in terms of information elements, i.e. equivalence relations over the data source domain. Shannon showed that these elements form a complete lattice, with the order expressing when one element is more informative than another. In the context of security and information flow this structure has been independently rediscovered several times, and used as a foundation for reasoning about information flow. The second theory of information is Dana Scott's domain theory, a mathematical framework for giving meaning to programs as continuous functions over a particular topology. Scott's partial ordering also represents when one element is more informative than another, but in the sense of computational progress, i.e. when one element is a more defined or evolved version of another. To give a satisfactory account of information flow in programs it is necessary to consider both theories together, to understand what information is conveyed by a program viewed as a channel (\`a la Shannon) but also by the definedness of its encoding (\`a la Scott). We combine these theories by defining the Lattice of Computable Information (LoCI), a lattice of preorders rather than equivalence relations. LoCI retains the rich lattice structure of Shannon's theory, filters out elements that do not make computational sense, and refines the remaining information elements to reflect how Scott's ordering captures the way that information is presented. We show how the new theory facilitates the first general definition of termination-insensitive information flow properties, a weakened form of information flow property commonly targeted by static program analyses.
翻译:本文建议对两种不同的信息理论进行调和。 首先, 最初在克洛德· 香农( Claude Shannon) 的较不为人知的工作中提出, 描述如何从质量上描述频道的信息内容, 但仍然抽象地描述信息要素, 即数据源域的等同关系 。 香农显示这些元素构成一个完整的线条, 当一个元素比另一个元素更具有信息性时, 表示一个元素比另一个元素更具有信息性时的顺序 。 在安全和信息流动的背景下, 这个结构被独立地重新发现, 并用作信息流动推理的基础 。 第二个信息理论是 Dana Scott 的域论, 一个数学框架, 将程序作为持续功能的功能赋予程序, 在一个特定的顶端函数中, 一个数学框架, 当一个元素比另一个数据源域的等同性( la Shactrial) 时, 部分的排序也代表一个数据流, 我们通过定义这些元素的直观的直观性结构, 来显示一个普通信息流。