Abstract
Modern formal verification requires the ability to reason about hyperproperties—properties that compare multiple executions of a system. While existing hyperlogics like HyperLTL focus on traces within a specific system model, this paper explores an extension of hypertrace logic that incorporates "unconstrained" trace quantifiers. By mapping the decidability of various fragments, the authors demonstrate that while unconstrained fragments are equivalent to the decidable logic S1S, specific quantifier patterns—particularly those where time quantifiers precede trace quantifiers—introduce undecidability.
Introduction
In the traditional verification of reactive systems, temporal logics such as LTL (Linear Temporal Logic) are used to describe the behavior of a single execution path. However, many critical security and reliability requirements, known as hyperproperties, cannot be expressed by looking at a single trace in isolation. For instance, "Non-interference"—a cornerstone of information security—stipulates that a system's public outputs must remain invariant regardless of changes to secret inputs. Verifying such a property requires comparing at least two different execution traces.
Existing hyperlogics, such as HyperLTL, typically employ constrained trace quantifiers. These quantifiers range strictly over the set of traces produced by a specific system model. While powerful, this approach leaves a gap: it cannot easily reason about unconstrained traces, which represent the universal set of all mathematically possible sequences of events. Reasoning about unconstrained traces is essential for specifying properties like "input enableness," where a system must be shown to produce valid outputs for any possible sequence of inputs, not just those currently accounted for in a specific model. This paper investigates the logical consequences of mixing these quantifier types.
Methodology
The research builds upon Hypertrace Logic (FO[<, T]), a first-order logic that distinguishes between two types of variables: time points and traces. The authors extend this framework through several key technical contributions:
- Syntax Extension: The logic is expanded to distinguish between traces constrained to a system model (denoted as $\exists \pi :: T$) and traces belonging to the universal set of all possible behaviors (denoted as $\exists \pi$).
- The
flattenFunction: To analyze the logic's complexity, the authors developed a transformation calledflatten. This function exploits the independence of distinct traces to rewrite hypertrace formulas into equisatisfiable versions where trace variables are replaced by simpler propositional variables. - Logical Reductions:
- Decidability: The authors prove decidability by demonstrating that unconstrained hypertrace logic can be translated into S1S (Monadic Second-Order Logic of One Successor), a well-understood decidable logic.
- Undecidability: To establish the boundaries of the logic, they employ a reduction from the non-halting problem of 2-counter Minsky machines, showing that certain quantifier configurations can simulate universal computation.
Key Insights: The Power of Alternation
The study reveals that the decidability of hyperlogics is sensitive to how quantifiers are ordered and alternated.
Unconstrained Logic and S1S
A major finding is that unconstrained hypertrace logic is expressively equivalent to S1S. This implies that quantifying over the set of all possible infinite traces is fundamentally the same as quantifying over sets of time points. This equivalence provides a clear path for leveraging existing S1S solvers for universal trace reasoning.
Trace-Prefixed vs. Time-Prefixed Fragments
The research identifies a critical divide based on the placement of quantifiers:
- Trace-prefixed formulas: These are formulas where all trace quantifiers appear before any time quantifiers. This fragment is generally well-behaved and aligns with the expressiveness of HyperQPTL.
- Time-prefixed formulas: These involve quantifying over time points before traces. This structure is significantly more complex. The authors prove that even simple time-prefixed patterns can become undecidable because they allow the logic to "synchronize" different traces in non-regular ways, effectively creating a memory mechanism that exceeds the capabilities of finite-state automata.
Results and Decidability Summary
The paper provides a comprehensive map of the decidability landscape for hypertrace logic:
- Decidable Fragments:
- Purely unconstrained hypertrace logic.
- Trace-prefixed fragments with $\exists^* \forall^*$ quantifier patterns (consistent with the decidable fragment of HyperQPTL).
- Specific time-prefixed fragments where time quantifiers are restricted to existential forms ($\exists_{N<}^*$).
- Undecidable Fragments:
- The general time-prefixed fragment. Specifically, patterns such as $\exists_N \forall_N \exists_N^2 \forall_N \dots$ are shown to be undecidable through Minsky machine simulation, proving that even limited alternation in time-prefixed formulas can lead to computational intractability.
Conclusion and Future Work
While this work successfully maps the boundaries of what can be automatically verified in extended hypertrace logics, it leaves open the question of relative expressiveness. While the "hardness" of solving these fragments is now known, it remains unclear if the trace-prefixed and time-prefixed fragments can express the same set of properties. Future research will focus on bridging these hyperlogics with classical first-order reasoning, potentially enabling the application of automated theorem-proving techniques to a broader range of complex hyperproperties.
Summary updated