基于 Rocq 的 Strand 空间偏序语义与操作语义

《Journal of Logical and Algebraic Methods in Programming》:Partial Order Semantics and Operational Semantics for Strand Spaces, via Rocq

【字体: 大 中 小 】 时间:2026年09月29日 来源:Journal of Logical and Algebraic Methods in Programming 1.0

编辑推荐:

   我们给出了归纳bundle定义,等价于原始bundle定义。 我们为 strand spaces 提供了操作语义。 我们证明了操作历史和bundles可以互相生成。 我们在 StrandsRocq 中形式化了类似 CPSA 的协议语法及其语义。 所有结果均使用 Rocq 中的

  

我们给出了归纳bundle定义,等价于原始bundle定义。
我们为 strand spaces 提供了操作语义。
我们证明了操作历史和bundles可以互相生成。
我们在 StrandsRocq 中形式化了类似 CPSA 的协议语法及其语义。
所有结果均使用 Rocq 中的 StrandsRocq 框架完全机械化实现。

引言

安全协议是分布式活动,其中参与者通过消息交互来建立认证、保密性及其他目标。虽然某些事件可能在因果上相互独立,但其他事件则表现出因果依赖。例如,消息的接收在因果上依赖于使该消息可用的发送;否则接收事件不可能发生。类似地,当协议合规的参与者在某个会话中执行一步操作时,这依赖于协议所定义的任何前序步骤;否则合规的参与者将不会准备好执行该步。

然而,这种因果依赖的排序是一个偏序。对于许多事件对,彼此都不依赖于对方,这些事件可以以任意顺序发生。例如,一个服务器可能要求两个参与者都发送消息后才能提供服务,而对哪个消息先发送保持中立。在异步网络模型中,服务器甚至可能无法确定哪个消息先发送。因此,为协议会话做出贡献的事件在因果上可能仍不可比较。因此,偏序语义是对安全协议基本语义的自然建模选择,并尊重了其固有的并发结构。

偏序语义在分析协议时也是实用可取的。如果要系统地探索其可能的执行过程,将因果无关事件以不同顺序出现的不相关交错折叠为一个称为 bundle 的结构是更高效的做法——该结构仅表示因果偏序。

另一方面,人们也希望能以系统化的方式逐步生成执行过程,这需要一种事件按顺序发生的操作语义。

本文的目标是连接安全协议行为的这两种语义观点。具体而言,我们证明了操作语义的每次执行都确定一个 bundle(定理 4)。反之,每个 bundle 都可以在结构化操作语义中逐步生成(定理 5)。确实,除非事件 e2 在 bundle 中因果先于另一个事件 e1,否则存在一种结构化操作语义的运行,其中 e1 在 e2 之前发生(定理 6)。因此,bundle 准确总结了操作语义运行的排序约束。

除了调和不同的语义观点之外,本文还向语法集成迈出了步伐。我们展示了密码协议形状分析器(Cryptographic Protocol Shapes Analyzer, CPSA)[1] 规范中使用的语法如何自然地嵌入 StrandsRocq [2] 并赋予操作语义。这连接了 CPSA 的自动化协议分析与 StrandsRocq 的人工机械化方法,使得之前使用 CPSA 分析的协议可以直接在 StrandsRocq 中进行分析。这样一来,每种工具也可以作为另一种工具的交叉验证工具。这项工作与 ALVIE [3] 具有更广泛的共同目标——连接自动化分析与可信的形式化模型:ALVIE 直接从黑盒实现中学习行为模型,而这里我们连接 CPSA 风格的协议分析与在 Rocq 中机械化验证的显式语义。

我们使用 Rocq 定理证明器基于初始的 StrandsRocq 形式化 [2] 形式化并证明了我们的所有主张。部分辅助引理和证明脚本借助 AI 辅助工具开发,随后由作者在 Rocq 中进行了审查、编辑和检查。

Rocq 系统地区分了命题性质的断言类实体,如公式以及应用于参数后生成公式的谓词,以及值类实体,如具体值以及应用于其参数后生成具体值的函数或高阶实体。Rocq 对后者而非前者支持计算。我们形式化的一个优势在于,我们的结果在分界线两侧均可用。使用计算版本,我们可以提取(线性)运行生成的(偏序)bundle,或者找到生成给定(偏序)bundle 的(线性)运行。

本文不包含的内容:我们将避免讨论如何使用 strand space 理论来证明协议的正确性,因为自 20 世纪 90 年代以来这已经是一系列长期论文的主题,例如 [4]、[5]、[6];新技巧不断被添加 [2]。Strand 思想的一个优势在于它们为协议组合推理提供了强有力的方法 [2]、[7]、[8]、[9],甚至为协议设计提供了良好的启发式方法 [10]。Strands 也得到了很好的机械化实现;CPSA 工具已经完善且可使用 [1],并足够健壮,能够验证具有硬件依赖的复杂协议 [11]。

事实上,本文的额外贡献之一是建立了 CPSA 的语法和方法与 StrandsRocq 理论细节之间的联系(第 4 节);这种联系创造了在 StrandsRocq 中机械化验证 CPSA 所执行步骤的机会,或者在 StrandsRocq 中生成协议特定的引理以证明 CPSA 在剪枝其搜索时的合理性。

产物可用性:本文所附产物,包括所有 Rocq 证明和形式化,已归档于 Zenodo,永久 DOI 为 https://doi.org/10.5281/zenodo.22939512。

致 Giangi!我们热切感谢 Giangi 在皮萨语义学派中所帮助编织的语义传统,从并发和移动性到进程演算和全球计算。本文通过多条 strand 与这一传统相连:通过 Flaminia 的皮萨根源、Matteo 来自皮萨的导师、Riccardo 经由博洛尼亚来自皮萨的导师传承,以及 Joshua 对 Giangi 在皮萨访问时的美好回忆。

章节片段

背景

本节提供了一些示例,以及对核心 strand space 概念的初步描述。

Bundle 的形式化

我们在 StrandsRocq 中直接形式化定义 2。2 该定义涉及一个三元组 ?=(??,→,?),其中 →,????×??;形式化通过一个具有三个组件的 bundle_type 记录类型来表示:一个节点列表、一个通信边列表 inter 和一个 strand 后继边列表 intra。我们经常通过 Rocq 的 ListSet 接口访问它们,这简化了使用列表来表示有限集合。谓词 is_bundle 随后描述了当元素为

协议

直到目前为止,我们都是在任意给定的 strand space 的相对下工作的。从这里开始,我们将考虑如何定义 strand space 以匹配在主动对抗者存在下特定协议中可能发生的情况。然后在第 5 节中,我们将提供一个结构化操作语义,用于推导给定协议的可能执行历史。第 6 节随后表明这些执行历史恰好代表了该协议 strand space 上的 bundles。

一个操作语义

在上节中,我们提供了接近 CPSA 的语法来指定协议,并描述了其含义。我们现在引入协议 P 的操作语义。7 协议 P 决定了哪些 ground traces 与该协议兼容,如 ??????? 所表达的。由于语义中的每个转换要么向现有 trace 附加一个事件,要么"生成"一个新的,我们的操作语义记录了事件

语义正确性

我们现在陈述关于操作语义与 bundle 语义的语义对应定理。在一个方向上,每个可达的 pool 产生一个归纳 bundle,代表 pool 中的事件。在另一个方向上,每个协议兼容的归纳 bundle 都可以通过操作语义生成。第 7 节然后从计算上细化这种对应关系,添加使构造在 Rocq 中可执行所需的见证。

计算标签语义

图 5 中的规则属于 Prop,即 Rocq 的命题宇宙,正如数学事实通常归属的那样。然而,为防止非预定性产生如 Girard 悖论 [19]、[20] 之类的矛盾,Rocq 限制了对这些关系证明项的消去,使得无法例如对操作语义中的推导进行模式匹配并利用提取的信息进行计算。9

实例:并发 Yahalom 协议

我们通过图 3 中并发 Yahalom 协议执行的推导结果来结束技术部分。该示例的目的不是重新分析 Yahalom,而是展示前面几节中引入的对象如何为一个具有多条 strand 和多个独立操作的协议组合在一起。

相关工作

Strand spaces 及其与其他形式化方法的关系 Strand spaces 最初由 Thayer 等人 [4] 作为协议分析的象征框架引入。Strand spaces 此后成为多项研究的主题,并在多个方向上进行了扩展,包括例如 [11]、[21]、[22]、[23]、[24]、[25]、[26]。特别是,Guttman 和 Thayer 用 skeletons、shapes 和认证检验原则扩展了 strand spaces 框架 [5]、[27],使得自动化协议

一些反思

在本文中我们研究了协议语义的两种方法。一种是因果的,另一种是操作语义。为了理解因果方法,我们从标准 strand space 执行模型的直接形式化——即 bundle——开始。它配备了一个由因果依赖生成的偏序,每个因果依赖要么是同一 strand 上节点对其直接前驱的依赖,要么是接收对较早节点的依赖,该节点

生成性 AI 和 AI 辅助技术在论文准备过程中的声明

在本工作准备过程中,作者使用了 OpenAI 的 Codex 和 Anthropic 的 Claude 来协助查找 Rocq 证明的部分以及起草论文某些章节的早期版本。所有证明均由 Rocq 检查。作者对所有 AI 生成的文本进行了彻底重写,并对已发表的文章承担全部责任。

CRediT 作者贡献声明

Matteo Busi:撰写–审阅与编辑,撰写–原稿,验证,软件,方法论,调查,形式分析,概念化。Riccardo Focardi:撰写–审阅与编辑,撰写–原稿,验证,软件,方法论,调查,形式分析,概念化。Joshua Guttman:撰写–审阅与编辑,撰写–原稿,验证,软件,方法论,调查,形式分析,概念化。Flaminia Luccio:撰写–

利益冲突声明

作者声明不存在已知的竞争经济利益或个人关系可能影响本文所报告的工作。

Matteo Busi | Riccardo Focardi | Joshua Guttman | Flaminia Luccio
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号