POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

We present TriCycle, a framework for deductive verification of $\forall\exists$ temporal hyperproperties. These properties are ubiquitous in the analysis of \emph{reactive systems}, but they are challenging to verify. Indeed, they require finding suitable \emph{existential witnesses}. In the temporal setting, such witnesses are infinite traces of events, and supplying them up-front is particularly difficult.

TriCycle is mechanized in the Rocq proof assistant and enjoys incremental, asynchronous, and compositional reasoning principles for a large class of hyperproperties, notably including $\forall\exists$-safety and $\forall\exists$-liveness. Such generality is beyond existing mechanized frameworks, which support at most $\forall\exists$-safety and compare traces synchronously, one pair of events at a time. This expressive power is achieved by combining two key ingredients: (1) a novel notion of \emph{asynchronous comparator automata} to specify temporal relations between execution traces and decompose their verification into local steps, possibly advancing the traces at different speeds; and (2) \emph{parameterized coinduction} to discover existential witnesses incrementally rather than construct them up-front. Together, these ingredients yield a simple yet versatile verification framework. In particular, TriCycle comes with a general soundness theorem that can be instantiated to obtain sound-by-construction deductive systems for any $\forall\exists$ temporal hyperproperty expressible as an asynchronous comparator automaton.

We present TriCyCle through a selection of examples, formally prove its soundness, and analyze the expressiveness of asynchronous comparator automata. In particular, we show that they can express arbitrary relations between finite traces, and at least all $\omega$-regular relations between infinite traces.