Higher-Order Program Verification via HFL Model Checking

Naoki Kobayashi, Takeshi Tsukada, Keiichi Watanabe

This paper, "Higher-Order Program Verification via HFL Model Checking," presents a unified framework for verifying higher-order functional programs by reducing various verification tasks—such as reachability, termination, and temporal logic—into a single logic: Higher-Order Modal Fixpoint Logic (HFL). By "flipping" the traditional roles of models and properties, the authors provide a sound and complete characterization of program behavior that works even for programs with infinite data domains like integers.

TL;DR

The authors show that verifying complex properties of higher-order programs can be simplified by translating programs into logic formulas (HFL) and properties into simple transition systems. This provides a mathematically "perfect" (sound and complete) way to represent program behavior, offering a more uniform alternative to previous specialized verification techniques.

What Problem Does This Paper Address?

Verifying higher-order programs—those where functions can take other functions as arguments—is notoriously difficult. Standard techniques often struggle when these programs also use infinite data, such as integers.

Previously, the "gold standard" was HORS (Higher-Order Recursion Schemes) model checking. However, HORS has a major limitation: it is primarily designed for finite data. To handle integers, researchers had to use "best-effort" transformations (like predicate abstraction) that were often incomplete—meaning they might fail to prove a property even if it were true. Furthermore, different properties (e.g., "will this crash?" vs. "will this run forever?") required entirely different mathematical treatments.

The authors sought a uniform method that could handle all these properties within a single logical framework while remaining complete (capturing the program's semantics exactly).

Methods

The core of their approach is HFL$_Z$, an extension of Higher-Order Modal Fixpoint Logic with integer predicates.

The "Role Flip"

In traditional model checking, you have a Model (the program) and a Property (the logic formula). You check if the Model satisfies the Property. The authors flip this:

  1. The Program becomes the Property: They provide a compositional translation that turns a higher-order program into a massive HFL formula.
  2. The Property becomes the Model: The specific requirement (like a file-access protocol) is represented as a small Labeled Transition System (LTS).

Fixpoint Logic

HFL uses "least fixpoints" ($\mu$) to represent liveness/reachability (something good eventually happens) and "greatest fixpoints" ($\nu$) to represent safety/invariance (something bad never happens). By nesting these, the authors can represent complex temporal properties.

Intersection Types

For the most difficult properties (Linear-Time Temporal Properties), the authors use intersection types. This technique replicates function arguments based on the different states an automaton (tracking the property) might be in, effectively "summarizing" how a function behaves across different execution contexts.

Datasets

As a theoretical paper in formal methods, it does not use traditional "datasets" in the machine-learning sense. Instead, the authors evaluate their method using:

  • Illustrative Program Fragments: Examples involving file-handling protocols (read/close) and recursive mathematical functions (like a CPS-style sum function).
  • Formal Proofs: The primary "result" is the mathematical proof of soundness and completeness for their reductions.

Key Insights and Ideas

  • Uniformity is Power: Instead of having five different tools for five different verification problems, you only need one HFL solver.
  • Completeness for Infinite Data: This is a major theoretical milestone. By moving the "complexity" of infinite data into the logic itself, they avoid the information loss typical of earlier HORS-based methods.
  • De Morgan Duality: Because the reduction is complete, if you want to prove the negation of a property (e.g., "this program cannot reach an error"), you simply take the logical dual of the HFL formula.
  • Logic as a Intermediate Representation: HFL acts as a "compiler target" for verification. Once a program is in HFL, you can use interactive theorem provers (like Coq) or automated SMT solvers to finish the job.

Key Results

  • Sound and Complete Reductions: The authors formally defined and proved reductions for May/Must Reachability, Trace Properties, and $\omega$-regular (Linear-Time Temporal) properties.
  • Complexity: They show that for programs with finite data, the problem is decidable. For infinite data, while the problem is undecidable (as expected due to the Halting Problem), the logic provides a perfect representation of the program.
  • Coq Integration: The authors demonstrated that the resulting HFL formulas can be effectively handled in the Coq proof assistant, allowing humans to help the computer prove difficult properties.

Limitations and Future Work

  • The "Solver Gap": While the reduction to HFL is now well-defined, we still need better HFL solvers. The paper mentions a prototype, but building a high-performance, fully automated solver for HFL with integers is a massive engineering challenge.
  • Undecidability: Because HFL$_Z$ can represent any computer program, it is inherently undecidable. The tool will always occasionally need human "hints" (invariants) for the most complex programs.
  • Efficiency: The transformation for temporal properties involves a polynomial blow-up in the size of the formula relative to the property's automaton. While polynomial is "good" in theory, it can still be slow for very large properties.

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},
}

Loading related content...

Figure