DocumentCode :
2799514
Title :
An Efficient 2-Phase Strategy to Achieve High Branch Coverage
Author :
Prabhu, Sarvesh ; Hsiao, Michael S. ; Krishnamoorthy, Saparya ; Lingappan, Loganathan ; Gangaram, Vijay ; Grundy, Jim
Author_Institution :
Dept. of Electr. & Comput. Eng, Virginia Tech, Blacksburg, VA, USA
fYear :
2011
fDate :
20-23 Nov. 2011
Firstpage :
167
Lastpage :
174
Abstract :
We present a new 2-phase symbolic execution driven strategy that achieves high branch coverage in software quickly. Phase 1 follows a greedy approach that quickly covers as many branches as possible by exploring each branch through its corresponding shortest path prefix. Phase 2 covers the remaining branches that are left uncovered if the shortest path to the branch was infeasible. In Phase 1, a basic conflict-driven learning is used to skip all the paths that may have any of the earlier encountered conflicting conditions, while in Phase 2, a more intelligent conflict-driven learning is used to skip regions that do not have a feasible path to any unexplored branch. This results in considerable reduction in unnecessary SMT solver calls. Experimental results show that significant speedup can be achieved, effectively reducing the time to detect a bug and providing higher branch coverage for a fixed time-out period than previous techniques.
Keywords :
computability; greedy algorithms; program debugging; program testing; 2-phase symbolic execution; SMT solver calls; bug detection; fixed time-out period; greedy approach; high branch coverage; intelligent conflict-driven learning; satisfiability modulo theory; shortest path prefix; Complexity theory; Databases; Explosions; Radiation detectors; Silicon; Software; Testing; branch coverage; conflict-driven learning; software testing; symbolic execution;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Test Symposium (ATS), 2011 20th Asian
Conference_Location :
New Delhi
ISSN :
1081-7735
Print_ISBN :
978-1-4577-1984-4
Type :
conf
DOI :
10.1109/ATS.2011.83
Filename :
6114531
Link To Document :
بازگشت