Abstract
Program verification—the process of proving software correctness—traditionally relies on expert-crafted heuristics. This report summarizes a novel approach using Relational Hypergraph Neural Networks (R-HyGNN) to learn features from Constrained Horn Clauses (CHCs). By evaluating two graph encoding strategies across five verification tasks, the research demonstrates that GNNs can capture deep semantic insights and predict complex program properties with high accuracy, even for undecidable problems.
Introduction
Machine learning for code faces significant hurdles, primarily syntactic noise and long-distance dependencies where distant code segments influence one another. To address these, researchers Chencheng Liang, Philipp Rümmer, and Marc Brockschmidt leverage CHCs as a "universal language" for verification. CHCs strip away language-specific syntax, leaving pure logical implications. The challenge lies in developing a graph representation that preserves both the syntax (structure) and semantics (behavior) of these logical formulas for neural processing.
Methodology
The authors propose two primary contributions: a specialized architecture and distinct graph representation strategies.
R-HyGNN Architecture
Standard GNNs typically operate on binary edges. However, logic often involves multi-node relations. The Relational Hypergraph Neural Network (R-HyGNN) extends the Relational Graph Convolutional Network (R-GCN) to handle hyperedges—edges connecting three or more nodes—by concatenating node representations based on their specific roles within a relation.
Graph Representations
Two encoding strategies were developed:
- Constraint Graph (CG): Focuses on syntax by mapping symbols and relations into typed nodes and binary edges, effectively building an Abstract Syntax Tree (AST) for the constraints.
- Control- and Data-flow Hypergraph (CDHG): Focuses on semantics by using ternary hyperedges to explicitly represent data and control flow.
Dataset and Scale
The study utilized benchmarks from CHC-COMP 2021, focusing on Linear Integer Arithmetic (LIA). The raw dataset of 17,000 SMT-LIB files was processed into approximately 5,600 graphs for primary tasks.
Experimental Evaluation
The models were tested against five "proxy tasks" designed to measure their understanding of logical structures and program behavior.
Key Results
- Semantics vs. Syntax: The CDHG representation consistently outperformed the CG on tasks requiring deep understanding, highlighting the importance of explicit data-flow encoding.
- Approximating the Undecidable: In Task 4 (Argument Bounds), an undecidable problem, the R-HyGNN achieved over 94% accuracy, suggesting the discovery of powerful patterns that approximate these complex properties.
- Counter-example Prediction: In the most challenging task (Task 5), the CDHG reached 90.59% accuracy in predicting which program parts appear in failure proofs.
- Scalability: The model maintained perfect predictions on complex graphs containing nearly 300 individual clauses.
Conclusion and Future Work
This research establishes that GNNs can effectively "read" the logic of Horn Clauses. While highly accurate, current limitations include the computational overhead of building complex hypergraphs and the need for integration into active Horn solvers like Eldarica. Future research will focus on generalizing these models to other logic theories, such as bit-vectors and arrays, to create a new generation of AI-augmented formal verification tools.
Summary updated