Keeping business processes compliant with regulations is of major importance for companies. Considering the huge number of models each company possesses, an automation of compliance maintenance becomes essential. Therefore, many approaches focused on automation of various aspects of a compliance problem, e.g. compliance verification. Such techniques allow localizing the problem within the process model. However, they are not able to resolve a detected violation. In this paper we make the first attempt to systematically approach the problem of automatic violation resolution, addressing violations of execution order compliance rules. We categorize the violations into types and describe possible violation resolution strategies. The problem of choosing the concrete resolution strategy is addressed by the concept of context.
In todays business, being compliant to regulations is inevitable. Companies are hiring experts to audit their business processes and to evidence process compliance to external/internal controls. Keeping business processes compliant with constantly changing regulations is expensive [11]. Process models provide enterprises an explicit view on their business processes. Thus, it is rational to employ them for the business process compliance checking.
Several approaches have been proposed to handle the divergent aspects of compliance on the level of process models. Most of them are focused on a model compliance checking, i.e. on a model verification problem [1,10,16]. The problem of violation visualization was addressed in [3], where the authors proposed a mechanism for identifying and presenting to the user process traces violating a compliance rule. However, the question of compliance violation resolution was discussed in literature (for instance, see [6]). Usually this problem is considered as a task for a human expert. However, it would be possible to (semi) automate the task of resolving compliance violations. This would be valued as an aid to the human expert to speed up the process of ensuring compliance. This paper tackles the violation resolution problem and at the same time complements our previous work on the compliance problem presented in [1,3].
In this paper we make the first step towards resolving execution order compliance rule violations. Since the problem is new, we start with an analysis and an identification of the main challenges. The main contribution of the paper is the set of patterns, capturing possible violation situations and their resolution strategies. We also introduce the notion of resolution context, which defines the choice of preferable resolution strategy.
The rest of the paper is organized as follows. Section 2 discusses the state of the art in the area of compliance management in business process modeling. Section 3 frames the problem of compliance rule violation resolution, identifying the main challenges. A formalism employed in resolution strategies is presented in Section 4. Sections 5 and 6 represent the paper contribution where we formally define a catalog of violation patterns and reflect on the influence of a resolution context on the operation choice. Section 7 concludes the paper and discusses the future work.
An essential problem of compliance is identification of violations. Today a large body of research on compliance checking of business process models is published. Our primary interest is a work on an execution order compliance checking. The research in this area can be divided into two directions: a compliance by design and a compliance checking of existing models. The idea of compliance by design is to enforce a process model compliance already at the stage of design. [7,8,14,18,19] show how this approach can be realized. The other branch of research employs model checking techniques to verify that existing process models satisfy the compliance rules. [1,5,16,25] consider this problem. Following this approach the authors of [9,10] use business contracts as a source of compliance rules. To formalize compliance rules Formal Contract Language (FCL) is used. [21] separates process modeling from control objectives; it also uses FCL to express control requirements over annotated process models.
A resolution of violations can be driven by the severity of violations. In this sense an interesting method was introduced in [15]. This formal approach enables measuring the degree of compliance. Once a compliance rule is specified, the approach tells the degree of a compliance for a given process model on the scale from 0 to 1. The approach is implemented in an automated tool, which supports management decisions if the compliance violations should be resolved.
Recently, several requirements frameworks for business process compliance management have been proposed. In [17] the authors formulate requirements for tools. The requirements specify compliance management of semantic constraints (compliance rules), addressing the issues of a lifetime compliance. The focus is also on requirements to languages expressing compliance rules, on rule priorities, and on validation of process models against rules during design time and runtime. Another framework was proposed in [4]. Among other requirements, the authors discuss compliance enforceability. In this context they perceive the violation resolution as a human task, i.e. only human experts are responsible for taking remedy actions when a violation is discovered.
It should be noticed that [6] discussed possible strategies for resolving compliance violations. However, the discussion was very high level.
The related work outlook demonstrates that the problem of business process compliance is actual, since many of its aspects have been investigated. On the other hand, it reveals that in the area of compliance violation resolution not much has been done. Many mentioned research projects may profit if they are complemented by the technique of violation resolution. Therefore, we perceive these projects as a motivation for the problem of compliance violation resolution.
The problem of violation resolution inevitably involves structural modifications of process models. In this sense, a paper on workflow inheritance and change management [22] provides valuable information. In [20] the authors described adaptations correctness criteria, guiding the change operations. Recently, a set of change patterns has been discussed in [24] along with the discussion of changes correctness.
The goal of this section is to shape the problem of compliance violation resolution. We start with a discussion of execution order compliance rules and illustrate by examples this type of rules and their violations. Afterwards, we outline the challenges to be responded on the way to the resolution of the violations.
Execution order compliance rules restrict an order in which activities appear in a process model. In previous work [1], we distinguished two types of execution order rules: leads to and precedes. Compliance rule A leads to B requires that once there is an occurrence of activity A in a process model, each path leading from A to a process end contains an occurrence of activity B. A precedes B rule requires that once there is an occurrence of activity B in a process model, each path leading from a process start to B contains an occurrence of activity A. These are considered two basic rules from which more rules can be derived.
The named rules can be illustrated by the process example in Fig. 1. The figure presents a fragment of a buying process in an electronic shop from the customer perspective. It captures the final stage of a process, when the customer has already selected the goods and decided to checkout. Once a delivery address is provided, the customer chooses a payment method: either credit card, or cash (on delivery). Depending on the preferred method, the process evolves assuring that the customer gets the goods delivered. In case of on delivery payment, the customer receives a notification, once the order is confirmed. The rule Confirm order leads to Receive goods holds, since every time a customer confirms an order, the goods are received. The rule Confirm order precedes Get notification also holds. However, one can impose compliance rules that are violated in this example. For instance, Go to checkout leads to Pay by cash rule is violated: there is an alternative path which allows to skip paying by cash. One can also notice that Get notification precedes Receive goods rule is violated, since on the upper branch activity Get notification is missing.
The example shows that there are numerous situations when execution order compliance rules are violated. To address these multiple cases we introduce violation patterns. Each pattern captures a certain violation type and describes structural modifications needed to assure model compliance. The modifications operate with fragments of a process model, i.e. a connected subgraph of a graph representing the process model. In the trivial case a fragment is one activity. The structural modifications involve two elementary operations:
Add introduces a new fragment to a business process model. Remove deletes a fragment, which presents in an initial business process model.
Along with the two basic operations we introduce Move operation, which is the composition of Add and Remove. For the sake of convenience we use Move as a shortcut in the paper.
Let us refer to the example in Fig. 1. As we have mentioned Go to checkout leads to Pay by cash rule is violated in this fragment. To make the model compliant, we have to guarantee that once Go to checkout is executed, Pay by cash is executed as well. This can be achieved in several ways:
• one more occurrence of activity Pay by cash is added between activity Go to checkout and the XOR split; • Pay by cash is moved to that position; • Go to checkout is removed from the model.
Each of the named operations assures the compliance, but may introduce an inconsistency into the model. For instance, addition of activity Pay by cash before the choice means that the user always pays twice. Thus, the initial logic of the business process is broken. This example illustrates that not every modification making a model compliant is acceptable. The operations are sensitive to resolution context. The resolution context is defined by constraints which are imposed on every activity and which are considered to be significant during resolution process. The resolution context is independent from a concrete business process, but describes the business environment. Within the context one or more aspects (types of constraints) can be distinguished. Examples of aspects are control flow, data flow, and semantic annotations of activities and their interdependencies. The context may combine these three aspects in different ways. Meanwhile, we do not aim at identification of all possible aspects. Rather, in Section 6 we will discuss the influence of the context, looking at the examples. We also assume initial process models containing violations to be correct with respect to every aspect defined by the context.
Resolution of compliance violations requires structural modifications of a process model. On the contrary, formal definitions of leads to and precedes compliance rules operate with temporal relations between the activities. This means that one compliance rule regulates relations between multiple activity occurrences (i.e. between multiple model nodes). For instance, compliance rule Go to checkout leads to Confirm order holds for the process model in Fig. 1, while the rule considers one occurrence of activity Go to checkout and two occurrences of activity Confirm order. This mismatch can be resolved by a method reducing an analysis of a compliance rule to an analysis of node pairs. Such a method is out of scope of this paper and we assume that we can identify a concrete pair of nodes which causes a violation. Although we assume strict matching between activity labels in rules and models, approaches like the one in [2] can be used to relax this assumption.
Another challenge is resolution of multiple violations within one model (e.g. when a model is checked against several compliance rules). In this case we propose to perform resolution of each violation in isolation from others. Multiple violations can be resolved sequentially, one after another. A problem rises if resolutions of two violations contradict one another, i.e. a correction of one violation causes another violation and vice versa. This case requires interference of a human modeler who resolves the conflict.
Graph-based modeling notations allow creation of models with an arbitrary structure. We assume that process models are structured workflows. [13] defines a structured workflow as one in which each split control element (e.g. and, or) is matched with a join control element of the same type, and such split-join pairs are also properly nested. At the same time we allow structured loops in the form presented in Fig. 2.
Correction of compliance violations assumes analysis and modification of business process models on the structural level. Therefore, we need a technique efficiently supporting these tasks. We rely on the concept of a process structure tree (PST), which is the process analogue of abstract syntax trees for programs. PSTs can be constructed using various algorithms. We propose to use an algorithm developed in [23]. The assumption that process models are structured workflows is the direct consequence of this algorithm: the technique can recognize the organization of a structured workflow. We foresee that an application of a more efficient technique softens this assumption.
The concept of a process structure tree is based on the unique decomposition of a process model into fragments. One approach is decomposition of a model into canonical single entry single exit (SESE) fragments, described in [12,23]. Informally, a SESE fragment is a fragment with exactly one incoming and exactly one outgoing edge. The node sets of two canonical SESE fragments are either disjoint or one contains the other. Following [23] we consider a maximal sequence of nodes to be a canonical SESE region. If the node set of SESE fragment f 1 is the subset of the node set of SESE fragment f 2 , then f 1 is the child of f 2 and f 2 is the parent of f 1 . If f 1 is the child of f 2 and there is no f 3 , such that f 3 is the child of f 2 and f 3 is the parent of f 1 , f 1 is the direct child of f 2 . One example of a SESE fragment is a structured loop with one incoming edge and one outgoing edge. Further we will consider such loops, and to avoid any ambiguity we provide the definition of the loop employed in this paper. Definition 1. A loop is a SESE fragment containing at least two gateways: a join and a split. The join is incident to the entry edge of the fragment, the split-to the exit edge of the fragment; the loop has two branches: one leading from the join to the split is always executed (we call it mandatory) and the other leading from the split to the join may be skipped (optional ). It is allowed that one branch does not contain nodes.
Canonical SESE fragments can be organized into a hierarchy according to the parent-child relation. The hierarchy is represented with a directed tree called process structure tree. The tree nodes represent canonical SESE fragments. Definition 2. A process structure tree P = (N, E, r, t) is a tree, where:
• N is a finite set of nodes, where nodes correspond to canonical SESE fragments • r ∈ N is the root of the tree where a, p ∈ N act .
Since a tree has no cycles, a path between two nodes is a unique node sequence.
If there is no path between n 0 and n k we denote it with path(n 0 , n k ) = ⊥. We write n ∈ path(n 0 , n k ) to express the fact that n lies on the path from n 0 to n k .
Definition 5 formalizes the notion of the least common parent for two nodes.
Definition 5. The least common parent of two nodes n, m ∈ N in tree
If a node is of type seq the execution order for its direct children is defined.
Definition 6. The order of execution of node n ∈ N with respect to node p ∈ N seq is a function: order : N seq × N → N, defined if (p, n) ∈ E and where the first argument is the parent node and second-its child.
The notion of order can be extended to all the children of a node with type seq. Definition 7. The order * of execution of a node n ∈ N with respect to node p ∈ N seq is a function:
Then, the execution order compliance rules can be expressed as follows.
Definition 8. A process model is compliant with rule A leads to B if the process model lacks activity A or in the corresponding PST P = (N, E, r, t)
Definition 8 states that a process model is compliant with leads to rule in two cases. The first case is when there is no occurrence of activity A in the model. The second case describes the situation when the model contains at least one occurrence of A. Then, for each occurrence of A there must be a fragment which is executed in a sequence after A and which assures that B is always executed within it. Definitions 8 and 9 reveal that the two compliance rules are structurally similar and symmetric. Profiting from this similarity, in the remainder of the paper we will discuss only one compliance rule type, namely leads to. All the conclusions made for leads to rule can be trivially deduced for precedes.
In this section we present the catalog of compliance rule violation patterns. For each pattern we give the name and briefly discuss the problem it addresses. We motivate patterns providing examples. Finally, we formalize patterns in terms of PST.
Compliance rule A leads to B is violated in two cases: either there is no execution path leading from A to B, or there is an execution path leading from A The suggested resolution strategies for each violation pattern are given in terms of adding, removing, or moving operations of activities under studies. These operations might be executed recursively on other activities that are related to the activities addressed by the compliance rule as will be shown later in Section 6.
Probably the most challenging violation of rule A leads to B is the case when activities A and B appear in the inverse order. This means that a process model contains both activities A and B, connected with a path, but this path leads from B to A. Obviously, a compliance rule can not hold.
The inverse order violation can be illustrated by the following example. Assume that a company sends a notification with an order summary to a customer once the order is prepared. Afterwards, the company contacts its logistics partner to arrange a delivery. Fig. 3(b) captures a fragment of the model corresponding to this process. New business conditions require the company to include the delivery information in the notification, i.e. first the delivery should be organized. This requirement is captured in the rule Organize delivery leads to Notify customer rule. In this case an inverse order violation takes place. Fig. 3(a In general, inverse order violation can be fixed with one of the following operations:
Activities A and B can be located on different branches of a block. Independently of the block type, compliance rule A leads to B is violated. From the structural perspective violation of a rule follows from the fact that there is no execution path neither leading from A to B, nor from B to A (see Fig. 4(a)).
The example of different branches violation is shown in Fig. 4(b). It presents a variation of the business process discussed in section 5.1. In contrast to the initial example, Notify customer and Organize delivery activities are executed in parallel. The concurrent activities allow the company to shorten the execution time. However, once the company policy requires to notify a client about delivery details (i.e. Organize delivery precedes Notify customer compliance rule is imposed), the business process becomes incompliant. The following operations resolve the violation:
1. Remove A from process model 2. Add B to the branch with A directly after A 3. Add B directly after block 4. Add A directly before block (for and block) 5. Move A to the branch with B directly before B 6. Move B to the branch with A directly after A 7. Move B directly after block 8. Move A directly before block (for and block)
This violation pattern can be motivated by the following example. Assume we have a business process, containing the fragment presented in Fig. 5. The fragment shows that once a purchase request is received, its budget should be approved; before the approval the request can be optionally analyzed. However, one can require that every received purchase request must be analyzed. This requirement can be formalized in the form of compliance rule Receive purchase request leads to Analyze request. In the presented fragment this rule is violated, since after a purchase request is received, the analysis can be skipped. We call this type of violation splitting choice. Leads to compliance rule has a violation of type splitting choice if a model contains both activities A and B and, either A and B are connected with a path, but this path contains a split gateway (either or, or xor), or there is a loop and activity B is on the optional branch, while A is either before the loop or on its mandatory branch (see Fig. 6). Thus, the process model provides an option not to execute B, once A is executed.
The following operations allow to resolve splitting choice violation:
1. Remove A from process model 2. Remove all the branches which do not contain B 3. Add B to every branch in the choice block 4. Add B in between A and the block, directly after A 5. Add B directly after the block 6. Move A to the branch with B directly before B 7. Move B in between A and the block, directly after A 8. Move B directly after the block
A process model is not compliant with rule A leads to B if it has at least one occurrence of A and no occurrence of B. Consider a compliance rule Receive purchase order leads to Close purchase order. Checking the process model fragment in Fig. 5 against this rule, we see that this rule is violated, since it is missing in the process model.
Definition 13. Process model has a violation of compliance rule A leads to B and this violation is of type lack of activity if the PST for this model contains node a corresponding to activity A and for a there is no corresponding occurrence of activity B.
The following operations allow to resolve lack of activity violation:
1. Remove A from process model 2. Add B directly after A
In the previous section we have discussed alternative violation resolutions. Meanwhile, we have not considered how to choose the appropriate operation in a particular case. This choice is driven by the resolution context. In this section we aim at formalizing the context notion and illustrating its influence. of activity execution in terms of aspects. One aspect of a context is a tuple (N act , A t , t, type, con t , pre t , post t ), where t ∈ T ∧ A t = {a : a ∈ A, type(a) = t}. Definition 14 captures aspects with three elements: sets A and T and function type. Set A is the set of objects, describing the business environment from a certain perspective, e.g. dependencies of activities on data objects, activities execution constraints, or their semantic annotations. Set T consists of object types; an example is T = {controlF low, dataF low, semanticAnnotation}. Function type specifies a type (element of set T ) for an element of A. Typification of objects allows distinguishing aspects, e.g. distinguishing a data flow from a semantic description of a process. Relation con shows which objects from A contradict each other. A context example with one aspect for a process model in Fig. 1 is the following: N act = {Confirm order, Get notification, Go to check out, Pay by cash, Provide address, Provide credit card data, Receive goods}, A = N act , Let us look at the examples, illustrating the influence of a context on the resolution. In the example we refer to the fragment in Fig. 1. The fragment is evaluated against two compliance rules: Go to checkout leads to Provide credit card data and Go to checkout leads to Get notification. A thorough inspection reveals that both compliance rules are violated. Furthermore, both violations are of the same type splitting choice.
The original business process violates Go to checkout leads to Provide credit card data rule, providing the customer the alternative form of payment (i.e. paying by cash on delivery). At first blush the violation can be fixed with any of the strategies proposed by splitting choice pattern. For instance, the activities on the upper branch can be moved to the position before the block. According to the resolution context, the resulting resolution makes the process inconsistent because the two contradicting activities Provide credit card data and Pay by cash appear in sequence. Thus, the violation requires a resolution preserving exactly one required payment option and the corresponding process completion. The most suitable strategy is to remove all the branches alternative to the credit card payment. This makes the business process compliant with the rule and rational at the same time. Fig. 7(a) presents the result of this transformation.
Let us refer to the violation of the second rule. The business process in the example is not compliant with the rule, since the customer receives a notification only if "pay on delivery" method is selected. Although this violation has the same type as in the first example, the resolution strategy employed in the previous case is inappropriate here: a removal of one branch means that only one payment method is accepted. This effect is undesired as this resolution restricts the business process logic too much. Both alternative process evolutions have to be preserved, while a notification delivery should be included in both. Thus, in this case an occurrence of activity Get notification is added to the upper branch after activity confirm order, so that pre relation holds. The result of a violation resolution is presented in Fig. 7
It is obvious how the availability of the resolution context affects the choice of the resolution strategy. With several resolution strategies applicable, one can choose the strategy with the least change in the process structure, yet consistent with the context.
In this paper we attempted to address the problem of resolving compliance violations systematically. The problem is extremely complex and, thus, we started with the problem definition. We scoped our work, narrowing the type of addressed rules to execution order compliance rules and setting up the number of important assumptions. We assumed that we can learn a pair of activities which causes a violation and that violations can be resolved independently. Another important assumption is that process models are structured workflows.
The main contribution of this paper are a) the catalog of violation patterns, capturing all possible violation types and proposing resolution operations and b) the notion of a resolution context, which drives the choice of a suitable operation.
The violation patterns and the resolution context are perceived by us as the basis for the future work: they formalize the knowledge a human expert employs during violation resolution. Therefore, in the next steps we aim at developing algorithms enabling the choice of resolution strategies basing on the context. Another interesting question is to what extent the automatic resolution is possible, i.e. what kinds of violations can be automatically fixed and which can not.