A novel invariants-based approach for automated software fault localization

Sahoo, Swarup K.

Permalink

https://hdl.handle.net/2142/42269 Copy

Description

Title

A novel invariants-based approach for automated software fault localization

Author(s)

Sahoo, Swarup K.

Issue Date

2013-02-03T19:29:48Z

Director of Research (if dissertation) or Advisor (if thesis)

Adve, Vikram S.

Doctoral Committee Chair(s)

Adve, Vikram S.

Committee Member(s)

• Adve, Sarita V.
• Marinov, Darko
• Parthasarathy, Madhusudan
• Zorn, Benjamin

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

Software bugs are everywhere. Not only do they infest software during development, but they escape our extermination efforts and enter production code. In addition to severe frustration to 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 reproducing the failure and finding its root cause, either during development time or during production run. Currently, debugging is a costly, time-consuming and manual process. Automating some of these steps will greatly help developers, reduce costs, increase productivity and software reliability. In this thesis proposal, I propose a novel way of doing automated software 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 affect reproducibility at the production site [1]. We manually examined 266 randomly selected bug reports of six server applications and consider their implications on automatic bug diagnosis 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 of inputs at the production site. We further found that very few input requests are needed to reproduce most failures; in fact, just one input request after session establishment suffices to reproduce the failure in nearly 77% of the cases. We describe the implications of the results on reproducing software failures and designing automated diagnosis tools for production runs. 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 using automatically generated good inputs that are close to the fault-triggering input, to select a set of candidate program locations which are possible root causes. We then trim the set of candidate root causes using software-implemented dynamic backwards slicing, plus two new filtering heuristics: dependence filtering, and filtering via multiple failing inputs that are also close to original failing input. Experimental results on 13 reported software bugs of 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 locations to between 5 and 28 locations for 12 out of 13 software bugs, even in programs that are hundreds of thousands of lines long. In our earlier work, we also showed invariants based techniques can be leveraged to effectively detect permanent hardware faults [3].

Graduation Semester

2012-12

Permalink

http://hdl.handle.net/2142/42269

Copyright and License Information

Copyright 2012 Swarup Sahoo

Owning Collections