Sun 16 Jan 2022 09:00 - 10:00 at Salon I - Invited Talk Chair(s): Thomas Wies

We study the problem of specifying sequential information-flow properties of systems. Information-flow properties are hyperproperties, as they compare different traces of a system. Sequential information-flow properties can express changes, over time, in the information-flow constraints. For example, information-flow constraints during an initialization phase of a system may be different from information-flow constraints that are required during the operation phase. We formalize several variants of interpreting sequential information-flow constraints, which arise from different assumptions about what can be observed of the system. For this purpose, we introduce a first-order logic, called Hypertrace Logic, with both trace and time quantifiers for specifying lineartime hyperproperties. We prove that HyperLTL, which corresponds to a fragment of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied variants of sequential information flow, including all variants in which the transition between sequential phases (such as initialization and operation) happens asynchronously. Our results rely on new equivalences between sets of traces that cannot be distinguished by certain classes of formulas from Hypertrace Logic. This presents a new approach to proving inexpressiveness results for HyperLTL.

Sun 16 Jan

Displayed time zone: Eastern Time (US & Canada) change

09:00 - 10:00
Invited TalkVMCAI at Salon I
Chair(s): Thomas Wies New York University
Sequential Information FlowRemote
Thomas A. Henzinger IST Austria, Austria