PaperlayerView exact revision on arXiv

Source-linked AI summary

Causality-Guided Adaptive Interventional Debugging

Anna Fariha, Suman Nath, Alexandra Meliou

arXiv:2003.09539v3cs.DBcs.SE

TL;DR

Intermittent nondeterministic bugs are hard to reproduce, and tracing can disrupt the timing that lets them manifest. AID combines statistical debugging, causal analysis, fault injection, and group testing to identify root causes and explain failure paths; it did so across six real-world applications with fewer interventions than adaptive group testing.

  • Problem

    Nondeterministic bugs can appear only rarely, making them difficult to reproduce; tracing overhead can interfere with the timing and scheduling needed for them to manifest.

    Source: §1 · p. 1

  • Method

    AID identifies discriminative predicates, uses their temporal properties to build an approximate causal DAG, then intervenes on selected predicates to refine causal relationships.

    Source: §1 · p. 2

  • Results

    Across six real-world applications, AID identified root causes and developer-consistent explanations with significantly fewer interventions than traditional adaptive group testing.

    Source: §1 · p. 2

  • Takeaways & Limitations

    AID's causal paths provide more interpretable explanations of program failures than statistical debugging's potential causes alone.

    Source: §1 · p. 2, §9 · p. 12

    If the true root cause is not represented by an available, safely intervenable predicate, AID identifies the closest intervenable predicate causally related to the failure.

    Source: §4 · p. 4

Abstract

from arXiv · show

Runtime nondeterminism is a fact of life in modern database applications. Previous research has shown that nondeterminism can cause applications to intermittently crash, become unresponsive, or experience data corruption. We propose Adaptive Interventional Debugging (AID) for debugging such intermittent failures. AID combines existing statistical debugging, causal analysis, fault injection, and group testing techniques in a novel way to (1) pinpoint the root cause of an application's intermittent failure and (2) generate an explanation of how the root cause triggers the failure. AID works by first identifying a set of runtime behaviors (called predicates) that are strongly correlated to the failure. It then utilizes temporal properties of the predicates to (over)-approximate their causal relationships. Finally, it uses fault injection to execute a sequence of interventions on the predicates and discover their true causal relationships. This enables AID to identify the true root cause and its causal relationship to the failure. We theoretically analyze how fast AID can converge to the identification. We evaluate AID with six real-world applications that intermittently fail under specific inputs. In each case, AID was able to identify the root cause and explain how the root cause triggered the failure, much faster than group testing and more precisely than statistical debugging. We also evaluate AID with many synthetically generated applications with known root causes and confirm that the benefits also hold for them.

1. INTRODUCTION

Runtime nondeterminism makes intermittent failures difficult to reproduce, while statistical debugging can leave developers with many correlated predicates and no causal explanation. AID combines statistical debugging, causal analysis, fault injection, and group testing to identify root causes and explain how they lead to failure.

1. INTRODUCTION

  • Intermittent concurrency bugs may appear only under rare thread interleavings, and recording or tracing can interfere with those timings.Such bugs can be difficult to reproduce even with the same input and environment.Source: §1 · p. 1
  • Statistical debugging can return many correlated predicates without identifying the true cause or explaining how a predicate leads to failure.In the Npgsql example, it identified 14 predicates, of which only three were causally related to the error.Source: §1 · p. 1
  • A Npgsql data race on an array index can cause an out-of-bounds access and exception that crashes the application.The race occurs only under a particular interleaving of racing threads.Source: §1 · p. 1
  • AID combines statistical debugging, causal analysis, fault injection, and group testing to identify root causes and build causal explanations through predicate interventions.Temporal properties first form an approximate causal DAG, which AID refines through interventions under counterfactual causality and a single-root-cause assumption.Source: §1 · p. 2
  • AID can identify root-cause and explanation predicates with significantly fewer intervention rounds than adaptive group testing.Each round requires rerunning the application with fault injection, making fewer rounds useful in practice.Source: §1 · p. 2
  • Across six real-world applications, AID identified root causes and explained failures faster than adaptive group testing and more precisely than statistical debugging.The reported benefits also held for synthetically generated applications with known root causes.Source: §1 · p. 2

2. BACKGROUND AND PRELIMINARIES

The background introduces predicate-based statistical debugging, counterfactual causality and interventions, fault injection, and group testing as foundations for AID.

Statistical Debugging

  • Statistical debugging logs runtime predicates across successful and failed executions, then identifies predicates statistically associated with failure.Discriminative predicates capture behaviors that distinguish failed from successful executions.Source: Statistical Debugging · p. 2

Causality

  • The paper focuses on counterfactual causality: C causes E if E would not occur unless C occurs.Interventions force variables to particular values while leaving other controlling mechanisms unperturbed; the analysis targets fully discriminative predicates to exclude trivial program invariants.Source: Causality · pp. 2–3

Fault Injection

  • Fault injection changes application behavior to intervene on predicates, such as repairing a null return or preventing a data race with delay or synchronization.The examples show interventions that make a predicate match its successful-execution behavior.Source: Fault Injection · p. 3

Group Testing

  • Group testing simultaneously intervenes on groups of predicates to identify those that cause failure while minimizing the number of tests.In adaptive group testing, each group is chosen after observing earlier test results; its stated upper bound is O(D log N) when D < N log N.Source: Group Testing · p. 3

3. AID OVERVIEW

AID targets applications that fail intermittently under the same inputs, using predicate logs to find root causes and construct explanations. Its predicate selection and interventions rely on assumptions about discriminativeness and intervention safety.

3. AID OVERVIEW

  • AID uses predicate logs to identify fully discriminative predicates, infer possible causal links from temporal precedence, and refine the resulting DAG through interventions.The refinement aims to discover the root cause and the path of predicates leading to failure.Source: §3 · p. 3

3.1 AID Predicates

  • AID requires the initial predicate set to contain a root-cause predicate, and its predicate design is otherwise orthogonal to the framework.The paper uses predicates from existing statistical-debugging techniques, particularly those for concurrency bugs.Source: §3.1 · p. 3
  • AID extracts predicate logs by instrumenting executions, recording runtime trace details, and evaluating predicates at execution points across repeated runs.The logs are labeled as successful or failed executions.Source: §3.1 · p. 3
  • Conjunctive causes can be represented with compound predicates, but AID focuses on counterfactual causality and does not support disjunctive root causes.A and B together can be encoded as a fully discriminative compound predicate even when each alone is not.Source: §3.1 · pp. 3–4

3.2 AID Interventions

  • AID intervenes by changing predicate values to match successful executions, often through delays or synchronization that alter timing and thread scheduling.Return-value or exception-handling interventions can have side effects; AID limits these to methods developers identify as not changing application state, and excludes interventions judged unsafe.Source: §3.2 · p. 4

4. APPROXIMATING CAUSALITY

AID uses predicates’ temporal precedence to construct an approximate causal DAG (AC-DAG). Because precedence is necessary but not sufficient for causality, the graph can include noncausal edges that later interventions prune.

4. APPROXIMATING CAUSALITY

  • AID treats repeated executions of a statement as separate instances, preserving temporal precedence as an over-approximation of causality even across loops, recursion, or repeated calls.The instances are distinguished by their relative order of appearance and mapped to separate predicates.Source: §4 · p. 4
  • The AC-DAG connects predicates when one temporally precedes the other in all logs where both appear, so it over-approximates causal relationships.Temporal precedence is necessary but not sufficient for causality, so some graph edges may not be truly causal.Source: §4 · p. 4
  • The AC-DAG includes all fully discriminative predicates that are safe to intervene on, but may omit a root cause absent from the available predicates.If the true cause is not represented, AID identifies the closest intervenable predicate that is causally related to the failure.Source: §4 · p. 4
  • AID uses computer clocks for precedence, but limited clock granularity and unsynchronized clocks across cores or machines can reduce precision.The passage notes that logical clocks such as Lamport’s Clock can address these issues.Source: §4 · p. 4
  • For time-window predicates, AID uses predicate-specific rules to resolve precedence when intervals overlap.For slow-running predicates, end-time determines precedence; for late-start predicates, start-time does.Source: §4 · p. 4
  • Any precedence heuristic that avoids cycles can be used; conservative heuristics may add false-positive edges, which interventions later prune.Source: §4 · p. 5

5. CAUSAL INTERVENTION

AID refines an approximate causal DAG through interventions to identify the failure’s causal path. It reduces intervention costs through adaptive predicate selection, grouped interventions, and pruning.

5. CAUSAL INTERVENTION

  • The intervention algorithm refines the AC-DAG to discover the causal path, grouping interventions and pruning predicates based on their outcomes.The section proceeds from the problem and assumptions to an example, pruning strategies, and the causality-guided group intervention algorithm.Source: §5 · p. 5

5.1 Problem Definition and Assumptions

  • AID assumes one root-cause predicate and a fixed sequence of effects; disjoint causal routes are reduced to their shared fully-discriminative predicates.AID seeks a maximal chain from the root cause to the failure predicate.Source: §5.1 · pp. 5–6

5.2 Illustrative Example

  • In the example, AID identifies P1 as the root cause and derives P1 → P2 → P11 → F in 8 interventions, versus 11 naïvely.Intervening on P2 prunes P7 without a direct intervention; intervening on P3 removes P3 and P10 from the causal path.Source: §5.2 · p. 6

5.3 Predicate Pruning

  • Interventional pruning removes an intervened predicate if failure persists, and can prune other predicates only when they are not ancestors of the intervention target.For eligible predicates, pruning uses a counterfactual violation between the predicate and failure.Source: §5.3 · p. 6

5.4 Causality-guided Intervention

  • GIWP divides predicates by topological order, intervenes on groups, and uses failure outcomes to identify causes while pruning spurious predicates.It recurses when an intervention prevents failure and a group has multiple predicates; it stops when all predicates are classified.Source: §5.4 · p. 7

Branch Pruning

  • Branch pruning uses junctions to identify independent branches for group intervention, removing branches not connected to failure and reducing the AC-DAG to a chain.Intervening on a branch requires intervening on all its disjunctive predicates.Source: Branch Pruning · pp. 7–8

6. THEORETICAL ANALYSIS

The theoretical analysis studies how many interventions AID needs to identify causal predicates. It frames the analysis using group testing and compares AID with Traditional Adaptive Group Testing.

6. THEORETICAL ANALYSIS

  • The analysis considers information-theoretic lower bounds and lower and upper bounds on interventions required by AID versus Traditional Adaptive Group Testing.Its target is identifying all predicates causally related to the failure.Source: §6 · p. 8
  • The supplied analysis passages state the bounds and comparison being studied but provide no bound values or comparative outcome.No result values are given in these passages.Source: §6 · p. 8
  • The group-testing framing models N predicates as items, with D causal predicates treated as faulty items to identify.The paper distinguishes causal predicates from group testing’s faulty predicates because group testing does not meaningfully reason about causality.Source: §6 · p. 8

2 Branch-Prune (G, F)

AID uses the AC-DAG’s causal-path structure to prune candidate predicates and reduce intervention search relative to group testing. The analysis characterizes this reduction in search space and intervention bounds, including the assumptions under which AID’s upper bound is lower than TAGT’s.

2 Branch-Prune (G, F)

  • TAGT requires O(D log N) interventions under D < N log N; otherwise, intervening on one predicate at a time is preferable.AID also uses topological order and causal relationships to prune predicates beyond those intervened on.Source: §2 · p. 8

6.1 Search Space

  • For six predicates on two branches, CPD’s search space is 15 candidates, versus 64 for GT; horizontal expansion is additive, while vertical expansion is multiplicative.AID uses the AC-DAG to exclude cross-path candidates.Source: §6.1 · p. 9

6.2 Lower Bound of Number of Interventions

  • CPD’s lower bound on interventions is reduced relative to GT when each group intervention discards at least one predicate, and decreases as more predicates are discarded.The analysis does not claim that AID attains this lower bound.Source: §6.2 · p. 9

6.3.1 Branch Pruning

  • With branch pruning, AID’s upper bound is J log T + D log NM, below TAGT’s D log T + D log NM when J < D.The bound assumes at most T branches at each of J junctions and at most NM predicates on any path.Source: §6.3.1 · p. 10

6.3.2 Predicate Pruning

  • With predicate pruning, AID’s intervention bound decreases as more predicates are discarded per causal-predicate discovery; when S2 = 1, it corresponds to TAGT without pruning.The theorem gives an upper bound conditioned on discarding at least S2 predicates per discovery.Source: §6.3.2 · p. 10

7. EXPERIMENTAL EVALUATION

Across six real-world applications, AID identified root causes and produced explanations consistent with developer accounts, using significantly fewer interventions than TAGT; SD produced many non-causal predicates. Synthetic tests likewise show fewer interventions with AID’s pruning and topological ordering.

7.1 Case Studies of Real-world Applications

  • Across six real-world applications, AID identified root causes and generated explanations, while requiring significantly fewer interventions than TAGT; SD produced many non-causal predicates.Figure 7 summarizes the real-world case-study results.Source: §7.1 · p. 10, Figure 7 · p. 11

7.1.1 Data race in Npgsql

  • In Npgsql, AID identified the data race and a developer-consistent failure explanation in 5 intervention rounds, versus TAGT’s 11 worst-case interventions.SD found 14 discriminative predicates but did not identify the root cause or explain the failure.Source: §7.1.1 · p. 10

7.1.2 Use-after-free in Kafka

  • In Kafka, AID used 17 interventions to identify the root cause and a five-predicate causal path; TAGT would require 33 worst-case interventions.The path explains how a child thread calls a method on an object after the main thread disposes it, causing an exception.Source: §7.1.2 · pp. 10–11

7.1.3 Timing bug in Azure Cosmos DB application

  • For the Azure Cosmos DB application, AID used 15 interventions to produce a seven-predicate explanation, versus TAGT’s 42 worst-case interventions.SD identified 64 discriminative predicates.Source: §7.1.3 · p. 11

7.1.4 Bugs in proprietary software

  • In three proprietary applications, developers confirmed AID’s identified root causes and explanations; AID also required significantly fewer interventions than TAGT in each case.The identified causes were a random number collision, an event order violation, and a race condition.Source: §7.1.4 · p. 11, Figure 7 · p. 11

7.2 Sensitivity Analysis

  • In synthetic tests, topological ordering and predicate and branch pruning each reduced intervention needs; in one worst-case setting, TAGT required up to 217 interventions while AID required at most 52.The benchmark generated 500 applications per parameter setting, with MAXt ranging from 2 to 40.Source: §7.2 · p. 11

8. RELATED WORK

Related work addresses failure diagnosis through causal analysis, statistical debugging, tracing, interventions, and program slicing. The paper distinguishes AID by its focus on intervention-guided causal paths that explain intermittent failures.

Causal inference and root-cause analysis

  • Attariyan et al. report likely root causes without further causal connections to performance anomalies, while observational causal methods [18] may miss intermediate explanation predicates.The text notes that observational approaches may not meet exchangeability and positivity requirements.Source: §8 · p. 12

Explanation-centric approaches

  • Explanation-centric methods for data errors and binary outcomes, and Viska for system performance differences, do not find causal paths explaining intermittent concurrency failures.Source: §8 · p. 12

Statistical debugging

  • Statistical debugging approaches rank likely causes but do not separate correlated predicates from causal ones or explain how causes lead to failures.Source: §8 · p. 12

Execution tracing

  • Execution tracing algorithms by Ball et al. can supply predicates for AID, despite having been developed for path profiling.Source: §8 · p. 12

Fault injection and group testing

  • AID’s interventions verify causal links among runtime predicates, unlike fault-injection techniques that choose faults based on whether they can occur in practice.Adaptive group testing [1] [9] [40] does not account for extra information a group test may reveal about causal paths.Source: §8 · p. 12

Program analysis and slicing

  • Control-flow methods do not model causal connections among predictors and failures; slicing methods face execution-trace or limited-comparison constraints.Differential slicing requires complete traces, while dual slicing omits compound predicates and considers only one successful and one failed execution.Source: §8 · p. 12

9. CONCLUSIONS

The conclusion presents AID as an efficient and effective framework for discovering root causes and causal paths that explain concurrent-program failures. The appendix describes post-execution predicate design and the instrumentation granularity used.

9. CONCLUSIONS

  • AID combines statistical debugging, causal analysis, fault injection, and group testing to discover root causes and causal paths explaining program failures.The authors identify multiple root causes, multiple causal paths, and multiple failure types as future directions.Source: §9 · p. 12

A. PROGRAM INSTRUMENTATION

  • AID separates instrumentation from predicate extraction, allowing predicates to be designed after traces are collected, including custom relations informed by domain expertise.Source: A. PROGRAM INSTRUMENTATION · p. 14
  • Method-call instrumentation was sufficient for the reported purpose; its sparse granularity meant sampling was not used.Source: A. PROGRAM INSTRUMENTATION · p. 14

B. PREDICATE EXTRACTION AND FAULT INJECTION

AID extracts predicates from instrumented execution traces and intervenes on discriminative predicates using fault injection. The section also motivates the simple-predicate assumption with findings from studies of real-world concurrency bugs.

B. PREDICATE EXTRACTION AND FAULT INJECTION

  • AID derives predicates and their precision and recall from instrumented execution traces, then uses fault injection to intervene on discriminative predicates.The traces include successful and failed executions; Figure 9 illustrates the extraction and intervention pipeline for an Npgsql bug.Source: B. PREDICATE EXTRACTION AND FAULT… · p. 14, Figure 9 · p. 15
  • AID can change method inputs or returns, trigger exceptions, or alter timing and thread interleavings to intervene on predicates.For return-value intervention, it adds an optional parameter and a conditional return to each function; a data-race predicate can be disabled by delaying an access or locking the shared variable.Source: B. PREDICATE EXTRACTION AND FAULT… · pp. 14–15

C. REAL-WORLD CONCURRENCY BUG CHARACTERISTICS

  • Prior studies report that most concurrency root causes fit reasonably simple single predicates, including common atomicity, ordering, single-variable, and two-thread patterns.Reported findings include 97% of non-deadlock concurrency bugs covered by two simple patterns and 96% involving no more than two threads.Source: C. REAL-WORLD CONCURRENCY BUG… · p. 15

D. PROOF OF THEOREM 2

The proof bounds the number of interventions by tracking how much information remains after interventions.

D. PROOF OF THEOREM 2

  • The proof begins by counting information obtained after the first intervention.The supplied passage does not state the amount of information.Source: D. PROOF OF THEOREM 2 · p. 15
  • With m interventions, the proof requires the remaining information to be at most zero once all information has been retrieved.Source: D. PROOF OF THEOREM 2 · p. 15
  • The proof turns that condition into an inequality involving a factorial count and introduces a condition for N to be small.Source: D. PROOF OF THEOREM 2 · p. 15

E. PROOF OF THEOREM 3

The proof bounds the required interventions by counting predicate discards across causal-predicate discoveries.

E. PROOF OF THEOREM 3

  • At least S2 predicates are discarded during each discovery, so the proof computes an upper bound across D causal predicates.Source: E. PROOF OF THEOREM 3 · p. 15
Loading 2003.09539v3…