[论文学习] 脆弱的推荐系统: 通过伪造共同访问对推荐系统进行攻击

导语:感谢非鱼子翻译并评注讲解这篇关于攻击推荐系统的文章。攻击推荐系统这个方向不像别的安全方向那么热门,但是其中的技术很有意义,特别是针对一个数据系统的不同信息层面设计的攻击技术。现在很多黑产正通过对推荐系统和排名系统的攻击谋取不当利益(比如app store刷榜比如恶意推榜等),安全研究员和系统设计师必须了解这些攻击方法并在实际工作里侦测和防护。–phunter

作者:非鱼子

原文引自: Yang, Guolei, N. Z. Gong, and Y. Cai. “Fake Co-visitation Injection Attacks to Recommender Systems.” Network and Distributed System Security Symposium 2017. 论文发表在信息安全四大会议之一NDSS 2017上,原文(包括论文、PPT和演讲视频)可以在NDSS官网上下载,本文的所有内容均从该论文中整理所得,遵循论文和会议规定的分发原则。

1. 概述

推荐系统在当前的互联网中扮演非常重要的角色,被大量的网站(包括视频、电子商务、广告等网站)用来推荐与用户特征匹配的物品(包括视频、商品等)。同样地,在学术界推荐系统的研究非常广泛,实现的算法种类与方法也多种多样。在众多的实现算法中,基于共同访问(co-visitation)的推荐系统由于其简洁性和高效性已经被众多网站使用。比如YouTube视频网站右侧的推荐列表,Amazon购物网站上“购买过该商品的用户也购买了…”等功能都是基于共同访问推荐系统的表现。事实上,基于共同访问的推荐系统利用了两个物品之间的共同访问信息,其最重要的想法是:过去两个经常被连续访问的物品,在将来也很容易被共同访问。

从推荐系统的目的来看,推荐系统必须向特定用户推荐与用户偏好度最匹配的物品。但是在本文中,作者提出了一种新的攻击来欺骗推荐系统,以使达到攻击者所期望的推荐结果(增加或者减少物品在推荐列表中的曝光次数)。该攻击主要针对的基于共同访问的推荐系统,通过向推荐系统中注入我伪造的共同访问以达到攻击的效果。这也是学术界第一次正式的、系统的研究针对推荐系统伪造共同访问的注入攻击的研究。

2 推荐系统与共同访问图

一般来说,推荐系统包含一组用户和一系列的item,用户包括注册用户和非注册用户,item可以是YouTube中的视频、Amazon中的商品等。推荐系统的目的是向用户推荐符合用户偏好的item。推荐系统的研究与应用非常多,本文主要关注的是基于共同访问的推荐系统。YouTube和Amazon在正式文章中均表明其使用基于共同访问的推荐系统。

基于共同访问的推荐系统中非常重要的数据结构是共同访问图(co-visitation graph)。如下图1所示,共同访问图可以表示为\(G =(V,E)\)。其中\(V\)是所有结点的集合,每个结点\(i\)表示一个item,结点的权重\(W_i\) 表示结点的popularity;\(E\)是所有边的集合,每条边\((i,j)\)表示至少有一个用户共同访问结点 \(i\) 和结点 \(j\) ,边的权重记为\(W_{ij}\),表示结点\(i\)和结点\(j\)被共同访问的次数。

图1 共同访问图
图1 共同访问图 (图片引自[1])

基于共同访问的item-to-item推荐系统工作方式: 从用户和item的角度看,一般推荐系统主要有两种推荐方式: item-to-item推荐和user-to-item推荐。在item-to-item推荐中,当一个用户访问某个item \(i\) 时,推荐系统会向用户推荐与\(i\)相似的N个其他item;而在user-to-item推荐中,当一个用户访问item时,推荐系统会根据用户的访问记录和profile来推荐N个其他item。本文主要关注的是item-to-item推荐系统,当然作者在论文中也表明,该攻击可使用与user-to-item推荐系统。
总的来说,基于共同访问的item-to-item推荐系统的工作流程主要有如下三个步骤:

  1. 计算共同访问图中item-item之间的similarity;

    例如,YouTube中的相似性计算函数为:$$S_{ij} = \frac{w_{ij}}{f(w_i,w_j)} = \frac{w_{ij}}{w_i * w_j}$$

  2. 对于与item i相似性程度从高到低进行排序;

  3. 生成最终的推荐列表,但是必须满足某些条件。

    比如: 满足popularity阈值\(\tau\)。因为对某些相似性计算函数来说,如果共同访问的数量不变,则结点popularity的值\(w_i\)或者\(w_j\)值越低,相似度值越高。为了避免不受欢迎的item更容易被推荐,所以一般会设置一个阈值来过滤掉popularity值低的item。

假设给定共同访问图如图1所示,popularity阈值为20,那么对Item 1而言,相似性排序为: $$S_{13} = \frac{4}{22 * 11} $$、$$S_{12} = \frac{8}{22 * 27}$$ 、$$S_{14} = \frac{6}{22 * 35}$$ ,但是由于Item 3 不满足popularity阈值,而Item 2满足popularity阈值,所以最终推荐Item 2。

3 共同访问注入攻击

3.1 攻击者的背景知识分类

一般来说,具备不同攻击背景知识的攻击者可以达到不同的攻击效果。所以在具体介绍本文的攻击之前,作者首先将攻击者根据背景知识不同分为如下三类,具体如下图2所示。

img
图2 攻击者背景知识的三种分类 (图片引自[1])

事实上,High knowledge的攻击者的要求非常高,需要了解推荐系统的共同访问图G和popularity阈值,一般只能是公司内部的人员实施攻击。Medium Knowledge的攻击者比较常见,可以了解到推荐系统中的推荐列表和所有item的popularity,符合攻击条件有YouTube视频网站等。最后一类是Low Knowledge的攻击者,一般只能获得推荐系统中的推荐列表,符合攻击条该件的推荐系统也很多,比如Amazon,eBay等网站。

3.2 攻击目标

由于攻击者的资源有限,比如IP地址、计算资源等,所以本文中攻击的主要目标是:在攻击者伪造共同访问数量有限的情况下,将攻击效果最大化。

一个非常重要的问题是,如何衡量攻击的效果?在本文中,攻击效果的度量方式是衡量未来用户对item增加或减少用户印象(User Impression, UI)数量。具体来说,\(UI\)表示为对未来一个随机的用户而言,target item获得Top-k的用户印象的可能性。假设有一个用户访问任何一个物品\(x\),\(p_i\)表示 item \(i\)被该用户访问到的概率,目标target item记为\(i_t\),用\(I_{i_{t}}\)表示为item的Top-k推荐列表中包含该target item \(i_t\)的其他所有item的集合。最终,target item \(i_t\)的Top-k用户印象总体概率计算为: \(UI = \sum_{i \in I_{i_t}} p_i\)。由于\(UI\)计算的是未来用户访问的可能性,无法真实地计算,所以作者采用的是利用过去该item的受欢迎程度来估计未来的该item的访问情况,即\(p_i = \frac{w_i}{w_i + w_2 + … + w_n}\)。所以UI的最终计算公式为:\(UI = \frac{\sum_{i \in I_{i_t}} p_i}{w_1 + w_2 + … + w_n}\),也就是\(UI = x\%\)表示有\(x\%\)的网站访问者将会通过其他item的推荐列表看到该target item。

3.3 伪造共同访问的攻击:Promotion Attack & Demotion Attack

根据攻击造成的效果不同,本文将针对推荐系统的伪造共同访问攻击分成两类: Promotion Attack 和 Demotion Attack。

  • Promotion Attack: 给定一个目标target item和一个有特定关于推荐系统背景知识的攻击者,Promotion Attack可以使得推荐系统向尽可能多的用户推荐该target item。假定对于target item \(i_t\)而言,所有item的Top-k推荐列表中包含该target item \(i_t\)的所有item的集合表示为 \(I_{i_{t}}\)。假设经过Promotion Attack之后,该集合扩大成\(J_{i_t}\), 那么该攻击的威胁效果可以定义成increased probability of top-k user impression(IUI), 即 \(IUI = \sum_{i \in J_{i_t} – I_{i_t}} pi\)。
  • Demotion Attack: 该攻击与Promote Attack类似,不同的是,它的目的是使得推荐系统尽可能少地向用户推荐target item。同样地,Demotion Attack的威胁效果定义成decreased probability of top-k user impression(DUI), 即\(IUI = \sum_{i \in I_{i_t} – J_{i_t}} pi\)。

4 Promotion Attack

4.1 Promotion Attack: 一个举例

假设现在有一个具有High knowledge的攻击者,即该攻击者可以获得推荐系统的共同访问图,其攻击目标是为了提升target item(item 3)在其他item中推荐列表中出现的概率,具体的攻击方式如下图3和图4所示。

BeforeAttack AfterAttack
图3 攻击前示意图[1] 图4 攻击后示意图[1]

具体步骤可以表示为:

  • [step 1] 根据攻击前的共同访问图3所示,为目标target item(本例中为item 3)选择anchor item。 因为item 1 和item 4的推荐列表中不包含item 3,但是都与item 3相连,所以选择item 1 和item 4 作为提升item 3 的anchor item;

    anchor item的表示的是那些原先的推荐列表中不含有target item的其他item

  • [step 2] 攻击者利用脚本自动地、重复地在同一个浏览器session中共同访问每个anchor item和target item(可以使用VPN等切换IP地址的方式,防止被发现);

  • [step 3] 利用step 2的方法,在item 3 和item 1之间注入10次虚假的共同访问。此时,item 1 的结点值变为32,item 3的结点值变为21, item 1 和item 3之间的边的权重变成14;

  • [step 4] 同样地,在item 3 和item 4 之间注入10次虚假的共同访问。此时,item 4的结点值变成45,item 3 的结点值变成31,item 4 和item 3 之间的边的权重变成17;

  • [step 5] 根据生成推荐列表的计算方法,计算item 1 和item 4的推荐列表顺序。最终计算得出,item 1 和 item 4 的推荐列表由原来的item 2 变成我们的目标item 3,从而达到 promote attack的预期效果,如图4所示。

4.2 Promotion Attack: 优化问题

上一小节是关于Promotion Attack的直观介绍,但是由于攻击者的资源有限,所以在实际应用过程中,Promote Attack会遇到两个非常关键的挑战:

  • 对特定的target item,如何选择对应的anchor item?
  • 对于每个anchor item,需要注入多少虚假的共同访问?

在文章中,作者提出的解决方法是将该攻击问题转化成一个优化问题。文章首先介绍如何将一个High Knowledge的Promote Attack转化成一个优化问题,然后再通过估计共同访问图中边的权重值,将Medium Knowledge的攻击者转化为High Knowledge的攻击者,接着通过估计共同访问图中结点值,从而将Low Knowledge的攻击者转化成Medium Knowledge攻击者。

4.2.1 High Knowledge的Promotion Attack

对于具有High Knowledge的攻击者而言,可以获得共同访问图\(G\)和popularity阈值\(\tau\)。假设攻击者总共可以注入\(m\)个虚假的共同访问,\(p_i\)表示 item \(i\)被该用户访问到的概率。首先攻击者选择一组可以被成功攻击的anchor item来达到最大化攻击效果的目的。为了方便起见,作者使用一个二进制变量\(a_j\)来表示item j是否被选择为anchor item,例如\(a_j = 1\)表示\(j\)是一个anchor item。利用上述条件,promote attack可以转化成如下的优化问题:

HighKnowledgePromoteAttack
图5 High Knowledge的Promotion 攻击的优化问题表示 (图片引自[2])

其中,$$V_k$$表示攻击前所有推荐列表的Top-k中不包含target item的所有item的集合,也就是最终选择的anchor item的集合。

下面我们逐一来解释上述的优化函数:图5中公式(8)表示的是优化问题的目标函数,即promote attack的目的是最大化IUI,使得推荐系统向尽可能多的用户在推荐列表的top-k中推荐target item。公式(9)是该优化问题的第一个限制条件,即限制所有注入的虚假共同访问次数不能超过\(m\),其中\(m_{jk}\)表示攻击者在item j和target item \(i_t\)之间注入的共同访问数量。公式(10)表示在Promote Attack之后,对于每个anchor item \(j\)来说,item \(j\) 和item \(i_t\)之间的相似度会大于 item \(j\)和item \(k_j\)之间的相似度,也就是说target item \(i_t\)会出现在anchor item \(j\)推荐列表的Top-k上。公式(11)同时表明攻击后的结点Popularity值要大于推荐系统要求的阈值\(\tau\)。具体地,可以利用公式(10)和(11)得出\(m_{jk}\)的最小值,接着将\(m_{jk}\)的最小值代入到 公式(9)中,所以将该问题优化问题转化为标准的线性规划问题。

总的来说,具有High Knowledge背景的攻击者的攻击步骤总结如下:

  • step 1: 攻击者利用常用的线性优化方法(如Ellipsoid方法等)解决上述的优化问题,从而获得攻击target item 所需要的anchor item集合,以及攻击者针对每个anchor item所要注入虚假共同访问的次数。
  • step 2: 攻击者利用脚本自动化向target item \(i_t\)和每一个anchor item \(j\)之间注入 \(m_{jk}\)
    次虚假的共同访问,以达到攻击的效果。

4.2.2 Medium Knowledge的Promotion Attack

对于Medium Knowledge背景的攻击者而言,无法获得共同访问图和popularity阈值,但是可以获得每个item的popularity值和对应的推荐列表。现在假设,对于攻击者所能了解到的每个item i, 如果我们能够获得每个item i和推荐列表Top-k中第k个item$k_j$的相似性$S_{ik_{j}}$,同时也能得到popularity阈值,那么我们就能将Medium Knowledge背景的Promote Attack转化成上一节介绍的High Knowledge背景的Promote Attack。

如何转化?该文章采用的方法是,通过估计缺失的参数,将medium knowledge攻击转化为High Knowledge攻击,从而可以利用优化问题解决。具体来说,对于Popularity阈值\(\tau\)来说,作者将该阈值估计为推荐列表中最不受欢迎item的popularity值。对相似性\(S_{ik_{j}}\)而言,由于item j和item j推荐列表中第k个推荐的item \(k_{j}\)间的相似度肯定小于等于item j与item \(k-1_{j}\)之间的相似度,肯定小于等于item j与item \(k-2_j\) 之间的相似度,以此类推…,也即: \(s_{j k_j} \leq s_{j k-1_j} \leq s_{j k-2_j} \dots \leq s_{j 2_j} \leq s_{j 1_j}\) 。又由于对任何\(S_{jx}\)而言,\(S_{jx} = \frac{w_{jx}}{f(w_j,w_x)} \leq \frac{max(w_j,w_x)}{f(w_j,w_x)}\)。所以,首先通过计算每个相似值 \(s_{j k-1_j}\) 、\(s_{j k-2_j}\) … \(s_{j 2_j}\) 、 \(s_{j 1_j}\) 的上限值,接着我们将所有上限值中的最小值作为\(S_{jk_j}\)的上限值。根据对上面Popularity阈值\(\tau\)和相似性\(S_{ik_{j}}\)的估计,也就可以进一步将其转换成High Knowledgede攻击的处理方法。

4.2.3 Low Knowledge的Promotion Attack

对于Low Knowledge背景的攻击者而言,唯一获得的是item的推荐列表,攻击条件非常苛刻。同样地,其解决方法也是通过估计每个item的popularity值,将该攻击转换成Medium Knowledge的攻击,最后进一步转化成High Knowledge的攻击,从而可以用最优化的方式解决。

作者通过查阅相关文献发现,item的popularity值可以由一组特征构成的函数表示,也即:\(w_j = g(f_1,f_2, \dots , f_F)\) 其中,F是特征总数量。在本文中,作者将函数\(g\)设定为线性函数,即\(w_j = g(f_1,f_2, \dots , f_F) = a_0 + \sum_{t=1}^{F} a_t*f_t\)。从机器学习的角度来看,函数\(g\)中所有的参数\(a_0\),\(a_i\), …,\(a_f\)都可以通过训练集来学习出来。具体的参数学习算法大家可以参阅论文和演讲Slides。

当然通过估算的方式来将Medium和Low Knowledge的攻击转化为High Knowledge的攻击,肯定会对攻击的效果产生影响。所以作者也在实验部分也在不同背景下攻击的进行对比实验,这部分对比分析详细见实验评估部分。总而言之,上述主要介绍了三种不同背景下的攻击者如何进行Promotion Attack。事实上,相似的解决方法也完全可以应用在Demotion Attack上,具体做法参阅论文,这里不再赘述。

5 实验与评估

在本文中,作者分别在人工的数据和真实的系统中进行评估实验。作者利用人工产生数据上的实验,用来对该攻击形成中的假设、参数等条件的验证;而针对真实系统(如YouTube、eBay、Amazon等)的攻击,主要用来表明该攻击在现实中可能造成的实际影响。下面我们简单介绍一下实验评估的结果,具体的实验过程与实验分析可以参阅论文的评估部分。

5.1 人工数据上的实验评估

  • 对不同背景知识的攻击者而言,其攻击效果比较:High Knowledge Attacker > Medium Knowledge Attack > Low Knowledge Attack
  • 在实验中,作者实验比较了基于三种不同的共同访问图结构的攻击,实验表明,共同访问图的图结构对攻击效果没有明显的影响
  • 攻击者可以产生的虚假访问数量越多、推荐列表中Top-k中k值越大,攻击者的成功概率越高

5.2 真实推荐系统上的实验评估

5.2.1 实验过程

针对真实各类推荐系统,作者设计实现了一种通用的攻击框架,具体如下图6所示。首先,作者现实生活中的推荐系统一般都没有High Knowledge的攻击背景,所以作者在初始化步骤中,在一周的时间内通过前面介绍的参数估计的方法将问题转化成High Knowledge的优化问题。接着,根据优化问题的解决方案,作者选择攻击所需要的anchor item,并且通过脚本自动化注入虚假共同访问。最后经过2到3天的攻击窗口时间,记录实验结果。

RealWorldAttack
图6 针对真实推荐系统的通用攻击框架示意图 (图片引自[1])

另外,在该攻击实验测试过程中,为了防止注入共同访问的行为被Web服务器检测,文章也采取了一系列的手段,包括使用VPN不断切换IP地址,攻击产生时间间隔随机化等方法。

5.2.2 实验结果

事实上,文章对多个互联网上真实的推荐系统进行攻击实验评估,包括YouTube、eBay、Amazon、Yelp、LinkedIn等。下面我们以YouTube的实验结果为例,简单介绍一下针对YouTube推荐系统的实验结果。针对其他推荐系统的攻击,读者可以自行参阅论文。

AttackYoutube
图7 攻击YouTube网站的实验结果 (图片引自[2])

从图7(a)和(b)中可以看出,不论是Promotion Attack还是Demotion Attack,都有超过一半的anchor item都被攻击成功。意味着对Promotion Attack而言,有超过一半的anchor item的推荐列表Top-k中包含了target item,而对Demotion Attack而言,有超过一半的anchor item的推荐列表Top-k中不再包含target item。图7(c)显示,对Promotion Attack来说,攻击成功的anchor item的所有popularity达到\(6 \times 10^5\),所以未来访问所有这些anchor item的用户都会看到target item。图7(d)表明在实现攻击过程中,如果anchor item的popularity值越大,那么该攻击所需要注入的共同访问数量越多。造成这种情况一种非常重要的原因是,item的popularity值越大,则该item与其他item的共同访问数量越大,所以要想达到攻击成功的效果,所需要注入的虚假共同访问数量也必须要越来越大。

6 结论

本文主要提出一种针对当前互联网服务中推荐系统的攻击:通过伪造共同访问,可以在一定程度上达到操控推荐系统推荐结果的目的。作者首先从基于共同访问图的推荐系统开始,通过将攻击者背景知识分类,详细地介绍了不同背景知识的攻击者如何具体实施攻击。文章的贡献不仅在于这是学术界第一篇系统地针对推荐系统的攻击论文,而且该攻击在真实的互联网推荐系统(Youtube、Amazon、LinkedIn等)中都是有效的,并且可以一定程度上操控其推荐结果。

参考资料:

[1] http://wp.internetsociety.org/ndss/wp-content/uploads/sites/25/2017/09/ndss2017_02b_4_yang-gong_slides.pdf
[2] Yang, Guolei, N. Z. Gong, and Y. Cai. “Fake Co-visitation Injection Attacks to Recommender Systems.” Network and Distributed System Security Symposium 2017.

“[论文学习] 脆弱的推荐系统: 通过伪造共同访问对推荐系统进行攻击”的3个回复

  1. 你好,请问这篇文章是否可以授权转载发布到我们公众号“AI前线”(ID:ai-front)上?我们会注明作者和文章来源。盼复,谢谢!

  2. 感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/5qkq9l 欢迎点赞支持!
    欢迎订阅《iOS 以及等等》https://toutiao.io/subjects/183

发表评论

电子邮件地址不会被公开。 必填项已用*标注