Streett Automata Model Checking of Higher-Order Recursion Schemes

Ryota Suzuki, Koichi Fujima, Naoki Kobayashi, Takeshi TsukadaFSCD 2017 · OpenReview

TL;DR

This paper introduces a new, practical algorithm for checking if a higher-order recursion scheme (HORS) generates a tree accepted by a Streett automaton. This is crucial for verifying liveness properties in higher-order programs. Their direct approach is significantly faster than previous methods that converted Streett automata to parity automata, and it's the first to achieve polynomial time complexity in the HORS size for Streett/parity automata model checking.

What Problem Does This Paper Address?

Verifying the correctness of programs, especially those with complex control flow and data structures, is a major challenge. Higher-order recursion schemes (HORS) are a powerful way to model the behavior of higher-order functional programs. Model checking HORS involves checking if the tree generated by a HORS satisfies certain properties, often expressed by tree automata.

A key application is verifying liveness properties, which essentially ask if "something good eventually happens." These properties are often formalized using Streett automata. However, existing model checkers for HORS that can handle the full power of Streett automata (or even parity automata, which are equivalent in expressive power) are computationally expensive, often suffering from hyper-exponential time complexity in the size of the HORS. This makes them impractical for many real-world scenarios. Previous practical algorithms for HORS model checking were limited to simpler types of automata (trivial tree automata).

The paper aims to bridge this gap by developing a practical and efficient algorithm for Streett automata model checking of HORS, and also a parity automata version, that can handle the full expressiveness of these automata while remaining computationally feasible.

Methods

The core of the paper's contribution lies in a novel type system designed for Streett automata model checking of HORS. This type system is parameterized by a Streett automaton and establishes a correspondence: a HORS is typable in this system if and only if its generated tree is accepted by the automaton. This type system is an adaptation of existing work on parity automata model checking, with a key innovation being the introduction of "effects" to capture the specific conditions required by Streett automata.

Based on this type system, the authors develop a practical algorithm. Instead of building the full, potentially massive, game graph associated with the type system, their algorithm constructs a subgame containing only relevant types. This is achieved through an iterative process of type expansion until a fixpoint is reached. This fixpoint then guides the construction of a smaller, manageable game that can be solved efficiently. The algorithm is inspired by existing saturation-based methods for simpler automata.

For the parity automata version, they adapt the type system and game construction to match the requirements of parity games.

Datasets

The paper describes experiments using two benchmark sets:

  1. A set of 97 parity automata model checking problems, including those used in previous work and new ones derived from program verification tasks.
  2. A set of inputs derived from existing work on fair non-termination verification, with modifications to test the impact of varying the complexity parameter 'k' of Streett conditions.

No new datasets were introduced; rather, existing benchmarks were used to evaluate the performance of their implemented model checkers.

Key Insights and Ideas

  • Direct Streett Automata Handling: The paper demonstrates that directly handling Streett automata in HORS model checking is not only possible but also more efficient than converting them to parity automata first. This is a significant practical improvement.
  • Polynomial Time Complexity (Fixed-Parameter): The algorithm achieves a breakthrough by being the first practical Streett or parity automata model checker for HORS that runs in time polynomial in the size of the HORS, assuming other parameters (automaton size, HORS order/arity) are fixed. This is a crucial step towards making HORS model checking scalable.
  • Type System with "Effects": The novel type system, incorporating "effects," is the theoretical foundation that allows for the direct and efficient handling of Streett automata. These effects capture the state transitions and conditions necessary for Streett acceptance.
  • Practicality through Subgame Construction: The algorithm's practicality stems from its ability to construct and solve a reduced game graph based on a fixpoint of relevant types, avoiding the exponential blow-up of the full game.

Key Results

  • HORSATS (Streett) vs. Indirect Approach: Experiments show that their direct Streett automata model checker (HORSATS) is often faster than an indirect approach that first converts Streett automata to parity automata and then uses HORSATP. The direct approach is also more scalable with respect to the complexity parameter 'k' of Streett conditions.
  • HORSATP (Parity) vs. Existing Checkers: The parity automata version (HORSATP) outperforms previous parity automata model checkers (APTRECS, TRAVMC2) on most inputs, especially for larger HORS. It successfully handles many inputs for which existing tools timed out.
  • Efficiency: The proposed algorithms are the first practical ones for Streett/parity automata model checking of HORS that achieve polynomial time complexity in the size of the HORS (under fixed-parameter assumptions).

Limitations and Future Work

  • Fixed-Parameter Assumption: The polynomial time complexity is achieved under the assumption that other parameters (automaton size, HORS order/arity) are fixed. While this is standard in fixed-parameter tractability, it means the complexity can still grow significantly if these parameters are not bounded.
  • Conversion to Parity Games: The implementation of HORSATS still converts Streett games to parity games for solving, as a direct Streett game solver was not readily available. Future work could explore direct Streett game solvers.
  • Further Optimizations: The authors suggest future work on further optimizing Streett/parity automata model checkers.
  • Proof Complexity: The correctness proof for the algorithm is noted as being non-trivial and more involved than for simpler automata.

Summary updated

Abstract

We propose a practical algorithm for Streett automata model checking of higher-order recursion schemes (HORS), which checks whether the tree generated by a given HORS is accepted by a given Streett automaton. The Streett automata model checking of HORS is useful in the context of liveness verification of higher-order functional programs. The previous approach to Streett automata model checking converted Streett automata to parity automata and then invoked a parity tree automata model checker. We show through experiments that our direct approach outperforms the previous approach. Besides being able to directly deal with Streett automata, our algorithm is the first practical Streett or parity automata model checking algorithm that runs in time polynomial in the size of HORS, assuming that the other parameters are fixed. Previous practical fixed-parameter polynomial time algorithms for HORS could only deal with the class of trivial tree automata. We have confirmed through experiments that (a parity automata version of) our model checker outperforms previous parity automata model checkers for HORS.
BibTeX
@inproceedings{suzuki2017streett,
  author = {Ryota Suzuki and Koichi Fujima and Naoki Kobayashi and Takeshi Tsukada},
  title = {{Streett Automata Model Checking of Higher-Order Recursion Schemes}},
  booktitle = {FSCD},
  year = {2017},
  url = {https://openreview.net/forum?id=uV53Qjn1bz},
}
Figure