《Information and Software Technology》:A first and fast symbolic approach for data-aware business process compliance checking
编辑推荐:
现有最先进的设计时合规性检查技术通常局限于验证控制流关系。在本文中,研究人员提出了一种算法,用于验证包括数据的业务流程模型的设计时合规性。为了真实反映现实世界案例,研究人员在活动结果中引入了一定程度的不确定性,使得单次执行不能保证导致唯一的数据状态。研究人员使
现有最先进的设计时合规性检查技术通常局限于验证控制流关系。在本文中,研究人员提出了一种算法,用于验证包括数据的业务流程模型的设计时合规性。为了真实反映现实世界案例,研究人员在活动结果中引入了一定程度的不确定性,使得单次执行不能保证导致唯一的数据状态。研究人员使用条件义务(conditional obligations)来表示合规性要求。所提出的方法采用符号化表示(symbolic representation)来紧凑地表示执行过程中可能的数据状态,并将其评估为约束满足问题(Constraint Satisfaction Problem,CSP),首先剪枝不需要进一步分析的路径的状态空间,最后评估执行是否违反了某一法规要求。将该方法的性能与NuXMV中实现的现有算法进行了评估。结果表明,研究人员的方法在各个方面显著优于现有算法。
**论文解读:面向数据感知业务流程合规性检查的首个快速符号化方法**
**研究背景与问题**
业务流程模型常作为业务执行的蓝图,需验证其设计是否合规于法规、业务规则及组织间要求。然而,现有设计时合规性检查技术主要局限于控制流关系验证,缺乏对数据视角的全面考量。由于设计时无法获取运行实例产生的实际数据,传统方法无法纳入数据值随活动序列演化的可能性,也无法涵盖数据赋值中的不确定性(包括未预见的变量变化)。因此,设计时合规性只能作为预防措施,无法保证完全合规。为克服这一局限,需开发一种能够同时处理数据演化与不确定性、且能高效验证全部执行路径的方法。
**研究内容与结论**
本文提出一种新颖的符号化方法,用于验证包含数据视角及活动结果不确定性的业务流程模型的完全合规性。研究人员将法规要求形式化为条件义务(conditional obligations),包括触发条件、要求条件和截止条件,并基于数据Petri网(Data Petri Nets,DPNs)建模过程行为。该方法通过递归的约束满足问题(Constraint Satisfaction Problem,CSP)求解,首先剪枝不可行路径的状态空间,进而评估是否存在违反义务的执行。实验采用SAP参考模型数据集中的三个模型,与NuXMV中的三种无限状态线性时序逻辑验证算法(Bounded Model Checking、incremental Simple Bounded Model Checking、Incremental Counterexample-Guided Abstraction Refinement)进行性能对比。结果表明,所提方法在几乎所有场景下显著优于现有算法,尤其在非合规情况下能快速检测失败。该论文发表在《Information and Software Technology》。
**主要关键技术方法**
研究人员采用以下关键技术:(1)符号化状态表示:通过演化表达式(evolution expressions)跟踪变量值的历史依赖,避免枚举所有数据路径;(2)约束满足问题(CSP)求解:使用维护弧一致性算法(MAC-3)将每个执行-义务对转化为一系列CSP,验证分支可行性及义务满足性;(3)分析树分支策略:基于义务生命周期状态(不活跃、活跃/未知、满足、违反)进行最多三路分支,剪枝无效路径。样本模型选自SAP R/3参考模型数据集(494个模型,从中选取3个不同规模与复杂度的模型)。
**研究结果**
- **与NuXMV的对比(第6节)**:通过三组实验(完全合规与非合规场景),对比了所提方法(原始执行版本与共享前缀优化版本)与NuXMV中ic3、bmc、sbmc_inc三种算法。结果显示,在完全合规实验中,共享前缀方法在大多数情况下优于所有NuXMV算法;在非合规实验中,所提方法因能快速找到违反路径而显著更快。仅当分析树密集且变量域增大时,ic3在完全合规输入上表现略优。
- **账户创建示例(第6.4节)**:针对图2的DPN与表2的义务,完全合规场景下共享前缀方法耗时257 ms,优于NuXMV的ic3(5225 ms)、bmc(2542 ms)和sbmc_inc(750 ms)。非合规变体下,共享前缀方法耗时198 ms,仍显著快于其他算法。此外,共享前缀方法能自动处理有界循环,无需预设循环迭代上限。
- **计算复杂度(第5.8节)**:单次执行-义务对的上界复杂度为O(3
l × l × u
w),其中l为最大执行长度,u为最大不确定性,w为写操作数量。整体模型评估复杂度为O(e × o × 3
l × l × u
w),其中e为执行数,o为义务数。
**讨论与结论**
本文提出的问题比现有文献中命题式问题更具表达力,原因在于:(1) 执行状态与义务表示不限于布尔谓词;(2) 模型转移结果存在不确定性;(3) 法规条件可使用一阶谓词。与通用符号模型验证(SMV)方法相比,所提方法利用预定义的义务自动机(图3)进行路径导向分析,避免即时构建属性自动机与同步系统的开销,且分支数上限为每步3路,优于线性时序逻辑(LTL)属性可能导致的指数级分支。实验表明,该方法在现实复杂案例中可在合理时间内得出合规性结论。研究结论部分(第7节)翻译如下:本文提出了一种业务流程模型合规性检查问题,支持比文献中通常处理的命题式问题更高的表达力。这种额外表达力的结果是问题更复杂,原因有三:(1) 模型执行状态与义务表示不限于布尔谓词;(2) 模型转移执行结果的不确定性;(3) 法规要求条件可使用一阶谓词表示。验证带数据的流程的完全合规性已知是困难的。尽管存在针对实际场景缩减初始状态空间的优化技术,数据的不确定性给验证算法增加了额外层复杂度,因为单次执行可能导致组合数量的分支来表示每种可能场景。本文提出了一种解决方案,通过符号化探索模型执行,将每个执行和义务转化为一系列约束满足问题。虽然符号模型验证(SMV)中有处理这些特征的技术,但应用通用SMV方法进行合规性检查存在若干效率问题。我们的方法以路径导向方式分析自动机,通过探索符号执行树,适用于程序化(具有显式源/汇状态)的流程模型,并可融入现有分支模型探索的优化。性能评估表明,我们的方法在几乎所有场景下显著优于现有算法。对于非合规情况,我们的方法能快速检测合规失败。通过这套基于真实过程结构设计的实验,我们的评估实证表明,对于大多数复杂而精细的现实案例,合规性设计通常可在合理时间内计算得出。本文提出了初步方法,并指出了未来工作方向,包括更优的CSP求解器、减少并发模型执行路径的优化、支持用户输入字符串等变量类型,以及扩展其他法规概念(如及时义务或持续义务)和循环处理。