Static Detection of Security Vulnerabilities
in Scripting Languages

1  Introduction

• We present an interprocedural static analysis algorithm for PHP. A language as dynamic as PHP presents unique challenges for static analysis: language constructs (e.g., include) that allow dynamic inclusion of program code, variables whose types change during execution, operations with semantics that depend on the runtime types of the operands (e.g., <), and pervasive use of hash tables and regular expression matching are just some features that must be modeled well to produce useful results.
  
  To faithfully model program behavior in such a language, we use a three-tier analysis that captures information at decreasing levels of granularity at the intrablock, intraprocedural, and interprocedural levels. This architecture allows the analysis to be precise where it matters the most–at the intrablock and, to a lesser extent, the intraprocedural levels–and use agressive abstraction at the natural abstraction boundary along function calls to achieve scalability. We use symbolic execution to model dynamic features inside basic blocks and use block summaries to hide that complexity from intra- and inter-procedural analysis. We believe the same techniques can be applied easily to other scripting languages (e.g., Perl).
  
  
• We show how to use our static analysis algorithm to find SQL injection vulnerabilities. Once configured, the analysis is fully automatic. Although we focus on SQL injections in this work, the same techniques can be applied to detecting other vulnerabilities such as cross site scripting (XSS) and code injection in web applications.
  
  
• We experimentally validate our approach by implementing the analysis algorithm and running it on six popular web applications written in PHP, finding 105 previously unknown security vulnerabilities. We analyzed two reported vulnerabilities in PHP-fusion, a mature, widely deployed content management system, and construct exploits for both that allow an attacker to control or damage the system.²

2  Background

1. Natural integration with SQL: PHP provides nearly native support for database operations. For example, using inline variables in strings, most SQL queries can be concisely expressed with a simple function call

   
   $rows=mysql_query("UPDATE users SET 
       pass=`$pass' WHERE userid=`$userid'");
   

   Contrast this code with Java, where a database is typically accessed through prepared statements: one creates a statement template and fills in the values (along with their types) using bind variables:

   
   PreparedStatement s = con.prepareStatement
     ("UPDATE users SET pass = ? 
       WHERE userid = ?");
   s.setString(1, pass); s.setInt(2, userid);
   int rows = s.executeUpdate();
   

   
   
   
2. Dynamic types and implicit casting to and from strings: PHP, like other scripting languages, has extensive support for string operations and automatic conversions between strings and other types. These features are handy for web applications because strings serve as the common medium between the browser, the web server, and the database backend. For example, we can convert a number into a string without an explicit cast:

   
   if ($userid < 0) exit;
   $query = "SELECT * from users 
             WHERE userid = `$userid'";
   

   
   
   
3. Variable scoping and the environment: PHP has a number of mechanisms that minimize redundancy when accessing values from the execution environment. For example, HTTP get and post requests are automatically imported into the global name space as hash tables $_GET and $_POST. To access the name field of a submitted form, one can simply use $_GET[`name'] directly in the program.
   
   If this still sounds like too much typing, PHP provides an extract operation that automatically imports all key-value pairs of a hash table into the current scope. In the example above, one can use extract(_GET, EXTR_OVERWRITE) to import data submitted using the HTTP get method. To access the $name field, one now simply types $name, which is preferred by some to $_GET[`name'].

1. SQL injection made easy: Bind variables in Java have the benefit of assuring the programmer that any data passed into an SQL query remains data. The same cannot be said for the PHP example where malformed data from a malicious attacker may change the meaning of an SQL statement and cause unintended operations to the database. These are commonly called SQL injection attacks.
   
   In the example above (case 1), suppose $userid is controlled by the attacker and has value

   ' OR `1' = `1

   The query string becomes

   
   UPDATE users SET pass='...' 
   WHERE userid='' OR '1'='1'
   

   which has the effect of updating the password for all users in the database.
   
   
2. Unexpected conversions: Consider the following code:

   
   if ($userid == 0) echo $userid;
   

   One would expect that if the program prints anything, it should be “0”. Unfortunately, PHP implicitly casts string values into numbers before comparing them with an integer. Non-numerical values (e.g., “abc”) convert to 0 without complaint, so the code above can print anything other than a non-zero number. We can imagine a potential SQL injection vulnerability if $userid is subsequently used to construct an SQL query as in the previous case.
   
   
3. Uninitialized variables under user control: In PHP, uninitialized variables default to null. Some programs rely on this fact for correct behavior; consider the following code:

   
   extract($_GET, EXTR_OVERWRITE);
   for ($i=0;$i<=7;$i++)
     $new_pass .= chr(rand(97, 122)); // append one char
   mysql_query("UPDATE ... $new_pass ...");
   

   This program generates a random password and inserts it into the database. However, due to the extract operation on line 1, a malicious user can introduce an arbitrary initial value for $new_pass by adding an unexpected new_pass field into the submitted HTTP form data.

3  Analysis

• We parse the PHP source into abstract syntax trees (ASTs). Our parser is based on the standard open-source implementation of PHP 5.0.5 [13]. Each PHP source file contains a main section (referred to as the main function hereafter although it is not part of any function definition) and zero or more user-defined functions. We store the user-defined functions in the environment and start the analysis from the main function.

  ---

  
  CFG := build_control_flow_graph(AST);
  foreach (basic_block b in CFG)
    summaries[b] := simulate_block(b);
  return make_function_summary(CFG, summaries);
  

  
  
  

  Figure 1: Pseudo-code for the analysis of a function.

  
  
  

  ---

  
  
  
• The analysis of a single function is summarized in Figure 1. For each function in the program, the analysis performs a standard conversion from the abstract syntax tree (AST) of the function body into a control flow graph (CFG). The nodes of the CFG are basic blocks: maximal single entry, single exit sequences of statements. The edges of the CFG are the jump relationships between blocks. For conditional jumps, the corresponding CFG edge is labeled with the branch predicate.
  
  
• Each basic block is simulated using symbolic execution. The goal is to understand the collective effects of statements in a block on the global state of the program and summarize their effects into a concise block summary (which describes, among other things, the set of variables that must be sanitized³ before entering the block). We describe the simulation algorithm in Section 3.1.
  
  
• After computing a summary for each basic block, we use a standard reachability analysis to combine block summaries into a function summary. The function summary describes the pre- and post-conditions of a function (e.g., the set of sanitized input variables after calling the current function). We discuss this step in Section 3.2.
  
  
• During the analysis of a function, we might encounter calls to other user-defined functions. We discuss modeling function calls, and the order in which functions are analyzed, in Section 3.3.

3.1  Simulating Basic Blocks

---

function simulate_block(BasicBlock b) : BlockSummary
{
  state := init_simulation_state();
  foreach (Statement s in b) {
    state := simulate(s, state);
    if (state.has_returned || state.has_exited)
      break;
  }
  summary := make_block_summary(state);
  return summary;
}

Figure 2: Pseudo-code for intra-block simulation.

---

3.1.1  Outline

1. the end of the block;
   
   
2. a return statement. In this case, the current block is marked as a return block, and the simulator evaluates and records the return value;
   
   
3. an exit statement. In this case the current block is marked as an exit block;
   
   
4. a call to a user-defined function that exits the program. This condition is automatically determined using the function summary of the callee (see Sections 3.2 and 3.3).

3.1.2  Language

---

Type (τ) ::= str | bool | int | ⊤ Const (c) ::= string | int | true | false | null L-val (lv) ::= x | Arg#i | lv[e] Expr (e) ::= c | lv | e binop e | unop e | (τ) e Stmt (S) ::= lv ← e | lv ← f(e1, …, en)      | return e | exit | include e   binop ∈ { +, −, concat, ==, !=, <, >, … } unop ∈ { −, ¬ }

Figure 3: Language Definition

---

---

Value Representation   Loc (l) ::= x | l[string] | l[⊤] Init-Values (o) ::= l0 Segment (β) ::= string | contains(σ) | o | ⊥ String (s) ::= ⟨ β1, ..., βn ⟩ Boolean (b) ::= true | false | untaint(σ0, σ1) Loc-set (σ) ::= { l1, ..., ln } Integer (i) ::= k Value (v) ::= s | b | i | o | ⊤   Simulation State   State (Γ) : Loc → Value   (a) Value representation and simulation state.   Locations     Γ ⊢ x Lv ⇒   x   var   Γ ⊢ Arg#n Lv ⇒   Arg#n   arg        Γ ⊢ e E ⇒   l     Γ ⊢ e' E ⇒   v'    v'' = cast(v', str)     Γ ⊢ e[e'] Lv ⇒   ⎧ ⎨ ⎩ l[α]    if v'' = ⟨“α”⟩ l[⊤]    otherwise   dim      (b) L-values.   Expressions   Type casts: cast(k, bool) = ⎧ ⎨ ⎩ true    if k ≠ 0 false    otherwise cast(true, str) = ⟨“1”⟩ cast(false, str) = ⟨⟩ cast(v = ⟨ β1, ..., βn ⟩, bool)        = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ true    if (v ≠ ⟨“0” ⟩) ∧ n ∨ i=1 ¬ is_empty(βi) false    if (v = ⟨“0” ⟩) ∨ n ∧ i=1 is_empty(βi) ⊤    otherwise … Evaluation Rules:     Γ ⊢ lv Lv ⇒   l     Γ ⊢ lv E ⇒   Γ(l)   L-val        Γ ⊢ e1 E ⇒   v1    cast(v1, str) = ⟨ β1, ..., βn ⟩     Γ ⊢ e2 E ⇒   v2    cast(v2, str) = ⟨ βn+1, ..., βm ⟩     Γ ⊢ e1 concat e2 E ⇒   ⟨ β1, ..., βm ⟩   concat          Γ ⊢ e E ⇒   v    cast(v, bool) = v'     Γ ⊢ ¬ e E ⇒   ⎧ ⎪ ⎨ ⎪ ⎩ true      if v' = false false      if v' = true untaint(σ1, σ0)      if v' = untaint(σ0, σ1) ⊤      otherwise        not      (c) Expressions.

Figure 4: Intrablock simulation algorithm.

---

3.1.3  State

function f($a, $b) {
   if (...) return $a;
   else return $b;
}
$ret = f($x.$y, $z);

$ok = is_safe($userid);
if (!$ok) exit;

3.1.4  Locations and L-values

$hash = $_POST;
$key = 'userid';
$userid = $hash[$key];

3.1.5  Expressions

3.1.6  Statements

function validate($x) {
 if (!is_numeric($x)) exit;
 return;
}
function my_query($q) {
  global $db;
  mysql_db_query($db, $q);
}
validate($a.$b);
my_query("SELECT...WHERE a = '$a' AND c = '$c'");

3.1.7  Block summary

• Error set ( E): the set of input variables that must be sanitized before entering the current block. These are accumulated during simulation of function calls that require sanitized input.
  
  
• Definitions ( D): the set of memory locations defined in the current block. For example, in

  
  $a = $a.$b; $c = 123;
  

  we have D = { a, c }.
  
  
• Value flow ( F): the set of pairs of locations (l₁, l₂) where the string value of l₁ on entry becomes a sub-string of l₂ on exit. In the example above, F = { (a, a), (b, a) }.
  
  
• Termination predicate ( T): trueif the current block contains an exit statement, or if it calls a function that causes the program to terminate.
  
  
• Return value ( R): records the representation for the return value if any, undefined otherwise. Note that if the current block has no successors, either R has a value or T is true.
  
  
• Untaint set ( U): for each successor of the current CFG block, we compute the set of locations that are sanitized if execution continues onto that block. Sanitization can occur via function calls, casting to safe types (e.g., int, etc), regular expression matching, and other tests. The untaint set for different successors might differ depending on the value of branch predicates. We show an example below.

  
  validate($a);
  $b = (int) $c;
  if (is_numeric($d))
        ...
  

  As mentioned earlier, validate exits if $a is unsafe. Casting to integer also returns a safe result. Therefore, the untaint set is { a, b, d } for the true branch, and { a, b } for the false branch.

3.2  Intraprocedural Analysis

1. Error set ( E): the set of memory locations (variables, parameters, and hash accesses) whose value may flow into a database query, and therefore must be sanitized before invoking the current function. For the main function, the error set must not include any user-defined variables (e.g. $_GET[`...'] or $_POST[`...'])—the analysis emits an error message for each such violation.
   
   We compute E by a backwards reachability analysis that propagates the error set of each block (using the E, D, F, and U components in the block summaries) to the start block of the function.
   
   
2. Return set ( R): the set of parameters or global variables whose value may be a substring of the return value of the function. R is only computed for functions that may return string values. For example, in the following code, the return set includes both function arguments and the global variable $table (i.e., R = { table, Arg#1, Arg#2 }).

   
   function make_query($user, $pass) {
     global $table;
     return "SELECT * from $table ".
       "where user = $user and pass = $pass";
   }
   

   We compute the function return set by using a forward reachability analysis that expresses each return value (recorded in the block summaries as R) as a set of function parameters and global variables.
   
   
3. Sanitized values ( S): the set of parameters or global variables that are sanitized on function exit. We compute the set by using a forward reachability analysis to determine the set of sanitized inputs at each return block, and we take the intersection of those sets to arrive at the final result.
   
   If the current function returns a Boolean value as its result, we distinguish the sanitized value set when the result is trueversus when it is false(mirroring the untaint representation for Boolean values above). The following example motivates this distinction:

   
   function is_valid($x) {
     if (is_numeric($x)) return true;
     return false;
   }
   

   The parameter is sanitized if the function returns true, and the return value is likely to be used by the caller to determine the validity of user input. In the example above,
   S = ( false ⇒ {}, true ⇒ { Arg#1 })
   For comparison, the validate function defined previously has S = ( * ⇒ { Arg#1 }). In the next section, we describe how we make use of this information in the caller.
   
   
4. Program Exit ( X): a Boolean which indicates whether the current function terminates program execution on all paths. Note that control flow can leave a function either by returning to the caller or by terminating the program. We compute the exit predicate by enumerating over all CFG blocks that have no successors, and identify them as either return blocks or exit blocks (the T and R component in the block summary). If there are no return blocks in the CFG, the current function is an exit function.

3.3  Interprocedural Analysis

1. Pre-conditions: We use the error set ( E) in the function summary to identify the set of parameters and global variables that must be sanitized before calling this function. We substitute actual parameters for formal parameters in E and record any unsanitized non-constant segments of strings in the error set as the sanitization pre-condition for the current block.
   
   
2. Exit condition: If the callee is marked as an exit function (i.e., X is true), we remove any statements that follow the call and delete all outgoing edges from the current block. We further mark the current block as an exit block.
   
   
3. Post-conditions: If the function unconditionally sanitizes a set of input parameters and global variables, we mark this set of values as safe in the simulation state after substituting actual parameters for formal parameters.
   
   If sanitization is conditional on the return value (e.g., the is_valid function defined above), we record the intersection of its two component sets as being unconditionally sanitized (i.e., σ₀ ∩ σ₁ if the untaint set is (false ⇒ σ₀, true ⇒ σ₁)).
   
   
4. Return value: If the function returns a Boolean value and it conditionally sanitizes a set of input parameters and global variables, we use the untaint representation to model that correlation:

   Γ ⊢ lv Lv ⇒   l    Γ ⊢ e1 E ⇒   v1   …   Γ ⊢ en E ⇒   vn       Summary(f) = ⟨ E, R, S, X ⟩     S = (false ⇒ σ0, true ⇒ σ1)    σ* = σ0 ∩ σ1     σ0' = subst   v (σ0 − σ*)    σ1' = subst   v (σ1 − σ*)     Γ ⊢ lv ← f(e1, …, en) S ⇒   Γ[l ↦ untaint(σ0', σ1')]

   In the rule above, subst_v(σ) substitutes actual parameters (v_i) for formal parameters in σ.
   
   If the callee returns a string value, we use the return set component of the function summary ( R) to determine the set of input parameters and global variables that might become a substring of the return value:

   Γ ⊢ lv Lv ⇒   l    Γ ⊢ e1 E ⇒   v1   …   Γ ⊢ en E ⇒   vn       Summary(f) = ⟨ E, R, S, X ⟩    σ' = subst   v ( R)     Γ ⊢ lv ← f(e1, …, en) S ⇒   Γ[l ↦ contains(σ')]

4  Experimental Results

---

Application (KLOC)	Err Msgs	Bugs		(FP)	Warn
News Pro (6.5)	8	8		(0)	8
myBloggie (9.2)	16	16		(0)	23
PHP Webthings (38.3)	20	20		(0)	6
DCP Portal (121)	39	39		(0)	55
e107 (126)	16	16		(0)	23
Total	99	99		(0)	115

Table 1: Summary of experiments. LOC statistics include embedded HTML, and thus is a rough estimate of code complexity. Err Msgs: number of reported errors. Bugs: number of confirmed bugs from error reports. FP: number of false positives. Warn: number of unique warning messages for variables of unresolved origin (uninspected).

---

4.1  Case Study: Two Exploitable SQL Injection Attacks in PHP-fusion

/* php-files/lostpassword.php */
if (!preg_match("/^[0-9a-z]{32}$/", $account)) 
        $error = 1;
if (!$error) { /* database access using $account */ }
if ($error) redirect("index.php");

/* php-files/lostpassword.php */
for ($i=0;$i<=7;$i++)
   $new_pass .= chr(rand(97, 122)); 
...
$result = dbquery("UPDATE ".$db_prefix."users 
  SET user_password=md5('$new_pass') 
  WHERE user_id='".$data['user_id']."'");

UPDATE users SET user_password=md5('???????') 
  WHERE user_id='userid'

UPDATE users SET user_password=md5('abc'), 
      user_level='103', user_aim=('???????') 
  WHERE user_id='userid'

---

if (isset($msg_view)) {
  if (!isNum($msg_view)) fallback("messages.php");
  $result_where_message_id="message_id=".$msg_view;
} elseif (isset($msg_reply)) {
  if (!isNum($msg_reply)) fallback("messages.php");
  $result_where_message_id="message_id=".$msg_reply;
}
... /* ~100 lines later */ ...
} elseif (isset($_POST['btn_delete']) || 
  isset($msg_delete)) { // delete message
  $result = dbquery("DELETE FROM ".$db_prefix.
   "messages WHERE ".$result_where_message_id. // BUG
   " AND ".$result_where_message_to);

Figure 5: An exploitable vulnerability in PHP-fusion 6.00.204.

---

DELETE FROM messages WHERE 1=1 /* AND ...

5  Related Work

5.1  Static techniques

1. WebSSARI uses an intraprocedural algorithm and thus only models information flow that does not cross function boundaries.
   
   Large PHP codebases typically define a number of application specific subroutines handling common operations (e.g., query string construction, authentication, sanitization, etc) using a small number of system library functions (e.g., mysql_query). Our algorithm is able to automatically infer information flow and pre- and post-conditions for such user-defined functions whereas WebSSARI relies on the user to specify the constraints of each, a significant burden that needs to be repeated for each source codebase examined. Examples in Section 3.3 represent some common forms of user-defined functions that WebSSARI is not able to model without annotations.
   
   To show how much interprocedural analysis improves the accuracy of our analysis, we turned off function summaries and repeated our experiment on News Pro, the smallest of the five codebases. This time, the analysis generated 19 error messages (as opposed to 8 with interprocedural analysis). Upon inspection, all 11 extra reports are false positives due to user-defined sanitization operations.
   
   
2. WebSSARI does not seem to model conditional branches, which represent one of the most common forms of sanitization in the scripts we have analyzed. For example, we believe it will report a false warning on the following code:

   
   if (!is_numeric($_GET['x'])) 
       exit;
   mysql_query(``... $_GET['x'] ...'');
   

   Furthermore, interprocedural conditional sanitization (see the example in Section 3.1.6) is also fairly common in codebases.
   
   
3. WebSSARI uses an algorithm based on static types that does not specifically model dynamic features in scripts. For example, dynamic typing may introduce subtle errors that WebSSARI misses. The include statement, used extensively in PHP scripts, dynamically inserts code to the program which may contain, induce, or prevent errors.

5.2  Dynamic Techniques

6  Conclusion

Acknowledgement

References

[1]

A. Aiken, E. Wimmers, and T. Lakshman. Soft typing with conditional types. In Proceedings of the 21st Annual Symposium on Principles of Programming Languages, 1994.

[2]

K. Ashcraft and D. Engler. Using programmer-written compiler extensions to catch security holes. In 2002 IEEE Symposium on Security and Privacy, 2002.

[3]

A. Christensen, A. Moller, and M. Schwartzbach. Precise analysis of string expressions. In Proceedings of the 10th Static Analysis Symposium, 2003.

[4]

J. S. Foster, T. Terauchi, and A. Aiken. Flow-sensitive type qualifiers. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1–12, June 2002.

[5]

C. Gould, Z. Su, and P. Devanbu. Static checking of dynamically generated queries in database applications. In Proceedings of the 26th International Conference on Software Engineering, 2004.

[6]

S. Hallem, B. Chelf, Y. Xie, and D. Engler. A system and language for building system-specific, static analyses. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, Berlin, Germany, June 2002.

[7]

Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D. Lee, and S.-Y. Kuo. Securing web application code by static analysis and runtime protection. In Proceedings of the 13th International World Wide Web Conference, 2004.

[8]

X. Leroy, D. Doligez, J. Garrigue, and J. Vouillon. The Objective Caml system. Software and documentation available on the web, http://caml.inria.fr.

[9]

V. Livshits and M. Lam. Finding security vulnerabilities in Java applications with static analysis. In Proceedings of the 14th Usenix Security Symposium, 2005.

[10]

Y. Minamide. Approximation of dynamically generated web pages. In Proceedings of the 14th International World Wide Web Conference, 2005.

[11]

A. Nguyen-Tuong, S. Guarnieri, D. Greene, J. Shirley, and D. Evans. Automatically hardening web applications using precise tainting. In Proceedings of the 20th International Information Security Conference, 2005.

[12]

Perl documentation: Perlsec. http://search.
cpan.org/dist/perl/pod/perlsec.pod.

[13]

PHP: Hypertext Preprocessor. http://www.php.
net.

[14]

PHP usage statistics. http://www.php.net/
usage.php.

[15]

D. Scott and R. Sharp. Abstracting application-level web security. In Proceedings of the 11th International World Wide Web Conference, 2002.

[16]

Security space apache module survey (Oct 2005). http://www.securityspace.com/s_survey/
data/man.200510/apachemods.html.

[17]

Symantec Internet security threat report: Vol. VII. Technical report, Symantec Inc., Mar. 2005.

[18]

TIOBE programming community index for November 2005.
http://www.tiobe.com/tpci.htm.

[19]

J. Whaley and M. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, 2004.

[20]

A. Wright and R. Cartwright. A practical soft type system for Scheme. ACM Trans. Prog. Lang. Syst., 19(1):87–152, Jan. 1997.

[21]

J. Yang, T. Kremenek, Y. Xie, and D. Engler. MECA: an extensible, expressive system and language for statically checking security properties. In Proceedings of the 10th Conference on Computer and Communications Security, 2003.

1

Installed on over 23 million Internet domains [14], and is ranked fourth on the TIOBE programming community index [18].

2

Both vulnerabilities have been reported to and fixed by the PHP-fusion developers.

3

Sanitization is an operation that ensures that user input can be safely used in an SQL query (e.g., no unescaped quotes or spaces).

4

In general, in a dynamically typed language, a more precise static approximation in this case would be a sum (aka. soft typing) [1, 20]. We have not found it necessary to use type sums in this work.

5

So do function calls that exits the program, in which case we remove any ensuing statements and outgoing edges from the current CFG block. See Section 3.3.

6

Here we assume that a regular expression used to sanitize input in one context will have the same effect in another, which, based on our experience, is the common case. Our implementation now provides paranoid users with a special switch that ignores recorded answers and repeatedly ask the user the same question over and over if so desired.

7

For example, Utopia News Pro misused “[0-9]+” to validate some user input. This regular expression only checks that the string contains a number, instead of ensuring that the input is actually a number. The correct regular expression in this case is “^[0-9]+$”.

8

Information about the results, along with the source codebases, are available online at:
 http://glide.stanford.edu/yichen/research/.

9

Database configuration variables such as $db_prefix accounted for 3 false positives, and information derived from the database queries and configuration settings (e.g. locale settings) caused the remaining 12.

This document was translated from L^AT_EX by H^EV^EA.