Precise Analysis of String Expressions

By Aske Simon Christensen, Anders Møller, Michael I. Schwartzbach. Sensors Applications Symposium, 2003

513 citations recorded by the source corpus.

We perform static analysis of Java programs to answer a simple question: which values may occur as results of string expressions? The answers are summarized for each expression by a regular language that is guaranteed to contain all possible values. We present several applications of this analysis, including statically checking the syntax of dynamically generated expressions, such as SQL queries. Our analysis constructs flow graphs from class files and generates a context-free grammar with a nonterminal for each string expression. The language of this grammar is then widened into a regular language through a variant of an algorithm previously used for speech recognition. The collection of resulting regular languages is compactly represented as a special kind of multi-level automaton from which individual answers may be extracted. If a program error is detected, examples of invalid strings are automatically produced. We present extensive benchmarks demonstrating that the analysis is efficient and produces results of useful precision.

Subfields: Artificial Intelligence, Software

View Paper: https://www.semanticscholar.org/paper/c146e9386cc0f90599332b06d33edacfffbe9bac

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Software

Citations in the corpus

AMNESIA: analysis and monitoring for NEutralizing SQL-injection attacks (2005, methodology): “It is worth noting that the JSA [5] technique generates Deterministic Finite Automata (DFAs), obtained by transforming each NDFA into a corresponding DFA.”
Saner: Composing Static and Dynamic Analysis to Validate Sanitization in Web Applications (2008, methodology): “In general, the precise modeling of cyclic string operations is a difficult problem [4, 24].”
Static Detection of Security Vulnerabilities in Scripting Languages (2006, methodology): “[3] develop a string analysis that approximates string values in a Java program using a context free grammar.”
Effective inter-component communication mapping in Android with Epicc: an essential step towards holistic security analysis (2013, unknown): “More complex analyses can be used if more precision is desired [7].”
Type Analysis for JavaScript (2009, unknown): “We design the analysis building on existing techniques, in particular recency abstraction [ 3 ].”
Static detection of cross-site scripting vulnerabilities (2008, background): “introduced the study of static string analysis for imperative (and real-world) languages by showing the usefulness of string analysis for analyzing reflective code in Java programs and checking for errors in dynamically generated SQL queries [1].”
HAMPI: a solver for string constraints (2009, methodology): “[7] have a static analysis tool to check for SQL injection vulnerabilities that uses automata-based techniques to represent over-approximation of string values.”
Using parse tree validation to prevent SQL injection attacks (2005, methodology): “Wasserman and Su [23] use the static analysis technique from [4] to generate finite state automata for modeling the set of valid SQL commands for each data access.”
Towards automatic generation of vulnerability-based signatures (2006, methodology): “performed string analysis on Java programs where type information is available [13].”
Profile-guided static typing for dynamic scripting languages (2009, methodology): “This is in contrast to using, e.g., purely static string analysis (Livshits et al. 2005; Christensen et al. 2003; Gould et al. 2004), which could easily over-approximate the set of strings seen at run time (Sawin and Rountev 2007).”
Amandroid: A Precise and General Inter-component Data Flow Analysis Framework for Security Vetting of Android Apps (2014, result): “For example, we could follow the approaches from prior research [13, 33].”
Sound and precise analysis of web applications for injection vulnerabilities (2007, methodology): “String analysis-based techniques [3, 20] use formal languages to characterize conservatively the set of values a string variable may assume at runtime.”