Title page for ETD etd-07132010-131953


Type of Document Master's Thesis
Author Krishnamoorthy, Saparya
Author's Email Address saparya@vt.edu
URN etd-07132010-131953
Title Strategies for Scalable Symbolic Execution-based Test Generation
Degree Master of Science
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Hsiao, Michael S. Committee Chair
Plassmann, Paul E. Committee Member
Schaumont, Patrick Robert Committee Member
Keywords
  • symbolic execution
  • software verification
  • dynamic test generation
  • path explosion
  • satisfiability modulo theories
Date of Defense 2010-06-28
Availability unrestricted
Abstract
With the advent of advanced program analysis and constraint solving techniques, several test generation tools use variants of symbolic execution. Symbolic techniques have been shown to be very effective in path-based test generation; however, they fail to scale to large programs due to the exponential number of paths to be explored. In this thesis, we focus on tackling this path explosion problem and propose search strategies to achieve quick branch coverage under symbolic execution, while exploring only a fraction of paths in the program. We present a reachability-guided strategy that makes use of the reachability graph of the program to explore unvisited portions of the program and a conflict driven backtracking strategy that utilizes conflict analysis to perform nonchronological backtracking. We also propose error-directed search strategies, that are aimed at catching bugs in the program faster, by targeting those parts of the program where bugs are likely to be found or those that are hard to reach. We present experimental evidence that these strategies can significantly reduce the search space and improve the speed of test generation for programs.
Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Krishnamoorthy_S_T_2010.pdf 890.34 Kb 00:04:07 00:02:07 00:01:51 00:00:55 00:00:04

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.