Handbook of Software Fault Localization: Foundations and Advances

ISBN-13: 9781119291800 / Angielski / Miękka / 2023 / 350 str.

Wiley,

Opis

Starting with the background and traditional techniques, this book will mainly focus on the up-to-date techniques, tools and critical issues in software fault localization. The techniques covered in this book are grouped into the following categories: traditional, slicing-based, spectrum-based, statics based, program state-based, machine learning-based, data mining-based, model-based and miscellaneous techniques. With this organization, the authors aim to provide a collective discussion with emphasis on the most important features of each approach. Different evaluation metrics to assess the effectiveness of fault localization techniques and tools are described. The book also explores critical aspects of software fault localization, including: fault localization with multiple bugs; inputs, outputs, and impact of test cases; coincidental correctness; faults introduced by missing code; combination of multiple fault localization techniques; ties within fault localization rankings; fault localization for concurrency bugs; spreadsheet fault localization: and theoretical studies on fault localization.

Spis treści

Editor Biographies xvList of Contributors xvii1 Software Fault Localization: an Overview of Research, Techniques, and Tools 1W. Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, Franz Wotawa, and Dongcheng li1.1 Introduction 11.2 Traditional Fault Localization Techniques 141.2.1 Program Logging 141.2.2 Assertions 141.2.3 Breakpoints 141.2.4 Profiling 151.3 Advanced Fault Localization Techniques 151.3.1 Slicing-Based Techniques 151.3.2 Program Spectrum-Based Techniques 201.3.2.1 Notation 201.3.2.2 Techniques 211.3.2.3 Issues and Concerns 271.3.3 Statistics-Based Techniques 301.3.4 Program State-Based Techniques 321.3.5 Machine Learning-Based Techniques 341.3.6 Data Mining-Based Techniques 361.3.7 Model-Based Techniques 371.3.8 Additional Techniques 411.3.9 Distribution of Papers in Our Repository 451.4 Subject Programs 471.5 Evaluation Metrics 501.6 Software Fault Localization Tools 531.7 Critical Aspects 581.7.1 Fault Localization with Multiple Bugs 581.7.2 Inputs, Outputs, and Impact of Test Cases 601.7.3 Coincidental Correctness 631.7.4 Faults Introduced by Missing Code 641.7.5 Combination of Multiple Fault Localization Techniques 651.7.6 Ties Within Fault Localization Rankings 671.7.7 Fault Localization for Concurrency Bugs 671.7.8 Spreadsheet Fault Localization 681.7.9 Theoretical Studies 701.8 Conclusion 71Notes 73References 732 Traditional Techniques for Software Fault Localization 119Yihao Li, Linghuan Hu, W. Eric Wong, Vidroha Debroy, and Dongcheng li2.1 Program Logging 1192.2 Assertions 1212.3 Breakpoints 1242.4 Profiling 1252.5 Discussion 1282.6 Conclusion 130References 1313 Slicing-Based Techniques for Software Fault Localization 135W. Eric Wong, Hira Agrawal, and Xiangyu Zhang3.1 Introduction 1353.2 Static Slicing-Based Fault Localization 1363.2.1 Introduction 1363.2.2 Program Slicing Combined with Equivalence Analysis 1373.2.3 Further Application 1383.3 Dynamic Slicing-Based Fault Localization 1383.3.1 Dynamic Slicing and Backtracking Techniques 1443.3.2 Dynamic Slicing and Model-Based Techniques 1453.3.3 Critical Slicing 1483.3.3.1 Relationships Between Critical Slices (CS) and Exact Dynamic Program Slices (DPS) 1493.3.3.2 Relationship Between Critical Slices and Executed Static Program Slices 1503.3.3.3 Construction Cost 1503.3.4 Multiple-Points Dynamic Slicing 1513.3.4.1 BwS of an Erroneous Computed Value 1523.3.4.2 FwS of Failure-Inducing Input Difference 1523.3.4.3 BiS of a Critical Predicate 1543.3.4.4 MPSs: Dynamic Chops 1573.3.5 Execution Indexing 1583.3.5.1 Concepts 1593.3.5.2 Structural Indexing 1613.3.6 Dual Slicing to Locate Concurrency Bugs 1653.3.6.1 Trace Comparison 1653.3.6.2 Dual Slicing 1683.3.7 Comparative Causality: a Causal Inference Model Based on Dual Slicing 1733.3.7.1 Property One: Relevance 1743.3.7.2 Property Two: Sufficiency 1753.3.8 Implicit Dependences to Locate Execution Omission Errors 1773.3.9 Other Dynamic Slicing-Based Techniques 1793.4 Execution Slicing-Based Fault Localization 1793.4.1 Fault Localization Using Execution Dice 1793.4.2 A Family of Fault Localization Heuristics Based on Execution Slicing 1813.4.2.1 Heuristic I 1823.4.2.2 Heuristic II 1833.4.2.3 Heuristic III 1853.4.3 Effective Fault Localization Based on Execution Slices and Inter-block Data Dependence 1883.4.3.1 Augmenting a Bad D(1) 1893.4.3.2 Refining a Good D(1) 1903.4.3.3 An Incremental Debugging Strategy 1913.4.4 Other Execution Slicing-Based Techniques in Software Fault Localization 1933.5 Discussions 1933.6 Conclusion 194Notes 195References 1954 Spectrum-Based Techniques for Software Fault Localization 201W. Eric Wong, Hua Jie Lee, Ruizhi Gao, and Lee Naish4.1 Introduction 2014.2 Background and Notation 2034.2.1 Similarity Coefficient-Based Fault Localization 2044.2.2 An Example of Using Similarity Coefficient to Compute Suspiciousness 2054.3 Insights of Some Spectra-Based Metrics 2104.4 Equivalence Metrics 2124.4.1 Applicability of the Equivalence Relation to Other Fault Localization Techniques 2174.4.2 Applicability Beyond Fault Localization 2184.5 Selecting a Good Suspiciousness Function (Metric) 2194.5.1 Cost of Using a Metric 2194.5.2 Optimality for Programs with a Single Bug 2204.5.3 Optimality for Programs with Deterministic Bugs 2214.6 Using Spectrum-Based Metrics for Fault Localization 2224.6.1 Spectrum-Based Metrics for Fault Localization 2224.6.2 Refinement of Spectra-Based Metrics 2274.7 Empirical Evaluation Studies of SBFL Metrics 2324.7.1 The Construction of D * 2344.7.2 An Illustrative Example 2354.7.3 A Case Study Using D * 2374.7.3.1 Subject Programs 2374.7.3.2 Fault Localization Techniques Used in Comparisons 2384.7.3.3 Evaluation Metrics and Criteria 2394.7.3.4 Statement with Same Suspiciousness Values 2404.7.3.5 Results 2414.7.3.6 Effectiveness of D * with Different Values of * 2474.7.3.7 D * Versus Other Fault Localization Techniques 2484.7.3.8 Programs with Multiple Bugs 2514.7.3.9 Discussion 2554.8 Conclusion 261Notes 262References 2635 Statistics-Based Techniques for Software Fault Localization 271Zhenyu Zhang and W. Eric Wong5.1 Introduction 2715.1.1 Tarantula 2725.1.2 How It Works 2725.2 Working with Statements 2745.2.1 Techniques Under the Same Problem Settings 2755.2.2 Statistical Variances 2755.3 Working with Non-statements 2835.3.1 Predicate: a Popular Trend 2835.3.2 BPEL: a Sample Application 2855.4 Purifying the Input 2865.4.1 Coincidental Correctness Issue 2865.4.2 Class Balance Consideration 2875.5 Reinterpreting the Output 2885.5.1 Revealing Fault Number 2885.5.2 Noise Reduction 291Notes 292References 2936 Machine Learning-Based Techniques for Software Fault Localization 297W. Eric Wong6.1 Introduction 2976.2 BP Neural Network-Based Fault Localization 2986.2.1 Fault Localization with a BP Neural Network 2986.2.2 Reduce the Number of Candidate Suspicious Statements 3026.3 RBF Neural Network-Based Fault Localization 3046.3.1 RBF Neural Networks 3046.3.2 Methodology 3056.3.2.1 Fault Localization Using an RBF Neural Network 3066.3.2.2 Training of the RBF Neural Network 3076.3.2.3 Definition of a Weighted Bit-Comparison-Based Dissimilarity 3096.4 C4.5 Decision Tree-Based Fault Localization 3096.4.1 Category-Partition for Rule Induction 3096.4.2 Rule Induction Algorithms 3106.4.3 Statement Ranking Strategies 3106.4.3.1 Revisiting Tarantula 3106.4.3.2 Ranking Statements Based on C4.5 Rules 3126.5 Applying Simulated Annealing with Statement Pruning for an SBFL Formula 3146.6 Conclusion 317Notes 317References 3177 Data Mining-Based Techniques for Software Fault Localization 321Peggy Cellier, Mireille Ducassé, Sébastien Ferré, Olivier Ridoux, and W. Eric Wong7.1 Introduction 3217.2 Formal Concept Analysis and Association Rules 3247.2.1 Formal Concept Analysis 3257.2.2 Association Rules 3277.3 Data Mining for Fault Localization 3297.3.1 Failure Rules 3297.3.2 Failure Lattice 3317.4 The Failure Lattice for Multiple Faults 3367.4.1 Dependencies Between Faults 3367.4.2 Example 3417.5 Discussion 3427.5.1 The Structure of the Execution Traces 3427.5.2 Union Model 3437.5.3 Intersection Model 3437.5.4 Nearest Neighbor 3437.5.5 Delta Debugging 3447.5.6 From the Trace Context to the Failure Context 3447.5.7 The Structure of Association Rules 3457.5.8 Multiple Faults 3457.6 Fault Localization Using N-gram Analysis 3467.6.1 Background 3477.6.1.1 Execution Sequence 3477.6.1.2 N-gram Analysis 3477.6.1.3 Linear Execution Blocks 3497.6.1.4 Association Rule Mining 3497.6.2 Methodology 3507.6.3 Conclusion 3537.7 Fault Localization for GUI Software Using N-gram Analysis 3537.7.1 Background 3547.7.1.1 Representation of the GUI and Its Operations 3547.7.1.2 Event Handler 3567.7.1.3 N-gram 3567.7.2 Association Rule Mining 3577.7.3 Methodology 3577.7.3.1 General Approach 3587.7.3.2 N-gram Fault Localization Algorithm 3587.8 Conclusion 360Notes 361References 3618 Information Retrieval-Based Techniques for Software Fault Localization 365Xin Xia and David Lo8.1 Introduction 3658.2 General IR-Based Fault Localization Process 3688.3 Fundamental Information Retrieval Techniques for Software Fault Localization 3698.3.1 Vector Space Model 3698.3.2 Topic Modeling 3708.3.3 Word Embedding 3718.4 Evaluation Metrics 3728.4.1 Top-k Prediction Accuracy 3728.4.2 Mean Reciprocal Rank (MRR) 3738.4.3 Mean Average Precision (MAP) 3738.5 Techniques for Different Scenarios 3748.5.1 Text of Current Bug Report Only 3748.5.1.1 VSM Variants 3748.5.1.2 Topic Modeling 3758.5.2 Text and History 3768.5.2.1 VSM Variants 3768.5.2.2 Topic Modeling 3788.5.2.3 Deep Learning 3788.5.3 Text and Stack/Execution Traces 3798.6 Empirical Studies 3808.7 Miscellaneous 3838.8 Conclusion 385Notes 385References 3869 Model-Based Techniques for Software Fault Localization 393Birgit Hofer, Franz Wotawa, Wolfgang Mayer, and Markus Stumptner9.1 Introduction 3939.2 Basic Definitions and Algorithms 3959.2.1 Algorithms for MBD 4019.3 Modeling for MBD 4049.3.1 The Value-Based Model 4059.3.2 The Dependency-Based Model 4099.3.3 Approximation Models for Debugging 4139.3.4 Other Modeling Approaches 4169.4 Application Areas 4179.5 Hybrid Approaches 4189.6 Conclusions 419Notes 420References 42010 Software Fault Localization in Spreadsheets 425Birgit Hofer and Franz Wotawa10.1 Motivation 42510.2 Definition of the Spreadsheet Language 42710.3 Cones 43010.4 Spectrum-Based Fault Localization 43110.5 Model-Based Spreadsheet Debugging 43510.6 Repair Approaches 44010.7 Checking Approaches 44310.8 Testing 44510.9 Conclusion 446Notes 446References 44711 Theoretical Aspects of Software Fault Localization 451Xiaoyuan Xie and W. Eric Wong11.1 Introduction 45111.2 A Model-Based Hybrid Analysis 45211.2.1 The Model Program Segment 45211.2.2 Important Findings 45411.2.3 Discussion 45411.3 A Set-Based Pure Theoretical Framework 45511.3.1 Definitions and Theorems 45511.3.2 Evaluation 45711.3.3 The Maximality Among All Investigated Formulas 46111.4 A Generalized Study 46211.4.1 Spectral Coordinate for SBFL 46211.4.2 Generalized Maximal and Greatest Formula in F 46411.5 About the Assumptions 46511.5.1 Omission Fault and 100% Coverage 46511.5.2 Tie-Breaking Scheme 46711.5.3 Multiple Faults 46711.5.4 Some Plausible Causes for the Inconsistence Between Empirical and Theoretical Analyses 468Notes 469References 47012 Software Fault Localization for Programs with Multiple Bugs 473Ruizhi Gao, W. Eric Wong, and Rui Abreu12.1 Introduction 47312.2 One-Bug-at-a-Time 47412.3 Two Techniques Proposed by Jones et al. 47512.3.1 J1: Clustering Based on Profiles and Fault Localization Results 47612.3.1.1 Clustering Profile-Based Behavior Models 47612.3.1.2 Using Fault Localization to Stop Clustering 47812.3.1.3 Using Fault Localization Clustering to Refine Clusters 47912.3.2 J2: Clustering Based on Fault Localization Results 48012.4 Localization of Multiple Bugs Using Algorithms from Integer Linear Programming 48112.5 MSeer: an Advanced Fault Localization Technique for Locating Multiple Bugs in Parallel 48312.5.1 MSeer 48512.5.1.1 Representation of Failed Test Cases 48512.5.1.2 Revised Kendall tau Distance 48612.5.1.3 Clustering 48812.5.1.4 MSeer: a Technique for Locating Multiple Bugs in Parallel 49412.5.2 A Running Example 49612.5.3 Case Studies 49912.5.3.1 Subject Programs and Data Collections 49912.5.3.2 Evaluation of Effectiveness and Efficiency 50112.5.3.3 Results 50312.5.4 Discussions 51012.5.4.1 Using Different Fault Localization Techniques 51012.5.4.2 Apply MSeer to Programs with a Single Bug 51012.5.4.3 Distance Metrics 51212.5.4.4 The Importance of Estimating the Number of Clusters and Assigning Initial Medoids 51412.6 Spectrum-Based Reasoning for Fault Localization 51412.6.1 Barinel 51512.6.2 Results 51712.7 Other Studies 51812.8 Conclusion 520Notes 521References 52213 Emerging Aspects of Software Fault Localization 529T.H. Tse, David Lo, Alex Gorce, Michael Perscheid, Robert Hirschfeld, and W. Eric Wong13.1 Introduction 52913.2 Application of the Scientific Method to Fault Localization 53013.2.1 Scientific Debugging 53113.2.2 Identifying and Assigning Bug Reports to Developers 53213.2.3 Using Debuggers in Fault Localization 53413.2.4 Conclusion 53813.3 Fault Localization in the Absence of Test Oracles by Semi-proving of Metamorphic Relations 53813.3.1 Metamorphic Testing and Metamorphic Relations 53913.3.2 The Semi-proving Methodology 54113.3.2.1 Semi-proving by Symbolic Evaluation 54113.3.2.2 Semi-proving as a Fault Localization Technique 54213.3.3 The Need to Go Beyond Symbolic Evaluation 54313.3.4 Initial Empirical Study 54313.3.5 Detailed Illustrative Examples 54413.3.5.1 Fault Localization Example Related to Predicate Statement 54413.3.5.2 Fault Localization Example Related to Faulty Statement 54813.3.5.3 Fault Localization Example Related to Missing Path 55213.3.5.4 Fault Localization Example Related to Loop 55613.3.6 Comparisons with Related Work 55813.3.7 Conclusion 56013.4 Automated Prediction of Fault Localization Effectiveness 56013.4.1 Overview of PEFA 56113.4.2 Model Learning 56413.4.3 Effectiveness Prediction 56413.4.4 Conclusion 56413.5 Integrating Fault Localization into Automated Test Generation Tools 56513.5.1 Localization in the Context of Automated Test Generation 56613.5.2 Automated Test Generation Tools Supporting Localization 56713.5.3 Antifragile Tests and Localization 56813.5.4 Conclusion 568Notes 569References 569Index 581

O autorze

W. Eric Wong, PhD, is a Full Professor, Director of Software Engineering Program, and the Founding Director of Advanced Research Center for Software Testing and Quality Assurance in Computer Science at the University of Texas at Dallas. He is also a Guest Researcher with the US National Institute of Standards and Technology. Professor Wong was the award recipient of the 2014 IEEE Reliability Society Engineer of the Year. In addition, he was the Editor-in-Chief of the IEEE Transactions on Reliability from June 2016 to May 2022. He received his MS and PhD in Computer Science from Purdue University.T.H. Tse received his PhD from London School of Economics, and was a Visiting Fellow at University of Oxford. He is an Honorary Professor in Computer Science with The University of Hong Kong after retiring from full professorship. He is a Steering Committee Chair of the IEEE International Conference on Software Quality, Reliability, and Security; and an Associate Editor of IEEE Transactions on Reliability. He has over 270 publications, including a book with Cambridge University Press. He ranks internationally as no. 2 in metamorphic testing. He was awarded an MBE by Queen Elizabeth II of the United Kingdom.