Automatic_Creation_of_SQL_Injection_and_Cross-Site

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/38003076 Automatic Creation of SQL Injection and Cross-Site Scripting Attacks Article  in  Proceedings - International Conference on Software Engineering · January 2009 DOI: 10.1109/ICSE.2009.5070521 · Source: OAI CITATIONS READS 218 594 4 authors, including: Karthick Jayaraman Syracuse University Adam Kiezun 17 PUBLICATIONS   424 CITATIONS    Broad Institute of MIT and Harvard 107 PUBLICATIONS   13,869 CITATIONS    SEE PROFILE SEE PROFILE All content following this page was uploaded by Adam Kiezun on 20 May 2014. The user has requested enhancement of the downloaded file.

Computer Science and Artificial Intelligence Laboratory Technical Report MIT-CSAIL-TR-2008-054 September 10, 2008 Automatic Creation of SQL Injection and Cross-Site Scripting Attacks Adam Kiezun, Philip J. Guo, Karthick Jayaraman, and Michael D. Ernst massachusetts institute of technology, cambridge, ma 02139 usa — www.csail.mit.edu

Automatic Creation of SQL Injection and Cross-Site Scripting Attacks Adam Kiez˙un Philip J. Guo Karthick Jayaraman Michael D. Ernst MIT Stanford University Syracuse University MIT [email protected] [email protected] [email protected] [email protected] Abstract code on the victim’s machine by exploiting inadequate val- idation of data flowing to statements that output HTML. In We present a technique for finding security vulnerabili- 2008, SQLI comprised 27% of Web-application vulnerabil- ties in Web applications. SQL Injection (SQLI) and cross- ities (up from 18% in 2007), and XSS comprised 24% (up site scripting (XSS) attacks are widespread forms of attack from 21%) [2]. in which the attacker crafts the input to the application to access or modify user data and execute malicious code. In Previous approaches to identifying SQLI and XSS vul- the most serious attacks (called second-order, or persistent, nerabilities and preventing exploits include defensive cod- XSS), an attacker can corrupt a database so as to cause ing, static analysis, dynamic monitoring, and test genera- subsequent users to execute malicious code. tion. Each of these approaches has its own merits, but also offers opportunities for improvement. Defensive coding [3] This paper presents an automatic technique for creating is error-prone and requires rewriting existing software to inputs that expose SQLI and XSS vulnerabilities. The tech- use safe libraries. Static analysis tools [12, 16, 29] can pro- nique generates sample inputs, symbolically tracks taints duce false warnings and do not create concrete examples of through execution (including through database accesses), inputs that exploit the vulnerabilities. Dynamic monitoring and mutates the inputs to produce concrete exploits. Ours tools [8,24,26] incur runtime overhead on the running appli- is the first analysis of which we are aware that precisely cation. Black-box test generation does not take advantage addresses second-order XSS attacks. of the application’s internals [27], while previous white-box techniques have not been shown to discover unknown vul- Our technique creates real attack vectors, has few false nerabilities [30]. positives, incurs no runtime overhead for the deployed ap- plication, works without requiring modification of appli- We have created a new technique for identifying SQLI cation code, and handles dynamic programming-language and XSS vulnerabilities. Unlike previous approaches, our constructs. We implemented the technique for PHP, in a tool technique works on unmodified existing code, creates con- A. We evaluated A on five PHP applications crete inputs that expose vulnerabilities, has no overhead for and found 68 previously unknown vulnerabilities (23 SQLI, the released software, and analyzes application internals to 33 first-order XSS, and 12 second-order XSS). discover vulnerable code. As an implementation of our technique, we created A, an automated tool for cre- 1 Introduction ating SQLI and XSS attacks in PHP/MySQL applications. In our experiments, A discovered 68 previously un- This paper presents a technique and an automated tool known vulnerabilities in five applications. for finding security vulnerabilities in Web applications. Multi-user Web applications are responsible for handling A is based on input generation, taint propagation, much of the business on today’s Internet. Such applica- and input mutation to find variants of an execution that ex- tions often manage sensitive data for many users, and that ploit a vulnerability. We now discuss these components. makes them attractive targets for attackers: up to 70% of recently reported vulnerabilities affected Web applica- A can use any input generator. Our current im- tions [2]. Therefore, security and privacy are of great im- plementation uses combined concrete and symbolic execu- portance for Web applications. tion [1,6,25,30]. During each execution, the input generator monitors the program to record path constraints that capture Two classes of attacks are particularly common and dam- the outcome of control-flow predicates. The input generator aging. In SQL injection (SQLI), the attacker executes ma- automatically and iteratively generates new inputs by negat- licious database statements by exploiting inadequate vali- ing one of the observed constraints and solving the modi- dation of data flowing from the user to the database. In fied constraint system. Each newly-created input explores cross-site scripting (XSS), the attacker executes malicious at least one additional control-flow path. A’s vulnerability detection is based on dynamic taint analysis [8, 29]. A marks data coming from the 1

user as potentially unsafe (tainted), tracks the flow of tainted SQL Injection. A SQLI vulnerability results from the ap- data in the application, and checks whether tainted data can plication’s use of user input in constructing database state- reach sensitive sinks. An example of a sensitive sink is the ments. The attacker invokes the application, passing as an PHP mysql query function, which executes a string argu- input a (partial) SQL statement, which the application exe- ment as a MySQL statement. If a string derived from tainted cutes. This permits the attacker to get unauthorized access data is passed into this function, then an attacker can poten- to, or to damage, the data stored in a database. To prevent tially perform an SQL injection, if the tainted string affects this attack, applications need to sanitize input values that the structure of the SQL query as opposed to just being used are used in constructing SQL statements, or else reject po- as data within the query. Similarly, passing tainted data into tentially dangerous inputs. functions that output HTML can lead to XSS attacks. First-order XSS. A first-order XSS (also known as Type 1, A’s taint propagation is unique in that it tracks the or reflected, XSS) vulnerability results from the application flow of tainted data through the database. When tainted inserting part of the user’s input in the next HTML page data is stored in the database, the taint information is stored that it renders. The attacker uses social engineering to con- with it. When the data is later retrieved from the database, vince a victim to click on a (disguised) URL that contains it is marked with the stored taint. Thus, only data that malicious HTML/JavaScript code. The user’s browser then was tainted upon storing is tainted upon retrieval. This displays HTML and executes JavaScript that was part of the precision makes A able to accurately detect second- attacker-crafted malicious URL. This can result in stealing order (persistent) XSS attacks. By contrast, previous tech- of browser cookies and other sensitive user data. To prevent niques either treat all data retrieved from the database as first-order XSS attacks, users need to check link anchors tainted [28, 29] (which may lead to false warnings) or treat before clicking on them, and applications need to reject or all such data as untainted [16] (which may lead to missing modify input values that may contain script code. real vulnerabilities). Second-order XSS. A second-order XSS (also known as Not every flow of tainted data to a sensitive sink indicates persistent, stored, or Type 2 XSS) vulnerability results from a vulnerability because the data may flow through routines the application storing (part of) the attacker’s input in a that check or sanitize it. To improve usability, A does database, and then later inserting it in an HTML page that is not require the user to provide a list of sanitizing routines. displayed to multiple victim users (e.g., in an online bulletin Instead, A systematically mutates inputs that propa- board application). It is harder to prevent second-order XSS gate taints to sensitive sinks, using a library of strings that than first-order XSS, because applications need to reject or can induce SQLI and XSS attacks. A then analyzes sanitize input values that may contain script code and are the difference between the parse trees of application out- displayed in HTML output, and need to use different tech- puts (SQL and HTML) to determine whether the attack may niques to reject or sanitize input values that may contain subvert the behavior of a database or a Web browser, respec- SQL code and are used in database commands. tively. This step enables A to reduce the number of false warnings and to precisely identify real vulnerabilities. Second-order XSS is much more damaging than first- order XSS, for two reasons: (a) social engineering is not This paper makes the following contributions: required (the attacker can directly supply the malicious in- put without tricking users into clicking on a URL), and (b) • A fully-automatic technique for creating SQLI and a single malicious script planted once into a database exe- XSS attack vectors, including those for second-order cutes on the browsers of many victim users. (persistent) XSS attacks. (Section 3) 2.1 Example PHP/MySQL Application • A novel technique that determines whether a propa- gated taint is a vulnerability, using input mutation and PHP is a server-side scripting language widely used in output comparison. (Section 4.3) creating Web applications. The program in Figure 1 imple- ments a simple message board that allows users to read and • A novel approach to symbolically tracking the flow of post messages, which are stored in a MySQL database. To tainted data through a database. (Section 4.4) use the message board, users of the program fill an HTML form (not shown here) that communicates the inputs to the • An implementation of the technique for PHP in a tool server via a specially formatted URL, e.g., A (Section 4), and evaluation of A on real PHP applications (Section 5). http://www.mysite.com/?mode=display&topicid=1 2 SQL Injection and Cross-Site Scripting Input parameters passed inside the URL are available in the $ GET associative array. In this example URL, the input This section describes SQLI and XSS Web-application has two key-value pairs: mode=display and topicid=1. vulnerabilities and illustrates attacks that exploit them. 2

1 // exit if parameter ’mode’ is not provided 1’ OR ’1’=’1 2 if(!isset($_GET[’mode’])){ 3 exit; This string leads to an attack because the query that the pro- 4} gram submits to the database in line 40, 5 SELECT msg FROM messages WHERE topicid=’1’ OR ’1’=’1’ 6 if($_GET[’mode’] == \"add\") contains a tautology in the WHERE clause and will retrieve 7 addMessageForTopic(); all messages, possibly leaking private information. 8 else if($_GET[’mode’] == \"display\") 9 displayAllMessagesForTopic(); To exploit the vulnerability, the attacker must create an 10 else attack vector, i.e., the full set of inputs that make the pro- 11 exit; gram follow the exact path to the vulnerable mysql query call and execute the attack query. In our example, the attack 12 vector must contain at least parameters mode and topicid set to appropriate values. For example: 13 function addMessageForTopic(){ 14 if(!isset($_GET[’msg’]) || mode → display 15 !isset($_GET[’topicid’]) || topicid → 1’ OR ’1’=’1 16 !isset($_GET[’poster’])){ 17 exit; First-order XSS attack. This attack exploits the lack of 18 } validation of the input parameter poster. After storing a message, the program displays a confirmation note (line 29) 19 using the local variable my poster, whose value is derived directly from the input parameter poster. Here is an attack 20 $my_msg = $_GET[’msg’]; vector that, when executed, opens a popup window on the 21 $my_topicid = $_GET[’topicid’]; user’s computer: 22 $my_poster = $_GET[’poster’]; mode → add 23 topicid → 1 msg → Hello 24 //construct SQL statement poster → Villain<script>alert(\"XSS\")</script> 25 $sqlstmt = \"INSERT INTO messages VALUES(’$my_msg’,’$my_topicid’)\"; This particular popup is innocuous; however, it demon- 26 strates the attacker’s ability to execute script code in the vic- tim’s browser (with access to the victim’s session data and 27 //store message in database permissions). A real attack might, for example, send the 28 $result = mysql_query($sqlstmt); victim’s browser credentials to the attacker. 29 echo \"Thank you $my_poster for using the message board\"; 30 } Second-order XSS attack. This attack exploits the lack of SQL validation of parameter msg when storing messages 31 in the database (line 25) and the lack of HTML validation when displaying messages (line 44). The attacker can use 32 function displayAllMessagesForTopic(){ the following attack vector to store the malicious script in 33 if(!isset($_GET[’topicid’])){ the application’s database. 34 exit; 35 } 36 37 $my_topicid = $_GET[’topicid’]; 38 39 $sqlstmt = \"SELECT msg FROM messages WHERE topicid=’$my_topicid’\"; 40 $result = mysql_query($sqlstmt); 41 42 //display all messages 43 while($row = mysql_fetch_assoc($result)){ 44 echo \"Message \" . $row[’msg’]; 45 } 46 } Figure 1: Example PHP program that implements a sim- ple message board using a MySQL database. This program is vulnerable to SQL injection and cross-site scripting at- tacks. Section 2.1 discuses the vulnerabilities. (For sim- plicity, the figure omits code that establishes a connection with the database.) This program can operate in two modes: posting a mes- mode → add sage or displaying all messages for a given topic. When topicid → 1 posting a message, the program constructs and submits the msg → Hello<script>alert(\"XSS\")</script> SQL statement to store the message in the database (lines 25 poster → Villain and 28) and then displays a confirmation message (line 29). In the displaying mode, the program retrieves and displays Now every user whose browser displays messages in topic 1 messages for the given topic (lines 39, 40, and 44). gets an unwanted popup. For example, executing the fol- lowing innocuous input results in an attack: This program is vulnerable to the following attacks, all of which our technique can automatically generate: mode → display topicid → 1 SQL injection attack. Both database queries, in lines 28 and 40, are vulnerable but we discuss only the latter, which 3 Technique exploits the lack of input validation for topicid. Our attack-creation technique generates a set of concrete Consider the following string passed as the value for in- inputs, executes the program under test with each input, put parameter topicid: and dynamically observes whether data flows from an input to a sensitive sink (e.g., a function such as mysql query 3

Database MySQL parameters: program P, database state db state result : SQLI or first-order XSS attack vectors Input Ardilla 1 attacks ∅; PHP Generator 2 while not timeExpired() do Program Concrete+Symbolic 3 input generateNewInput(P); inputs Database 4 taints, db exec&PropagateTaints(P, input, db); 5 attacks attacks ∪ gen&CheckAttacks(taints, P, input); Executor/Taint Attack 6 return attacks; Propagator vectors Figure 3: Algorithm for creating SQLI and first-order XSS taint sets attacks. Section 3.2 describes the algorithm. Attack • The Concrete+Symbolic Database is a relational Generator/Checker database engine that can execute SQL statements both concretely and symbolically. Our technique uses this Figure 2: The architecture of A. The inputs to component to track the flow of tainted data through A are the PHP program and its associated MySQL the database, which is critical for accurate detection of database. The output is a set of attack vectors for the pro- second-order XSS attacks. gram, each of which is a complete input that exposes a se- curity vulnerability. 3.2 First-order Attacks or echo), including any data-flows that pass through a Figure 3 shows the algorithm for generating SQLI and database. If an input reaches a sensitive sink, our technique first-order XSS attacks (both called first-order because they modifies the input by using a library of attack patterns, in do not involve tracking taint through the database). The an attempt to pass malicious data through the program. algorithm for creating SQLI and first-order XSS attacks are identical except for the sensitive sinks (mysql query for This section first shows the four components of our tech- SQLI, echo and print for XSS) and certain details in the nique (Section 3.1) and then describes the algorithms for au- attack generator/checker. tomatically generating first-order (Section 3.2) and second- order (Section 3.3) attacks. The algorithm takes the program P under test and its as- sociated database db populated with the proper tables and 3.1 Technique Components initial data (usually done via an installation script or taken from an existing installation). Until a time limit expires, the Figure 2 shows the architecture of our technique and of algorithm generates new concrete inputs (line 3), runs the the A tool that we created as an implementation of the program on each input and collects taint sets (line 4), and technique for PHP. Here, we briefly describe its four com- then creates attack vectors (line 5). ponents as an aid in understanding the algorithms. Section 4 describes A and the four components in detail. Example. Here is how our technique generates the first- order XSS attack presented in Section 2.1: • The Input Generator creates a set of inputs for the program under test, aiming to cover many control-flow First, new inputs are successively generated and the pro- paths. gram executes on each input (and propagates taints) until some input allows the program to reach line 29 in the code • The Executor/Taint Propagator runs the program on in Figure 1, which contains the sensitive sink echo. An ex- each input produced by the input generator and tracks ample of such an input I is: which parts (parameters) of the input flow into sensi- tive sinks. For each sensitive sink, the executor outputs mode → add a set of input parameters whose values flow into the topicid → 1 sink (called a taint set). msg → 1 poster → 1 • The Attack Generator/Checker takes a list of taint sets (one for each sensitive sink), creates candidate at- (Even though only the value of mode determines whether tacks by modifying the inputs in the taint sets using a execution reaches line 29, all parameters are required to be library of SQLI and XSS attack patterns, and runs the set; otherwise the program rejects the input in line 17. Our program on the candidate attacks to determine (check) input generator picks 1 as the default “don’t care” value.) which are real attacks. Second, the executor/taint propagator runs the program on I and creates taint sets for sensitive sinks. In the example, the executor marks all input parameters as tainted and de- termines that the value of the parameter poster flows into 4

parameters: program P, database state db rithm maintains a set of inputs generated so far (in the inputs result : second-order XSS attack vectors variable), from which, in each iteration, the algorithm picks 1 inputs ∅; two inputs (lines 6 and 7). Then, the algorithm executes 2 attacks ∅; the two inputs in sequence (lines 8 and 9) using the con- 3 dbsym makeSymbolicCopy(db); crete+symbolic database. The first execution (simulating 4 while not timeExpired() do the attacker) sets the state of the database (dbsym) that the 5 inputs inputs ∪ generateNewInput(P); second execution (simulating the victim) uses. Finally, the 6 input1 pickInput(inputs); attack generator/checker (line 10) creates second-order XSS 7 input2 pickInput(inputs); attack scenarios (i.e., input pairs). 8 taints1, dbsym exec&PropagateTaints(P, input1, dbsym); 9 taints2, dbsym exec&PropagateTaints(P, input2, dbsym); To favor execution paths that lead to second-order XSS 10 attacks attacks ∪ gen&CheckAttacks(taints2, P, input1, input2 ); attacks, on line 6 our implementation picks an input that 11 return attacks; executes a database write, and on line 7 picks an input that executes a database read on the same table. Figure 4: Algorithm for creating second-order XSS attacks. Section 3.3 describes the algorithm. Example. Here is how our technique generates the second- order XSS attack introduced in Section 2.1: the local variable my poster, which flows into the sensitive sink echo in line 29: First, the input generator creates inputs and picks the fol- lowing pair I1: $my poster = $ GET[’poster’]; ... mode → add echo \"Thank you $my poster for using the message board\"; topicid → 1 msg → 1 Thus, the taint set of this echo call contains (only) the input poster → 1 parameter poster. and I2: Third, the attack generator mutates the input I by replac- ing the value of all parameters in the taint set (here only mode → display poster) with XSS attack patterns. An example pattern is topicid → 1 <script>alert(\"XSS\")</script>. Picking this pattern alters input I into I : Second, the executor/taint propagator runs the program on I1, using the concrete+symbolic database. During this mode → add execution, the program stores the value 1 of the input pa- topicid → 1 rameter msg (together with the taint set that contains the msg → 1 parameter msg itself) in the database (line 25 of Figure 1). poster → <script>alert(\"XSS\")</script> Third, the executor/taint propagator runs the program Fourth, the attack checker runs the program on I and on I2, using the concrete+symbolic database. During determines that I is a real attack. this execution, the program retrieves the value 1 from the database (together with the value’s stored taint set that con- Finally, the algorithm outputs I as an attack vector for tains msg) and outputs the value via the echo in line 44. the first-order XSS vulnerability in line 29 of Figure 1. echo is a sensitive sink, and its taint set contains the pa- rameter msg from I1. Thus, the algorithm has dynamically 3.3 Second-order Attacks tracked the taint from msg to the local variable my msg (line 20), into the database (line 28), back out of the Figure 4 shows the algorithm for generating second- database (line 40), into the $row array (line 43), and finally order XSS attacks, which differs from the first-order algo- as a parameter to echo (line 44), across two executions. rithm by using a concrete+symbolic database and by run- ning the program on two inputs during each iteration. The Fourth, the attack generator uses the library of attack pat- first input represents one provided by an attacker, which terns to alter msg in I1 to create an attack candidate input I1: contains malicious values. The second input represents one provided by a victim, which does not contain malicious val- mode → add ues. The algorithm tracks the flow of data from the at- topicid → 1 tacker’s input, through the database, and to a sensitive sink msg → <script>alert(\"XSS\")</script> in the execution on the victim’s innocuous input. poster → 1 The algorithm takes the program P under test and a Fifth, the attack checker runs the program, in sequence, database db. In the first step (line 3), the algorithm makes on I1 and I2 (note that I2 remains unchanged), and deter- a symbolic copy of the concrete database, creating a con- mines that this sequence of inputs is an attack scenario. crete+symbolic database. Then, until a time limit expires, the algorithm generates new concrete inputs and attempts Finally, the algorithm outputs the pair I1, I2 as a to create attack vectors by modifying the inputs. The algo- second-order XSS attack scenario that exploits the vulnera- bility in line 44 of Figure 1. 5

4 The A Tool 1. Taint sources give rise to tainted data during execution of the PHP program under test. Taint sources are inputs As an implementation of our technique, we created (e.g., $ GET and $ POST). A assigns a unique taint to A, an automated tool that generates concrete attack each value read from an input parameter, identified by the vectors for Web applications written in PHP. The user of value’s origin. For example, A assigns taint msg to a A needs to specify the type of attack (SQLI, first- value retrieved from $ GET[’msg’]. order XSS, or second-order XSS), the PHP program to an- alyze, and the initial database state. The outputs of A 2. Taint sets describe how each runtime value is influ- are attack vectors. This section describes A’s imple- enced by taint sources, and can contain any number of el- mentation of each component of the technique described in ements. For example, taint set {msg, poster} may corre- Section 3. spond to a runtime value derived from input parameters msg and poster (e.g., via string concatenation). 4.1 Dynamic Input Generator 3. Taint propagation specifies how runtime values ac- The dynamic input generator creates inputs for the PHP quire and lose taint. A propagates taint sets un- program under test. Inputs for PHP Web applications are changed across assignments and procedure calls in appli- Web server requests: their parameters are mappings from cation code. At a call to a built-in PHP function (e.g., chop, keys (strings) to values (strings and integers) in associative which removes trailing whitespace from a string) that is arrays such as $ GET[] and $ POST[]. not a taint filter (see next component), A constructs a taint set for the return value that is a union of taint sets A uses the input-generation component from for function argument values. A also constructs taint Apollo [1], but A could potentially use any generator sets for string values created from concatenation by taking for PHP applications such as the one described by Wasser- a union of taint sets for component strings. At a call to a mann et al. [30]. The input generator is based on dynamic database function (e.g., mysql query), A stores or test-input generation that combines concrete and symbolic retrieves taint for the data values. (Section 4.4 describes the execution [6, 25]. Here, we briefly describe this technique, interaction of taint propagation with the database.) which A uses as a black box. 4. Taint filters are built-in PHP functions that are For each program input (starting with an arbitrary known to sanitize inputs (i.e., modify the inputs to make well-formed concrete input, and then using subsequently- them harmless for XSS or SQLI attacks). For example, generated ones), the input generator executes the program htmlentities converts characters to HTML entities (e.g., concretely and also collects symbolic constraints for each < to &lt;) and makes the output safe from XSS attacks. runtime value. These constraints describe an input that fol- At a call to a taint filter function, A creates an empty lows a given control-flow path through the program. Negat- taint set for the return value. Users of A can option- ing the symbolic constraint at a branch-point (e.g., an if ally specify a list of taint filters. statement) and discarding subsequent constraints gives a set of constraints for a different path through the program. The 5. Sensitive taint sinks are built-in PHP functions that are input generator then attempts to solve those constraints to exploitable in XSS and SQLI attacks: for example, echo create a concrete input that executes the new path. The and print for XSS and mysql query for SQLI. When input generator repeats this process for each branch-point reaching a call to a sensitive sink, A records the taint in an execution, possibly generating many new inputs from sets of the argument, indicating a data-flow from the inputs each executed one. to the sink, and thus a possibility of an attack. 4.2 Executor and Taint Propagator A’s Executor and Taint Propagator is implemented by modifying the Zend PHP interpreter1 (previously used The Executor and Taint Propagator runs the program in Apollo [1] for finding faulty HTML output) to perform under test on each input and tracks the dynamic data- regular program execution and to simultaneously propagate flow of input parameters throughout the execution. For taints from inputs to other runtime values. each sensitive sink, the executor outputs the set of in- put parameters (taint set) whose values flow into the sink. 4.3 Attack Generator and Checker A’s taint propagation is unique in that it can track the flow of tainted data through the database, by using a The attack generator creates candidate attack vectors that concrete+symbolic database (Section 4.4). Dynamic taint are variants of the given input. The attack checker deter- propagation in A can be characterized by the follow- mines whether a candidate can be used as an attack, by com- ing five components. paring its execution to that of the original input. 1 http://www.zend.com 6

4.3.1 Attack Generator msg topicid msg s topicid s The attack generator starts with an input for which there Test message 1 ∅ ∅ is dataflow from a parameter to a sensitive sink. For each parameter whose value flows into the sink (member of the Hello 2 {msg} {topicid} taint set), the generator creates new inputs that differ only for that parameter. The generator replaces the value of that Figure 5: Example state of the concrete+symbolic database parameter by a value taken from an attack pattern library— table messages used by the PHP program of Figure 1. Each a set of values that may result in an attack if supplied to a concrete column (left-most two columns) has a symbolic vulnerable input parameter. counterpart (right-most two columns) that contains taint sets. The ∅ values represent empty taint sets. A uses attack patterns developed by security pro- fessionals. A’s SQLI attack pattern library contains 6 by control-flow (taint sets only reflect data-flow) and cannot patterns distilled from several lists2,3 A’s XSS attack capture input filtering. pattern library4 contains 113 XSS attack patterns, includ- ing many filter-evading patterns (that use various character The SQLI attack checker compares database state- encodings, or that avoid specific strings in patterns). ments (e.g., SELECT, INSERT) issued by the PHP program executed separately on the two inputs. The checker com- 4.3.2 Attack Checker pares the first pair of corresponding statements, then the second, etc., The checker signals an attack if the statements In SQLI and XSS attacks, the PHP program interacts with in any pair are both valid SQL but have different syntactic another component (a database or a Web browser) in a way structure (i.e., parse tree). the programmer did not intend. The essence of an SQLI attack is a change in the structure of the SQL statement The XSS attack checker signals an attack if the HTML that preserves its syntactic validity (otherwise, the database page produced from the execution of a candidate attack in- rejects the statement and the attack attempt is unsuccess- put (or sequence of inputs, for second-order attacks) con- ful) [26]. The essence of an XSS attack is the introduction tains additional script-inducing constructs. of additional script-inducing constructs (e.g., <script> tags) into a dynamically-generated HTML page [29]. 4.4 Concrete+Symbolic Database A detects attacks by looking for differences in the The concrete+symbolic database stores both concrete way the program behaves when run on two inputs: one in- and symbolic values for each data record. In a PHP Web nocuous and the other potentially malicious. We assume application, the database is a shared state that enables the that the input generator creates innocuous (non-attack) in- exchange of data between users. The concrete+symbolic puts, since the input parameters’ values are simple constants database tracks the flow of user-provided data between dif- such as 1 or literals from the program text. Therefore, the ferent runs of the PHP program and is critical in creating innocuous input represents how the program is intended to second-order XSS attacks. interact with a component (database or browser). The attack generator creates the potentially malicious input. The concrete+symbolic database is implemented as a duplicate of the concrete database, with each table having The checker runs the program on the two inputs and additional columns that store symbolic data. A uses compares the executions. Running the program on the at- these columns to store taint sets, but it is also possible to tack candidate input avoids two potential sources of false store symbolic expressions there. warnings: (i) input sanitizing—the program may sanitize (i.e., modify to make harmless) the input before passing it Figure 5 shows an example database state during the exe- into a sensitive sink. A does not require the user to cution of the program in Figure 1. Assume the database was specify a list of sanitizing routines. (ii) input filtering—the pre-populated with a test message in topic 1, so the taint sets program may reject inputs that satisfy a malicious-input pat- for fields in the first row are empty. When the user posts a tern (blacklisting), or else fail to satisfy an innocuous-input message Hello in topic 2 (line 28), the taint sets from the pattern (whitelisting). However, the taint sets are unaffected respective input parameters are stored along with their con- crete values in the second row. Later, when the user fetches 2 http://www.justinshattuck.com/2007/01/18/ data from that row (line 43), the taint sets are also fetched mysql- injection- cheat- sheet, and propagated to the assigned variables. http://ferruh.mavituna.com/sql- injection- cheatsheet- oku, http://pentestmonkey.net/blog/mysql- sql- injection- cheat- sheet A dynamically rewrites each SQL statement in the PHP program to account for the new columns—either up- 3A’s list omits attacks that transform one query into multiple dating or reading taint sets, as appropriate. Our current queries, because the PHP mysql query function only allows one query implementation handles a subset of SQL, rewriting their to be executed per call. strings before passing them into mysql query: CREATE TABLE, INSERT, UPDATE, and (non-nested) SELECT. (Note 4 http://ha.ckers.org/xss.html 7

that the DELETE statement and WHERE condition do not need and managing documents, 1712 LOC), EVE 1.0 (player ac- to be rewritten—MySQL can locate the relevant rows using tivity tracker for an online game, 915 LOC), and geccbblite the concrete values.) 0.1 (a simple bulletin board, 326 LOC). We used the latest • CREATE TABLE creates a new table. A rewrites the available versions as of 5 September 2008. statement to add a duplicate for each column (e.g., the two right-most columns in Figure 5) to use for storing taint sets. We performed the following procedure for each subject • INSERT adds new rows to tables. A rewrites the program. First, we ran the program’s installation script statement to store taint sets in the duplicate columns. For to create the necessary database tables. Second, we pre- example, consider the following PHP string representing an populated the database with representative data (e.g., de- SQL statement (PHP automatically performs the string con- faults where available). Third, we ran A with a 30- catenation): minute time limit in each of three modes: SQLI, first-order XSS, and second-order XSS. The time limit includes all INSERT INTO messages VALUES(’$ GET[’msg’]’,’$ GET[’topicid’]’) experimental tasks, i.e., input generation, program execu- tion and taint propagation, and attack generation and attack A dynamically rewrites the statement as follows: checking. When necessary, we provided the input generator with (non-administrator) username and password combina- INSERT INTO messages VALUES(’Hello’,’2’, ’{msg}’,’{topicid}’) tions. Doing so poses no methodological problems because an attacker can use a legitimate account to launch an attack. on an execution in which parameters msg and topicid have Fourth, we manually examined attack vectors reported by concrete values Hello and 2 and have one-element taint A to determine if they reveal true security vulnera- sets that contain only the parameters themselves. bilities. We did not know any SQLI or XSS vulnerabilities • UPDATE modifies values in tables. For example, for: in the subject programs before performing the experiments. (Thanks to previous studies [28, 29], we were aware of the UPDATE messages SET msg=’$ GET[’msg’]’ presence of first-order XSS and SQLI vulnerabilities in gec- WHERE topicid=’$ GET[’topicid’]’ cbblite and EVE.) A’s dynamic rewriting for UPDATE is similar to that We ran A in two modes for checking validity of for INSERT (the WHERE condition is unchanged): XSS attacks: lenient and strict. (The SQLI checker has only one mode.) In the lenient mode, the XSS checker reports a UPDATE messages SET msg=’Hi’, msg s=’{msg}’ WHERE topicid=’3’ vulnerability when the outputs differ in script-inducing ele- ments or HTML elements like href. In the strict mode, the • SELECT finds and returns table cells. A rewrites XSS checker only reports a vulnerability when the outputs the statement to include the duplicate (symbolic) column differ in script-inducing elements. names in the selection. Thereafter, A uses the value retrieved from the duplicate column as the taint set for the 5.1 Measurements concrete value retrieved from the original column. For ex- ample, consider the concrete statement executed in line 39 Number of sensitive sinks (all) is the statically computed of the program in Figure 1 (given the example state of the number of echo/print (for XSS) or mysql query state- concrete+symbolic database in Figure 5). ments (for SQLI), whose parameter is not a constant string. Number of reached sinks (reach) on all generated inputs is SELECT msg FROM messages WHERE topicid = ’2’ an indication of coverage achieved by the input generator. This measure is suitable for A, because A looks A rewrites the statement to: for attacks on sensitive sinks. Number of tainted sinks (taint) is the number of sensitive SELECT msg, msg s FROM messages WHERE topicid = ’2’ sinks reached with non-empty taint sets during execution. Each such occurrence potentially exposes a vulnerability, The result of executing this rewritten statement on the ta- which A uses the attack generator and checker to test. ble in Figure 5 is a 1-row table with concrete string Hello Number of verified vulnerabilities (Vuln): We count at and associated taint set {msg}, in columns msg and msg s. most one vulnerability per sensitive sink, since a single-line A augments functions such as mysql fetch assoc code-fix would eliminate all attacks on the sink. If a sin- to assign concrete values to the proper variables (e.g., row gle attack vector attacks multiple sensitive sinks, then we in line 43) and to simultaneously propagate their taint sets. examine and count each vulnerability separately. Number of false positives (F): We manually inspected each 5 Evaluation A report and determined whether it really constituted an attack (i.e., corruption or unintended disclosure of data We evaluated A on five open-source programs for SQL, and unintended HTML structure for XSS). For downloaded from http://sourceforge.net: school- mate 1.5.4 (tool for school administration, 8181 lines of code, or LOC), webchess 0.9.0 (online chess game, 4722 LOC), faqforge 1.3.2 (tool for creating 8

sensitive sinks lenient strict Example created SQLI attack. In webchess, A found a vulnerability in mainmenu.php that allows an at- program mode all reach taint Vuln F Vuln F tacker to retrieve information about all players without en- schoolmate tering a password. The application constructs the vulnera- webchess SQLI 218 28 23 60 60 ble statement directly from user input: faqforge XSS1 14 6 10 0 EVE XSS2 122 26 20 40 20 \"SELECT * FROM players WHERE nick = ’\" . $ POST[’txtNick’] . \"’ geccbblite SQLI 12 0 12 0 AND password = ’\" . $ POST[’pwdPassword’] . \"’\" Total XSS1 122 4 4 13 18 13 0 XSS2 00 00 The attack vector contains the following two crucial pa- SQLI 93 42 40 10 10 rameters (others omitted for brevity) XSS1 40 40 XSS2 76 39 39 00 00 ToDo → NewUser SQLI 20 20 txtNick → foo’ or 1=1 -- XSS1 76 40 0 20 20 XSS2 30 20 which causes execution to construct the following malicious SQLI 33 7 1 20 20 SQL statement which bypasses authentication (-- starts an XSS1 00 00 SQL comment): XSS2 35 10 4 50 40 SELECT * FROM players WHERE nick = ’foo’ or 1=1 SQLI 35 0 0 23 0 23 0 -- ’ AND password = ’’ XSS1 33 24 29 0 XSS2 12 6 6 12 0 80 Comparison to previous studies. Two of our subject pro- grams were previously analyzed for vulnerabilities. In gec- 24 5 4 cbblite, a previous study [29] found 1 first-order XSS vul- nerabilities, and 7 second-order XSS vulnerabilities (possi- 24 5 3 bly including false positives). However, our manual exam- ination of geccbblite found no first-order XSS vulnerabili- 10 8 6 ties. In EVE, another study [28] found 4 SQLI vulnerabili- ties. The result data from neither study are available so we 17 17 11 cannot directly compare the findings. 17 17 5 Comparison to black-box fuzzing. We compared A’s ability to find first-order XSS attacks to that of 366 91 76 a black-box fuzzer for finding XSS attacks: Burp Intruder5 (listed in the 10 most popular Web-vulnerability scanners6). 274 97 78 We configured the fuzzer according to its documentation. The fuzzer requires manual setting up of HTTP request pat- 274 66 12 terns to send to the Web application (and requires manual indication of variables to mutate). We ran the fuzzer using Figure 6: Results of running A to create SQLI, XSS1 the same attack pattern library that A uses, and on the (first-order XSS), and XSS2 (second-order XSS) attacks. same subject programs. (We have not been able to success- The lenient and strict columns refer to A modes (Sec- fully configure webchess to run with the fuzzer.) We ran the tion 5). Section 5.1 describes the remaining columns (Vuln fuzzer until completion (up to 8 hours). The fuzzer found 1 columns in bold list the discovered real vulnerabilities). first-order XSS vulnerability in schoolmate, 3 first-order in faqforge, 0 in EVE, and 0 in geccbblite. We examined all second-order XSS, we checked that the attacker’s malicious vulnerabilities reported by the fuzzer and determined that input can result in an unintended Web page for the victim. they were a subset of those discovered by A. 5.2 Results Limitations. A can only generate attacks for a sensi- tive sink if the input generator creates an input that reaches A found 23 SQLI, 33 first-order XSS, and 12 the sink. However, effective input generation for PHP is second-order XSS vulnerabilities in the subject programs challenging [1,19,30], complicated by its dynamic language (see Figure 6). The attacks that A found, as well as features and execution model (running a PHP program of- the attack patterns we used, are available at http://pag. ten generates an HTML page with forms and links that re- csail.mit.edu/ardilla. quire user interaction to execute code in additional files). In particular, the generator that A uses can create inputs We examined two of the three instances in which A found no vulnerabilities. In geccbblite, we man- 5 http://portswigger.net/intruder ually determined that there are no first-order XSS vulner- 6 http://sectools.org/web- scanners.html abilities. In faqforge, we manually determined that each database write requires administrator access, so there are no second-order XSS vulnerabilities. (We did not manually inspect webchess for second-order XSS attacks, due to the program’s size and our unfamiliarity with the code.) We examined all 23 SQLI reports issued by A and found no false positives. All attacks involved disrupting the SQL WHERE clause. In 4 cases, attacks result in data corrup- tion (by disrupting UPDATE); in 19 cases, attacks result in information leaking (by disrupting SELECT), sometimes as serious as bypassing login authentication. We examined all 86 unique XSS reports issued by A and classified them as true vulnerabilities or false positives. We found 24 false positives in the lenient mode for first-order XSS (42% false-positive rate), and 0% per- cent false-positive rate for all other cases: strict first-order XSS, lenient and strict second-order XSS. 9

only for one PHP script at a time and cannot simulate ses- dynamic monitoring. QED [18] combines static analysis sions (i.e., user–application interactions that involve multi- and model checking to automatically create SQLI and first- ple pages), which is a serious hindrance to achieving high order XSS attacks on Java applications. In contrast to our coverage in Web applications; line coverage averaged less technique, QED does not target second-order XSS, and re- than 50%. In fact, only on one application (webchess) did quires the user to describe attacks in a specialized specifica- the input generator run until the full 30-minute time-limit— tion language. This makes QED more general but less easy in all other cases, the generator finished within 2 minutes to use. Our system is fully automatic and does not require because it could not manage to cover more code. We also users to learn a specification language. attempted to run the generator on a larger application, the phpBB Web-forum creator (35 KLOC), but it achieved even Black-box scanners (see ranking at http://sectools. lower coverage (14%). A uses the input generator as a org) attempt to exploit security flaws by unguided (black- black box and any improvement in input generation is likely box) generation of inputs from a library of known at- to improve A’s effectiveness. tacks. McAllister et al. [19] present a scanner that uses pre-recorded user-interactions and fuzzing. In contrast, our 6 Related Work technique is white-box—it uses the information about the application code to observe the actual flow of user-provided We divide previous approaches to dealing with input- data through the application and the database. based Web application attacks into defensive coding, static prevention, dynamic monitoring, and hybrid approaches. Our technique uses a test-input generator that is based on combined concrete and symbolic execution [6, 25]. This Defensive coding techniques rely on specially-developed approach, previously shown to be effective in desktop ap- libraries to create safe SQL queries [3, 20], requiring pro- plications, has recently been applied to PHP [1, 30]. grammers to rewrite code to use the new libraries. An ad- vantage of defensive coding is that, in principle, it can pre- The Apollo tool that we have previously developed [1] vent all SQLI and XSS vulnerabilities. A disadvantage is generates test inputs for PHP, checks the execution for that it requires rewriting existing code. In contrast, while crashes and validates the output’s conformance to HTML our technique cannot find all vulnerabilities, it requires no standards. The goal of A is entirely different: to change to the programming language or the application. find security vulnerabilities. In A, we used the test- input generator subcomponent of Apollo as a black box. Static approaches can, in principle, prove the absence A’s taint propagation implementation is also partially of vulnerabilities [7, 12, 16, 28, 31]. In practice, however, based on that of Apollo, but is enhanced significantly by analysis imprecision causes false warnings. Additionally, adding support for propagation across function calls, taint static techniques do not create concrete attack vectors. In filters, taint sinks, and taint tracing across database calls. contrast, our technique does not introduce such imprecision and creates attack vectors. Dynamic taint propagation has been applied in the con- text of dynamic monitoring [22–24] and for increasing cov- Dynamic monitoring for SQLI attacks works by tracking erage of test suites [15]. In contrast, we apply dynamic of user-provided values [4, 8, 23, 24, 26] during operation tainting to create attacks for Web applications. of a deployed application. Advantages are that the analy- sis needs no approximations (the actual concrete inputs are Emmi et al.’s test-input generation technique [5] models available) and that it can, in principle, prevent all attacks. a database using symbolic constraints and provides a spe- The main disadvantage is the performance penalty. In con- cialized solver to create concrete database states that make trast, our approach does not incur any performance penalty the application that interacts with the database exercise var- on the deployed application. Developers and testers can ap- ious execution paths. Our work differs in objective (finding ply our technique to find and remove vulnerabilities before security vulnerabilities vs. improving code coverage) and in the application reaches users. the targeted language (PHP vs. Java). Mitigation techniques for XSS vulnerabilities are related Wassermann et al.’s tool [30] executes a PHP applica- to dynamic monitoring for SQLI attacks and can prevent tion on a concrete input and collects symbolic constraints. leakage of information [13]. Browser-Enforced Embedded Upon reaching a SQL-related statement, the tool attempts Policies combines client- and server-side techniques [11]. to create an input that will expose a SQL injection vulner- Madou et al.’s server-side mitigation [17] learns allowed ability, by using a string analysis [21]. The authors show HTML patterns during training and enforces them during that their tool can re-discover 3 previously known vulner- deployment. In contrast to mitigation, our technique is for abilities. The most important differences between Wasser- creating attack vectors and is applicable before deployment. mann’s work and ours are: (i) Their tool has not discov- ered any previously unknown vulnerabilities, and requires Static and dynamic approaches can be combined [9, 10]. a precise indication of an attack point. In contrast, our Lam et al. [14] combine static analysis, model checking and tool has discovered 68 previously unknown vulnerabilities and requires no manual indication of vulnerable points. (ii) 10

Their technique focuses only on SQLI, while ours targets [12] N. Jovanovic, C. Kruegel, and E. Kirda. Pixy: A static anal- both SQLI and XSS. (iii) Their tool performs automated ysis tool for detecting Web application vulnerabilities (short source-code instrumentation and backward-slice computa- paper). In S&P, 2006. tion by re-executing and instrumenting additional code. In contrast, our tool works on unchanged application code. (iv) [13] E. Kirda, C. Kruegel, G. Vigna, and N. Jovanovic. Noxes: Their tool requires manual loading of pages and supplying a client-side solution for mitigating cross-site scripting at- of inputs to the page, while our tool is fully automatic. tacks. In SAC, 2006. 7 Conclusion [14] M. Lam, M. Martin, B. Livshits, and J. Whaley. Securing Web applications with static and dynamic information flow We have presented a technique for creating SQL injec- tracking. In PEPM, 2008. tion and cross-site scripting (XSS) attacks in Web appli- cations and an automated tool, A, that implements [15] T. R. Leek, G. Z. Baker, R. E. Brown, M. A. Zhivich, and the technique for PHP. Our technique is based on input R. P. Lippmann. Coverage maximization using dynamic generation, dynamic taint propagation, and input mutation taint tracing. Technical Report 1112, MIT Lincoln Lab, to find a variant of the input that exposes a vulnerability. March 2007. Using a novel concrete+symbolic database to store taint, A can effectively and accurately find the most dam- [16] B. Livshits and M. Lam. Finding security vulnerabilities in aging type of input-based Web application attack: stored Java applications with static analysis. In USENIX Security, (second-order) XSS. A novel attack checker that compares 2005. the output from running on an innocuous input and on a candidate attack vector allows A to detect vulnerabil- [17] M. Madou, E. Lee, J. West, and B. Chess. Watch what you ities with high accuracy. In our experiments, A found write: Preventing cross-site scripting by observing program 68 attack vectors in five programs, each exposing a different output. In OWASP, 2008. vulnerability, with few false positives. [18] M. Martin and M. Lam. Automatic generation of XSS and References SQL injection attacks with goal-directed model checking. In USENIX Security, 2008. [1] S. Artzi, A. Kiez˙un, J. Dolby, F. Tip, D. Dig, A. Paradkar, and M. Ernst. Finding bugs in dynamic Web applications. [19] S. McAllister, E. Kirda, and C. Kru¨gel. Leveraging user in- In ISSTA, 2008. teractions for in-depth testing of Web applications. In RAID, 2008. [2] Cenzic. Application security trends report Q1 2008. http://www.cenzic.com. [20] R. McClure and I. Kru¨ger. SQL DOM: compile time check- ing of dynamic SQL statements. In ICSE, 2005. [3] W. Cook and S. Rai. Safe query objects: statically typed objects as remotely executable queries. In ICSE, 2005. [21] Y. Minamide. Static approximation of dynamically gener- ated Web pages. In WWW, 2005. [4] M. Cova, D. Balzarotti, V. Felmetsger, and G. Vigna. Swad- dler: An approach for the anomaly-based detection of state [22] J. Newsome and D. Song. Dynamic taint analysis for au- violations in Web applications. In RAID, 2007. tomatic detection, analysis, and signature generation of ex- ploits on commodity software. In NDSS, 2005. [5] M. Emmi, R. Majumdar, and K. Sen. Dynamic test input generation for database applications. In ISSTA, 2007. [23] A. Nguyen-Tuong, S. Guarnieri, D. Greene, J. Shirley, and D. Evans. Automatically hardening Web applications using [6] P. Godefroid, N. Klarlund, and K. Sen. DART: Directed precise tainting. In IFIP Security, 2005. automated random testing. In PLDI, 2005. [24] T. Pietraszek and C. V. Berghe. Defending against injection [7] C. Gould, Z. Su, and P. Devanbu. Static checking of dynam- attacks through context-sensitive string evaluation. In RAID, ically generated queries in database applications. In ICSE, 2005. 2004. [25] K. Sen, D. Marinov, and G. Agha. CUTE: A concolic unit [8] W. Halfond, A. Orso, and P. Manolios. WASP: Protecting testing engine for C. In FSE, 2005. Web applications using positive tainting and syntax-aware evaluation. IEEE TSE, 34(1):65, 2008. [26] Z. Su and G. Wassermann. The essence of command injec- tion attacks in Web applications. In POPL, 2006. [9] W. G. Halfond and A. Orso. AMNESIA: Analysis and Mon- itoring for NEutralizing SQL-Injection Attacks. In ASE, [27] M. Sutton, A. Greene, and P. Amini. Fuzzing: Brute Force 2005. Vulnerability Discovery. Addison-Wesley, 2007. [10] Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D.-T. Lee, and S.- [28] G. Wassermann and Z. Su. Sound and precise analysis of Y. Kuo. Securing Web application code by static analysis Web applications for injection vulnerabilities. In PLDI, and runtime protection. In WWW, 2004. 2007. [11] T. Jim, N. Swamy, and M. Hicks. Defeating script injection [29] G. Wassermann and Z. Su. Static detection of cross-site attacks with browser-enforced embedded policies. In WWW, scripting vulnerabilities. In ICSE, 2008. 2007. [30] G. Wassermann, D. Yu, A. Chander, D. Dhurjati, H. Ina- mura, and Z. Su. Dynamic test input generation for Web applications. In ISSTA, 2008. [31] Y. Xie and A. Aiken. Static detection of security vulnerabil- ities in scripting languages. In USENIX-SS, 2006. 11

View publication stats