Fault localization by analyzing failure propagation with samples in cloud computing environment

Software fault localization can help developers improve the reliability and safety of information systems, such as cloud computing systems, etc. So many approaches have been proposed. These approaches can be divided into program spectra-based, program slicing, state-based, model-based, program invariant based, mutation analysis, and machine learning-based approach [19‐23] etc. These methods have their own advantages and disadvantages [10, 11].

Among them, the program spectra-based method has been widely studied because of its low computational complexity and simple implementation. Program spectra-based methods locate suspicious code by comparing the program spectrum of failure execution and successful execution. Predefined measurement formulas are used to calculate the suspiciousness of each program element (e.g. statement), and the program elements are ranked according to the suspiciousness. The main difference of various program spectra-based methods is that the measurement formulas used are different. Some formulas are equivalent in terms of localization effectiveness [24‐26].

Empirical studies have been carried out to evaluate the effectiveness of fault localization tools [27‐33], especially the spectra-based methods. Although the conclusion are different from different researches because of different study subjects, some common observations can be got from these researches. To sum up, in order to be well-adopted by practitioners, the following future work of fault localization is needed.

Besides these observations, it is particularly important to note that except for the program slicing method, most of existing approaches perform fault localization by comparing the execution information of successful test cases and failure test cases [34, 35]. However, defective programs may fail for all the test cases in the given test suite. We call such programs “completely failed programs". In this case, these fault localization methods will not work. Therefore, it is necessary to study the scenarios without successful test cases in the given test suite.

It is difficult to obtain a complete formal specification of requirements for industrial software. Therefore, in software fault localization and repair, the execution information of test cases is usually used to assist the analysis. However, only using testing results as the criteria of automatic software repair may cause the overfitting problem. Even if a patched program passes all tests, it may still be incorrect [16, 17]. Therefore other information is needed to complement the test suite. Existing work has shown that example programs mining from open source software, can provide useful information for the generation of patches [18].

Yi et al. studied the performance of current popular industrial software repair tools, GenProg [36], AE [37], Prophet [38] and Angellix [39], in guiding students to debug programs [40]. All the four tools adopt a test-driven approach, that is, if the patch passes all test cases in the test suite, it is considered a successful fix. For example, GenProg first uses program spectra-based method to locate suspicious statements by comparing the statements of successful test cases with those of failed test cases, and assigns suspicious statements a higher probability of selection to be modified. Then genetic programming algorithm is used to transfer correct statements from other locations of the program to be repaired. After continuous evolution, patches that can pass all tests are searched. The results have shown that the repair rate of these tools is low. One reason is that student programs usually have multiple bugs, which require complex modifications, and often need to introduce new program logic when making modifications. However, the studied tools are difficult to repair missing statements and complex defects with dependencies. Another reason is that these tools use the program spectra-based fault localization method to identify potential modification locations. The program spectra-based method locates suspicious statements by comparing the successful execution and failure execution, while the students’ programs may fail for all the given test cases in the test suite. In this case, the spectra-based method can not be applied. The inaccuracy of fault localization results will directly reduce the effectiveness of program repair.

The enlightenment of the above researches to this paper is as follows.

(1) It is necessary to further study the fault localization method under the scenario of complex defects which lead to the failure of all the given test cases.

(2) In addition to test cases, sample programs can also be mined from a large number of correct programs to provide auxiliary information for fault localization.

This paper focuses on the sample based fault localization method.

The combination of dynamic execution value sequences analysis and static structural semantics analysis helps to identify the differences between the defective program and the sample program accurately and locate the suspicious statements in defective programs. The related definitions are as follows.

Definition (Variable pairs matched by value sequences): Given a test case set T, variable var_b at assignment statement s_b in program P_b, variable var_s at assignment statement s_s in program P_s, variable var_b and var_s are variable pairs matched by value sequences, and s_b and s_s are matched assignment statements, if and only if ValueSeq_s(T,s_b,var_b)≡ValueSeq_s(T,s_s,var_s), that is, var_b and var_s have the same execution value sequence.

Definition(Control dependence tree): program P’s control dependence tree, defined as T=(V,E), is a directed, ordered tree, where V is a set of nodes, representing statements and predicates in the program, E is a set of control dependency edges and procedure call edges [39]. The following attributes are satisfied.

(1) T is a directed tree. The control dependence edge from node u to node v represents the control dependence, and v control depends on u. This means that whether node v executes or not depends on the value of predicate in node u.

(2) T is an ordered tree. If node v and node u have the same parent node, they are called brothers. If v is the left brother of u, v precedes u in the execution.

(3) The node is a triple (id, type, exp), where id is the line number of the statement in the program, type is the statement type, exp is the abstract syntax tree of the expression.

(4) The procedure call edge represents the call relationship between functions, and connects the function call node and the entry node of the function being called.

Based on the control dependence tree to perform structural semantic analysis, the variable pairs matched by structural semantics are further identified.

Definition(Variable pairs matched by structural semantics): Given a test case set T, variable var_b at assignment statement s_b in program P_b, variable var_s at assignment statement s_s in program P_s, variable var_b and var_s are variable pairs matched by structural semantics, and s_b and s_s are matching assignment statements, if and only if in the control dependence tree of P_b and P_s, the syntax trees of s_b and s_s are completely matched, and both the control dependent paths of s_b and s_s have the same type of nodes.

Fault localization by analyzing the context of failure propagation is shown in Algorithm 1. The inputs include a defective program, the sample program, and a test case set. The goal is to identify the statements that are different between the defective program and the sample program as suspicious locations, return mutation operations that may be performed to repair defects, and map variables in the defective program and the sample program to assist program repair.

Lines 1 to 5, instrument and execute the defective program and the sample program with each test case, so as to collect the execution value sequence of each assignment variable.

Lines 6 to 9, map the equivalent variables and assignment statements in the defective program and the sample program by matching the execution value sequences.

Line 10, create the control dependence tree for the defective program and the sample program respectively.

Lines 11 to 15, and Lines 16 to 20, mark the equivalent assignment statements matched by the execution sequences in the two control dependence trees, respectively.

Line 21, The dynamic programming algorithm is used to find the maximum matching between two control dependence trees. On the one hand, the equivalent assignments and the variable pairs matched by structural semantics are identified to reduce the false positives of suspicious statements caused by failure propagation. The variable pairs are added to the variable mapping table. On the other hand, the different statements in the two programs are assigned higher suspiciousness, the mutation operations (insertion, deletion, replacement) that may repair the suspicious statements are identified and given higher mutation operation probability.

Finally, The variable mapping table, mutation operation probability, suspicious location and probability are output to assist understanding the causes of errors. Statement nodes with high probability are suspicious, and mutation operation with high probability is a more likely editing operation to repair the suspicious statement. The control dependence trees with the matching marks can also be output to assist the understanding of the failure context.

Figure 3 is an example of the structural semantic analysis of the programs in Fig. 1. By matching the subtrees of the program control dependence trees, the similar nodes and different nodes of the defect program C and the sample program A are identified, so as to localize the nodes that may contain defects, identify the possible mutation operations to repair the defects, and narrow the search scope.

Each node in the node sequence of the defect program and the sample program is given a weight, the mismatched node is given a higher probability (value is 0.8), and the matched node is given a lower probability (value is 0.2). The unmatched nodes in the defective program are regarded as suspicious statement. The unmatched nodes in the sample program are likely to be statement nodes that can be used to repair defects.

The research questions are as follows.

(1) RQ1: What is the effectiveness of the program clustering method? Ideally, programs with similar structure and semantics but possibly with code variations should be divided into the same cluster, and programs with different implementation logic or algorithms should be divided into different clusters.

(2) RQ2: What causes a program failed on all the test cases?

(3) RQ3: Can the proposed fault localization method effectively identify the differences between the defective programs and the sample program? Which factors affect the effectiveness of fault localization?

Yi et al. provided a benchmark, as shown in Table 1, when studying the performance of industrial software repair tools in debugging students’ programs [40].

These programs are actually written by students in the course of introductory programming. Each experiment has 4-8 programming tasks. The principle of Yi et al. in choosing programming tasks is to cover as many syntactic structures and algorithms as possible. The correct versions and the buggy versions are distinguished by comparing the actual and expected results. In the benchmark, each programming task provides a correct template program and multiple program pairs (Pb, Pc). Pb is a defective program version, which failed on one or more test cases. Pc is a modified version of Pb, which is obtained by the same person who modifies Pb. Pc can pass all test cases in the test suite. There are 661 defective programs in the data set, all of which contain logic errors and no syntactic errors.

There are two reasons for our experimenting on this benchmark. The first one is that it provides not only the buggy versions, but also the correct versions which helps in verify our sample based approach. The second one is that we want to test the capability of our method in deal with programs with complex bugs that cannot pass any test case, this benchmark provides such buggy versions.

To answer RQ1, the correct versions of each programming task were clustered to select template programs. Ideally, the programs in each cluster are structurally and semantically equivalent, and the programs in different clusters should adopt different implementation logic or algorithms. In order to improve the efficiency of code review, Gumtree [43] was used to generate syntax tree differences between two programs, and then these differences were manually examined to determine whether the two programs should belong to the same cluster.

Clustering result is related to distance threshold. The smaller the distance threshold is, the higher the similarity between programs in the same cluster will be, and the more clusters will be generated. It is expected that the programs in the same cluster should be as similar as possible to avoid filtering out too many template programs to provide sufficient template programs, so the distance threshold is set to 0.1.

The clustering effectiveness was evaluated by Purity and Entropy. Purity calculates the proportion of the correct clustered programs to the total number of programs. Entropy reflects the uncertainty of clustering results.

The average Purity is 0.95576, and the average Entropy is 0.15497. The clustering partition and the actual expectation partition are in good agreement. Therefore, the program clustering method is effective.

To answer RQ2, the benchmark provided by Yi et al. are further analyzed [40]. Among 661 defective programs, 206 defective programs failed to pass any test case in the test suite. Because there is not any successful test case information, these programs cannot analyzed by traditional fault localization methods, such as spectra-based method. This subsection focuses on the analysis of these programs, which are called “completely failed programs".

In the complete failed program set, 86 programs only contain one defect and 120 programs contain multiple defects. Figure 4 counts the number of program versions containing single defect and multiple defects in each programming task.

As shown in Table 2, the types of defects in completely failed programs are various. For example, an operator error, a logical expression error, or an output format error may cause the programs failed on the whole test case set, and the interaction of different kinds of defects may also lead to completely failure. In the completely failed program set, the single defective program mainly contains the following types of defects: input and output format, logical expression, arithmetic expression, variable initialization, variable assignment, array subscript, function parameter errors, etc. The defect types of multiple defect programs include not only the defect types in the single defective programs mentioned above, but also the large concepts missing, complex control structure errors, function invocation errors, statement order errors and so on. A program may also contain many types of defects. These defects interact with each other, resulting in the failure of the program on the entire test case set.

To answer RQ3, the effectiveness of fault localization on defective programs failed on all test cases in three cases was analyzed.

Case1: Provide sufficient sample programs. Using the original data in the benchmark, that is, there is a corrected version of P_c corresponding to each defective program P_b.

Case 2: Perform clustering to select sample program. A program is randomly selected from each cluster and added to the template set. In this case, for a defective program P_b, in the process of fault localization, the matching sample program may not be its initial corresponding version P_c, but semantically equivalent to the P_c, but there may be multiple correct versions such as expressions, variable names, statement order, etc.

Case 3: The sample program is inadequate. On the basis of Case2, the set of template programs is reduced. From the set of template programs generated by clustering algorithm, 1/2 and 1/3 number of template programs are randomly selected to form a new template set.

Table 3 counts the number of false positives of fault locations in three cases. It is considered that the defects in the program are correctly localized only when the location of defects is identified as suspicious. If a correct statement is identified as suspicious statement, it is considered as a false positive.

The following conclusions can be drawn from Table 3 and Fig. 5.