A novel invariants-based approach for automated software fault localization

Software Reliability;Bug Diagnosis;Fault Localization;Likely Invariants;Delta Debugging

Sahoo, Swarup K.

关键词: Software Reliability;    Bug Diagnosis;    Fault Localization;    Likely Invariants;    Delta Debugging;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/42269/Swarup_Sahoo.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Software bugs are everywhere. Not only do they infest software during development, but theyescape our extermination efforts and enter production code. In addition to severe frustrationto customers, software failures result in billions of dollars of lost revenue to service providers.The most important steps for debugging and eliminating a software failure are reproducingthe failure and finding its root cause, either during development time or during productionrun. Currently, debugging is a costly, time-consuming and manual process. Automatingsome of these steps will greatly help developers, reduce costs, increase productivity andsoftware reliability. In this thesis proposal, I propose a novel way of doing automatedsoftware bug diagnosis.Reproducing bug symptoms is a prerequisite for performing automatic bug diagnosis.Do bugs have characteristics that ease or hinder automatic bug diagnosis? As a first step,we conducted a thorough empirical study of several key characteristics of bugs that affectreproducibility at the production site [1]. We manually examined 266 randomly selectedbug reports of six server applications and consider their implications on automatic bugdiagnosis tools. Our results were promising. From the study, we found that nearly 82%of bug symptoms can be reproduced deterministically by re-running with the same set ofinputs at the production site. We further found that very few input requests are needed toreproduce most failures; in fact, just one input request after session establishment suffices toreproduce the failure in nearly 77% of the cases. We describe the implications of the resultson reproducing software failures and designing automated diagnosis tools for productionruns.We also propose an automatic diagnosis technique for isolating the root cause(s) of soft-ware failures after it is reproduced [2]. We use likely program invariants, constructed usingautomatically generated good inputs that are close to the fault-triggering input, to selecta set of candidate program locations which are possible root causes. We then trim the setof candidate root causes using software-implemented dynamic backwards slicing, plus twonew filtering heuristics: dependence filtering, and filtering via multiple failing inputs thatare also close to original failing input. Experimental results on 13 reported software bugsof three large open-source servers MySQL, Squid, Apache web server and LLVM C/C++clang compiler show that we are able to narrow down the number of candidate bug locationsto between 5 and 28 locations for 12 out of 13 software bugs, even in programs that arehundreds of thousands of lines long. In our earlier work, we also showed invariants basedtechniques can be leveraged to effectively detect permanent hardware faults [3].