AUTOMATED TEST INPUT GENERATION FOR WEB APPLICATIONS

• US 20090125976A1
• Filed: 10/10/2008
• Published: 05/14/2009
• Est. Priority Date: 11/08/2007
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: DOCOMO Communications Laboratories USA, Inc.
• Inventors: Wassermann, Gary, Inamura, Hiroshi, Chander, Ajay, Dhurjati, Dinakar, Yu, Dachuan
• Granted Patent: US 8,302,080 B2
• Time in Patent Office: Days
• US Class Current: 726/1
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06

Abstract

A method and apparatus is disclosed herein for automated test input generation for web applications. In one embodiment, the method comprises performing a source-to-source transformation of the program; performing interpretation on the program based on a set of test input values; symbolically executing the program; recording a symbolic constraint for each of one or more conditional expressions encountered during execution of the program, including analyzing a string operation in the program to identify one or more possible execution paths, and generating symbolic inputs representing values of variables in each of the conditional expressions as a numeric expression and a string constraint including generating constraints on string values by modeling string operations using finite state transducers (FSTs) and supplying values from the program'"'"'s execution in place of intractable sub-expressions; and generating new inputs to drive the program during a subsequent iteration based on results of solving the recorded string constraints.

Claims

1. A method for generating test inputs for testing a program, the method comprising:

performing a source-to-source transformation of the program;

performing interpretation on the program based on a set of test input values;

symbolically executing the program;

recording a symbolic constraint for each of one or more conditional expressions encountered during execution of the program, including

analyzing a string operation in the program to identify one or more possible execution paths, and

generating symbolic inputs representing values of variables in each of the conditional expressions as a numeric expression and a string constraint including generating constraints on string values by modeling string operations using finite state transducers (FSTs) and supplying values from the program'"'"'s execution in place of intractable sub-expressions; and

generating new inputs to drive the program during a subsequent iteration based on results of solving the recorded string constraints.

2. The method defined in claim 1 wherein the test inputs are dynamically generated input strings based on symbolic string constraints and concrete values gathered from executions of the program.

3. The method defined in claim 2 wherein the input strings are test cases for applications that cover string- and array-centric operations.

4. The method defined in claim 1 wherein the test cases achieve a designated code-coverage metric.

5. The method defined in claim 4 wherein the code-coverage metric is one of a group consisting of:

branch coverage and bounded path coverage.

6. The method defined in claim 1 wherein recording a symbolic constraint for each conditional expression encountered during execution of the program comprises, for each variable occurrence in a Boolean control expression, creating a copy of the expression and setting all other variable occurrences in the expression to their concrete values from the execution, thereby generating a set of expressions where each expression in the set has only a single variable occurrence and each subexpression that does not depend on that variable is replaced with its concrete values.

7. The method defined in claim 6 wherein generating, based on analysis of the recorded constraints, new inputs to drive the program during a subsequent iteration comprises selecting from an expression from the list to invert and discarding expressions following the expression in the list.

8. The method defined in claim 1 wherein generating symbolic inputs comprises generating a string constraint on one variable in an expression by solving the expression against a constraint.

9. The method defined in claim 1 further comprising replacing one symbolic expression by a concrete value when the one symbolic expression becomes non-linear.

10. The method defined in claim 1 wherein the FSTs represent library string functions and further comprising analyzing string operations in the program using the FSTs.

11. The method defined in claim 1 further comprising using the FSTs for solving the constraints for input variables by inverting the FSTs.

12. The method defined in claim 1 wherein modeling string operations using FSTs comprises approximating expressions in the program by considering only one variable occurrence per expression at a time.

13. The method defined in claim 1 further comprising:

identifying a point of possible failure in the program; and

computing approximately a backward slice from the point of failure, and wherein constraints are only recorded from the backward slice.

14. The method defined in claim 13 wherein the points include a point where an API function is called to send a query to a database.

15. The method defined in claim 14 further comprising adding all functions in which these points occur to a set of functions to be analyzed.

16. The method defined in claim 15 wherein adding all functions comprises:

resolving control dependencies by recording a stack trace at a beginning of a function call; and

adding functions that called the function to the set of functions to be analyzed.

17. The method defined in claim 16 wherein resolving control dependencies comprises examining symbolic values and determining where branches terminate a function call, and further wherein adding those functions to the set of functions

18. The method defined in claim 1 further comprising checking string values against one or more existing policies to prevent SQL injection attacks.

19. The method defined in claim 18 wherein at least one security policy classifies, as tainted, any SQL query in which characters in tokens are non-literals, and the method includes flagging an error if such a query is identified.

20. The method defined in claim 18 wherein at least one security policy classifies, as tainted, strings in an output document of a web application that invoke a JavaScript interpreter of a client, and the method includes flagging an error if such a string is identified.

21. The method defined in claim 1 wherein recording a constraint results in selective recording of constraints for scaling beyond single functions.

22. The method defined in claim 1 wherein the program is written in a scripting language.

23. The method defined in claim 22 wherein the scripting language is part of a web application.

24. The method defined in claim 22 wherein the scripting language is PHP.

25. An article of manufacture having one or more computer readable storage media storing instructions therein which, when executed by a system, causes the system to perform a method comprising:

performing a source-to-source transformation of the program;

performing interpretation on the program based on a set of test input values;

symbolically executing the program;

recording a symbolic constraint for each of one or more conditional expressions encountered during execution of the program, including

analyzing a string operation in the program to identify one or more possible execution paths, and

generating symbolic inputs representing values of variables in each of the conditional expressions as a numeric expression and a string constraint including generating constraints on string values by modeling string operations using finite state transducers (FSTs) and supplying values from the program'"'"'s execution in place of intractable sub-expressions; and

generating new inputs to drive the program during a subsequent iteration based on results of solving the recorded string constraints.

26. A method comprising:

receiving a web application; and

applying concolic testing to the web application using string constraints and a decision procedure for the string constraints.

27. The method defined in claim 26 further comprising checking string values against one or more policies to prevent SQL injection attacks and cross-site scripting.

28. An article of manufacture having one or more computer readable storage media storing instructions therein which, when executed by a system, causes the system to perform a method comprising:

receiving a web application; and

applying concolic testing to the web application using string constraints and a decision procedure for the string constraints.