String Analysis with Logic Circuit Representation: Theory and Applications
Date Issued
2016
Date
2016
Author(s)
Wang, Hung-En
Abstract
Many severe security vulnerabilities in web applications can be attributed to string manipulation mistakes, which can often be avoided through formal string analysis. String analysis tools are indispensable and under active development. Prior string analysis methods are primarily automata-based or satisfiability-based. The two approaches exhibit distinct strengths and weaknesses. Specifically, existing automata-based methods have difficulty in generating counterexamples at system inputs to witness vulnerability, whereas satisfiability-based methods are inadequate to produce filters amenable for firmware or hardware implementation for real-time screening of malicious inputs to a system under protection. In this thesis, we propose a new string analysis method based on a scalable logic circuit representation for (nondeterministic) finite automata to support various string and automata manipulation operations. It enables both counterexample generation and filter synthesis in string constraint solving. By using the new data structure, automata with large state spaces and/or alphabet sizes can be efficiently represented. Empirical studies on a large set of open source web applications and well-known attack patterns demonstrate the unique benefits of our method compared to prior string analysis tools.
Subjects
String Constraint
Automata
Logic Circuits
Security
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R03943083-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):9498545de1d0bd898c07f893d2facc41