💻 computer science

Runtime Verification: Monitoring, Knowledge, and Uncertainty (Lecture Notes)

本讲义阐述了运行时验证的自动机理论、时序逻辑与认识论基础，涵盖规范形式化方法、诊断、不透明性与可监控性，以阐释离线分析如何为部分可观测系统构建监视器，同时探讨实时环境中时序扩展所面临的挑战。

原作者： Benedikt Bollig

发布于 2026-04-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Benedikt Bollig

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

想象一下，你正在试图判断一台神秘的机器是否正常工作。你无法看到机器内部（它是一个“黑盒”），也无法停下来将其拆解。你只能观察从它内部流出的东西：一串灯光、声音或数据点。

这就是运行时验证（Runtime Verification）的世界。与其在机器启动前试图预测它可能做的每一件事（这就像在进入迷宫前试图绘制出所有可能的路径），运行时验证是在机器运行时观察它，一旦发现异常便发出警报。

本讲座系列由 Benedikt Bollig 主讲，探讨了在存在不确定性的情况下如何进行运行时验证。也许机器隐藏了某些动作，或者你并不确切知道它是如何工作的。笔记使用一种特殊的逻辑（称为“认识逻辑”）来精确追踪观察者在任何给定时刻知道什么以及不知道什么。

以下是使用日常类比对主要思想的分解：

1. 了解机器的三个层级

该论文描述了我们与系统交互的三种方式：

白盒：你拥有蓝图。你确切知道每个齿轮如何转动。这就像拥有手册且引擎已打开。你甚至可以在启动机器之前检查它是否会完美运行（模型检测）。
灰盒：你拥有一份模糊的手册。上面写着“也许会发生这个，也许会发生那个”。存在空白。你无法百分之百确定会发生什么，因此必须观察其运行才能确定。
黑盒：你根本没有手册。你只能看到输出。你必须根据所见来猜测内部发生了什么。

2. 三个主要游戏：诊断、不透明性与监控

该论文将三个不同的问题视为同一游戏的变体：“我能从所见中推断出什么？”

诊断：侦探

目标：你想知道是否发生了特定的坏事（“故障”）。
类比：想象一名保安在监视银行金库。金库有一个无声警报（故障），没人能听到。保安只能看到人们进出。
- 如果有人走进来，保安不知道他们是否偷了东西。
- 但如果保安看到有人带着一袋金子走出来，他们就能确定盗窃发生了。
- 诊断是指能够断言“我百分之百确定盗窃发生了”，即使你没有亲眼看到盗窃本身，只看到了后果。论文问道：保安最终是否总能弄清楚这一点？

不透明性：间谍

目标：你想要隐藏一个秘密。你想要确保观察者永远不知道秘密是否发生。
类比：想象一名间谍试图将秘密信息偷偷带入一个房间。观察者在监视门口。
- 如果间谍进入，观察者看到“有人进入了”。
- 如果普通人进入，观察者看到的也是“有人进入了”。
- 不透明性是一门艺术，旨在让间谍的进入看起来与普通人完全一样。如果观察者永远无法区分，该秘密就是“不透明”的（隐藏的）。论文问道：是否有可能设计一个系统，使间谍的秘密始终被隐藏？

监控：交警

目标：对系统行为在发生过程中给出裁决。
类比：一名交警在观察一辆汽车。
- 裁决“真”：汽车行驶完美。交警知道它永远不会撞车。
- 裁决“假”：汽车刚刚闯了红灯。交警知道它违反了规则。
- 裁决“？”：汽车目前行驶正常，但它可能在 5 秒后闯红灯。交警还不确定。
- 论文探讨了交警何时能停止说“？”，转而说“真”或“假”。有时，无论观察多久，你都无法确定（裁决保持为“？”）。

3. “知识”问题

论文的核心在于，不确定性是主要的敌人。

如果你看到一盏灯闪烁，你知道这意味着“错误”还是仅仅意味着“系统检查”吗？
论文使用认识逻辑（关于知识的逻辑）来描绘这一点。它将观察者的心智视为一张地图。
- 如果地图上只显示一条可能的路径，观察者就知道真相。
- 如果地图显示两条路径（一条包含错误，一条不包含），观察者就不确定。

4. 转折：时间改变了一切

最后一章将时间加入其中。想象这台机器不仅仅是做事，而是以特定的速度做事。

没有时间：如果你等待足够长的时间，你可能会弄清楚真相。
有时间：事情变得混乱。
- 诊断：你可能需要在5 秒内知道错误发生了。如果系统很慢，你可能会错过确认的时间窗口。
- 不透明性：如果事件的时间安排暴露了秘密，隐藏秘密就会变得更加困难。
- 最大的坏消息：论文揭示了一个可怕的极限。在时间世界中，如果你试图将“检查时钟”与“弄清楚观察者知道什么”结合起来，数学就会崩溃。这变得不可判定。这意味着没有任何算法能始终告诉你一个带时间的系统是否安全或不透明。这就像试图解决一个拼图，而当你看着它们时，拼图块却在不断改变形状。

总结

这篇论文是构建复杂系统“智能观察者”的指南。

它教导我们如何构建即使在无法看到一切时也能工作的诊断器（侦探）和监控器（交警）。
它表明诊断（发现故障）和不透明性（隐藏秘密）是同一枚硬币的两面。
它证明，虽然我们可以为简单系统解决这些谜题，但加入时间会使其中一些谜题变得无法完美解决。

最终的启示是：在一个信息部分缺失的世界里，我们无法总是立即知道真相。我们必须明智地对待我们能知道什么、我们何时能知道，以及何时我们必须接受我们永远无法知道。

技术摘要：运行时验证、监控、知识与不确定性

1. 问题陈述

运行时验证（RV）是一种轻量级验证技术，旨在分析系统执行过程，而非像模型检测那样离线探索完整的系统模型。这些讲义所解决的核心挑战是源于以下方面的不确定性：

部分可观测性：观察者（代理）通常无法看到所有系统动作或内部状态（黑盒或灰盒系统）。
无限执行：系统是反应式的，产生无限轨迹，但在运行时，仅能获得有限前缀。
认知局限：观察者仅凭观测到的历史，可能无法确定某个属性是否成立、是否曾成立或将来是否成立。

本文旨在利用认知时序逻辑，为三个不同但相关的验证问题——诊断（检测故障）、不透明性（隐藏秘密）和监控（验证属性）——提供一个统一框架。文章进一步探讨了这些概念如何扩展到**实时（带时）**系统，其中时间和认知算子的引入带来了显著的算法挑战。

2. 方法论

作者采用基于**认知线性时序逻辑（LTL $\sim$ ）**的形式化、自动机理论方法。

2.1 形式化框架

系统模型：系统被建模为** Büchi 自动机**（针对无限词）或带时 Büchi 自动机（针对实时系统）。
观测：代理根据可观测命题的子集（ $AP_a \subseteq AP$ ）观测全局执行轨迹的投影。不可区分性（ $\sim_a$ ）通过观测序列的完美回忆来定义。
逻辑：该逻辑在标准 LTL 基础上扩展了：
- 认知算子： $K_a \phi$ （“代理 $a$ 知道 $\phi$ "）。
- 时序算子：严格未来（ $U^+$ ）和过去（ $S^+$ ）算子，允许对轨迹中的特定位置进行推理。
- 认知语义：如果在所有与当前观测不可区分的执行中 $\phi$ 均为真，则 $K_a \phi$ 在该点成立。

2.2 核心机制

认知监控器：文章构建了确定性有限自动机（DFA）（或 Moore 机），用于跟踪与观测历史一致的可能系统状态集合（信念状态）。这些监控器根据属性是否已知为真、为假或不确定来输出裁决。
转换器：为了解决模型检测问题，作者构建了**（系统，公式）转换器**。这些自动机与系统并行运行，在每一步输出公式的真值。
双生植物构造（Twin-Plant Constructions）：针对可诊断性，该方法涉及并行模拟两个系统运行（一个故障，一个无故障），以检查它们在超过一定延迟后是否仍保持观测上的不可区分性。

3. 主要贡献

3.1 验证问题的统一

文章证明，诊断、不透明性和监控可以在同一系统模型上统一表达为认知时序属性：

诊断： $G(\text{fault} \to F K_a \text{Past}(\text{fault}))$ 。代理最终会知道故障发生过。
不透明性： $G \neg K_a \text{Past}(\text{secret})$ 。代理永远不会知道秘密发生过。
监控：基于 $K_a \hat{\phi}$ 、 $K_a \neg \hat{\phi}$ 或两者皆非导出的三值裁决系统（真、假、？）。

3.2 算法结果（非带时设定）

可判定性：LTL $\sim$ 的模型检测是可判定的。认知监控器的构建使得可诊断性和不透明性的有效验证成为可能。
复杂度：
- 标准 LTL 模型检测是 PSPACE 完全的。
- 由于完美回忆下信念状态所需的迭代幂集构造，添加认知算子会导致非初等复杂度的爆炸。
- 可诊断性（检查系统是否可诊断）尽管一般逻辑更复杂，但在有界延迟下可在多项式时间（P）内判定。
- 不透明性被证明是PSPACE 完全的。

3.3 可监控性

文章将可监控性定义为一种结构属性，确保对于每个观测前缀，都存在一个导致明确裁决的有限延续。

安全性与共安全性：证明了这些经典类别是可监控的。
一般 LTL：可监控性是可判定的，但是 PSPACE 难的。可监控公式的类严格包含安全性/共安全性，但又是所有 LTL 的真子集。

3.4 带时系统（实时）

最后一章将理论扩展到带时自动机和带时时序逻辑（TLTL）。

带时模型检测的可判定性：对于 TLTL（不含认知）是可判定的，使用区域抽象。
认知带时逻辑的不可判定性：将认知算子添加到带时逻辑（ $TLTL\sim$ ）中使得模型检测变为不可判定。这是通过从带时自动机的通用性问题归约证明的。
带时不透明性：因此，带时不透明性是不可判定的。
带时可监控性：
- 过去片段：仅含过去公式的带时可监控性是可判定的。
- 全 TLTL：由带时自动机定义的语言的可监控性是不可判定的。

4. 关键结果摘要

问题	设定	复杂度 / 状态	关键洞察
模型检测	非带时 (LTL $\sim$ )	可判定 (非初等)	认知算子导致信念状态爆炸。
可诊断性	非带时 (有界)	多项式时间	归约为“双生植物”乘积中的可达性问题。
不透明性	非带时	PSPACE 完全	等价于 NFA 的通用性问题。
可监控性	非带时	可判定 (PSPACE 难)	结构属性；安全性/共安全性是充分但非必要条件。
模型检测	带时 (TLTL)	可判定	使用区域抽象；过去算子比未来算子更容易。
模型检测	带时 (TLTL $\sim$ )	不可判定	知识 + 时间 = 不可判定（从带时通用性归约）。
不透明性	带时	不可判定	认知带时逻辑不可判定的直接后果。
可监控性	带时 (过去)	可判定	可通过确定性带时自动机构建。
可监控性	带时 (一般)	不可判定	即使对于由带时自动机定义的语言也是如此。

5. 意义与影响

理论统一：文章利用认知逻辑作为共同的语义基础，成功弥合了离散事件系统理论（诊断/不透明性）与形式化验证（模型检测/监控）之间的鸿沟。这阐明了“检测故障”与“隐藏秘密”作为知识双重问题的关系。
复杂度的澄清：它精确划定了可处理问题与不可处理问题之间的界限。虽然诊断在实践中通常高效（多项式时间），但一般的认知模型检测问题计算成本高昂。
“知识 + 时间”障碍：一个关键贡献是证明，虽然带时验证在孤立情况下是可判定的，但实时约束与认知推理（知识）的结合会导致不可判定性。这为部分可观测实时系统中可自动验证的内容设定了硬性限制。
实际监控器构建：构造性证明提供了构建运行时监控器（Moore 机）和诊断器（DTA）的算法。这些不仅仅是理论存在性证明，而是实施蓝图，处理了从离线分析到在线执行的过渡。
处理不确定性：通过不可区分性关系将“不确定性”形式化，这些讲义提供了一种严格的方法，用于推理观察者能和不能知道什么，这对于复杂部分可观测系统中的安全性（不透明性）和可靠性（诊断）至关重要。

总之，这些讲义建立了一个在不确定性下进行运行时验证的综合理论框架，既突出了认知逻辑统一多样化验证任务的能力，也揭示了结合时间与知识所带来的根本性算法限制。