A Type-Based HFL Model Checking Algorithm

Youkichi Hosoi, Naoki Kobayashi, Takeshi Tsukada

Abstract

Higher-order modal fixpoint logic (HFL) is a higher-order extension of the modal mu-calculus, and strictly more expressive than the modal mu-calculus. It has recently been shown that various program verification problems can naturally be reduced to HFL model checking: the problem of whether a given finite state system satisfies a given HFL formula. In this paper, we propose a novel algorithm for HFL model checking: it is the first practical algorithm in that it runs fast for typical inputs, despite the hyper-exponential worst-case complexity of the HFL model checking problem. Our algorithm is based on Kobayashi et al.'s type-based characterization of HFL model checking, and was inspired by a saturation-based algorithm for HORS model checking, another higher-order extension of model checking. We prove the correctness of the algorithm and report on an implementation and experimental results.

Introduction

Higher-Order modal Fixpoint Logic (HFL) is a powerful tool for formal verification, extending the standard modal $\mu$-calculus with higher-order predicates. This allows it to describe complex, non-regular properties of programs that simpler logics cannot capture. However, HFL model checking comes with a massive computational cost: the problem is $k$-EXPTIME complete for formulas of order $k$.

Example of a finite state transition system used in model checking.

Until now, there was no HFL model checker capable of handling high-order formulas on realistic systems due to this hyper-exponential complexity. This paper introduces HomuSat, the first practical algorithm for HFL model checking. By leveraging a type-based approach and a novel backward expansion technique, HomuSat bypasses worst-case complexity to solve real-world program verification problems efficiently.

Methods: Type-Based Saturation

The authors propose a type-based saturation algorithm that rests on three main pillars:

  1. Typability Games: The model checking problem is transformed into a "typability game" (a specific kind of parity game). If the system can be "typed" according to certain rules, the formula is satisfied.
  2. Backward Expansion: Instead of constructing the entire, massive game arena upfront, the algorithm starts with a small, initial set of types. It then uses a "Backward Expansion Function" to iteratively discover only the types necessary to prove or disprove the formula.
  3. Recursion-Free Approximations: To guide this search, the algorithm uses finite "unfoldings" of the HFL formula. By looking at these simpler, non-recursive versions, the algorithm identifies which types are likely to be part of a winning strategy in the full game.
Visualization of the saturation-based algorithm mapping a transition system to a type-based game.

Essentially, the algorithm "saturates" a small subgame with just enough information to reach a conclusion, avoiding the hyper-exponential state space of the full theoretical model.

Experimental Results

To evaluate HomuSat, the authors used 136 benchmarks originally designed for Higher-Order Recursion Scheme (HORS) model checkers, mechanically translated into HFL. These included formulas up to order 8 and transition systems with over 200 states.

  • Performance: HomuSat often outperformed HorSatP, a state-of-the-art HORS model checker, despite working on more complex translated formulas.
  • Scalability: The tool successfully solved the xhtmlf-div-2 benchmark—involving an order-2 HES and 220 states—in under 2 seconds.
  • Practical Complexity: While HFL is $k$-EXPTIME in the worst case, experiments showed that for many practical problems, the running time is actually a fixed-parameter polynomial relative to the size of the equation system.

Key Insights and Future Work

The most significant insight is that for "typical" inputs derived from actual program verification, only a tiny fraction of theoretically possible types are needed. The authors also found that using subtyping relations allowed them to prune the search space significantly by ignoring "weaker" types when a "stronger" type already proves a property.

Future work will focus on testing HomuSat on "native" HFL problems that utilize branching-time properties HORS cannot express. The authors also plan to implement more sophisticated flow analysis and integrate negation directly into the type system to further improve performance and formula readability.

Summary updated

Abstract

Higher-order modal fixpoint logic (HFL) is a higher-order extension of the modal mu-calculus, and strictly more expressive than the modal mu-calculus. It has recently been shown that various program verification problems can naturally be reduced to HFL model checking: the problem of whether a given finite state system satisfies a given HFL formula. In this paper, we propose a novel algorithm for HFL model checking: it is the first practical algorithm in that it runs fast for typical inputs, despite the hyper-exponential worst-case complexity of the HFL model checking problem. Our algorithm is based on Kobayashi et al.'s type-based characterization of HFL model checking, and was inspired by a saturation-based algorithm for HORS model checking, another higher-order extension of model checking. We prove the correctness of the algorithm and report on an implementation and experimental results.
BibTeX
@inproceedings{hosoi2019type,
  author = {Youkichi Hosoi and Naoki Kobayashi and Takeshi Tsukada},
  title = {{A Type-Based HFL Model Checking Algorithm}},
  booktitle = {APLAS},
  year = {2019},
  url = {https://openreview.net/forum?id=VpZ1XvgZmy},
}
Figure