A practical data-flow verification scheme for business processes

Data in business processes becomes more and more important. Current standard languages for process modeling like BPMN 2.0 which include the data flow reflect this. Ensuring the correctness of the data flow in processes is challenging. Model checking, i.e., verifying properties of process models, is a well-known technique to this end. An important part of model checking is the construction of the state space of the model. However, state-space explosion typically is in the way of an effective verification. We study how to overcome this problem in our context by means of reduction. More specifically, we propose a reduction on the level of the process model. To our knowledge, this is new for the data-flow analysis of processes. The core of our approach are so-called regions of the process model that are relevant for the verification of properties describing the data flow. Non-relevant regions are candidates for reduction of the process model, yielding a smaller state space. Our evaluation shows that our approach works well on industrial process models.     

Compositional encoding for bounded model checking

Verification techniques like SAT-based bounded model checking have been successfully applied to a variety of system models. Applying bounded model checking to compositional process algebras is, however, a highly non-trivial task. One challenge is that the number of system states for process algebra models is not statically known, whereas exploring the full state space is computationally expensive. This paper presents a compositional encoding of hierarchical processes as SAT problems and then applies state-of-the-art SAT solvers for bounded model checking. The encoding avoids exploring the full state space for complex systems so as to deal with state space explosion. We developed an automated analyzer which combines complementing model checking techniques (i.e., bounded model checking and explicit onthe-fly model checking) to validate system models against event-based temporal properties. The experiment results show the analyzer handles large systems.     

Verification and optimization of a PLC control schedule

We report on the use of model checking techniques for both the verification of a process control program and the derivation of optimal control schedules. Most of this work has been carried out as part of a case study for the EU VHS project (Verification of Hybrid Systems), in which the program for a Programmable Logic Controller (PLC) of an experimental chemical plant had to be designed and verified. The original intention of our approach was to see how much could be achieved here using the standard model checking environment of SPIN/Promela. As the symbolic calculations of real-time model checkers can be quite expensive it is interesting to try and exploit the efficiency of established non-real-time model checkers like SPIN in those cases where promising work-arounds seem to exist. In our case we handled the relevant real-time properties of the PLC controller using a time-abstraction technique; for the scheduling we implemented in Promela a so-called variable time advance procedure . To compare and interpret the results we carried out the same case study with the aid of the real-time model checker Uppaal, enhanced with facilities for cost-guided state space exploration. Both approaches proved sufficiently powerful to verify the design of the controller and/or derive (time-)optimal schedules within reasonable time and space requirements. Published online: 2 October 2002 The work reported here was carried out while the second and third authors were employed by the Computer Science Department of the University of Nijmegen, Netherlands. The second author was supported by an NWO postdoc grant, the third author by an NWO PhD grant, and both were supported by the EU LTR project VHS (Project No. 26270).     

Interface Grammars for Modular Software Model Checking

Verification techniques relying on state enumeration (e.g., model checking) face two important challenges: the state-space explosion, an exponential increase in the state space as the number of components increases; and environment generation, modeling components that are either not available for analysis, or that cannot be handled by the verification tool in use. We propose a semi-automated approach for attacking these problems. In our approach, interfaces for the components not under analysis are specified using a specification language based on grammars. Specifically, an interface grammar for a component specifies the sequences of method invocations that are allowed by that component. We have built an compiler that takes the interface grammar for a component as input and generates a stub for that component. The stub thus generated can be used to replace that component during state space exploration, either to moderate state space explosion, or to provide an executable environment for the component under verification. We conducted a case study by writing an interface grammar for the Enterprise JavaBeans (EJB) persistence interface, and using the resulting stub to check EJB clients using the JPF model checker. Our results show that EJB clients can be verified efficiently with JPF using our approach.     

Generating Scenarios by Multi-Object Checking

These days, many systems are developed applying various UML notations to represent the structure and behavior of (technical) systems. In addition, for safety critical systems like Railway Interlocking Systems (RIS) the fulfillment of safety requirements is demanded. UML-based Railway Interlocking (UML-based RI) is proposed as a methodology in designing and developing RIS. It consists of infrastructure objects and UML is used to model the system behavior. This design is validated and demonstrated by using simulation with Rhapsody. Automated verification techniques like model checking have become a standard for proving the correctness of state-based systems. Unfortunately, one major problem of model checking is the state space explosion if too many objects have to be taken into account. Multi-object checking circumvents the state space explosion by checking one object at a time. We present an approach to enhance multi-object checking by generating counterexamples in a sequence diagram fashion providing scenarios for model-based testing.     

A template-based approach for the generation of abstractable and reducible models of featured networks

We investigate the relationship between symmetry reduction and inductive reasoning when applied to model checking networks of featured components. Popular reduction techniques for combatting state space explosion in model checking, like abstraction and symmetry reduction, can only be applied effectively when the natural symmetry of a system is not destroyed during specification. We introduce a property which ensures this is preserved, open symmetry. We describe a template-based approach for the construction of open symmetric Promela specifications of featured systems. For certain systems (safely featured parameterised systems) our generated specifications are suitable for conversion to abstract specifications representing any size of network. This enables feature interaction analysis to be carried out, via model checking and induction, for systems of any number of featured components. In addition, we show how, for any balanced network of components, by using a graphical representation of the features and the process communication structure, a group of permutations of the underlying state space of the generated specification can be determined easily. Due to the open symmetry of our Promela specifications, this group of permutations can be used directly for symmetry reduced model checking.The main contributions of this paper are an automatic method for developing open symmetric specifications which can be used for generic feature interaction analysis, and the novel application of symmetry detection and reduction in the context of model checking featured networks.We apply our techniques to a well known example of a featured network – an email system.     

Analysis and improvement of business process models using spreadsheets

Software in general is thoroughly analyzed before it is released to its users. Business processes often are not – at least not as thoroughly as it could be – before they are released to their users, e.g., employees or software agents. This paper ascribes this practice to the lack of suitable instruments for business process analysts, who design the processes, and aims to provide them with the necessary instruments to allow them to also analyze their processes. We use the spreadsheet paradigm to represent business process analysis tasks, such as writing metrics and assertions, running performance analysis and verification tasks, and reporting on the outcomes, and implement a spreadsheet-based tool for business process analysis. The results of two independent user studies demonstrate the viability of the approach.     

Exploring the CSCW spectrum using process mining

Process mining techniques allow for extracting information from event logs. For example, the audit trails of a workflow management system or the transaction logs of an enterprise resource planning system can be used to discover models describing processes, organizations, and products. Traditionally, process mining has been applied to structured processes. In this paper, we argue that process mining can also be applied to less structured processes supported by computer supported cooperative work (CSCW) systems. In addition, the ProM framework is described. Using ProM a wide variety of process mining activities are supported ranging from process discovery and verification to conformance checking and social network analysis.     

Combining search space partition and abstraction for LTL model checking

The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the integration of search space partition and abstraction improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.     

Combining search space partition and search Space partition and abstraction for LTL model checking

The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size.Abstraction-based methods have been particularly successful in this regard.This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking.The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the Integration of search space partition and abstraction improves the efficiencyof verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.     

Verification of reactive systems via instantiation of Parameterised Boolean Equation Systems

Verification problems for finite- and infinite-state processes, like model checking and equivalence checking, can effectively be encoded in Parameterised Boolean Equation Systems (PBESs). Solving the PBES then solves the encoded problem. The decidability of solving a PBES depends on the data sorts that occur in the PBES. We describe a pragmatic methodology for solving PBESs, viz., by attempting to instantiate them to the sub-fragment of Boolean Equation Systems (BESs). Unlike solving PBESs, solving BESs is a decidable problem. Based on instantiation, verification using PBESs can effectively be done fully automatically in most practical cases. We demonstrate this by solving several complex verification problems using a prototype implementation of our instantiation technique. In addition, practical issues concerning this implementation are addressed. Furthermore, we illustrate the effectiveness of instantiation as a transformation on PBESs when solving verification problems involving systems of infinite size.     

Model-driven specification and enforcement of RBAC break-glass policies for process-aware information systems

ContextIn many organizational environments critical tasks exist which – in exceptional cases such as an emergency – must be performed by a subject although he/she is usually not authorized to perform these tasks. Break-glass policies have been introduced as a sophisticated exception handling mechanism to resolve such situations. They enable certain subjects to break or override the standard access control policies of an information system in a controlled manner.ObjectiveIn the context of business process modeling a number of approaches exist that allow for the formal specification and modeling of process-related access control concepts. However, corresponding support for break-glass policies is still missing. In this paper, we aim at specifying a break-glass extension for process-related role-based access control (RBAC) models.MethodWe use model-driven development (MDD) techniques to provide an integrated, tool-supported approach for the definition and enforcement of break-glass policies in process-aware information systems. In particular, we provide modeling support on the computation independent model (CIM) layer as well as on the platform independent model (PIM) and platform specific model (PSM) layers.ResultsOur approach is generic in the sense that it can be used to extend process-aware information systems or process modeling languages with support for process-related RBAC and corresponding break-glass policies. Based on the formal CIM layer metamodel, we present a UML extension on the PIM layer that allows for the integrated modeling of processes and process-related break-glass policies via extended UML Activity diagrams. We evaluated our approach in a case study on real-world processes. Moreover, we implemented our approach at the PSM layer as an extension to the BusinessActivity library and runtime engine.ConclusionOur integrated modeling approach for process-related break-glass policies allows for specifying break-glass rules in process-aware information systems.     

A modular approach to the specification and management of time duration constraints in BPMN

The modeling and management of business processes deals with temporal aspects both in the inherent representation of activity coordination and in the specification of activity properties and constraints. In this paper, we address the modeling and specification of constraints related to the duration of process activities. In detail, we consider the Business Process Model and Notation (BPMN) standard and propose an approach to define re-usable duration-aware process models that make use of existing BPMN elements for representing different nuances of activity duration at design time. Moreover, we show how advanced event-handling techniques may be exploited for detecting the violation of duration constraints during the process run-time. The set of process models specified in this paper suitably captures duration constraints at different levels of abstraction, by allowing designers to specify the duration of atomic tasks and of selected process regions in a way that is conceptually and semantically BPMN-compliant. Without loss of generality, we refer to real-world clinical working environments to exemplify our approach, as their intrinsic complexity makes them a particularly challenging and rewarding application environment.     

Automatic verification of concurrent systems using a formula-based compositional approach

When verifying concurrent systems, described by transition systems, state explosion is one of the most serious problems: systems are often described by transition systems with a prohibitive number of states. The primary cause of this problem is the parallel composition of interacting processes. In the recent years, compositional techniques have been developed to attack the state explosion problem. These techniques are based on dividing the verification task into simpler tasks, exploiting the natural decomposition of complex systems into processes. In this paper we present a formula-based compositional approach that allows us to deduce a property of a parallel composition of processes by checking it only on a component process. The approach can be automated and it is completely transparent to the user. Received: 17 May 2001 / 27 February 2002     

From fine-grained to abstract process models: A semantic approach

Organizations actively managing their business processes face a rapid growth of the number of process models that they maintain. Business process model abstraction has proven to be an effective means to generate readable, high-level views on business process models by showing coarse-grained activities and leaving out irrelevant details. In this way, abstraction facilitates a more efficient management of process models, as a single model can provide for many relevant views. Yet, it is an open question how to perform abstraction in the same skillful way as experienced modelers combine activities into more abstract tasks. This paper presents an approach that uses semantic information of a process model to decide on which activities belong together, which extends beyond existing approaches that merely exploit model structural characteristics. The contribution of this paper is twofold: we propose a novel activity aggregation method and suggest how to discover the activity aggregation habits of human modelers. In an experimental validation, we use an industrial process model repository to compare the developed activity aggregation method with actual modeling decisions, and observe a strong correlation between the two. The presented work is expected to contribute to the development of modeling support for the effective process model abstraction.     

Static analysis and process model transformation for an advanced business process to Petri net mapping

Verification of business processes typically relies on Petri net–based process models. While they allow for natural modeling and analysis of aspects such as parallelism and message exchange, such a process model is seldom complete and precise. This is mainly because the available techniques for deriving a Petri net model from the original model neglect process data in favor of feasible verification. In this paper, we present an approach for deriving more precise process models by leveraging a process‐to‐Petri‐net compiler, which takes as input a business process and generates as output a Petri net model for the process. This can be subsequently used for verification. However, in contrast to a conventional compiler, our compiler's objective is not to create the most efficient code but rather to produce a most precise but still effectively verifiable Petri net–based process model.     

Modeling and execution of event stream processing in business processes

The Internet of Things and Cyber-physical Systems provide enormous amounts of real-time data in the form of streams of events. Businesses can benefit from the integration of these real-world data; new services can be provided to customers, or existing business processes can be improved. Events are a well-known concept in business processes. However, there is no appropriate abstraction mechanism to encapsulate event stream processing in units that represent business functions in a coherent manner across the process modeling, process execution, and IT infrastructure layer. In this paper we present Event Stream Processing Units (SPUs) as such an abstraction mechanism. SPUs encapsulate application logic for event stream processing and enable a seamless transition between process models, executable process representations, and components at the IT layer. We derive requirements for SPUs and introduce EPC and BPMN extensions to model SPUs at the abstract and at the technical process layer. We introduce a transformation from SPUs in EPCs to SPUs in BPMN and implement our modeling notation extensions in Software AG ARIS. We present a runtime infrastructure that executes SPUs and supports implicit invocation and completion semantics. We illustrate our approach using a logistics process as running example.     

Symbolic abstraction and deadlock-freeness verification of inter-enterprise processes

The design of complex inter-enterprise business processes (IEBP) is generally performed in a modular way. Each process is designed separately and then the whole IEBP is obtained by composition. Even if such a modular approach is intuitive and facilitates the design problem, it poses the problem that correct behavior of each business process of the IEBP taken alone does not guarantee a correct behavior of the composed IEBP (i.e. properties are not preserved by composition). Proving correctness of the (unknown) composed process is strongly related to the model checking problem of a system model. Among others, the symbolic observation graph based approach has proven to be very helpful for efficient model checking in general. Since it is heavily based on abstraction techniques and thus hides detailed information about system components that are not relevant for the correctness decision, it is promising to transfer this concept to the problem raised in this paper: How can the symbolic observation graph technique be adapted and employed for process composition? Answering this question is the aim of this paper.     

工作流过程建模中的形式化验证技术

工作流过程建模是一个复杂且易错的过程．若过程定义在投入运行之后被发现有错,则修复错误的代价相当高,这个问题引起了研究界和工业界的高度重视．因此,在建模阶段进行有效的过程验证是十分必要的．综述了工作流过程验证技术的发展现状,包括强调验证的重要性,叙述了需要验证的问题和复杂度;介绍了对验证方法的要求;讨论了过程合理性验证和化简验证技术等;并通过对研究现状的分析和对比,提出了仍然没有解决的问题和将来的工作．     

Designing fast LTL model checking algorithms for many-core GPUs

Recent technological developments made various many-core hardware platforms widely accessible. These massively parallel architectures have been used to significantly accelerate many computation demanding tasks. In this paper, we show how the algorithms for LTL model checking can be redesigned in order to accelerate LTL model checking on many-core GPU platforms. Our detailed experimental evaluation demonstrates that using the NVIDIA CUDA technology results in a significant speedup of the verification process. Together with state space generation based on shared hash-table and DFS exploration, our CUDA accelerated model checker is the fastest among state-of-the-art shared memory model checking tools.