Handbook of Software Fault Localization: Foundations and Advances

Description

Handbook of Software Fault Localization A comprehensive analysis of fault localization techniques and strategies In Handbook of Software Fault Localization: Foundations and Advances, distinguished computer scientists Prof. W. Eric Wong and Prof. T.H. Tse deliver a robust treatment of up-to-date techniques, tools, and essential issues in software fault localization. The authors offer collective discussions of fault localization strategies with an emphasis on the most important features of each approach. The book also explores critical aspects of software fault localization, like multiple bugs, successful and failed test cases, coincidental correctness, faults introduced by missing code, the combination of several fault localization techniques, ties within fault localization rankings, concurrency bugs, spreadsheet fault localization, and theoretical studies on fault localization. Readers will benefit from the authors’ straightforward discussions of how to apply cost-effective techniques to a variety of specific environments common in the real world. They will also enjoy the in-depth explorations of recent research directions on this topic. Handbook of Software Fault Localization also includes: A thorough introduction to the concepts of software testing and debugging, their importance, typical challenges, and the consequences of poor efforts Comprehensive explorations of traditional fault localization techniques, including program logging, assertions, and breakpoints Practical discussions of slicing-based, program spectrum-based, and statistics-based techniques In-depth examinations of machine learning-, data mining-, and model-based techniques for software fault localization Perfect for researchers, professors, and students studying and working in the field, Handbook of Software Fault Localization: Foundations and Advances is also an indispensable resource for software engineers, managers, and software project decision makers responsible for schedule and budget control. 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