On Higher-Order Reachability Games Vs May Reachability

Kazuyuki Asada, Hiroyuki Katsura, Naoki Kobayashi

TL;DR

This paper proves a surprising equivalence between two-player "reachability games" and one-player "may-reachability" problems in higher-order functional programs. The authors show that solving a reachability game for a program of order $n$ is computationally equivalent to solving a may-reachability problem for a program of order $n+1$, allowing researchers to use existing verification tools interchangeably across these different classes of problems.

What Problem Does This Paper Address?

In the world of formal verification, we often want to know if a program can reach a certain state (like an error or a success point). There are two common ways to frame this:

  1. May-Reachability: A "one-player" problem. Does there exist any sequence of non-deterministic choices that leads to the target? This is typical for safety checking (e.g., "Can this program ever crash?").
  2. Reachability Games: A "two-player" problem involving "angelic" choices (made by the player to reach the goal) and "demonic" choices (made by an opponent to prevent it). This is used for more complex properties, like termination (e.g., "Can the player reach the end regardless of what the environment does?").

Higher-order programs (where functions can take other functions as arguments) make these problems significantly harder. While tools exist for both types of problems, they are usually specialized. The authors address the gap in our understanding of how these two types of reachability relate to one another in a higher-order context.

Methods

The authors formalize the problem using $\mu$HFL(Z), a fragment of higher-order fixpoint logic with integers. This logic serves as a bridge, as there is a direct correspondence between program reachability and the validity of $\mu$HFL(Z) formulas.

The core of the paper consists of two polynomial-time translations:

  • Order-$n$ Game to Order-$(n+1)$ May-Reachability: The "demonic" choices (conjunctions in logic) are transformed into higher-order functions. Essentially, the "game" is simulated by a one-player program that uses higher-order arguments to keep track of the requirements imposed by the demonic opponent.
  • Order-$(n+1)$ May-Reachability to Order-$n$ Game: This is the reverse direction, showing that the extra "order" of a program can be traded back for the complexity of a two-player game.

The authors prove the correctness of these reductions using fixpoint semantics and induction on types.

Datasets

As a theoretical computer science paper, it does not use traditional "datasets." Instead, it uses a benchmark suite from RETHFL, which consists of "non-termination" problems—programs where the goal is to prove that they cannot reach a certain state under any circumstances. These benchmarks are used to evaluate how the new translation improves the performance of existing automated solvers.

Key Insights and Ideas

  • The "Order-Shift" Trade-off: The most profound insight is that the "demonic" nondeterminism of a game isn't inherently different from "angelic" nondeterminism; it just requires a higher level of abstraction (a higher type order) to represent as a one-player problem.
  • Logic as a Bridge: By using $\mu$HFL(Z) instead of raw program syntax, the authors simplify the proof of correctness. They show that angelic/demonic branches in code map perfectly to disjunctions/conjunctions in logic.
  • Tool Interoperability: This theoretical result has immediate practical value. It means a tool like MoCHi (designed for may-reachability) can now be used to solve reachability games, and CHC solvers (designed for games) can be used for higher-order may-reachability.

Key Results

  • Theoretical Equivalence: The paper successfully establishes that order-$n$ reachability games and order-$(n+1)$ may-reachability are effectively the same problem class.
  • Performance Gains: In experimental tests, the authors applied their translation to the RETHFL solver. On several benchmarks, the translated version (RETHFL+tr.) was significantly faster. For example:
  • The unfoldr_nonterm test timed out (over 180s) on the standard solver but finished in 4.22 seconds using the translation.
  • The loopHO test went from a timeout to 0.121 seconds.
  • Polynomial Complexity: The translations are "size-preserving," meaning the resulting program/formula is only polynomially larger than the original.

Limitations and Future Work

  • Solver Sensitivity: While the translation simplifies the type of nondeterminism, it increases the order of the program. Some solvers are very sensitive to type order, meaning the translation might make a problem harder for certain specific tools even if it is theoretically "simpler."
  • Greatest Fixpoints: The current work focuses on $\mu$HFL(Z), which only uses least fixpoints. The authors suggest that extending this to full HFL(Z) (including greatest fixpoints for liveness properties) is a promising but complex direction for future research.
  • Infinite Data Domains: While the logic handles integers, the relationship between these translations and other infinite data types remains to be explored.

Summary updated

Abstract

We consider the reachability problem for higher-order functional programs and study the relationship between reachability games (i.e., the reachability problem for programs with angelic and demonic nondeterminism) and may-reachability (i.e., the reachability problem for programs with only angelic nondeterminism). We show that reachability games for order-\(n\) programs can be reduced to may-reachability problems for order-(\(n+1\)) programs, and vice versa. We formalize the reductions by using higher-order fixpoint logic and prove their correctness. We also discuss applications to higher-order program verification.
BibTeX
@inproceedings{asada2022higher,
  author = {Kazuyuki Asada and Hiroyuki Katsura and Naoki Kobayashi},
  title = {{On Higher-Order Reachability Games Vs May Reachability}},
  booktitle = {RP},
  year = {2022},
  url = {https://openreview.net/forum?id=kVi95KjFVd},
}

Loading related content...

Figure