理论计算机科学电子笔记121（2005）3-21www.elsevier.com/locate/entcs流程挖掘与安全：检测异常流程执行和检查流程一致性W.M.P. van der Aalst1，2荷兰埃因霍温理工大学技术管理系A.K.A. de Medeiros1，3荷兰埃因霍温理工大学技术管理系摘要安全系统的一种方法是通过审计跟踪分析。 审计跟踪是系统中和网络上发生的所有事件的记录，即，它提供了用户/系统操作的跟踪，以便安全事件可以与特定个人或系统组件的操作相关。可以检查审计跟踪是否存在某些模式。 本文提倡使用流程挖掘技术来分析安全违规的审计跟踪。 它显示了一个特定的算法，称为α算法，可以用来支持从低级入侵检测到高级欺诈预防的各种级别的关键词：过程挖掘，安全，审计跟踪，模式发现，数据挖掘，Petri网。1作者要感谢Ton Weijters、Boudewijn van Dongen、Minseok Song、Laura Maruster、Eric Verbeek、Monique Jansen-Vullers、Hajo Reijers、Michael Rosemann和Peter vanden Brand在埃因霍温理工大学对流程挖掘技术和工具的持续研究2电子邮件：w.m.p.v.d. tm.tue.nl3电子邮件：a.k. tm.tue.nl1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.10.0134W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）31介绍在事务信息系统中事件日志无处不在的推动WFM，ERP，CRM，SCM和B2B系统），流程挖掘已经成为一个生动的研究领域[5，6]。直到最近，这些事件日志中的信息很少用于分析底层流程。 流程挖掘旨在通过提供从事件日志中发现流程、控制、数据、组织和社会结构的技术和工具来改进这一点，即，流程挖掘的基本思想是通过挖掘事件日志来诊断流程。到目前为止，过程挖掘的研究主要集中在过程发现和过程改进上。在本文中，我们专注于应用程序挖掘的安全问题。在考虑企业信息系统时，安全性在不同级别上发挥作用，即，从UNIX进程级别到组织间业务进程级别。安全策略可能涉及从加密和基于角色的访问控制到审计和四眼原则的范围。安全违规行为可能由黑客实施，也可能由白领犯罪分子实施（参见安然和帕玛拉特丑闻之后关于“公司治理”的讨论）。关于安全的文献可以分为计算机安全[11]和审计[32]。尽管计算机安全和审计处于非常不同的级别，但某些行为模式的存在或不存在可能表明存在安全违规。因此，审计跟踪是有用的。幸运的是，许多企业信息系统以某种结构化的形式存储相关事件。例如，工作流程管理系统通常会记录活动的开始和完成[3]。SAP等ERP系统记录所有事务，例如，用户填写表格、更改文档等。企业对企业（B2B）系统记录与其他方的消息交换。呼叫中心软件包以及通用CRM系统记录与客户的交互。这些示例表明，许多系统都有某种类型的事件日志，通常称为事件日志通常包含与活动和案例相关的事件的信息。案例（也称为过程实例）是正在处理的“事物”，例如，客户订单、工作申请、保险索赔、建筑许可等。活动（也称为任务、操作、动作或工作项）是对案例的某种操作。通常，事件具有指示发生时间的时间戳。此外，事件日志通常还包含关于参与者的信息，即，执行或启动事件的人或系统组件。我们将把这样一个演员称为发起者或执行者。基于这些信息，已经开发了几种用于流程挖掘的工具和技术[2，4，5，7，8，13，23，24，29，33，36]。流程挖掘之所以有用，至少有两个原因。首先，它可能是W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）35作为一种工具，用来找出人和/或程序是如何真正工作的。例如，考虑由SAP等ERP系统支持的流程（例如，采购过程）。这种系统记录所有交易，但在许多情况下并不强制执行特定的工作方式。在这样的环境中，流程挖掘可以用来深入了解实际流程。另一个例子是医院里病人的流动。请注意，在这种环境中，所有活动都将被记录，但有关底层进程的信息通常会丢失。在这种情况下，重要的是要强调，管理信息系统提供有关关键绩效指标的信息，如资源利用率、流程时间和服务水平，但不提供有关底层业务流程的信息（例如，因果关系、活动顺序等）。其次，流程挖掘可以用于Delta分析，即，将实际过程与预定过程进行比较。请注意，在许多情况下，存在描述性或规定性的过程模型。这种模型具体说明了人们和组织如何被假设/期望工作。通过将描述性或规定性过程模型与发现的模型进行比较，可以检测两者之间的差异并用于改进过程。例如，考虑SAP环境中所谓的参考模型。这些模型描述了系统应该如何使用。使用过程挖掘可以验证是否是这种情况。事实上，流程挖掘也可以用于比较使用相同ERP系统的不同部门/组织。显然，这两个方面（发现和增量分析）都与计算机安全和审计有关。例如，在[19]中，提出了一种用于入侵检测的方法。该方法检查审计跟踪并使用固定长度模式来区分自我（即，正常进程执行）与其它（即，潜在的安全违规）。在[37]中，这被扩展到可变长度的pat。不幸的是，像[19，37]这样的方法不考虑过程结构，并且无法检测并行性和因果关系。因此，我们在安全性的上下文中探讨了进程挖掘的概念和一个算法（α算法，[7]）。本文的其余部分组织如下。第二节介绍了流程挖掘的概念。第三节介绍了基本的符号表示法，并给出了基本的α算法。然后重点研究了两个问题：异常进程执行检测（第4节）和进程一致性检查（第5节）。第6节提供了一些相关的工作。最后，第7节对本文进行了总结。6W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）32流程挖掘：概述流程挖掘的目标是从事务日志中提取有关流程的信息[5]。我们假设有可能记录事件，(i) 每个事件指的是一个活动（即，过程中定义明确的步骤），（ii）每个事件都涉及一个案例（即，过程实例），（iii）每个事件可以具有执行者，也称为发起者（执行或发起活动的行动者），以及（iv）事件具有时间戳并且是完全有序的。表1显示了一个包含19个事件、5个活动和6个发起者的日志示例除了此表中显示的信息外，某些事件日志还包含有关案例本身的更多信息，即，数据元素涉及案件的属性。例如，案件处理系统FLOWer记录某些数据元素的每次事件日志4（例如表1中所示的事件日志）用作挖掘的起点。我们区分了三种不同的视角：（1）过程视角，（2）组织视角和（3）案例视角。过程视角关注控制流程，即，活动的顺序伊茨。挖掘这种观点的目的是找到所有可能路径的良好特征，例如，用Petri网[31]或事件驱动过程链（EPC）[24，25]表示。组织视角侧重于发起人领域，即，哪些表演者参与其中，以及它们之间的关系。其目标是通过将人员按以下方面进行分类来构建组织或者显示各个执行者之间的关系（即，建立一个社交网络[9，10，12，16，20，21，28，30，34，35]）。案例视角关注案例的属性。案例可以通过其在流程中的路径或处理案例的发起者来表征。 然而，病例也可以通过相应数据元素的值来表征。例如，如果一个案例代表一个补货订单，那么了解供应商或订购的产品数量是很有意义的。过程视角关注的是“如何”？问题，组织视角关注的是“谁？”问题，和案件的角度是关注的“什么？”问题为了说明前两种情况，请看图1。表1所示的日志包含有关五种情况的信息（即，过程实例）。日志显示，对于四种情况（1、2、3和4），活动A、B、C和D已经执行。在第五种情况下，只执行三个活动：活动A、E和D。每一个案件都以执行A开始，以执行D结束。如果活动B被执行，那么活动C也被执行。然而，在某些情况下，活动C在活动B之前执行。根据表1所示的信息，4在安全性方面，事件日志应被解释为审计跟踪。W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）37病例id活动id发起者时间戳情况1活动A约翰二零零四年三月九日：15.01壳体2活动A约翰二零零四年三月九日：15.12壳体3活动A起诉二零零四年三月九日：16.03壳体3activity B卡罗尔二零零四年三月九日：16.07情况1activity B迈克二零零四年三月九日：18.25情况1活动C约翰二零零四年十月三日：9.23壳体2活动C迈克2004年3月10日：10.34壳体4活动A起诉2004年3月10日：10.35壳体2activity B约翰2004年3月10日：12.34壳体2活动D皮特2004年3月10日：12.50壳体5活动A起诉2004年3月10日：13.05壳体4活动C卡罗尔2004年3月11日：10.12情况1活动D皮特2004年3月11日：10.14壳体3活动C起诉2004年3月11日：10.44壳体3活动D皮特2004年3月11日：11.03壳体4activity B起诉2004年3月11日：11.18壳体5活动E克莱尔2004年3月11日：12.22壳体5活动D克莱尔二零零四年三月十一日：14.348W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3壳体4活动D皮特二零零四年三月十一日：15.56表1事件日志（审计跟踪）。通过对日志的完整性做出一些假设（即，假设这些情况是有代表性的，并且观察到了足够大的可能行为子集），我们可以推导出图1（a）所示的过程模型该模型用Petri网表示[31]。Petri网以活动A开始，以活动D结束。这些活动由过渡表示。在执行A之后，可以选择是并行执行B和C，还是只执行活动E。为了并行执行B和C，添加了两个不可观察的活动（AND-拆分和AND-连接）W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）39B和- 分和- 加C一DE(a)用Petri网表示的控制流结构约翰·苏角色X角色Y角色Z克莱尔迈克约翰·苏·迈克·卡罗尔·皮特·克莱尔皮特卡罗尔(b) 用活动-角色-执行者图表示的组织结构。(c) 基于工作转移的社会图。Fig. 1.基于事件日志的流程视角（a）和组织视角（b和c）的一些挖掘结果如表1所示。添加这些活动仅用于路由目的，不会出现在事件日志中。请注意，对于这个例子，我们假设两个活动是并行的，如果它们以任何顺序出现。通过区分活动的开始事件和完成事件，可以显式地检测并行性。图1（a）没有显示关于该组织的任何信息，即，它不使用关于执行活动的人的任何信息。然而，表1显示了关于执行者的信息例如，我们可以推断活动A由John或Sue执行，活动B由John、Sue、Mike或Carol执行，C由John、Sue、Mike或Carol执行，D由Pete或Clare执行，E由Clare执行。我们可以在图1（a）中指出这一信息。 这些信息也可以用来“猜测”或“发现”组织结构。例如，可以猜测有三个角色：X、Y和Z。对于A的执行，需要角色X，John和Sue具有此角色。对于B和C的执行，需要角色Y，并且John、Sue、Mike和Carol具有该角色。 用于执行D和E角色Z是必需的，皮特和克莱尔有这个角色。 在五种情况下，这些选择可能看起来是任意的，但对于更大的数据集，这样的推论抓住了组织中的主导角色。由此产生的这三个图1（c）显示了基于工作从一个人转移到另一个人的组织的另一个视图，即，不是关注过程与个人之间的关系，而是关注个人（或个人群体考虑例如表1。虽然10W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3Carol和Mike可以执行相同的活动（B和C），Mike总是与John一起工作（案例1和2），Carol总是与Sue一起工作（案例3和4）。Carol和Mike可能有相同的角色，但根据表1中显示的小样本，似乎John没有与Carol一起工作，Sue也没有与Mike一起工作。5这些例子表明，事件日志可用于导出活动执行者之间的关系，从而形成社会关系图。例如，可以根据工作从一个人转移到另一个人来生成社会图，如图所示图1（c）。每个节点代表六个执行者之一，arc表示工作从一个人转移到另一个人。“工作从A转移到B”的定义例如，在案例1和案例2中，都存在从John到Mike的转移。图1（c）没有显示频率。然而，出于分析目的，可以添加这些频率。从John到Mike的弧的权重为2。通常，我们不使用绝对频率，而是使用加权频率来获得0和1之间的相对值图1（c）显示工作转移给Pete，但反之亦然。迈克只和约翰打交道，卡罗尔只和苏打交道。克莱尔是唯一一个把工作转给自己的人。除了“怎么做”和“谁”问题（即，过程和组织视角），还有一种案例视角关注的是“什么？”问题图1没有解决这个问题。事实上，当数据元素也被记录时，关注案例透视图是最有趣的，但是这些数据元素没有在表1中列出。案例视角将案例视为一个整体，并试图在案例的各种属性之间建立关系。请注意，某些属性可能涉及正在执行的活动、处理案例的执行者以及链接到案例的各种数据元素的值。例如，使用聚类算法，可以显示订单大小或处理时间与特定人员的参与之间的正相关关系。与三个视角（过程、组织和案例）正交，挖掘结果可能涉及逻辑问题和/或性能问题。例如，流程挖掘可以关注流程模型的逻辑结构（例如，图1（a）中所示的Petri网）或性能问题（如排队时间）。为了挖掘组织视角，重点可以放在角色或社交网络上（参见图1（b）和（c））或利用情况[5]显然，表1中的事件数量太少，无法准确地建立这些假设。然而，为了论证，我们假设没有发生的事情永远不会发生。W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）311··执行者或执行频率。为了解决这三个方面以及逻辑和性能问题，我们开发了一套工具，包括EMiT [2]，Thumb [36]和MinSoN [4]。这些工具共享一个通用的XML格式。欲了解更多详情，请访问http://www.processmining.org。3WF网与α算法本节包含α算法中使用的主要定义。有关α算法及其支持定义的更多信息，请参阅[7]。我们假设一些基本的Petri网知识。 不熟悉基本概念的读者，如（P，T，F）作为Petri网的表示，触发规则，触发序列，预设x，后集x，有界性，活性，可达性等参考[1，14，31]。3.1工作流程网在介绍α-算法之前，我们简要地讨论了Petri网的一个子类--工作流网（WF-nets）。该子类被定制用于对工作流程6或任何其他情况驱动过程的控制流程维度进行建模，例如，登录到一个系统。应该注意的是，工作流网指定了孤立的单个情况的动态行为[1]。定义3.1[工作流网]设N=（P，T，F）是一个Petri网，且新鲜标识符不在P∈T中。N是一个工作流网（WF-net）i，(i) 对象创建：P包含一个输入位置i，使得·i=0，(ii) 对象完成：P包含一个输出位置o，使得o·=0，塔阿(iii) 连接数s：N<$=（P，T<${t<$}， F<${（o，t<$），（t<$，i）}）是连续的，图1所示的Petri网是一个工作流网。注意，虽然网不是强连通的，具有过渡t<$的短路网络是强连通的。即使一个网络满足定义中规定的所有语法要求，initiation3.1，相应的进程可能会出现错误，如死锁，任务永远不会成为活动的，活锁，垃圾被留在进程终止后，等等，因此，我们定义了以下的正确性标准。定义3.2[声音]设N=（P，T，F）是输入位置为i的WF-网和输出位置O。 N是声音i：(i) 安全：（N，[i]）是安全的，6请注意，我们可以互换使用工作流程和过程这两个词。12W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3•≥⟩·(ii) 真完备：对于任何标记s∈[N，[i] n，o∈s蕴涵s=[o]，(iii) 选择完成：对于任何标记s∈[N，[i] n，[o]∈[N，sn，和(iv) 不存在死任务：（N，[i]）不包含死转换。所有声音WF-网的集合记为W。图1所示的WF网络是可靠的。可靠性可以使用标准的基于Petri网的分析技术进行验证[1，3]。大多数流程建模语言都提供了标准的构建块，如AND-分割、AND-连接、XOR-分割和XOR-连接[3]。这些用于模拟顺序，条件，并行和迭代路由。显然，工作流网可以用来指定案件的路由，即，过程实例。任务，也被称为活动，通过转换建模，因果依赖关系通过位置和弧建模。事实上，位置对应于可以用作任务的前置和/或后置条件的条件。AND分裂对应于具有两个或更多个输出位置的转换，AND连接对应于具有两个或更多个输入位置的转换。异或分割/异或连接对应于具有多个传出/传入弧的位置。鉴于任务和过渡之间的密切关系，我们可以互换使用这两个术语我们的过程挖掘研究旨在从事件日志中重新发现WF-网。然而，并不是声音WF网络中的所有位置都可以被检测到。例如，位置可以是隐式的，这意味着它们不影响进程的行为这些地方仍未被发现。因此，我们的调查到没有隐式位置的WF网。定义3.3[隐式位置]设N=（P，T，F）是初始标记为s的Petri网。一个位置p∈P称为隐在（N，s）中当且仅当对所有可达标记SJ∈[N，s∈P·，SJ≥·t\{p} ∈SJ≥·t.7图1不包含隐式位置。然而，添加一个连接变迁A和D的位置p会产生一个隐式位置。没有挖掘算法能够检测到p，因为添加位置不会改变网络的行为，因此在日志中不可见对于流程挖掘，工作流网的结构清楚地反映其行为是非常重要的。因此，我们也排除了图2所示的构造。左边的结构说明了选择和同步永远不会遇到的约束。如果两个转换共享一个输入位置，因此“争夺”同一个标记，那么它们不需要同步。这意味着选择（具有多个输出转换的位置）不应该7[N，s是网N从标记s开始时的可达标记集，p是p的输出转移集，t是t的输入位置集，是多重集上的标准序关系。W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）313∈∈∈|·|| · |(i)（二）图二. 在SWF网络中不允许构造。与同步混合。图2中的右侧结构说明了如果存在同步，则所有前面的转换都应该被触发的约束，即，不允许XOR连接直接先于同步。满足这些要求的工作流网被称为结构化工作流网，定义为：定 义 3.4[SWF-net] 一 个 WF-netN = （ P ， T ， F ） 是 一 个 SWF-net（Structured Work Flow Net）当且仅当：(i) 对于所有p∈P和t∈T，其中（p，t）∈F：|p·|> 1意味着|·t|= 1。(ii) 对于所有pP和tT，其中（p，t）F：t >1意味着p= 1。(iii) 没有隐含的地方。3.2α算法流程挖掘的起点是事件日志。日志是一组轨迹。事件跟踪和日志定义为：定义3.5[事件跟踪，事件日志]设T是一组任务。 σ∈T是一个事件迹，W∈ P（T∈）是事件日志。8从事件日志中，可以推断任务之间的顺序关系。在α算法的情况下，事件日志中的每两个任务必须具有以下四种排序关系之一：>W（跟随），→W（因果），W（并行）和#W（不相关）。这些顺序关系是基于事件轨迹中的局部信息提取的。排序关系定义为：定义3.6[基于日志的排序关系]设W是T上的事件日志，即，W∈ P（T∈）.设a，b∈T：• a > Wb当且仅当存在迹σ=t1t2t3. t n−1且i∈ {1，.，n−2}使得σ∈W且ti=a且ti+1=b，8T是由来自T的零个或更多个任务组成的所有序列的集合。P（T）是T的幂集，即，我的天。14W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3--• a→Wb当且仅当a >W b且bW a，• a#Wb当且仅当aW b且b/>W a，• a ≠ Wb当且仅当a > W b且b > W a.为了确保事件日志包含挖掘过程所需的最少量信息，日志完整性的概念定义为：定义3.7[完整事件日志]设N=（P，T，F）是一个可靠的WF网，即，N∈W。W是N的事件日志，当且仅当W∈ P（T），并且每个迹σ∈W是N的从状态[i]开始到状态[o]结束的触发序列，即，（N，[i]）[σ（N，[o]）. W是N的完备事件日志当且仅当（1）对N的任意事件日志WJ：>WJ<$>W，（2）对任意t∈T有σ∈W使得t∈σ。对于图1，可能的完整事件日志W是ABCD、ACBD、AED。从这个完整的日志中，可以推断出以下顺序关系：• （如下）A >W B，A >W C，A >W E，B >W C，B >W D，C >W B，C >W D和E >W D。• （因果）A→WB，A→WC，A→WE，B→WD，C→WD和E→WD。• （parallel）BWCandCWB.现在我们可以给出α算法的形式定义，然后给出更直观的解释。定义3.8[挖掘算法α]设W是T上的事件日志。的α（W）定义如下。(i) T W={t∈T| <$σ∈Wt∈ σ}，(ii) T I={t∈T| <$σ∈Wt = first（σ）}，(iii) T O={t∈T| <$σ∈Wt = last（σ）}，(iv) XW={（A，B） | AT WBT Wa∈Aba1，a 2∈Aa1#Wa2 <$b 1，b2∈Bb1#Wb2}，(v) Y W={（A，B）∈X W|<$（AJ，BJ）∈XWA<$A J<$B <$BJ=<$（A，B）=（AJ，BJ）}，(vi) PW={p（A，B）|（A，B）∈YW}<${iW，oW}，（vii）FW={（a，p（A，B））|（A，B）∈YW<$a∈A}<${（p（A，B），b）|（A，B）∈Y W<$b∈B}<${（i W，t）|t∈T I}<${（t，o W）|t∈T 0}，以及（viii）α（W）=（PW，TW，FW）.α算法的工作原理如下。首先，它检查事件跟踪，并（步骤1）创建流程中的转换集（TW），（步骤2）源位置的输出转换（TI）的集合，以及（步骤3）源位置的输出转换（T I）的集合。W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）315P → W∈ W∈·∩·∅·∩·∅B一EDC接收器位置9的输入转换（T0）。在步骤4和5中，α算法创建集合（分别为XW和YW），用于定义所发现的WF-网的位置在步骤4中，α算法发现哪些转换是因果相关的。 因此，对于XW中的每个元组（A，B），集合A因果关系到集合B中的所有转换，并且A（或B）中没有转换在某些触发序列中彼此对集合A和B中的元素的这些约束允许正确地挖掘AND-分裂/联接和XOR-分裂/联接构造。请注意，XOR拆分/连接需要位置的融合。在步骤5中，α算法通过只取关于集合包含的最大元素来细化集合XW。实际上，步骤5确定了所发现的网络所具有的位置（不包括源位置iW和汇位置oW）。这些位置在步骤6中创建，并在步骤7中连接到它们各自的输入/输出转换。发现的WF-net将在步骤8.图3显示了将α算法应用于表1所示的日志的结果，即W={ABCD，ACBD，AED}。请注意，α算法不能发现图1所示的AND-分裂和AND-连接（这些不在日志中），但仍然能够构建等效的WF-网。图三. 由α算法发现的WF-网（基于表1）。最后，我们定义了重新发现WF网的意义，并粗略地描述了α算法正确工作的过程类。定义3.9[重新发现的能力]设N=（P，T，F）是一个可靠的WF网，即，N，设α是映射N个事件日志的挖掘算法，到健全的WF网，即， α：（T）。如果对于N中的任何完整事件日志W，挖掘算法返回N（对位置的重命名取模），则α能够重新发现N。定理3.10设N=（P，T，F）是一个可靠的SWF-网，W是N的一个完全事件日志。 如果对于所有a，b不是B=或ba=，则α（W）=N模地名名.9在工作流网中，源位置i没有输入转换，宿位置o没有输出转换。16W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3}请注意，没有挖掘算法能够找到地名。因此，我们忽略地名，即，α能够重新发现N当且仅当α（W）=N模位置重命名。还要注意不允许“短循环”的要求。使用[27]中描述的细化可以避免这种额外的要求4检测异常进程执行在3.2小节中，我们介绍了α算法如何挖掘表1中的案例，并发现描述所有可能行为的过程（见图3）。如果我们将事件日志视为审计跟踪，则类似的推理也适用于安全问题，例如会话ID。在本节中，我们将展示（i）如何使用α算法来发现系统中可接受的或正常的行为，以及（ii）如何使用发现的网络来检测不期望的行为。当作为输入的完整日志只有可接受的审计跟踪时，α算法发现一个网络，该网络对所有可接受的行为进行建模，并且发现的网络是一个可靠的WF网络。例如，想象一个用于销售产品的网站。假设这个网站中的每个用户都有一个可以随时编辑的购物篮。如果用户离开网站时购物篮中包含产品，则用户购物篮的状态将被保存，并在用户再次进入网站时检索。可能的用户操作由图4所示的WF-网络描述。现在，假设我们不知道图4中的网络，但是我们有一个完整的可接受的审计跟踪日志。例如，让此审计日志为W OK={“输入，选择产品，添加到购物篮，取消订单“，“输入，选择产品，从购物篮中删除，取消“，“输入，选择产品，添加到购物篮，继续购物，选择产品，从购物篮中删除，继续购物，选择产品，添加到购物篮，继续结账，填写交付信息，填写付款信息，提供密码，处理订单，完成结账“，“输入，选择产品，从购物篮中删除，继续结账，填写付款信息，填写交付信息，提供密码，处理订单，完成结账“。给定WOK作为输入，α算法发现图4所示的网络。一旦网络被发现，每个新的审计跟踪的一致性可以通过玩“令牌游戏”来验证。 请注意，异常的审计跟踪并不对应于被发现网络的“令牌游戏”中可能的触发序列。此外，例如，让我们验证新的审计日志W NOK={“输入，选择产品，从购物篮中删除，继续结账，W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）317下沉位置图四、在网站上购买产品的过程描述示例填写送货信息，填写付款信息，提供密码，处理订单，完成结账“，“输入，选择产品，从购物篮中删除，继续结账，填写付款信息，填写送货信息，处理订单，完成结账“}，通过在图4中的网络中播放W OK中的每个跟踪。WNOK的第一个审计线索是可以接受的。 请注意，此踪迹不在WOK中，但它可以由已发现的网络生成。第二个线索是一个异常线索，因为它不包含任务Provide Password。通过玩换句话说，EMiT工具[15]支持请注意，α算法正确地发现了图4中的网络，而不需要然而，由于α算法旨在发现过程视角，因此它不捕获与系统中的数据相关的约束，例如循环可能重复的最大次数。对于图4中的示例，循环可以无限次执行而不会违反安全问题。 尽管如此，如果循环将对应于用户尝试登录到系统中，则必须设置循环迭代的最大次数。如果是这种情况，则必须显式地修改所发现的WF-网以包含所需的数据相关约束。 最后，我们想指出，玩“代币游戏”的简单想法通过明确地建模过程。然而，考虑到系统和过程的演化性质，α算法是保持“安全过程”最新的有用工具。例如，如果审计线索生源地选择产品进入结算页面提供密码工艺订单完成签出取消订单填写付款信息继续购物填写送货信息Remove from篮子进入添加到购物篮18W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3yz→事件，则可以将其添加到α算法使用的事件日志中。可以从日志中删除看起来不错但被证明是潜在安全漏洞的审计跟踪。通过将α算法应用于修改后的事件日志，可以获得新的和更新的5检查过程一致性排序关系可用于检查系统属性。 在第4节中，从可接受的审计跟踪中导出过程模型。然后，发现的网络用于检查新的审计跟踪。在这种情况下，每个审计跟踪都必须符合流程。但是，有时安全性仅适用于流程的一部分。例如，对于图4中的流程，关键的安全问题是执行任务“在处理订单之前提供密码”。换句话说，任务“提供密码”应该导致任务“处理顺序”。这种情况的 流 程 片 段 是 图 5 中 的 构 造 （ a ） 。 这 个 构 造 被 映 射 到 排 序 关 系ProvidePasswordProcessOrder。因此，给定一个审计日志，我们可以检查这种模式是否适用于系统。也就是说，考虑到所有的审计跟踪，我们检查是否与期望的模式等价的排序关系保持。 回到我们在第4节中的例子 ， 考 虑 审 计 日 志 W=W OKW NOK ， 我 们 确 实 推 断 出 关 系 式 ProvidePassword→WProcess Order。因此，我们可以得出结论，W描述的过程包含图5（a）所示的模式。X yx y，xz，和y||zx y、x z和y#zx z，y z，和x|| yx z，y z，x #y图五. 将基于对数的关系>W、→W、CNOW和#W与基本的Petri网结构相关联。检查流程一致性的方法验证了模式是否成立，但并不保证总是如此。完全一致性可以通过将这种方法与第4节中的方法相结合来验证。 不同之处在于，我们现在与子网玩通过以所需模式播放每个事件跟踪，我们检查Provide Password和Process Order之间是否始终存在因果关系。请注意，并非所有情况Xy（一（b）yXzXzy（d）X（c）Xzy（五W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）319在W中的轨迹和异常的轨迹将被检测到。 检查流程一致性的方法的主要优点是，它不需要整个流程的完整审计日志，而只需要模式中涉及的任务的审计日志。图5展示了可用于构建流程片段的基本模式。6相关工作流程挖掘的思想并不新鲜[2，5，7，8，13，23，24，26，29，33，36]，大多数技术都是针对控制流程的观点。然而，流程挖掘并不局限于控制流程的视角.例如，在[4]中，我们使用过程挖掘技术来构建社交网络。有关流程挖掘的更多信息，请参阅《工业计算机》关于流程挖掘的特刊[6]和一篇调查论文[5]。不幸的是，在本文件中，不可能公正地评价在这方面所做的工作本文的重点是α-算法。有关算法的更多信息，请参阅[2，7，26，36]。在[27]中，[26]中提出的一个问题在安全领域，有相关的论文涉及基于审计跟踪的入侵检测[19，37]。这些文件将“正常行为”分解为更小的模式，然后使用这些模式比较实际的审计跟踪。注意，与α算法不同，这些方法不考虑显式过程模型。已经有许多正式的安全方法，例如，使用Petri网或进程代数[17，18]。与我们的方法不同，他们通常专注于设计的验证，而不是分析实际行为。为了支持我们的采矿业，我们开发了一套工具，包括EMiT [2]，Thumb[36]和MinSoN [4]。这些工具共享一个通用的XML格式。欲了解更多详情，请访问www.processmining.org。7结论本文探讨了进程挖掘技术在安全领域的应用。首先，我们介绍了流程挖掘，然后我们重点介绍了一种算法来挖掘过程的角度。然后我们展示了该算法在安全问题中的应用首先，我们讨论了在挖掘工作流网络的然后，我们证明了可以通过将进程片段与发现的WF-网进行比较来检查进程一致性我们想强调的是，我们认为α-20W.M.P. van der Aalst，又名de Medeiros/Electron.注意Theor。Comput. Sci. 121（2005）3任何安全级别的算法，即，从低级入侵检测到高级欺诈呈现。对公司治理和政府法规（如萨班斯-奥克斯利法案）的关注引发了在业务流程层面实施和检查安全性的工具的开发。 我们认为，组织将越来越需要存储和监控审计跟踪。流程挖掘技术，如α算法，可以帮助这些工作。引用[1] 范德阿尔斯特Petri网在工作流管理中的应用。电路、系统与计算机杂志，8（1）：21[2] W. M. P. van der Aalst和B. F. 范东恩。 从时间序列中发现工作流绩效模型。 耶氏酵母中 汉，S.Tai和D. Wikarski，编者，合作信息系统工程与部署国际会议（EDCIS 2002），计算机科学讲义第2480卷，第45-63页。Springer-Verlag，柏林，2002年。[3] W. M. P. van der Aalst和K. M.范熙。工作流程管理：模型，方法和系统。麻省理工学院出版社，马萨诸塞州剑桥，2002年。[4] 范德阿尔斯特和M.歌 挖掘社交网络：揭示业务流程中的交互模式。In M.韦斯克湾Pernici和J.Desel，编辑，业务流程管理国际会议（BPM 2004），计算机科学讲义，施普林格出版社，柏林，2004年。[5] W.M.P. van der Aalst，B.F.范东根，J.赫布斯特，L.马拉斯特湾Schimm和A.J.M.M. 魏特斯工作流程挖掘：问题和方法的调查。数据与知识工程，47（2）：237[6] 范德阿尔斯特和阿杰默德. Weijters，编辑. 过程挖掘，工业计算机专刊，第53卷，第3期。ElsevierScience Publishers，Amsterdam，2004.[7] 范德阿尔斯特Weijters和L.马鲁斯特工作流程挖掘：从事件挖掘中发现流程模型。昆士兰科技大学技术报告，FIT-TR-2003-03，昆士兰科技大学，布里斯班，2003年。（已接受在IEEETransactions on Knowledge and Data Engineering上发表）。[8] R. Agrawal，D. Gunopulos和F.莱曼 从工作流中挖掘过程模型。在第六届扩展数据库技术国际会议，第469-483页[9] A.A.巴韦拉斯群结构的数学模型。Human Organization，7：16[10] H.R.伯纳德警察局基尔沃思角McCarty，GA. Shelley和S.罗宾逊四种不同的个人社交网络测量方法的比较。社交网络，12：179[11] M.主教 计算机安全：艺术与科学 Addison-Wesley，波士顿，美国，2003年。[12] R.S. Burt和M. Minor. 应用网络分析：方法论导论。Sage，Newbury Park CA，1983年。[13] J.E.库克和A·L·沃尔夫 从基于事件的数据中发现软件过程模型。ACM软件工程与方法学报，7（3）：215[14] J. Desel 和 J. Esparza 。 Free Choice Petri Nets ， Cambridge Tracts in Theoretical ComputerScience第40卷。剑桥大学出版社，剑桥，英国，1995年。W.M.P. van der Aalst，又
