Handbook of Software Fault Localization: Foundations and Advances

Cover
Title Page
Copyright Page
Contents
Editor Biographies
List of Contributors
Chapter 1 Software Fault Localization: an Overview of Research, Techniques, and Tools
1.1 Introduction
1.2 Traditional Fault Localization Techniques
1.2.1 Program Logging
1.2.2 Assertions
1.2.3 Breakpoints
1.2.4 Profiling
1.3 Advanced Fault Localization Techniques
1.3.1 Slicing-Based Techniques
1.3.2 Program Spectrum-Based Techniques
1.3.2.1 Notation
1.4 Subject Programs
1.5 Evaluation Metrics
1.6 Software Fault Localization Tools
1.7 Critical Aspects
1.7.1 Fault Localization with Multiple Bugs
1.7.2 Inputs, Outputs, and Impact of Test Cases
1.7.3 Coincidental Correctness
1.7.4 Faults Introduced by Missing Code
1.7.5 Combination of Multiple Fault Localization Techniques
1.7.6 Ties Within Fault Localization Rankings
1.7.7 Fault Localization for Concurrency Bugs
1.7.8 Spreadsheet Fault Localization
1.7.9 Theoretical Studies
1.8 Conclusion
1.8 Notes
References
Chapter 2 Traditional Techniques for Software Fault Localization
2.1 Program Logging
2.2 Assertions
2.3 Breakpoints
2.4 Profiling
2.5 Discussion
2.6 Conclusion
References
Chapter 3 Slicing-Based Techniques for Software Fault Localization
3.1 Introduction
3.2 Static Slicing-Based Fault Localization
3.2.1 Introduction
3.2.2 Program Slicing Combined with Equivalence Analysis
3.2.3 Further Application
3.3 Dynamic Slicing-Based Fault Localization
3.3.1 Dynamic Slicing and Backtracking Techniques
3.3.2 Dynamic Slicing and Model-Based Techniques
3.3.3 Critical Slicing
3.3.3.1 Relationships Between Critical Slices (CS) and Exact Dynamic Program Slices (DPS)
3.3.3.2 Relationship Between Critical Slices and Executed Static Program Slices
3.3.3.3 Construction Cost
3.3.4 Multiple-Points Dynamic Slicing
3.3.4.1 BwS of an Erroneous Computed Value
3.3.4.2 FwS of Failure-Inducing Input Difference
3.3.4.3 BiS of a Critical Predicate
3.3.4.4 MPSs: Dynamic Chops
3.3.5 Execution Indexing
3.3.5.1 Concepts
3.3.5.2 Structural Indexing
3.3.6 Dual Slicing to Locate Concurrency Bugs
3.3.6.1 Trace Comparison
3.3.6.2 Dual Slicing
3.3.7 Comparative Causality: a Causal Inference Model Based on Dual Slicing
3.3.7.1 Property One: Relevance
3.3.7.2 Property Two: Sufficiency
3.3.8 Implicit Dependences to Locate Execution Omission Errors
3.3.9 Other Dynamic Slicing-Based Techniques
3.4 Execution Slicing-Based Fault Localization
3.4.1 Fault Localization Using Execution Dice
3.4.2 A Family of Fault Localization Heuristics Based on Execution Slicing
3.4.2.1 Heuristic I
3.4.2.2 Heuristic II
3.4.2.3 Heuristic III
3.4.3 Effective Fault Localization Based on Execution Slices and Inter-block Data Dependence
3.4.3.1 Augmenting a Bad D(1)
3.4.3.2 Refining a Good D(1)
3.4.3.3 An Incremental Debugging Strategy
3.4.4 Other Execution Slicing-Based Techniques in Software Fault Localization
3.5 Discussions
3.6 Conclusion
3.6 Notes
References
Chapter 4 Spectrum-Based Techniques for Software Fault Localization
4.1 Introduction
4.2 Background and Notation
4.2.1 Similarity Coefficient-Based Fault Localization
4.2.2 An Example of Using Similarity Coefficient to Compute Suspiciousness
4.3 Insights of Some Spectra-Based Metrics
4.4 Equivalence Metrics
4.4.1 Applicability of the Equivalence Relation to Other Fault Localization Techniques
4.4.2 Applicability Beyond Fault Localization
4.5 Selecting a Good Suspiciousness Function (Metric)
4.5.1 Cost of Using a Metric
4.5.2 Optimality for Programs with a Single Bug
4.5.3 Optimality for Programs with Deterministic Bugs
4.6 Using Spectrum-Based Metrics for Fault Localization
4.6.1 Spectrum-Based Metrics for Fault Localization
4.6.2 Refinement of Spectra-Based Metrics
4.7 Empirical Evaluation Studies of SBFL Metrics
4.7.1 The Construction of D*
4.7.2 An Illustrative Example
4.7.3 A Case Study Using D*
4.7.3.1 Subject Programs
4.7.3.2 Fault Localization Techniques Used in Comparisons
4.7.3.3 Evaluation Metrics and Criteria
4.7.3.3.1 The EXAM Score
4.7.3.3.2 Cumulative Number of Statements Examined
4.7.3.3.3 Wilcoxon Signed-Rank Test
4.7.3.4 Statement with Same Suspiciousness Values
4.7.3.5 Results
4.7.3.6 Effectiveness of D* with Different Values of *
4.7.3.7 D* Versus Other Fault Localization Techniques
4.7.3.8 Programs with Multiple Bugs
4.7.3.8.1 The Expense Score-Based Approach
4.7.3.8.2 The One-Bug-at-a-Time Approach
4.7.3.9 Discussion
4.7.3.9.1 Intuition
4.7.3.9.2 Best and Worst Effectiveness Versus Other Alternatives
4.7.3.9.3 Threats to Validity
4.8 Conclusion
4.8 Notes
References
Chapter 5 Statistics-Based Techniques for Software Fault Localization
5.1 Introduction
5.1.1 Tarantula
5.1.2 How It Works
5.2 Working with Statements
5.2.1 Techniques Under the Same Problem Settings
5.2.2 Statistical Variances
5.3 Working with Non-statements
5.3.1 Predicate: a Popular Trend
5.3.2 BPEL: a Sample Application
5.4 Purifying the Input
5.4.1 Coincidental Correctness Issue
5.4.2 Class Balance Consideration
5.5 Reinterpreting the Output
5.5.1 Revealing Fault Number
5.5.2 Noise Reduction
5.5.2 Notes
References
Chapter 6 Machine Learning-Based Techniques for Software Fault Localization
6.1 Introduction
6.2 BP Neural Network-Based Fault Localization
6.2.1 Fault Localization with a BP Neural Network
6.2.2 Reduce the Number of Candidate Suspicious Statements
6.3 RBF Neural Network-Based Fault Localization
6.3.1 RBF Neural Networks
6.3.2 Methodology
6.3.2.1 Fault Localization Using an RBF Neural Network
6.3.2.2 Training of the RBF Neural Network
6.3.2.3 Definition of a Weighted Bit-Comparison-Based Dissimilarity
6.4 C4.5 Decision Tree-Based Fault Localization
6.4.1 Category-Partition for Rule Induction
6.4.2 Rule Induction Algorithms
6.4.3 Statement Ranking Strategies
6.4.3.1 Revisiting Tarantula
6.4.3.2 Ranking Statements Based on C4.5 Rules
6.4.3.2.1 Heuristic
6.4.3.2.2 Computing a Statement Ranking
6.4.3.2.3 Rule Selection
6.5 Applying Simulated Annealing with Statement Pruning for an SBFL Formula
6.6 Conclusion
6.6 Notes
References
Chapter 7 Data Mining-Based Techniques for Software Fault Localization
7.1 Introduction
7.2 Formal Concept Analysis and Association Rules
7.2.1 Formal Concept Analysis
7.2.2 Association Rules
7.3 Data Mining for Fault Localization
7.3.1 Failure Rules
7.3.2 Failure Lattice
7.4 The Failure Lattice for Multiple Faults
7.4.1 Dependencies Between Faults
7.4.2 Example
7.5 Discussion
7.5.1 The Structure of the Execution Traces
7.5.2 Union Model
7.5.3 Inter section Model
7.5.4 Nearest Neighbor
7.5.5 Delta Debugging
7.5.6 From the Trace Context to the Failure Context
7.5.7 The Structure of Association Rules
7.5.8 Multiple Faults
7.6 Fault Localization Using N-gram Analysis
7.6.1 Background
7.6.1.1 Execution Sequence
7.6.1.2 N-gram. Analysis
7.6.1.3 Linear Execution Blocks
7.6.1.4 Association Rule Mining
7.6.2 Methodology
7.6.3 Conclusion
7.7 Fault Localization for GUI Software Using N-gram Analysis
7.7.1 Background
7.7.1.1 Representation of the GUI and Its Operations
7.7.1.2 Event Handler
7.7.1.3 N-gram
7.7.2 Association Rule Mining
7.7.3 Methodology
7.7.3.1 General Approach
7.7.3.2 N-gram Fault Localization Algorithm
7.8 Conclusion
7.8 Notes
References
Chapter 8 Information Retrieval-Based Techniques for Software Fault Localization
8.1 Introduction
8.2 General IR-Based Fault Localization Process
8.3 Fundamental Information Retrieval Techniques for Software Fault Localization
8.3.1 Vector Space Model
8.3.2 Topic Modeling
8.3.3 Word Embedding
8.4 Evaluation Metrics
8.4.1 Top-k Prediction Accuracy
8.4.2 Mean Reciprocal Rank (MRR)
8.4.3 Mean Average Precision (MAP)
8.5 Techniques for Different Scenarios
8.5.1 Text of Current Bug Report Only
8.5.1.1 VSM Variants
8.5.1.2 Topic Modeling
8.5.2 Text and History
8.5.2.1 VSM Variants
8.5.2.2 Topic Modeling
8.5.2.3 Deep Learning
8.5.3 Text and Stack/Execution Traces
8.6 Empirical Studies
8.7 Miscellaneous
8.8 Conclusion
8.8 Notes
References
Chapter 9 Model-Based Techniques for Software Fault Localization
9.1 Introduction
9.2 Basic Definitions and Algorithms
9.2.1 Algorithms for MBD
9.3 Modeling for MBD
9.3.1 The Value-Based Model
9.3.2 The Dependency-Based Model
9.3.3 Approximation Models for Debugging
9.3.4 Other Modeling Approaches
9.4 Application Areas
9.5 Hybrid Approaches
9.6 Conclusion
9.6 Notes
References
Chapter 10 Software Fault Localization in Spreadsheets
10.1 Motivation
10.2 Definition of the Spreadsheet Language
10.3 Cones
10.4 Spectrum-Based Fault Localization
10.5 Model-Based Spreadsheet Debugging
10.6 Repair Approaches
10.7 Checking Approaches
10.8 Testing
10.9 Conclusion
10.9 Notes
References
Chapter 11 Theoretical Aspects of Software Fault Localization
11.1 Introduction
11.2 A Model-Based Hybrid Analysis
11.2.1 The Model Program Segment
11.2.2 Important Findings
11.2.3 Discussion
11.3 A Set-Based Pure Theoretical Framework
11.3.1 Definitions and Theorems
11.3.2 Evaluation
11.3.3 The Maximality Among All Investigated Formulas
11.4 A Generalized Study
11.4.1 Spectral Coordinate for SBFL
11.4.2 Generalized Maximal and Greatest Formula in F
11.5 About the Assumptions
11.5.1 Omission Fault and 100% Coverage
11.5.2 Tie-Breaking Scheme
11.5.3 Multiple Faults
11.5.4 Some Plausible Causes for the Inconsistence Between Empirical and Theoretical Analyses
11.5.4 Notes
References
Chapter 12 Software Fault Localization for Programs with Multiple Bugs
12.1 Introduction
12.2 One-Bug-at-a-Time
12.3 Two Techniques Proposed by Jones et al.
12.3.1 J1: Clustering Based on Profiles and Fault Localization Results
12.3.1.1 Clustering Profile-Based Behavior Models
12.3.1.2 Using Fault Localization to Stop Clustering
12.3.1.3 Using Fault Localization Clustering to Refine Clusters
12.3.2 J2: Clustering Based on Fault Localization Results
12.4 Localization of Multiple Bugs Using Algorithms from Integer Linear Programming
12.5 MSeer: an Advanced Fault Localization Technique for Locating Multiple Bugs in Parallel
12.5.1 MSeer
12.5.1.1 Representation of Failed Test Cases
12.5.1.2 Revised Kendall tau Distance
12.5.1.3 Clustering
12.5.1.3.1 Estimation of the Number of Clusters and Assignment of Initial Medoids
12.5.1.3.2 Improved K-medoids Clustering Algorithm
12.5.1.4 MSeer: a Technique for Locating Multiple Bugs in Parallel
12.5.2 A Running Example
12.5.3 Case Studies
12.5.3.1 Subject Programs and Data Collections
12.5.3.2 Evaluation of Effectiveness and Efficiency
12.5.3.3 Results
12.5.4 Discussions
12.5.4.1 Using Different Fault Localization Techniques
12.5.4.2 Apply MSeer to Programs with a Single Bug
12.5.4.3 Distance Metrics
12.5.4.4 The Importance of Estimating the Number of Clusters and Assigning Initial Medoids
12.6 Spectrum-Based Reasoning for Fault Localization
12.6.1 Barinel
12.6.2 Results
12.7 Other Studies
12.8 Conclusion
12.8 Notes
References
Chapter 13 Emerging Aspects of Software Fault Localization
13.1 Introduction
13.2 Application of the Scientific Method to Fault Localization
13.2.1 Scientific Debugging
13.2.2 Identifying and Assigning Bug Reports to Developers
13.2.3 Using Debuggers in Fault Localization
13.2.4 Conclusion
13.3 Fault Localization in the Absence of Test Oracles by Semi-proving of Metamorphic Relations
13.3.1 Metamorphic Testing and Metamorphic Relations
13.3.2 The Semi-proving Methodology
13.3.2.1 Semi-proving by Symbolic Evaluation
13.3.2.2 Semi-proving as a Fault Localization Technique
13.3.3 The Need to Go Beyond Symbolic Evaluation
13.3.4 Initial Empirical Study
13.3.5 Detailed Illustrative Examples
13.3.5.1 Fault Localization Example Related to Predicate Statement
13.3.5.2 Fault Localization Example Related to Faulty Statement
13.3.5.3 Fault Localization Example Related to Missing Path
13.3.5.4 Fault Localization Example Related to Loop
13.3.6 Comparisons with Related Work
13.3.7 Conclusion
13.4 Automated Prediction of Fault Localization Effectiveness
13.4.1 Overview of PEFA
13.4.2 Model Learning
13.4.3 Effectiveness Prediction
13.4.4 Conclusion
13.5 Integrating Fault Localization into Automated Test Generation Tools
13.5.1 Localization in the Context of Automated Test Generation
13.5.2 Automated Test Generation Tools Supporting Localization
13.5.3 Antifragile Tests and Localization
13.5.4 Conclusion
Notes
References
Index
EULA