探寻一般的 Order-2 CSO

在研究了如何定义一般的 order-2 BGSO 后，我感觉自己在相关方面的了解仍然不足。毕竟，二阶的 BGSO 终究还是比较特殊，于是我想先学习一下一般情况的二阶 opacity. 于是顺藤摸瓜，我找到了这两篇文献：You Don’t Know What I Know: On Notion of High-Order Opacity in Discrete-Event Systems 和 High-order estimation-based properties and high-order observers for labeled finite-state automata.

You Don’t Know What I Know: On Notion of High-Order Opacity in Discrete-Event Systems

这篇文献定义了所谓的 high order opaque. 不过在阅读之后，我发现其中提出的东西，和我想要的东西，依然有不小的差距。（比如这里的 high order 实际上是二阶，而不是一般情况的高阶；以及这里定义的 opaque, 依然是选取了特殊 secret 集合之后的情况，而不是更加一般的情况。不过，由于我只阅读了文献的部分段落，所以不能保证其在后文是否有对更一般的情形进行补充。毕竟我在当时读文献的时候，只是取了自己所需的部分。）

下面，先来看看从文献中摘取的一个定义：

定义（高阶不透明性，High-Order Opacity） 设系统 $G=(X,\Sigma,\delta,x_0)$，用户和入侵者的投影分别为 $P_o$、$P_a$. 用户观察到 $\alpha$ 后的状态估计为

$$\hat X_o(\alpha) = \{\delta(x_0,s)\mid s\in L(G),\ P_o(s)=\alpha\}.$$

给定需要区分的状态对集合

$$T_{\mathrm{spec}}\subseteq X\times X,$$

定义用户“知道”为

$$\operatorname{Know}(\alpha) \iff \bigl(\hat X_o(\alpha)\times\hat X_o(\alpha)\bigr) \cap T_{\mathrm{spec}} =\varnothing.$$

若

$$\forall s\in L(G),\quad \operatorname{Know}(P_o(s)) \Rightarrow \exists t\in L(G): \begin{cases} P_a(t)=P_a(s),\\ \neg\operatorname{Know}(P_o(t)), \end{cases}$$

则称 $G$ 关于 $(T_{\mathrm{spec}},P_a,P_o)$ 是 high-order opaque。

原始定义：Definition 2

以下是我阅读之后的一些思考：

首先，由于 $G$ 是确定性的（deterministic），因此 $\hat X_o(\alpha)$ 是一个当前状态估计集合（可以简称为 CSE(current state estimate)）.

其次，$\forall (x,x')\in T_{\mathrm{spec}}$，$\operatorname{Know}(\alpha)$ 表示 $x$ 与 $x'$ 不会同时出现在 $\hat X_o(\alpha)$ 中。要求两个状态不同时出现在估计中的意义是避免冲突。对于这个定义，可以用一个具体的例子来解释：

例. 若 $x$ 表示刹车状态、$x'$ 表示加速状态，则二者不应同时出现在当前状态估计中。

而在经典的 opacity 问题的框架下考虑，毫无疑问，我们是需要知道此时的秘密集合是什么的。这篇文章也可以看作经典 opacity 问题的一个特例，其中秘密集合规定为

$$\mathcal S =\left\{X'\subseteq X\;\middle|\; (X'\times X')\cap T_{\mathrm{spec}}=\varnothing \right\}.$$

更一般地，可以令 $\mathcal S\subseteq 2^X$。因此，更准确地说，该定义研究的是选定特定秘密集合后的二阶不透明性（second-order opacity）特例。

---

大概读到这里之后，我觉得这篇文献目前所展示的内容不太符合我想要的东西，于是我开始阅读下一篇文献。

High-order estimation-based properties and high-order observers for labeled finite-state automata

定义（二阶当前状态 opacity，Ord2CSO）：给定有限状态自动机 $G$（状态集为 $Q$）、两个观察者 $A_1,A_2$（标记函数分别为 $\ell_1,\ell_2$）及任意秘密知识状态族 $\mathcal S\subseteq2^Q$。定义 $A_2$ 对 $A_1$ 当前状态估计的推断为

$$M_{A_1\leftarrow A_2}(G,\alpha) :=\{M_1(G,\ell_1(s))\mid s\in L(G),\ \ell_2(s)=\alpha\}.$$

若

$$\forall\alpha\in\ell_2(L(G)),\qquad M_{A_1\leftarrow A_2}(G,\alpha)\nsubseteq\mathcal S,$$

则称 $G$ 关于 $A_1,A_2,\mathcal S$ 是二阶当前状态 opaque。等价地，每个 $A_2$ 的观测都必须允许至少一个非秘密的 $A_1$ 当前状态估计：

$$\forall\alpha\in\ell_2(L(G)),\quad \exists X\in M_{A_1\leftarrow A_2}(G,\alpha):\ X\notin\mathcal S.$$

这里 $\mathcal S$ 的元素是状态估计 $X\subseteq Q$，而不是单个系统状态。来源：Zhang et al., §4.3, Definition 16, p. 23。

如何理解 $A_2$ 对 $A_1$ 当前状态估计的推断? 对于 $A_2$ 的观测 $\alpha$，可能的事件串为

$$s\in\ell_2^{-1}(\alpha)\cap L(G).$$

每个候选事件串 $s$ 都产生 $A_1$ 的观测 $\ell_1(s)$，进而确定一个当前状态估计 $M_1(G,\ell_1(s))$。收集所有这些候选估计，便得到二阶估计

$$M_{A_1\leftarrow A_2}(G,\alpha) =\left\{ M_1(G,\ell_1(s)) \;\middle|\; s\in L(G),\ \ell_2(s)=\alpha \right\}.$$

如何理解二阶秘密？一阶当前状态不透明性要求观察者不能确定当前真实状态是否属于秘密状态集；二阶不透明性则要求 $A_2$ 不能确定 $A_1$ 的当前状态估计是否属于秘密估计族 $\mathcal S$。其等价表述为

$$\begin{aligned} &\forall s\in L(G),\quad M_1(G,\ell_1(s))\in\mathcal S\\ &\Rightarrow\ \exists t\in L(G):\quad \ell_2(t)=\ell_2(s) \ \wedge\ M_1(G,\ell_1(t))\notin\mathcal S. \end{aligned}$$

读完这个定义之后，我对于“为什么要用 $M_{A_1\leftarrow A_2}(G,\alpha)\nsubseteq\mathcal S$” 来定义 opaque 感到有些疑惑，也找不到什么好的解释与动机。再加上对于这个二阶观测的定义，我感到有些绕，于是提出了 真实路径 的概念，来更好地建模和梳理这其中的逻辑：

定义（真实路径，Ground-Truth Path） 系统实际执行的路径记为

$$\rho^\ast: q_0^\ast\xrightarrow{s^\ast}q^\ast, \qquad q_0^\ast\in Q_0,$$

其中，$\rho^\ast$ 称为真实路径。由该路径确定的当前真实状态为 $q^\ast$，$A_1$ 的当前真实状态估计定义为

$$X^\ast:=M_1\bigl(G,\ell_1(s^\ast)\bigr).$$

由定义可知

$$q^\ast\in X^\ast, \qquad X^\ast\in M_{A_1\leftarrow A_2} \bigl(G,\ell_2(s^\ast)\bigr).$$

只有 $\rho^\ast$ 被称为真实路径；$q^\ast$ 与 $X^\ast$ 分别称为当前真实状态和当前真实状态估计。上式说明：当前真实状态属于当前真实状态估计，而当前真实状态估计属于 $A_2$ 基于实际观测形成的二阶估计。

之后，我尝试了一些例子来辅助理解，以下是我尝试过的例子与其对现实问题的建模：

例. 目标移动与传感器观测

设目标位于三个房间之一，状态集为 $Q=\{1,2,3\}$，初始状态集为 $Q_0=\{1,2\}$。$A_1$ 是通过传感器追踪目标的侦察员；$A_2$ 是敌方，其目的在于判断 $A_1$ 是否已经确定目标位置。两者都知道系统模型，但分别接收不同的传感器输出。

目标的移动或停留触发传感器事件。定义如下转移及观测标记，其中 $h_i$ 表示目标在房间 $i$ 停留时触发的检测事件：

事件	状态转移	$A_1$ 的输出 $\ell_1$	$A_2$ 的输出 $\ell_2$
$e_{12}$	$1\to2$	$a$	$z$
$e_{23}$	$2\to3$	$b$	$w$
$h_1$	$1\to1$	$c$	$z$
$h_2$	$2\to2$	$c$	$z$

所有事件对两者均可见，但标记不同：$A_1$ 能区分移动事件 $e_{12}$ 与停留检测，$A_2$ 则把三者都观察为 $z$。

在一次行动中，目标实际上从房间 $1$ 移至房间 $2$，穿过门口时触发事件 $e_{12}$。因此真实路径、真实事件串和当前真实状态分别为

$$\rho^\ast=1\xrightarrow{e_{12}}2,\qquad s^\ast=e_{12},\qquad q^\ast=2.$$

$A_1$ 实际观察到 $a$，只有事件串 $e_{12}$ 与该观测一致，因此其当前真实状态估计为

$$X^\ast=M_1(G,a)=\{2\}.$$

$A_2$ 实际观察到 $\alpha=z$。与此一致的事件串为 $e_{12},h_1,h_2$。其中 $e_{12}$ 使 $A_1$ 观察到 $a$，而 $h_1,h_2$ 都使 $A_1$ 观察到 $c$，且

$$M_1(G,c)=\{1,2\}.$$

故 $A_2$ 基于实际观测形成的二阶估计为

$$Y=M_{A_1\leftarrow A_2}(G,z) =\{\{2\},\{1,2\}\}.$$

我们希望 $A_2$ 无法确定“$A_1$ 已知目标位置”。所谓 $A_1$ 已知目标位置，是指 $A_1$ 的当前状态估计（CSE）仅含一个状态，即 $|X^\ast|=1$。$A_2$ 的二阶估计 $M_{A_1\leftarrow A_2}(G,\alpha)$ 既包含当前真实状态估计 $X^\ast$，也可能包含其他可能路径导出的当前状态估计 $X$。对 $A_2$ 而言，$X$ 与 $X^\ast$ 是同等地位的，因此无法区分哪一个是 $A_1$ 的当前真实状态估计。若存在 $X\in M_{A_1\leftarrow A_2}(G,\alpha)$ 使得 $|X|>1$，那么 $A_2$ 就无法断定 $A_1$ 已知目标位置。

抽象出其中的结构，可以令“任意 Agent 已知目标位置”是需要保守的秘密，即

$$\mathcal S:=\{X\subseteq Q\mid |X|=1\} =\{\{1\},\{2\},\{3\}\}.$$

$\mathcal S$ 来自保密目标，而非此次 $X^\ast$。

此次 $X^\ast=\{2\}\in\mathcal S$，但 $Y$ 还包含非秘密当前状态估计 $\{1,2\}$，所以 $Y\nsubseteq\mathcal S$：$A_2$ 无法确定 $A_1$ 是否已确定目标位置。事件串 $h_1$（或 $h_2$）就是隐藏真实秘密事件串 $e_{12}$ 的非秘密替代串。

这里的候选当前状态估计 $X=\{1,2\}$ 并不等于当前真实状态估计 $X^\ast=\{2\}$。但在 $A_2$ 看来，两者对应的事件串产生相同观测 $z$，所以 $A_2$ 无法判断哪一个才是 $A_1$ 的当前真实状态估计。也就是说，$A_2$ 无法排除 $X$ 是 $A_1$ 当前状态估计的可能性。由于 $X\notin\mathcal S$，有

$$\exists X\in M_{A_1\leftarrow A_2}(G,z):\ X\notin\mathcal S,$$

即 $M_{A_1\leftarrow A_2}(G,z)\nsubseteq\mathcal S$。

注意：这只说明观测 $z$ 满足保护条件，并不证明整个系统 opaque。例如 $A_2$ 观察到 $w$ 时，能够确定发生了 $e_{23}$，进而确定 $A_1$ 的估计为 $\{3\}$，此时秘密泄露。

---

上述例子比较特殊，S 的元素全部是单元素集合。下面来看另一个例子：

设房间 $1,2$ 属于东区，$3,4$ 属于西区，状态集为 $Q=\{1,2,3,4\}$。

保密目标：$A_2$ 无法确定“$A_1$ 已知目标在哪个区”。

因此：

$$\mathcal S= \{X\subseteq Q\mid X\neq\varnothing,\ X\subseteq\{1,2\}\ \text{或}\ X\subseteq\{3,4\}\}.$$

例如 $X^\ast=\{1,2\}$：$A_1$ 不知道具体房间，但已确定目标在东区，因此属于秘密。

---

此外，由于之前对原文中的定义感到不解，我还尝试提出了如下的条件：

$$M_{A_1\leftarrow A_2}(G,\alpha)\cap\mathcal S=\varnothing$$

这是一个更强的局部判断：$A_2$ 能够确定秘密不成立。在之前的例子中，$\mathcal S$ 表示“$A_1$ 知道目标所在区域”；该条件意味着 $A_2$ 能确定，依据此次观测，$A_1$ 并不知道目标所在区域。若要求该条件对所有观测成立，则意味着 $A_1$ 的当前状态估计始终不属于秘密估计族。

1. 这一全局性质与 $A_2$ 无关，等价于 $\forall s\in L(G),\ M_1(G,\ell_1(s))\notin\mathcal S$。
2. $\mathcal S\subseteq2^Q$ 仍是二阶 opacity 中使用的秘密知识状态族；但此处只判断 $A_1$ 的估计是否属于 $\mathcal S$，没有对另一代理的估计进行推断，因此是一阶估计性质。阶数取决于推断层数，而不是秘密集合的命名。该性质可视为 $A_1$ 的 observer 上避开禁用状态族 $\mathcal S$ 的安全性质，已有一阶估计性质框架覆盖，见 Zhang et al., §3.1。

相关文献：Bohan Cui, Ziyue Ma, Shaoyuan Li, Xiang Yin. On Epistemic Properties in Discrete-Event Systems: A Uniform Framework and Its Applications. arXiv:2409.06588, 2024. 全文.

总结：两篇文献的表述层次不同。Cui et al. 在 §4.3、式(4)显式定义了给定观测下的认知判断；取值 $\mathsf N$ 表示“$A_2$ 此时确定 $A_1$ 的知识谓词为假”，对应 $M_{A_1\leftarrow A_2}(G,\alpha)\cap\mathcal S=\varnothing$。Zhang et al. 给出一般估计性质框架，也能表达这一条件。仅针对已产生的观测 $\alpha$ 时，该判断仍依赖 $A_2$；只有要求所有观测都满足时，才等价于与 $A_2$ 无关的一阶全局性质“$A_1$ 的估计始终不属于 $\mathcal S$”。应区分某次观测下的局部认知判断与对所有观测成立的全局性质。

---

另一个问题是：

如果已经确定一阶秘密 Q_s, 能否 somehow construct order-2 secret?

相关文献：Bohan Cui, Ziyue Ma, Shaoyuan Li, Xiang Yin. On Epistemic Properties in Discrete-Event Systems: A Uniform Framework and Its Applications. arXiv:2409.06588, 2024. §4.2、Definition 1 及安全分析示例。

该文定义了状态估计上的知识谓词，并明确以“$A_1$ 确定当前处于秘密状态”为例：给定一阶秘密 $Q_s\subseteq Q$，对非空估计 $X\subseteq Q$，定义

$$\varphi(X,Q_s)\iff X\subseteq Q_s.$$

若保密目标是让 $A_2$ 无法确定“$A_1$ 已知当前处于 $Q_s$”，则将满足该谓词的知识状态收集为二阶秘密族：

$$\mathcal S=\{X\subseteq Q\mid\varnothing\neq X\subseteq Q_s\}.$$

这里的 $\mathcal S$ 记号是对该文知识谓词的集合形式改写。一般地，可先指定关于 $Q_s$ 的秘密认知谓词 $\varphi$，再构造 $\mathcal S=\{X\subseteq Q\mid X\neq\varnothing,\ \varphi(X,Q_s)\}$；具体谓词由应用决定，$Q_s$ 本身不唯一决定 $\mathcal S$。