We study the problem of completely automatically verifying uninterpreted programsÐprograms that work over arbitrary data models that provide an interpretation for the constants, functions and relations the program uses. The verification problem asks whether a given program satisfies a postcondition written using quantifier-free formulas with equality on the final state, with no loop invariants, contracts, etc. being provided. We show that this problem is undecidable in general. The main contribution of this paper is a subclass of programs, called coherent programs that admits decidable verification, and can be decided in Pspace. We then extend this class of programs to classes of programs that are k-coherent, where k ∈ N, obtained by (automatically) adding k ghost variables and assignments that make them coherent. We also extend the decidability result to programs with recursive function calls and prove several undecidability results that show why our restrictions to obtain decidability seem necessary. This work is licensed under a Creative Commons Attribution 4.0 International License. Umang Mathur, P. Madhusudan, and Mahesh Viswanathan constants like 0, 1, functions like +, −, and relations like ≤, where there is an implicit assumption on the meaning of these constants, functions, and relations. Programs over uninterpreted data models work over arbitrary data-models, where the interpretation of functions and relations are not restricted in any way, except of course that equality is a congruence with respect to their interpretations (e.g., if x = y, then f (x ) = f (y), no matter what the interpretation of f is). A program satisfies its assertions over uninterpreted data models if it satisfies the assertions when working over all data-models. The theory of uninterpreted functions is a theory that only has the congruence axioms, and is an important theory both from a theoretical and practical standpoint. Results in classical logic such as Gödel's (weak) completeness theorem are formulated for such theories. And in verification, when inductive loop invariants are given, verification conditions are often formulated as formulas in SMT theories, where the theory of uninterpreted functions is an important theory used to model memory, pointers in heaps, arrays, and mathematical specifications. In particular, the quantifier-free logic of uninterpreted functions is decidable and amenable to Nelson-Oppen combination with other theories, making it a prime theory in SMT solvers [Bradley and Manna 2007] . We show, perhaps unsurprisingly, that verification of uninterpreted programs is undecidable. The main contribution of this paper is to identify a class of programs, called coherent programs, for which verification is decidable. Program executions can be viewed abstractly as computing terms conditioned on assumptions over terms. Assignments apply functions of the underlying data-domain and hence the value of a variable at any point in an execution can be seen as computing a term in the underlying data-model. Conditional checks executed by the program can be seen as assumptions the program makes regarding the relations that hold between terms in the data-model. For example, after an execution of the statements x := y; x := x + 1; assume(x > 0); z := x * y, the program variable z corresponds to the term ( y + 1) * y, and the execution makes the assumption that y + 1 > 0, where y is the value of variable y at the start of the execution. A coherent program has only executions where the following two properties hold. The first is the memoizing property that says that when a term is recomputed by the execution, then some variable of the program already has the same term (or perhaps, a different term that is equivalent to it, modulo the assumptions seen so far in the execution). The second property, called early assumes says, intuitively, that when an assumption of equality between variables x and y is made by a program, superterms of the terms stored in variables x and y computed by the program must be stored in one of the current variables. We show that the notion of coherence effectively skirts undecidability of program verification. Both notions of memoizing and early-assumes require variables to store certain computed terms in the current set of variables. This notion in fact is closely related to bounded path-width of the computational graph of terms computed by the program; bounded path-width and bounded tree-width are graph-theoretic properties exploited by many decision procedures of graphs for decidability of MSO and for efficient algorithms [Courcelle and Engelfriet 2012; Seese 1991], and there have been several recent works where they have been useful in finding decidable problems in verification [Chatterjee et al. 2016 [Chatterjee et al. , 2015 Madhusudan and Parlato 2011] . Our decidability procedure is automata-theoretic. We show that coherent programs generate regular sets of coherent executions, and we show how to construct automata that check whether an execution satisfies a post-condition assertion written in quantifier-free theory of equality. The automaton works by computing the congruence closure of terms defined by equality assumptions in the execution, checking that the disequality assumptions are met, while maintaining this information only on the bounded window of terms corresponding to the current valuation of variables of the program. In fact, the automaton can be viewed as a streaming congruence closure algorithm that computes the congruence closure on the moving window of terms computed by the program. The
Furthermore, the restrictions of coherence studied in REF and the work here that are based on bounded path-width notions seem very different from studies of decidable problems in KAT.
Decidable verification of uninterpreted programs
PACMPL
Computer Science