Static Approximation of Dynamically Generated Web Pages
Yasuhiko Minamide
Department of Computer Science
University of Tsukuba
Tsukuba 305-8573, Japan

minamide@cs.tsukuba.ac.jp

ABSTRACT

called cross-site scripting, which may cause leakage of critical information such as HTTP cookies. It is critical for aserver-side program to prevent this kind of vulnerability andto guarantee security.
We have applied static program analysis to static checking of properties of Web pages generated dynamically by aserver-side program. Our analysis approximates the string
output of a program with a context-free grammar. The
approximation obtained by the analysis is conservative inthe sense that it contains any possible output string that
could be generated by the program. By applying the analysis to a server-side program, its dynamically generated Web
pages can also be approximated with a context-free grammar. Then, the approximation obtained by the analysis has
many applications in checking the validity and security of aserver-side program.
We have applied the analysis to detect cross-site scripting
vulnerabilities in a server-side program. The vulnerabilities
can be detected by checking the approximation against the
speciﬁcations of safe or unsafe strings. For example, Web
pages that do not include code executed at the client side
are considered to be safe strings.
The second application of our analysis is HTML validation. We present two approaches to validating pages dynamically generated by a server-side program. The ﬁrst
approach is to generate sample Web pages from the grammar and validate them with a standard HTML validation
tool. The second approach is to check the approximation
against the HTML speciﬁcation. This requires to solve an
undecidable problem whether a context-free language is a
sublanguage of another context-free language. However, by
taking the characteristics of the pages generated by a serverside script into consideration, we show that the Web pages
generated by the majority of server-side programs can bevalidated.
Our analysis is based on the Java string analyzer of Christensen, Møller and Schwartzbach [7]. Their analyzer approximates the value of a string expression in a Java programwith a regular language instead of a context-free language.
Both their and our analyzers ﬁrst extract a grammar withstring operations from a program. After this phase, ourstring analyzer directly eliminates string operations in thegrammar and transforms it into a context-free grammar. In
this phase, a string operation is modeled with an automatonwith output called a transducer. The theory of transducers
has crucial roles both in this phase and in applications of
our analysis.
To demonstrate the eﬀectiveness of our string analysis onServer-side programming is one of the key technologies that
support today’s WWW environment. It makes it possible
to generate Web pages dynamically according to a user’s
request and to customize pages for each user. However,
the ﬂexibility obtained by server-side programming makes
it much harder to guarantee validity and security of dynamically generated pages.
To check statically the properties of Web pages generated
dynamically by a server-side program, we develop a static
program analysis that approximates the string output of aprogram with a context-free grammar. The approximation
obtained by the analyzer can be used to check various properties of a server-side program and the pages it generates.
To demonstrate the eﬀectiveness of the analysis, we have
implemented a string analyzer for the server-side scripting
language PHP. The analyzer is successfully applied to publicly available PHP programs to detect cross-site scripting
vulnerabilities and to validate pages they generate dynamically.

Categories and Subject Descriptors
D.2.4 [Software Engineering]: Formal methods, Validation; F.3.2 [Semantics of Programming Languages]:
Program analysis

General Terms
Languages, Veriﬁcation, Security

Keywords
Server-side scripting, static analysis, context-free grammars,
cross-site scripting, HTML validation

1. INTRODUCTION
Server-side programming is one of the key technologies
that support today’s WWW environment. It makes it possible to generate Web pages dynamically according to a user’s
request and to customize pages for each user. However,
the ﬂexibility obtained by server-side programming makes
it much harder to guarantee validity and security of dynamically generated pages. For example, it is well known that
inappropriate treatment of input data causes vulnerabilities
Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use,and personal use by others.
WWW 2005, May 10-14, 2005, Chiba, Japan.
ACM 1-59593-046-9/05/0005.

432

This analysis works even if a program contains string operations other than concatenation. Let us consider the following revised program:server-side programs, we have implemented a string analyzer
for PHP. The analyzer takes two inputs: a PHP programand an input speciﬁcation that describes the set of possible input to the program. It then generates a context-freegrammar approximating the Web pages generated from the
input. The analyzer is successfully applied to publicly available PHP programs to detect cross-site scripting vulnerabilities and to validate pages they generate dynamically.

<?phpfor ($i = 0; $i < $n; $i++)$x = "0".$x."1";echo str_replace("00","0",$x);?>

Huang et al. also developed a static program analyzer for
PHP [12]. Their analyzer was based on trust analysis (information ﬂow analysis) and can be used to detect vulnerabilities such as cross-site scripting and SQL injection. Althoughboth their analyzer and ours can be applied to detect vulnerabilities in PHP programs, they diﬀer in principle andwe believe that neither analyzer has a theoretically better
ability to detect cross-site scripting vulnerabilities than theother.

where str_replace("00","0",$x) replaces the string 00 in$x with 0. The set of strings the variable $x may contain after the for loop is represented by the context-free grammar
above. Therefore, we can obtain the context-free grammar
for the output of the revised program if we know how agrammar is transformed by str_replace("00","0",$x).
A ﬁnite automaton with output called a transducer plays
a crucial rule here. A transducer has the key property thatthe image of a context-free language under a transducer iscontext-free [4]. Furthermore, many string operations canbe realized by transducers.
Let us consider str_replace("00","0",$x) in the example: this operation can be realized by the following transducer:

2. PHP STRING ANALYZER
PHP is one of the most popular server-side scripting languages used to generate Web pages dynamically [1]. We havedeveloped a string analyzer for PHP that approximates thestring output of a program as a context-free grammar. The
analyzer takes two inputs: a PHP program and an input
speciﬁcation. The input speciﬁcation is given as a regularexpression and describes the set of possible inputs to the
PHP program. In this section, we illustrate our string analyzer by examples. The internal structure of the analysis isdiscussed in Section 5.
To illustrate the string analysis, let us consider the following program.

0/

89:;
?>=<
1

A/0A,0/0

0/0

?/.-,
()*+
>=<
/ 89:;
2

A/A

where A is any character except 0. There are three states
0, 1 and 2 in this transducer: the state 0 is the start state,
and 0 and 2 are the ﬁnal states. The transitions labeledwith 0/ and A/0A mean that the transducer produces and 0A for the inputs 0 and A, respectively. For example,
this transducer outputs 0abc11 for the input 00abc11.
There is an algorithm to compute the image of a contextfree language under a transducer. Then, we can compute thefollowing context-free grammar with the start symbol S bycomputing the image of the previous context-free grammar.

<?php
for ($i = 0; $i < $n; $i++)$x = "0".$x."1";echo $x;?>
In PHP, the inﬁx operator dot represents string concatenation. This program concatenates the same number of "0"sto the left and "1"s to the right of $x: the number depends
on the value of $n.
The input speciﬁcation is given by specifying the initialvalues of global variables in our analyzer. The initial valuesof $x and $n are described in the following speciﬁcation.

SX→ abc | xyz | X1
→ 0abc | 0xyz | 0S1

This is the approximation obtained by our analyzer. This
grammar represents the following set of strings.

$x : /abc|xyz/$n : int∪

The speciﬁcation /abc|xyz/ is a regular expression representing the set of strings {abc, xyz}. Only the type is speciﬁed for the variable $n.
The idea of string analysis is to consider assignments as
production rules of a context-free grammar. By considering
assignments as production rules and translating the input
speciﬁcation into production rules, we can obtain the following grammar approximating the output of the program.
X
X
X


?>=<
89:;
()*+
/.-,
0
< V
|

{0n abc12n | n ≥ 0} ∪ {0n xyz12n | n ≥ 0}{0n+1 abc12n+1 | n ≥ 0} ∪ {0n+1 xyz12n+1 | n ≥ 0}

As we can see in this example, the output of a program canoften be precisely approximated even if it contains string
operations.

3.

DETECTING CROSS-SITE SCRIPTING
VULNERABILITIESWe consider detection of cross-site scripting vulnerabilities in PHP programs as the ﬁrst application of our analyzer.
A cross-site scripting vulnerability results from inappropriate treatment of input data and may cause leakage of criticalinformation such as HTTP cookies. To prevent the vulnerability, a string coming from a user input must be sanitized
before embedding it in a Web page. Sanitization is achieved

→ abc
→ xyz
→ 0X1

This grammar represents the set of strings, {0n abc1n | n ≥0} ∪ {0n xyz1n | n ≥ 0}, as we expect. Based on this idea,
we have developed a string analyzer for PHP.

433

by escaping the special characters such as < and & in HTML.
Let us consider the following PHP program.

Notice that the counter-example above cannot actually be
an output of the program because there is a for loop that
repeats twice in the program. This kind of impreciseness isinevitable in program analysis.

<html><body><?php$x = $_POST[’name’];//$x = htmlspecialchars($x);
for ($i = 0; $i < 2; $i++)
echo $x;?></body></html>

There is another mode of checking in our analyzer to specify the set of safe strings instead of unsafe strings. The
following regular expression speciﬁes the set of strings that
contain only the html and body tags:(<html>|</html>|<body>|</body>|[^<])*
where [^<] represents any character except <. This can beconsidered the speciﬁcation of the set of safe strings for the
program above. Without the sanitization code, our analyzer
shows a counter example as before. With the sanitization
code, it says that the PHP program is safe. This check is
conducted by computing the complement of the language ofthe regular expression. Because the complement of a regular language is regular, we can use the algorithm checking
disjointness between a regular language and a context-freelanguage as before.
Dynamically generated Web pages often contain code to
be executed at the client side identiﬁed by the script tag.
Then, it is not clear how to specify safe or unsafe strings.
Still, we can check whether the output of a PHP program
may contain an invalid tag such as <xyz>. If an output of the
program contains such a tag, the program is likely to havecross-site scripting vulnerabilities or at least some bugs.

This program receives a potentially unsafe input string froma Web browser in the associative array $_POST. The value
corresponding to the key name is assigned to the variable $x
and output in the for loop. Thus it may generate a Web
page with unsafe strings from the input and is therefore
vulnerable. This vulnerability is called a cross-site scripting
vulnerability. If the sanitization code that is commented out
in the code is enabled, the code is safe: htmlspecialchars
converts special characters such as < and & into the corresponding HTML entities: &lt; and &amp;. The resulting
string is safe to embed in a Web page.
We can detect cross-site scripting vulnerabilities by checking the approximation obtained by the string analyzer against
the speciﬁcation of the set of safe or unsafe strings. The approximation must be constructed for the input speciﬁcation
corresponding to the fact that any string might be sent by
a Web browser. The following is the speciﬁcation for thevariable $_POST.

Furthermore, our string analyzer can be used to check
what tags may appear in output, by applying a transducer
that extracts tags from a string. Our string analyzer hasa mode to specify a regular expression to extract strings
matching it from the approximation of the output. The
following regular expression speciﬁes the set of strings with< and > as the ﬁrst and last characters, respectively, with no< and > between them.

$_POST : [/.*/]
This represents an array which contains any string. A speciﬁcation of an array is given in the form [ reg ].
Let us consider detecting a cross-site scripting vulnerability by checking whether a Web page generated with a PHP
program may contain the <script> tag. A Web page containing this tag can be considered as an unsafe output fora program that is not expected to generate such a page.
To conduct this security check, we specify the set of unsafe
strings with the following regular expression.

<[^<>]*>
With sanitization, the analyzer shows the following results
for the program above.
</body></html><body><html>.*<script>.*
This regular expression denotes the set of strings that contain the <script> tag. Then, we can check whether thecontext-free language obtained by the analyzer is disjoint
with this set. If they are disjoint, it is guaranteed that theoutput cannot contain a <script> tag. Checking the previous program against the speciﬁcation above by our analyzer
produces the following counter example.

On the other hand, it says that the set of tags is not ﬁnite
without sanitization.

4.

HTML VALIDATIONAs the second application of our analyzer, we describeHTML validation of the Web pages dynamically generated
by a server-side program. There are several HTML validation tools that can validate a static Web page against theHTML speciﬁcation. However, to check that a server-side
program always generates valid Web pages, it must be extensively tested to cover all the possible execution path of the
program. This requires knowledge of the internal structureof the program and is very time consuming.
On the other hand, we can automatically test or checkthe validity of the pages based on the context-free grammar obtained by our analyzer. There are two approaches toHTML validation in our analyzer: the automated validation
test and matching validation.

<html><body><script></body></html>
That means that the program may produce the above output and thus may be unsafe. On the other hand, if thesanitization code is enabled, the analyzer says that the approximation of the output and the speciﬁcation are disjoint,
and therefore the code is safe. This check is done by analgorithm checking whether a context-free language is disjoint with a regular language. The algorithm is based on
the context-free graph reachability algorithm proposed forinterprocedural dataﬂow analysis [21, 15].

434

4.1 Automated Validation Testa PHP program always generates a valid HTML page. The
speciﬁcation of HTML can be described with a context-freegrammar. Hence, we had a validation algorithm if we had analgorithm to determine L1 ⊂ L2 for two context-free grammars L1 and L2 . Unfortunately, this problem is known to be
undecidable in general. However, taking the characteristicsof the pages generated by a server-side program into consideration, we can still validate the majority of server-side
programs.
We investigated the depth of nesting of tags in the pages
generated by server-side programs. We believe that in majority of cases, the nesting depth of tags in the generated
pages is bounded. We think that this holds because themajority of PHP programs are used to generate pages withtable-like structures.
If the nesting depth is bounded, the validity check canbe done in the following manner. First, the grammar Li ,specifying valid pages with the maximum tag-nesting depthi, is constructed from the context-free grammar LHTML
of the HTML speciﬁcation. With this restriction on thedepth, the language of Li is regular. Then, the context-freelanguage obtained by the analyzer is checked against Li : if
the language is a subset of Li , the program always generates
a valid HTML page with a depth that is equal to or lessthan i. This is repeated for i = 1, 2, 3, . . .. However, it will
be computationally expensive to construct Li (i = 1, 2, . . .)directly for LHTML and check the approximation againstthem.
We have implemented in our analyzer a simpliﬁed version of the validation above, which checks that start andend tags always match. We call this validation a matchingvalidation. Let us consider the following context-free grammar with the start symbol U specifying a set of strings that
contain matching head, title, and body tags1 .

The ﬁrst approach is to generate sample Web pages fromthe context-free grammar and check the pages with a standard HTML validator such as the W3C Markup Validation
Service [25] and WDG HTML Validator [20]. This approach
will be quite eﬀective if we can obtain a set of sample pages
which cover all the possible execution path.
Let us consider validation of the Web pages generated by
the following PHP program.
<head><title>test</title></head><body><?php
if ($_POST["abc"] == "abc")
echo "abc";
elseecho htmlspecialchars($_POST["xyz"]);?></body>To simplify discussion, we check this program for the input speciﬁcation $_POST : [/[a-z<]*/], representing arrays with strings consisting of lower case characters and thecharacter <. Then, our string analyzer extracts the following
sample pages if we ask the analyzer to extract three sample
pages.
<head><title>test</title></head><body>
abc</body>-------------------------------<head><title>test</title></head><body>
a</body>-------------------------------<head><title>test</title></head><body>&lt;</body>T
U

Then Li with the start symbol Ui is constructed as follows:

The validity of these pages can be checked with the standard
validation tools.
Furthermore, the test cases can be reduced with the following transducer, which removes the parts of a Web page
not related tags:

U0
T1
U1
T2
U2

</<

X/

6


?>=<
89:;
()*+
/.-,
0

"
b

89:;
?>=<
()*+
/.-,
1
h

→ <head> U </head> | <title> U </title> |<body> U </body>→  | TU

→ 
→ <head> U0 </head> | <title> U0 </title> |<body> U0 </body>→  | T1 U1→ <head> U1 </head> | <title> U1 </title> |<body> U1 </body>→  | T2 U2

Based on the series of grammars like Li , we have implemented a matching validation that checks that start andend tags always match in our analyzer.

Y /Y

>/>

where X is any character except < and Y is any character
except >. If we apply this transducer to the previous example, the approximation obtained by the analyzer is reduced
to a singleton set and thus can be completely checked by astandard validation tool.

5.

INSIDE THE STRING ANALYZER

We describe the algorithm to approximate the string output of a program with a context-free grammar. The analysis
consists of two phases: the ﬁrst phase extracts a grammar
extended with string operations and the second phase transforms the grammar into a context-free grammar. Transducers have crucial roles in the second phase.

4.2 Matching Validation
Because the validity checking described above cannot cover
all cases in general, it is not complete. Therefore, it is desirable to develop a validation algorithm to check whether

1435

For simplicity, we ignore the text except for the tags.

$O1 = ""$i1 = 0$S1 = ""
$O2 = $O1."abc"$i3 = φ($i1,$i2)/ $S3 = φ($S1,$S2)
if $i3 < 10

/ $T1 = str replace("x","xx",$S3)$O3 = $O2.$T1

$S2 = $S3."xy"$i2 = $i3+1
Figure 1: A PHP program in static single assignment form

5.1 Extracting a Grammar

Finally, we extract a grammar from a program in static
single assignment form. An assignment of the form x =φ(y, z) is translated into two productions: x → y and x → z
and the other assignments are directly translated into productions.

The ﬁrst phase of the analysis extracts a grammar froma program by considering assignments as production rules,
as we described in Section 2. However, we must translate
output functions into assignments and divide live ranges ofvariables to obtain precise approximations.
Let us consider the following program to illustrate how to
extract a grammar.

O1
S1
O2
S3
S3
S2
T1
O3

$i = 0; $S = "";echo "abc";
while ($i < 10) {$S = $S."xy";$i = $i + 1;}
$T = str_replace("x","xx",$S);
echo $T;

→
→
→
→
→
→
→
→



O1 abcS1
S2
S3 xy
str replace(x, xx, S3 )O2 T1

Notice that productions are generated only for assignments
related to string values here. This is done by using information obtained by the program analysis called alias analysis in
our implementation. The grammar extracted from a static
single assignment form in this way may not be context-free.
For example, the grammar above has the string operation
str replace in the right-hand side of a production. We callthis kind of grammar a context-free grammar with operation
productions. We describe in the next subsection how to obtain a context-free grammar from a grammar with operation
productions.

The ﬁrst step is to translate the output functions in the
program into assignments to treat them uniformly with otherassignments. For the translation, we introduce a global variable $O representing the current output. The previous example is translated as follows.
$O = "";$i = 0; $S = "";$O = $O."abc";
while ($i < 10) {$S = $S."xy";$i = $i + 1;}
$T = str_replace("x","xx",$S);$O = $O.$T;

5.2

Transforming a Grammar into a ContextFree Grammar

A grammar with operation productions is extracted froma program as described in the previous section. The next
phase is to transform it into a context-free grammar. We
can transform it into a context-free grammar representing
the same set of strings if the following conditions hold.

The value of $O is initialized to the empty string at the
beginning of execution. The function echo is translated into
a combination of an assignment and a concatenation.
Then, we translate the program into static single assignment form [2, 22] to represent constraints between variables
in greater detail. The result of the translation is shown in
Figure 1. In static single assignment form, each assignment
introduces a new variable and φ-functions are introduced
where control ﬂows merge. For example, $i3 = φ($i1,$i2)
means that $i1 is assigned to $i3 if its execution comes fromthe block above and $i2 is assigned to $i3 if its execution
comes from the block below.

• Each string operation in the grammar transforms acontext-free grammar into another context-free grammar.
• No string operation occurs in a cycle of productions.
The string operations in PHP are classiﬁed in Table 1
to discuss the ﬁrst of above conditions. The functions areclassiﬁed by considering them as functions with one argument by ﬁxing the other arguments. The second and lastrows show the number and examples of the functions in eachclass, respectively.

436

Classiﬁcation
homomorphism
transducer
pushdown transducer
others

# Ops
11
20
1
6

Operations
htmlspecialchars, strtolower, addslashes
str replace, trim, ucﬁrst, stripslashes
strip tags
strrev, str shuﬄe, str repeat, crypt, md5, sha1

Table 1: Classification of the string functions in the String Functions Section of the PHP manual• A homomorphism is a mapping from characters tostrings. The image of a context-free language under ahomomorphism is also context-free and it is straightforward to compute the grammar representing the image. For example, htmlspecialchars is a homomorphism as follows:
<
>
&
"
a
b
..
.

→

→

→

→

→

→

• There are operations not in the classes listed above:the class of context-free languages is closed for strrev,
but not closed for the others 2 .
The table shows that the class of context-free languages
is closed for a large proportion of the functions in PHP andthus they can be eliminated from a grammar. The otherkinds of functions are eliminated from a grammar by approximating it.

&lt;
&gt;
&amp;
&quot;ab..
.

• Any pushdown transducer is conservatively approximated by a transducer that forgets the stack of the
pushdown transducer.
• The output of some string operations is reasonably
approximated by a regular expression. For example,
the output of the function md5 is approximated withthe regular expression, [0-9a-f]{32}, representing 32character hexadecimal numbers.

• A transducer is a ﬁnite automaton with output, as described in Section 2. The image of a context-free grammar under a transducer is also context-free. We havedeveloped an algorithm to compute the image based on
the context-free graph reachability algorithm [21, 15].
The algorithm is expensive in the sense that the image
has O(n3 m) productions for a context-free grammar
with m productions and a transducer with n states.

The second condition “No string operation occurs in a cycle of productions,” is also crucial in obtaining a context-freegrammar precisely approximating a grammar with operation
productions. If we have a string operation in a cycle of productions, the language it generates may not be context-free.
Let us consider the following grammar with the start symbolS.

A transducer can be nondeterministic. The following is a nondeterministic transducer realizing the function rtrim, which strips whitespace from the end of astring:SS
TThe language it generates is {xn 0y n 1z n | n ≥ 0}, which is
not context-free. Therefore, we must approximate the language to obtain a context-free grammar for it. We adopted
the same approximation as the Java string analyzer [7]: computing the set of characters Σ the language may containand approximating the language with Σ∗ . For the example
above, we obtain the context-free language corresponding to{x, y, z, 0, 1}∗ . This results in a very rough approximation,
but this situation rarely occurs in a grammar extracted froma real PHP program.

S/S

S/

(

89:;
?>=<
()*+
/.-,
1 o

S/


?>=<
89:;
()*+
/.-,
0
Vb
N/N

"

89:;
?>=<
2

v

→ 01
→ str replace(0, x0y, T )→ str replace(1, 1z, S)

S/S

N/N

where S and N are space and nonspace characters,
respectively.
• A pushdown transducer is a pushdown automaton with
output. The image of a context-free grammar under apushdown transducer may not be context-free. We
found only one function in this class: the function
strip_tags strips HTML tags from a string. It leaves
the character > which does not have the matching < asfollows:

5.3

Regular Expression Functions

Scripting languages such as Perl and PHP oﬀer advantages in string manipulation by providing powerful string
manipulation functions based on regular expressions. They
are so powerful that the class of context-free languages is not
closed for them. However, they can often be approximatedwith a combination of transducers with suﬃcient accuracy.
Let us consider how to model the following string operation.

strip_tags("<<abc>>>>") = ">>"

2

A stack is necessary in modeling this function as an
automaton to count the number of unmatched < symbols.

The functions md5 and sha1 can theoretically be represented with transducers. However, they require a huge number of states.

437

This precisely represents the result of preg replace. However, the context-free grammar obtained in this method is
not precise in general, but an approximation.

preg_replace("/a([0-9]*)b/","x\\1y",$x)

Our analyzer dynamically constructs the transducers described above for a grammar with regular expression functions and translates it into a context-free grammar. To construct the transducers described above, the pattern strings
such as /a([0-9]*)b/ must be determined at ﬁrst. However, the pattern strings might be dynamically constructed
at runtime and not known statically. Thus, we apply ourstring analysis to the pattern string and approximate it witha ﬁnite set of strings 3 . Then, the method above is applied
for each pattern string.

This function replaces substrings matching a([0-9]*)b in $xwith x\\1y where \\1 is replaced with the string matching
the ﬁrst grouped subexpression ([0-9]*). The following
example clariﬁes the operation.
preg_replace("/a([0-9]*)b/","x\\1y","a01ba234b") = "x01yx234y"
A regular expression replacement function like this is approximated with a combination of transducers. To illustrate how a grammar is transformed by the transducers forthe function above, let us consider the following grammar Lwith the start symbol Y .
X
Y

→
→

6.

We have implemented a PHP string analyzer, which uses
a context-free grammar to approximates Web pages generated by a PHP program. It can be used for the various
kinds of checks we have described in this paper. The analyzer is implemented with the Objective Caml programming
language [14] and contains about 10,000 lines of code. It
consists of a library to manipulate formal languages including automata, transducers and context-free grammars, andthe analyzer itself. The analyzer supports basic features of
PHP, though not objects and references.
The analyzer ﬁrst translates a PHP program into a functional intermediate language, which is basically equivalent
to the static single assignment form. A grammar with string
operations is extracted from it. In this phase, we use alias
analysis to treat arrays. Finally, the context-free grammar
approximating it is obtained by the methods described in
Section 5.
The speciﬁcation of inputs is given in the following format.

 | X0aXb | b11a

The grammar is transformed by transducers as follows:
1. Construct the grammar approximating the set of strings
matching the pattern [0-9]* and occurring between aand b. It is done by the following transducer:
D/D

X/

6

 a/

89:;
?>=<
89:;
/ ?>=<
0
1

b/

?/.-,
()*+
>=<
/ 89:;
2hX/

where X is any character and D is any digit. The
transducer is applied to L and then we obtain the following grammar with the start symbol X1 .
X0
X1

→ X0 0 | 0→  | X0// specification for variables$x : [int]// array of integers$y : /abc|xyz/// string : regular expression// abc|xyz$_POST : [/.*/]// array containing any string

This grammar corresponds to the regular expression0∗ .
2. Construct the grammar approximating the set of strings
that the pattern is replaced with. It is obtained fromthe grammar above and the replacement string x\\1y.
X0
X1Z// specification of the return value of functions
isset : bool
mysql_num_fields : int
mysql_field_name : /.*/→ X0 0 | 0→  | X0
→ xX1 yThe speciﬁcation consists of two parts: speciﬁcation of variables and functions. For a variable, we can specify its typeor a regular expression representing its value. For a function, we can only specify the return value of the function.
No relationship between arguments and the return value canbe speciﬁed in our current implementation.

3. Construct the grammar representing the set of strings
that are obtained by replacing the substrings matchingwith a([0-9]*)b in L with Z. Then we obtain thefollowing grammar.
Y→

Z | b11a

We applied our string analyzer to several publicly available PHP programs. Table 6 summarizes our experiments:
it shows the number of nonterminals and productions of
the context-free grammar obtained by the analyzer, and thetime spent to analyze each program. Experiments were doneon a Linux PC with an AMD Athlon FX-53 processor (2.4GHz) and 4 GByte memory.

This transformation is done with two transducers usedby Mohri and Sproat [17] to compile context-sensitive
rewrite rules on strings.
Finally, we obtain the following grammar with the start symbol Y by combining the grammars in steps 2 and 3.
X0
X1
Y

IMPLEMENTATION AND
EXPERIMENTS→ X0 0 | 0→  | X0
→ xX1 y | b11a3

Currently, our analyzer fails if a pattern string argument
cannot be approximated with a ﬁnite set of strings. It will
be possible to adopt a rough approximation for that case.

438

Program
webchessschoolmate
faqforge
phpwims
timeclocktagit# lines
2224
8085
843
726
462
890

# nonterminals
300
7985
180
82
656
858365# productions
450
9505
443
226
1233
6961180

Time (sec)
0.36
39.92
0.16
0.13
0.15
4933.17

Table 2: Measurements: approximating outputs with a context-free grammar
In the programs, we found only one case where string
operations occurred in a cycle of productions. The following
is the simpliﬁed version of code found in the program tagit.

standard validation tool, some of them may be overlooked.
For example, we found the following bug in webchess.
If the echo function is executed, the code generates aninvalid page. The code should generate matching <p>
and </p>.

$a["abc"] = "ABC";$a["xyz"] = "XYZ";
foreach($a as $key=>$value)$x = eregi_replace($key, $value, $x);

if ($errMsg != "")echo("<p><h2><font color=’red’>".
$errMsg."</font></h2><p>\n");The variable $x appears on both left and right sides of
the assignment with eregi_replace. The string operation
eregi_replace thus appears in a cycle of productions extracted from the program. Hence, we can obtain only a very
rough approximation for tagit with this code. The result inthe table was obtained by commenting out this code.
The grammars obtained for the programs except tagit are
not large and the analysis does not take much time. On theother hand, the analysis of tagit generates a huge contextfree grammar. This comes from the following code:

This echo function is executed only when some error
occurs and thus the bug might be overlooked with tests
by a standard validation tool.
• We also found some false positive alarms in HTMLvalidation. The following is a simpliﬁed example ofcode that causes a false alarm.
if ($x != 0) echo ’<b> nonzero’;if ($x == 0) echo ’<b> zero’;echo ’</b>’;$post = str_replace(’[b]’, ’<b>’, $post);$post = str_replace(’[/b]’, ’</b>’, $post);$post = str_replace(’[i]’, ’<i>’, $post);$post = str_replace(’[/i]’, ’</i>’, $post);...

Our analyzer currently ignores the conditions in ifstatements. It is therefore impossible to ﬁnd that exactly one of the bodies of the if-statements is executedand thus it generates a string with the matching b tag.
This kind of false positive alarm was found only in the
program schoolmate.

where string replacement functions are repeatedly applied
to the same variable 17 times. Each replacement grows agrammar by some factor and thus the factor by which thegrammar is enlarged in total is exponential in the numberof replacement functions applied. This exponential behavior
appears in this program.

Finally, we applied the matching validation described in
Section 4.2 to the programs. The results are shown in thefollowing table. The programs were revised so that start

We also checked cross-site scripting vulnerabilities of the
programs by the method described in Section 3. The programs other than tagit do not sanitize input at all and we
could not ﬁnd interesting bugs causing cross-site scripting
vulnerabilities in those programs. In tagit, however, wefound the following sanitization code.

Programwebchess
faqforge
phpwims
timeclockschoolmate$tagitname = strip_tags($tagitname);$tagitname = stripslashes($tagitname);
The content of the variable $tagitname is sanitized. However, this variable is not used in the other ﬁles at all andinstead the variable $tagitnames is used there. This causesa cross-site scripting vulnerability.

Depth
9
10
9
14
17

Bugs
1
30
7
11
14

Opt tags
60003Time (sec)123.3345.64
63.93
145.617580.69

Table 3: Matching validationand end tags always matched: the column “Bugs” in thetable shows the number of bugs found in this revision andthe column “Opt tags” shows the number of optional tags
inserted so that start and end tags match. The table also
shows that the maximum depth of pages the programs may
generate and the time spent on checking.
Some PHP programs are not designed to generate a valid
HTML page when the program stops its execution with theexplicit exit commands: exit or die. Our analyzer has an

We have also checked the validity of the pages generated
by the programs and found that all of the programs may
generate invalid HTML pages.
• For most of the bugs, the required end tag matchinga start tag is omitted or the nesting of tags is invalid.
Although most of them may easily be found with a439

option not to analyze output if a program stops its execution
with an explicit exit command. The programs timeclock andschoolmate were checked in this mode.
The time spent on checking is large compared to the timespent obtaining a grammar approximating the output of aprogram. This is because a large automaton is constructed
for each depth and the computationally expensive algorithmof checking disjointness between a regular language and acontext-free language is applied. The complexity of the algorithm is O(m3 n3 ), where m is the number of terminals
and nonterminals in the grammar, and n is the number ofstates of the automaton [15]. The program tagit was excluded from this experiment because it is a bulletin board
program where a user can write a text with some tags on
the board, and then a page that it generates may have an
arbitrary depth and be an invalid HTML text.

ing validation. In his type system, a program that may
generate a document with an arbitrary depth can be typechecked against a context-free grammar. However, the grammar must be carefully crafted and a program must be written so that it is checked against it. The type system wasdesigned for an applied lambda calculus with string concatenation, and it was not discussed how to deal with string
operations other than concatenation.

7.2

Domain Specific Languages for HTML andXML

Extensive studies have been done in the area of designing
domain speciﬁc languages for HTML and XML [13, 5, 6, 11,3]. One of the key issues there is to guarantee validity ofdynamically generated documents.
Ladd and Ramming proposed the MAWL language [13]where an HTML document is constructed from templates.
A template is an HTML document with named gaps wherea string is inserted. This approach was extended to higherorder templates and adopted in the <bigwig> and JWIG
projects [5, 6]. To guarantee the validity of the operation
ﬁlling a gap with a string, JWIG applies a simple form ofstring analysis.
Hosoya and Pierce designed a statically typed XML processing language called XDuce based on the theory of ﬁnite
tree automata [11]. Finite tree automata have good mathematical properties including that it is decidable whether
the language accepted by one tree automata is included inthat accepted by another. The type system of XDuce has
similarities with string analysis in the sense that it is basedon the theory of formal languages. However, XDuce does
not directly work on strings, but on trees representing XML
documents.

7. RELATED WORK
7.1 String Analysis
Christensen, Møller and Schwartzbach developed a string
analyzer for Java, which approximates the value of a string
expression with a regular language [7]. The approximation
can be checked against the speciﬁcation of expected stringvalues embedded in the Java program. The key phase in
their analysis is a transformation developed by Mohri and
Nederhof [16] approximating a context-free language with aregular language. Our string analyzer diﬀers from theirs in
the following ways. Firstly, our analysis is based on contextfree languages instead of regular languages and thus our approximations can be more precise. The analysis is also simpliﬁed by removing the transformation of Mohri and Nederhof. Secondly, our analyzer approximates the whole output
of a program representing a Web page and thus can be used
to check properties of a dynamically generated Web page asa whole.
Syntax checking based on string analysis was extended totype checking by Gould et al. in the context of SQL query
strings [10]. They developed a system that guarantees that
SQL query strings generated by a Java program at runtime
are well typed. Their system is based on the Java string
analyzer of Christensen, Møller and Schwartzbach. The
context-free reachability algorithm is used for type checking. Their method can be incorporated into our analyzer.

7.3

Trust Checking

Vulnerabilities in a server-side program such as cross-site
scripting and SQL injection are caused by applying criticaloperations to untrusted (or tainted) data submitted by auser. It is possible to avoid such potential unsafe operations
by classifying data into trusted and untrusted data. Perl’staint mode keeps track of this classiﬁcation at runtime andensures that no untrusted data is used in potentially unsafe
operations [26]. Program analysis to statically classify data
was presented by Ørbæk [18] and Ørbæk and Palsberg [19].
This analysis was extended and adopted by the static analysis for PHP by Huang et al. [12]. These analyses are closely
related to information ﬂow analysis [8, 9] and can be considered as its duals.
A key concept in trust checking is conversion from untrusted to trusted data. Intuitively, sanitization functions
correspond to this conversion in server-side programming.
However, sanitization is done in a great variety of ways inpractice and it is diﬃcult to determine what are sanitization beforehand. On the other hand, security checks basedon string analysis are more declarative: the key concept inthis case is what are safe (or unsafe) strings.

It is possible to formulate string analysis as a type system.
A type system based on regular expressions was studied by
Tabuchi et al. for a minimal functional language with string
concatenation and pattern matching over strings [23]. By
adopting regular expressions as types, they could include
rich operations over types in their type structure, and thatmade it possible to capture precisely the behavior of patternmatching over strings in their type system. However, a full
type inference algorithm was not given in the paper. We
have not considered pattern matching in our analyzer since
PHP does not have it. It will be interesting to extend ouranalysis for pattern matching. The extension is not straightforward because our analysis is based on context-free grammars.
Recently, Thiemann presented a type system for string
analysis based on context-free grammars and presented a
type inference algorithm based on Earley’s parsing algorithm [24]. The type inference is incomplete as our match-

8.

CONCLUSION AND FUTURE WORK

We have designed and implemented a program analyzer
that approximates the output of a program with a contextfree grammar. The analyzer was successfully applied to publicly available PHP programs to detect cross-site scripting
vulnerabilities and to validate pages dynamically generated

440

by them. We are planning to extend our analyzer to support
the full features of PHP and to evaluate the analyzer further
for a wider range of PHP programs.
The theory of context-free languages and transducers has
a signiﬁcant role in our analysis. The grammar obtainedby the analysis is checked against a speciﬁcation by checking the disjointness of regular and context-free languages.
Transducers are used to model and approximate string operations in PHP, and to transform the grammars obtainedby the analysis for applications.
The precision of the approximation will be improved withtechniques available in compilers and other program analysis. We are planning to combine symbolic evaluation andmore precise alias analysis to improve approximations.

[11] H. Hosoya and B. Pierce. XDuce: A statically typed
XML processing language. ACM Transactions on
Internet Technology, 3(2):117–148, 2003.
[12] Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D. T. Lee,and S.-Y. Kuo. Securing web application code bystatic analysis and runtime protection. In Proceedingsof the 13th International World Wide Web
Conference, pages 40–52, 2004.
[13] D. A. Ladd and J. C. Ramming. Programming the
Web: An application-oriented language for
hypermedia service programming. In Proceedings ofthe 4th International World Wide Web Conference,
1995.
[14] X. Leroy. The Objective Caml system release 3.08:
Documentation and user’s manual, 2004.
http://caml.inria.fr/index-eng.html.
[15] D. Melski and T. Reps. Interconvertibility of a class of
set constraints and context-free language reachability.
Theoretical Computer Science, 248(1–2):29–98, 2000.
[16] M. Mohri and M.-J. Nederhof. Regular approximationof context-free grammars through transformation. In
Robustness in Language and Speech Technology, pages
153–163, 2001.
[17] M. Mohri and R. Sproat. An eﬃcient compiler forweighted rewrite rules. In 34th Meeting of the
Association for Computational Linguistics (ACL ’96),
Proceedings of the Conference, 1996.
[18] P. Ørbæk. Can you trust your data? In Proceedings of
the 6th International Conference on Theory andPractice of Software Development: TAPSOFT, volume
915 of LNCS, pages 575–590, 1995.
[19] P. Ørbæk and J. Palsberg. Trust in the λ-calculus.
Journal of Functional Programming, 7(6):557–591,
1997.
[20] L. Quinn. WDG HTML validator.
http://www.htmlhelp.com/tools/validator/.
[21] T. Reps. Program analysis via graph reachability.
Information and Software Technology,
40(11–12):701–726, 2000.
[22] B. K. Rosen, M. N. Wegman, and F. K. Zadeck.
Global value numbers and redundant computations.
In Proceedings of the 15th ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages,
pages 12–27, 1988.
[23] N. Tabuchi, E. Sumii, and A. Yonezawa. Regularexpression types for strings in a text processing
language. In Proceedings of International Workshop
on Types in Programming, ENTCS 75, 2002.
[24] P. Thiemann. Grammar-based analysis of string
expressions. In Proceedings of the ACM
SIGPLAN-SIGACT Workshop on Types in Language
Design and Implementation, pages 59–70, 2004.
[25] The W3C markup validation service.
http://validator.w3.org/.
[26] L. Wall, T. Christiansen, and J. Orwant. Programming
Perl (3rd Edition). O’Reilly, 2000.

9. ACKNOWLEDGMENTS
We would like to thank Nobuo Otoi for developing theformal language library used in our analyzer. This work
has been supported by CREST of JST and the Kayamori
Foundation of Informational Science Advancement.

10. REFERENCES[1] M. Achour, F. Betz, et al. PHP Manual, 2005.
http://www.php.net/docs.php.
[2] B. Alpern, M. N. Wegman, and F. K. Zadeck.
Detecting equality of variables in programs. In
Proceedings of the 15th ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages,
pages 1–11, 1988.
[3] V. Benzaken, G. Castagna, and A. Frisch. CDuce: an
XML-centric general-purpose language. In Proceedingsof the Eighth ACM SIGPLAN International
Conference on Functional Programming, pages 51–63,
2003.
[4] J. Berstel. Transductions and Context-Free Languages.
Teubner Studienbucher, 1979.
[5] C. Brabrand, A. Møller, and M. I. Schwartzbach. The<bigwig> project. ACM Transactions on Internet
Technology, 2(2):79–114, 2002.
[6] A. S. Christensen, A. Møller, and M. I. Schwartzbach.
Extending Java for high-level web service
construction. ACM Transactions on Programming
Languages and Systems, 25(6):814–875, 2003.
[7] A. S. Christensen, A. Møller, and M. I. Schwartzbach.
Precise analysis of string expressions. In Proceedingsof the Static Analysis Symposium (SAS), volume 2694
of LNCS, pages 1–18, 2003.
[8] D. E. Denning. A lattice model of secure information
ﬂow. Communications of ACM, 19(5):236–243, 1976.
[9] D. E. Denning and P. J. Denning. Certiﬁcation ofprograms for secure information ﬂow.
Communications of ACM, 20(7):504–513, 1977.
[10] C. Gould, Z. Su, and P. Devanbu. Static checking ofdynamically generated queries in databaseapplications. In Proceedings of the 26th International
Conference on Software Engineering, pages 645–654,
2004.

441