TL;DR
This paper introduces HORSAT and HORSATT, novel algorithms for model checking higher-order recursion schemes (HORS). These algorithms combine the strengths of existing type-based and saturation-based approaches, enabling backward propagation of information for more efficient and scalable verification of higher-order programs. Experimental results show HORSAT and HORSATT often outperform state-of-the-art model checkers.
What Problem Does This Paper Address?
Model checking is a crucial technique for verifying the correctness of software. Higher-order recursion schemes (HORS) are a powerful formalism for modeling higher-order programs, making HORS model checking essential for verifying complex functional software. However, existing HORS model checkers face scalability challenges, often struggling with large programs. The field is broadly divided into two main approaches: type-based methods that analyze HORS directly and propagate information forward, and saturation-based methods that work on a related formalism (collapsible pushdown systems) and propagate information backward. These two approaches have remained largely independent, making it difficult to leverage their combined benefits. This paper aims to bridge this gap by developing a new algorithm that integrates backward propagation with direct analysis of HORS using intersection types, thereby improving scalability and efficiency.
Methods
The paper proposes two new algorithms, HORSAT (for co-trivial automata) and HORSATT (for trivial automata), for HORS model checking. These algorithms are inspired by the saturation-based approach for collapsible pushdown systems (CPDS) but are adapted to work directly on HORS.
Key methodological contributions include:
- Backward Propagation with Intersection Types: Unlike previous type-based algorithms that propagate information forward, HORSAT and HORSATT start from target (or "bad") configurations and iteratively compute "pre-images" to determine if the initial state can reach these configurations. This backward analysis is facilitated by using intersection types to represent sets of terms.
- Direct HORS Analysis: The algorithms operate directly on HORS, avoiding the need for complex translations to other formalisms like CPDS.
- Certificate Generation: HORSATT, for trivial automata, is designed to generate intersection types as certificates, which can be independently verified.
- Algorithm Structure: HORSAT uses a fixed-point computation of a function on type environments to determine reachability. HORSATT builds upon HORSAT by incorporating a "shrinking" step to refine the certificate.
Datasets
The paper does not introduce new datasets. Instead, it evaluates its algorithms on a benchmark suite of HORS derived from various applications, including those from the HMTT verification tool, MoCHi, PMRS, exact flow analysis, and data compression. These benchmarks are described as "hard instances" and are automatically generated from program verification problems, with some requiring "No" as the expected output (marked with "(neg)").
Key Insights and Ideas
- Bridging the Gap: The core insight is that backward propagation, traditionally used with CPDS, can be effectively combined with direct HORS analysis using intersection types. This unification offers a more powerful and potentially more efficient approach.
- Backward Analysis for HORS: The paper demonstrates that backward analysis is not only feasible but also beneficial for HORS model checking, offering a different perspective compared to the prevalent forward-analysis techniques.
- Intersection Types as a Unified Representation: Intersection types serve as a flexible and powerful mechanism to represent sets of terms (configurations) in both forward and backward analysis, and to generate verifiable certificates.
- Scalability through Backward Analysis: By starting from target states and working backward, the algorithms can potentially prune the search space more effectively, leading to better scalability than purely forward methods.
Key Results
The paper reports on an implementation of HORSAT and HORSATT. Experimental results on a benchmark suite of HORS show that:
- HORSAT and HORSATT often outperform existing state-of-the-art model checkers like TRECS, GTRECS2, and TravMC, particularly in terms of the number of timeouts.
- HORSAT demonstrates an advantage over CSHORE (a saturation-based checker for CPDS) by working directly on HORS, suggesting that the detour to CPDS is not always necessary.
- The algorithms are theoretically efficient, satisfying fixed-parameter polynomial time complexity, which is expected to lead to better performance on large inputs compared to TRECS.
Limitations and Future Work
- Inhabitance Check Cost: The paper acknowledges that the inhabitance check, crucial for computing the saturation function, can be computationally expensive (EXPTIME-complete). While they propose optimizations and argue it can be treated as a constant-time operation under fixed-parameter assumptions, practical performance might still be affected.
- "Pathological Cases": The authors note that HORSAT experienced a timeout on "fibstring," described as a pathological case where a large string is concisely expressed by a HORS. This suggests that certain HORS structures might still pose challenges.
- Future Work: The paper suggests that the backward approach is arguably more natural for representing regular sets of terms. They also mention that a more streamlined version of CPDS could be used to establish a more precise connection between their type environment representation and alternating tree automata. Further improvements to the implementation are also suggested to achieve near-linear running times.
Summary updated