賈俊杰，段超強

(西北師范大學(xué)計算機科學(xué)與工程學(xué)院，甘肅 蘭州 730070)

1 引言

目前，推薦系統(tǒng)大量應(yīng)用于電商、社交媒體、電影推薦和外賣等互聯(lián)網(wǎng)服務(wù)中。推薦系統(tǒng)通過收集、分析用戶信息，向用戶推薦可能感興趣的信息，以滿足用戶個性化的服務(wù)需求?，F(xiàn)代推薦系統(tǒng)通常采用基于協(xié)同過濾CF(Collaborative Filtering)[1]的推薦算法，協(xié)同過濾基于與用戶相似的用戶的偏好，通過用戶的歷史行為尋找與目標用戶相似的用戶組成最近鄰，最近鄰對目標項目的偏好即為用戶的偏好[2，3]。這種算法在實際應(yīng)用中具有良好的推薦效果，但容易受到托攻擊(Shilling Attack)[4]。托攻擊是指利用獲取的用戶歷史評分構(gòu)造攻擊概貌，與目標用戶形成最近鄰來影響推薦效果。檢測托攻擊是當(dāng)前推薦系統(tǒng)安全的研究熱點之一。

檢測托攻擊本質(zhì)上是對真實用戶和攻擊概貌進行分類[5]。對真實用戶和攻擊概貌分類需要尋找分類特征作為依據(jù)，即真實用戶和攻擊概貌評分在某個指標上具有明顯的差別，可以通過這個差別將二者區(qū)分開來。目前已有一系列關(guān)于用戶評分的特征指標，但單個特征指標無法有效地對各種攻擊方式的托攻擊進行檢測，同時特征指標的選取角度不同會加大數(shù)據(jù)的處理難度。

基于上述問題，本文提出基于用戶評分離散度的托攻擊檢測Dispersion-C算法。從用戶評分離散度出發(fā)，提取用戶評分極端評分比PER(Proportion of Extreme Ratings)、去極端評分方差RESV(Remove Extreme Score Variance)和用戶評分標準差SD(Standard Deviation)3個特征，作為真實用戶和攻擊概貌的分類特征;然后將3個特征作為監(jiān)督學(xué)習(xí)分類算法—ID3(Iterative Dichotomiser 3)決策樹算法的分類特征，訓(xùn)練各自的分類器，對托攻擊用戶進行檢測。實驗結(jié)果表明，本文算法對托攻擊用戶具有良好的檢測效果，魯棒性較強。

2 相關(guān)技術(shù)

2.1 托攻擊模型

目前流行的攻擊模型主要有隨機攻擊(Random Attack)、均值攻擊(Average Attack)、流行攻擊(Bandwagon Attack)和段攻擊(Segment Attack)等[5]，4種攻擊模型的攻擊概貌組成如表1所示。

Table 1 Four common attack models

2.2 檢測技術(shù)

現(xiàn)有的托攻擊檢測技術(shù)主要分為基于監(jiān)督學(xué)習(xí)的檢測技術(shù)、基于半監(jiān)督學(xué)習(xí)的檢測技術(shù)和無監(jiān)督學(xué)習(xí)的檢測技術(shù)。

為了對托攻擊概貌和真實用戶概貌進行分類，學(xué)者們提出了很多方法。Rashid等人[8]提出了多種可能有效分析各種托攻擊模式攻擊概貌的特征，包括預(yù)測偏差數(shù)量、用戶評分的標準偏差、與其他用戶的評分偏移度和最近鄰平均偏移度。Chirita等人[9]利用平均評分偏移度結(jié)合Degsim特征，提出了一種新的檢測算法。該算法可以成功檢測隨機攻擊、均值攻擊和流行攻擊概貌，但無法有效檢測段攻擊概貌。Bruke等人[10,11]在此基礎(chǔ)上提出了加權(quán)平均評分偏離度和加權(quán)評分偏離度，并提出了一些真實評分特征，但該算法受攻擊概貌填充率影響，對于較低填充率的段攻擊概貌識別效率不高。

(1)基于監(jiān)督學(xué)習(xí)的檢測技術(shù)。

將上述用戶評分特征與KNN(K-Nearest Neighbor)、SVM(Support Vector Machine)等監(jiān)督學(xué)習(xí)算法相結(jié)合稱之為基于監(jiān)督學(xué)習(xí)的檢測算法。Bryan等人[12]利用方差校正均方殘差Hv-score發(fā)現(xiàn)攻擊概貌，攻擊概貌具有更大的Hv-score值，但極易受到攻擊概貌填充率影響，在填充率低時，檢測效果不佳。李文濤等人[13]從用戶選擇評分項入手，根據(jù)用戶已評分項目流行度的不同，提出了一種基于用戶評分流行度的區(qū)分真實用戶和攻擊概貌的方法，但由于流行攻擊和段攻擊存在選擇項，該方法對段攻擊的檢測效率不高?；诒O(jiān)督學(xué)習(xí)的檢測技術(shù)的關(guān)鍵在于擬合出合適的訓(xùn)練集和測試集來構(gòu)造分類器。

(2)基于無監(jiān)督學(xué)習(xí)的檢測技術(shù)。

由于基于監(jiān)督學(xué)習(xí)的檢測技術(shù)過多依賴于特征和測試集，因此研究者轉(zhuǎn)向利用無監(jiān)督學(xué)習(xí)構(gòu)建分類器。Metha等人[14,15]利用PCA(Principal Component Analysis)算法在檢測算法中的思想，無需任何先驗知識，提出根據(jù)托攻擊概貌之間的相似性高于真實用戶這一特點對攻擊概貌進行檢測的PCA VarSelect技術(shù)，是一種無監(jiān)督的托攻擊檢測算法，但這種算法必須提前知道攻擊強度，否則檢測準確率會嚴重降低，而現(xiàn)實中攻擊強度一般是無法獲取的。李聰?shù)热薣16]提出了LFAMR模型，該模型以用戶非隨機缺失數(shù)據(jù)為依托，對導(dǎo)致評分缺失的潛在因素進行解析，利用聚類發(fā)現(xiàn)攻擊概貌，但這種模型無法有效探測低攻擊強度攻擊。

(3)基于半監(jiān)督學(xué)習(xí)的檢測算法。

在大多數(shù)的推薦系統(tǒng)中，未標記的用戶數(shù)量遠遠大于標記用戶數(shù)量，因此同時對標記用戶和未標記用戶概貌進行建模有助于提高托攻擊檢測效率。Cao等人[17,18]提出Semi-SAD算法，該算法充分利用了標記和未標記的用戶概貌，結(jié)合樸素貝葉斯和EM-λ算法，首先在標記用戶概貌上訓(xùn)練一個樸素貝葉斯分類器，然后利用期望最大化算法和未標記的用戶概貌對初始貝葉斯算法進行改進，提高攻擊概貌的檢測效率。但是，該算法對低強度的攻擊檢測效率不好，且EM迭代過程時間較長，需要極大的時間代價。

從已有的檢測技術(shù)可以看出，檢測托攻擊概貌的關(guān)鍵在于特征選擇，本文根據(jù)不同攻擊模型和用戶評分在離散度上的差異，從托攻擊概貌和真實用戶概貌的評分離散度選擇特征，將這些特征作為決策樹算法的分類特征。最后，通過實驗說明了基于用戶評分離散度的托攻擊檢測算法的可行性和優(yōu)越性。

3 基于用戶評分離散度的托攻擊檢測算法

3.1 基于用戶評分離散度的特征選擇

本文通過對美國Minnesota大學(xué)GroupLens項目組收集的MovieLens數(shù)據(jù)集[19]進行分析，發(fā)現(xiàn)用戶評分存在一個顯著的特點：用戶對于電影項目的評分多是由用戶對于電影的喜愛程度和電影的質(zhì)量高低決定的，評分是隨機的、個性化的。同時評分項目越多的用戶，不同評分次數(shù)分布更接近，也就是說真實用戶評分的離散度是在一定范圍內(nèi)隨機分布的。托攻擊用戶概貌可采取一定的模型進行部署，攻擊者根據(jù)其擁有的背景知識和想要達到的攻擊效果采取不同的攻擊模型，不同的攻擊模型具有不同的評分生成方式，且評分生成滿足一定的條件，因此托攻擊概貌評分的頻數(shù)分布是不均衡的，攻擊概貌的評分離散度接近且和真實用戶存在差異。本文從這個角度出發(fā)，以用戶評分離散度區(qū)分真實用戶和攻擊概貌，提出了基于用戶評分離散度的PER、RESV和SD3個分類特征，接下來通過不同攻擊模型對分類特征進行說明。

3.1.1 隨機攻擊和均值攻擊概貌

從攻擊模型中可以看出，攻擊概貌與真實用戶在評分分布上存在一定的差異。其中隨機攻擊和均值攻擊不具有選擇項，且評分為隨機生成，這2類模型可以一起討論。隨機攻擊的填充項評分服從系統(tǒng)評分的正態(tài)分布。均值攻擊的任一填充項評分的生成服從項目自身評分的正態(tài)分布。在生成這2種攻擊方式的過程中發(fā)現(xiàn)，隨機攻擊和均值攻擊的項目評分出現(xiàn)極端評分的概率極低，而真實用戶中極端評分是常有的。

基于這種情況，Yang等人[20]提出了用戶最高評分填充比來對此進行描述，但僅以最高評分區(qū)分真實用戶和攻擊概貌效果不佳，極易將真實用戶劃分為攻擊概貌，影響推薦效果。因此，本文在此基礎(chǔ)上提出極端評分比作為檢測攻擊概貌的特征之一。

定義1(極端評分比PER)PER描述用戶評分中評分最大值和最小值的項目數(shù)占用戶評分所有項目數(shù)的比值。用戶u的極端評分比如式(1)所示：

(1)

圖1和圖2所示為隨機攻擊和均值攻擊概貌極端評分比與真實用戶的對比情況。2種攻擊模型由于不具有選擇項且填充項的評分滿足一定條件，出現(xiàn)極端評分的概率明顯小于真實用戶，且由于2種攻擊方式接近，極端評分比的分布方式也相似。通過圖1和圖2可以發(fā)現(xiàn)，利用極端評分比可以有效區(qū)分真實用戶和攻擊概貌。

Figure 1 Comparison of PER between random attackers and normal users

Figure 2 Comparison of PER between average attackers and normal users

3.1.2 流行攻擊概貌

流行攻擊選擇當(dāng)前系統(tǒng)中最流行的項目作為選擇項，其評分為系統(tǒng)最高評分，選擇項與隨機攻擊相同。由于流行攻擊具有評分為系統(tǒng)最高分的選擇項，故流行攻擊中極端評分比根據(jù)其選擇項的規(guī)模發(fā)生變化。圖3所示為不同填充率下流行攻擊中的極端評分比和真實用戶的對比，流行攻擊的極端評分比隨攻擊概貌的填充率發(fā)生變化且和真實用戶的極端評分比相似。因此，使用極端評分比作為特征無法有效區(qū)分流行攻擊概貌和真實用戶，但流行攻擊的概貌特征與真實用戶在評分離散度檢測下仍存在可區(qū)分的特征。下面對流行攻擊概貌進行討論。

Figure 3 Comparison of PER between bandwagon attackers and normal users

流行攻擊屬于推攻擊，可以看作是隨機攻擊的一種擴展。這種攻擊方式具有的選擇項為當(dāng)前系統(tǒng)中流行度最高的幾個項目，且評分均為系統(tǒng)最高評分，其填充項和隨機攻擊填充項的部署方式相同。因此，流行攻擊概貌的評分分布存在一個有趣的現(xiàn)象，即去除極端評分后，剩余的評分分布與隨機攻擊相同。而對于真實用戶在去除極端評分后，用戶評分的離散度會降低。因此，本文定義去極端評分方差對流行攻擊概貌和真實用戶進行區(qū)分。

定義2(去極端評分方差RESV)RESV描述用戶去除極端評分后其余評分的方差。用戶u的去極端評分方差定義如式(2)所示：

(2)

如圖4所示，在去除極端評分后，流行攻擊用戶概貌的評分方差為用戶整體評分的均值和方差。而真實用戶去除極端評分值后，評分方差降低。因此，通過圖4可以確定，利用去極端評分方差可以有效地區(qū)分真實用戶和流行攻擊概貌。

Figure 4 Comparison of RESV between bandwagon attackers and normal users

3.1.3 段攻擊概貌

段攻擊同樣屬于推攻擊，具有選擇項。但是，段攻擊概貌和流行攻擊概貌的區(qū)別在于，段攻擊選擇項為與目標用戶類別相似的項目，評分均為系統(tǒng)最高評分。填充項與流行攻擊的不同之處在于，段攻擊的填充項為系統(tǒng)隨機選擇，但填充項目的評分均為系統(tǒng)最低分。這是由于段攻擊是只針對目標項目具有潛在興趣的一組用戶群，而不影響推薦系統(tǒng)整體，因此利用去極端評分方差無法檢測段攻擊概貌。

段攻擊概貌中選擇項為系統(tǒng)最高分而填充項為系統(tǒng)最低分，但真實用戶評分中用戶根據(jù)對項目的喜愛程度進行評分。真實用戶的評分是隨機且波動較為平穩(wěn)的，2類用戶在整體評分離散度上存在較大差異，因此本文引入用戶評分標準差作為檢測段攻擊的評分特征。

定義3(用戶評分標準差SD)SD指的是用戶對各個項目評分與評分均值的離差平方的算數(shù)平均數(shù)的平方根，如式(3)所示：

(3)

由圖5可見，真實用戶評分的離散度明顯小于段攻擊概貌的，因此SD可以區(qū)分真實用戶的段攻擊概貌。

Figure 5 Comparison of SD between segment attackers and normal users

3.2 基于用戶評分離散度的托攻擊檢測算法

根據(jù)上面的討論，托攻擊概貌和真實用戶概貌在評分離散度上存在差異，本文用極端評分比PER、去極端評分方差RESV和用戶評分標準差SD3個特征對用戶評分離散度進行描述。利用這些特征差異對攻擊概貌和真實用戶進行分類。

以上3個特征中，PER是一個適合對不具有選擇項的隨機攻擊和均值攻擊進行檢測的分類特征，對真實用戶和攻擊概貌中的極端評分比進行統(tǒng)計可以看出，隨機攻擊和均值攻擊的PER均低于正常用戶的。RESV是針對流行攻擊提出的分類特征，在去除極端評分比之后，流行攻擊概貌的評分方差大于真實用戶的評分方差。SD是專門針對段攻擊的分類特征，由于段攻擊由特殊的攻擊概貌構(gòu)成，其用戶評分均方差大于真實用戶的。為了從用戶離散度上對攻擊用戶進行檢測，將PER、RESV和SD3個特征作為相應(yīng)攻擊模型的分類特征，使用ID3決策樹算法訓(xùn)練分類器。

決策樹算法是一個以實例為基礎(chǔ)的歸納學(xué)習(xí)算法[21]，從一個無次序、無規(guī)則的實例集合中歸納出一組采用樹形結(jié)構(gòu)表示的分類規(guī)則。ID3決策樹算法是對決策樹算法的一種改進算法。本文將標記的數(shù)據(jù)集作為訓(xùn)練集，將ID3決策樹算法作為分類算法。ID3決策樹算法根據(jù)信息增益率選擇測試屬性，通過屬性離散化的方式對連續(xù)屬性進行處理。本文中系統(tǒng)標記的虛假用戶和真實用戶樣本集D={x1,x2,…,xn}，每個樣本xi的屬性向量P=(a1,a2,…,am)，其中m=3，ai包括PER，RESV，SD3個特征值。類別屬性C={C1,C2,…,Ck}，其中k=2，根據(jù)屬性特征值可以將樣本劃分為C1和C22個子集，代表真實用戶和攻擊概貌。步驟如下所示：

步驟1計算每個樣本的RESV、PER和SD3個屬性，得到用戶評分屬性特征向量。

步驟2計算待分類數(shù)據(jù)樣本在每個屬性A=ai時的信息增益度h(D,A)=Gain(D,A)/Entropy(D),i=1,2,3，選擇信息增益度最大的屬性作為根節(jié)點，其中Entropy(D)是當(dāng)前樣本的信息熵，Gain(D,A)為屬性在當(dāng)前樣本下的分類信息增益，其計算公式如式(4)所示：

Gain(D,A)=Entropy(D)-

∑v∈V(A)Entropy(Dv)

(4)

其中，D為當(dāng)前待分的數(shù)據(jù)樣本集，Dv是樣本集D中屬性A的值等于v的樣本集合,V(A)是屬性A的值域。

步驟3對于根節(jié)點屬性的每個可能值vi和相應(yīng)的數(shù)據(jù)點集合Dv，遞歸步驟2選擇子樹根節(jié)點建立子樹，直至某個分支下只有一個類標簽的樣本子集為止。

本文算法流程如算法1所示：

算法1基于評分離散度的托攻擊檢測算法

輸入：含有攻擊用戶的用戶評分數(shù)據(jù)集S，用戶集合U，項目集I，決策樹算法分類數(shù)K=2。

輸出：分類結(jié)果。

BEGIN

步驟1foru∈U

步驟2fori∈I

步驟3計算特征向量P=(a1,a2,a3)/*用戶特征向量由SD,PER,RESV組成*/

步驟4endfor

步驟5endfor

步驟6foru∈U

步驟7計算用戶特征向量集合；

步驟8fori≤3

步驟9A=ai；

步驟10計算屬性A的分類信息增益度：

步驟11Gain(D,A)=Entropy(D)-∑v∈V(A)Entropy(Dv)；

步驟12計算信息增益度：

步驟13MAE(ai)=root；

步驟14endfor

步驟15endfor

END

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集與實驗指標

本文使用MovieLens數(shù)據(jù)集[19]進行實驗，包括943個用戶對1 682個項目的評分數(shù)據(jù)，并且每個用戶至少對20部電影進行評分，評分取值為[1,5]。實驗假定系統(tǒng)中原有的用戶為真實用戶，利用托攻擊的模型向系統(tǒng)中注入的用戶為攻擊概貌，實驗的目的是在不刪除虛假用戶的情況下，對目標用戶進行分類。

托攻擊常用準確率fp和召回率fr的綜合指標F值[13]作為監(jiān)測指標，設(shè)N為分類器預(yù)測出的虛假用戶數(shù)量，Na為分類器正確分類出的虛假用戶數(shù)，Nt為系統(tǒng)中實際存在的虛假用戶數(shù)。為了適應(yīng)本文算法，重新定義N為ID3決策樹算法中虛假用戶集C1中用戶的數(shù)量，Na為C1中虛假用戶數(shù)，Nt為系統(tǒng)中實際存在的虛假用戶數(shù)。則準確率fp、召回率fr及綜合指標F值的計算公式分別如式(5)～式(7)所示：

fp=Na/N

(5)

fr=Na/Nt

(6)

F=2fpfr/(fp+fr)

(7)

4.2 實驗與討論

為了說明實驗的效果，本文進行了2組實驗。首先在注入不同的攻擊概貌之后，驗證Dispersion-C算法的準確率fp和召回率fr；其次利用fp和fr的綜合指標值，在10%的攻擊強度下，將本文算法與文獻[13，16，22]的托攻擊檢測算法進行對比驗證。

4.2.1 算法的檢測效果分析

為了說明實驗效果，在不同的實驗參數(shù)下對本文Dispersion-C算法的效果進行測試。實驗的參數(shù)包括：裝填規(guī)模和攻擊規(guī)模。其中，攻擊強度取5%,7%,10%和12%，填充率取3%,8%,10%,12%,15%和20%，攻擊模型為隨機攻擊、均值攻擊、流行攻擊和段攻擊。將2個參數(shù)進行相互組合，每一種組合對應(yīng)一個實驗設(shè)置，其中選擇75%的數(shù)據(jù)樣本組成訓(xùn)練集，25%的數(shù)據(jù)樣本組成測試集，然后計算算法的準確率和召回率，并在重復(fù)進行100次實驗后，統(tǒng)計得到最終的結(jié)果。

表2～表5是Dispersion-C算法在不同裝填規(guī)模和攻擊規(guī)模下的分類效果，從中可以發(fā)現(xiàn)，對于不同填充率和攻擊強度的流行攻擊和均值攻擊，Dispersion-C算法均有較好的檢測效果，并且隨著填充率和攻擊強度的增大檢測效果逐漸提高，算法魯棒性較好。對于具有選擇項的流行攻擊和段攻擊，Dispersion-C算法的檢測效果同樣優(yōu)勢明顯，特別是針對段攻擊的檢測。實驗中算法存在召回率大于準確率的現(xiàn)象，說明本文算法檢測嚴格，出現(xiàn)了將真實用戶劃分為攻擊概貌的現(xiàn)象。

Table 2 Detection precision and recall of random attack detected by Dispersion-C algorithm

4.2.2 Dispersion-C算法與其他算法對比

為了對本文提出的 Dispersion-C算法的檢測效果進行更加全面的分析，將本文算法與文獻[13]提出的基于用戶評分流行度分類特征的監(jiān)督學(xué)習(xí)的DegreeSAD算法、文獻[22]提出的利用特征指標進行托攻擊檢測的半監(jiān)督學(xué)習(xí)的檢測算法SEDSA-CI和文獻[16]提出的無監(jiān)督學(xué)習(xí)的檢測算法LFAMR一起進行討論。在相同配置的情況下，且攻擊強度均為10%時，將4種算法的檢測效果利用式(7)進行比較。實驗結(jié)果如圖6所示。

Table 3 Detection precision and recall of average attack detected by Dispersion-C algorithm

Table 4 Detection precision and recall of bandwagon attack detected by Dispersion-C algorithm

Table 5 Detection precision and recall of segment attack detected by Dispersion-C algorithm

Figure 6 Comparison of detection effects between Dispersion-C and other algorithms

圖6展示了4種算法對于不同攻擊模型的檢測效果。Dispersion-C算法根據(jù)用戶評分離散度選取分類特征，不易受到項目填充率的影響，因此對于較低項目填充率的攻擊概貌檢測效果較好，但因攻擊概貌始終存在接近真實用戶評分分布的可能性，因此很難達到完美的檢測效果。

與同為有監(jiān)督學(xué)習(xí)的基于流行度分類特征的算法DegreeSAD相比，Dispersion-C算法針對4種攻擊模型具有較優(yōu)的檢測效果。由于DegreeSAD算法從用戶選擇評分項目的方式入手，因此對于存在選擇項的流行攻擊和段攻擊，在填充率低于10%時，檢測效果不太理想，并且隨著填充率的增加，對于隨機攻擊的檢測存在F值下降的現(xiàn)象，說明DegreeSAD算法的檢測不穩(wěn)定。對于半監(jiān)督學(xué)習(xí)SEDSA-CI算法，由于其使用K-means算法對標記用戶進行分類，算法易受到聚類中心選擇的影響，導(dǎo)致檢測效果不穩(wěn)定，且檢測效果較差。無監(jiān)督學(xué)習(xí)算法LFAMR從用戶評分的缺失項目潛在因素構(gòu)建分類特征，在填充率較低時目標項和選擇項的數(shù)目相差不大，算法對各類攻擊的檢測能力均較差。

根據(jù)以上實驗對比，基于用戶評分離散度的托攻擊檢測算法與傳統(tǒng)的有監(jiān)督學(xué)習(xí)的托攻擊檢測算法相比具有較好的檢測效果；同時與半監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)算法相比，不受填充率的影響，且具有較好的魯棒性。

5 結(jié)束語

托攻擊的檢測通常面臨魯棒性問題，針對這一問題，本文對真實用戶和攻擊概貌的評分分布情況進行分析，發(fā)現(xiàn)真實用戶和攻擊概貌在評分頻數(shù)分布上是不同的。引入評分離散度作為衡量標準，將評分離散度的描述特征PER、RESV和SD作為檢測攻擊概貌的分類特征。選擇信息增益最大的特征作為ID3決策樹的分類屬性，對真實用戶和攻擊概貌進行分類，實現(xiàn)托攻擊的檢測。實驗結(jié)果表明，本文算法在不同的填充率和攻擊強度下，對攻擊概貌均有較好的檢測效果，同時算法具有良好的魯棒性。本文算法主要針對單一推薦系統(tǒng)的托攻擊檢測，而目前分布式協(xié)同過濾算法越來越流行，下一步工作將對分布式協(xié)同過濾算法中的托攻擊檢測算法進行研究。