PaperlayerView exact revision on arXiv

Source-linked AI summary

Inforence: Effective Fault Localization Based on Information-Theoretic Analysis and Statistical Causal Inference

Farid Feyzi, Saeed Parsa

arXiv:1712.03361v1cs.SE

TL;DR

Spectrum-based fault localization considers statements in isolation and may miss failures caused by interactions among statements. Inforence uses information-theoretic analysis to select interdependent statements, constructs cause-effect chains, and applies statistical causal inference to rank them. Inforence outperformed many distinguished methods; on gzip, examining 4% of the code located the first bug in 82 (68.33%) of 120 multi-bug versions in the best cases.

  • Problem

    Spectrum-based fault localization considers statements in isolation and may miss failures caused by interactions among statements.

    Source: §1 · p. 1

  • Method

    Inforence uses information-theoretic analysis to select interdependent statements, constructs cause-effect chains, and applies statistical causal inference to rank them.

    Source: §1 · p. 2, §3.2.2 · p. 7, §3.3 · p. 10

  • Results

    Inforence outperformed many distinguished methods; on gzip, examining 4% of the code located the first bug in 82 (68.33%) of 120 multi-bug versions in the best cases.

    Source: §4.3.2 · p. 21, §7 · p. 25

  • Takeaways & Limitations

    Cause-effect chains provide failure context by connecting selected bug-related statements according to program structure.

    Source: §1 · p. 2, §7 · p. 25

    The evaluation assumes programmers identify a fault whenever they examine a faulty statement, which may understate the statements needed in practice.

    Source: §6 · p. 25

Abstract

from arXiv · show

In this paper, a novel approach, Inforence, is proposed to isolate the suspicious codes that likely contain faults. Inforence employs a feature selection method, based on mutual information, to identify those bug-related statements that may cause the program to fail. Because the majority of a program faults may be revealed as undesired joint effect of the program statements on each other and on program termination state, unlike the state-of-the-art methods, Inforence tries to identify and select groups of interdependent statements which altogether may affect the program failure. The interdependence amongst the statements is measured according to their mutual effect on each other and on the program termination state. To provide the context of failure, the selected bug-related statements are chained to each other, considering the program static structure. Eventually, the resultant cause-effect chains are ranked according to their combined causal effect on program failure. To validate Inforence, the results of our experiments with seven sets of programs include Siemens suite, gzip, grep, sed, space, make and bash are presented. The experimental results are then compared with those provided by different fault localization techniques for the both single-fault and multi-fault programs. The experimental results prove the outperformance of the proposed method compared to the state-of-the-art techniques.

1 Introduction

Inforence targets fault localization cases where combinations of statements, rather than isolated statements, contribute to program failure. It combines information-theoretic selection, causal ranking, and program structure to identify and connect suspicious statements.

1 Introduction

  • Inforence addresses a limitation of spectrum-based fault localization: treating statements individually can miss failures caused by statement interactions.The introduction motivates modeling the combinatorial effect of statements in failing and passing executions.Source: §1 · p. 1
  • The method uses information-theoretic relevance, interdependence, and redundancy analysis to select groups of statements that may jointly affect failure.It then uses statistical causal inference to estimate selected statements’ failure-causing effects.Source: §1 · p. 2
  • Inforence links selected statements into cause-effect chains using program structure and ranks chains by causal effect on failure.The stated contributions also include evaluation across programs ranging from 141 to 59,864 LOC against representative spectrum-based techniques.Source: §1 · p. 2

2 Motivating example

The motivating example shows how two related statements can jointly trigger failure even when neither statement alone is a strong fault indicator. Inforence identifies their grouping effect and links them using program dependencies.

2 Motivating example

  • In the calculator example, incorrect output occurs only when S9 and S15 are both executed, illustrating a failure caused by a statement combination.The program has six passing and six failing test cases; the table shows their statement coverage.Source: §2 · p. 3, Table 1 · p. 3
  • Inforence analyzes relevance, interdependence, and redundancy to identify joint causes, then links S15 to S9 through their data dependency in the program-dependence graph.The example illustrates coincidental correctness as a challenge for isolated statement analysis.Source: §2 · pp. 3–4
  • Compared spectrum-based techniques rank S6 highest, whereas Inforence identifies faulty S9 and S15 as jointly relevant in the example.The compared techniques’ scores for S9 and S15 are weaker because their individual presence in failing runs is lower than S6’s.Source: §2 · pp. 3–4, Table 1 · p. 3

3 The method overview

The method overview describes how Inforence analyzes passing and failing executions to select failure-associated statements, connect interdependent candidates into cause-effect chains, and prioritize likely causes using estimated causal effects, with propensity-score matching to control confounding.

3 The method overview

  • The framework has preprocessing, information-theoretic analysis, and causal analysis/fault locating modules; it takes a buggy program and test suite as input.For dynamic slices, it uses the framework introduced in to instrument and execute the program and collect dynamic dependence data.Source: §3 · p. 4

3.1 Preprocessing stage

  • Backward dynamic slices of failing outputs narrow the search space to candidate statements instead of using all program statements to build spectra.The spectra are constructed using slices from passing and failing test cases; incorrect outputs with multiple values are handled by taking the union of their backward slices.Source: §3.1 · pp. 4–5

3.2 Information theoretic analysis stage

  • The information-theoretic stage targets groups of interdependent statements that collectively cause failure, then chains selected statements by static structure to provide failure context.These combined causes are distinguished from multiple independent bugs: the statements collectively contribute to program failure.Source: §3.2 · pp. 5–6

3.2.1 Preliminaries of information theory

  • Because conventional feature selection can discard correlated statements that are weak individually, Inforence evaluates statement relevance, redundancy, and interdependence together.It uses generalized entropy for mutual information, a linearized approximation for computational tractability, and symmetric uncertainty to normalize mutual information to a 0-to-1 range.Source: §3.2.1 · p. 6, §3.2.2 · p. 7
  • The selection algorithm iteratively chooses statements using their relevance and dynamically updated weights, then uses static data/control dependencies to construct cause-effect chains until threshold δ is exceeded.The weights reflect correlation with the selected subset, and δ is user-specified.Source: §3.2.2 · pp. 7–8
  • A class-proximity function distinguishes statements associated with failed executions from those associated with passing executions, since discriminative power alone does not establish fault relevance.The function uses failed- and passed-test coverage ratios, adjusted for noise in fault-failure correlation measurements.Source: §3.2.2 · p. 8
  • Feature selection iteratively selects statements by relevance to termination, updates their weights for interdependence and redundancy with selected statements, and links selected statements into chains.Source: §3.2.2 · pp. 9–10

3.3 Statistical causal inference of failure cause-effect

  • Inforence estimates causal effects for statements in PDG-linked cause-effect chains and ranks chains to address multiple chains, long chains, and combined-cause bugs.Restricting inference to candidate statements in the chains reduces the costs of collecting, storing, and analyzing execution profiles.Source: §3.3 · pp. 10–11

3.3.1 Identification of confounding variables

  • Inforence treats a statement’s direct program-dependence predecessors as confounders in a causal DAG, representing each predecessor by whether it is covered in an execution.Source: §3.3.1 · p. 11

3.3.2 Matching executions and estimating casual effects

  • For each chain statement, Inforence fits a logistic propensity model from coverage and confounders, uses optimal full matching, discards unmatched executions, and estimates failure-causing effects.Matching aims to balance treatment and control executions on propensity scores to reduce confounding bias.Source: §3.3.2 · pp. 12–13

4 Empirical study

The empirical study compares Inforence with fault-localization techniques across seven program sets and evaluates single- and multiple-bug settings, failure-context chains, and efficiency. Its results show strong but setting-dependent localization performance, with separate measures for code inspection and chain quality.

4 Empirical study

  • The study covered seven program sets and 13 subject programs, ranging from small Siemens programs to Bash at more than 59,000 lines of code.The evaluation also considered scalability on large programs.Source: §4 · pp. 13–14

4.1 Evaluation metrics

  • Effectiveness was assessed with EXAM score and average statements examined, while cause-effect chains were evaluated with precision, recall, and F-measure.EXAM measures the percentage of statements examined before reaching the first faulty statement.Source: §4.1 · p. 14

4.2 Fault localization techniques used in comparisons

  • Comparisons included spectrum-based, feature-selection, causal, and genetic-programming techniques, including Dstar, Ochiai, Relief, and GP variants.The study used GP02, GP03, and GP19 as theoretically best genetic-programming-based comparators.Source: §4.2 · p. 14

4.3.1 Results on programs with a single bug

  • On Siemens, examining 10% of code located 77% of faults in the best case and 64% in the worst for Inforence, versus D-Star’s 64% and 52%.For single-bug programs, tied suspiciousness rankings were evaluated under both best- and worst-case inspection assumptions; on Space, Inforence’s worst-case average was 65.41 statements versus O’s 62.89.Source: §4.3 · p. 14, §4.3.1 · p. 15, Figure 2 · p. 16

4.3.2 Results on programs with multiple bugs

  • The multi-bug evaluation combined faulty versions into 600 programs with three to six bugs and applied a one-bug-at-a-time procedure to assess locating the first bug.Thirty distinct versions were created for each of gzip, grep, sed, make, and space.Source: §4.3.2 · p. 18
  • For gzip multi-bug versions, inspecting 4% of code let Inforence locate the first bug in 82 of 120 versions (68.33%) in best cases and 77 (64.16%) in worst cases.At the same inspection level, Crosstab located 96 versions (80%) in best cases and 75 (62.5%) in worst cases.Source: §4.3.2 · p. 21

4.3.3 Providing failure context

  • Inforence supplies failure context as cause-effect chains, whose quality was evaluated using precision, recall, and F-measure.The paper notes that one chain may achieve precision one while recall remains low when other chains exist.Source: §4.3.3 · p. 21

4.3.4 Complexity analysis

  • Relevance calculation is linear in candidate statements; iterative selection has a stated worst case when all candidates are selected, while a smaller threshold δ gives O(nδ) complexity.The analysis compares runtime overhead with Ochiai and Baah’s causal approach.Source: §4.3.4 · p. 21, Table 11 · p. 22

5 Related Works

Related work spans machine-learning, spectrum-based, information-theoretic, and slicing-based fault localization. The reviewed approaches use different evidence and assumptions, and the paper notes that no spectrum-based technique is best in every scenario.

5 Related Works

  • Prior machine-learning approaches infer fault locations from coverage and test outcomes, using neural networks, SVMs, and combinations with feature selection or control-flow analysis.Wong et al. proposed a back-propagation network, followed by an RBF-network approach.Source: §5 · p. 22
  • Information-theoretic work includes information gain for comparing similarity measures, entropy-based test prioritization, and feature selection using divergence or mutual information,,.These approaches apply information theory to different stages of fault localization, including suspiciousness, test ordering, and statement selection.Source: §5 · p. 23
  • Spectrum-based approaches include DStar and Ochiai, while Naish et al. proposed techniques for single- and multiple-bug settings.Reported comparisons include Ochiai outperforming Tarantula and Naish et al.’s techniques outperforming Tarantula and Ochiai for single-bug programs.Source: §5 · p. 23
  • The review notes that no spectrum-based technique is optimal in every scenario, and that coverage assumptions used to rank formulas can fail in practice.Xie et al. assume a single fault and faulty statement, among other conditions; a small coverage reduction can affect theoretically best formulas.Source: §5 · pp. 23–24
  • Slicing-based methods use slices, critical-predicate switching, or value replacement, but may scale poorly and miss other faults or missing-code bugs.Some slicing techniques depend on a single failing execution; predicate switching and value replacement can also face scalability problems.Source: §5 · p. 24

6 Threats to validity

The authors identify limits on generalizing their empirical findings and on interpreting their evaluation measures as real-world localization costs. They also describe potential internal and construct validity threats.

6 Threats to validity

  • The findings may not represent all possible programs because fault types are diverse, and Inforence’s effectiveness varies across programs, bugs, and test cases.The evaluation spans varied programs, but the authors still caution against generalizing to every program.Source: §6 · p. 24
  • Internal validity may be affected by implementation errors, coverage-measurement tools, or execution environments such as compilers, operating systems, and hardware.The authors note that the open-source algorithm packages have been used by other researchers, providing confidence in their stability.Source: §6 · p. 24
  • The evaluation metrics may understate real manual effort because they assume programmers always recognize a fault when examining a faulty statement.If that assumption fails, the number of statements examined to identify a bug may increase.Source: §6 · p. 25

7 Concluding remarks

Inforence selects and reweights statements to account for group-level information, then uses causal inference to rank failure chains. The authors report that it outperforms many distinguished fault-localization methods.

7 Concluding remarks

  • Inforence starts with statements in backward dynamic slices and uses correlation ratio to adjust candidate weights according to their interdependence with selected statements.The method aims to identify groups whose combined discriminatory power exceeds that of their members considered individually.Source: §7 · p. 25
  • Inforence targets combinations of statements that traditional feature selection may overlook when their individual discriminatory power is weak.The conclusion frames the approach as revealing faults affected by combinations of program statements.Source: §7 · p. 25
  • Causal inference ranks cause-effect chains built from selected statements, and the authors report that Inforence outperforms many distinguished fault-localization methods.The authors describe the approach as scalable and cost-effective, with chains providing failure context.Source: §7 · p. 25
Loading 1712.03361v1…