跳到正文
原文

面向神经网络验证的高效符号推理

Efficient Symbolic Reasoning for Neural-Network Verification

arXiv· arXiv:2303.13588· Zi Wang, Somesh Jha, Krishnamurthy, DvijothamUniversity of Wisconsin-Madison; Google Research本站收录· 23 天前· 原文发表防御

论文速读

防御

据论文 PDF 整理(AI 生成),以原文为准

作者提出用二次关系符号化编码神经网络验证问题并松弛为 SDP 的框架;在 MNIST 的 ℓ2 认证上,ShenBao 认证数平均比 BCP 高 60%。

威胁模型针对输入的 ℓp 对抗扰动(评测用 ℓ2,半径 ǫ),攻击者扰动输入使分类改变;受害系统为 MNIST 上的 ReLU 前馈网络(small:单隐层 64 节点;medium:双隐层 128/64 节点)。

问题
神经网络易受对抗扰动影响,而精确验证是 NP/coNP-hard;作者认为基于线性关系的非符号抽象域难以处理非线性扰动和非常规结构,需要在效率与精度间取得平衡。
方法
提出 symbolic reasoning 框架:给网络各计算组件赋予符号,用二次关系精确编码计算与攻击约束,把验证问题写成二次程序,再用 Shor 松弛转成可多项式时间求解的 SDP;并给出 ReLU、ℓp 扰动、度量学习和 DEQ 的编码。
实验与结果
在 MNIST 的 ℓ2 认证任务上实现工具 ShenBao,与 BCP 比较:200 个测试点上 ShenBao 认证数多数设置更高,作者称平均高 60%;例外是 BCP 训练的模型上 BCP 略高。ShenBao 每个 SDP 需 102.4–426.2 秒,BCP 约 2 秒完成全部。
局限与可以继续做的
作者指出瓶颈是求解 SDP,其实现用 CPU 上的 MOSEK,比 GPU 版 BCP 慢;作者称多层网络 FGL 估计的 SDP 没有近似保证([62] 的开放问题),哪种二次编码松弛更好也未探索。实验只覆盖 MNIST 上两个 ReLU 前馈网络的 ℓ2 数据依赖认证。
实验设置small DNN (single hidden layer with 64 ReLU nodes)、medium DNN (two hidden layers with 128 and 64 nodes) · MNIST · Accuracy、PGD 攻击后正确数 等
威胁模型
针对输入的 ℓp 对抗扰动(评测用 ℓ2,半径 ǫ),攻击者扰动输入使分类改变;受害系统为 MNIST 上的 ReLU 前馈网络(small:单隐层 64 节点;medium:双隐层 128/64 节点)。目标是认证给定半径内预测不变。
被测模型
small DNN (single hidden layer with 64 ReLU nodes)medium DNN (two hidden layers with 128 and 64 nodes)
基准
MNIST
指标
AccuracyPGD 攻击后正确数认证正确数(ShenBao / BCP,200 个测试点)认证运行时间(秒)
AI 导读针对神经网络易受对抗攻击等问题,研究者提出名为符号推理的程序推理框架用于神经网络验证。该框架以语义灵活的符号域和表达力强的二次关系为核心,将许多神经网络验证问题编码为二次规划,再松弛为可高效求解的半定规划。作者称其可验证不同场景下的多种神经网络性质,尤其是非符号域难以处理的情形,有望带来新的理论见解与实用工具。

针对神经网络易受对抗攻击等问题,研究者提出名为符号推理的程序推理框架用于神经网络验证。该框架以语义灵活的符号域和表达力强的二次关系为核心,将许多神经网络验证问题编码为二次规划,再松弛为可高效求解的半定规划。作者称其可验证不同场景下的多种神经网络性质,尤其是非符号域难以处理的情形,有望带来新的理论见解与实用工具。

深度解读

6个问题,点开问题读完整回答

  1. 这篇论文试图解决什么问题?

    作者提出把神经网络验证编码为二次程序再松弛为 SDP 的符号推理框架,以处理非符号域难以验证的任务。

    核心问题:如何高效且精确地验证神经网络在对抗扰动下的性质,尤其是非线性扰动和非常规结构这类基于线性关系的抽象域难以处理的任务。

    • 问题场景:DNN 已集成进现代软件系统,但对对抗攻击脆弱;作者称多种防御机制后来仍被攻破,社区因此关注可认证鲁棒性(certifiable robustness)。
    • 现有方法的不足:精确验证已被证明是 NP/coNP-hard([29, 30, 61]),必须过近似;作者认为基于抽象解释的方法多以线性关系定义抽象域,对非线性扰动和非常规架构需要许多 ad-hoc 技术。
    • 核心观察:二次关系表达力强,许多难组合优化问题可写成二次程序;作者认为可以把多种 DNN 验证任务精确编码为二次程序(QP),再松弛为可高效求解的半定规划(SDP)。
    • 论文提出的内容:名为 symbolic reasoning 的程序推理框架,包含符号域(symbolic domain)和二次关系两个组件;给出多种攻击与激活的二次编码,并在 ℓ2 鲁棒性认证任务上做了实证。
    • 威胁模型:
      • 攻击者目标:对输入施加 ℓp 范数扰动(p ≥ 1),使模型预测改变。
      • 扰动约束:||x̃ − x||p ≤ ǫ,论文重点编码 ℓ2 与 ℓ∞,附录 A 给出 ℓ1 和一般 ℓp 的编码。
      • 受害系统:以 ReLU 为激活的前馈分类网络;第 4 节还讨论度量学习模型和深度均衡模型(DEQ)。
      • 防御方目标:认证在给定半径内预测不变(数据依赖分析),或估计网络的形式全局 Lipschitz 常数(数据独立分析)。
  2. 有哪些相关研究?

    相关工作分为抽象解释验证、SDP 验证与 Lipschitz 估计、以及 SDP 求解改进三类,作者称本文把这些工作背后的范式统一并推广。

    基于抽象解释的神经网络验证

    • Gehr 等 [23](AI2)、Singh 等 [58]、Wang 等 [60]——定义抽象域过近似输入并把网络执行重新解释,实现 sound 验证。论文指出这类方法的抽象域通常用线性关系定义,处理非线性计算需要 ad-hoc 技术。
    • Wong 与 Kolter [63]——用线性规划(LP)松弛认证问题;Katz 等 [30] 的 Reluplex 用 SMT 精确验证,论文称其为指数时间验证器。

    用 SDP 做 DNN 验证与 Lipschitz 估计

    • Raghunathan 等 [53]——提出 ℓ∞ 鲁棒性认证的 SDP 松弛;[52] 设计了针对两层网络的 SDP 认证与训练方法。
    • Fazlyab 等 [22]——用 SDP 估计多层网络的 ℓ2 Lipschitz 常数;Wang 等 [62] 给出 [22] 的组合式解释并推广到 ℓ∞,还证明 [22] 和 [52] 的 SDP 就是 Equation (7) 的 Shor 松弛(原始与对偶形式)。
    • 论文转述:[35] 称 [22] 无法迁移到 ℓ∞ 情形,[53] 认为 [52] 只适用于两层网络;作者认为从本框架看这些 SDP 足够通用,这些迁移是直接的。

    SDP 验证的质量与效率改进

    • Zhang [66] 研究 SDP 松弛何时无精度损失;Dathathri 等 [20] 设计可在 GPU 上实现的一阶 SDP 算法并扩展到 CIFAR 规模网络;Newton 与 Papachristodoulou [46]、Xue 等 [65] 利用 chordal sparsity 加速 DNN 诱导的 SDP 求解。
    • Salman 等 [55] 试图统一高效鲁棒性认证工作并提出凸松弛障碍;论文指出他们只研究了 LP 松弛、未能纳入 SDP 认证方法 [53],作者称本文可视为对 [55] 的补充,因为 SDP 比 LP 更强([14] 证明多项式规模 LP 与 SDP 之间存在精度差距)。

    基线与基准:实验部分的基准工具是 BCP [37](结合 ℓ2-Lipschitz 常数与区间域的认证方法),另用 PGD 攻击 [39] 做对照;数据集为 MNIST [36]。

    作者将本文定位为:从这些既有 SDP 工作中蒸馏出统一的符号推理框架,说明其适用范围超出原有任务,并为验证问题提供 QP/SDP 新表示。

  3. 论文如何解决这个问题?

    框架把网络各组件符号化、用二次关系精确编码验证任务得到 QP,再用 Shor 松弛转成 SDP 求解。

    整体思路:类似经典符号执行,框架"执行"DNN 并生成精确刻画验证问题的优化程序——不是可满足性程序而是 QP;再用 Shor 松弛把难解的 QP 转成凸的 SDP,在多项式时间内求解。框架名为 symbolic reasoning,两个核心组件是符号域和二次关系。

    符号化执行与二次编码

    • 给每个组件函数的输入和输出各配一个符号,用二次关系约束它们;仿射变换是线性的因此也是二次的,关键在激活函数的编码。
    • ReLU 有两种解释:(i) slope-restricted 解释(来自 [22]):任意两点斜率在 [0,1],编码为 ((z − z̃) − (y − ỹ))(z − z̃) ≤ 0;(ii) 精确解释(来自 [53]):y ≤ z、z ≥ 0、(z − y)z ≤ 0 三个二次不等式。
    • Remark 3.2 给出另一种精确编码:引入分支符号 s,用 s(s − 1) = 0、(s − 1/2)y ≥ 0、z = sy;作者称 slope-restricted 解释可视为不考虑执行状态的 stateless 解释。
    • 扰动编码:ℓ2 球写为 Σ(xi − x̃i)² ≤ ǫ²;ℓ∞ 写为对每个 i 有 (xi − x̃i)² ≤ ǫ²;附录 A 用 Hölder 不等式编码 ℓ1 和一般有理数 p 的 ℓp 约束。

    数据依赖分析(局部认证)

    • 固定输入 a,量化 ℓp 扰动下 f(a) 的最大变化,得到 QP(Equation 5):最大化 vz + c,约束包括 ReLU 计算、仿射变换和 ||x − a||p ≤ ϵ;作者称该 QP 精确编码验证问题。
    • 对 ℓ2 情形用 Shor 松弛:定义 PSD 变量 V(由 1、z、x 构成,分解为 Z、X、Y 等块),代入 yi = wi x + bi 后得到 SDP(Equation 6),含逐神经元的二次约束和 tr(X) − 2xᵀa + aᵀa − ǫ² ≤ 0。
    • 多层网络只需为每层的输入输出引入更多符号并按同样方式约束,再同样松弛。

    数据独立分析(FGL 估计)

    • 目标是估计形式全局 Lipschitz 常数(FGL,[62] 定义):所有激活被视为独立时的最大梯度算子范数,是 Lipschitz 常数的上界。
    • 用 ∆x、∆y、∆z 表示两点差,QP(Equation 7)为最大化 v∆z,约束 (∆zi − ∆yi)∆zi ≤ 0、∆yi = wi ∆x、||∆x||p ≤ 1;作者称 [22] 和 [52] 的 SDP 就是它的 Shor 松弛。

    框架的扩展应用

    • 度量学习:模型把表示层输出归一化到单位球并输出最近锚点的类;作者推导 (z̄ − õ)² − (z̄ − o)² 的符号等价于最小化 (o − õ)z,因此验证度量学习模型与标准分类模型相同。
    • DEQ 模型:隐层输出 z 同时反馈回隐层输入(不动点);FGL 估计的 QP 只需把 ∆yi = wi ∆x 改为 ∆yi = wi ∆x + ui ∆z,其余不变。
    • 附录 B 给出其他激活的编码:slope-restricted 解释只需导数上下界 a、b,用 (∆z − a∆x)(∆z − b∆x) ≤ 0;非代数激活(如 tanh)用分段线性函数任意精度逼近,再以 ReLU 编码为积木构造(以 ReLUθ 为例)。

    求解与理论结果

    • QP 一般是 NP-hard(如 MAXCUT 可写成 QP),因此用 Shor 松弛:原始形式把标量变量松弛为多维向量、去掉 dyadic 矩阵的 rank-1 要求得到 SDP;对偶形式即 Lagrangian 松弛(附录 C)。
    • Theorem 6.1:两层网络 FGL 估计的 SDP 最优值 O = minh nλmax(M + diag(h))(h 各分量之和为 0),即只需检查 M + diag(h) 的最大特征值;作者称该界比 [52] 的界更紧,并给出例子。
  4. 论文做了哪些实验?

    在 MNIST 的 ℓ2 认证任务上,ShenBao 认证数多数设置高于 BCP(作者称平均高 60%),但每个 SDP 需 102.4–426.2 秒。

    实验设置

    • 任务:ℓ2 数据依赖认证——认证 200 个测试点在指定半径的 ℓ2 扰动下仍被正确分类;选此任务是因为没有同框架的现成工具、但有基准工具可比。
    • 被测网络:两个 ReLU 前馈网络,small(单隐层 64 节点)和 medium(双隐层 128、64 节点),在 MNIST(10 类)上训练。
    • 训练模式:自然训练(ǫ = 0)、BCP 训练(small ǫ = 0.5,medium ǫ = 1.0)、PGD 训练(small ǫ = 0.5,medium ǫ = 1.0);small 训练 60 epoch,medium 训练 100 epoch。
    • 工具:ShenBao 用 MATLAB CVX 加 MOSEK 求解器实现;基准为 BCP;另用 PGD 攻击测对抗准确率作为认证正确率的上界 sanity check。
    • 指标:Accuracy(无攻击正确数)、PGD(攻击后正确数)、ShenBao 与 BCP 各自的认证正确数,分母均为 200 个测试点。
    • 运行环境:48 核 Intel Xeon Silver 4214(2.20GHz)、258GB 内存、8 块 RTX 2080 Ti;ShenBao 的 MOSEK 只能跑 CPU,BCP 在 GPU 上运行。

    主结果

    Table 1:200 个测试点上的认证正确数(ShenBao / BCP),按模型、训练方式和攻击半径列出。

    表格较宽,可左右滑动

    模型(训练方式)半径PGDShenBaoBCP
    small(自然训练,Acc 200)0.318112658
    small(自然训练)0.5138705
    small(自然训练)0.790200
    small(BCP 训练,Acc 198)0.3192186188
    small(BCP 训练)0.5190177176
    small(PGD 训练,Acc 198)0.3196193159
    medium(PGD 训练,Acc 199)0.71951770
    medium(PGD 训练)1.3167900

    (据 Table 1;省略的行:small BCP 训练 0.7(156/158)、small PGD 训练 0.5(178/72)与 0.7(161/12)、medium BCP 训练 0.7/1.0/1.3(151/158、126/128、100/105)、medium PGD 训练 1.0(142/0)。)

    • 作者称 ShenBao 一致优于 BCP,例外是 BCP 训练的模型(如 small BCP 训练、半径 0.3 时 186 对 188);作者解释 BCP 训练会正则化模型使其界更紧,即便如此 ShenBao 仍接近。
    • 作者称平均而言框架比基准好 60%(摘要与第 5 节均为此数)。
    • 作者指出一个观察:PGD 训练的 medium 模型在半径 0.7 时 ShenBao 认证 177/200(约 88%),而 BCP 完全无法认证;作者称这说明 PGD 训练的模型可达到与 BCP 训练相当甚至更好的可认证鲁棒性。

    认证速度

    • Table 2:ShenBao 求解 small 模型单个 SDP 平均 102.4 秒,medium 模型 426.2 秒;BCP 认证全部 200 个点分别约 2.1 秒和 1.8 秒。
    • MNIST 有 10 类,ShenBao 认证一个输入需解 9 个相互独立的 SDP,可并行;表中记录的是求解一个 SDP 的平均时间,BCP 记录的是全部 200 点的总时间。
    • 作者解释瓶颈在于使用通用 SDP 求解器 MOSEK 且只能跑 CPU,而 BCP 用 GPU 实现;作者称与 Reluplex 这类指数时间验证器相比,框架是多项式时间且能处理实际规模的网络。

    其他消融与分析

    • 论文未做其他消融实验;理论分析见第 6.2 节:作者转述 [62] 证明两层网络 FGL 的 SDP 松弛对 ℓ∞ 有 K_G(Grothendieck 常数)近似保证、对 ℓ2 有 √(π/2) 近似保证,且分别在 P ≠ NP 和唯一博弈猜想下最优([11]、[51])。
    • 作者指出多层网络 FGL 估计的 SDP 没有近似保证,[62] 将其列为开放问题。
    • 作者证明 Theorem 6.1 并给出其界比 [52] 更紧的例子(附录 E)。
  5. 有什么可以进一步探索的点?

    作者指出 SDP 求解效率是瓶颈、多层 FGL 无近似保证、编码选择未探索;实验只覆盖 MNIST 上两个 ReLU 网络的 ℓ2 认证。

    作者指出的局限与后续方向

    • 求解效率瓶颈(第 5 节 RQ2、第 6.1 节):框架依赖现成 SDP 求解器,作者的实现中比基准慢;作者称求解验证任务诱导的 SDP 超出本文范围,并希望激励面向 DNN 验证的专用 SDP 求解算法。
    • 多层 FGL 无近似保证(第 6.2 节):多层 DNN 的 FGL 估计 SDP 没有近似保证,作者转述 [62] 将其作为开放问题。
    • LP 与 SDP 的精度差距(第 6.2 节):作者认为研究 DNN 验证问题是否也存在类似 [14] 的 LP/SDP 精度差距是有趣的问题。
    • 编码选择(第 6.2 节):同一问题的二次编码不唯一,等价 QP 的松弛可能给出不同解;作者称探索哪种编码给出更好的松弛是有趣的问题,但超出本文范围。
    • 用 SDP 约束训练网络(第 6.2 节):作者认为分析 SDP、发现适合一阶方法的替代目标以训练具有期望性质的网络是有前景的方向。

    实验覆盖范围

    • 被测网络为 MNIST 上的两个 ReLU 前馈网络:small(单隐层 64 节点)和 medium(双隐层 128/64 节点),共 2 个。
    • 实证任务只有 ℓ2 数据依赖认证;度量学习、DEQ、ℓ∞/ℓ1/一般 ℓp 编码和其他激活只给出推导,未做实验。
    • 基准工具为 BCP,对照攻击为 PGD;每个设置为 200 个测试点,论文未报告重复次数。
    • 攻击半径:small 为 0.3/0.5/0.7,medium 为 0.7/1.0/1.3;训练模式为自然、BCP、PGD 三种。
    • 论文未报告 ShenBao 认证结果与真实鲁棒性之间差距的度量(认证正确数只与 PGD 对抗准确率上下夹逼)。
  6. 总结一下论文的主要内容

    作者提出把 DNN 验证编码为 QP 再松弛为 SDP 的符号推理框架,在 MNIST ℓ2 认证上认证数多数高于 BCP,但求解慢。

    这是一篇神经网络验证方法的论文:针对精确验证 NP/coNP-hard、而基于线性关系的抽象域难以处理非线性扰动和非常规结构的问题,作者提出 symbolic reasoning 框架。

    • 方法:给网络各计算组件配符号,用二次关系精确编码计算与攻击约束,把验证任务写成 QP,再用 Shor 松弛转成可多项式时间求解的 SDP;框架可组合、易适配不同架构。
    • 覆盖的任务:数据依赖的 ℓp 鲁棒性认证、数据独立的 FGL 估计;并推导了度量学习模型(验证等价于标准分类模型)和 DEQ 模型的编码;附录给出 ℓ1/一般 ℓp 和其他激活(含 ReLUθ)的编码。
    • 理论结果:作者称 [22] 和 [52] 的 SDP 就是 FGL 估计 QP 的 Shor 松弛;证明 Theorem 6.1,把两层网络 FGL 的 SDP 最优值表示为 nλmax(M + diag(h)) 的最小化,并称该界比 [52] 更紧。
    • 实证:在 MNIST 的 ℓ2 认证任务上实现工具 ShenBao(CVX + MOSEK),与 BCP 比较 200 个测试点的认证数;ShenBao 多数设置更高,作者称平均高 60%,例外是 BCP 训练的模型上 BCP 略高。
    • 代表性数字:small PGD 训练模型半径 0.3 时 ShenBao 认证 193/200、BCP 159;medium PGD 训练模型半径 0.7 时 ShenBao 177/200、BCP 为 0(Table 1)。
    • 代价与结论:ShenBao 求解单个 SDP 平均 102.4 秒(small)和 426.2 秒(medium),BCP 约 2 秒完成全部 200 点(Table 2);作者认为框架为验证任务提供了 QP/SDP 新表示,可带来矩阵分析、近似理论等新工具,并希望激励专用 SDP 求解算法的研究。

相关论文

共同使用 MNIST
再看 3 篇
共同使用 MNIST
阅读原文arxiv.org