Backward Responsibility in Transition Systems Beyond Safety
Christel Baier, Rio Klatt, Sascha Klüppelholz, Johannes Lehmann · 2025
Read Backward Responsibility in Transition Systems Beyond Safety by Christel Baier, Rio Klatt, Sascha Klüppelholz, Johannes Lehmann (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-2506-05192.txt.
Introduction
When a software system fails, engineers want to know which states of the system share the blame. Christel Baier and co-authors study that question in 2025 under the name backward responsibility, extending earlier work that covered only safety failures.
Responsibility is scored with Shapley values borrowed from game theory, spread over the states of a transition system. The authors pin down tight complexity bounds for computing the scores under reachability, Büchi, and parity goals, three standard ways a run can count as good. For the Büchi case they give a fast method to find every state with a positive score. A refinement algorithm, guided by heuristics, handles systems too large for exact methods.
Catalog record
| CREATOR | Christel Baier, Rio Klatt, Sascha Klüppelholz, Johannes Lehmann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-05192
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Backward Responsibility in Transition Systems Beyond Safety Christel Baier, Rio Klatt, Sascha Klüppelholz, Johannes Lehmann Abstract As the complexity of software systems rises, methods for explaining their behaviour are becoming ever-more important. When a system fails, it is critical to determine which of its components are responsible for this failure. Within the verification community, one approach uses graph games and the Shapley value to ascribe a responsibility value to every state of a transition system. As this is done with respect to a specific failure, it is called backward responsibility . This paper provides tight complexity bounds for backward responsibility for reachability, Büchi and parity objectives. For Büchi objectives, a polynomial algorithm is given to determine the set of responsible states. To analyse systems that are too large for standard methods, the paper presents a novel refinement algorithm that iteratively computes responsibility and demonstrates its utility with a prototypical implementation. 1 Introduction With modern computational systems becoming more complex and simultaneously less transparent to their users, there is growing demand for explaining which internal mechanisms lead to the exhibited behaviour of such systems. This is particularly true for cyber-physical systems and AI systems that are capable of solving complex tasks opaquely while interacting closely with their environment and users. Supporting perspicuity throughout the entire system lifecycle, from design-time over execution-time to inspection-time, therefore becomes an important feature that can improve all processes and workflows where humans are in-the-loop, e.g. maintenance, debugging and system repair. Explainable AI is one example of a recent and rapidly growing research area that has emerged driven by the need for transparency, trust, and accountability in AI systems. Orthogonal to explainable AI are recent trends towards explainable Formal Methods. Among others, these techniques aim to augment verification results in terms of mathematical concepts that explicate why a system model fulfils or violates its specification. Examples of such concepts are mathematical certificates like inductive invariants or deductive proofs [ MannaPnueliBook ] if the model satisfies its specification and counterexamples generated by a model checker or theorem prover in case of a specification violation (see e.g. [ Chockler2016Causality , FromVerificationToCausalityBaseExplications ] for an overview). In the taxonomy of [ ForwardBackward ] , the former are examples for forward-looking explications that take all possible behaviors of a model into account, while counterexamples and explications derived from them are backward-looking in the sense that they aim to explain a specific error scenario. Counterexamples for regular linear-time properties are finite prefixes of computations, representing an ultimately periodic path that starts in an initial state and eventually enters a loop that is repeated ad infinity and that does not satisfy the property. Despite various techniques to generate short counterexamples [ Gastin2004MinimizationOfCounterexamples , Gastin2007MinimalCounterexample , Hansen2006MinimalCounterexamples ] , counterexamples can still be very long, which makes it difficult to identify the reason for the misbehavior. Motivated by this observation, multiple approaches have been proposed to explain counterexamples in terms of causality-based concepts or quantitative notions that measure the degree of responsibility of states or system components. Some of these approaches rely on Halpern and Pearl’s notions of actual causality and interventions [ HalpernPearlCauses , HalpernPearlExplanations ] . The idea is to define causes as minimal sets of items that need to be modified (e.g. switching the truth value of atomic propositions in states) to avoid specification violations. The degree of responsibility of an individual item is then defined as 1/n where n is the size of a smallest cause containing that item. This approach has been used to define the degree of responsibility of states in the forward-looking [ chockler2008causes ] and the backward-looking [ Beer2009ExplainingCounterexamplesCausality ] setting. Halpern and Pearl’s notion of causality is also at the heart of [ Koelbl2020DynamicCauses , Caltas2018CausalityForGeneralLTL , LeitnerFischer2014SpinCause , LeitnerFischer2013CausalityChecking ] . Other approaches to identify causes in counterexamples rely on Stalnaker’s and Lewis’ semantics of counterfactuals in terms of most similar computations that avoid the error scenario. This is formalised by distance functions on computations [ Groce2006DistanceMetrics , ParreauxCounterfactualCausalityDistanceFunctions ] . Delta debugging [ ZellerDeltaDebugging ] uses a divide-and-conquer technique to generate the most similar passing run. The difference between passing and failing runs can also be used statistically to assess which components of a program are most suspicious [ LandsbergStatisticalFaultLocalisation ] . Another direction to explain counterexamples relies on Shapley values that have been introducted to measure the impact of individual players on the outcome of cooperative games [ ShapleyValueOriginal ] 1 1 1 A recent discussions on the Shapley value can be found in [ ShapleyHandbook , ShapleyValueHandbook ] . . Such Shapley-value based approaches have been first proposed for stochastic multi-player game structures [ GameTheoreticResponsibility ] and for the forward-looking approach for temporal properties in transition systems [ ImportanceValuesTL ] . In recent work, these approaches have been adapted to the backward-looking perspective by explaining counterexamples for safety properties [ BackwardRespTS ] . This has been extended by lifting responsibility from individual states to higher-level concepts such as components, modules and actors [ BackwardRespTS ] . The current paper is in the line of these approaches, mostly of [ BackwardRespTS ] . Given a transition system as operational model, a temporal objective representing the specification and a counterexample path, a state s has responsibility for the outcome if there is a set of states C such that C is not sufficient for satisfying the objective in the induced game, while C\cup\{s\} is, i.e. s is responsible whenever it made a difference in whether the objective is satisfied. Responsibility is then quantified using the Shapley value. Contribution. Our contribution is threefold. First, we provide complexity results for two decision problems (positivity and threshold) as well as the computation problem covering optimistic and pessimistic backward responsibility with reachability, Büchi and parity objectives ( Section 4 ). This includes a polynomial-time algorithm that decides the optimistic positivity problem for Büchi objectives ( Algorithm 1 ). Secondly, we present a refinement algorithm (cf. in Section 5 ) that allows for computing the set of states with positive responsibility. Thirdly, we provide a new version of our existing responsibility tool [ BackwardRespTS ] extended with the refinement algorithm and the new objective classes. experimentally evaluates the scalability and performance of the refinement algorithm and compares several heuristics. We show that for large models with few responsible states, the refinement algorithm can improve performance by several orders of magnitude. The proofs omitted for in the main paper are given in the appendix. 2 Preliminaries We briefly present the notations for transition systems, games on graphs and Shapley values. For more details, see e.g. [ ModelCheckingBook ] . Transition systems. A transition system is a tuple \mathcal{T}=(S,\mathord{\rightarrow},s_{\mathit{init}}) , where S is a finite set of states , \mathord{\rightarrow}\subseteq S\times S is the transition relation (and we write s\rightarrow t for (s,t)\in\mathord{\rightarrow} ) and s_{\mathit{init}}\in S is the initial state . A run on \mathcal{T} is an infinite sequence of states \rho=\rho_{0}\rho_{1}\ldots\in S^{\omega} , where \rho_{0}=s_{\mathit{init}} and for all i\in\mathbb{N} , we have \rho_{i}\rightarrow\rho_{i+1} . A run \rho is lasso-shaped if there are finite state sequences u,v\in S^{\ast} with \rho=uv^{\omega} and a lasso-shaped run is simple if every state occurs at most once in v and no state from