Discovering neglected conditions in software by mining program dependence graphs
by Chang, Ray-Yaung, Ph.D., CASE WESTERN RESERVE UNIVERSITY, 2008, 181 pages; 3375077

Abstract:

Neglected conditions are an important but difficult-to-find class of software defects. This thesis presents an intraprocedural approach and an interprocedural approach to revealing neglected conditions that integrate static program analysis and advanced data mining techniques to discover implicit conditional rules in a code base and rule violations that indicate neglected conditions. The approaches require the user to indicate minimal constraints on the context of the rules to be sought, rather than specific rule templates. In order to permit this generality, rules are modeled as graph minors of enhanced procedure dependence graphs (EPDGs), in which control and data dependence edges are augmented by edges representing shared data dependences. Greedy algorithms for mining maximal frequent subgraphs and frequent graph minors are used to extract candidate rules from EPDGs, and heuristic algorithms based on graph matching are used to identify rule violations. The evaluation of our approaches on open source projects such as the openssl, net-snmp , and Apache projects demonstrates that our approaches based on mining program dependence graphs are able to discover a significant number of neglected conditions. The experimental results show that our approaches detected 62 new bugs from the latest versions of these applications, with 35 of them confirmed and fixed by developers according to our reports. More interestingly, our empirical study indicates that our approaches are able to discover ordering rules, which involve ordering of function calls, and the corresponding rule violations also.

 
AdviserH. Andy Podgurski
SchoolCASE WESTERN RESERVE UNIVERSITY
SourceDAI/B 70-09, p. , Nov 2009
Source TypeDissertation
SubjectsComputer engineering
Publication Number3375077
Adobe PDF Access the complete dissertation:
 

» Find an electronic copy at your library.
  Use the link below to access a full citation record of this graduate work:
  http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3375077
  If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.