[Paper] On Conformant Planning and Model-Checking of $exists^*forall^*$ Hyperproperties

Source: arXiv - 2512.23324v1

Overview

The paper uncovers a deep link between two seemingly unrelated research areas: conformant planning (finding a plan that works despite nondeterministic action outcomes) and model‑checking of ∃*∀* hyperproperties (verifying system properties that relate multiple execution traces, such as information‑flow or fairness). By showing that each problem can be transformed into the other, the authors open up new avenues for reusing tools and techniques across planning and verification.

Key Contributions

• Bidirectional reduction
  • A sound‑and‑complete translation from hyperproperty model‑checking instances (∃*∀*) to conformant planning problems.
  • A converse encoding that treats any conformant planning task as a hyperproperty model‑checking problem.
• Complexity insight: Demonstrates that the computational difficulty of ∃*∀* hyperproperty checking is essentially the same as that of conformant planning (both PSPACE‑complete in the general case).
• Tool‑reuse blueprint: Provides a practical recipe for leveraging existing conformant planners (e.g., CFF, KPlanner) to verify hyperproperties, and vice‑versa.
• Formal guarantees: Proofs of soundness (no false positives) and completeness (no false negatives) for both reductions.

Methodology

1. Formal Foundations

   • Conformant planning is formalized as a tuple ⟨S, A, R, I, G⟩ (states, actions, nondeterministic transition relation, initial belief state, goal condition).
   • Hyperproperties are expressed in HyperLTL, focusing on the ∃*∀* fragment (existential quantifiers followed by universal quantifiers).

2. Reduction from Hyperproperty Checking → Conformant Planning

   • Given a system model M and an ∃*∀* HyperLTL formula φ = ∃π₁…∃π_k ∀π_{k+1}…∀π_{k+m}. ψ, they construct a belief‑state planning problem where:
     • The existential traces become nondeterministic choices of actions that “pick” concrete executions.
     • The universal traces are encoded as the nondeterministic outcomes that the planner must be robust against.
   • The goal condition enforces that ψ holds across the selected existential traces for all possible universal extensions.

3. Reduction from Conformant Planning → Hyperproperty Checking

   • Starting from a conformant planning instance, they build a Kripke structure that captures all possible execution trees of the plan.
   • The hyperproperty formula asserts the existence of a single “plan trace” (existential quantifier) that, for every nondeterministic branch (universal quantifiers), satisfies the goal predicate.

4. Proof Sketches

   • Both reductions preserve satisfiability: a solution to the planning problem ↔ a model that satisfies the hyperproperty, and vice‑versa.
   • Complexity arguments rely on known PSPACE‑hardness of conformant planning and of ∃*∀* HyperLTL model‑checking.

Results & Findings

• Equivalence: The two problems are computationally equivalent; any algorithmic breakthrough in one domain immediately transfers to the other.
• Prototype Evaluation: The authors implemented the forward reduction and fed several benchmark hyperproperty instances (information‑flow, fairness) to a state‑of‑the‑art conformant planner. The planner solved them within comparable time to dedicated HyperLTL model‑checkers, confirming practical viability.
• Scalability Insight: The reduction incurs only a linear blow‑up in the size of the original model plus the quantifier prefix, meaning that the approach scales similarly to existing planners.

Practical Implications

• Security‑by‑Design: Developers can now verify complex information‑flow policies (e.g., non‑interference across multiple users) using mature conformant planning tools, sidestepping the need for specialized hyperproperty model‑checkers.
• Fairness & Scheduling: System architects can model fairness constraints as hyperproperties and automatically synthesize robust schedules that guarantee fairness even under nondeterministic task durations.
• Cross‑Domain Tooling: Existing AI planning pipelines (e.g., ROS‑based planners) can be repurposed for verification tasks, reducing tooling overhead for teams already invested in planning infrastructure.
• Education & Prototyping: The reduction offers a pedagogical bridge—students learning planning can experiment with hyperproperty verification without learning a new formalism, and vice‑versa.

Limitations & Future Work

• Fragment Restriction: The equivalence holds for the ∃*∀* fragment of HyperLTL; richer quantifier alternations (e.g., ∀∃∀) are not covered and may lead to higher complexity.
• State‑Explosion in Practice: Although the theoretical blow‑up is linear, real‑world models with large belief spaces can still cause memory pressure for planners not optimized for symbolic representation.
• Tool Integration: The current prototype is a proof‑of‑concept; deeper integration with mainstream verification suites (e.g., SPIN, NuSMV) and planning frameworks (e.g., PDDL planners) remains to be engineered.
• Probabilistic Extensions: Extending the reduction to probabilistic conformant planning and quantitative hyperproperties (e.g., differential privacy) is an open research direction.

Bottom line: By bridging conformant planning and ∃*∀* hyperproperty model‑checking, the paper equips developers with a versatile new lens for building and verifying robust, security‑aware, and fair systems—leveraging the best of AI planning and formal verification.

Authors

• Raven Beutner
• Bernd Finkbeiner

Paper Information

• arXiv ID: 2512.23324v1
• Categories: cs.AI, cs.LO
• Published: December 29, 2025
• PDF: Download PDF