Automatically predicting faults that caused software failures using a Markov logic network

Patent metadata

Field	Value
Publication number	US-10296443-B2
Application number	US-201615286824-A
Country	US
Kind code	B2
Filing date	Oct 6, 2016
Priority date	Oct 9, 2015
Publication date	May 21, 2019
Grant date	May 21, 2019

Abstract

A system and methods for automatically localizing faults for functional field failures that enables users to enter symptoms of a failure that occur during deployment of a given application along with the values of the input and configuration parameters in order to return locations in the source code that are likely to contain specific faults as well as show navigation paths from a suggested to the failure such that the code may be corrected. Successful and faulty runs of a software application are executed, and used to obtain ground facts and a knowledge base. A particular formula for the ground facts and knowledge base is discussed. A Markov Logic Network (MLN) is generated from the ground facts and knowledge base. Abductive reasoning based on the MLN is used to localize faults for the user-entered functional field failures.

First claim

The invention claimed is:

1. A method for localizing faults of a field failure, comprising the steps of:
a. Executing a software under test application to obtain successful runs, the software under test application comprising a configuration file, wherein the configuration file specifies one or more selected from the group of: a main class of the software under test application, a main method of the software under test application, a range of values of input parameters and configuration options, and one or more output variables;
b. Introducing one or more faults to the software under test application to obtain faulty runs, wherein each faulty run includes a failed output;
c. Performing differential diagnosis on the successful runs and the faulty runs to obtain ground facts and a knowledge base using a formula I(x,0,10) M(s,t) →O(y,−) for the range of values of the input parameters x∈[0 . . . 10] for an output variable y, and the one or more introduced faults M of type t, into a statement s, a value of the output variable y changes to a negative;
d. Generating a Markov Logic Network (MLN) from the ground facts and the knowledge base, wherein the MLN is generated using one or more predicates and/or logic formulae selected from the group:
(1) an infection fault rule: if the one or more introduce faults M is injected into the statement s and a state of a mutated software under test application after executing the statement s differs from a state of the original software under test application, then the state of the original software under test application is infected at the statement s;
(2) a propagation rule: if the statement s is infected and an other statement s 2 controls, then the other statement s 2 is infected;
(3) an output failure rule: if the statement s is infected and an executed software under test application reaches the output o that is dataflow dependent on the statement s, then the output o failed with a symptom p that depends on the output o;
(4) a control flow change rule: if the statement s is infected and the output o is dataflow dependent on the statement s and a branch condition is modified so that the value of the output o is not computed, then the output o fails; and
(5) a transitive infection rule: if the output o is a failure and it serves as an input parameter to the other statement s 2 , then the other statement s 2 is infected;

e. Deploying a software application, wherein the deployed software application includes one or more field failures;
f. Performing abductive reasoning on both the MLN and symptoms of the one or more field failures to obtain ranked hypotheses predicting a localization of one or more faults of each field failure in the deployed software application; and
g. Generating a graphical user interface on which the ranked hypotheses are displayed.

2. The method according to claim 1 further comprising the step of determining whether the software under test application and the configuration file specify a main class, a main methods of the software under test application, ranges of the values for the software's input parameters, configuration options, or the output variables.

3. The method according to claim 1 further comprising the step of producing a modifiable software application from the software under test application and the configuration file.

4. The method according to claim 3 further comprising the step of determining whether the modifiable software application is a copy of the software under test application.

5. The method according to claim 3 further comprising the step of reconfiguring the modifiable software application to make it a copy of the software under test application.

6. The method according to claim 3 further comprising the step of running the software under test application in parallel with the modifiable software application.

7. The method according to claim 6 further comprising the step of collecting diagnostic information from the running step.

8. The method according to claim 7 further comprising the step of determining whether there was a faulty run.

9. The method according to claim 3 further comprising the step of injecting faults and inputs into the modifiable software application.

10. The method according to claim 1 , wherein the introducing step further comprises introducing one or more additional faults.

11. The method according to claim 1 further comprising the step of identifying the faults that do not result in failure.

12. The method according to claim 1 , wherein the abductive reasoning is represented as a formula O(y,−)→I(x,0,10) M(s,t).

13. A system useful in identifying and locating faults for failures, the system comprising a processor in communication with:
a. a sensitivity analyze instructed to introduce one or more faults in a software under test application;
b. a modifiable software under test application comprising the one or more faults introduced to the software under test application resulting in successful runs and faulty runs, wherein each faulty run includes a failed output;
c. a Markov Logic Network (MLN) generator comprising ground facts and a knowledge base using a formula I(x,0,10) M(s,t) →O(y,−) for a range of values of input parameters x∈[0 . . . 10] for an output variable y, and the one or more introduced faults M of type t, into a statement s, a value of the output variable y changes to a negative,
the MLN generator instructed to generate a Markov Logic Network (MLN) from the ground facts and the knowledge base, wherein the MLN further comprises one or more predicates and/or logic formulae selected from the group:
(1) an infection fault rule: if the one or more introduced faults M is injected into the statement s and a mutated application after executing the statement s differs from a state of the original software under test application, then the state of the original software under test application is infected at the statement s;
(2) a propagation rule: if the statement s is infected and an other statement s 2 controls, then the other statement s 2 is infected;
(3) an output failure rule: if the statement s is infected and an executed software under test application reaches the output o that is dataflow dependent on the statement s, then the output o failed with a symptom p that depends on the output o;
(4) a control flow change rule: if the statement s is infected and the output o is dataflow dependent on the statement s and a branch condition is modified so that the value of the output o is not computed, then the output o has failed; and
(5) a transitive infection rule: if the output o is a failure and it serves as an input parameter to the other statement s 2 , then the other statement s 2 is infected;

d. a deployed software application including one or more field failures;
e. an abductive reasoner instructed to perform abductive reasoning on both the MLN and symptoms of the one or more field failures to obtain one or more ranked hypotheses, each directed to a prediction of a localization of one or more faults for each field failure in the deployed software application; and
f. a display by which the one or more faults is illustrated.

14. The system from claim 13 , wherein the system further comprises a differential diagnoser instructed to introduce additional faults into the software under test application for testing the one or more ranked hypotheses.

15. the system from claim 14 , wherein the system further comprises a test script and input data selector instructed to inject the additional faults into the software under test application.

16. the system from

Assignees

• Univ Illinois

Inventors

• Grechanik Mark

Classifications

• G06F11/366 Primary

  using diagnostics (G06F11/0703 takes precedence) · CPC title

• G06F11/3688

  for test execution, e.g. scheduling of test suites · CPC title

• G06N5/025

  Extracting rules from data · CPC title

• G06F8/71

  Version control (security arrangements therefor G06F21/57); Configuration management · CPC title

• G06N5/041

  Abduction · CPC title