Conformance checking, a method of process mining, is commonly used to assess how well a set of historic log traces ts a given process model, or vice versa. Here we explore online conformance checking, i.e., to check conformance on logs while they are written. This can be useful for near-realtime detection of errors and deviations from the desired path. While the online aspect leads to some challenges, we also study e cient detection of timing anomalies and violations of numerical invariants. The approach is implemented in CCaaS, a RESTful service that detects un tting events and other errors in split seconds.
One main activity in process mining is conformance checking, i.e., determining
if a process model ts a given event log, or vice versa. Conformance checking
is often used to assess the quality of discovery algorithms [
In contrast, in this work we propose to use conformance checking as an online
activity, to detect tness errors as soon as they can be observed. Consider the
example of earlier work, where we have shown that process-oriented analysis and
online error detection can strongly improve system reliability [
The applicability of online conformance checking is much wider than system log analysis. Whenever a process model needs to be followed strictly, e.g., to ensure compliance with laws and regulations, online conformance checking can be used to detect deviations in near-realtime.
Our contributions in this paper are4:
Retrieve log data
Basic conformance checking
Detect num.
invariant violations Detect timing anomalies
Visualize results (POD-Viz) { Timing anomaly detection, based on timing anomaly intervals that can be exported from a ProM plugin and imported into CCaaS, which in turn checks if the duration of any activity is anomalous. { Applying numerical invariants to conformance checking: based on numerical information in log events, CCaaS learns how many loop iterations or multiinstantiated (MI) subprocess instances should be executed, and checks if the actual number of executions adheres to this constraint.
CCaaS is part of the POD tool suite NICTA has developed over the past two years,5 where POD stands for Process-Oriented Dependability. 2
In this section we discuss the core features of CCaaS, shown in Fig. 1: retrieving events and mapping them to process models, basic conformance checking, timing anomalies, and numerical invariants. Finally, we discuss the implementation. 2.1
To retrieve log events in a timely fashion, a log agent can be deployed on the log-emitting system. We use the open-source tool Logstash6 for this purpose. Since CCaaS is implemented as a RESTful service, it su ces to con gure the Logstash agent to watch the location where logs are emitted (log le, database, or similar) and to forward each new log event to CCaaS via a HTTP invocation.
Once a new event is retrieved by CCaaS, we parse the event for the
information that allows us to associate the event with a process model, instance, and
activity in the model. This is log-type speci c, and implemented with regular
expressions. Relevant regular expressions can largely be learned during process
discovery, e.g., using POD-Discovery [
The main methods to check conformance are token replay [
Token replay reenacts a historic log on the model by moving tokens through the model based on the observed events (after they have been mapped to activities in the model). If an activity's execution is observerd, but there is no token activating it, an error is thrown indicating the missing token, and a new token is inserted to activate the activity.
CCaaS accepts process models in BPMN. BPMN's execution semantics can
be expressed as a token game, see e.g. [
However, there is one challenge in implementing online token replay: for decision points (like XOR splits) it is a priori unclear which subsequent branch should be activated, i.e., which outgoing edge should receive a token. In essence, for the purposes of token replay we have to interpret each XOR split as a deferred choice. While in the process model the decision may be based on deterministic criteria, for CCaaS as an outside observer, the criteria are in general not visible. Hence we have to wait for the next observable event, i.e, activity execution, before we know which decision was made.
We solve the challenge using a token pull mechanism, which, in brief, works
as follows. If activity A is observed, but not activated, we try to pull a token
from its predecessor in the model. If that predecessor is another activity or a join
gateway, the pull fails. If the predecessor is a split gateway, and is activated, the
gateway is executed and the pull succeeds; if the split gateway is not activated,
it attempts to pull a token from its predecessor, using the same logic.
Multiinstantiation can be handled by CCaaS as described in [
When business processes and activities are enacted multiple times and we measure the time spent in activities, we can learn the expected performance characteristics of activities. That is, we can learn the duration distributions of activities, which give us detailed insights into the timing behavior. We are interested in deviations from the expected behavior, e.g., if an activity is nished too early.
Based on the work of Rogge-Solti and Kasneci [
Technically, we compute the boundaries of the intervals by looking at the
distribution of the log-likelihood of random samples from the duration
distribution as suggested by Yeung and Chow [
With the 5th percentile estimated, we use its value d of the probability density
function (pdf) as a threshold. Finally, we subtract the density d from the pdf and
need to nd the roots of this shifted function. That is, we look for the regions
where this shifted pdf is negative. In the case of non-parametric kernel density
estimates using Gaussian heaps, we lack a closed analytic formula for the density.
Therefore, we apply a numeric root- nding algorithm as presented by Ford [
Once timing anomaly intervals are computed for the activities, CCaaS compares the durations of the activities, as observed through the respective events, to the corresponding intervals. If an observed duration is anomalous, i.e., it lies within the anomaly intervals, an according error is raised to warn the analyst. 2.4
In processes with iteration or multi-instantiation, some log events may contain
numerical information about the number of iterations or multi-instantiated (MI)
subprocesses that is expected if the current process instance operates correctly.
For instance, in logs from Net ix Asgard7 rolling upgrade, one log line states
"The group gr01 has 8 instances. 8 will be replaced, 1 at a time."
Subsequently, a loop is executed exactly 8 times, unless there is an error. One
technique to discover such numerical invariants in logs can be found in the
literature [
Based on such a speci cation, CCaaS watches for the start trigger; once observed, the concrete values for xmin and xmax in the current process instance are known. Then, CCaaS tracks every start of the invariant's scope and retains the number xcurr. If xcurr > xmax is observed, CCaaS raises an error. Once the end trigger is observed, CCaaS checks that xmin xcurr xmax, and that each of the xcurr instances of the scope completed successfully. Should any of these criteria not be met, an error is raised. 2.5
CCaaS is implemented in about 1800 lines of Java code, using the Spring framework, and is available as open-source.8 When invoked through the loopback network interface, average response time is typically below 10ms. In most deployments, higher network delays should be taken into consideration.
The computation and export of anomaly intervals are implemented in the ProM framework9, also available as open-source. Starting from an enriched stochastic Petri net, the plugin can compute anomaly intervals for all transitions, which are then exported as JSON for online anomaly detection in CCaaS.
General-purpose online conformance checking can support many usage scenarios.
Any scenario where the timeliness of detecting non-conformance or errors is
important can bene t strongly, e.g., so that the underlying issue can be corrected
before it turns into a serious problem. Behavioral log analysis and tracking can
be of great value to system reliability, as outlined in our previous work [
Two screencast videos accompany this paper. First, we show CCaaS through the POD-Viz frontend.10 Second, a brief screencast video shows the export of timing anomaly intervals from ProM.11 10 https://youtu.be/I-EjJGbvmzQ 11 http://andreas.solti.de/temporal-anomaly-intervals