Nurhachu Null 路编译

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

互联网时代恶意攻击频繁出现,之前的研究主要研究托攻击。南大庞明、周志华等研究者将目光对准了无组织恶意攻击,即攻击者在没有任何组织者的情况下单独使用少量的用户配置文件来攻击目标,并提出了对应的解决方案——无组织恶意攻击检测算法(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 算法:

实验

表 1:在结合了传统策略的无组织恶意攻击下,UMA 与其他算法在数据集 MovieLens 100K 和 MovieLens 1M 上的检测查准率、查全率以及 F1 得分对比。

表 2:在一般无组织恶意攻击下,UMA 和其他算法在数据集 MovieLens 100K 和 MovieLens 1M 上的检测查准率、查全率和 F1 得分对比。

表 3:UMA 与其他算法在 Douban 10K 上的检测查准率,查全率以及 F1 得分对比。

理论NIPS 2018周志华无组织恶意攻击检测算法
1
相关数据
收敛技术
Convergence

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

协同过滤技术
Collaborative filtering

协同过滤(英语:Collaborative Filtering),简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要。协同过滤又可分为评比(rating)或者群体过滤(social filtering)。其后成为电子商务当中很重要的一环,即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”,也就是借由社区的喜好提供个人化的信息、商品等的推荐服务。除了推荐之外,近年来也发展出数学运算让系统自动计算喜好的强弱进而去芜存菁使得过滤的内容更有依据,也许不是百分之百完全准确,但由于加入了强弱的评比让这个概念的应用更为广泛,除了电子商务之外尚有信息检索领域、网络个人影音柜、个人书架等的应用等。

推荐系统技术
Recommender system

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

亚马逊机构
Amazon

亚马逊(英语:Amazon.com Inc.,NASDAQ:AMZN)是一家总部位于美国西雅图的跨国电子商务企业,业务起始于线上书店,不久之后商品走向多元化。目前是全球最大的互联网线上零售商之一,也是美国《财富》杂志2016年评选的全球最大500家公司的排行榜中的第44名。

https://www.amazon.com/
涉及领域