Flavours of Sequential Information Flow

Ezio Bartocci, Thomas Ferrère, Thomas A. Henzinger, Dejan Nickovic, Ana Oliveira da CostaarXiv 2021 · OpenReview

Abstract

Information-flow policies prescribe which information is available to a given user or subsystem. We study the problem of specifying such properties in reactive systems, which may require dynamic changes in information-flow restrictions between their states. We formalize several flavours of sequential information-flow, which cover different assumptions about the semantic relation between multiple observations of a system. Information-flow specification falls into the category of hyperproperties. We define different variants of sequential information-flow specification using a first-order logic with both trace quantifiers and temporal quantifiers called Hypertrace Logic. We prove that HyperLTL, equivalent to a subset of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied two-state independence variants. For our results, we introduce a notion of equivalence between sets of traces that cannot be distinguished by certain classes of formulas in Hypertrace Logic. This presents a new approach to proving inexpressiveness results for logics such as HyperLTL.

Introduction

Information-flow policies, such as non-interference, are essential for ensuring that sensitive data remains inaccessible to unauthorized observers. These policies are categorized as hyperproperties, as they describe relationships between sets of system executions (traces) rather than properties of individual traces. For instance, "independence" requires that for any two observations, a third must exist that merges their public components, thereby demonstrating that secret inputs do not influence public outputs.

Modern reactive systems often employ dynamic security policies where restrictions evolve over time—a concept the authors term sequential information flow. A common scenario is declassification, where a secret is initially protected but released after a specific trigger. This research investigates whether standard formalisms like HyperLTL can express these dynamic "flavours" of information flow, particularly when state transitions occur at different times across executions.

Methodology: Hypertrace Logic and Two-State Independence

To address the limitations of existing logics, the authors introduce Hypertrace Logic (FO[<, T]). This is a two-sorted first-order logic that explicitly quantifies over both system traces and time points. Unlike HyperLTL, which restricts trace quantifiers to the beginning of a formula, Hypertrace Logic allows for more flexible interleaving of quantifiers.

The study centers on a benchmark property called two-state independence: "The value of $y$ is independent of $x$ until a state change occurs, after which $z$ becomes independent of $x$." This property is analyzed across two primary dimensions:

  1. Semantics: Point semantics (independence verified at every time step) vs. Segment semantics (independence verified over execution blocks).
  2. Action Timing: Synchronous (state changes align across traces), Asynchronous (changes occur at different times), and Hidden (changes are unobservable).

The authors utilize abstract trace sets to evaluate these properties. Figure 1 illustrates a set of traces consistent with two-state independence, where shading indicates state transitions.

Figure 1: A set of traces consistent with two-state independence. White cells represent state 0, gray cells represent state 1.

To prove inexpressiveness, the authors developed a technique based on indistinguishable trace sets. By defining an equivalence relation between trace sets for specific logic fragments, they can show that if a logic cannot distinguish between a set that satisfies a property and one that does not, the logic is inexpressive for that property.

Expressiveness Results

The core finding of the paper is that HyperLTL faces a "quantifier bottleneck." Because HyperLTL requires all trace quantifiers to be prefixed, it struggles to "align" traces when events occur asynchronously.

The results, summarized in Figure 2, reveal significant gaps in HyperLTL's capabilities:

  • Success: HyperLTL can only express the Synchronous Segment variant of two-state independence.
  • Failure: It cannot express any variant involving Asynchronous or Hidden action timing. Furthermore, it fails to express the Synchronous Point variant.
Figure 2: Expressiveness of HyperLTL for different variants of two-state local independence.

In contrast, the more general Hypertrace Logic is capable of expressing all studied variants, highlighting the necessity of its flexible quantifier structure for complex security policies.

Conclusion and Future Work

This research demonstrates that while HyperLTL is a powerful tool for static hyperproperties, it is fundamentally limited when dealing with the asynchronous nature of sequential information flow. While the study focused on simple two-state transitions, it provides a rigorous framework for evaluating more complex declassification policies.

Future work will explore whether extensions like Asynchronous HyperLTL can bridge this expressiveness gap and investigate the computational trade-offs between the power of Hypertrace Logic and the tractability of model-checking.

Summary updated

Abstract

Information-flow policies prescribe which information is available to a given user or subsystem. We study the problem of specifying such properties in reactive systems, which may require dynamic changes in information-flow restrictions between their states. We formalize several flavours of sequential information-flow, which cover different assumptions about the semantic relation between multiple observations of a system. Information-flow specification falls into the category of hyperproperties. We define different variants of sequential information-flow specification using a first-order logic with both trace quantifiers and temporal quantifiers called Hypertrace Logic. We prove that HyperLTL, equivalent to a subset of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied two-state independence variants. For our results, we introduce a notion of equivalence between sets of traces that cannot be distinguished by certain classes of formulas in Hypertrace Logic. This presents a new approach to proving inexpressiveness results for logics such as HyperLTL.
BibTeX
@misc{bartocci2021flavours,
  author = {Ezio Bartocci and Thomas Ferrère and Thomas A. Henzinger and Dejan Nickovic and Ana Oliveira da Costa},
  title = {{Flavours of Sequential Information Flow}},
  year = {2021},
  eprint = {2105.02013},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.02013},
}
Figure