💻 computer science

A Privacy-Preserving Approach to Conformance Checking

本文提出了一种利用同态加密和字符串处理算法的隐私保护合规性检查方法，能够在不向对方泄露过程模型或事件日志的前提下安全地识别两者之间的差异，尽管其代价是较高的计算和内存需求。

原作者： Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

发布于 2026-05-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是用通俗语言和日常类比对该论文的解读。

宏观视角：在不查看食材的情况下检查食谱

想象你是一位订购了定制蛋糕的顾客。你想确保面包师遵循了你的特定食谱（即过程模型），并且他们在厨房实际执行的步骤与你要求的一致（即事件日志）。

通常，为了检查这一点，面包师必须向你展示他们的秘密食谱书，而你也必须向他们展示你的秘密订单表。但如果面包师担心你会窃取他们的秘密食谱，或者你担心他们会看到你的秘密订单详情，该怎么办呢？

本文提出了一种方法，可以在双方都不查看对方秘密信息的情况下，检查蛋糕是否被正确制作。

问题：隐私与检查的冲突

在商业软件领域，“一致性检查”（Conformance Checking）是将计划的工作流程（如食谱）与实际发生记录（如厨房日志）进行比对的过程。

模型：“预期”路径（食谱）。
日志：“实际”路径（厨师实际所做的操作）。

传统上，由第三方（或数据所有者）同时查看两者以发现错误。但在敏感行业（如高科技制造），公司不愿分享其秘密蓝图，客户也不愿分享其私人订单详情。

解决方案：“魔法盒”与“搜索引擎”

作者创建了一个系统，利用两种主要工具来解决这个隐私难题：

1. 魔法盒（同态加密）

将同态加密想象成一个特殊的“魔法盒”。

你可以将一个秘密数字放入盒中。
你可以要求某人在不打开盒子或看不到数字的情况下，将该数字加 5。
他们在盒内对“加密”后的数字执行数学运算，然后将结果交还给你。
当你打开盒子时，得到的结果是正确答案（原始数字 + 5）。

在本文中，“客户端”（拥有轨迹数据的人）将数据放入这个魔法盒中。“服务端”（模型的所有者）在盒内执行检查计算，而无需看到实际数据。

2. 搜索引擎（FM-Index 与字符串处理）

为了检查步骤是否匹配，系统将整个过程模型转换为一个巨大的文本字符串（就像将食谱变成一句长句）。然后，它在该文本之上构建了一个超快速的搜索引擎（称为FM-Index）。

通常，搜索引擎允许你输入一个单词并立即找到它在文本中出现的位置。在这里，系统利用该搜索引擎来查看客户端日志中的“步骤”是否存在于模型的文本“步骤”中。

工作原理：“向后搜索”游戏

本文描述了客户端与服务端之间进行的一场特定游戏，以检查匹配情况：

准备：服务端将其秘密模型转换为一个长文本字符串，并在此基础上构建搜索引擎（FM-Index）。他们对此保密。
查询：客户端拥有一个秘密的步骤列表（轨迹）。他们想知道这些步骤是否符合模型。
秘密搜索：
- 客户端从后往前查看其步骤列表（从最后一步到第一步）。
- 客户端不直接发送步骤，而是向服务端发送一个“锁定”的请求。
- 服务端利用搜索引擎在模型中查找该步骤。
- 关键点：服务端在“魔法盒”内执行此数学运算。服务端只能看到乱码数字，看不到实际的步骤名称。
- 服务端将结果返回给客户端。
- 客户端解锁结果，查看该步骤是否被找到。
处理错误（日志移动）：如果客户端列表中的某一步骤与模型不匹配，系统允许“跳过”（称为日志移动）。这就像说：“好吧，这一步不在食谱中，但让我们看看下一步是否匹配。”系统会记住出错前的位置，以便在不向服务端泄露错误的情况下再次尝试。

代价：速度慢且占用资源大

论文承认，虽然这是一个出色的隐私解决方案，但它付出了沉重的代价：速度与内存。

类比：想象在一张纸上做一个简单的数学题，只需一秒钟。现在想象你必须把这张纸放进一个铅衬保险箱，寄给朋友，让他们透过厚厚的玻璃窗做数学题，然后再寄回来。这需要更长的时间。
结果：作者在真实和伪造数据上测试了该系统。他们发现，检查一个过程大约需要每条轨迹1.12 分钟。虽然准确，但比无加密检查要慢得多。“魔法盒”（加密）需要大量的计算能力和内存。

主张总结

他们做了什么：他们构建了一个系统，用于检查过程日志是否与过程模型匹配，而无需任何一方查看对方的数据。
他们是如何做到的：通过将快速的文本搜索算法（FM-Index）与“魔法盒”加密方法（同态加密）相结合。
他们发现了什么：它有效！你可以安全地检查不匹配项。
局限性：由于加密数学运算繁重，目前速度非常慢且占用大量内存。此外，它目前仅处理“日志移动”（跳过日志中的步骤），尚未处理“模型移动”（跳过模型中的步骤）。

简而言之，该论文证明了可以在不泄露任何一方的情况下，将秘密食谱与秘密订单进行比对，但目前执行这些数学运算需要很长时间。

以下是论文《一种隐私保护的合规性检查方法》的详细技术总结。

1. 问题陈述

合规性检查是流程挖掘的核心操作，它将流程模型（预期行为）与事件日志（观测行为）进行对比，以识别差异。传统上，分析师可以访问模型和日志。然而，在敏感场景（如定制制造或专有生产线）中，流程模型所有者必须保护其知识产权，而客户（日志所有者）必须保护其运营数据。

所解决的核心问题是：如何在向日志所有者不泄露模型、也不向模型所有者泄露日志的情况下，对流程模型和事件日志执行合规性检查？

2. 方法论

作者提出了一种基于客户端 - 服务器架构的安全合规性检查技术，利用全同态加密（FHE）和字符串处理算法。

A. 核心概念

Petri 网与展开：流程模型表示为 Petri 网。为了将其转换为适合字符串搜索的格式，作者使用了因果完备前缀展开。这将 Petri 网（由于循环而可能具有无限行为）转换为包含所有可能“运行”（完整执行）的有限无环结构。
字符串表示：展开产生的运行被线性化并连接成单个文本字符串，由特殊分隔符隔开。
FM 索引与反向搜索：连接后的字符串使用FM 索引（基于 Burrows-Wheeler 变换和波瓦矩阵）进行索引。这允许在 $O(m)$ 时间内高效地进行子串搜索（判断某条轨迹是否存在于模型的运行中）。
同态加密（FHE）：系统使用一种公钥加密方案（具体为提升的 ElGamal 方案），允许直接在加密数据上执行计算（加法和乘法）。

B. 安全协议

该方法将寻找最优对齐（最小化偏差）的问题映射为近似子串匹配问题。

服务器端（模型所有者）：
- 接收流程模型，对其进行展开，连接运行，并构建 FM 索引（BWT 和波瓦矩阵）。
- 将索引数据结构（具体为 0-RANK 和 1-SRANK 向量）存储在内存中。
- 不查看客户端的轨迹。
客户端（日志所有者）：
- 持有待检查的事件轨迹。
- 在向服务器发送查询之前，加密轨迹数据和搜索状态（索引）。
交互过程（安全反向搜索）：
- 客户端按逆序遍历轨迹字符。
- 对于每个字符，客户端在 FM 索引上执行反向搜索。这涉及逐行（按位）遍历波瓦矩阵以更新搜索区间 $[f, g]$ 。
- 隐私机制：
  - 客户端发送代表当前搜索索引的加密向量。
  - 服务器基于波瓦矩阵行，执行同态点积和加法来更新这些索引。
  - 为了防止客户端了解中间区间（这可能泄露关于模型的信息），服务器在返回结果之前添加随机偏移量。
- 处理不匹配（日志移动）：
  - 如果轨迹中的某个字符与模型不匹配（即“日志移动”），客户端恢复迭代前存储的先前搜索索引，并在对齐中插入一个“跳过”操作。
  - 此过程是在服务器不知道哪个字符导致不匹配的情况下完成的，因为客户端基于解密（但已混淆）的结果控制逻辑流。

3. 主要贡献

FHE 在合规性检查中的首次应用：该论文声称是首个将同态加密专门应用于合规性检查问题的研究。
通过字符串匹配实现安全对齐：它创新地将复杂的轨迹对齐问题映射为使用 FM 索引的子串匹配，从而能够在加密域中使用高效的字符串算法。
客户端 - 服务器隐私模型：建立了一种协议，其中模型所有者永远看不到轨迹，日志所有者永远看不到模型，但仍可计算对齐分数（以及对齐本身）。
处理日志移动：该算法专门支持“日志移动”（即日志中包含模型中不存在的事件的偏差），通过允许客户端安全地回退搜索状态来实现。

4. 结果与评估

该方法使用 mcl 库在 C++ 中实现同态加密，并在标准笔记本电脑工作站上进行了评估。

数据集：使用一个真实世界的事件日志和两个合成日志（具有并发、选择和循环的小到中等规模）进行评估。
性能：
- 准确性：该方法成功计算了符合模型的轨迹以及注入偏差的轨迹的对齐。
- 开销：主要瓶颈是同态操作的计算成本。
- 复杂度：理论复杂度为 $O(C \cdot |q| \cdot |T|)$ ，其中 $C$ 是加密/解密的大常数， $|q|$ 是轨迹长度， $|T|$ 是索引模型运行的规模。
- 执行时间：对于包含 144 个运行且每条轨迹 9 个事件的小型模型，平均对齐时间为1.12 分钟。每个符号的时间约为 0.11 分钟。
- 可扩展性：执行时间相对于轨迹长度显示出准线性趋势，但由于沉重的加密开销，绝对时间目前对于实时、大规模工业应用来说过高。

5. 意义与未来工作

意义：这项工作弥合了流程挖掘与隐私保护数据挖掘之间的差距。它证明了敏感业务流程可以在不暴露专有逻辑或运营数据的情况下进行审计，这是定制制造和医疗保健等行业的关键要求。
局限性：
- 目前仅支持日志移动（跳过日志中的事件）。它尚不支持模型移动（跳过模型中的事件），这需要更复杂的逻辑。
- 高内存和处理需求使其目前对于非常大的模型或实时系统不切实际。
未来方向：
- 扩展该方法以处理模型移动。
- 改进对循环的处理（目前受限于展开深度）。
- 优化加密实现，以缩小明文执行与加密执行之间的计算差距。

总之，该论文提出了一个理论健全且技术可行的安全合规性检查原型，证明了以大量计算资源为代价可以保护隐私。