第45卷 第1期2022年1月计  算  机  学  报CHINESE JOURNAL OF COMPUTERSVol. 45No. 1Jan.2022 收稿日期:2020-04-20;在线发布日期:2021-07-09.本课题得到浙江省自然科学基金杰出青年项目(LR19F020003)、国家重点研发计划项目(2020YFB2103802)、国家自然科学基金项目(61772466, U1936215, U1836202)、中央高校基本科研业务费专项资金(浙江大学NGICS大平台)资助.纪守领(通信作者),博士,研究员,计算机学会(CCF)会员(66979M),主要研究领域为人工智能与安全、数据驱动安全、软件与系统安全、大数据分析.E-mail: sji@zju.edu.cn. 杜天宇,博士研究生,计算机学会(CCF)学生会员(9603239),主要研究领域为人工智能安全.邓水光,博士,教授,计算机学会(CCF)会员(06679S),主要研究领域为服务计算、边缘计算、流程管理和大数据等. 程 鹏,博士,教授,计算机学会(CCF)会员(38682M),主要研究领域为控制系统安全、物联网/信息物理融合系统、数据安全与隐私保护. 时 杰,博士,主要研究领域为人工智能安全与隐私等. 杨 珉,博士,教授,计算机学会(CCF)会员(10568M),主要研究领域为网络与系统安全. 李 博,博士,助理教授,主要研究领域为人工智能安全、机器学习安全与隐私、博弈论等.深度学习模型鲁棒性研究综述纪守领1) 杜天宇1) 邓水光1) 程 鹏2) 时 杰3) 杨 珉4) 李 博5)1)(浙江大学计算机科学与技术学院 杭州 310027)2)(浙江大学控制科学与工程学院 杭州 310027)3)(华为新加坡研究所 新加坡 138589 新加坡)4)(复旦大学计算机科学技术学院 上海 201203)5)(伊利诺伊大学香槟分校计算机科学学院 厄巴纳香槟 61822 美国)摘 要 在大数据时代下,深度学习理论和技术取得的突破性进展,为人工智能提供了数据和算法层面的强有力支撑,同时促进了深度学习的规模化和产业化发展.然而,尽管深度学习模型在现实应用中有着出色的表现,但其本身仍然面临着诸多的安全威胁.为了构建安全可靠的深度学习系统,消除深度学习模型在实际部署应用中的潜在安全风险,深度学习模型鲁棒性分析问题吸引了学术界和工业界的广泛关注,一大批学者分别从精确和近似的角度对深度学习模型鲁棒性问题进行了深入的研究,并且提出了一系列的模型鲁棒性量化分析方法.在本综述中,我们回顾了深度学习模型鲁棒性分析问题当前所面临的挑战,并对现有的研究工作进行了系统的总结和科学的归纳,同时明确了当前研究的优势和不足,最后探讨了深度学习模型鲁棒性研究以及未来潜在的研究方向.关键词 深度学习;对抗样本;鲁棒性分析;人工智能安全中图法分类号TP18        DOI号10.11897/SP.J.1016.2022.00190Robustness Certification Research on Deep Learning Models: A SurveyJI Shou-Ling1) DU Tian-Yu1) DENG Shui-Guang1) CHENG Peng2) SHI Jie3) YANG Min4) LI Bo5)1)(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)2)(College of Control Science and Engineering, Zhejiang University, Hangzhou 310027)3)(Huawei Singapore Research Center, Singapore 138589,Singapore)4)(School of Computer Science, Fudan University, Shanghai 201203)5)(Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana-Champaign 61822, USA)Abstract  In the era of big data, breakthroughs in theories and technologies of deep learning have provided strong support for artificial intelligence at the data and the algorithm level, as well as have promoted the development of scale and industrialization of deep learning in a large number of tasks, such as image classification, object detection, semantic segmentation, natural language processing and speech recognition. However, though deep learning models have excellent per-formance in many real-world applications, they still suffer many security threats. For instance, it is now known that deep neural networks are fundamentally vulnerable to malicious manipula-tions, such as adversarial examples that force target deep neural networks to misbehave. In re-cent years, a plethora of work has focused on constructing adversarial examples in various do-mains. The phenomenon of adversarial examples demonstrates the inherent lack of robustness of deep neural networks, which limits their use in security-critical applications. In order to build a safe and reliable deep learning system and eliminate the potential security risks of deep learning models in real-world applications, the security issue of deep learning has attracted extensive at-tention from academia and industry. Thus far, intensive research has been devoted to improving the robustness of DNNs against adversarial attacks. Unfortunately, most defenses are based on heuristics and thus lack any theoretical guarantee, which can often be defeated or circumvented by more powerful attacks. Therefore, defenses only showing empirical success against attacks, are difficult to be concluded robust. Aiming to end the constant arms race between adversarial at-tacks and defenses, the concept of robustness certification is proposed to provide guaranteed ro-bustness by formally verifying whether a given region surrounding a data point admits any adver-sarial example. Robustness certification, the functionality of verifying whether the given region surrounding a data point admits any adversarial example, provides guaranteed security for deep neural networks deployed in adversarial environments. Within the certified robustness bound, any possible perturbation would not impact the prediction of a deep neural network. A large number of researchers have conducted in-depth research on the model robustness certification from the perspective of complete and incomplete, and proposed a series of certification methods. These methods can be generally categorized as exact certification methods and relaxed certifica-tion methods. Exact certification methods are mostly based on satisfiability modulo theories or mixed-integer linear program solvers. Though these methods are able to certify the exact robust-ness bound, they are usually computationally expensive. Hence, it is difficult to scale them even to medium size networks. Relaxed certification methods include the convex polytope methods, reachability analysis methods, and abstract interpretation methods, etc. These methods are usu-ally efficient but cannot provide precise robustness bounds as exact certification methods do. Nevertheless, considering the expensive computational cost, relaxed certification methods are shown to be more promising in practical applications, especially for large networks. In this sur-vey, we review the current challenges of model robustness certification problem, systematically and scientifically summarize existing research work, and clarify the advantages and disadvantages of current research. Finally, we explore future research directions of model robustness certifica-tion research.Keywords  deep learning; adversarial example; robustness certification; artificial intelligence se-curity1 引 言受益于计算力和智能设备的飞速发展,全世界正在经历第三次人工智能浪潮.人工智能以计算机视觉、序列处理、智能决策等技术为核心在各个应用领域展开,并延伸到人类生活的方方面面,包括自适应控制[1]、模式识别[2]、游戏[3]以及自动驾驶[4]等安全攸关型应用.例如,无人驾驶飞机防撞系统(Air-craft Collision Avoidance System, ACAS)使用深度神经网络根据附近入侵者飞机的位置和速度来预测最佳行动.然而,尽管深度神经网络已经显示出解决复杂问题的有效性和强大能力,但它们仅限于仅满足最低安全完整性级别的系统,因此它们在安全关键型环境中的采用仍受到限制,主要原因在于在大多数情况下神经网络模型被视为无法对其预测行为进行合理解释的黑匣子,并且在理论上难以证明其性质.1 9 1 1期 纪守领等:深度学习模型鲁棒性研究综述随着深度学习的对抗攻击领域日益广泛,对抗样本的危险性日益凸显[5-7],即通过向正常样例中添加精细设计的、人类无法感知的扰动达到不干扰人类认知却能使机器学习模型做出错误判断.以图像分类任务为例,如图1所示,原始样本以57.7%的置信度被模型分类为“熊猫”,而添加对抗扰动之后得到的样本则以99.3%的置信度被错误地分类为“长臂猿”,然而对于人而言,对抗样本依然会被视为熊猫.由于这种细微的扰动通常是人眼难以分辨的,因而使得攻击隐蔽性极强、危害性极大,给ACAS等安全攸关型应用中部署的深度学习模型带来了巨大的安全威胁.图1 对抗样本示例[5]为了防御对抗样本攻击,研究者进行了一系列的防御方法探索[8-13].然而,即使是被广泛认可并且迄今为止最成功的ℓ∞ 防御[5],它的ℓ0鲁棒性比未防御的网络还低,并且仍然极易受到ℓ2的扰动影响[14].这些结果表明,仅对对抗攻击进行经验性的防御无法保证模型的鲁棒性得到实质性的提升,模型的鲁棒性需要一个定量的、有理论保证的指标进行评估.因此,如果要将深度学习模型部署到诸如自动驾驶汽车等安全攸关型应用中,我们需要为模型的鲁棒性提供理论上的安全保证,即计算模型的鲁棒性边界.模型鲁棒性边界是针对某个具体样本而言的,是保证模型预测正确的条件下样本的最大可扰动范围,即模型对这个样本的分类决策不会在这个边界内变化.具体地,令输入样本x的维度为d,输出类别的个数为K,神经网络模型为f:ℝd→ℝK,输入样本的类别为c=argmaxfj(x),j=1,2,…,K,在ℓp空间假设下,模型对x提供-鲁棒性保证表明模型对x的分类决策不会在这个样本ℓp空间周围 大小内变化.在本文中,我们首先阐述了深度学习模型鲁棒性分析现存的问题与挑战,然后从精确与近似两个角度对现有的鲁棒性分析方法进行系统总结和科学归纳,并讨论了相关研究的局限性.最后,我们讨论了模型鲁棒性分析问题未来的研究方向.2 问题与挑战目前,深度神经网络的鲁棒性分析问题的挑战主要集中在以下几个方面:(1)神经网络的非线性特点.由于非线性激活函数和复杂结构的存在,深度神经网络具有非线性、非凸性的特点,因此很难估计其输出范围,并且验证分段线性神经网络的简单特性也已被证明是NP完全问题[15].这一问题的难点在于深度神经网络中非线性激活函数的存在.具体地,深度神经网络的每一层由一组神经元构成,每个神经元的值是通过计算来自上一层神经元的值的线性组合,然后将激活函数应用于这一线性组合.由于这些激活函数是非线性的,因此这一过程是非凸的.以应用最为广泛的激活函数ReLU为例,当ReLU函数应用于具有正值的节点时,它将返回不变的值,但是当该值为负时,ReLU函数将返回0.然而,使用ReLU验证DNN属性的方法不得不做出显著简化的假设,例如仅考虑所有ReLU都固定为正值或0的区域[16].直到最近,研究人员才能够基于可满足性模理论等形式方法,对最简单的ReLU分段线性神经网络进行了初步验证[15].由于可满足性模理论求解器难以处理非线性运算,因此基于可满足性模理论的方法通常只适用于激活函数为分段线性的神经网络,无法扩展到具有其它类型激活函数的神经网络.(2)神经网络的大规模特点.在实际应用中,性能表现优秀的神经网络通常具有大规模的特点.因此,尽管每个ReLU节点的线性区域可以划分为两个线性约束并有效地进行验证,但是由于线性片段的总数与网络中节点的数量成指数增长[17-18],对整个网络进行精确验证是非常困难的.这是因为对于任何大型网络,其所有组合的详尽枚举极其昂贵,很难准确估计输出范围.此外,基于可满足性模理论的方法严重受到求解器效率的限制,仅能处理非常小的网络(例如,只有10到20个隐藏节点的单个隐藏层[19]),无法扩展到大多数现实世界中的大型网络,而基于采样的推理技术也需要大量数据才能在决策边界上生成严格的准确边界[20].总之,由于不同学者所处的研究领域不同,解决问题的角度不同,所提出的鲁棒性分析方法也各有侧重,因此亟需对现有的研究工作进行系统的整理和科学的归纳、总结、分析.典型的模型鲁棒性分析方法总结如表1所示,主要分为两大类:(1)精确方2 9 1 计  算  机  学  报 2022年法:可以证明精确的鲁棒性边界,但计算复杂度高,在最坏情况下计算复杂度相对于网络规模是成指数增长的,因此通常只适用于极小规模的神经网络;(2)近似方法:效率高、能够扩展到复杂神经网络,但只能证明近似的鲁棒性边界.表1 典型的模型鲁棒性分析方法总结方法 精确 模型 效率 激活函数 领域Reluplex[15]√ FCN ○ ReLU 图像PLANET[21]√ FCN ○ ReLU 图像Huang et al.[22]√ FCN ○ arbitrary 图像Tjeng et al.[23]√ FCN, CNN ReLU 图像Szgedy et al.[12]× FCN ● ReLU 图像Hein et al.[24]× FCN ● ReLU 图像SDP[25]× FCN ○ ReLU 图像Wong et al.[26]× FCN, CNN ReLU 图像Dvijotham[27]× FCN 任意 图像Fast-lin/Fast-lip[28]× FCN ● ReLU 图像CROWN[29]× FCN ● 3种 图像CNN-Cert [30]× FCN, CNN ● ReLU 图像CLEVER[31]× 任意 ● 任意 图像PixelDP[32]× FCN, CNN 任意 图像Cohen et al.[33]× 任意 任意 图像AI2[34]× FCN, CNN ReLU 图像DeepZ[35]× FCN, CNN ● 3种 图像DiffAI[36]× FCN, CNN ReLU 图像DeepPoly[37]× FCN, CNN ● 3种 图像RefineAI[38]× FCN, CNN ReLU 图像k-ReLU[39]× FCN, CNN ReLU 图像IBP[40]× FCN, CNN ReLU 图像Chen et al.[41]× Tree-based / 图像Wang et al.[42]× k-nearest / 图像Huang et al.[43]× CNN ReLU 文本POPQORN[44]× RNN 2种 文本Jia et al.[45]× RNN ● 2种 文本Shi et al.[46]× RNN 2种 文本Zügner et al.[47]× GNN ReLU 图Bojchevski[48]× GNN ReLU 图  注:√=满足,×=不满足;效率:○=低,=中,●=高.3 精确方法精确方法主要是基于离散优化(Discrete Opti-mization)理论来形式化验证神经网络中某些属性对于任何可能的输入的可行性,即利用可满足性模理论(Satisfiability Modulo Theories, SMT)或混合整数线性规划(Mixed Integer Linear Program-ming, MILP)来解决此类形式验证问题.这类方法通常是通过利用ReLU的分段线性特性并在搜索可行解时尝试逐渐满足它们施加的约束来实现的.图2梳理了典型模型鲁棒性精确分析方法的相关研究工作.图2 典型模型鲁棒性精确分析方法概念图3.1 基于可满足性模理论的方法  Katz等人提出具有实数算术原理的SMT求解器Reluplex[15],通过扩展单纯形(simplex)算法(用于解决LP实例的标准算法)以支持ReLU约束,并验证了激活函数为ReLU的前馈神经网络的鲁棒性.虽然他们使用了线性规划作为与SMT的比较,但没有提到对线性规划的任何优化方法.此外,这种方法效率非常低,对于一个约含100个神经元的小规模网络来说,计算一个样本至少需要若干个小时.因此,虽然Reluplex可以形式上地验证神经网络的一些特性,但由于计算成本太高,无法扩展到实际模型中.此外,Reluplex通过将ReLU网络描述为一个分段线性函数来进行分析,它使用一个矩阵乘法都为线性的理论模型.但实际上,由于浮点算法的存在,计算机上的矩阵乘法并非线性的.Huang等人[22]研究了图像分类器的安全性,例如划痕、相机角度或照明条件的变化对分类结果造成的影响,以及在原始图像的较小邻域内的分类不变性.他们为前馈多层神经网络开发了一种新的自动验证框架,利用SMT将输入样本周围的无限区域离散到一组点,然后在这个区域内进行有限穷举搜索并逐层传播分析,以验证神经网络的局部鲁棒性.Ehlers等人[21]考虑了整个神经网络的全局线性逼近,并使用整数算法来提升SMT线性逼近范围的精确性,减少了SMT求解器的调用次数.Narodytska等人[49]研究了二值神经网络(Bi-narized Neural Networks)[50]的鲁棒性验证问题,将二值神经网络编码为布尔公式,然后利用布尔可满足性(Boolean Satisfiability,SAT)问题的典型求解方法进行求解,或是基于反例引导(counterexam-ple-guided)搜索的思想,更有效地利用这些编码的结构来求解最终的SAT公式[51].这种编码是深度3 9 1 1期 纪守领等:深度学习模型鲁棒性研究综述神经网络的第一个精确布尔表示,不依赖于网络结构的任何近似值,这意味着这种编码使我们能够通过研究SAT域中的相似属性来研究BNN的属性,并且将这些属性从SAT映射回神经网络域是精确的.但是这种方法只适用于二值神经网络,难以扩展到其他类型的神经网络.然而,这些基于SMT的方法具有很高的计算复杂度,仅对非常小的网络才有意义.此外,由于SMT难以处理非线性运算,因此基于SMT的方法通常只适用于激活函数为分段线性的神经网络.3.2 基于混合整数线性规划的方法  Cheng等人[52]将计算模型鲁棒性边界的问题形式化为混合整数规划(Mixed Integer Program-ming, MIP)问题,并且设计了一系列启发式算法进行网络函数的编码,以大大减少MIP求解器的运行时间.具体地,他们利用基于分支定界算法的MIP求解器处理含有整数变量的非线性函数的编码,利用著名的big-M编码策略[53]的变体将许多非线性表达式线性化.此外,他们还定义了一个数据流分析[54],该数据流分析用于生成相对较小的big-M作为加速MIP解决的基础.Lomuscio等人[55]研究了ReLU前馈神经网络的可达性问题,并将其形式化为线性规划问题求解.具体地,他们提出的方法能够检查一个特定的输出,比如一个漏洞,是否能够由一个给定的神经网络产生,而对抗样本则可以被视为一种特殊的可达性情况,在这种情况下输入集相对于特定输入是受限的,因此他们提出的公式具有一定的通用性.特别地,他们对线性规划中的浮点运算处理方式进行优化,并采用了一种较为高效的线性规划求解方法,相比于Reluplex[15]中作为对比的线性规划方法效率大大提升.例如,Reluplex只能分析最多300个ReLU约束条件,而他们的方法能够轻松处理500多个ReLU约束条件.Xiang等人[56]研究了多层感知机(Multi-Layer Perception, MLP)的可达性问题和鲁棒验证问题,基于仿真验证思想[57],利用大量仿真结果中的信息估计MLP的输出可达集并进行鲁棒性验证.具体地,他们引入了称为最大灵敏度的概念,对于激活函数为单调函数的一类多层感知机,将最大灵敏度的计算公式形式化为一组凸优化问题,然后通过解决凸优化问题来计算最大灵敏度.然后,利用结果获得最大灵敏度,通过检查有限数量的MLP采样输入的最大灵敏度属性来执行MLP的可达集合估计.最后,基于输出可达集的估计结果开发了一个自动验证MLP的方法,并介绍了安全验证在具有两个关节的机器人手臂模型中的应用.Bunel等人[58]利用分支定界理论[59]将现有方法纳入到一个统一框架中,收集并公开了一个基准数据集(benchmark),其中包含现有方法所用到的测试用例以及新的benchmark,并使用这一基准数据集对现有算法进行首次大规模实验比较.在此框架的基础上,他们发现了验证算法的可改进之处,特别是在计算边界的方式、考虑的分支类型以及指导分支的策略上.与先前的技术相比,这些改进实现了将近两个数量级的加速.Tjeng等人[23]将分段线性神经网络的鲁棒性验证问题形式化为混合整数线性规划问题,通过精心设计的预求解方法和有效的剪枝算法显著地减少了搜索空间,相比于基于SMT的方法计算速度提升了若干个数量级,因此可以用于计算含有超100,000个神经元的神经网络的鲁棒边界.特别地,他们首次证明了MNIST分类器在有界ℓ∞范数 =0.1扰动下的精确对抗精度:4.38%的测试样本在这个扰动范围内至少存在一个对抗样本,而其余测试样本在这个扰动范围内是鲁棒的,即不存在对抗样本.虽然这类方法在小规模网络上取得了不错的结果,但是将它们扩展到更大规模的网络仍然是一个极具挑战性的问题.此外,这种方法也只适用于分段线性神经网络,即神经网络中只包含最大池化层和ReLU激活函数这两种非线性形式.4 近似方法由于在ℓp-ball假设空间内,对于激活函数为ReLU的神经网络,计算其精确的鲁棒性边界是一个NP完备(NP-Complete,NPC)问题[15],因此大多数研究者通常利用近似方法计算模型鲁棒性边界的下界,下文提到模型鲁棒性边界时通常也指的是这个下界.此外,对抗攻击[12]可以得到模型鲁棒性边界的上界[24].因此,精确的模型鲁棒性边界可以由上界和下界共同逼近.这类方法通常基于鲁棒优化思想,通过解决公式(1)的内层最大化问题来估计模型鲁棒性边界:θ=argminθmaxx ~∈Dk(x)L(y,fθ(x~)) (1)其中,x代表正常样本,x~代表对抗样本,Dk(x)代表对抗样本可能存在的范围,y代表样本真实标签,fθ代表以θ为参数的模型,L代表损失函数.图3梳4 9 1 计  算  机  学  报 2022年理了典型模型鲁棒性近似分析方法的相关研究工作.图3 典型模型鲁棒性近似分析方法概念图4.1 基于凸松弛的方法  Wong等人[26]采用凸多面体松弛方法来计算在范数有界扰动下的模型鲁棒边界,并将其形式化为一个线性规划问题求解.如图4所示,左图中黑色的点代表原始样本,正方形表示可扰动范围,即对抗样本可能存在的区域.经过神经网络的层层计算之后,正方形变成了非凸的多边形,因此他们的主要思想就是求多边形边框的凸近似,将非凸优化转换成凸优化问题.此外,他们证明了该线性规划的对偶问题可以用与反向传播网络相似的深层网络表示,从而提出了一种非常有效的优化方法,给出了有理论保证的鲁棒边界.但是,这种方法只讨论了ReLU这一种分段线性激活函数和最简单的前馈神经网络,未考虑其他类型尤其是非线性激活函数,也并未考虑带有卷积层或残差结构的复杂神经网络.并且,这种方法计算复杂度较高,在最坏情况下计算复杂度与神经元的个数成平方,因此也不适用于在Ima-geNet等大规模数据集上训练的大型神经网络.图4 Wong&Kolter[26]采用的凸多面体松弛方法示意图为了克服上述挑战,Wong等人[60]改进了上述方法,将其扩展到了带有卷积层或残差结构的复杂神经网络,并且神经网络的激活函数不再局限于ReLU.具体地,他们采用了非线性随机投影(Ran-dom Projection)理论[61],提出了一种基于共轭函数的、从对偶结构中派生对偶网络的方法,使得算法的计算复杂度降低至与网络的神经元个数成线性关系.与[26]提出的共轭形式不同的是,[60]不再假设网络由线性操作和激活函数组成,而是选择使用任意k函数序列,这简化了对典型神经网络架构中常见的最大池