G.O.S.S.I.P 阅读推荐 2023-04-04

今天要给大家推荐的论文是来自和北京大学谢涛教授研究组的论文SoK: Certified Robustness for Deep Neural Networks，该论文已发表在S&P 2023上。作为一篇综合性的SoK论文，这篇论文系统介绍了机器学习安全里一个蓬勃发展的方向：可验证的鲁棒性。

https://www.ieee-security.org/TC/SP2021/downloads/Oakland_PC_Report_2021.pdf

在机器学习的安全里，一种广泛存在的隐患是输入逃逸攻击（input evasion attacks）。具体来说，对于一个正常训练得到的高准确率的神经网络图片分类模型，很容易能找到微小到人眼无法识别的噪声，让神经网络以很高的置信度给出错误的预测结果。这一鲁棒性隐患不仅仅存在于图片分类模型，众多深度学习场景比如自动驾驶、入侵检测、机器控制等等都具有鲁棒性隐患，并且，在众多场景上都已经发现了具有100%成功率的输入逃逸攻击，并且生成的对抗样本往往还具有很高的迁移攻击成功率。因此，鲁棒性隐患对当今的深度学习系统构成了深远的挑战，特别是对于自动驾驶等信息物理系统（cyber-physical systems, CPS）这些安全性十分重要的场景。

（图源：Explaining and Harnessing Adversarial Examples, Goodfellow et al, ICLR 2015.）

为了衡量输入逃逸攻击下的鲁棒性隐患，一种经典的问题模型是(lp, ε)-adversary：攻击者对于给定的深度神经网络模型F和类别为y0的输入x0，寻找微小的扰动delta，其中delta的Lp范数需小于ε来保证攻击的隐蔽性，使得篡改后的输入x0 + delta能够欺骗模型来给出错误的分类结果，即F(x0+delta)≠y0。这里的Lp范数常常选用实际意义较浅显的L2范数（欧几里得距离）和L∞范数（逐维/逐像素最大更改），这里的ε阈值通常较小，以确保攻击的隐蔽性。

围绕着鲁棒性隐患特别是(lp, ε)-adversary，过去几年的研究主要围绕着一场“攻防竞赛”。在攻击侧，不断涌现出新的更强的白盒和黑盒攻击方法，这些方法对给定的深度神经网络模型能更有效地找到约束条件内的对抗样本(x0 + delta)。在防御侧，则往往是通过特定的神经网络训练方法如对抗训练（adversarial training）、对抗样本检测方法、模型后处理方法等来提高模型的鲁棒性。

然而，这场“攻防竞赛”存在着一项重大隐患——防御方法往往只针对已有攻击评估防御能力，而无法保证对未来更强有力的攻击，防御是否仍然有效。比如，一些防御方法在MNIST数据集上，使用FGSM攻击评估，仍有90%的鲁棒准确率，但在随后的更强攻击方法（如PGD攻击）或自适应攻击方法下，准确率却可下降到不足10%。解决这一隐患的需求催生出了可验证鲁棒性的研究。

根据本文的分析，可验证鲁棒性领域的研究可分为两个大类：鲁棒性验证方法（robustness verification approaches）和鲁棒训练方法（robust training approaches）。鲁棒性验证方法旨在对给定的模型、给定的输入数据点、和给定的扰动阈值ε，提供尽量紧的鲁棒性保证。鲁棒训练方法则是通过特定的训练算法来得到易于验证且具有高鲁棒性的模型，鲁棒训练方法往往利用到了鲁棒性验证方法的某些性质，从而使训练得到的模型对验证方法有很好的适配性。通常来说，为了在一种数据集上实现高可验证鲁棒性，作者会将鲁棒训练方法与鲁棒性验证方法结合——先用训练方法得到模型，再用验证方法去计算鲁棒性保证。当一个数据点能被验证具有鲁棒性保证时，从数学上作者就证明了在该数据点附近是不存在对抗样本的，也就不必再担心更强攻击方法的存在了，因此，作为防御方，上段所提出的隐患便不复存在。

从2017年至今，可验证鲁棒性领域经历了深刻的发展。在典型的图像分类数据集上，目前已经基本解决了小规模数据集（如MNIST）的可验证鲁棒分类问题，在中型规模数据集（如CIFAR-10）上提供一定的可验证鲁棒性，并在大规模数据集（如ImageNet）上取得了一定的进展。我们常常使用鲁棒准确率（Certified Accuracy）来衡量可验证的鲁棒性，这一指标衡量了在给定Lp范数和给定扰动范围阈值ε内，有多少比例的测试集数据可以被验证为总能得到正确的分类结果。

在MNIST上，允许每个像素点都有30%扰动的情形下（即L∞范数，ε=0.3），已经能达到93.4%的鲁棒准确率。30%的扰动范围实际上已经非常大，因为50%的扰动就能让任何输入变成半灰的图像从而不可能实现鲁棒分类。在CIFAR-10上，允许每个像素点扰动8/255时，我们能实现40%左右的鲁棒准确率。而在ImageNet上，仅能在L2范数的ε=2扰动阈值内实现大概42%的鲁棒准确率，在Linf范数下的鲁棒准确率则还不足20%。这意味着在大规模数据集上，可验证鲁棒分类还是一个待解决的问题。作者在https://sokcertifiedrobustness.github.io/leaderboard里，维护着这一领域最新的进展和突破。

实现可验证鲁棒是一个较为困难的任务，这一困难性的典型体现是，鲁棒性验证是一个NP完全问题。具体来说，对于一个仅含有ReLU作为激活函数的全连接分类神经网络F，对于任意给定输入x，精确计算L∞范数下的鲁棒性阈值ε，也就是max ε s.t. F(x) = F(x+delta) ∀delta, ||delta||∞ < ε是一个NP完全问题。进一步地，在L1范数下，得到这一阈值的常数比例的估计都是NP完全的。这意味着在当前阶段，对鲁棒性的完全验证（也就是精确计算出鲁棒性阈值ε）需要指数级别的复杂度，这对于大型神经网络是难以接受的。

这一局限性催生出了不完全验证方法。不完全验证方法不追求提供精确的阈值ε，而是退而求其次，只要求对精确的阈值求出一个下界。因此，不完全验证方法仍能提供鲁棒性的保证，只是这一保证不一定是最强的，而是相对保守的。不完全验证方法通常借助一些放缩来实现，比如对ReLU的线性放缩（之后将会介绍到），并且通常具有多项式时间的复杂度，因此可以运用于大型网络。在实践中，虽然不完全验证方法提供的保证较松，但对于特别训练过的网络具有很好的效果，也可以运用在完全验证方法中作为子程序来提供显著的加速。目前在大规模数据集上实现的可验证鲁棒性都是通过在特别训练过的网络上运用不完全验证方法来得到的。

本篇SoK的一大主要贡献是对鲁棒性验证方法提供了细致的分类和总结。

下面来介绍四种主要的鲁棒性验证方法：

1. 分支定界法（Branch-and-Bound） - 目前最高效的完全验证方法

分支定界法是一种通用的优化问题求解方法，被广泛运用于混合整数规划问题的求解。在深度神经网络的鲁棒性验证中，分支定界法也是一种很高效的方法。

深度神经网络模型常常使用ReLU作为非线性激活函数，因此可以视为线性映射与ReLU激活函数交替的叠加。

总体上，鲁棒性验证可以视为判断神经网络在一个输入区域内的最小值是否大于零，比如鲁棒分类就可以转化为判断神经网络对于正确类别与对于其他类别的差是否恒大于零。基于此，分支定界法的思想是，首先考察放缩后得到的下界是否大于零（若是，则结束，当前子问题鲁棒性得到验证）或者得到的上界是否小于零（若是，则结束，当前问题鲁棒性无法得到验证），若无法提前结束，结束定界步骤，进入分支步骤，根据神经网络的ReLU激活函数的状态，对当前优化问题进行分治（根据某个神经元处于激活态或者非激活态来划分输入空间，生成两个子问题），再递归验证子问题。注意到在子问题中，ReLU神经元处于激活态或者非激活态时均为线性映射：y=x或者y=0，因此递归生成的子问题会减少一项非线性约束，使得针对子问题的放缩会更紧。当所有非线性约束消失时，子问题归结为线性规划问题，因此递归是有限的。

在分支定界法里，快速的紧放缩，以及分支时神经元的选择是关键。快速的紧放缩通常借助下文将介绍的线性放缩法来实现，而分支时神经元的选择有一系列启发式算法。虽然分支定界法具有最差情况指数级别的复杂度，在实践中，最新的验证器α-β-CROWN已经可以实现对数十万神经元的神经网络在GPU上一两分钟内验证出解。

2. 线性放缩法（Linear Relaxation）- 广为使用的通用不完全验证方法

线性放缩法的主要思想是对神经网络的非线性激活函数进行线性放缩，下图展示了几种常见的线性放缩。其中(a)展示的是考虑单神经元的情况下最紧的线性放缩，在此放缩下，神经网络的验证为一线性规划问题。而(b)、(c)、(d)虽然是更为松弛的放缩，但可以让线性界在神经网络逐层间高效传导，因此效率更高。

线性放缩法的保守性随着网络的加深而逐渐增大，虽然效率较好，但对于一般的神经网络往往得到的鲁棒性保证过于保守。不过，如果将线性边界融合进训练方法，对于这样特殊训练出的神经网络，往往能得到比较不错的鲁棒性保证。

3. Lipschitz法 - 简单高效的不完全验证方法

Lipschitz常数定量化地衡量了一个函数的变化速度。

因为分类神经网络对每个类别会输出置信分数并选择置信分数最高的类别作为输出，如果我们知道一个神经网络的Lipschitz常数和对于未扰动的输入的置信分数，就可以使用不同类别间置信分数的差除以Lipschitz常数来得到可以接受的扰动阈值。

因此，更大的置信分数差和更小的Lipschitz常数是决定更好的可验证鲁棒性的两个主要因素。其中，让深度神经网络模型有更小的Lipschitz常数这一方向上有很多进展，这些进展主要可以分为两个流派。一个流派是通过训练时的正则化，来让神经网络的权重来调整到具有比较小的矩阵范数。另一个流派是通过设计特定的网络结构，来让网络自发的具有固定的Lipschitz常数。目前来说，后者取得的可验证鲁棒性更佳。比如，一种网络结构是将ReLU激活函数替换为L∞神经元，如下图所示。

4. 随机平滑化（Randomized Smoothing） - 目前最高效的概率性验证方法

随机平滑化方法是目前对大规模神经网络支持最好的可验证鲁棒性方法，它是唯一可以为大型ImageNet提供鲁棒性保证的方法，而作为代价，它对推断速度有一定牺牲，并且得到的保证不是确定性，而是和采样相关具有概率性。

随机平滑化方法与以上方法均有一定的不同，体现在它会对神经网络的推断过程进行修改，具有一个后处理的过程。这个后处理的过程是，在当前输入的周围以一定的分布（如高斯分布）采样一些噪声，将噪声叠加到输入上，再根据已有模型对这些噪声输入在各个类别上的分类概率，来选择概率最高的一个类别作为分类的输出结果。

随机平滑化方法的主要作用在于，对于输入上的微小扰动，以输入为中心的噪声分布仍具有一定的重叠，利用这个重叠，我们可以得到各个类别在扰动后分类概率的上下界，只要正确类别的下界仍大于其他所有类别的概率上界，我们就能保证鲁棒性。

经过数学分析，可以计算得出鲁棒扰动阈值的下界，这个下界和选定的噪声分布的种类及方差、和在未扰动输入上各类别的分类概率相关，并可以通过精细化的采样与抽象来得到更紧的扰动阈值。

随机平滑化方法可以视为通过噪声与投票，来人为地给本不平滑的分类系统注入平滑性（在一些工作中，可以推导出Lipschitz常数），从而提供鲁棒性的保证。在这一过程中我们可以看出，随机平滑化方法不需要知道深度神经网络模型的具体结构和权值信息，而只要求对模型的分类结果的访问权限即可，因此也被称为黑盒方法，并且可以与去噪模型如扩散模型（diffusion models）结合作为预处理组件，来对已有的不鲁棒的分类模型进行可验证的鲁棒化处理，因此具有比较广阔的运用空间。

实现可验证的鲁棒性，除了验证方法外，还需要鲁棒训练方法的加持。本文总结了设计鲁棒训练方法的三大主要思路：（1）正则化：在训练中添加额外的正则化项来鼓励神经网络通过训练达到某些性质，如ReLU神经元在领域内的稳定性，具有小的Lipscihtz常数等。（2）放缩：针对已有攻击实现鲁棒性的主要方法是对抗训练，在对抗训练中通过优化邻域内分类损失函数的近似最大值（通过基于梯度的对抗攻击查找）来实现鲁棒性。为了实现可验证的鲁棒性，作者对这一设计原则进行扩展，通过不完全验证方法得到分类损失函数的上界，并通过优化这一上界，来实现针对不完全验证方法的可验证鲁棒性。（3）数据增强：随机平滑化方法期望模型能对添加噪声的输入仍具有较高的分类准确度，因此，对于随机平滑化方法，一种广为使用的鲁棒训练思路就是使用噪声进行数据增强。这三大鲁棒训练方法的思路又可以引出许多具体的训练算法以及它们的结合。另外，作者可以主要到，鲁棒训练方法与鲁棒性验证方法高度相关——每种验证方法都有与之最为匹配的鲁棒训练思路。

除了对这一领域的已有进展进行总结外，本文的另一大主要贡献是对现有的神经网络验证方法开发出了综合的开源工具集VeriGauge。这一开源工具集提供了约20种常见鲁棒验证方法的开源实现，借助这一工具，本文提供了对主流验证方法的统一评测，具体评测结果在论文的附属网页https://sokcertifiedrobustness.github.io/benchmark/进行了细致的展示。根据评测结果，论文站在使用者的角度，在每种使用情形下对最适合的“鲁棒性验证方法+鲁棒训练方法”进行了推荐。

尽管这一论文主要集中在可验证鲁棒性这一具体方向上，但可验证鲁棒性是众多深度学习安全特别是深度学习验证技术的基石。具体来说，对于输入逃逸攻击的验证已经被直接扩展到语义变换攻击、输入局部补丁攻击（patch attacks）、生成模型攻击、输入分布偏移、全局逃逸攻击、荼毒和后门攻击等等情形下的安全性验证，并且，这些对于深度神经网络的验证方法也已经被扩展到其他机器学习模型上，如集成逻辑模型、决策树模型、生成模型、图神经网络等等。在具体的机器学习应用，如NLP和强化学习上，也已经有了成功的实践。

本文的最后用了整整一页多的篇幅讨论了这一领域的困难、挑战、开放问题，并提出了众多研究问题和方向，感兴趣的读者欢迎参阅原文，相信能从中获得不少研究上的启发。

网站：https://sokcertifiedrobustness.github.io/ （网站是个综合入口，论文链接、代码链接、和详细实验数据都可以通过网站查询到）

https://www.computer.org/csdl/proceedings-article/sp/2023/933600a094/

代码：https://github.com/AI-secure/VeriGauge