CoChat

LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invariant Inference

Wu, Guangyuan, Cao, Weining, Yao, Yuan, Wei, Hengfeng, Chen, Taolue, Ma, Xiaoxing · 2024 · Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering

The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.

Abstract

Loop invariant inference, a key component in program verification, is a challenging task due to the inherent undecidability and complex loop behaviors in practice. Recently, machine learning based techniques have demonstrated impressive performance in generating loop invariants automatically. However, these methods highly rely on the labeled training data, and are intrinsically random and uncertain, leading to unstable performance. In this paper, we investigate a synergy of large language models (LLMs) and bounded model checking (BMC) to address these issues. The key observation is that, although LLMs may not be able to return the correct loop invariant in one response, they usually can provide all individual predicates of the correct loop invariant in multiple responses. To this end, we propose a "query-filter-reassemble" strategy, namely, we first leverage the language generation power of LLMs to produce a set of candidate invariants, where training data is not needed. Then, we employ BMC to identify valid predicates from these candidate invariants, which are assembled to produce new candidate invariants and checked by off-the-shelf SMT solvers. The feedback is incorporated into the prompt for the next round of LLM querying. We expand the existing benchmark of 133 programs to 316 programs, providing a more comprehensive testing ground. Experimental results demonstrate that our approach significantly outperforms the state-of-the-art techniques, successfully generating 309 loop invariants out of 316 cases, whereas the existing baseline methods are only able to tackle 219 programs at best. The code is publicly available at https://github.com/SoftWiser-group/LaM4Inv.git.

Overview

Integrity signals

Registry

Crossref · 10.1145/3691620.3695014

Cites

40 of 40 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Research works printed but not linked: 15

  1. Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. 2019. SyGuS-Comp 2018: Results and Analysis. CoRR abs/1904.07146 (2019). arXiv preprint arXiv:1904.07146 (2019). · arXiv
  2. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. 2017. Sygus-comp 2017: Results and analysis. arXiv preprint arXiv:1711.11438 (2017). · arXiv
  3. Edmund Clarke, Armin Biere, Richard Raimi, and Yunshan Zhu. 2001. Bounded model checking using satisfiability solving. Formal methods in system design 19 (2001), 7--34.
  4. 10.5555/1792734.1792766 · doi:10.5555/1792734.1792766
  5. Michael D Ernst, Jeff H Perkins, Philip J Guo, Stephen McCamant, Carlos Pacheco, Matthew S Tschantz, and Chen Xiao. 2007. The Daikon system for dynamic detection of likely invariants. Science of computer programming 69, 1--3 (2007), 35--45.
  6. 10.1145/3276501 · doi:10.1145/3276501
  7. Hossein Hojjat and Philipp Rümmer. 2018. The ELDARICA horn solver. In 2018 Formal Methods in Computer Aided Design (FMCAD). IEEE, 1--7.
  8. Chris Lattner. 2008. LLVM and Clang: Next generation compiler technology. In The BSD conference, Vol. 5. 1--20.
  9. Long Ouyang Jeffrey Wu Xu Jiang Diogo Almeida Carroll Wainwright Pamela Mishkin Chong Zhang Sandhini Agarwal Katarina Slama Alex Ray et al. 2022. Training language models to follow instructions with human feedback. Advances in neural information processing systems (NeurIPS) 35 (2022) 27730--27744.
  10. Kexin Pei, David Bieber, Kensen Shi, Charles Sutton, and Pengcheng Yin. 2023. Can large language models reason about program invariants?. In International Conference on Machine Learning. PMLR, 27496--27520.
  11. Mukund Raghothaman and Abhishek Udupa. 2014. Language to specify syntax-guided synthesis problems. arXiv preprint arXiv:1405.5590 (2014). · arXiv
  12. Xujie Si, Hanjun Dai, Mukund Raghothaman, Mayur Naik, and Le Song. 2018. Learning loop invariants for program verification. Advances in Neural Information Processing Systems (NeurIPS) 31 (2018).
  13. Hari Govind Vediramana Krishnan, YuTing Chen, Sharon Shoham, and Arie Gurfinkel. 2023. Global guidance for local generalization in model checking. Formal Methods in System Design (2023), 1--29.
  14. Haoze Wu, Clark Barrett, and Nina Narodytska. 2024. Lemur: Integrating Large Language Models in Automated Program Verification. In The Twelfth International Conference on Learning Representations (ICLR).
  15. Jianan Yao, Ziqiao Zhou, Weiteng Chen, and Weidong Cui. 2023. Leveraging large language models for automated proof synthesis in rust. arXiv preprint arXiv:2311.03739 (2023). · arXiv

Cited by

See all 25

Metadata

Authors
Wu, G., Cao, W., Yao, Y., Wei, H., Chen, T., & Ma, X.
Affiliations
  • Nanjing University (CN)
  • State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu, China
  • Birkbeck, University of London (GB)
Venue
Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering
Publisher
ACM
Published
2024-10-27
Pages
406-417
OpenAlex
W4403536765
Cited by
24
References
39
Citations by year
2026: 18 · 2025: 6
FWCI
15.60
Type
conference paper
Language
en
Open access
closed
Locations
IEEE/ACM International Conference on Automated Software Engineering (ASE) (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
  • Physical Sciences › Computer Science › Software › Logic, programming, and type systems
Keywords
large language models, bounded model checking, program verification, neuro-symbolic reasoning, SMT solvers, immediate feedback, invariant generation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.