一轮攻防的Naive理论分析

下面是题目原内容：

来源：安全通论作业一：数值分析攻击信道容量

内容：用matlab/python等作图工具，数值分析攻击信道容量。

要求：形成分析报告，字数不限。以PDF附件形式上传~

本来说是不用算的，然后结果我就把攻击信道容量算出来了。。。但是解释起来着实有点牵强，最后的理解还是攻击方能够产生的最大威胁当量。不过这个作业也算给了我一些比较好的启发，尝试基于学过的一些理论的内容，构建模型。虽然说是人家好像在十几年前就利用乔姆斯基范式研究过了哈哈哈（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}$ 也行，毕竟我们也是有相关约束在的。