Strategies for Scalable Symbolic Execution-based Test Generation

dc.contributor.authorKrishnamoorthy, Saparyaen
dc.contributor.committeechairHsiao, Michael S.en
dc.contributor.committeememberPlassmann, Paul E.en
dc.contributor.committeememberSchaumont, Patrick R.en
dc.contributor.departmentElectrical and Computer Engineeringen
dc.description.abstractWith 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.en
dc.description.degreeMaster of Scienceen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.subjectsymbolic executionen
dc.subjectsoftware verificationen
dc.subjectdynamic test generationen
dc.subjectpath explosionen
dc.subjectsatisfiability modulo theoriesen
dc.titleStrategies for Scalable Symbolic Execution-based Test Generationen
dc.typeThesisen and Computer Engineeringen Polytechnic Institute and State Universityen of Scienceen
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
869.47 KB
Adobe Portable Document Format