LLM-based Generation of Weakest Preconditions and Precise Array Invariants

Abstract

The weakest precondition (WP) of a program describes the largest set of initial states from which all terminating executions of the program satisfy a given postcondition. The generation of WPs is an important task with practical applications in areas such as software verification and runtime error-checking. For programs containing loops, WP generation critically depends upon synthesizing loop invariants that are inductive in nature; these WPs then essentially embed the inductive properties required for program verification. This paper investigates the use of Large Language Models (LLMs) to generate WPs (and accompanying loop invariants) in order to prove the correctness of non-deterministic programs containing arrays, loops, and arithmetic. Specifically, we employ several models of ChatGPT to derive the WPs and invariants for the aforementioned programs. We then compare these LLM-derived WPs and invariants to their provable counterparts obtained by the MaxPrANQ tool. We find that the quality of the LLM-derived results can vary greatly and is highly dependent on the underlying model used by ChatGPT. This variance in performance propels us to outline directions for future work and discuss how LLMs and formal-tools can complement one another in generating valid WPs and strong invariants.