Higher-Order Program Verification via HFL Model Checking

Naoki Kobayashi, Takeshi Tsukada, Keiichi Watanabe

Abstract

There are two kinds of higher-order extensions of model checking: HORS model checking and HFL model checking. Whilst the former has been applied to automated verification of higher-order functional programs, applications of the latter have not been well studied. In the present paper, we show that various verification problems for functional programs, including may/must-reachability, trace properties, and linear-time temporal properties (and their negations), can be naturally reduced to (extended) HFL model checking. The reductions yield a sound and complete logical characterization of those program properties. Compared with the previous approaches based on HORS model checking, our approach provides a more uniform, streamlined method for higher-order program verification.

Introduction

Verifying higher-order programs—where functions can accept other functions as arguments—presents significant challenges, particularly when these programs operate on infinite data domains like integers. Historically, Higher-Order Recursion Schemes (HORS) model checking served as the primary framework for such tasks. However, HORS is fundamentally limited to finite data. Extending it to handle integers often requires "best-effort" transformations like predicate abstraction, which are frequently incomplete. Furthermore, different classes of properties, such as safety (reachability) versus liveness (termination), typically required distinct mathematical treatments.

This research proposes a unified framework using Higher-Order Modal Fixpoint Logic (HFL) to address these limitations. By translating programs into HFL formulas, the authors achieve a sound and complete characterization of program behavior across a wide range of temporal properties.

Methodology: HFL and the Role Flip

The core innovation lies in the use of HFL$_Z$, an extension of HFL with integer predicates. The framework employs a "role flip" compared to traditional model checking. In standard approaches, a program is the model and the property is a formula. Here, the program is translated into a large HFL formula, while the property to be verified is represented as a small Labeled Transition System (LTS).

Fixpoint Logic and Typing

HFL utilizes least fixpoints ($\mu$) for liveness/reachability and greatest fixpoints ($\nu$) for safety/invariance. The nesting of these fixpoints allows for the representation of complex temporal properties. The formal structure of this logic is governed by a set of typing rules that ensure the consistency of the higher-order transformations.

Typing rules for Higher-Order Modal Fixpoint Logic (HFL).

Property Representation as Models

By representing properties as models (LTS), the verification task becomes a check of whether the "program formula" holds on the "property model." For example, a file-access protocol requiring a read to be followed eventually by a close can be modeled as a simple transition system.

A simple Labeled Transition System (LTS) representing a file-access protocol.

This approach is particularly powerful for Linear-Time Temporal Properties. The authors use intersection types to "summarize" function behavior across the various states of the property automaton, effectively handling the higher-order nature of the code.

Key Insights and Results

The primary contribution is the definition of sound and complete reductions for May/Must Reachability, Trace Properties, and $\omega$-regular properties.

  • Uniformity: A single HFL solver can replace multiple specialized tools.
  • Completeness: By embedding infinite data complexity directly into the logic, the method avoids the information loss inherent in previous HORS-based abstractions.
  • Duality: The completeness of the reduction allows for straightforward verification of negated properties through logical duality.
  • Practical Integration: The authors demonstrated that the resulting HFL formulas can be processed within the Coq proof assistant, facilitating semi-automated verification for complex cases.

Conclusion and Future Work

While this framework provides a mathematically "perfect" representation of program behavior, practical implementation faces the "Solver Gap." Developing high-performance automated solvers for HFL with integers remains a significant engineering challenge. Additionally, because HFL$_Z$ is expressive enough to represent any program, the underlying problem is undecidable, necessitating human-provided invariants for the most complex verification tasks. Future work will focus on improving solver efficiency and handling the polynomial blow-up associated with complex temporal property transformations.

Summary updated

Abstract

There are two kinds of higher-order extensions of model checking: HORS model checking and HFL model checking. Whilst the former has been applied to automated verification of higher-order functional programs, applications of the latter have not been well studied. In the present paper, we show that various verification problems for functional programs, including may/must-reachability, trace properties, and linear-time temporal properties (and their negations), can be naturally reduced to (extended) HFL model checking. The reductions yield a sound and complete logical characterization of those program properties. Compared with the previous approaches based on HORS model checking, our approach provides a more uniform, streamlined method for higher-order program verification.
BibTeX
@inproceedings{kobayashi2018higher,
  author = {Naoki Kobayashi and Takeshi Tsukada and Keiichi Watanabe},
  title = {{Higher-Order Program Verification via HFL Model Checking}},
  booktitle = {ESOP},
  year = {2018},
  url = {https://openreview.net/forum?id=GztySCDZrd},
}
Figure