Data-Driven Verification of Procedural Programs with Integer Arrays
Open Access
- 23 July 2025
- book chapter
- Published by Springer Nature
- p. 338-363
Abstract
We address the problem of verifying automatically procedural programs manipulating parametric-size arrays of integers, encoded as a constrained Horn clauses solving problem. We propose a new algorithmic method for synthesizing loop invariants and procedure pre/post-conditions represented as universally quantified first-order formulas constraining the array elements and program variables. We adopt a data-driven approach that extends the decision tree Horn-ICE framework to handle arrays. We provide a powerful learning technique based on reducing a complex classification problem of vectors of integer arrays to a simpler classification problem of vectors of integers. The obtained classifier is generalized to get universally quantified invariants and procedure pre/post-conditions. We have implemented our method and shown its efficiency and competitiveness w.r.t. state-of-the-art tools on a significant benchmark.Keywords
All Related Versions
This publication has 52 references indexed in Scilit:
- Counterexample-Guided Prophecy for Model Checking Modulo the Theory of Arrays2021
- Verifying Array Manipulating Programs with Full-Program Induction2020
- Quantified Invariants via Syntax-Guided Synthesis2019
- Overfitting in Synthesis: Theory and Practice2019
- Extending VIAP to Handle Array Programs2018
- HoIce: An ICE-Based Non-linear Horn Clause Solver2018
- Quantifiers on Demand2018
- Lazy Abstraction with Interpolants2006
- What’s Decidable About Arrays?2005
- Construction of abstract state graphs with PVS1997