一轮攻防的Naive理论分析

这篇文章的主题是在完成安全通论第一次作业的过程中想到的，虽然现在回过头来看感觉还是有点幽默。下面是作业题目原内容：

• 来源：安全通论作业一：数值分析攻击信道容量
• 内容：用matlab/python等作图工具，数值分析攻击信道容量。
• 要求：形成分析报告，字数不限。以PDF附件形式上传~

本来说是不用算的，然后作业里面我就把攻击信道容量算出来了（见附录），而且从其图像来看确实在那个模型下不安全的情况一定存在（攻击信道容量 > 0）。。。但是解释起来着实有点牵强，最后的理解还是攻击方能够产生的最大威胁当量。不过这个作业也算给了我一些比较好的启发，尝试基于学过的一些理论的内容，构建模型。虽然说是人家好像在十几年前就利用乔姆斯基范式研究过了（LangSec），而且还证明了一定不存在完全安全的软件。哈哈哈。但是过程挺好玩的，遂分享。
其实这个模型中间问题也挺多的，比如把系统抽象为 DFA 是否合理，资源函数也是存在一定定义问题。。然后把防御方也分开成了一个 PPT，攻击方也进行了分级别的抽象等等。还有灰盒模型的建模，求出来的界好像也有点怪怪的。
娱乐性质大于科学性。√

1. 基本建模

1.1 攻防双方的形式化建模

对于攻防双方，我们将其各自抽象为一个概率多项式图灵机：

• 【防守方】 考虑非动态变化的防守方，即防守方提前部署策略，它不知道哪个攻击方会进行什么攻击，它的机器为多项式时间图灵机：

  $\mathcal{M}_D(x) \to \{0, 1\}$

  其中 $1$ 表示拦截，$0$ 表示放行。

  设 $\mathcal{M}_D$ 能判定的语言是：

  $L_D = \mathcal{M}_D^{-1}(1)$

  同时定义防守资源函数：

  $\psi(L_D) = \min_{M:L(M)=L_D} \left\{ \max_{x\in\Sigma^*} \left\{ T_M(x) + S_M(x) \right\} \right\}$

  这里我们考虑 $\max$ 是因为，在真实的工程防御中，攻击者可能采用一种称为算法复杂度攻击的攻击方式。例如，防守方使用正则表达式引擎（一种判定图灵机）来匹配恶意特征。大部分正常的载荷在几毫秒内就能匹配完成，但攻击者可以精心构造一个引发 ReDoS 的特定载荷 $x_{worst}$。在这个特定的 $x_{worst}$ 上，机器的时空开销 $T_M(x_{worst}) + S_M(x_{worst})$ 会呈指数级飙升。

  形式上定义防守方可以承载的资源最大值为 $\mathcal{R}_D$，这时即要求：

  $\psi(L_D) \leqslant \mathcal{R}_D$

• 【攻击方】 攻击方定义为两个阶段的图灵机 $\mathcal{M}_A$：

  $\begin{aligned} &\text{输入：环境资源描述 }\langle S \rangle, \text{随机数} r\\ &\text{运行：}\\ &\qquad 1.\quad w^*\leftarrow \mathcal{M}_A^{\text{off}}(\langle S \rangle, r);\\ &\qquad 2.\quad x\leftarrow \mathcal{M}_A^{\text{on}}(\langle S \rangle, w^*, r);\\ &\text{输出：}x \end{aligned}$

  其中 $\langle S\rangle$ 表示系统上下文包括系统公开的架构、版本、网络拓扑等资源；$r$ 显然为概率多项式图灵机内部的随机数；对于 $w$，这里这样定义是因为我们想要凸显出攻击方的核心资产：漏洞证据。

  • 若 $w = \emptyset$，此时攻击者处于什么都不知道的状态，它是盲打击的；
  • 若 $w = w_{\text{CVE}}$，此时漏洞处于 1-day 状态，攻防双方需要比拼谁先利用漏洞或者打上补丁；
  • 若 $w = w_{\text{0-day}}$，此时攻击者处于绝对优势，攻防双方信息绝对不对称。

  同样定义攻击资源函数：

  $\Phi(\mathcal{M}_A) = \max_{x\in \Sigma^*} \left\{ T_{\mathcal{M}_A^{\text{off}}}(x) + S_{\mathcal{M}_A^{\text{off}}}(x) \right\} + \max_{x\in \Sigma^*} \left\{ T_{\mathcal{M}_A^{\text{on}}}(x) + S_{\mathcal{M}_A^{\text{on}}}(x) \right\}$

  类似地，形式上定义攻击方可以承载的资源最大值为 $\mathcal{R}_A$，这时即要求：

  $\Phi(\mathcal{M}_A) \leqslant \mathcal{R}_A$

记黑客生成的载荷子集为：

$\text{Supp}(\mathcal{M}_A) = \left\{ x \in \Sigma^* \mid \Pr(\mathcal{M}_A \to x) > 0 \right\}$

我们还需要对防守方的业务相关内容进行建模。

根据防守方的 PPT 机器 $\mathcal{M}_A$，设其对应的状态集合为 $\mathbb{S}$。
对于防守方来说，他自评地将状态集合划定成两个不交子集：

• $\mathcal{S}_S \subseteq \mathbb{S}$：符合防守方期望的安全状态，满足机密性、完整性、可靠性等指定安全服务需求；
• $\mathcal{S}_U = \mathbb{S} - \mathcal{S}_S$：非安全状态。

在单论攻防交互下，考虑防守方的业务是一个概率状态转移的过程，即概率状态转移函数 $\delta$ 定义如下：

$\delta : \mathbb{S} \times \Sigma^* \times \mathbb{S} \to [0, 1]$

此时应当有要求，对于任意给定的当前状态 $s$ 与输入载荷 $x$，系统转移到所有下一个可能状态为 $s'$ 的概率之和应当满足：

$\sum_{s'\in \mathbb{S}} \delta(s, x, s') = 1$

单个字符的转移函数记为 $\delta_0: \mathbb{S} \times \Sigma \times \mathbb{S} \to [0, 1]$。

对于单论攻防，设系统处于某个初始状态 $s_0$，则此时对于输入载荷 $x$，系统单次执行后落入非安全状态的概率为：

$p_u(s_0, x) = \Pr_{x\in\Sigma^*} (\text{from } s_0 \text{ to unsafe}) = \sum_{s'\in \mathcal{S}_U} \delta(s_0, x, s')$

定义恶意载荷语言集合：

$\mathcal{L}_{\text{mal}}(s) = \left\{ x\in\Sigma^* \mid \sum_{s'\in \mathcal{S}_U} \delta(s, x, s') > 0 \right\}$

对于一轮攻防，可以记：

$\mathcal{L}_{\text{mal}} = \mathcal{L}_{\text{mal}}(s_0)$

1.2 攻击动作

在前序的建模中，我们直接指定了黑客所使用的特定图灵机，而事实上由于攻防的不对称性，攻击者应当是在一族满足条件的黑客图灵机中进行选择。下面考虑将攻击者定义为一个资源受限的概率多项式通用图灵机 $\mathcal{U}$，攻击者在其中所做的战术选择形式化为一段多项式长度的策略描述 $\langle \pi\rangle$。通用图灵机以环境 $\langle S \rangle$、随机数 $r$ 以及策略描述 $\langle \pi \rangle$ 为输入，模拟执行该策略，即 $x \leftarrow \mathcal{U}(\langle \pi \rangle, \langle S \rangle, r)$。

定义攻击者为一个受限于多项式时空资源的概率通用图灵机 $\mathcal{U}_{\mathcal{A}}$。定义策略空间 $\Pi$，其中任意策略 $\langle \pi \rangle \in \Pi$ 是一段多项式长度的描述。

在单轮攻防中，攻击者基于当前观测到的环境上下文 $\langle S \rangle$，选择某一种策略 $\langle \pi \rangle$，并结合内部的随机数带 $r$，通过通用图灵机模拟执行该策略，生成利用脚本 $\mathcal{M}_A$，从而输出攻击载荷 $x$：

$\mathcal{M}_A \leftarrow \mathcal{U}_{\mathcal{A}}(\langle \pi \rangle, \langle S \rangle, r)$

通用图灵机生成的脚本的资源开销必须满足系统的物理上限：

$\Phi(\mathcal{M}_A) \leqslant \mathcal{R}_{\mathcal{A}}$

在这一框架下，攻击者生成的载荷分布 $\mathcal{D}_{\pi}$ 完全由其输入的策略描述 $\langle \pi \rangle$ 决定。相应的，盲自评成功率 $p$ 与联合概率 $a$ 不再是固定值，而是依赖于策略 $\langle \pi \rangle$ 的动态函数：

$p(\pi) = \Pr_{x \gets \mathcal{D}_{\pi}} (x \in \mathcal{L}_{\text{mal}})$

$a(\pi) = \Pr_{x \gets \mathcal{D}_{\pi}} (x \in L_D \cap \mathcal{L}_{\text{mal}})$

下面我们关注两个语言类 $L_D$ 与 $\mathcal{L}_{\text{mal}}$，针对这两个语言类的分析相当于就是在分析防守方是否真的防守成功。

• $L_D \cap \mathcal{L}_{\text{mal}}$：防御方成功检测并拦截的能够攻击防御方的载荷的语言集合；
• $L_D - \mathcal{L}_{\text{mal}}$：防御方检测出来并拦截但是无危害的载荷的语言集合；
• $\mathcal{L}_{\text{mal}} - L_D$：防御方并没有检测出来但能够成功攻击防御方的载荷的语言集合。

下面其实就可以走杨义先《安全通论》里面的那套说法，但是我还是觉得有点牵强，就不放上来了。

1.3 资源分析

在攻击方生成并投递载荷 $x$ 后，防守方机器 $\mathcal{M}_D$ 被动接收该载荷并启动判定过程。由于 $\mathcal{M}_D$ 为概率多项式图灵机，其内部存在随机数带 $r_{\mathcal{D}}$。形式化地，对于任意输入的具体载荷 $x$，定义 $\mathcal{M}_D$ 的单次执行为一个位形序列的演化路径 $C_0, C_1, \dots, C_k$。定义在此确定的 $(x, r_{\mathcal{D}})$ 下：

• 实际时间消耗 $t(x, r_{\mathcal{D}}) = k$（状态转移的总步数）；
• 实际空间消耗 $s(x, r_{\mathcal{D}}) = \max\{|C_i| \mid 0 \leqslant i \leqslant k\}$（读写头访问过的最大纸带元胞数）。

由此，定义防守方针对于特定载荷 $x$ 的资源消耗函数 $W_{\mathcal{M}_D}(x)$ 为基于内部随机空间的数学期望：

$W_{\mathcal{M}_D}(x) = \mathbb{E}_{r_{\mathcal{D}}} \left[ t(x, r_{\mathcal{D}}) + s(x, r_{\mathcal{D}}) \right]$

当攻击者以策略 $\langle \pi \rangle$ 生成载荷分布 $\mathcal{D}_{\pi}$ 时，防守方接收一次该策略下投递的载荷，其被迫产生的预期资源消耗代价为：

$C_{\mathcal{M}_D}(\pi) = \mathbb{E}_{x \gets \mathcal{D}_{\pi}} \left[ W_{\mathcal{M}_D}(x) \right]$

对于防守方物理资源上限 $\mathcal{R}_D$，定义指示函数 $\mathbb{I}_{DoS}(x) = 1 \iff W_{\mathcal{M}_D}(x) > \mathcal{R}_D$。在单轮交互中，载荷 $x$ 的恶意语义即为：引发的计算开销击穿物理上限。此时，系统以概率 $1$ 强制坍缩至非安全状态 $\mathcal{S}_U$：

$\text{若}\ W_{\mathcal{M}_D}(x) > \mathcal{R}_D, \text{ 则 }\ \forall s \in \mathbb{S}, \sum_{s' \in \mathcal{S}_U} \delta(s, x, s') = 1$

此时攻击者通过算法复杂度攻击（如 ReDoS）在物理维度上造成了拒绝服务（DoS）。

---

2. 受限资源下的绝对防御

在单轮对抗中，若对于任意满足资源约束 $\Phi(\mathcal{M}_A)\leqslant \mathcal{R}_A$ 的黑客 $\mathcal{M}_A$，在满足 $\psi(L_D)\leqslant \mathcal{R}_D$ 的图灵机 $\mathcal{M}_D$ 下的优势严格为 $0$ 则称 $\mathcal{M}_D$ 为 $(\mathcal{R}_A, \mathcal{R}_D)$-绝对防御的，即：

$\text{Adv}_{\mathcal{A}}(\mathcal{R}_A, \mathcal{R}_D) = \max_{\mathcal{M}_A:\Phi(\mathcal{M}_A)\leqslant \mathcal{R}_A} \left\{ \mathbb{E}_{x\gets\mathcal{M}_A} \left[ (1-r^{\mathcal{R}_D}(\mathcal{M}_A)) \cdot p_u(s_0, x) \right] \right\} = 0$

这里把一次成功的攻击拆解为三个独立的概率事件：

• 攻击者生成载荷 $x$ 的概率（隐藏在期望的分布 $x \leftarrow \mathcal{M}_A$ 中）；
• 防守方未能拦截的概率 $(1 - r^{\mathcal{R}_D}(\mathcal{M}_A))$，其中 $r^{\mathcal{R}_D}(\mathcal{M}_A) = \Pr_{x\gets \mathcal{M}_A}(x\in L_D \mid \psi(L_D) \leqslant \mathcal{R}_D)$ 表示真实拦截概率；
• 载荷触发系统非安全状态转移的概率 $p_u(s_0, x)$。

要构建 $(\mathcal{R}_A, \mathcal{R}_D)$-绝对防御的 $\mathcal{M}_D$ 的条件是什么？

由概率的非负性可得，要么 $r^{\mathcal{R}_D} = 1$，要么 $\forall x\in \text{Supp}(\mathcal{M}_A)$，$p_u(s_0, x) = 0$。对于 $r^{\mathcal{R}_D} = 1$，它等价于 $\forall x\in \text{Supp}(\mathcal{M}_A)$，$x\in L_D$，即等价于 $\text{Supp}(\mathcal{M}_A) \subseteq L_D$。对于 $\forall x\in \text{Supp}(\mathcal{M}_A)$，$p_u(s_0, x) = 0$，它等价于 $\forall x\in \text{Supp}(\mathcal{M}_A),\ \forall s'\in\mathcal{S}_U$，$\delta(s_0, x, s') = 0$，即等价于 $\text{Supp}(\mathcal{M}_A)\cap \mathcal{L}_{\text{mal}} = \emptyset$。综上所述，$(\mathcal{R}_A, \mathcal{R}_D)$-绝对防御的 $\mathcal{M}_D$ 存在等价于存在 $\mathcal{M}_D$ 使得 $\text{Supp}(\mathcal{M}_A)\cap(\mathcal{L}_{\text{mal}} - L_D) = \emptyset$。

下面应当研究：$\mathcal{L}_{\text{mal}} - L_D$ 应当有多大。

注意到防守方受到资源 $\mathcal{R}_D$ 的约束，因此考虑防守方可接受输入最大为 $N = \log \mathcal{R}_D$，据此我们对攻击方也做同等约束。

要计算长度为 $N$ 的载荷中，既能造成破坏又不会被拦截的载荷数量。定义语言集合：

$L_{\text{gap}} = (\mathcal{L}_{\text{mal}} \setminus L_D) \cap \Sigma^N$

为了计算 $|L_{\text{gap}}|^{(N)}$，我们需要在有限状态机上进行路径计数：

• $G_{\text{mal}} = (\mathbb{S}, E_{\text{sys}})$：系统业务逻辑的状态转移图，目标状态集为 $\mathcal{S}_U$。
• $G_{\mathcal{D}}^- = (V_{\mathcal{D}}, E_{\mathcal{D}}^-)$：假设在给定的资源约束下，防守方的判定逻辑可以等效或近似为一个 DFA。我们取其补语言的自动机，即将输出 $0$（放行）的状态设为接受状态集 $F_{\mathcal{D}}^-$。

构建乘积自动机图 $G_{\text{mix}} = G_{\text{mal}} \times G_{\mathcal{D}}^-$，其中：

• 顶点集：$V_{\text{mix}} = \mathbb{S} \times V_{\mathcal{D}}$；
• 边集：如果在给定字符 $c \in \Sigma$ 下，系统转移有效且防守方放行，则存在有向边。
• 邻接矩阵：设 $A$ 为图 $G_{\text{mix}}$ 的邻接矩阵，矩阵元素 $A_{i,j}$ 表示状态 $i$ 到状态 $j$ 的合法字符转移数。

设指示向量 $u^T$ 为初始状态 $(s_0, q_0)$，向量 $v$ 为目标状态集 $\mathcal{S}_U \times F_{\mathcal{D}}^-$。那么长度为 $N$ 的恶意漏报载荷总数，在图论上严格等价于从起点到终点长度为 $N$ 的路径总数：

$|L_{\text{gap}}|^{(N)} = u^T A^N v$

就接下来采用 Perron-Frobenius 定理和 Jordan 分解来求 $A^N$ 的渐进界。

对邻接矩阵 $A$ 进行 Jordan 分解：

$A = P J P^{-1}$

其中，$P$ 是可逆矩阵，$J$ 是 Jordan 标准型矩阵。$J$ 是一个分块对角矩阵，形如 $J = \text{diag}(J_1, J_2, \dots, J_k)$。对于其中任意一个特征值为 $\lambda_i$、阶数为 $m_i$ 的 Jordan 块 $J_i$，它可以被分解为一个对角矩阵和一个幂零矩阵 $N_i$ 的和：

$J_i = \lambda_i I + N_i$

其中 $N_i$ 是主对角线上方全为 $1$，其余全为 $0$ 的矩阵。

对于单个 Jordan 块，由于 $\lambda_i I$ 与 $N_i$ 乘法可交换，我们直接应用二项式定理：

$J_i^N = (\lambda_i I + N_i)^N = \sum_{j=0}^N \binom{N}{j} \lambda_i^{N-j} N_i^j$

因为当 $j \geqslant m_i$ 时，$N_i^j = \mathbf{0}$，所以上述级数被严格截断：

$J_i^N = \sum_{j=0}^{\min(N, m_i-1)} \binom{N}{j} \lambda_i^{N-j} N_i^j$

当 $N$ 足够大时，在矩阵 $J_i^N$ 的元素中，多项式系数最大的项出现在 $j = m_i-1$ 时。此时该项的值严格为：

$\binom{N}{m_i-1} \lambda_i^{N-(m_i-1)}$

此时回到总路径数公式：

$|L_{\text{gap}}|^{(N)} = u^T (P J^N P^{-1}) v$

令行向量 $c^T = u^T P$，列向量 $d = P^{-1} v$，则总路径数是 $J^N$ 中各个元素的线性组合。当 $N \to \infty$，即 $N$ 足够大时，$A^N$ 的增长速度完全由矩阵 $A$ 的最大特征值 $\lambda_{\max}$（谱半径）主导。

在渐近复杂度下，常数系数与低阶项被忽略。组合数 $\binom{N}{m-1} \approx \frac{N^{m-1}}{(m-1)!}$，其关于 $N$ 的渐近阶为 $N^{m-1}$。因此，漏报的载荷总数随着长度 $N$ 的增长严格满足渐近关系：

$|L_{\text{gap}}|^{(N)} = \Theta \left( N^{m-1} \lambda_{\max}^{N - m + 1} \right) \sim \Theta \left( \log(\mathcal{R}_D)^{m-1} \cdot \mathcal{R}_D^{\log(\lambda_{\max})} \right)$

此时，我们可以看到：

• 若 $\lambda_{\max} = 0$：图 $G_{\text{mix}}$ 中不存在环，漏报载荷数量有限，防守方在足够长的输入下实现了绝对防御；
• 若 $\lambda_{\max} = 1$：存在漏洞，但恶意载荷数量呈多项式 $\Theta(N^{m-1})$ 增长；
• 若 $\lambda_{\max} > 1$：恶意载荷数量随着长度 $N$ 呈指数级 $\Theta(\lambda_{\max}^N)$ 爆发。

这里 $\lambda_{\max}$ 基本反映了这个系统的漏洞数。

---

3. 灰盒模型

现实中肯定不是在 $\Sigma^N$ 中进行 $|\Sigma|^{-N}$ 的纯随机攻击的。这里我们尝试讨论灰盒攻击的攻击策略。 攻击者虽然初始时没有完整的图 $G_{\text{mix}}$（即 $w_0 = \emptyset$），但系统在每次处理载荷后，客观上会泄漏侧信道信息（如 CPU 分支覆盖率、执行时间、内存消耗）。这时，证据 $w$ 不再是静态的，而是一个随时间 $t$ 递增的已观测子图 $G_{\text{obs}}^{(t)} \subseteq G_{\text{mix}}$。（按理来说这里我们应该对黑客模型重新构建，但事实上并不太必要）。

当黑客投递载荷 $x$ 时，他能够观测到该载荷在系统内部触发的执行路径 $\tau(x)$，即一条状态转移边序列。这时知识库的更新过程为：

$G_{\text{obs}}^{(t)} = G_{\text{obs}}^{(t-1)} \cup \tau(x_t)$

灰盒攻击者投递的分布是一个随着知识库动态更新的条件概率分布：

$\mathcal{D}_{\text{fuzz}}(\cdot \mid G_{\text{obs}}^{(t)})$

啊这里定义了后面其实就没有用这个定义。

3.1 灰盒攻击策略

设 $G_{\text{mix}} = (V, E)$，设定我们攻击的目标是找到一条从初始状态 $s_0$ 到非安全状态 $s_k \in \mathcal{S}_U$ 的特定路径 $\rho = (s_0, \cdots, s_k)$。

定义一个随机化 Fuzzer：

• 种子队列 $\mathbb{Q}$：Fuzzer 维护所有已发现状态对应的输入载荷。设系统可达状态总数的上限为 $|\mathbb{S}|$，因此任何时刻队列的大小 $|\mathbb{Q}| \leqslant |\mathbb{S}|$；
• 纯随机调度：在每一轮测试 $t$ 中，Fuzzer 以均匀分布从 $\mathbb{Q}$ 中随机抽取一个种子进行变异。因此，选中目标路径上当前前沿状态 $s_i$ 的概率严格满足：$P_{\text{select}}(s_i) = 1/|\mathbb{Q}| \geqslant 1/|\mathbb{S}|$；
• 纯随机变异：假设从 $s_i$ 转移到 $s_{i+1}$ 需要正确变异 $c_i$ 个字节。Fuzzer 在这 $c_i$ 个字节上进行均匀随机替换。单次变异命中的概率为 $P_{\text{mutate}} = |\Sigma|^{-c_i}$。（这里忽略了多项式级别的，找到这 $c_i$ 个字节的位置的多项式概率 $\binom{N-c_i}{k-c_i}/\binom{N}{k}$）

容易指出：在任意一轮 $t$ 中，如果 Fuzzer 当前已经探索到了状态 $s_i$，那么它在这一轮中成功突破到 $s_{i+1}$ 的联合概率 $p_i$ 严格下界为：

$p_i = P_{\text{select}}(s_i) \cdot P_{\text{mutate}} \geqslant \frac{1}{|\mathbb{S}| \cdot |\Sigma|^{c_i}}$

设随机变量 $X_i$ 为 Fuzzer 从已经到达 $s_i$ 的状态开始，直到首次成功触发到达 $s_{i+1}$ 所需要的总变异轮数。由于每一轮变异是独立的伯努利试验，$X_i$ 严格服从参数为 $p_i$ 的几何分布：

$X_i \sim \text{Geo}(p_i)$

几何分布的数学期望为：

$\mathbb{E}[X_i] = \frac{1}{p_i} \leqslant |\mathbb{S}| \cdot |\Sigma|^{c_i}$

设突破整条长度为 $k$ 的漏洞路径所需的总时间为 $T_{\text{hit}}$。显然 $T_{\text{hit}} = \sum_{i=0}^{k-1} X_i$。（事实上这是因为系统会向后续步骤泄露侧信道信息，求和意味着各个阶段相互独立且状态不会回退。）此时，总期望时间为：

$\mathbb{E}[T_{\text{hit}}] = \sum_{i=0}^{k-1} \mathbb{E}[X_i] \le |\mathbb{S}| \sum_{i=0}^{k-1} |\Sigma|^{c_i}$

设所有局部突破中最难的一步对应的成功率为：

$p_{\min} = \min_i (p_i) = \frac{1}{|\mathbb{S}| |\Sigma|^{c_{\max}}}$

那么 $T_{\text{hit}}$ 随机占优于负二项分布 $\text{NB}(k, p_{\min})$（即 $k$ 个 i.i.d. 的分布 $\text{Geo}(p_{\min})$ 之和），从而根据 Chernoff 不等式，有 $\forall \delta > 0$：

$\Pr \left( T_{\text{hit}} > (1+\delta) \frac{k}{p_{\min}} \right) \leqslant \exp\left( - \frac{\delta^2}{2(1+\delta)} k \right)$

设分配给灰盒攻击者的资源为 $\mathcal{R}_A^{\text{grey}} = (1+\delta)\frac{k}{p_{\min}}$。若要保证随机化 Fuzzer 能够以概率 $(1-\varepsilon)$ 挖出 0-day 漏洞，那么只要：

$\varepsilon = \exp\left( - \frac{\delta^2}{2(1+\delta)} k \right)$

即：

$\delta \approx \sqrt{\frac{2\ln(1/\varepsilon)}{k}}$

最后我们得到下述结论：
对任意状态空间为 $\mathbb{S}$，漏洞路径长度 $k$，最大分支判定长度为 $c_{\max}$ 的防守方保护的系统，在纯随机灰盒 Fuzzing 模型下，以 $(1 - \varepsilon)$ 的概率挖出 0-day 漏洞的攻击者理论算力最多只需要：

$\mathcal{R}_A^{\text{grey}} \leqslant O\left( k \cdot |\mathbb{S}| \cdot |\Sigma|^{c_{\max}} \cdot \ln(1/\varepsilon) \right)$

反过来，只要灰盒攻击者的资源满足 $\mathcal{R}_A^{\text{grey}} > k \cdot |\mathbb{S}| \cdot |\Sigma|^{c_{\max}}$，它在算力耗尽前成功找到漏洞的概率满足：

$\Pr(\text{succeed}) \geqslant 1 - \exp\left( - \frac{ \left( \frac{\mathcal{R}_A}{|\mathbb{S}| \cdot |\Sigma|^{c_{\max}} \cdot k} - 1 \right)^2 }{ 2 \cdot \frac{\mathcal{R}_A}{|\mathbb{S}| \cdot |\Sigma|^{c_{\max}} \cdot k} } \cdot k \right)$

3.2 受限资源防御下攻击导向的随机化灰盒分析

我们把我们的视角从整个图 $G_{\text{mix}}$ 转移到考虑找到集合 $L_{\text{gap}}^{(N)}$ 中的任意一条路径。这时资源约束仍然为 $N = \log \mathcal{R}_D$，此时也有渐进关系 $|L_{\text{gap}}|^{(N)} = \Theta(N^{m-1}\lambda_{\max}^{N-m+1})$。

设 Fuzzer 突破整个 $L_{\text{gap}}$ 路径需要经过 $k$ 个节点，且在第 $i$ 个节点 $s_i$ 攻击者需要变异长度为 $c_i$ 的字符。此时，由于 $L_{\text{gap}}$ 是一个大的目标集合，所以有效分支会增加为 $d_i$ 个，此时单步随机变异命中的客观概率为：

$P_{\text{mutate}, i} = d_i \cdot |\Sigma|^{-c_i}$

同时注意到：

$\prod_{i=1}^k d_i = |L_{\text{gap}}|^{(N)} = \Theta(N^{m-1}\lambda_{\max}^N)$

以及同时，载荷总长度守恒：

$\sum_{i=1}^k c_i = N$

Fuzzer 在第 $i$ 步的单次联合成功概率为 $p_i = \frac{1}{|\mathbb{Q}|} \cdot d_i |\Sigma|^{-c_i}$。保守估计 $|\mathbb{Q}| \le |\mathbb{S}|$。完成该步突破的期望时间（几何分布期望）为：

$\mathbb{E}[X_i] = \frac{1}{p_i} \leqslant |\mathbb{S}| \cdot \frac{|\Sigma|^{c_i}}{d_i}$

完成整个 $L_{\text{gap}}$ 路径搜索的总期望时间 $\mu$ 为各独立阶段期望之和：

$\mu = \sum_{i=1}^k \mathbb{E}[X_i] \le |\mathbb{S}| \sum_{i=1}^k \frac{|\Sigma|^{c_i}}{d_i}$

总和往往被瓶颈控制，设对于 $b$ 恰有：

$\frac{|\Sigma|^{c_b}}{d_b} = \max_{1 \le i \le k} \left( \frac{|\Sigma|^{c_i}}{d_i} \right)$

即：

$\mu = \Theta \left( |\mathbb{S}| \cdot \frac{|\Sigma|^{c_b}}{d_b} \right)$

同理可得：

$\Pr(\text{success}) \geqslant 1 - \exp\left( - \frac{ ( \mathcal{R}_A - \mu )^2 }{ 2 \cdot \mathcal{R}_A \cdot \mu } \cdot k \right)$

中间尝试引入 $\lambda_{\max}$ 但失败了，因为我们这里将 Fuzzer 完全随机化了，并不能看到 $\lambda_{\max}$ 大小对 Fuzzing 能力的影响。这也印证了一句话：系统有多危险，从来不取决于它包含了多少个高危漏洞，而仅仅取决于通往这些漏洞的最短路径上，最容易被绕过的那道门槛有多低。 额，当然你硬要说瓶颈间接依赖于 $\lambda_{\max}$ 也行，毕竟我们也是有相关约束在的。

看起来好像灰盒测试不如白盒测试（$O(|V| + |E|)$），不过其实还好灰盒测试的机动性很高，白盒测试往往会遇到会卡住的一些地方（比如深递归）导致其过不去。引入混合模糊测试技术应当是能缓解的。这个模型还是有点蠢蠢的，但是感觉挺好玩的。

---

A. 附：攻击信道建模

下面的讨论更加的启发式，且啊啊啊确实或多或少有强行解释的嫌疑。。。

A.1 基本建模

根据攻击信道模型，我们可以将攻击者和防御者的状态用概率矩阵和信道逻辑进行描述。

举例一些具体的场景常常便于理解：

• $X=0$，$Y=0$时（此时 $X = 0$，$Z = 0$），黑客仅发送了一些探测包或使用了失效的exp，认为自己并没有打入系统；防守方的 IDS 却对这些探测产生了严重的误报，导致安全团队恐慌，自认为防线已经被攻破，而事实上系统安然无恙；
• $X=0$，$Y=1$时（此时 $X = 0$，$Z = 1$），黑客注入了一个payload，但并没有观测到结果，但事实上有一个隐蔽的地方发生了有效栈溢出；
• $X=1$，$Y=0$时（此时 $X = 1$，$Z = 1$），黑客成功拿到了服务器的最高权限，同时防守方的监控系统也爆出严重告警，数据被明显勒索或破坏，双方都清楚地知道防线已经被实质性击穿；
• $X=1$，$Y=1$时（此时 $X = 1$，$Z = 0$），黑客自己认为自己攻击成功了，但实际上被沙箱隔离了。

该攻击过程抽象为一个带有加性噪声的通信信道：

• 信道输入：攻击者盲自评 $X$
• 加性噪声：防御者盲自评 $Y$（作为外部干扰）
• 信道输出：攻击者成功攻击 $Z = X \oplus Y$

$p$、$q$ 分别表示黑客（攻击方）、红客（防御方）盲自评为成功的概率；$a$ 表示红黑双方同时盲自评为成功的联合概率（即 $\Pr(X=1, Y=1)$）。

考虑黑客和红客都足够理性，接下来我们应当明确 $p$ 和 $q$ 其值大小的具体的含义：

• 对于 $p$：黑客认为（盲自评）自己成功的概率是 $p$。也就是说，黑客评估自己的攻击有 $p$ 的概率成功，而有 $1-p$ 的概率失败，那么黑客的评估依据在哪里呢？这样的评估依赖于具体的情景，比如在考虑操作系统开启了 ASLR 等缓解措施的情况下，单次盲打命中的概率天生就极低（$p$ 极小）；相反，如果利用的是一个清晰 RCE（或者甚至是 0day），只要触发（注意触发也存在概率），执行的确定性就较高（$p$ 较大）。
• 对于 $q$：红客认为（盲自评）自己防守（拦截）成功的概率是 $q$。也就是说，防守方评估其安全体系能够有效发现并阻断潜在威胁的概率为 $q$，而有 $1-q$ 的概率发生漏报或被绕过。红客对 $q$ 的评估依据同样依赖于防守侧的具体情景。比如，如果系统部署了全流量解密、WAF、主机侧的 EDR，防守方对流量和内存状态拥有极高的可见度，此时预估的 $q$ 就会较大；反之，如果存在大量监控不到的加密流量盲区或者影子资产，$q$ 则会偏低等等。

那么 $a$ 是什么？ 黑客改变 $a$ 的含义是黑客具备环境感知与威胁情报获取的能力，他能通过探测主动将其攻击行为与防守方的盲区产生关联。也就是说，黑客在想，自己产生的攻击，到底需不需要和红客的防守策略等等产生关联。

A.2 攻击信道容量计算

对于黑客（攻击方）来说，红客盲自评为成功的概率他无法控制，因此视为常量，这时问题就转化为：当红客的防守成功概率 $q$ 固定时，黑客为了达到攻击能力的极限（即最大化信道容量 $C$），应该如何调整自己的攻击概率 $p$ 以及联合概率 $a$？

根据 PPT 中给出的公式：

$I(X,Z) = d\log\frac{d}{(1-p)(a+d)} + c\log\frac{c}{(1-p)(b+c)} + a\log\frac{a}{p(a+d)} + b\log\frac{b}{p(b+c)}$

其中 $d = 1 + a - p - q$，$c = q - a$。

注：下述记号 $I_{q}(p, a)$ 表示将 $q$ 看作参数，$p, a$ 看作变量。

对联合概率 $a$ 的分析

注意到 $\max\limits_{p, a}I(p, a) = \max\limits_{p}(\max\limits_{a}I(p, a))$，因此可以先暂时把 $p$ 也看作常量，对 $a$ 进行深入研究：

此时：

$I_{q}(p, a) = d \log \frac{d}{(1-p)Z_0} + c \log \frac{c}{(1-p)Z_1} + a \log \frac{a}{p Z_0} + b \log \frac{b}{p Z_1}$

其中，$Z_0 = 1-p-q+2a$，$Z_1 = p+q-2a$，$b=p-a$，$c=q-a$，$d=1-p-q+a$。接着我们对 $a$ 求导并解方程：

$\frac{\partial I_{q}(p, a)}{\partial a} = \log \left( \frac{(p+q-2a)^2}{(1-p-q+2a)^2} \cdot \frac{a(1-p-q+a)}{(p-a)(q-a)} \right) = 0$

展开得：

$-(1-2p)(1-2q)a^2 + (1-p-q)(p+q-4pq)a - pq(1-p-q)^2 = 0$

其中 $\Delta = [(1-p-q)(p-q)]^2$。

得到两个解析解：

$a_1 = \frac{q(1-p-q)}{1-2q}, \quad a_2 = \frac{p(1-p-q)}{1-2p}$

注意到 $a$ 的大小是受到 $p$ 和 $q$ 限制的：

$\begin{cases} b = p - a > 0 \Rightarrow a < p\\ c = q - a > 0 \Rightarrow a < q\\ d = 1 - p - q + a > 0 \Rightarrow a > p + q - 1 \end{cases}$

即：

$\max(0, p+q-1) < a < \min(p, q)$

然而：

$a_1 - p = \frac{(q-p)(1-q)}{1-2q}, \quad a_1 - q = \frac{q(q-p)}{1-2q}$

$a_2 - p = \frac{p(p-q)}{1-2p}, \quad a_2 - q = \frac{(p-q)(1-p)}{1-2p}$

这意味着 $a_1$ 和 $a_2$ 中只有更小的那个根是在上述范围内的，这与 $p$ 和 $q$ 的相对大小有关。不难验证，合法的 $a$ 是函数 $I(a)$ 的谷点，因此最大化攻击信道容量的 $a$ 只能是边界值 $\max(0, p+q-1)$ 或者 $\min(p, q)$。

简单理解如下：

• $a = \min(p, q)$：此时，$X=1$ 和 $Y=1$ 重合的可能性达到极限，这说明如果红客拦截成功，则黑客也必定触动了攻击，反之亦然。
• $a = \max(0, p+q-1)$：此时，$\Pr(X=1, Y=1)$ 接近 $0$，这意味着黑客成功绕过了红客的防守。

那么 $a$ 取到边界值的含义怎么具体理解？

• 当 $a$ 取到左边界时，此时意味着黑客彻底摸清了红客的防守盲区：
  • 当 $a = 0$ 时，暗度陈仓：即 $\Pr(X=1, Y=1) = 0$，此时黑客构造的攻击向量（比如0day或者内存马免杀）完美绕过了红客自以为是的防守，红客防守到的攻击都是假攻击。信息被不授权的黑客获取了，防守系统的机密性被破坏。
  • 当 $a = p + q - 1$ 时，草船借箭：这说明红客或者黑客的动静都有点太大了，黑客绝对隐蔽是不太可能了，但是黑客这时还是尽可能小地去避免重叠，耗费防守方的一部分资源。这时候我们计算：

    $\Pr(Y=1 \mid X=0) = \frac{\Pr(X=0, Y=1)}{\Pr(X=0)} = \frac{q - a}{1 - p} = \frac{q - (p+q-1)}{1 - p} = \frac{1 - p}{1 - p} = 100\%$

    发现在黑客没有发动真实攻击（$X=0$）的前提下，防守方永远会产生告警（$Y=1$）。黑客利用这种方式反向武器化防守规则，耗尽了防守方的耐力与算力，防守系统的可用性被破坏。
• 当 $a$ 取到右边界时，此时意味着黑客直面红客的防守：
  • 当 $a = p$ 时，破釜沉舟：这时 $p \leqslant q$，防守方十分敏感。随着防守方敏感程度变得极端（$q \to 1$），这时黑客自认为自己攻击成功的概率低于防守方敏感程度，于是他现在考虑将 $a$ 最大化为自己觉得攻击成功的概率 $p$，让自己的所有能力去碰瓷防守方的防守资源，从而威胁防守方系统的稳定性，防守系统遭受此时该黑客能够给到的最大威胁当量，防守系统的资源被消耗。
  • 当 $a = q$ 时，没找到典故：这时 $p \geqslant q$，黑客的凶猛程度（攻击密度，使用漏洞的危险程度）高过防守方的响应和应对能力。黑客在让防守方满负载的情况下还有余力进行进一步的攻击，防守系统的可用性被最大化破坏，机密性也遭受响应破坏。

对于固定水平的黑客而言，他要么硬刚，要么暗度陈仓。

也就是说：

$\max\limits_{a}{I_q(p, a)}\in \left\{I_q\left(p, 0\right), I_q\left(p, p+q-1\right), I_q\left(p, p\right), I_q\left(p, q\right)\right\}$

根据观察 $\max\limits_{p, a}I(p, a) = \max\limits_{p}(\max\limits_{a}I(p, a))$，进而有：

$\max\limits_{p, a}{I_q(p, a)}\in \left\{\max\limits_{p}I_q\left(p, 0\right), \max\limits_{p}I_q\left(p, p+q-1\right), \max\limits_{p}I_q\left(p, p\right), \max\limits_{p}I_q\left(p, q\right)\right\}$

对黑客水平 $p$ 的分析

下面，就让我们来进行分类讨论吧！

当 $p + q\leqslant 1$ 时，左侧选取 $a = 0$

此时：

$I(q, p) = I_q(p, 0) = -(1-p)\log(1-p)+q\log q - (p+q)\log(p+q)$

即得：

$\frac{dI_q}{dp} = \log \left( \frac{1-p}{p+q} \right) = 0$

即：

$p^*_{a=0} = \frac{1-q}{2}$

此时的互信息为：

$I(q)=(q+1)(1-\log(1+q))+q\log q$

当 $p + q\geqslant 1$ 时，左侧选取 $a = p + q - 1$

此时：

$I(q, p) = I_q(p, p+q-1) = (1-q)\log(1-q)-p\log p-(2-p-q)\log(2-p-q)$

即得：

$\frac{dI}{dp} = \log \left( \frac{2-p-q}{p} \right) = 0$

即：

$p^*_{(a = p + q - 1)} = p=1-\dfrac{q}{2}$

此时的互信息为：

$I(q)=(2-q)(1-\log(2-q))+(1-q)\log(1-q)$

当 $p \leqslant q$ 时，右侧选取 $a = p$

此时：

$I(q, p) = I_q(p, p) = (1-q)\log(1-q)-(1-p)\log(1-p)-(1+p-q)\log(1+p-q)$

即得：

$\frac{dI}{dp} = \log \left( \frac{1-p}{1+p-q} \right) = 0$

即：

$p^*_{(a = p)} = \frac{q}{2}$

此时的互信息为：

$I(q) = (2-q)\left(1 - \log_2(2-q)\right) + (1-q)\log_2(1-q)$

当 $p \geqslant q$ 时，右侧选取 $a = q$

此时：

$I(q, p) = I_q(p, q) = q\log q - p\log p -(1+q-p)\log(1+q-p)$

即得：

$\frac{dI}{dp} = \log \left( \frac{1+q-p}{p} \right) = 0$

即：

$p^*_{(a = q)} = \frac{1 + q}{2}$

此时的互信息为：

$I(q)=(q+1)(1-\log(1+q))+q\log q$

即：

$C(q)\in\left\{ (q+1)(1-\log(1+q))+q\log q, (2-q)\left(1 - \log_2(2-q)\right) + (1-q)\log_2(1-q) \right\}$

---

攻击信道容量

最终，我们就得到了下述关系式：

$C(q) = \begin{cases} (1+q)\left(1 - \log_2(1+q)\right) + q\log_2 q, & 0 < q \leqslant \dfrac{1}{2} \\ (2-q)\left(1 - \log_2(2-q)\right) + (1-q)\log_2(1-q), & \dfrac{1}{2} < q < 1 \end{cases}$

攻击信道容量的意义为：黑客在单次攻击中所产生的针对红客的最大有效威胁当量。展开来说就是在红客防守水平 $q$ 固定的前提下，黑客穷尽一切极其理性的战术组合（完美调整盲自评成功率 $p$ 和联合概率 $a$），他在单次博弈中能够对系统造成的“有效威胁当量”的理论最大值。

理解 $p$，$q$ 对于黑红双方是先验的，黑客预估自己当前攻击的方式得到的对攻击成功率的预判。

• $q = 0$ 就像是说一个大厦的门完全没有保安，任何人都可以随意进出，发生任何事情也无法及时产生响应。（无防守无响应状态）这时候黑客完全不需要探测或者获取情报（$a = 0$），此时如果黑客视角下攻击的成功概率（黑客盲自评）恰好为 $p = \frac{1}{2}$，那么就算防守方后续真的去审计日志，也基本上完全辨别不出来，防守方完全不知道黑客来过，此时黑客产生的威胁达到最大。
• $q = \frac{1}{2}$ 就像是说我随便一个想要进入大厦的人我都有 $\frac{1}{2}$ 的概率拒绝你进入，我黑客再怎么样对你产生威胁也不会很大，因为防守方自主筛掉了黑客一半的访问（不管是否合法）。
• $q = 1$ 就像是说我谁进入大厦我都拒绝你，事实上这时大厦的可用性基本完全丧失，所有的资源都耗费在了防守上，大厦丧失了大厦最根本的服务功能。大概就是自己太内耗了反而黑客稍微煽动一下就破防了。

A.3 最后是一些蒙特卡洛模拟

对 $q, p, a$ 进行均匀随机采样，计算对应的互信息，我们得到图像如上所示。可以看到我们得到的离散点十分标准地落在我们计算得到的上包络的下方，这充分验证了我们前面对于闭式解计算的正确性。 但是这里有一个奇怪的现象，我们发现某一些点聚集在了另一条更低的曲线上（极值奇异性），这恰好是 $a = p\cdot q$ 即攻防双方盲自评完全相互独立的情形，这个曲线就是 $1 - H(q)$ 的函数图像。但是这种假设（盲自评相互独立）合理吗？ 笔者认为是存在不同情况的，对点打击的黑客往往是对防守方的布防进行深入研究的，而像蠕虫这种暴力病毒在0day状态下确实可以考虑盲自评与防守方无关。

我们列出如下四组关系式：

• 在 $0 \leqslant q < \frac{1}{2}$ 时，攻击信道容量为 $(1+q)\left(1 - \log_2(1+q)\right) + q\log_2 q$，此时选取 $a = 0$ 或 $q$。
  • 当 $a = 0$ 时，$p^* = \frac{1 - q}{2}$，$a^* = 0$，$a^* = 0$（$\frac{1}{4} < p \leqslant \frac{1}{2}$）
  • 当 $a = q$ 时，$p^* = \frac{1 + q}{2}$，$a^* = q$，$a^* = 2p - 1$（$\frac{1}{2} \leqslant p \leqslant \frac{3}{4}$）
• 在 $\frac{1}{2} \leqslant q < 1$ 时，攻击信道容量为 $(2-q)\left(1 - \log_2(2-q)\right) + (1-q)\log_2(1-q)$，此时选取 $a = p + q - 1$ 或 $p$。
  • 当 $a = p + q - 1$ 时，$p^* = 1 - \frac{q}{2}$，$a^* = \frac{q}{2}$，$a^* = 1 - p$（$\frac{1}{2} < p \leqslant \frac{3}{4}$）
  • 当 $a = p$ 时，$p^* = \frac{q}{2}$，$a^* = \frac{q}{2}$，$a^* = p$（$\frac{1}{4} \leqslant p \leqslant \frac{1}{2}$）

此时，我们均匀随机选取 $q, p, a$，计算对应的攻击信道互信息，其中颜色越亮代表互信息越大。基于我们前面的讨论，我们对应地标记出红线与品红线，分别就代表黑客理论上的绝对最优攻击轨迹（恰好达到信道容量的轨迹）。

接下来是分别针对固定的 $q = 0.3, 0.5, 0.7$，均匀随机采样 $p, a$ 计算对应的互信息得到的图，其中红色线表示的是当前最大互信息，星星表示的就是当前 $q$ 下的攻击信道容量：

$q = 0.3$ 时的蒙特卡洛模拟：

$q = 0.5$ 时的蒙特卡洛模拟：

$q = 0.7$ 时的蒙特卡洛模拟：

---

A.4 与 IND-CPA 的联系

IND-CPA （选择明文攻击下的不可区分性）的具体定义为：

$\forall$ PPT 敌手不能区分两个相同长度的消息 $m_0$，$m_1$的密文 $\text{Enc}(pk, m_0)$ 与 $\text{Enc}(pk, m_1)$，其中 $m_0$ 和 $m_1$ 是敌手看到 $pk$ 后选取的。$\forall$ PPT 敌手 $\mathcal{A}$ 有：

$\dfrac{1}{2}\text{Adv}_{\text{IND}}(\mathcal{A}) = \left|\Pr\left[\begin{aligned} &(pk, sk)\leftarrow \text{Gen}(1^{\lambda}), (m_0, m_1)\leftarrow\mathcal{A}(pk), b\leftarrow\{0, 1\},\\ &c\leftarrow\text{Enc}(pk, m_b), b'\leftarrow \mathcal{A}(pk, c):b'=b \end{aligned} \right] - \dfrac{1}{2}\right|\leqslant \text{negl}(\lambda)$

可以参考下图进行理解：

如果我们利用 IND-CPA （选择明文攻击下的不可区分性）构建信道，那么我们或许可以看到一些有趣的现象。

让我们观察一下 IND-CPA 安全模型中 Challenger（对应防守方） 和 Adversary（对应攻击方）之间的交互过程：

• 输入端（Challenger）：挑战者均匀随机地选择一个秘密比特 $b \xleftarrow{\$} \{0,1\}$。如果我们将 $b$ 视为攻击信道的输入变量 $X$，则有：

  $P(X=0) = P(X=1) = \frac{1}{2}$

• 输出端（Adversary）：敌手 $\mathcal{A}$ 接收到密文 $c = \text{Enc}_k(m_b)$ 后，输出一个猜测比特 $b' \in \{0,1\}$。此时可以将敌手的输出 $b'$ 视为攻击信道的输出变量 $Z$。
• 攻击信道 $F$：这个系统恰好构成了一个以 $X$ 为输入、$Z$ 为输出的信道 $X \xrightarrow{F} Z$。

在密码学中，敌手 $\mathcal{A}$ 的 IND-CPA 优势定义为它猜对的概率与随机猜测的偏差：

$\text{Adv}_{\text{CPA}}(\mathcal{A}) = \left| \Pr[Z = X] - \frac{1}{2} \right| \times 2$

设 $p_0 = \Pr(Z=0\mid X = 0)$ 以及 $p_1 = \Pr(Z=1\mid X=1)$，对应地设 $\mathrm{Adv}_0 = 2p_0 - 1$，$\mathrm{Adv}_1 = 2p_1 - 1$，以及：

$\mathrm{Adv}_{\mathrm{CPA}} = \dfrac{\mathrm{Adv}_0 + \mathrm{Adv}_1}{2}$

为了便于计算，我们同时设 $\delta = \mathrm{Adv}_0 - \mathrm{Adv}_{\mathrm{CPA}}$，与此同时就有 $\mathrm{Adv}_1 = \mathrm{Adv}_{\mathrm{CPA}} - \delta$。

首先计算 $\Pr(Z=0)$，根据全概率公式：

$\Pr(Z=0) = \Pr(X = 0)\Pr(Z=0\mid X=0) + \Pr(X = 1)\Pr(Z=0\mid X=1)$

$\Pr(Z=0) = \frac{1}{2}p_0 + \frac{1}{2}(1 - p_1)$

将 $p_0 = \dfrac{1 + \mathrm{Adv}_{\mathrm{CPA}} + \delta}{2}$ 与 $p_1 = \dfrac{1 + \mathrm{Adv}_{\mathrm{CPA}} - \delta}{2}$ 代入化简可得：

$\Pr(Z=0) = \frac{1}{4}(1 + \mathrm{Adv}_{\mathrm{CPA}} + \delta) + \frac{1}{4}(1 - \mathrm{Adv}_{\mathrm{CPA}} + \delta) = \frac{1 + \delta}{2}$

同时：

$H(Z\mid X) = \frac{1}{2}H(Z\mid X=0) + \frac{1}{2}H(Z\mid X=1) = \frac{1}{2}H(p_0) + \frac{1}{2}H(p_1)$

在密码学中，由于敌手优势是可忽略的（即 $\mathrm{Adv}_{\mathrm{CPA}}, \delta \to 0$），我们可以利用二元熵函数在 $p=\frac{1}{2}$ 处的泰勒展开 $H\left(\frac{1+x}{2}\right) \approx 1 - \frac{x^2}{2\ln 2}$ 进行近似：

$\begin{aligned} I(X;Z) &= H\left(\frac{1 + \delta}{2}\right) - \frac{1}{2}\left[H\left(\frac{1 + \mathrm{Adv}_{\mathrm{CPA}} + \delta}{2}\right) + H\left(\frac{1 + \mathrm{Adv}_{\mathrm{CPA}} - \delta}{2}\right)\right]\\ &\approx \left(1 - \frac{\delta^2}{2\ln 2}\right) - \frac{1}{2}\left[\left(1 - \frac{(\mathrm{Adv}_{\mathrm{CPA}} + \delta)^2}{2\ln 2}\right) + \left(1 - \frac{(\mathrm{Adv}_{\mathrm{CPA}} - \delta)^2}{2\ln 2}\right)\right] \end{aligned}$

此时 $\delta^2$ 项被完美消去：

$I(X;Z) \approx \left(1 - \frac{\delta^2}{2\ln 2}\right) - \left(1 - \frac{\mathrm{Adv}_{\mathrm{CPA}}^2 + \delta^2}{2\ln 2}\right) = \dfrac{\left(\mathrm{Adv}_{\mathrm{CPA}}\right)^2}{2\ln 2}$

通过上式我们得到一个有趣的客观结论：基于密码学的攻击信道容量 $C$（即信息泄露量的上界）大致与密码学敌手优势 $\text{Adv}_{\text{CPA}}$ 的平方成正比。（更一般地，$C$ 的下界被 $\text{Adv}^2$ 限制住了）

更有趣的是，接下来我们设：

$\mathrm{Adv}_{\mathrm{D}} = \left|q - \frac{1}{2}\right|$

我们发现攻击信道容量可以写成一个统一的表达式：

$C(\mathrm{Adv}_\mathrm{D}) = \left(\frac{3}{2} - \mathrm{Adv}_\mathrm{D}\right)\left(1 - \log_2\left(\frac{3}{2} - \mathrm{Adv}_\mathrm{D}\right)\right) + \left(\frac{1}{2} - \mathrm{Adv}_\mathrm{D}\right)\log_2\left(\frac{1}{2} - \mathrm{Adv}_\mathrm{D}\right)$

防守的“漏报”和“误报”在信息论视角下是等价的，它们都是确定性的泄露，都会被黑客利用，从而影响防守方的机密性，可用性，资源损耗等等。

如果我们对这个统一公式求 $\mathrm{Adv}_\mathrm{D}$ 的导数：

$\frac{dC}{d\mathrm{Adv}_\mathrm{D}} = -1 + \log_2\left(\frac{\frac{3}{2} - \mathrm{Adv}_\mathrm{D}}{\frac{1}{2} - \mathrm{Adv}_\mathrm{D}}\right)$

当 $\mathrm{Adv}_\mathrm{D} \to 0$（即 $q \to \frac{1}{2}$）时，我们发现它的导数并不为 0：

$\left. \frac{dC}{d\mathrm{Adv}_\mathrm{D}} \right|_{\mathrm{Adv}_\mathrm{D}=0} = \log_2 3 - 1$

这意味着在 $q=\frac{1}{2}$ 处，攻击信道容量的图像有一个带有绝对值特征的V型尖点。这证明了黑客的战术切换不是平滑渐进的。跨越 $q=\frac{1}{2}$ 时，黑客必须进行突变式的战术相变，与我们前面的分析和图示一致。

A.5 对于攻击信道建模的总结

• 无论如何，防守方的响应状态越确定，黑客可能产生的最大威胁当量越大，一定的威胁当量可能不会对系统直接造成破坏（不会直接破防），但是会对防守方的资源等造成损耗，防守方存在沉默成本。 而值得一提的是，实际而言，防守方构建完全 $1/2$ 的信道并不现实。
• 攻击信道容量存在非零正尖点，说明尖点附近黑客需要考虑突变式战术相变，且黑客的威胁永远存在。也就是说，在这个模型下，我们证明了绝对的安全是不存在的。
• 一拳超人总有他应顾不暇的时候，而谜语人对对方造成的迷惑最大。可惜这个时候防守方的可用性却被摧毁了。
• 总的来说还是，这个模型的计算完全可以脱离“安全”这个概念而存在，所以笔者理解这就是一个套皮解释的工作。这里的互信息或者信道容量我们完全可以直接理解成能量，即这里所说的（最大）威胁当量。当量大不代表防守方真的攻破了。先随着防守方盲自评增加，但是还没达到一半的时候，黑客的优势在于找到防守方没有防住的部分；当防守方的盲自评进一步增加，超过一半之后，对于黑客来说，客观上他要造成更大的威胁就是直接去硬碰硬防守方防住的地方。中间的尖点就是因为黑客的策略在 $1/2$ 附近发生突变了。