Counterexample-Guided Abstraction Refinement for Generalized Graph Transformation Systems (Full Version)

Barbara König, Arend Rensink, Lara Stoltenow, Fabian Urrigshardt · 2025

Read Counterexample-Guided Abstraction Refinement for Generalized Graph Transformation Systems (Full Version) by Barbara König, Arend Rensink, Lara Stoltenow, Fabian Urrigshardt (2025) 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-2504-08617.txt.

Introduction

Barbara König, Arend Rensink, Lara Stoltenow, and Fabian Urrigshardt wrote this 2025 paper on proving that graph-based systems stay safe. A graph transformation system rewrites graphs by rules, and the question is whether bad states can ever be reached from a class of starting graphs. With endless possible states, the question cannot be settled by brute force.

The team use abstract interpretation to shrink the state space to a finite sketch. When the sketch reports a bad state, they check whether the example is real; if not, they sharpen the sketch and repeat. Bad and starting states are both stated in a rich logic of nested conditions. Though aimed at graph systems, the result is framed for reactive systems in general.

Catalog record

CREATORBarbara König, Arend Rensink, Lara Stoltenow, Fabian Urrigshardt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE318 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08617

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counterexample-Guided Abstraction Refinement for Generalized Graph Transformation Systems (Full Version) Barbara König, Arend Rensink, Lara Stoltenow, Fabian Urrigshardt Abstract This paper addresses the following verification task: Given a graph transformation system and a class of initial graphs, can we guarantee (non-)reachability of a given other class of graphs that characterizes bad or erroneous states? Both initial and bad states are characterized by nested conditions (having first-order expressive power). Such systems typically have an infinite state space, causing the problem to be undecidable. We use abstract interpretation to obtain a finite approximation of that state space, and employ counter-example guided abstraction refinement to iteratively obtain suitable predicates for automated verification. Although our primary application is the analysis of graph transformation systems, we state our result in the general setting of reactive systems. 1 Introduction One of the successful techniques to analyze systems with very large or infinite state spaces is abstract interpretation . This either under- or over-approximates the possible behaviours, reducing the state space to a manageable size (and also covering a set of potential initial states rather than just one) at the cost of precision: essentially, different states are regarded as the same not if they are for all intents and purposes equivalent, but if they are, in some precise sense, alike. If we want to check certain properties about the behaviour of the original system, such as the absence of errors in reachable states or the satisfaction of more refined temporal logic properties, this can be done on the abstracted state space instead; however, due to the imprecision, the answers obtained in this way may not be correct for the full state space. In particular, if the abstraction was an under-approximation, analysing whether an error state is reachable may yield false negatives (the answer no may be incorrect for the full, concrete state space); if it was an over-approximation, the analysis may yield false positives (the answer yes may be incorrect). Of these two, false positives can be detected more easily, since the answer yes to a question of the type “can an error state be reached” or “is there a trace with a certain temporal property” comes with a witness , being an actual trace in the abstract state space that reaches that error state or has that property. For historical reasons, such a witness is usually called a counterexample , even though in our narrative it is rather an example . We can then typically check whether such a counterexample actually exists in the full state space — a task that is feasible even if the full state space is infinite. If the counterexample does exist, the original yes answer was correct after all; if it does not exist (in which case it is called spurious ), we know that the original yes answer cannot be trusted; it may still be correct, but we do not know. The method of counter-example guided abstraction refinement (CEGAR) [ 9 , 20 ] builds upon this principle by relying on a notion of abstraction that can be tuned . In particular, two states are considered to be “alike” if they satisfy the same predicates. A spurious counterexample contains concrete evidence of where the original abstraction gives rise to “harmful” over-approximation: namely a trace in the abstract transition system leading to a state that does not rule out that a certain property \mathsf{Bad} (encoding some unwanted feature) holds, but which does not exist in the concrete state space. This check provides additional predicates, leading to a stronger notion of “alike”, which results in a new, refined abstraction in which at least this particular (spurious) counterexample no longer exists. We can then start over again using the new, refined, abstract state space, until we get either a no answer or a yes answer for which the counterexample is real, or we run out of time. This leads to the so-called CEGAR loop (see Figure 1 ). In the general case there is no guarantee that the loop will ever terminate (e.g. due to undecidability of the verification problem), but good results have still been achieved in practice with the development of verification tools based on CEGAR [ 7 , 2 , 1 ] . A related technique for proving correctness relies on finding an invariant I , which is a property that holds in the initial state and is preserved by all transitions, such that I entails \neg\mathsf{Bad} . In fact, the abstraction refinement procedure outlined above may be seen as a recipe for generating such an invariant. Start with a coarse initial abstraction Does the abstraction trace is real Refine the abstraction such that the spurious counterexample disappears violate property ? [formula] no Check whether violating trace is real yes (witness trace) trace is spurious successful verification! error found! Figure 1 : A schematic depiction of the CEGAR loop The contribution of this paper is to propose a variant of CEGAR in the spirit of reactive systems . This is a framework developed by Milner et al. [ 31 ] that subsumes graph transformation via double-pushout. We assume that the states are arrows in a suitable category, and transitions are generated by conditional rules that modify those objects using categorical operations. Our abstraction is based on so-called nested conditions (related to first-order logic) [ 41 , 17 ] , again defined relative to the category of choice, with a notion of satisfaction over the states. The predicates mentioned above take the shape of such nested conditions; the abstraction is driven by a finite set P of them. The abstraction of a state, or a set of states, is defined as the subset of elements of P that provably hold in that (set of) state(s). In previous work [ 4 ] , we have shown how to compute strongest postconditions and weakest preconditions for rules with application conditions, and this allows us to compute the abstract (over-approximating) transitions, as well as to check whether a counterexample found on the abstract level fails to exist on the concrete level, i.e., is spurious. Given a spurious counterexample, we can then refine the abstraction by augmenting P with the characteristic properties of all the (sets of) concrete states traversed by the counterexample. This refined abstraction is certain not to include that counterexample any more. A complication lies in the fact that the method outlined above at several points requires the computation of entailment among nested conditions. Depending on the underlying category, this is equivalent to entailment of First-Order Logic and hence undecidable; in practice, we are forced to rely on provable entailment (i.e., using available tooling), which is necessarily a weaker relation — or in the terminology above, may yield false negatives. Fortunately, though this introduces further imprecision in our abstraction, we show that this does not invalidate the method. A further contribution of this paper consists in a prototype implementation of this CEGAR method for a concrete base category, viz. that of graphs . Rules in this category are (essentially) double-pushout transformation rules, and the nested conditions correspond to ones studied before by [ 17 , 41 ] . We report some experiments. Unfortunately, the performance is such that only very small examples

Read the complete text