NIPS 2018 | 南大周志华等人提出无组织恶意攻击检测算法UMA

2018 年 11 月 8 日 机器之心

选自arXiv

作者：Ming Pang、Wei Gao、Min Tao、Zhi-Hua Zhou

机器之心编译

参与：Nurhachu Null、路

互联网时代恶意攻击频繁出现，之前的研究主要研究托攻击。南大庞明、周志华等研究者将目光对准了无组织恶意攻击，即攻击者在没有任何组织者的情况下单独使用少量的用户配置文件来攻击目标，并提出了对应的解决方案——无组织恶意攻击检测算法（UMA），实验证明该算法能够有效检测无组织恶意攻击。目前，该论文已被 NIPS 2018 接收。

互联网的繁荣使得在线活动早已成为我们日常生活中一个必不可少的部分，例如，越来越多的客户更喜欢使用 Amazon 和 eBay 购物；很多人在 Youtube 和 Netflix 上观看各种各样的电影和电视节目。由于内容和用户的数量都在急剧增长，有效地推荐合适的产品是很有挑战性的工作。因此，各种各样的协同过滤技术被开发用于形形色色的系统，以帮助客户在一众内容中选择他们最喜爱的产品（Li et al., 2009; Bresler et al., 2014; Rao et al., 2015）。

很多协同过滤方法无力应对垃圾邮件制造者和排名操纵（Ling et al., 2013; Gunes et al., 2014），攻击者可能会向 user-item 评分矩阵中插入虚假的评分来使系统产生偏差。一些攻击者可能会增加他们内容的流行度（push attack，推攻击），一些攻击者则可能会减少竞品的流行度（nuke attack，核攻击）。大多数攻击检测研究聚焦于托攻击（shilling attack），并且在多种托攻击策略上表现出了较好的检测性能 (Mehta, 2007; Hurley et al., 2009; Ling et al., 2013)。他们认为所有的攻击都在使用同样的策略使某个特定的条目升级或者降级。例如，某个攻击组织者可能会生成数百个虚假用户资料，在这种策略中，每个假用户会给最流行的电影给出高分评价，而给要降级的目标电影给出低分评价。

各种各样切实可行的技术被开发用于控制托攻击，例如，网站注册需要实名和电话号码认证；验证码被用于确定某个响应是否由机器人生成；客户在购物网站上购买了某个产品之后才能进行评价。基于这些方法，传统的托攻击可能面临比较高昂的代价。例如，Amazon 等电商网站上的小型在线零售商可能不太愿意生成百上千个虚假客户来实现一次托攻击。

这篇论文研究了一种新型攻击模型——无组织恶意攻击（unorganized malicious attack），攻击者在没有任何组织者的情况下单独使用少量的用户资料来攻击目标。这种攻击类型在很多实际应用中都有发生，例如，Amazon 上的在线商店可能会制造一些虚假评价，降低其竞品高质量鞋子的评分；作家可能会雇佣几个读者给他们的低质量书籍打好评。实际证明这种少数的无组织恶意攻击会严重地影响系统，例如，首次恶意差评能够将卖家的销量较低 13% (Luca, 2016)。

研究者先将无组织恶意攻击公式化为矩阵补全问题的变体。X 代表没有噪声和攻击的真实评价矩阵，该矩阵是低秩矩阵，因为用户的偏好会受多个因素的影响 (Salakhutdinov et al., 2007)。让 Y 代表稀疏攻击评分矩阵，Z 代表噪声矩阵。我们可以观察到一个（部分）矩阵 M = X + Y + Z。据我们所知，之前的研究工作没有对攻击检测做出类似的公式化阐述。本研究中的优化问题和鲁棒 PCA 之间的主要区别是：鲁棒 PCA 主要聚焦于从完全或者不完全矩阵中恢复低秩矩阵 X，本研究则更注重从微弱扰动的噪声项 Z 中区分稀疏攻击项 Y。

理论上，本研究证明了低秩评价矩阵 X 和稀疏矩阵 Y 可以在一些经典的矩阵补全假设下恢复。本研究提出了无组织恶意攻击检测算法（UMA），可以看作是一种近似交替分裂增广拉格朗日（proximal alternating splitting augmented Lagrangian）方法。研究者开发了一些新技术，证明该方法在全局收敛的最糟糕的情况下也具有 O(1/t) 的收敛速度。实验结果证明了该算法的有效性，且优于当前最优的攻击检测方法。

论文：Unorganized Malicious Attacks Detection

论文链接：https://arxiv.org/pdf/1610.04086.pdf

摘要：过去十年，推荐系统吸引了很多关注。人们开发了许多攻击检测算法来提供更好的推荐，这些算法大多数聚焦于托攻击，在托攻击中，攻击组织者生成大量的用户资料，通过同样的策略来升级或者降级某个商品。本研究考虑了一种不同的攻击类型：无组织恶意攻击。在这种攻击中，攻击者在没有组织者的情况下单独使用少量的用户资料来攻击不同的目标。尽管这种无组织恶意攻击发生在很多实际应用中，但是相关的研究仍然是一个开放性问题。我们首次将无组织恶意攻击公式化地阐述为一个矩阵补全问题，并且提出了无组织恶意攻击检测算法（UMA），这是一种近似交替分裂增广拉格朗日方法。我们分别在理论上和实验中验证了该方法的有效性。

UMA 算法：