论文【流程感知信息系统日志中轨迹异常检测的算法】翻译

Algorithms for anomaly detection of traces in logs of process aware information systems

流程感知信息系统日志中轨迹异常检测的算法

Abstract

This paper discusses four algorithms for detecting anomalies in logs of process aware systems.

One of the algorithms only marks as potential anomalies traces that are infrequent in the log. The

other three algorithms: threshold, iterative and sampling are based on mining a process model from

the log, or a subset of it. The algorithms were evaluated on a set of 1500 artificial logs, with different

profiles on the number of anomalous traces and the number of times each anomalous traces was

挖掘流程模型。这些算法在一组 1500 条人工日志上进行了评估，其中异常轨迹的数量以及

每个异常轨迹在日志中出现的次数都有不同的概况。事实证明，采样算法是最有效的解决方

案。我们还将该算法应用于真实日志，并将检测到的异常轨迹与依赖于手动选择的不同程序

检测到的异常轨迹的结果进行比较。

1. Introduction and motivation

1. 简介和动机

Process aware information systems (PAISs) are ‘‘a software system that manages and executes

operational processes involving people, applications, and/or information sources on the basis of

process models’’ [17]. In this paper we are interested in systems in which the execution of said

processes are not predefined beforehand. Such systems fall within the ad hoc and loosely framed

统。此类系统属于[17]中描述的临时且松散框架的系统。这种松散框架系统的核心在于，执

行活动的人员可以控制决定案件下一步如何进行，以实现案例的目标。这种松散框架系统包

括灵活的工作流程系统、案例处理系统和科学工作流。

These systems allow for more control by the people executing the process, and are a possible

solution to what has been called the inflexibility of workflow systems [25,33]. But such flexibility

may come with a cost. Systems that are not under control of a pre-specified process model may be

subject to frauds and errors. Detecting such cases of frauds, exceptions and errors, which we will

call anomalies, is the goal of this research.

这些系统允许执行流程的人员进行更多控制，并且是所谓的工作流系统不灵活性的可能解决

方案[25,33]。但这种灵活性可能会带来成本。不受预先指定的流程模型控制的系统可能会受

severance benefits’’ and so on. In this paper, activities are considered atomic and their duration is

not important, thus the set of activities executed can be seen as a sequence. Furthermore we will not

attribute meaningful names to the activities, but refer to them using single letter names. Thus, Mr.

Schmidt firing case is seen as the sequence of activities abcbd, for example. Such sequences of

single letter activities are called traces. The set (or better the multiset) of traces from which one is

trying to identify the anomalies is called a log. Each trace can appear many times in the log, and

thus the multiset, and each time a particular trace appears in the log is called a trance-instance.

从本研究的角度来看，案例或流程实例的执行是代表该案例执行的一系列活动。因此，“解

雇 John Jacob Jingleheimer Schmidt”案件是“解雇”流程的一个实例，对于 Schmidt 先生案

件，执行了以下活动：“通知 Schmidt 先生”、“”计算应付余额”、“解释遣散费”等。在本

anomaly is detected solely based on the sequence and choices of activities that took place in that

anomalous execution. Thus, using the example above, one would detect that Mr. Schmidt firing was

anomalous because the particular sequence abcbd of activities was too different from the sequences

of activities for all or most of the other firing cases. For example, it may be the case that the activity

‘‘terminate Mr. Schmidt system access’’ was performed much later than usual, which could indicate

either that the system administrator was not properly trained regarding the security policies, or that

there was a collusion to allow Mr. Schmidt access to data he no longer should access.

这项研究展示了检测 PAIS 执行日志中的异常的结果，其中仅根据异常执行中发生的活动

的顺序和选择来检测异常。因此，使用上面的示例，人们会检测到 Schmidt 先生解雇案例

是异常的，因为特定的活动序列 abcbd 与所有或大多数其他解雇案例的活动序列差异太大。

Of course, the anomalous nature of a case may be derived from the values involved in some of the

activities (for example, Mr. Schmidt’s health benefits remain active for 300 month after his firing),

or because of the people who executed some of the activities (for example, the system access

termination activity was executed by a senior vice president), or because of time to perform an

activity or the whole process was greater or less than normal (for example, the calculation of balance

due was faster then normal). We call these examples as data, organizational, and time anomalies, to

match the other four aspects of process models [36]. This research is restricted to control flow

anomalies.

当然，案件的异常性质可能源于某些活动所涉及的价值观（例如，施密特先生的健康福利在

incorrect executions or if they are acceptable executions, and if they are found to be incorrect

executions, the reasons for and consequences of these executions must be further investigated. Thus,

the algorithms discussed in this paper must be used as a first automated step toward a more

comprehensive security auditing practice for flexible or loosely framed PAIS. This places some

constraints for the algorithms. If we focus on a fraud perspective—that is, that the anomalous traces

are a possible indication of frauds, then missing any of the potential fraudulent executions has

serious consequences. Thus, the algorithms to detect the anomalous traces must have a very low

false negative rate. The false negative cases are traces that the algorithm flagged as negative (or

‘‘normal’’) and that attribution was wrong. Such false negative cases will not be forwarded to the

specialists that would determine that the trace was indeed a fraud and take the appropriate measures.

本文讨论的算法必须用作针对灵活或松散框架的 PAIS 进行更全面的安全审计实践的自动

化第一步。这给算法带来了一些限制。如果我们关注欺诈的角度，即异常轨迹可能是欺诈的

迹象，那么错过任何潜在的欺诈执行都会产生严重的后果。因此，检测异常痕迹的算法必须

具有非常低的假负率。假负性案例是算法标记为负（或“正常”）且为错误的轨迹。此类假

负案例不会转发给专家，专家将确定该跟踪确实是欺诈行为并采取适当的措施。另一方面，

考虑到人工分析异常轨迹是否确实是欺诈是一个成本高昂的过程，人们也希望算法具有较低

的假负率，即被错误标记为异常（事实上它们不是）的案例数量——也应该保持低水平。但

低假正率不如低假负率重要。

If the anomalous traces are interpreted as errors, either erroneous execution or erroneous logging of

the processes, then the unbalance of costs between a false negative and a false positive is less severe.

A false negative will not generate the loss of revenue that an undetected fraud usually will incur.

Therefore under this perspective a more even balance between false negative and false positive rates

should be aimed at. In this paper we will also explore this alternative.

如果异常轨迹被解释为错误，或者错误执行或者错误记录流程，则假负性和假正性之间的成

本不平衡就不那么严重。假负性不会造成未发现的欺诈行为通常会造成的收入损失。因此，

从这个角度来看，应该在假负性率和假正性之间实现更均衡的平衡。在本文中，我们还将探

讨这种替代方案。

one has the intuition that anomalies are data points that have low probability of occurring (given the

appropriate generative model for the ‘‘normal’’ data), this intuition leads to the development of

family of techniques described in [10, Section 7] as statistical detection models.

The same apply to our research: we have no formal definition of an anomalous traces, but we have

some intuitions that guided the development of the algorithms discussed herein. They are

⚫ the set of executions can be partitioned into a set of normal and anomalous executions,

⚫ each of the anomalous execution is ‘‘infrequent’’ among the set of all executions, although

the whole set of anomalous executions may not be that infrequent,

⚫ the process models that ‘‘explain’’ the executions in the normal set ‘‘make sense’’,

⚫ the process models that could explain both the normal executions and some of the

,

,

.

最后，让我们解决什么是流程异常执行的问题。 Chandola 等人在一项关于异常检测的

重要调查中讨论了异常没有正式的定义，只有指导不同算法和技术开发的直觉。例如，人们

可能有这样的直觉：“正常”数据“在一起”（以某种适当的距离度量），而异常数据“分散”。

这种基于距离的直觉导致了许多基于最近邻的算法的发展。另一方面，如果人们有这样的直

如果想将这些直觉转化为一种或多种算法，那么术语“不频繁”、“解释”和“有意义”

需要进一步细化。然而，这些直觉可以用一些更精确的符号形式化，将不确定性限制在一些

常数和关系中。

，

是日志中轨迹的重数，

，

，

为 󰇝  󰇞 偏序  下的最大值。

1.2.简单的检测方法

Before discussing these terms (‘‘infrequent’’, ‘‘explain’’, and ‘‘make sense’’), the intuitions above

lend themselves to a first algorithm, which we call the naive algorithm. The naive algorithm resolves