Abstract
Mixed concrete and symbolic execution is an important technique for finding and understanding software bugs, including securityrelevant ones. However, existing symbolic execution techniques are limited to examining one execution path at a time, in which symbolic variables reflect only direct data dependencies. We introduce loop-extended symbolic execution, a generalization that broadens the coverage of symbolic results in programs with loops. It introduces symbolic variables for the number of times each loop executes, and links these with features of a known input grammar such as variable-length or repeating fields. This allows the symbolic constraints to cover a class of paths that includes different numbers of loop iterations, expressing loop-dependent program values in terms of properties of the input. By performing more reasoning symbolically, instead of by undirected exploration, applications of loop-extended symbolic execution can achieve better results and/or require fewer program executions. To demonstrate our technique, we apply it to the problem of discovering and diagnosing buffer-overflow vulnerabilities in software given only in binary form. Our tool finds vulnerabilities in both a standard benchmark suite and 3 real-world applications, after generating only a handful of candidate inputs, and also diagnoses general vulnerability conditions.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the 18th International Symposium on Software Testing and Analysis, ISSTA 2009 |
Publisher | Association for Computing Machinery, Inc |
Pages | 225-235 |
Number of pages | 11 |
ISBN (Electronic) | 9781605583389 |
DOIs | |
State | Published - Jul 19 2009 |
Event | 18th International Symposium on Software Testing and Analysis, ISSTA 2009 - Chicago, United States Duration: Jul 19 2009 → Jul 23 2009 |
Publication series
Name | Proceedings of the 18th International Symposium on Software Testing and Analysis, ISSTA 2009 |
---|
Other
Other | 18th International Symposium on Software Testing and Analysis, ISSTA 2009 |
---|---|
Country/Territory | United States |
City | Chicago |
Period | 7/19/09 → 7/23/09 |
Bibliographical note
Publisher Copyright:Copyright 2009 ACM.