Name
Abstract | ||
|---|---|---|
Reasoning about string variables, in particular program inputs, is an important aspect of many program analyses and testing frameworks. Program inputs invariably arrive as strings, and are often manipulated using high-level string operations such as equality checks, regular expression matching, and string concatenation. It is difficult to reason about these operations because they are not well-integrated into current constraint solvers. We present a decision procedure that solves systems of equations over regular language variables. Given such a system of constraints, our algorithm finds satisfying assignments for the variables in the system. We define this problem formally and render a mechanized correctness proof of the core of the algorithm. We evaluate its scalability and practical utility by applying it to the problem of automatically finding inputs that cause SQL injection vulnerabilities. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1542476.1542498 | Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation |
Keywords | Field | DocType |
sql injection,regular expression,regular language,satisfiability,system of equations | String searching algorithm,Constraint satisfaction,Regular expression,Programming language,Computer science,Theoretical computer science,Concatenation,Program analysis,Regular language,String (computer science),String operations | Conference |
Volume | Issue | ISSN |
44 | 6 | 0362-1340 |
Citations | PageRank | References |
49 | 2.22 | 35 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pieter Hooimeijer | 1 | 598 | 26.19 |
| Westley Weimer | 2 | 3510 | 162.27 |