An Integrated Framework for Fault Resolution in Business Processes

Illustrative Example:

Fig. 1 shows a small BP graph representing an elementary BP from the e-commerce domain. Shaded gray boxes represent activities corresponding to invocation of web service operations e.g., searchProduct, verifyEmail, etc. White rectangular boxes represent the input and output attributes of the service operations e.g., productId, taxClassId, etc. Control flow edges in the BP are denoted by solid arrows. Arrows with dotted lines denote dataflow edges that link each service operation with its input/output attributes. Arrows with dashed lines model the variable assignment which is essentially a dataflow from the output of one service operation to the input of another service operation (e.g., the edge from productId to product_code where productId is produced by searchProduct and it is assigned to product_code, which represents an input attribute of the createOrder service operation).

BP Fault Resolution Problem:

Given a faulty BP, G_f, and a set of test cases, T = {t₁, …, t_m}, compute a minimal set of candidate fixes, 𝒞 = {G_c1, G_c2, …, G_ck}, that when applied to G_f produces a BP that successfully passes all the test cases in T.

Note that we do not address the test case generation problem for BPs in this paper. We assume that the test cases are either provided by the user or existing test case generation techniques [17]–[21] can be applied for this purpose as discussed in Section VI.

A. Efficient G&V approach (EGV) for fault resolution

Fig. 2 shows the main steps of the proposed EGV approach. EGV takes as input a faulty BP graph (G_f) and a set of test cases and attempts to resolve faults in G_f. There are four key steps which are executed repeatedly until all faults are resolved (as per the execution on the test suite). First, the test cases are executed to check the correctness of the given BP, G_f. If it results in an unexpected/incorrect output, fault localization is performed (discussed in Section III-A1) to identify location(s) where faults are observed in the BP. These locations are referred to as fault observation points (fop), which may not necessarily correspond to the actual source of the fault in the BP. The source of the actual fault might b present at a location prior to fop.

Specifically, we perform statistical fault localization [22] to identify fop. For a given fop, we perform program slicing [23] to obtain suspicious code blocks. These suspicious code blocks are referred to as BP slices. We use the BP slices that lie between the starting vertex ($v_f^{\mathit{\text{start}}}$) of G_f and the given fop for generating candidate fixes. Fault localization and BP slicing help us to keep the generated number of candidate fixes to a minimum but still relevant. Once the BP slices are identified, we apply the different mutation operators and their combinations to obtain mutants of G_f which are called candidate fixes. Then, for the given fop, we run the test cases against each candidate fix to check if the faults are resolved without introducing any new faults. For executing test cases, first, the BP code is generated and deployed. If a candidate fix removes all the faults then our approach terminates and returns the candidate fix that passes all the test cases. In case the faults up to the given fop are fixed, but execution of test cases results in faults at a later point in the BP, we repeat the entire process to identify subsequent fop and candidate fixes. This process is repeated in an iterative manner until all the faults are resolved or all the candidate fixes are exhausted.

Algorithm 1 outlines the steps required to fix a faulty BP. Lines 1 and 2 find the fop and BP slice respectively using statistical fault localization and BP slicing as discussed in Sections III-A1 and III-A2. Next the relevant BP slices between the starting vertex ($v_f^{\mathit{\text{start}}}$) of G_f and the fop is extracted for generating candidate fixes (Lines 3 – 13). Candidate fixes are generated by successively applying mutation operators and their combinations on the input BP G_f. Each candidate fix, G_c is validated to check if it passes the failed test cases up to the computed fop (Line 17). If any such G_c is found, it is tested against all the test cases for the entire BP (Line 18). If it passes all these test cases, then all the faults with respect to the given test cases have been removed. The resulting BP is returned to the user (Line 19). Otherwise, we recursively call the EGV fault resolution procedure (Line 21) until all the faults are fixed or the entire space of mutants is exhausted.

We provide detailed description of each component of Fig. 2 below.

B. Hybrid Approach

The EGV approach for fault localization examines a BP in isolation therefore it lacks the capability to identify any control flow and branching faults that occur due to any activity/element removal in the BP e.g., a missing service operation or a branch path in an XOR block. CFR is a collaborative fault resolution (CFR) approach [5] that is capable of resolving such faults.

CFR relies on a set of existing BPs that are composed of similar services and are assumed to be correct. The knowledge of these BPs is utilized to discover and fix fault in a faulty BP. However CFR requires a certain minimum overlapping services between the faulty BP and existing BPs for providing accurate results. Rather than examining the faulty BP in isolation (as EGV does), we propose a hybrid of EGV and CFR approaches that allows for broader coverage of fault types by leveraging knowledge from existing BPs.

Hybrid approach combines both EGV and CFR in an interleaved fashion. We consider two versions of the hybrid approach:

• H1:

  EGV is executed first to resolve faults for a given fop. If EGV fails, only then CFR is invoked for that fop. This interleaved execution continues until either the BP is fixed or there are no more candidate fixes to apply.

• H2:

  CFR is executed first to resolve faults for a given fop. If CFR fails, only then EGV is executed for that fop. Similar to H1, H2 is executed in an interleaved manner.

Algorithm 2 outlines the hybrid fault resolution approach, H1. The inputs to this algorithm are faulty BP graph, G_f, a set of test cases, T, and the set of existing BPs, 𝓑. H1 first calls fault localization to find the fop (Line 1). Next, a subgraph of G_f from $v_f^{\mathit{\text{start}}}$ to fop is extracted for generating candidate fixes (Line 2). EGV is called on this subgraph for resolution of faults up to the fop (Line 3). If a candidate fix (G_c) is found for the subgraph S, it is combined with the remaining part of G_f after the fop (Line 5). If G_c not only fixes the fault up to the given fop but also of the entire BP then the resulting BP is returned to the user as a fault-free BP Lines (6 – 8). Otherwise, if the candidate fix partially fixes the fault (i.e., it passes some, but not all, of the test cases that were originally failed), we use that candidate fix for further discovery and repair of faults by recursively calling H1 (Line 10). In case no partial fix is found, we call CFR for collaborative fault resolution (Line 13). Similar to the steps given in lines 4 – 11, we repeat these steps for CFR in lines 12 – 23. We recursively call H1 fault resolution procedure until all the faults are fixed or the entire space of candidate fixes is exhausted. The algorithm of hybrid fault resolution approach H2 is similar to Algorithm 2 except that it invokes CFR first followed by EGV.

Dataset:

For experimental evaluation, we consider the same dataset that was used for validation of CFR approach in [5]. This dataset consists of 48 fault-free BPs from three domains including, insurance, E-commerce, and flight reservation. For generation of faulty BPs, we used random fault injection to a correct BP from insurance domain which is not considered in above mentioned 48 BPs. Specifically, we applied random combinations of the mutation operators given in Table I to generate 208 faulty BPs which are considered for validation of the proposed approach. For generating a faulty BP, the number of mutation operators applied were between 1 and 4. The mean of the number of mutation operators applied was 2.24 and standard deviation was 0.81. The resulting faulty BPs covered all the fault categories (depicted in Table I) and their random combinations.

For comparison with CFR as well as evaluation of hybrid approach, we built a repository of existing BPs including all 48 fault-free BPs.

EGV:

For comparison of EGV with basic G&V, we performed experiments on 40 BPs as shown in Table III. Basic G&V outperforms EGV with 0.9 accuracy as opposed to 0.65 of EGV. But the higher accuracy is achieved at the cost of generating a lot more candidate fixes. Basic G&V, on average, validates 4139 candidate fixes for each BP whereas EGV only uses 10 candidate fixes. The accuracy of EGV is quite low (0.42) for variable assignment fault types as compared to G&V with an accuracy of 0.84. The accuracy of both EGV and G&V is almost the same for other fault types, though EGV uses a much smaller number of candidate fixes.

For comparison of EGV with CFR, we performed experiments on 112 BPs out of 208 that do not contain faults related to branch removal (AIE), activity removal (AEL), or constant modification (ECN). As discussed in Section III-B EGV is not designed for resolving fault types in which one or more BP elements are removed. Table IV shows the accuracy results of EGV in comparison to CFR approach. The results show that EGV has a higher accuracy than CFR on BPs with 1 and 2 fops and lower accuracy with 3 and 4 fops. Overall, EGV has an accuracy of 0.83 while CFR has an accuracy of 0.76. Apart from the gain in accuracy, EGV has the advantage of being able to resolve the faults without relying on existing BPs that have overlapping services with respect to the faulty BP. In terms of execution time EGV takes less time than CFR for resolving faults in BPs with 3 or less fops while CFR performs slightly better with 4 fops. This is because the number of mutants increase significantly with the increase in fops.

Hybrid Approach:

Hybrid approach combines both EGV and CFR in an interleaved fashion. As discussed in Section III-B, we consider two versions of hybrid approach, H1 and H2.

Table V shows the accuracy results of both H1 and H2 in comparison with CFR. As expected, both H1 and H2 have similar accuracy because both of them use the same underlying approaches but in a different order. Fig. 5 compares the execution time taken by CFR, H1 and H2. Overall, CFR performs slightly better than H1 and much better than H2 which takes almost twice as much time as CFR. However, H1 is more time-efficient for BPs with 1 or 2 fops, whereas, both H2 and CFR perform better than H1 for BPs with 3 and 4 fops. This is due to the fact the BPs with a higher number of fops have complex faults that cannot be resolved in isolation as done by EGV. In the presence of such complex faults, CFR and H2 (executing CFR first) perform better with respect to execution time because of the higher fault coverage of CFR.

A. Discussion

As depicted in Table III, EGV significantly improves the performance in terms of number of candidate fixes by reducing the search space. However, the overall accuracy of EGV is lower than the basic G&V approach.

EGV also outperforms CFR in terms of computation time with comparable accuracy but CFR provides a broader fault coverage as discussed in Section III-B. For example, CFR can resolve faults belonging to branch and activity removal. These faults cannot be resolved by the basic G&V and EGV. However, CFR requires a repository of existing BPs.

If such a repository exists, EGV can be combined with CFR to get the best of both worlds. This is exactly what the hybrid approach is designed to achieve. Both hybrid approaches H1 and H2 have similar accuracy across all fops as depicted in Table V. The accuracy of CFR is slightly higher than the hybrid approach (both H1 and H2) for one fop but is taken over by the hybrid approach as the number of fops increase. Consequently, the hybrid approach is preferred over CFR for better accuracy especially when higher number of fops are expected. In terms of performance, H1 is a better candidate for BPs with 1 or 2 fops. However, for BPs with higher number of fops H2 performs better than H1.

Test case generation.

Test case generation is an essential step towards automated testing of programs. Significant work has been done on automated testing and test case generation in the context of BPs [17]–[21]. Bartolini et al. [17] presented an approach that uses test services for white-box testing of third-party services and a tool, WS-TAXI, for automated generation of test cases from the WSDL definition of web services. Tarhini et al. [26] addressed the problem of test case generation for service compositions and validation of service compositions using WSDL definitions. Sun et al. [27] proposed a scenario-oriented framework for test case generation for web service compositions in BPEL. BP graph model is considered to derive test scenarios based on which test cases are generated. A constraint-based technique is employed for test data generation for execution of generated test cases.

Fault localization.

The purpose of fault localization is to identify locations (branches, statements, or blocks) in a faulty program that are suspicious i.e., likely to be erroneous and associated with the fault. The objective is to support programmers fix the faults by focusing only on the suspicious locations and to support automated repair and recovery of the given program [13], [25]. Existing works on fault localization techniques can be categorized into static and dynamic analysis-based techniques [25]. The static techniques mostly rely on model checking and static program analysis. Dynamic techniques compare and contrast the runtime behavior of correct and incorrect executions to isolate the fault-relevant locations.

Program slicing is one of the most frequently used techniques [25] that analyzes the runtime profile of a program to isolate the statements and blocks that are fault-relevant. Fault-relevant slice is obtained by filtering out the program slice that does not correspond to incorrect output(s) [23], [28], [29]. The most common fault localization techniques are spectra-based and employ dynamic analysis and coverage information of test cases to assign suspicious score to program elements. The program elements are then ranked by this score and programmers are expected to examine these elements in the ranked order [23], [30], [31]. Tarantula [32] is one representative technique in this category that has also been adapted in the context of business processes [23]. BPELSwice [23] targets the fault localization problem for business processes developed using BPEL. It uses predicate switching and program slicing to isolate the suspicious statements with greater precision. BPELSwice significantly reduces the size of the slice by acting at the statement level and identifying only suspicious statements from within BPEL blocks rather than marking the whole block as fault-relevant. Our proposed EGV approach employs the BPELswice approach for identifying suspicious code blocks in the faulty BP.

Delta debugging [9] works by applying small changes (deltas) to the programs and monitors their effect on the output. It can be used to discover development, deployment, and configuration faults. Delta debugging has also been adapted in the context of microservices [9] to unveil deployment and configuration faults as well as the faults that occur in execution orders of microservices. Delta debugging has also been used in combination with mutation testing [33] for accurate fault localization.

In our proposed EGV fault resolution approach, we use a combination of statistical fault localization and program slicing. However, our approach is independent of the underlying technique used for fault localization.

Fault resolution.

Considerable work has been done on automated program repair for software programs developed in C/C++ and Java but the existing approaches do not address automated repair in the context of BPs. Generate-and-validate (G&V) is a widely used technique [13]–[16] for automated repair and recovery that uses a faulty program and a set of passing and failing test cases as input to generate candidate fixes by heuristically searching the program space. The generated fix candidates are validated by running all available test cases that explores the search space of a program and finds candidate fixes by applying variety of changes heuristically. G&V requires a fault localization mechanism for identifying suspected code blocks in a faulty program. Candidate fixes are computed by applying mutations to the elements contained in these suspected code blocks. These candidates are then validated against the available test suite. Xu et al. have proposed RESTORE which is an efficient G&V-based framework focusing repair of Java programs [13]. RESTORE first performs fault localization to compute suspicious program snapshots. Candidate fixes are then generated for every suspicious snapshot by taking into account different mutations of the given program. To address the efficiency issue, only selected candidate fixes are validated by executing test cases in order of their suspicion scores. In case no candidate fix passes the entire test suite, partially successful fixes passing a subset of test cases are considered for generating variants of the given faulty program. All steps are then repeated for the generated variant until valid program fixes are identified. This retrospective strategy improves the efficiency of G&V by avoiding exhaustive validation of all candidate fixes.

In our recent work, we proposed the Collaborative Fault Resolution (CFR) approach [5] for BPs. CFR relies on a set of existing BPs that are composed of similar services and are assumed to be correct. Rather than examining the faulty BP in isolation, CFR makes use of the knowledge of these BPs to discover and fix faults in a faulty BP. However CFR requires a certain minimum overlapping services between the faulty BP and existing BPs for providing accurate results. It uses statistical fault localization to identify the fops in the given BP and then performs a pairwise analysis of the given faulty BP in comparison with related BPs of other users to identify their structural and semantic differences. Association rule mining is applied to these differences to identify the minimal overlapping set of differences that can be used to fix the faults. In this work, we have extended our proposed EGV approach with CFR for higher coverage of fault types as discussed in Subsection III-B.