Why does it fail? Explanation of verification failures
Lars-Henrik Eriksson · 2026
Read Why does it fail? Explanation of verification failures by Lars-Henrik Eriksson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21788.txt.
Introduction
Eriksson explains why formal verification fails, in terms a domain expert can use. When a proof fails, the solver returns a counterexample with thousands of variables and no clear story. Eriksson's method works when the checks are written with concepts from a formal domain model. A relevance score picks the predicates most likely to explain the failure. Links between predicates then chain those picks into a branching set of explanations. The goal is to help engineers find the real fault faster. Examples compare the method with other approaches.
Catalog record
| CREATOR | Lars-Henrik Eriksson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49269 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21788
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Why does it fail? Explanation of verification failures Lars-Henrik Eriksson Abstract Satisfiability solving is a common technique for formal verification forming the basis of many proof and model checking systems. Failure to show a proof obligation will produce a counterexample or failure trace with typically many thousands or even millions of boolean variables. Interpreting such a counterexample poses a challenge. Even if the individual variables are all understood, it is difficult to form a “big picture” of the situation causing the failure. We consider the case where verification conditions are expressed using concepts from a formal application domain model in a language based on predicate logic or a similar language. We introduce a method to explain verification failures in application domain terms. A measure of the relative relevance of predicates is used to extract the parts of a formula most likely to contribute meaningfully to the explanation. Dependencies between predicates are used to form a branching sequence of successive explanations. These explanations can help a practitioner find faults in the system being verified. The method is demonstrated on examples and compared to other methods. 1 Introduction Satisfiability (SAT) solving is a fundamental proof technique that is used as the underlying method of many proof and model checking tools used for formal modelling and verification, notably the Alloy Analyzer [ 7 ] . Many verification problems expressed in a rich specification language can be naturally translated into propositional logic. Even though such translations typically give rise to very large SAT problems with hundreds of thousands or even several million propositional variables, modern SAT solving engines solve such problems efficiently [ 3 ] . When formal verification fails, the tool will provide a counterexample – a set of facts, such as combination of inputs and outputs or parts of a trace, which disagrees with the formal specification. When traditional testing fails, the specific situation that leads to an error is given by the test case. In formal verification there are no test cases as such, instead a particular situation where the error occurs is implicit in the counterexample. It is then necessary to analyse the counterexample to reconstruct a “test case” after the fact to be able to understand why the failure occurred. Given the large amount of low-level data involved in the counterexample and that most of it will be unrelated to the fault, this is a daunting task to take on. A formal domain model [ 2 ] is a mathematical description of the environment (application domain) in which a computer system operates. A well-structured model helps the software engineer to better understand the application domain and thus to write better formal requirements specifications of a software system. It also makes it easier for application domain experts who are not themselves formal methods practitioners to understand formal specifications. A formal domain model can describe the environment on different levels. For example, in the railway domain , a domain model can describe the kinds of entities and their possible relationships such as the physical tracks, signalling systems, train movements, time tables, rolling stock management, reservations, ticketing etc. depending on the purpose of the software to be designed [ 11 ] . Combining the domain model with data about concrete entities and relations, e.g. descriptions of the actual tracks, signals etc. of a particular railway [ 5 , 6 ] , yields a model of the environment in which a specific computer system operates. Formal domain models can be used to create high-level descriptions of counterexamples. Low-level counterexample data can be translated back to concepts defined in the domain models. For example, in the railway domain individual signal lamp status signals can be translated back to abstract signal aspects. However, there need also be a mechanism to filter out relevant data from the counterexamples. As an example, if a railway signalling system omits a necessary check of a status signal, causing a high-level requirement to be violated, an explanation of the counterexample could point to that particular status signal. We have developed a method to create such explanations. Compared to other methods, the main innovation is the use of a concept of “interest” to extract the information most likely to give a useful explanation. The method has been implemented and experimentally tested on the verification tool GTO [ 6 , 12 ] . The method can of course also explain “positive” results e.g. why a formula is true, but it was developed primarily with failure explanations in mind. This article is organised as follows: In section 2 we summarise our logical formalism. Section 3 describes our method for explanation-finding while section 4 given an applied example. Section 5 discusses the method and compares it to an alternative method. Section 6 discusses relevant existing work. Finally, in section 7 we give conclusions and directions for further work. 2 Foundations We consider the problem of finding explanations to failed formal verification problems in many-sorted first-order (predicate) logic with finite universes (bounded quantification), such as can be found using SAT solvers. In this section we summarise the necessary logical concepts. They are for the most part standard and are included as a reference to the particular variant of formalism we use. The formulæ of our logic are constructed in the standard way from a set of predicate symbols including equality, constant symbols, variables, and the operators \lnot,\land,\lor,\rightarrow,\leftrightarrow,\forall,\exists . Predicate symbols (or simply “predicates”) take zero or more variables or constants as arguments. (Zero argument predicates are the same as propositional symbols.) For simplicity, we do not include function symbols in the language, but generalisation to a logic with function symbols is straightforward. An atom is a predicate applied to a set of arguments (constants or variables). A literal is an atom or a negated atom. We will write predicates, variables and constants in lowercase and use uppercase names for formulæ. Our logic also has definitions of the form p(x_{1},\dots,x_{n})\equiv P,n\geq 0 where the x_{i} are distinct variables. Logically, they represent the formulæ \forall x_{1},\dots,x_{n}.(p(x_{1},\dots,x_{n})\leftrightarrow P) but provide additional information to our explanation algorithm. Free and bound variables are defined in the usual way. Variables range over objects of some particular subset of a universe , depending on their sorts . We assume that every object in the universe is associated with an individual constant symbol. To simplify the presentation, we will identify objects with their corresponding constants. A closed formula is a formula with no free variables. We will sometimes use sets of formulæ in place of a single formula. Such a set should be understood as a representation of the conjunction of all formulæ in the set. The empty set represents a formula that is always true. An interpretation , \mathcal{I} , is an assignment of truth values to ground (variable-free) atoms. Thus under an interpretation any closed formula has a particular truth value. In the sequel, we will identify an interpretation with the set of atoms true under the interpretation. The standard definition of an interpretation in predicate logic is a structure which includes the universe. Here we separate the two and take the universe (and the sorts) as given. This is motivated below. An interpretation \mathcal{I} satisfies a closed formula P ,