Loading patent…
AssigneeNtt Docomo, Inc.
InventorsGary Wassermann, Dachuan Yu, Ajay Chander, Dinakar Dhurjati, Hiroshi Inamura
Estimating the term…
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.
A method for generating test inputs for applying concolic testing in a program, the method comprising:
A method for generating test inputs for applying concolic testing in a program, the method comprising:
A non-transitory computer readable storage medium having instructions stored thereon which, when executed by a system, causes the system to perform a method for generating test inputs for applying concolic testing in a program;
A method comprising:
A non-transitory computer readable storage medium having instructions stored thereon which, when executed by a system, causes the system to perform a method comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Test management: for test execution, e.g. scheduling of test suites
Arrangements for software engineering
Computing and data processing
About 4 years 9 months of term left · ends 1 Aug 2031 (estimated)
The present invention relates to the field of analysis of computer programs; more particularly, the present invention is related to generating test inputs based on symbolic constraints and concrete values gathered from executions of the program.
Web applications continue to offer more features, handle more sensitive data, and generate content dynamically based on more sources as users increasingly rely on them for daily activities. The increased role of web applications in important domains, coupled with their interactions not only with other web applications but also with users' local systems exacerbates the effects of bugs and raises the need for correctness.
Testing is a widely used approach for identifying bugs and for providing concrete inputs and traces that developers use for fixing bugs. However, manual testing requires extensive human effort, which comes at significant cost. Additionally, quality assurance (QA) testing usually attempts to ensure that the software can do everything it ought to do, but it does not check whether the software can do things it ought not to do; such functionality usually constitutes security holes.
The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of various embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments, but are for explanation and understanding only.
FIG. 1 illustrates one embodiment of a FST composition algorithm.
FIG. 2 illustrates exemplary FSA image construction.
Methods and apparatuses for generating input strings based on symbolic constraints and concrete values gathered from program executions are disclosed. In one embodiment, test cases for applications are automatically generated that cover string- and array-centric operations and achieve a designated code-coverage metric: branch coverage or (bounded) path coverage. In one embodiment, library string functions are represented as finite state transducers (FSTs), and constraints on strings include equality and inclusion constraints. These FSTs can be composed and inverted to solve for input variables. When constraints cannot be represented precisely using finite state transducers concrete values can be used to construct approximations that are finite state transducers. In one embodiment, as part of the test input generation process, a process is used to check string values against existing policies to prevent SQL injection attacks and cross-site scripting. In one embodiment, the test input generation process is fully automated, does not require an interface specification, handles string operations, detects injection vulnerabilities, and generates test inputs for scripting languages, which may utilize general meta-programming.
In the following description, numerous details are set forth to provide a more thorough explanation of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.
Some portions of the detailed descriptions which follow are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.