Can large language models reason about program invariants?

K Pei, D Bieber, K Shi, C Sutton… - … Conference on Machine …, 2023 - proceedings.mlr.press
Identifying invariants is an important program analysis task with applications towards
program understanding, bug finding, vulnerability analysis, and formal verification. Existing …

Learning invariants using decision trees and implication counterexamples

P Garg, D Neider, P Madhusudan, D Roth - ACM Sigplan Notices, 2016 - dl.acm.org
Inductive invariants can be robustly synthesized using a learning model where the teacher is
a program verifier who instructs the learner through concrete program configurations …

ICE: A robust framework for learning invariants

P Garg, C Löding, P Madhusudan, D Neider - … , CAV 2014, Held as Part of …, 2014 - Springer
We introduce ICE, a robust learning paradigm for synthesizing invariants, that learns using
examples, counter-examples, and implications, and show that it admits honest teachers and …

Optimization and abstraction: a synergistic approach for analyzing neural network robustness

G Anderson, S Pailoor, I Dillig… - Proceedings of the 40th …, 2019 - dl.acm.org
In recent years, the notion of local robustness (or robustness for short) has emerged as a
desirable property of deep neural networks. Intuitively, robustness means that small …

Data-driven precondition inference with learned features

S Padhi, R Sharma, T Millstein - ACM SIGPLAN Notices, 2016 - dl.acm.org
We extend the data-driven approach to inferring preconditions for code from a set of test
executions. Prior work requires a fixed set of features, atomic predicates that define the …

Constraint-based relational verification

H Unno, T Terauchi, E Koskinen - International Conference on Computer …, 2021 - Springer
In recent years they have been numerous works that aim to automate relational verification.
Meanwhile, although Constrained Horn Clauses (CHCs CHCs) empower a wide range of …

Compositional learning and verification of neural network controllers

R Ivanov, K Jothimurugan, S Hsu, S Vaidya… - ACM Transactions on …, 2021 - dl.acm.org
Recent advances in deep learning have enabled data-driven controller design for
autonomous systems. However, verifying safety of such controllers, which are often hard-to …

A data driven approach for algebraic loop invariants

R Sharma, S Gupta, B Hariharan, A Aiken… - … 2013, Held as Part of the …, 2013 - Springer
We describe a Guess-and-Check algorithm for computing algebraic equation invariants of
the form∧ ifi (x 1,…, xn)= 0, where each fi is a polynomial over the variables x 1,…, xn of the …

From invariant checking to invariant inference using randomized search

R Sharma, A Aiken - Formal Methods in System Design, 2016 - Springer
We describe a general framework c2i for generating an invariant inference procedure from
an invariant checking procedure. Given a checker and a language of possible invariants, c2i …

A data-driven CHC solver

H Zhu, S Magill, S Jagannathan - ACM SIGPLAN Notices, 2018 - dl.acm.org
We present a data-driven technique to solve Constrained Horn Clauses (CHCs) that encode
verification conditions of programs containing unconstrained loops and recursions. Our CHC …