FAULT LOCALIZATION USING CONDITION MODELING AND RETURN VALUE MODELING

• US 20120054553A1
• Filed: 09/01/2010
• Published: 03/01/2012
• Est. Priority Date: 09/01/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ARTZI, Shay, Dolby, Julian, Pistoia, Marco, Tip, Frank
• Granted Patent: US 9,043,761 B2
• Time in Patent Office: Days
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 11/3692 for test results analysis

Abstract

Disclosed is a novel computer implemented system, on demand service, computer program product and a method that leverages combined concrete and symbolic execution and several fault-localization techniques to create a uniquely powerful tool that automatically detects failures and localizes faults in PHP Web applications. The fault-localization techniques evaluated combine variations on the Tarantula algorithm with a technique based on maintaining a mapping between executed statements and the fragments of output they produce, mapping of conditional results, and values returned from function calls. These techniques have been implemented in a tool called Apollo, and evaluated by localizing 75 randomly selected faults that were exposed by automatically generated tests in four PHP applications. Our findings indicate that, using our best technique, 87.7% of the faults under consideration are localized to within 1% of all executed statements, which constitutes an almost five-fold improvement over the Tarantula algorithm.

Claims

1. A computer-implemented method to localize faults in a software application, the computer-implemented method comprising:

receiving a set of tests to apply on at least a portion of a software application;

associating one or more domain elements with the portion of the software;

receiving a statistical fault localization technique that uses the set of tests to localize at least one fault in the domain elements;

executing each test in the set of tests on the portion of the software application, and recording, for each executed test, a set of test information including;

a test outcome on whether a specific fault has occurred,

one or more executed statements in the portion of the software application, and

an abstract value for each executed statement in the portion of the software application that indicates a domain element to which it corresponds; and

using the statistical fault localization technique which has been received, calculating a suspiciousness rating for each of the domain elements based on the set of test information which has been recorded.

2. The computer implemented method of claim 1, wherein the domain element is at least one of:

a pair comprising of a conditional statement and a value that identifies a branch of that conditional statement; and

an unconditional statement.

3. The computer implemented method of claim 1, wherein the domain element is at least one of:

a pair comprising of a call to a function, and an abstract representation of the return value of that function; and

a statement other than a function call.

4. The computer implemented method of claim 1, further comprising:

reporting a list containing a suspiciousness rating for each domain element.

5. The computer implemented method of claim 4, wherein the reporting the list containing a suspiciousness rating for each domain element is reported in a decreasing order of suspiciousness.

6. The computer implemented method of claim 1, wherein the executed statements in the portion of the software application includes one or more function calls and wherein the executing each test in the set of tests, and recording the set of test information further includes recording:

an abstract model of a result for each execution of the function calls.

7. The computer implemented method of claim 1, wherein the executed statements in the portion of the software application includes one or more of branches, statements, and functions.

8. The computer implemented method of claim 1, wherein the executing each test in set of tests, and recording the set of test information further includes recording one of:

a pass outcome;

a fail outcome; and

an exception outcome.

9. The computer implemented method of claim 1, wherein the conditional branch is one of:

a while statement;

an if statement, and

a switch statement.

10. A computer program product for analyzing an application comprising a plurality of code fragments, the computer program product comprising:

a storage medium readable by a computer system, the computer readable medium storing software programming instructions capable of performing with a processor programming code to carry out;

receiving a set of tests to apply on at least a portion of a software application;

associating one or more domain elements with the portion of the software;

receiving a statistical fault localization technique that uses the set of tests to localize at least one fault in the domain elements;

executing each test in the set of tests on the portion of the software application, and recording, for each executed test, a set of test information including;

a test outcome on whether a specific fault has occurred,

one or more executed statements in the portion of the software application, and

an abstract value for each executed statement in the portion of the software application that indicates a logical statement to which it corresponds; and

using the statistical fault localization technique which has been received, calculating a suspiciousness rating for each of the domain elements based on the set of test information which has been recorded.

11. The computer program product of claim 10, wherein the domain element is at least one of:

a pair comprising of a conditional statement and a value that identifies a branch of that conditional statement; and

an unconditional statement.

12. The computer program product of claim 10, wherein the domain element is at least one of:

a pair comprising of a call to a function, and an abstract representation of the return value of that function; and

a statement other than a function call.

13. The computer program product of claim 10, further comprising:

reporting a list containing a suspiciousness rating for each domain element.

14. The computer program product of claim 13, wherein the reporting the list containing a suspiciousness rating for each domain element is reported in a decreasing order of suspiciousness.

15. The computer program product of claim 10, wherein the executed statements in the portion of the software application includes one or more function calls and wherein the executing each test in the set of tests, and recording the set of test information further includes recording:

an abstract model of a result for each execution of the function calls.

16. The computer program product of claim 10, wherein the executed statements in the portion of the software application includes one or more of branches, statements, and functions.

17. The computer program product of claim 10, wherein the executing each test in set of tests, and recording the set of test information further includes recording one of:

a pass outcome;

a fail outcome; and

an exception outcome.

18. The computer program product of claim 10, wherein the conditional branch is one of:

a while statement;

an if statement, and

a switch statement.

19. A system for analyzing an application comprising a plurality of code fragments, the system comprising:

a computer memory capable of storing machine instructions; and

a processor in communication with said computer memory, said processor capable of accessing said machine instructions to perform;

receiving a set of tests to apply on at least a portion of a software application;

associating one or more domain elements with the portion of the software;

receiving a statistical fault localization technique that uses the set of tests to localize at least one fault in the domain elements;

executing each test in the set of tests on the portion of the software application, and recording, for each executed test, a set of test information including;

a test outcome on whether a specific fault has occurred,

one or more executed statements in the portion of the software application, and

an abstract value for each executed statement in the portion of the software application that indicates a logical statement to which it corresponds; and

using the statistical fault localization technique which has been received, calculating a suspiciousness rating for each of the domain elements based on the set of test information which has been recorded.

20. The system of claim 19, wherein the domain element is at least one of:

a pair comprising of a conditional statement and a value that identifies a branch of that conditional statement; and

an unconditional statement.