Precise Analysis of String Expressions

Aske Simon Christensen; Anders Møller; Michael Ignatieff Schwartzbach

doi:10.1007/3-540-44898-5_1

Precise Analysis of String Expressions

Aske Simon Christensen, Anders Møller, Michael Ignatieff Schwartzbach

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

272 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Static Analysis : 10th International Symposium, SAS 2003 San Diego, CA, USA, June 11-13, 2003 Proceedings
Number of pages	18
Publisher	Springer
Publication date	2003
Pages	1-18
ISBN (Print)	3-540-40325-6
DOIs	https://doi.org/10.1007/3-540-44898-5_1
Publication status	Published - 2003
Event	Static Analysis International Symposium. SAS 2003 - San Diego, California, United States Duration: 11 Jun 2003 → 13 Jun 2003 Conference number: 10

Conference

Conference	Static Analysis International Symposium. SAS 2003
Number	10
Country/Territory	United States
City	San Diego, California
Period	11/06/2003 → 13/06/2003

Series	Lecture Notes in Computer Science
Volume	2694
ISSN	0302-9743

Keywords

Regular language
Static analysis
Graph flow
Flow graphs
Fluence graph
SQL
Regular expression
Speech recognition
Context free grammar
Data flow
Database query
JAVA language
Program verification
Program analysis
Character string

Access to Document

10.1007/3-540-44898-5_1

Cite this

@inproceedings{1f432f003e9811dcbee902004c4f4f50,

title = "Precise Analysis of String Expressions",

abstract = "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.",

keywords = "Regular language, Static analysis, Graph flow, Flow graphs, Fluence graph, SQL, Regular expression, Speech recognition, Context free grammar, Data flow, Database query, JAVA language, Program verification, Program analysis, Character string",

author = "Christensen, {Aske Simon} and Anders M{\o}ller and Schwartzbach, {Michael Ignatieff}",

year = "2003",

doi = "10.1007/3-540-44898-5_1",

language = "English",

isbn = "3-540-40325-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--18",

booktitle = "Static Analysis",

address = "Netherlands",

note = "Static Analysis International Symposium. SAS 2003 ; Conference date: 11-06-2003 Through 13-06-2003",

}

Christensen, AS, Møller, A & Schwartzbach, MI 2003, Precise Analysis of String Expressions. in Static Analysis: 10th International Symposium, SAS 2003 San Diego, CA, USA, June 11-13, 2003 Proceedings. Springer, Lecture Notes in Computer Science, vol. 2694, pp. 1-18, Static Analysis International Symposium. SAS 2003, San Diego, California, United States, 11/06/2003. https://doi.org/10.1007/3-540-44898-5_1

Precise Analysis of String Expressions. / Christensen, Aske Simon; Møller, Anders; Schwartzbach, Michael Ignatieff.
Static Analysis: 10th International Symposium, SAS 2003 San Diego, CA, USA, June 11-13, 2003 Proceedings. Springer, 2003. p. 1-18 (Lecture Notes in Computer Science, Vol. 2694).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Precise Analysis of String Expressions

AU - Christensen, Aske Simon

AU - Møller, Anders

AU - Schwartzbach, Michael Ignatieff

N1 - Conference code: 10

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Regular language

KW - Static analysis

KW - Graph flow

KW - Flow graphs

KW - Fluence graph

KW - SQL

KW - Regular expression

KW - Speech recognition

KW - Context free grammar

KW - Data flow

KW - Database query

KW - JAVA language

KW - Program verification

KW - Program analysis

KW - Character string

U2 - 10.1007/3-540-44898-5_1

DO - 10.1007/3-540-44898-5_1

M3 - Article in proceedings

SN - 3-540-40325-6

T3 - Lecture Notes in Computer Science

SP - 1

EP - 18

BT - Static Analysis

PB - Springer

T2 - Static Analysis International Symposium. SAS 2003

Y2 - 11 June 2003 through 13 June 2003

ER -

Precise Analysis of String Expressions

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this