神经网络的安全保障真的安全吗？如何计算可信的鲁棒性认证

# 神经网络中的安全性保证真的安全吗？如何计算可信赖的鲁棒性认证

来源：https://arxiv.org/html/2606.23858

¹研究基金会与技术 - 希腊，伊拉克利翁，希腊  
电子邮件：{mercoyris,varsosk,fgeo}@ics.forth.gr  
²克里特大学，伊拉克利翁，希腊  
³加泰罗尼亚高等研究机构，巴塞罗那，西班牙  
电子邮件：[email protected]  
⁴莱里达大学，莱里达，西班牙  

###### 摘要

AI安全中的一个主要挑战是对抗样本的存在——轻微失真的输入会导致神经网络 (NN) 误分类。为了缓解这一问题，最近的研究集中于计算*鲁棒性认证*，该认证针对给定输入，确定在不破坏网络预测的情况下，输入可以承受的最大失真。鲁棒性认证可以解释为轴对齐的超矩形（*多维区间*）。大多数现有方法侧重于最大化认证的*体积*，但最近的计算不可行性结果表明，在合理时间内无法计算体积最优的认证。我们引入了*边心距*度量——输入与区间某一面之间的最小松弛量，并展示了如何在与输入域直径成*线性*次数的 NN 验证器（*预言机*）调用中计算*边心距最优*的认证。此外，我们证明，即使*忽略*预言机成本，也不可能存在体积最优且基于预言机的算法。同时，我们引入了*对偶认证*——一个包含某类所有实例的区间——从而为鲁棒性认证提供*边心距最小*的上界。我们还介绍了 ParallelepipedoNN¹ 系统，并在标准 MNIST 和 Fashion MNIST 基准上进行了评估。与现有工作在相同数据集上的初步比较表明，在最小边长方面至少有两倍的改进。

## 1 引言

神经网络 (NN) 已成功应用于各种机器学习任务，实现了高性能和实证准确性。然而，人们观察到输入的轻微失真可能会破坏网络的预测。这种失真的输入被称为*对抗样本* [28, 7]，并推动了*鲁棒性认证*的研究。在鲁棒性认证中，给定一个输入，我们必须计算出在不导致误分类的情况下，该输入可以承受的最大失真。通过计算每个维度的容忍区间并取其笛卡尔积，我们得到一个*轴对齐的超立方体*或*多维区间*。这种几何解释允许我们将鲁棒性认证表述为一个*优化问题*，使得寻找最佳认证对应于针对给定度量进行优化。该领域最广泛使用的方法是将鲁棒性认证表述为受约束的凸优化问题，然后使用一阶微分方法进行数值求解 [30, 20, 18, 12]。这种方法还利用强大的 NN 框架（例如 PyTorch、TensorFlow）来高效计算必要的梯度。尽管效率很高，但这种方法是有代价的：为了应用于现实世界的 NN，网络需要进行*线性松弛*。由于 ReLU 激活函数不可微，传统的 NN 只能用导致非线性约束的布尔变量描述，因此线性松弛实际上是一种近似。特别地，对 NN 进行线性松弛会导致误报，将安全的输入标记为对抗样本。这导致鲁棒性认证人为地变小，低估了网络的局部稳定性。这种不确定性阻碍了鲁棒性认证在实践中的适用性。例如，考虑常见的鲁棒性认证质量度量——*体积* [30, 19, 18]。假设为了认为网络是鲁棒的，我们需要达到体积阈值 \(v_1\)。然而，我们计算出的认证体积为 \(v_2\)，且 \(v_2 < v_1\)。如果我们无法确定认证是否是*有效的*（由于近似），我们就会面临一个困境：是否信任这个网络？我们*知道*存在一个具有更大体积的认证，但我们没有找到它。线性松弛的近似性质引入了一个*不确定性*因素：我们无法确定结果是真阳性还是假阳性。为了消除这个不确定性，我们需要一个*精确的* NN 验证器 [9, 8, 26, 13]，它每次都会给出一个确定的“是”或“否”答案。但即使我们使用这样的验证器来计算鲁棒性认证，仍然存在一个问题：如何将多个验证查询转化为一个*有意义的*认证？我们*需要*一种*算法*来驱动这些查询。

在本文中，我们提出了这样一种算法，并对相关理论进行了澄清。我们引入了*边心距*度量，它衡量输入与最近对抗样本之间的距离。然后，我们证明，如果存在一个体积为 \(v_2\) 的认证，那么也存在一个边心距至少为 \(\sqrt[d]{v_2/d}\) 的认证（见命题 3）。因此，如果我们在输入空间中只进行 \(O(d)\) 次验证器查询（即与输入域直径成线性关系），就可以计算出边心距最优的认证。此外，我们证明，即使忽略验证器的成本，任何计算体积最优认证的算法都需要指数数量的查询。因此，边心距是比体积更易于处理且更实用的质量度量。此外，我们引入了*对偶认证*的概念。在常规认证中，我们寻找包含输入且不包含对抗样本的区间。在对偶认证中，我们寻找一个包含给定类所有实例的区间。该区间必然包含对抗样本，因此给出了鲁棒性认证的*上界*：如果这个包含整个类的区间很小，那么任何鲁棒性认证都必须更小。相比之下，常规认证提供的是*下界*。因此，这两个认证共同为输入周围的稳健区域提供了一个边界。为了一般性，我们用任意度量 \(\mu\) 来论证我们的结果。我们证明了，对于体积度量，不可能存在一个 \(O(d^k)\) 的算法（\(k\) 为某个固定常数）来找到最优认证，即使我们能够直接访问一个 NN 验证器（即，我们可以在假设的时间内调用它）。但当我们使用边心距度量时，存在一个算法可以在 \(O(d)\) 次验证器调用中找到最优认证。我们还证明，最优边心距认证可以通过*贪婪*过程构建。注意，这与经典的最优\(L_\infty\) 球（即，超立方体）认证不同；最优边心距认证可能不是对称的，因此其体积严格大于最优\(L_\infty\) 球。这很重要，因为\(L_\infty\) 对抗攻击并不一定是寻找对抗样本的最有效方法；事实上，更复杂的攻击可能会在不同的方向上造成更小的扰动。然而，鲁棒性认证必须对所有可能的对抗失真提供保障。

在走向算法之前，我们在第 2 节中介绍了多维区间代数。然后，在第 3 节中，我们定义了鲁棒性算子，特别是*约束*算子，该算子从区间中排除一个对抗样本，同时保持边心距最优。我们展示了如何扩展它来处理多个对抗样本，产生一个*自下而上*的算子，该算子计算给定 NN 的边心距最优认证。我们还讨论了*对偶认证*以及一个*自上而下*的算子。在第 4 节中，我们描述了如何将 NN 验证器与这些算子结合使用，并展示了一个用于边心距最优认证的算法，该算法进行 \(O(d)\) 次验证器调用。此外，我们还展示了如何利用对偶认证来验证边心距最优认证。我们还在第 5 节中证明了下界：即使忽略了验证器成本，也不可能存在计算体积最优认证的多项式时间算法。我们在第 6 节中评估了我们的方法，在几种度量上将其与基线和现有软件进行了比较。然后我们在第 7 节中总结了相关工作，并在第 8 节中作了总结。我们的主要结论是：如果比较两个鲁棒性认证，一个体积为 \(v_1\)，另一个体积为 \(v_2\)，且 \(v_1 > v_2\)，我们*知道*对于该 NN *不存在*这样的认证。我们将我们的算法实现在 ParallelepipedoNN 系统中，并在标准 MNIST 和 Fashion MNIST 数据集上对多种度量进行了评估。值得注意的是，与现有软件的初步比较显示，在认证的最小边长方面有两倍的改进，在认证的直径方面至少有一个数量级的改进。

## 2 多维区间

我们首先介绍 Sunaga 的*区间代数*的一些基础结果 [27]。首先，我们将 \(\leq \subseteq \mathbb{R} \times \mathbb{R}\) 关系推广到多维空间。对于两个向量 \(\boldsymbol{\ell}, \boldsymbol{u} \in \mathbb{R}^d\)，我们记 \(\boldsymbol{\ell} \leq \boldsymbol{u}\) 当且仅当对所有 \(i \in [d]\) 都有 \(\ell_i \leq u_i\)，并记 \(\boldsymbol{\ell} < \boldsymbol{u}\) 当且仅当对所有 \(i \in [d]\) 都有 \(\ell_i < u_i\)。**定义 1.** 给定点 \(\mathbf{x} \in \mathbb{F}\)，我们用 \([\boldsymbol{\ell}, \boldsymbol{u}]\) 表示包含 \(\mathbf{x}\) 的区间，其中 \(\boldsymbol{\ell} \leq \boldsymbol{x} \leq \boldsymbol{u}\)。我们用 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 表示 \(\mathbb{F}\) 中所有包含 \(\mathbf{x}\) 的区间构成的集合。区间是轴对齐的超矩形（即，超矩形体）。同时，域 \(\mathbb{F}\) 本身也是一个区间，即 \([\mathbf{0}, \mathbf{1}]\)，但没有任何要求。区间由其对角线端点 \([\boldsymbol{\ell}, \boldsymbol{u}]\) 完全描述。对于某个 \(\rho > 0\)，我们称形如 \([\mathbf{x} - \rho \mathbf{1}, \mathbf{x} + \rho \mathbf{1}]\) 的区间为*均匀*区间。均匀区间在几何上表示轴对齐的*超立方体*。此外，对于任何向量 \(\mathbf{v} \geq \mathbf{0}\)，我们称形如 \([\mathbf{x} - \mathbf{v}, \mathbf{x} + \mathbf{v}]\) 的区间为*对称*区间。最后，*任意*区间由两个向量 \(\mathbf{a}, \mathbf{b} \geq \mathbf{0}\) 刻画，使得 \([\mathbf{x} - \mathbf{a}, \mathbf{x} + \mathbf{b}]\)。见图 1 (左)。

![图1 左：区间族：均匀、对称和任意。右：区间度量：\(\mathcal{A}\) 直径，\(\pi\) 周长，\(v\) 体积，\(\alpha\) 最小边，\(\varpi\) 边心距。](图片)

### 2.1 区间运算与区间格

回顾一下，我们用 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 表示 \(\mathbb{F}\) 中包含输入 \(\mathbf{x}\) 的区间空间。空间 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 通过简单的代数运算具有高度结构化的性质。

###### 定义 2  
设 \([\boldsymbol{\ell}, \boldsymbol{u}], [\boldsymbol{m}, \boldsymbol{n}] \in \mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\)。我们定义以下运算：
1.  \([\boldsymbol{\ell}, \boldsymbol{u}] + [\boldsymbol{m}, \boldsymbol{n}] \overset{\Delta}{=} [\boldsymbol{\ell} + \boldsymbol{m}, \boldsymbol{u} + \boldsymbol{n}]\)
2.  \([\boldsymbol{\ell}, \boldsymbol{u}] \sqcup [\boldsymbol{m}, \boldsymbol{n}] \overset{\Delta}{=} [\min\{\boldsymbol{\ell}, \boldsymbol{m}\}, \max\{\boldsymbol{u}, \boldsymbol{n}\}]\)
3.  \([\boldsymbol{\ell}, \boldsymbol{u}] \sqcap [\boldsymbol{m}, \boldsymbol{n}] \overset{\Delta}{=} [\max\{\boldsymbol{\ell}, \boldsymbol{m}\}, \min\{\boldsymbol{u}, \boldsymbol{n}\}]\)

容易看出 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 在定义 2 的运算下是*封闭*的。两个区间的求和对应于众所周知的*闵可夫斯基和*。我们有时会滥用符号，记 \(\mathbf{x} + [\boldsymbol{\ell}, \boldsymbol{u}]\) 而不是 \([\mathbf{x}, \mathbf{x}] + [\boldsymbol{\ell}, \boldsymbol{u}]\)（其他运算类似）。\(\sqcup, \sqcap\) 运算由 Sunaga [27] 引入，并揭示了潜在的*格*结构。一个偏序集是格，当任意两个元素都存在*最小上界 (lub)* 和*最大下界 (glb)*。在 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 格结构中，lub 由*并*运算 \(\sqcup\) 给出，glb 由*交*运算 \(\sqcap\) 给出。

###### 定理 2.1 (区间格 [27])  
区间空间 \(\mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 在 \(\subseteq\) 下构成一个完备*格*，分别以 \(\sqcup, \sqcap\) 为*交*和*并*运算。

### 2.2 区间目标函数

我们接着讨论区间度量。一个*度量* \(\mu: \mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}} \to \mathbb{R}_{\geq 0}\) 是一个函数，它为区间赋予一个正实数值。平凡区间必须具有零度量，并且度量必须关于集合包含关系单调。我们还引入了新颖的*边心距*度量。

###### 定义 3 (区间度量)  
考虑区间 \(I = \mathbf{x} + [\boldsymbol{\ell}, \boldsymbol{u}] \in \mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\)，且 \(\boldsymbol{\ell} \leq \boldsymbol{u}\)。那么我们定义以下度量：
- 边心距: \(\varpi(I) = \min\Big\{ \min_{i \in [d]} (x_i - \ell_i), \min_{j \in [d]} (u_j - x_j) \Big\}\)
- 最小边: \(\alpha(I) = \min_{i \in [d]} u_i - \ell_i\)
- 周长: \(\pi(I) = \sum_{i \in [d]} u_i - \ell_i\)
- 体积: \(v(I) = \prod_{i \in [d]} u_i - \ell_i\)
- 直径: \(\mathcal{A}(I) = \max_{i \in [d]} u_i - \ell_i = \|u_i - \ell_i\|_\infty\)

定义 3 中的所有度量都描绘在图 1 (右) 中。在我们的实验评估中，我们还使用了*平均边长* \(\overline{E}(I)\)，定义为 \(\overline{E}(I) = \pi(I)/d\)。边心距²衡量输入 \(\mathbf{x}\) 与相应超矩形某一面之间的最小“松弛量”。在下文中，我们将看到鲁棒性认证的面将被对抗样本所界定。因此，我们可以使用边心距来衡量输入 \(\mathbf{x}\) 与最近对抗样本之间的最小距离。命题 3 关联了上述度量。省略的证明见附录 0.A。

\{restatable propositionnumericalgeometricmean\}
对于区间 \(I \in \mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\) 和定义 3 中的度量，我们有：
\[
\mathcal{A}(I) \geq \frac{1}{d} \cdot \pi(I) \geq \sqrt[d]{v(I)} \geq \alpha(I) \geq 2 \cdot \varpi(I) \quad (1)
\]

## 3 鲁棒性算子

这里我们将抽象地工作，以考虑鲁棒性认证的组合方面及其与多维区间的关系。特别地，考虑一个神经网络域 \(\mathbb{F}\) 和一个对抗样本集 \(\mathcal{V} \subset \mathbb{F}\)。此外，令 \(\mathbf{x} \in \mathbb{F}\) 为给定输入。一个鲁棒性认证将是一个区间 \(I \in \mathbb{I}(d)|_{\mathbf{x}}^{\mathbb{F}}\)，使得 \(\mathbf{x} \in I\) *且* \(I \cap \mathcal{V} = \varnothing\)。关于如何获得对抗样本集 \(\mathcal{V}\) 的技术细节将在第 4 节讨论。目前，我们假设这个集合是完备的，意思是如果我们成功地排除了它的成员，域 \(\mathbb{F}\) 中没有其他输入会破坏预测。这让我们可以专注于一个微妙但重要的问题：*从所有候选区间 \(J \subseteq \mathbb{F} \setminus \mathcal{V}\) 中，我们应该选择哪一个？* 我们分两步进行。首先，我们考虑排除单个对抗样本 \(\mathbf{v} \in \mathcal{V}\) 的情况，定义边心距最优的“小步”³*约束*算子。然后，我们将其推广到多个对抗样本，定义“大步”*自下而上*算子，同时确保边心距最优性。最后，我们讨论由大步*自上而下*算子返回的对偶认证。

### 3.1 小步鲁棒性

![图2 左：约束算子。右：域空间如何划分为锥体。锥体 \(\overline{C_i}\) 包含所有导致修改上端点 \(\boldsymbol{u}\) 的第 \(i\) 个坐标的对抗样本。](图片)

现在我们讨论我们的“小步”鲁棒性算子。对于输入 \(\mathbf{x}\)，考虑一个区间 \(I\) 使得 \(\mathbf{x} \in I\)。此外，令 \(\mathbf{v} \in I\) 为我们想要排除的对抗样本。我们的小步鲁棒性算子将做到这一点，以*边心距最优*的方式从区间 \(I\) 中排除对抗样本 \(\mathbf{v}\)。我们将此操作称为*约束*，并记作 \(I / \mathbf{v}\)。随后，令 \(I' = I / \mathbf{v}\)。回忆一下，区间本质上是一组 \(2d\) 个不等式，每个不等式对应输入空间 \(d\) 个坐标之一的下界或上界，可以紧凑地写作 \(I = \mathbf{x} + [\boldsymbol{\ell}, \boldsymbol{u}]\)，其中 \(\boldsymbol{\ell} \leq \mathbf{0} \leq \boldsymbol{u}\)。为了确保 \(\mathbf{v} \notin I'\)，只需确保这些不等式中的一个不成立即可。为了实现边心距最优，我们选择维度 \(k \in [d]\)，使得 \(\|v_k - x_k\|\) 最大。如果 \(v_k - x_k > 0\)，则必须减小上界以排除 \(\mathbf{v}\)，通过修改 \(\boldsymbol{u}\) 的第 \(k\) 维来产生一个 \(\boldsymbol{u}'\)，使得 \(\mathbf{v}\) 不在 \(I'\) 中；否则，相应地增加下界。这里一个重要技术细节是，我们使用一个精度常数 \(\delta > 0\) 来确保区间的“有意义的”缩减。当修改上界时，我们设置 \(u_k' = v_k - x_k - \delta\)，对称地用于下界。这有两个目的。首先，它以“严格意义”排除 \(\mathbf{v}\)（否则 \(\mathbf{v}\) 会在 \(I'\) 的边界上）。其次，它避免了无穷小的修改。正如我们稍后将看到的，这对于保证我们算法的终止是必要的。此过程如图 2 (左) 所示，并正式定义如下。

###### 定义 4 (约束算子)  
考虑输入 \(\mathbf{x} \in \mathbb{F}\)，区间 \(I = \mathbf{x} + [\boldsymbol{\ell}, \boldsymbol{u}]\)，其中 \(\boldsymbol{\ell} \leq \mathbf{0} \leq \boldsymbol{u}\)，以及一个对抗样本