离散对抗攻击与次模优化及其在文本分类中的应用
Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification
作者把文本离散对抗攻击形式化为集合函数优化,证明两类文本分类器上该函数次模,并提出梯度引导贪心与句词联合改写攻击。
目标攻击(targeted attack):最大化分类器对指定目标标签的输出概率。
- 为文本等离散输入生成对抗样本比连续数据更难:梯度法不直接适用、替换组合空间指数增长,且难以保持原文语义和句法。
- 把离散攻击形式化为集合函数最大化,证明其在两类文本分类器(简化 W-CNN、一维隐单元 RNN)上次模,使贪心有 1−1/e 近似保证;并提出梯度引导贪心词改写与句级+词级联合改写流程。
- 在 News、Trec07p、Yelp 三任务攻击 WCNN 和 LSTM:λw=20% 时对抗准确率最低至 16.5%(LSTM、News,Table 2);仅词级攻击时 Algorithm 3 成功率高于两种基线且耗时更低(Table 3);5 人人工评估(各 n=60)认为生成文本与原文质量接近(Table 4)。
- 次模证明依赖简化假设(如无 dropout/softmax 的 W-CNN、一维隐单元 RNN);只测 WCNN 与 LSTM 两个模型、三个英文分类任务;人工评估仅 5 人、每人 60 条;论文未专门讨论局限章节。
- 威胁模型
- 目标攻击(targeted attack):最大化分类器对指定目标标签的输出概率。攻击者能计算被攻击分类器的梯度(用梯度引导搜索),对每个特征最多 k−1 种替换、最多改 m 个特征;受害系统为文本分类器(WCNN、LSTM),论文未用 black-box/white-box 术语标注威胁模型。
- 被测模型
- WCNNLSTM
- 基准
- Fake/Real NewsTrec07pYelp reviews
- 指标
- adversarial test accuracyattack success rate (SR)timehuman evaluation (Task I accuracy, Task II 1–5 分)
研究者提出一种针对文本分类器的离散对抗攻击方法,将离散输入上的攻击形式化为集合函数优化任务。论文在简化假设下证明该集合函数对一些常见神经网络文本分类器是次模的,从而保证使用贪心算法的攻击具有 1-1/e 近似因子,并利用被攻击分类器的梯度引导贪心搜索。在三个文本分类任务上的实验显示,该优化方案相比多种基线显著提升了攻击能力与效率;作者还采用句子与词语联合改写技术保持原文语义和句法,并通过人类主观评估验证了生成对抗文本在质量与语义连贯性上的表现。
深度解读
这篇论文试图解决什么问题?
为文本等离散输入生成对抗样本:组合空间指数级、梯度法不直接适用,且难以保持原文语义句法。
核心问题:如何为文本等离散输入结构快速且有效地生成对抗样本,同时保持原文的语义和句法。
- 问题场景:对抗样本是对输入的微小修改,能改变分类器输出却不易被人察觉。作者指出,连续数据(图像、音频)上的攻击已成功,但文本、代码等离散结构上生成对抗样本更难。
- 现有方法的不足(按论文说法):梯度法不直接适用于离散结构,其变体(模型对 embedding 层可微时)效率高但成功率差;逐特征替换的组合空间随输入长度指数增长,求最优解不可行;已有的字符级/词级贪心启发式方法慢,且何时有效缺乏理论理解。
- 保持功能性的困难:作者指出现有方法要么改动过多特征、要么改变原意,例如 [19] 改动多达 50% 的词仅获 30% 成功率,[18] 用完全不同的词替换,[21] 插入无关句子,这些改动容易被人发现。
- 论文的核心观察:作者把离散攻击写成集合函数上的优化问题,并证明在两类常用文本分类器上该集合函数是次模(submodular)的,从而贪心算法有 1 − 1/e 近似保证。
- 论文提出的内容:一个离散攻击通用框架、梯度引导的贪心词级改写算法(Gradient-Guided Greedy Word Paraphrasing)、句级与词级联合改写技术,以及在三个文本分类任务上的实验验证。
- 威胁模型:
- 目标:目标攻击(targeted attack),最大化分类器对指定目标标签 y 的输出概率(Problem 1)。
- 知识:攻击者可计算被攻击分类器对词 embedding 的梯度(Algorithm 3 用梯度引导搜索);论文未用 white-box/black-box 术语标注。
- 能力:每个特征最多 k−1 种候选替换,最多改 m 个特征(约束 klk0 ≤ m);实验中词改写比例 λw=20%。
- 受害系统:文本分类器(WCNN、LSTM),任务为假新闻检测、垃圾邮件过滤、情感分析。
有哪些相关研究?
相关工作分连续数据攻击、离散/文本攻击、保持语义的改写三类;基线为 [19] 的贪心与 [18] 的梯度法。
连续数据(图像/音频)上的对抗攻击与防御
- Szegedy et al. [4] 发现深度神经网络图像分类器可被微小像素扰动欺骗;Goodfellow et al. [5]、DeepFool [6]、Carlini & Wagner [8] 等延续这一方向。
- 防御方面,论文提到对抗训练 [5, 13] 是现有最先进的防御,但构建鲁棒分类器仍困难(Athalye et al. [14])。
离散/文本输入上的攻击
- 词或字符级替换攻击:用连续词 embedding 或设计的打分函数选替换词,已用于攻击 NLP 分类器 [15, 16, 22, 23, 24, 25, 18, 19, 26, 27, 20] 和 sequence-to-sequence 模型 [17, 28, 29, 30]。
- Ribeiro et al. [31] 用语义等价规则调试 NLP 模型;论文指出这类工作只在单一输入结构(词或字符)内考虑攻击,没有联合攻击,也未考虑句子层面的影响。
- Jia and Liang [21] 通过插入额外句子攻击阅读理解系统;论文认为这超出了本文范围,因为该做法改变了原文含义。
- 另有工作关注对词表外术语的鲁棒性 [32] 和 embedding 空间表示 [33],论文说明它们不被视为对抗样本。
基线方法与基准
- 基线:[19](Kuleshov et al., 2018)的 objective-guided greedy 方法,按函数值逐词贪心替换;[18](Gong et al., 2018)的梯度方法,按一阶泰勒展开选同义词替换。
- 基准/数据集:Fake/Real News(6336 篇,5336 训练/1000 测试)、Trec07p 垃圾邮件语料(75,419 封,10% 作测试)、Yelp reviews(560,000 训练/38,000 测试),三个任务与 [19] 相同。
本文定位:作者称与 [31] 等只考虑单一输入结构的工作不同,本文做句级与词级联合改写;与 [19] 的贪心相比,本文用梯度幅值引导搜索,一轮可替换多个词;理论上也统一了梯度法(解松弛问题)与贪心法(次模假设下有近似保证)两类启发式。
论文如何解决这个问题?
把攻击写成集合函数最大化,证明次模性保证贪心近似比,再用梯度引导贪心加句词联合改写实现。
整体思路:把离散对抗攻击形式化为集合函数上的优化问题,证明该函数在两类文本分类器上是次模的,从而贪心算法有 1 − 1/e 近似保证;据此设计梯度引导贪心词改写与句级+词级联合改写的完整攻击流程。
问题设定与形式化
- 输入 x = [x1, …, xn],每个特征最多 k−1 种替换;变换 T 由索引向量 l ∈ {0,…,k−1}ⁿ 标记,约束 klk0 ≤ m(最多改 m 个特征)。
- 目标攻击:l∗ = argmax|l|0 ≤ m Cy(V(Tl(x))),即在替换数约束下最大化分类器对目标标签 y 的输出;等价于求集合 S∗ = argmax|S| ≤ m f(S),其中 f(S) 是只允许改 S 中特征时目标标签输出的最大值。
- Proposition 1:该问题对一般分类器是 NP-hard,即使对某些凸分类器也可由 subset sum 归约。
理论:两条可解路径
- 梯度法 = 松弛问题:假设 Cy 光滑,用一阶泰勒展开把问题松弛为最大化 V(Tl(x))ᵀ∇Cy(v)(Problem 2),类似 Frank-Wolfe;Proposition 2 证明该松弛对 bag-of-words 和 word2vec embedding 都可多项式时间求解(集合函数退化为模函数)。作者认为 [18] 属于此类,但 ReLU 破坏光滑性、一阶展开只看局部,限制了效果。
- 贪心法 = 次模假设:若 f 单调非降且次模,则基数约束下贪心有 1 − 1/e 近似(Claim 1,引用 Nemhauser et al. [38])。作者称 [19] 的贪心与本文方法都隐含次模假设。
次模性的两个证明
- 简化 W-CNN(Theorem 1):无 dropout 和 softmax 层、窗口不重叠(s ≥ h)、输出层权重 w0 全非负、且只考虑会增大输出的替换时,f 是次模的;证明思路是 max pooling 作用在模函数上是次模的,次模函数之和仍次模。
- 一维隐单元 RNN(Theorem 2):T 个时间步、每个隐层单节点,w 和输出权重 y 为正、激活函数非降且凹时,f 次模;作者称该结果令人意外,因为词向量在不同时间步影响输出、并不可分。
攻击流程(Algorithm 1–3)
- 候选集构建:词级用 Paragram-SL999 的 300 维 paragram embedding 生成邻近改写,句级用 Wieting and Gimpel 的 Para-nmt-50m 预训练模型生成句子改写;每个词/句最多保留 k 个候选。
- 语义与句法约束:语义上用 Word Mover Distance(WMD)限制候选与原文的距离(阈值 δs、δw);句法上用语言模型 P 要求 |ln P(x) − ln P(x′)| ≤ δ。
- Algorithm 2(句级贪心):逐句尝试候选改写,按分类器输出值贪心选择,直到 Cy(V(x)) ≥ τ 或改写句数达 λs·l。
- Algorithm 3(梯度引导贪心词改写):每轮按词 embedding 的梯度 L2 范数选出 N=5 个最重要的词,在这 5 个词的候选集笛卡尔积中枚举所有组合,取使分类器输出最大的组合;直到 Cy(x) ≥ τ 或改写词数达 λw·n。作者称一轮替换多词可考虑多词联合效果,设计灵感来自坐标下降中的 Gauss-Southwell 规则 [39]。
- 整体顺序:先做句级改写(Algorithm 2),若已达终止阈值 τ 则直接返回,否则再做词级改写(Algorithm 3)。作者说明词级才用梯度,是因为句子改写会改变词数,改写前算的梯度可能对应不上新句子的位置。
关键参数(Section 6.2)
- 终止阈值 τ = 0.7;候选邻居数 k = 15;语义相似度 δw = δs = 0.75(spacy 的 WMD 相似度,[0,1] 区间)。
- 句法约束 δ = 2(News、Yelp),Trec07p 因邮件含大量损坏词、语言模型失效而设 δ = ∞。
- 改写比例:λw = 20%(所有数据集);λs = 20%(Yelp、News),λs = 60%(Trec07p)。
论文做了哪些实验?
在三个任务上攻击 WCNN 和 LSTM:对抗准确率最低至 16.5%,优化算法更快更优,人工评估质量接近原文。
实验设置
- 被测模型:WCNN(kernel size 3 的时间卷积 + max-pooling + 全连接)和一层 512 隐节点的 LSTM,共 2 个。
- 数据集:Fake/Real News(5336 训练/1000 测试)、Trec07p(67.9k 训练/7.5k 测试)、Yelp reviews(560k 训练/38k 测试),见 Table 6。
- 基线:[19] 的 objective-guided greedy(含论文报告值与作者用相同词候选集复现的值,均允许 λw=50%)和 [18] 的梯度方法。
- 指标:原始/对抗测试准确率(Table 2)、攻击成功率 SR 与耗时(Table 3,单位论文未说明)、人工评估(Table 4)。
- 训练设置:词表取频率前 100,000 的词,embedding 用预训练 word2vec(300 维),10% 训练数据作验证集,mini-batch 16。
- 人工评估:5 名评估者,每人看 n = 60 条文本(一半原文一半生成),Task I 分类准确率取多数投票,Task II 按"像人写的程度"1–5 分取平均。
主结果
Table 2:三个数据集上的原始与对抗测试准确率(本文方法 λw=20%;[19] 两列均 λw=50%,* 为作者用相同词候选集复现)。
表格较宽,可左右滑动
数据集 模型 Origin ADV (ours) ADV [19] ADV [19]* News WCNN 93.1% 35.4% 71.0% 70.5% News LSTM 93.3% 16.5% 37.0% 22.8% Trec07p WCNN 99.1% 48.6% 64.5% 63.5% Trec07p LSTM 99.7% 31.1% 39.8% 37.6% Yelp WCNN 93.6% 23.1% 39.0% 41.2% Yelp LSTM 96.4% 30.0% 24.0% 29.2% - 作者称在两种对比设置下,本文方法用更少的词改写(20% 对 50%)翻转了更多预测类别,并据此认为句词联合改写比单纯词替换更有效。
- 例外:Yelp 上攻击 LSTM 时,本文对抗准确率 30.0% 高于 [19] 报告值 24.0%(即攻击更弱),但低于复现值 29.2%。
- 作者称句级攻击几乎完整保留原意,因此更不易被人察觉;附录 C 给出与 [19, 18] 对比的具体示例。
改写比例的联合影响(Figure 4)
- 测了什么:攻击 LSTM 时,句级改写比例 λs 从 0% 到 60%、词级比例 λw 取 0%/10%/20%/30% 的成功率。
- 结果:作者报告在情感分析任务上,仅改写 10% 的词只能成功攻击约 5% 的评论;先做 60% 句级改写后成功率升至接近 60%。
- 作者解读:句级改写在只允许少量词改写时作用最大。
词级优化算法对比(Table 3)
- 测了什么:WCNN 上仅做词级攻击(不做句级改写),比较 Algorithm 3、[19] 的 objective-guided greedy、[18] 的梯度方法在 λw=5% 和 20% 下的 SR 与耗时。
- 结果(λw=20%):SR 在 News 上为 45.4%(本文)对 28.4%([19])和 12.8%([18]);Trec07p 上 45.3% 对 24.9% 和 3.4%;Yelp 上 55.9% 对 45.0% 和 9.1%。耗时上作者称本文方法只需 [19] 的 1/5 到 1/3(如 News λw=20%:0.31 对 1.46)。
- 作者解读:本文方法在三种机制中最有效;[18] 的梯度方法在允许替换少时表现差。作者称本文方法对 WCNN 更合适,部分因为推理时用了 5% dropout,[19] 每轮只改一个词难以与 dropout 噪声区分,而本文每轮改 5 个词。
人工评估(Table 4)
- 测了什么:5 名评估者对原文与生成文本做分类(Task I)和"像人写的程度"1–5 打分(Task II),每人 n = 60 条。
- 结果:Task I 分类准确率原文/对抗为 News 70.0%/50.0%、Trec07p 80.0%/80.0%、Yelp 100.0%/100.0%;Task II 为 News 3.06±0.67/3.13±0.50、Trec07p 3.23±0.31/3.10±0.40、Yelp 1.93±0.55/2.10±1.05。
- 作者解读:生成文本质量与原文接近,Yelp 上甚至略高,但作者说明这一发现不一定有统计显著性。
对抗训练(Table 5)
- 测了什么:随机取 20% 训练数据用 Algorithm 1 生成对抗样本,带正确标签并入训练集重训。
- 结果:对抗准确率普遍上升,如 LSTM+News 从 16.5% 升至 32.7%,LSTM+Yelp 从 30.0% 升至 46.7%,WCNN+Yelp 从 23.1% 升至 44.4%;干净测试准确率也大多略升(如 LSTM+News 93.3%→94.5%)。
- 作者解读:在几乎所有情形下,对抗训练提升了模型泛化并降低被攻击成功率。
其他消融与分析
- Figure 1 与附录 C 给出 6 组具体生成示例(三数据集 × 两模型),红色标注句级改写、蓝色标注词级改写,并与 [19]、[18] 的输出对比。
- 附录示例中 [18] 的梯度方法多次未能翻转预测(如 C.1 中 ADV 仍为 99.5% Real),与 Table 3 中其低 SR 一致。
有什么可以进一步探索的点?
论文未设局限章节;理论依赖简化假设,实验只覆盖两个模型、三个英文任务,人工评估规模小。
作者指出的局限与后续方向
- 论文未专门讨论局限(无 Limitations/Discussion 小节)。以下为正文中作者自己说明的适用条件与保留:
- 次模性证明依赖简化假设:W-CNN 需无 dropout/softmax、窗口不重叠、w0 非负且只考虑增大输出的替换(Theorem 1,Section 4.2.1);RNN 需一维隐单元、w 和 y 为正、激活非降且凹(Theorem 2,Section 4.2.2)。
- 作者称梯度法的光滑假设"不自然":ReLU 破坏光滑性、一阶展开只看局部,同义词 embedding 未必接近(Section 4.1)。
- 词级才用梯度引导,因为句子改写改变词数、改写前的梯度可能对应不上新句子位置,句级梯度信息"不太可信"(Section 5.2)。
- 人工评估中 Yelp 上生成文本评分略高,但作者说明该发现不一定有统计显著性(Table 4 图注)。
- 作者称框架可推广到恶意软件检测、垃圾邮件过滤、图像分割等离散攻击(Section 1),但实验只在文本分类上做。
实验覆盖范围
- 被测模型为 WCNN 和 LSTM 共 2 个(Section 6.1);理论分析覆盖简化 W-CNN 和一维隐单元 RNN。
- 数据集为 News、Trec07p、Yelp 三个英文文本分类任务(Table 6),均为二分类。
- 攻击设置:词改写比例 λw ≤ 20%(主结果),句改写比例 λs 为 20%(News、Yelp)或 60%(Trec07p);Figure 4 扫描了 λs 0–60% 与 λw 0–30%。
- 基线为 [19] 的 objective-guided greedy 与 [18] 的梯度方法;优化算法对比(Table 3)只在 WCNN 上做。
- 人工评估为 5 名评估者、每人 n = 60 条(Table 4);论文未报告攻击的查询次数、单条样本生成总耗时(Table 3 的 time 单位未说明)和评估者间一致性。
总结一下论文的主要内容
离散攻击的次模优化框架:理论保证贪心近似比,梯度引导加句词联合改写,三个任务上验证有效。
一篇关于离散对抗攻击的优化框架论文,面向文本分类场景。
- 问题:文本等离散输入上生成对抗样本比连续数据难:梯度法不直接适用、替换组合空间指数增长、且难以保持原文语义句法。
- 方法:把攻击形式化为集合函数 f(S) 在基数约束下的最大化;证明该问题一般情形 NP-hard,但在简化 W-CNN(无 dropout/softmax、窗口不重叠)和一维隐单元 RNN 上 f 是次模的,贪心算法因此有 1 − 1/e 近似保证。攻击实现为句级贪心改写(Algorithm 2)加梯度引导贪心词改写(Algorithm 3,每轮按梯度范数选 5 个词枚举组合),候选由 paraphrase 语料生成并用 WMD 和语言模型过滤。
- 主结果:在 News、Trec07p、Yelp 上攻击 WCNN 和 LSTM,λw=20% 时对抗准确率最低至 16.5%(LSTM、News,Table 2),多数设置下优于允许 λw=50% 的 [19];例外是 Yelp+LSTM 上 30.0% 高于 [19] 报告值 24.0%。
- 优化对比:仅词级攻击时 Algorithm 3 在 WCNN 上 SR 为 45.4%/45.3%/55.9%(News/Trec07p/Yelp,λw=20%),高于 [19] 和 [18],耗时为 [19] 的 1/5 到 1/3(Table 3)。
- 质量与防御:5 名评估者(各 n=60)认为生成文本与原文质量接近(Table 4);用 20% 训练数据生成对抗样本做对抗训练后,对抗准确率普遍上升(如 LSTM+News 16.5%→32.7%,Table 5)。
- 作者结论:作者称梯度引导贪心继承了梯度法的效率与贪心法的攻击能力,句词联合改写能在保持语义句法的同时生成攻击空间;理论上次模假设统一了现有梯度与贪心两类启发式。