VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY NGUYEN THU TRANG AUTOMATED LOCALIZATION AND REPAIR FOR VARIABILITY FAULTS IN SOFTWARE PRODUCT LINES DOCTOR OF PHILOSOPHY DISSERTATION Major: Software Engineering Hanoi - 2024 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY NGUYEN THU TRANG AUTOMATED LOCALIZATION AND REPAIR FOR VARIABILITY FAULTS IN SOFTWARE PRODUCT LINES DOCTOR OF PHILOSOPHY DISSERTATION Major: Software Engineering Code: 9480103 Supervisor: Dr. Vo Dinh Hieu Co-Supervisor: Assoc. Ho Si Dam Hanoi - 2024 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY NGUYEN THU TRANG Automated Localization and Repair for Variability Faults in Software Product Lines DOCTOR OF PHILOSOPHY DISSERTATION Major: Software Engineering Code: 9480103 Supervisor: Dr. Vo Dinh Hieu Co-Supervisor: Assoc.
Ho Si Dam PhD Candidate Supervisors VNU University of Engineering and Technology Hanoi - 2024 Acknowledgement I am deeply grateful to the following individuals and organizations for their invaluable support and encouragement throughout the journey of completing my doctoral disserta- tion. I would like to express my great appreciation to my supervisor, Dr. Vo Dinh Hieu, who is always willing to give me advice and comments on my problems. His constant support, guidance, and encouragement have been invaluable throughout the entire process.
I feel very fortunate to be a student under the supervision of Dr. Vo Dinh Hieu. I also would like to extend my sincere appreciation to my co-supervisor, Assoc. Ho Si Dam who gives me many valuable comments to improve my research and complete my dissertation.
I am grateful to Dr. Nguyen Van Son, who teaches me not only research skills but also presentation and writing skills. Without his expertise and encouragement, the completion of this dissertation would not have been possible. I would like to thank MSc.
Ngo Kien Tuan who is always willing to discuss with me and helps me a lot in conducting experiments. My gratitude also extends to my teachers at the Department of Software Engineering, Assoc. Pham Ngoc Hung, Assoc. Dang Duc Hanh, Dr.
Vu Thi Hong Nhan, my colleagues, and friends at UET-VNU. Without their knowledge and support, this dissertation would not have been successful. I am thankful to Vingroup Innovation Foundation (VINIF) and The Development Foun- dation of Vietnam National University, Hanoi for providing financial support for this research. Their investment in my academic pursuits has been crucial in enabling the successful completion of this dissertation.
Lastly, I want to express my deepest gratitude to my family, who stand by me with unwavering support, patience, and understanding. Their encouragement, love, and belief in my abilities sustained me through the challenges of this doctoral journey. Declaration I hereby declare that this Doctoral Dissertation was carried out by me for the degree of Doctor of Philosophy under the guidance and supervision of my supervisors. This dissertation is my own work and includes nothing, which is the outcome of work done in collaboration except as specified in the text.
It is not substantially the same as any I have submitted for a degree, diploma or other qualification at any other university; and no part has already been, or is currently being submitted for any degree, diploma or other qualification. Hanoi, August 2024 Author Nguyen Thu Trang i Abstract Software Product Line (SPL) systems are becoming popular and widely employed to de- velop large industrial projects. However, their inherent variability characteristics pose extreme challenges for assuring the quality of these systems. Although automated de- bugging in single-system engineering has been studied in-depth, debugging SPL systems remains mostly unexplored.
In practice, debugging activities in SPL systems are often performed manually in an ad-hoc manner. This dissertation sheds light on the automated debugging SPL systems by focusing on three fundamental tasks, including false-passing product detection, variability fault localization, and variability fault repair. First, this dissertation aims to improve the reliability of the test results by detecting false- passing products in SPL systems failed by variability bugs. Given a set of tested products of an SPL system, the proposed approach, Clap, collects failure indications in failing products based on their implementation and test quality.
For a passing product, Clap evaluates these indications, and the stronger the indications, the more likely the product is false-passing. Specifically, the possibility of the product being false-passing is evaluated based on if it has a large number of statements that are highly suspicious in the failing products and if its test suite is lower quality compared to the failing products’ test suites. Second, this dissertation presents VarCop, a novel and effective variability fault localiza- tion approach. For an SPL system failed by variability bugs, VarCop isolates suspicious code statements by analyzing the overall test results of the sampled products and their source code.
The isolated suspicious statements are the statements related to the inter- action among the features that are necessary for the visibility of the bugs in the system. In VarCop, the suspiciousness of each isolated statement is assessed based on both the overall test results of the products containing the statement as well as the detailed results of the test cases executed by the statement in these products. Third, this dissertation proposes two approaches, product-based and system-based, to repair the variability bugs in an SPL system to fix the failures of the failing products and not to break the correct behaviors of the passing products. For the product-based approach, each failing product is fixed individually, and the obtained patches are then propagated and validated on the other products of the system.
For the system-based approach, all the products are repaired simultaneously. The patches are generated and validated by all the sampled products of the system in each repair iteration. Moreover, to improve the repair performance of both approaches, this dissertation also introduces several heuristic rules for effectively and efficiently deciding where to fix (navigating modification points) and how to fix (selecting suitable modifications). These heuristic rules use intermediate validation results of the repaired programs as feedback to refine the fault localization results and ii evaluate the suitability of the modifications before actually applying and validating them by test execution.
To evaluate the proposed approaches, this dissertation conducted several experiments on a large public dataset of buggy SPL systems. The experimental results show that Clap can effectively detect false-passing and true-passing products with an average accuracy of more than 90%. Especially, the precision of false-passing product detection by Clap is up to 96%. This means among ten products predicted as false-passing products, more than nine products are precisely detected.
For variability fault localization, VarCop significantly improves two state-of-the-art tech- niques by 33% and 50% in ranking the incorrect statements in the systems containing a single bug each. In about two-thirds of the cases, VarCop correctly ranks the buggy statements at the top-3 positions in the ranked lists. For the cases containing multiple bugs, VarCop outperforms the state-of-the-art approaches two times and ten times in the proportion of bugs localized at the top-1 positions. Furthermore, for repairing variability faults, the experimental results show that the product- based approach is around 20 times better than the system-based approach in the number of correct fixes.
Notably, the heuristic rules could improve the performance of both ap- proaches by increasing of 30-150% the number of correct fixes and decreasing of 30-50% the number of attempted modification operations. Keywords: Software product line, variability fault, coincidential correctness, fault local- ization, automated program repair iii Contents Acknowledgement Declaration i Abstract ii TABLE OF CONTENTS iv List of Figures viii List of Tables x Acronyms xii Chapter 1 Introduction 1 1.2 Objective and Contributions .3 Research methodology and Scope. 11 Chapter 2 Background and Literature Review 12 2.1 Software Product Line .2 Testing Software Product Lines .4 Automated Program Repair .3 Benchmarks for Software Product Lines. 30 Chapter 3 False-passing Product Detection 33 3.2 Motivation and Problem Formulation .3 False-passing Product Detection .1 Suspiciousness of Product Implementation .4 Detecting False-passing Products .4 Mitigation of Negative Impact of False-passing Products on Variability Fault Localization .2 Mitigating Impact of False-passing Products on Fault Localization (RQ2) .6 Threats to Validity.
69 Chapter 4 Variability Fault Localization 71 4.1 An Example of Variability Faults in Software Product Lines .1 Feature Interaction Formulation .2 The Root Cause of Variability Failures .4 Buggy Partial Configuration Detection .1 Buggy Partial Configuration .2 Important Properties to Detect Buggy Partial Configuration .3 Buggy Partial Configuration Detection Algorithm .5 Suspicious Statement Identification .6 Suspicious Statement Ranking .1 Product-based Suspiciousness Assessment .2 Test Case-based Suspiciousness Assessment .2 Evaluation Setup, Procedure, and Metrics .1 Accuracy and Comparison (RQ1) .4 Performance in Localizing Multiple Bugs (RQ4) .6 Threats to Validity. 111 Chapter 5 Automated Variability Fault Repair 112 5.3 Automated Variability Fault Repair .1 Product-based Approach (P rodBasedbasic ) .2 System-based Approach (SysBasedbasic ) .3 Product-based Approach vs System-based Approach .4 Heuristic Rules for Improving the Repair Performance .1 Heuristic Rules for Improving the Performance of Automated Program Repair Tools .2 Applying the Heuristic Rules in Repairing Variability Faults .2 Evaluation Procedure and Metrics .4 Threats to Validity. 153 Chapter 6 Conclusion 155 List of Publications 159 References 160 vii List of Figures 1.1 The proposed debugging process of SPL systems .1 Overview of an engineering process for software product lines[1] .2 An example of feature model of Elevator system .3 SPL testing interest: actual test of products [2] .4 Example of sampling algorithms [3] .5 Program spectrum of a program with n elements and m test cases .6 Example of program spectrum and FL results by Tarantula and Ochiai .7 Standard steps in the pipeline of the test-suite-based program repair .2 The presence of the suspicious statements in the passing products .3 The presence of bug-involving statements in the passing products .4 The portion of suspicious statements in the passing products which are not covered by their test suites .5 The undiagnosability (DDU’) of the passing products’ test suites .6 The incorrectness verification of the passing products’ test suites .7 The correctness reflectability of the passing products’ test suites .2 Hit@1–Hit@5 of VarCop, S-SBFL and SBFL .3 Performance by number of involving features of bugs .4 Impact of Buggy PC Detection on performance .5 Impact of Normalization on performance .6 Impact of choosing score(s, M ) on performance .7 Impact of choosing combination weight on performance .8 Impact of the sample size on performance .9 Impact of the size of test set on performance .10 VarCop, S-SBFL and SBFL in localizing multiple bugs .1 The feature model of the ExamDB system .2 The process of APR with the two proposed heuristic rules .3 RQ2 – Impact of the suitability threshold θ on P rodBasedenhanced ’s perfor- mance .4 RQ2 – Impact of the suitability parameters (α, β) on P rodBasedenhanced ’s performance .5 RQ3 – The performance of P rodBasedenhanced in fixing variability bugs of different SPL systems .6 RQ3 – Impact of the number of failing products on P rodBasedenhanced ’s performance – BankAccount .7 RQ3 – Impact of the number of suspicious statements on P rodBasedenhanced ’s performance – BankAccount. 152 ix List of Tables 2.1 The sampled products and their overall test results .2 Several popular SBFL formulae [4] .1 Empirical study about the impact of false-passing products on variability fault localization performance (in Rank ) .2 Products’ test suites before and after being transformed .4 Accuracy of false-passing product detection model .5 Mitigating the false-passing products’ negative impact on FL performance .6 Impact of different experimental scenarios .7 Clap’s performance on each system in system-based edition .8 Clap’s performance on each system in within-system edition .9 Impact of different training data sizes (the number of systems) .10 Impact of attributes on Clap’s performance .1 The sampled products and their overall test results .3 Performance of VarCop, SBFL, the combination of Slicing and SBFL (S- SBFL), and Arrieta et al.4 Performance by Mutation Operators .5 Performance by Code Elements of Bugs .1 The tested products of ExamDB system and their test results .