PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy Guided Spectrum Based Bug Localization Using Statistical Language Model

Saikat Chakraborty, Yujian Li, Matt Irvine, Ripon Saha, Baishakhi Ray

arXiv:1802.06947v1cs.SE

TL;DR

Bug localization can weaken when its single information source, especially test coverage, is inadequate. EnSpec combines spectrum-based suspiciousness with code entropy from a statistical language model, and the reported results show improved localization across benchmarks and languages. The approach remains dependent on test-suite adequacy, although its language-model component uses source code alone.

  • Problem

    Existing bug-localization techniques can suffer when their information source is inadequate, particularly when SBBL relies on weak test-suite coverage.

  • Method

    EnSpec combines code entropy from a statistical language model with spectrum-based suspiciousness using machine learning to rank suspicious lines.

  • Results

    EnSpec improves standard spectrum-based bug localization across the evaluated Defects4J and ManyBugs benchmarks and both Java and C projects.

  • Takeaways & Limitations

    Code entropy provides an additional information source that can make spectrum-based bug localization more robust when test-suite information is insufficient.

  • Takeaways & Limitations

    EnSpec still depends on test-suite adequacy because insufficient failing tests can hurt SBBL and therefore EnSpec’s performance.

Abstract

from arXiv · show

Locating bugs is challenging but one of the most important activities in software development and maintenance phase because there are no certain rules to identify all types of bugs. Existing automatic bug localization tools use various heuristics based on test coverage, pre-determined buggy patterns, or textual similarity with bug report, to rank suspicious program elements. However, since these techniques rely on information from single source, they often suffer when the respective source information is inadequate. For instance, the popular spectrum based bug localization may not work well under poorly written test suite. In this paper, we propose a new approach, EnSpec, that guides spectrum based bug localization using code entropy, a metric that basically represents naturalness of code derived from a statistical language model. Our intuition is that since buggy code are high entropic, spectrum based bug localization with code entropy would be more robust in discriminating buggy lines vs. non-buggy lines. We realize our idea in a prototype, and performed an extensive evaluation on two popular publicly available benchmarks. Our results demonstrate that EnSpec outperforms a state-of-the-art spectrum based bug localization technique.

1. INTRODUCTION

EnSpec augments spectrum-based bug localization with code entropy from a statistical language model to address weaknesses caused by inadequate test-suite information. Evaluated on Defects4J and ManyBugs, it improves standard SBBL and supports cross-project localization.

  • 1. INTRODUCTION: SBBL accuracy depends strongly on test-suite quality, while static approaches can be imprecise or inaccurate.Limited coverage can leave developers relying heavily on manual effort and prior experience.
  • 1. INTRODUCTION: The method is motivated by evidence that code entropy captures unnaturalness associated with buggy code and can provide information complementary to SBBL.This complementarity is intended to help when tests poorly discriminate buggy lines or many lines receive similar suspiciousness scores.
  • 1. INTRODUCTION: EnSpec was evaluated on more than 500 bugs across about 4M lines of code in the Defects4J and ManyBugs benchmarks.The benchmarks contain Java and C projects, respectively.
  • 1. INTRODUCTION: Entropy score significantly improves the bug-localization capability of standard SBBL.The authors report this result across the evaluated benchmarks and programming languages.
  • 1. INTRODUCTION: Entropy score also boosts SBBL in cross-project bug-localization settings.This extends the reported benefit beyond within-project evaluation.
  • 1. INTRODUCTION: EnSpec combines entropy scores with spectrum-based suspiciousness using machine learning to rank suspicious lines for investigation.The approach operates at line granularity and uses source code as its required information source.

2. PRELIMINARIES

Spectrum-based bug localization ranks program elements from passing and failing test traces, while language models estimate code naturalness through token probabilities. EnSpec’s workflow combines these dynamic and static signals, motivated by the higher entropy of unnatural or buggy code.

  • 2. PRELIMINARIES: SBBL computes suspiciousness from how program elements are executed by passing and failing test cases, then ranks those elements for inspection.The approach can operate at granularities such as files, methods, blocks, or statements.
  • 2. PRELIMINARIES: The suspiciousness score is a function of four counts: passed and failed tests that execute an element, plus passed and failed tests that do not.Tarantula and Ochiai are presented as widely used suspiciousness measures.
  • 2. PRELIMINARIES: N-gram language models approximate token probabilities by assuming each token depends on the previous n −1 tokens.The model parameter n controls the context length, while empirical probabilities depend on training data.
  • 2. PRELIMINARIES: A cache-augmented $gram model incorporates locally frequent n-grams alongside a global model and defines entropy for a code sequence.The cache reflects the observation that source-code token sequences are often localized within files, classes, or functions.
  • 2. PRELIMINARIES: Prior work reports that buggy code is less natural and more entropic than non-buggy code, with entropy decreasing after bugs are fixed.Syntax-sensitive entropy standardizes entropy by line type using its mean and standard deviation.

3. MOTIVATING EXAMPLE

SBBL can perform poorly when passing tests provide low code coverage, motivating entropy-based features as additional information; Table 2 evaluates their effectiveness.

  • 3. MOTIVATING EXAMPLE: Low coverage in passing tests can leave SBBL with many highly suspicious false positives, because its results depend heavily on test-case quality.Generating an adequate test suite is difficult, so SBBL may perform poorly in practice.
  • 3. MOTIVATING EXAMPLE: Table 2 presents the reported effectiveness of entropy-based features for improving SBBL.

4. PROPOSED APPROACH

EnSpec combines dynamic spectrum-based bug localization with static language-model defect prediction to localize bugs using both execution behavior and code naturalness.

  • 4. PROPOSED APPROACH: EnSpec is a hybrid technique combining dynamic spectrum-based bug localization with static natural-language-model defect prediction.The tool takes training and testing code corpora as input and computes entropy scores before combining them with spectrum-based information.
  • 4. PROPOSED APPROACH: Although EnSpec is theoretically applicable at line, method, or file granularity, this paper evaluates bug localization at line granularity.

Step-1: Generating entropy using LM

EnSpec generates language-model entropy features and combines them with spectrum-based suspiciousness information and execution traces for later learning-to-rank stages.

  • Step-1: Generating entropy using LM: EnSpec derives three entropy features for each source-code line using a statistical language model: forward, backward, and average entropy.Forward entropy uses prefix token sequences, backward entropy uses suffix sequences in reverse parsing order, and average entropy averages the two.
  • Step-1: Generating entropy using LM: The three entropy values are normalized by abstract-syntax-tree type and used as the model’s entropy-related features.
  • Step-2: Extracting suspiciousness score using SBBL techniques: EnSpec uses 25 literature-based suspiciousness scores as SBBL features in its learning-to-rank setup.
  • Step-2: Extracting suspiciousness score using SBBL techniques: SBBL features are extracted from execution traces that record source-line coverage and passing or failing test status.The resulting test spectra summarize how frequently each line executes across passing and failing tests.
  • Step-2: Extracting suspiciousness score using SBBL techniques: The extracted features feed later training and testing stages based on an adapted learning-to-rank algorithm.

Step-3: Training Phase

During training, EnSpec learns how SBBL and entropy-related features relate to whether program lines are buggy or non-buggy.

  • Step-3: Training Phase: EnSpec learns the relation between SBBL features, entropy-related features, and the bugginess of program lines.
  • Step-3: Training Phase: Training lines receive higher relevance scores when buggy than when non-buggy, and a machine learner estimates P(R_l|S_p_l, E_n_l).Each line is represented by its SBBL features, entropy-related features, and bug-relevance score.

Step-4: Testing Phase

EnSpec computes hybrid suspiciousness scores for test-corpus lines by combining SBBL-derived information with entropy-related features, then ranks lines for investigation.

  • Step-4: Testing Phase: The testing phase computes each line’s suspiciousness score using the paper’s expected-relevance formulation.
  • Step-4: Testing Phase: The formulation uses monotonically increasing functions for the relevance terms, instantiated as identity functions in the implementation.
  • Step-4: Testing Phase: EnSpec ensembles M models trained on randomly sampled subsets, with each model producing a suspiciousness score for the line.
  • Step-4: Testing Phase: EnSpec outputs source-code lines in decreasing order of hybrid suspiciousness, placing the highest-scoring line first.

5. EXPERIMENTAL SETUP

The evaluation uses Defects4J and ManyBugs, derives buggy lines from dataset differences and project evolution, and measures localization with Cost Effectiveness and AUCEC.

  • 5. EXPERIMENTAL SETUP: The study evaluates EnSpec using Defects4J and ManyBugs, with reproducible bugs, passing and failing tests, and execution-trace instrumentation.Defects4J contains Java projects, while ManyBugs contains C projects.
  • 5. EXPERIMENTAL SETUP: Buggy lines are identified from deleted or modified statements by comparing buggy and fixed versions, while omission bugs are filtered out.The study targets existing buggy lines rather than missing functionality requiring additions in the fixed version.
  • 5. EXPERIMENTAL SETUP: The evolutionary procedure finds bug-fix commits by keyword search, traces bug-introducing commits with SZZ, and uses reverse git blame to locate buggy lines.
  • 5. EXPERIMENTAL SETUP: 1541 additional buggy lines were identified across five Defects4J projects, yielding 1761 buggy lines studied in that dataset.
  • 5. EXPERIMENTAL SETUP: Cost Effectiveness measures inspection effort against bugs found, plotting inspected program elements on the x-axis and bugs found on the y-axis.
  • 5. EXPERIMENTAL SETUP: AUCEC summarizes the area under the Cost Effectiveness curve; random ranking has AUCEC 0.5, optimal ranking approaches 1.00, and higher values indicate better prioritization.
  • 5. EXPERIMENTAL SETUP: Random Forest was selected for subsequent experiments because it outperformed RankBoost on all studied projects except Wireshark using AUCEC100 with SBBL features.
  • 5. EXPERIMENTAL SETUP: The research questions test whether entropy improves SBBL and whether a language model trained across projects can help smaller code bases lacking sufficient history.

6. RESULT

EnSpec combines entropy with spectrum-based suspiciousness to improve bug localization, especially for lines covered by failing tests and under realistic inspection budgets. Across Defects4J and ManyBugs, entropy generally improves SBBL, though performance can weaken for smaller projects and a few individual projects.

  • For failing-test spectra, buggy lines are significantly more entropic than non-buggy lines, whereas the association is not significant outside failing spectra.The failing-spectrum difference has p-value < 0.05 and a small Cohen’s D effect size; the authors attribute other cases to test-suite or bug complexity factors.
  • 6.617% overall AUCEC100 gain is observed when entropy-related features are added, including 3.81% for Defects4J and 9.11% for ManyBugs.Average Entropy is the most important feature in every reported case.
  • 33.33% overall AUCEC20 gain raises detected buggy lines from 80.08% to 98.63% when entropy features augment SBBL.These values summarize all studied projects at a 20% inspection budget.
  • At lower inspection budgets, SBBL plus entropy outperforms SBBL for every studied project except near-equal Apache commons-math and worse-performing Libtiff.This result is reported from the individual-project cost-effectiveness curves.
  • 75.34% and 54.5% AUCEC20 gains occur for Defects4J and ManyBugs, respectively, under cross-project localization with entropy.At this budget, EnSpec detects 33.54% versus 19.24% of buggy lines in Defects4J and 59.65% versus 35.72% in ManyBugs.
  • EnSpec improves SBBL in cross-project localization, but smaller projects may lack enough bug data to train the model effectively.Average gains at 100% inspection are 16.59% for Defects4J and 25.95% for ManyBugs.

7. RELATED WORK

Bug localization research includes static source-based methods and dynamic execution-based methods, alongside newer statistical and multimodal approaches. This paper combines code entropy with program spectra rather than relying on textual similarity, aiming to use complementary information for line-level localization.

  • Static approaches use source code through program analysis or information retrieval, while dynamic approaches use passing and failing test execution traces.Static methods include buggy-pattern detection and bug-report similarity; SBBL ranks elements using program spectra.
  • Static methods may be coarse or unable to detect functional bugs, whereas dynamic methods depend strongly on test-suite coverage and quality.Insufficient coverage can leave developers relying substantially on manual effort and prior experience.
  • Statistical modeling and machine learning introduced language-model and defect-detection approaches that estimate probable or defective code.Reported examples include a Deep Belief Network for file-level defects and an n-gram language model for probable bugs.
  • Multimodal localization combines multiple information sources, such as bug reports, source code, and test cases, to improve localization accuracy.Prior work combined information-retrieval similarity with spectrum-based localization and required a fault-reproducing test case.
  • EnSpec combines source-code entropy with program spectra instead of IR textual similarity, providing a multimodal approach that does not require a bug report.The paper presents this combination as distinct from prior uses of local code and test-spectrum information.

8. THREATS TO VALIDITY

EnSpec’s validity is bounded by training-data availability, test-suite adequacy, bug-label completeness, and evaluation scope, although cross-project results and language diversity mitigate some concerns.

  • EnSpec’s efficiency depends on available previous bugs for training, but cross-project evaluation shows it can work when project-specific bug histories are limited.
  • Insufficient failing-test coverage can reduce SBBL performance and therefore EnSpec’s performance, although its language-model component still uses source code alone.
  • Bug annotations rely on public datasets and evolutionary bugs, so undiscovered bugs in the code corpus may pollute the results.
  • External validity is constrained by evaluation on 10 projects in only C and Java, although the authors report that EnSpec is not restricted to one programming language.

9. CONCLUSION

The paper introduces code entropy as a new complement to spectrum-based bug localization and implements the combination in EnSpec. Experiments support entropy’s usefulness for bug localization and cross-project use, while future work targets repair and semantic language models.

  • EnSpec combines code entropy from a statistical language model with spectrum-based suspiciousness scores to make bug localization more robust.
  • Code entropy is positively correlated with buggy lines executed by failing test cases, and using entropy with SBBL outperforms configurations using only SBBL features.
  • EnSpec can support cross-project bug detection for relatively new projects whose project bug databases and evolutionary histories are limited.
  • Future work includes improving buggy-line repair and incorporating language models that capture code semantics alongside syntax.
Loading 1802.06947v1…