基于項(xiàng)目評分行為序列的群組攻擊檢測算法

胡玉琦，李 雪，曲越奇

(1. 燕山大學(xué) 信息與工程學(xué)院，河北 秦皇島 066004；2. 燕山大學(xué) 里仁學(xué)院，河北 秦皇島 066004)

0 引言

推薦系統(tǒng)通過在海量信息中為用戶尋找所需要的信息，進(jìn)行個性化推薦，有效地解決信息過載問題，但系統(tǒng)的開放性使得其很容易被惡意用戶攻擊。目前攻擊行為正逐漸由個體攻擊行為轉(zhuǎn)變?yōu)槿航M攻擊行為[1]，群組攻擊行為通過多個用戶共同作用的方式有目的地對系統(tǒng)注入攻擊概貌以增加或減少目標(biāo)項(xiàng)目被推薦的頻率[2-3]。相對于個體攻擊行為而言，攻擊群組中的各個用戶互相協(xié)作和掩護(hù)，攻擊的迷惑性更強(qiáng)，傳統(tǒng)的檢測算法逐漸失效，推薦系統(tǒng)的魯棒性正受到挑戰(zhàn)。

針對攻擊群組的檢測算法中，Wan等人采用AP聚類對用戶進(jìn)行群組劃分，將每個群組表示為評分向量，并根據(jù)壓縮后的評分向量矩陣找出被攻擊的目標(biāo)項(xiàng)目，根據(jù)目標(biāo)項(xiàng)目找出攻擊群組。該算法可以檢測多種類型的攻擊，但對分段攻擊類型的小攻擊規(guī)模數(shù)據(jù)集檢測效果不穩(wěn)定[4]。Dou等人采用了矩陣分解和決策樹檢測攻擊用戶，用特征向量表示用戶的信息，利用決策樹對用戶進(jìn)行分類。該算法需要事先獲得用戶標(biāo)簽，并且如果在數(shù)據(jù)集中正常用戶和攻擊用戶比例相差較大的情況下檢測性能會降低[5]。Zhang等人需要事先了解攻擊規(guī)模并標(biāo)記種子用戶，而實(shí)際的攻擊規(guī)模具有隨機(jī)性難以獲取，該條件影響了算法的實(shí)用性。另外，該算法還受種子用戶比例的影響，如果選取的種子用戶少，檢測性能將降低[6]。Gao等人采用時間序列檢測攻擊用戶，計算每個時間區(qū)間的評分分布與其他區(qū)間評分分布的差值，差值較大被判定為可疑區(qū)間，即攻擊群組[7]。Zhou等人首先根據(jù)共同評分項(xiàng)目計算每個用戶的特征值，根據(jù)特征值利用K-means算法對用戶聚類，判定攻擊群組，但該方法不能有效地檢測共同評分項(xiàng)目很少或利用嚴(yán)格攻擊模型注入的攻擊用戶[8]。Mehta等人提出了PCA-VarSelect算法，該算法利用主成分分析降維的方法過濾攻擊概貌，可以有效地檢測多種類型的攻擊，但受限于評分矩陣的密度[9]。Cai等人通過構(gòu)建用戶有序評分序列來挖掘用戶特征，利用PCA方法提取主成分組成矩陣，然后通過計算用戶向量和預(yù)測向量的差值來檢測可疑用戶[10]。

與群組攻擊檢測算法相關(guān)的是對電商平臺中虛假評論群組的檢測。Mukherjee等人提出了采用頻繁項(xiàng)集挖掘的方法來尋找候選群組，并依據(jù)群組、個體和商品的特征計算候選群組得分，按群組得分進(jìn)行排序，篩選虛假群組，并提出了8個虛假群組的特征，彌補(bǔ)了以往檢測特征過少的缺點(diǎn)[11-12]。韓忠明等人通過構(gòu)建用戶關(guān)系圖，對鄰接矩陣特征分解，找出異常特征向量，通過異常特征向量來檢測攻擊群組，該方法在建圖時需要共同評分項(xiàng)目數(shù)量不小于3，而現(xiàn)實(shí)中無論是正常用戶還是攻擊用戶之間很少甚至沒有共同評分項(xiàng)目，因此該方法會丟失很多信息[13]。Wang等人提出通過檢測圖的拓?fù)浣Y(jié)構(gòu)來檢測虛假群組，根據(jù)用戶評論數(shù)據(jù)建立用戶關(guān)系圖，尋找圖中雙連通分量和最小分割圖，判定虛假群組，但該方法會產(chǎn)生大量的孤立節(jié)點(diǎn)[14]。Ye等人根據(jù)鄰居節(jié)點(diǎn)多樣性和節(jié)點(diǎn)與網(wǎng)絡(luò)的相似性這兩個特征分析評論者，通過2-hop子圖尋找群組中評論者的異常行為，并采用層次聚類判定虛假群組[15]。

本文針對已有群組攻擊檢測方法的局限性，提出了一種基于項(xiàng)目評分行為序列的群組攻擊檢測算法，稱為IRBS(Item Rating Behavior Sequence)算法。

1 IRBS檢測算法結(jié)構(gòu)

如圖1所示，IRBS有以下3個步驟：步驟一，根據(jù)評分?jǐn)?shù)據(jù)集提取每個項(xiàng)目的評分行為序列，按時間先后順序?qū)π蛄兄械脑剡M(jìn)行排列。設(shè)置時間長度固定的時間窗口依次交叉劃分評分行為區(qū)間，并在劃分過程中篩選出區(qū)間內(nèi)元素個數(shù)不小于2的區(qū)間；步驟二，計算區(qū)間的評分中值偏離度，根據(jù)偏離度利用層次聚類[16]篩選區(qū)間，計算區(qū)間可疑度；步驟三，對區(qū)間可疑度進(jìn)行指數(shù)縮放處理，根據(jù)可疑度利用K-means聚類[17]判定攻擊群組。

圖1 IRBS檢測算法框架Fig.1 Frame of IRBS detection algorithm

2 IRBS檢測算法

2.1 評分行為區(qū)間的劃分

2.1.1項(xiàng)目評分行為序列的提取

在推薦系統(tǒng)中，攻擊用戶為了隱蔽而快速地達(dá)到攻擊目的，通常在短時間內(nèi)以群體協(xié)作的方式對目標(biāo)項(xiàng)目進(jìn)行攻擊，并且根據(jù)攻擊概貌的類型對其他項(xiàng)目進(jìn)行評分，以增強(qiáng)隱蔽性。但無論采用哪種攻擊概貌，攻擊群組對目標(biāo)項(xiàng)目的“評分極端”和“時間集中”特性不會改變，因此通過提取數(shù)據(jù)集中每個項(xiàng)目的評分行為集合，按照時間先后順序?qū)π蛄兄械脑剡M(jìn)行排列，生成有序的項(xiàng)目評分行為序列。

定義1項(xiàng)目評分行為序列(IRBSi)指對項(xiàng)目i∈I的所有評分行為的順序集合，評分行為包括評分用戶、評分級別和評分時間，表示為

(1)

其中，m表示項(xiàng)目i的評分行為序列中評分行為的數(shù)量。

2.1.2評分行為區(qū)間的交叉劃分

根據(jù)攻擊群組的“攻擊時間集中”的特性，設(shè)置固定時間長度的窗口對每個項(xiàng)目的評分行為序列進(jìn)行劃分，窗口時間長度設(shè)置為30天，采用交叉劃分的方法，即窗口每次滑動步長為1，使區(qū)間之間有交集，從而避免了因窗口時間長度固定而導(dǎo)致某些攻擊用戶被排除掉。另外，同一序列中的區(qū)間之間不能存在包含關(guān)系，避免序列被劃分的過于精細(xì)而使區(qū)間冗余導(dǎo)致的計算量增大。

劃分群組后，由于個別用戶不能構(gòu)成群組，因此需要根據(jù)區(qū)間中用戶的數(shù)量對區(qū)間進(jìn)行篩選，將篩選出的區(qū)間用戶數(shù)量不小于2的區(qū)間作為候選區(qū)間。

文中使用的參數(shù)說明如表1所示。

表1 參數(shù)說明Tab.1 Notes of parameters

由2.1.1和2.1.2節(jié)總結(jié)出劃分評分行為區(qū)間的算法1描述如下：

算法1 劃分評分行為區(qū)間

輸入：數(shù)據(jù)集D(U,I,R,T)，評分行為窗口RBW

輸出：評分行為區(qū)間集合IRBIS

1.IRBIS←?

2. for each itemi∈Ido

3.IRBSi←項(xiàng)目i的評分行為序列

4. while True do

5.IRBIi←?,startelen←IRBSi[n]

[|IRBSi|]} do

9. end if

10. end for

11. if |IRBIi|≥2 andIRBIiIRBISi[|IRBISi|] then

12.IRBISi←IRBISi∪IRBIi

13. end if

14. ifIRBIi[|IRBIi|]=IRBSi[|IRBSi|] then

15. break

16. end if

17.n←n+1

18. end while

19.IRBIS←IRBIS∪IRBISi

20. end for

returnIRBIS

算法1主要包括兩部分：第一部分(第1～3行)生成項(xiàng)目評分行為序列，第二部分(第4～18行)劃分項(xiàng)目評分行為區(qū)間并篩選區(qū)間。

算法1的時間復(fù)雜度分析：生成項(xiàng)目評分行為序列(第1～3行)的時間復(fù)雜度為O(|I|2)，劃分項(xiàng)目評分行為區(qū)間并篩選區(qū)間(第4～18行)的時間復(fù)雜度為O(|U|·|I|)，因此算法1的時間復(fù)雜度為O(|I|2+|U|·|I|)。

2.2 區(qū)間可疑度

2.2.1區(qū)間評分中值偏離度

攻擊群組對目標(biāo)項(xiàng)目進(jìn)行極端評分，通過計算區(qū)間用戶對該項(xiàng)目評分的平均值與數(shù)據(jù)集評分中值的偏離程度，即可知道該區(qū)間為攻擊群組的可能性。

(2)

在計算偏離度之后，濾掉偏離度很小攻擊區(qū)間，縮小檢測范圍，因此設(shè)置一個閾值，如果某區(qū)間的項(xiàng)目評分中值偏離度大于該閾值，將該區(qū)間作為備選區(qū)間，否則過濾掉。

確定該閾值的方法利用層次聚類自動確定。由于所有區(qū)間的項(xiàng)目評分中值偏離度可能有重復(fù)值，而大量的重復(fù)值不但會增加計算量，而且會對檢測結(jié)果造成干擾，因此在計算之前去掉重復(fù)值，然后利用層次聚類對偏離度值進(jìn)行聚類，聚類數(shù)量為2，選取平均值最大的類別中的最小值作為閾值。該方法的優(yōu)點(diǎn)是可以根據(jù)數(shù)據(jù)集或數(shù)據(jù)量的不同，自動確定閾值，同時避免了重復(fù)項(xiàng)對檢測結(jié)果的干擾。

2.2.2區(qū)間可疑度

在篩選出候選區(qū)間后，針對攻擊群組和攻擊用戶的特征，提出了區(qū)間的可疑度的性能指標(biāo)，以此檢驗(yàn)可疑群組。

在固定的時間窗口長度內(nèi)，如果該區(qū)間占用評分行為的比例大，說明該區(qū)間的用戶評分時間比較密集，該區(qū)間用戶的行為就越可疑。

(3)

式中，Ni,s是項(xiàng)目i評分行為序列中區(qū)間s所包含用戶的數(shù)量，Ni是對項(xiàng)目i評分的用戶數(shù)量。

為了增強(qiáng)群組攻擊的隱蔽性，除目標(biāo)項(xiàng)目外，攻擊用戶力求和正常用戶行為相似，因此用戶之間在評分均值相似。如果每個用戶的歷史評分的均值和該用戶對區(qū)間所屬產(chǎn)品的評分相差較大，則該項(xiàng)目可能是目標(biāo)項(xiàng)目，該區(qū)間的可疑度也比較大。

(4)

正常用戶是通過自己對項(xiàng)目的喜好去評分，而攻擊用戶是有目的地對項(xiàng)目進(jìn)行評分，因此攻擊用戶之間具有更高的相似性，攻擊用戶的歷史評分的分布也非常相似，這里采用變異系數(shù)來衡量。通過實(shí)驗(yàn)發(fā)現(xiàn)，攻擊用戶的歷史評分的變異系數(shù)比較密集，通過變異系數(shù)來衡量區(qū)間用戶變異系數(shù)的密集程度，密集程度越大，該區(qū)間就越可疑。

(5)

(6)

σs,c是區(qū)間用戶評分變異系數(shù)的標(biāo)準(zhǔn)差，μs,c是區(qū)間用戶評分變異系數(shù)的均值，μc是數(shù)據(jù)集所有用戶評分變異系數(shù)的均值，σs,u,r是區(qū)間用戶歷史評分的標(biāo)準(zhǔn)差，μs,u,r是區(qū)間用戶歷史評分的均值。

(7)

由2.2.1和2.2.2節(jié)總結(jié)出區(qū)間可疑度的算法2，描述如下：

算法2 計算區(qū)間可疑度

輸入：評分行為區(qū)間集合IRBIS，聚類數(shù)k=2

輸出：區(qū)間可疑度集合IRBIAndSuss

1.IRBIAndSuss←?,SusDegrees←?

6. end for

7.SusDegrees←Set(SusDegrees)

8. MAX_Values1,MIN_Values2←

AgglomerativeClustering(SusDegrees,2)

9.threshold←MIN(MAX_Values1)

13. else

17. end if

18. end for

returnIRBIAndSuss

算法2主要包括3部分：第一部分(第1～6行)計算區(qū)間評分中值偏離度，第二部分(第7～9行)計算偏離度閾值，第三部分(第10～18行)篩選區(qū)間并計算區(qū)間可疑度。

算法2的時間復(fù)雜度分析：計算區(qū)間評分中值偏離度(第1～6行)的時間復(fù)雜度為O(|U|2·|I|)，計算偏離度閾值(第7～9行)的時間復(fù)雜度為O(|I|3)，篩選區(qū)間并計算區(qū)間可疑度(第10～18行)的時間復(fù)雜度為O(|I|3)，因此算法2的時間復(fù)雜度為O(|I|3)。

2.3 攻擊群組

2.3.1指數(shù)縮放的區(qū)間可疑度

現(xiàn)有的對數(shù)據(jù)進(jìn)行縮放處理的方法通常是線性縮放處理，如數(shù)據(jù)歸一化處理。這種數(shù)據(jù)縮放處理方法通常在對一維數(shù)據(jù)進(jìn)行縮放處理時，通常只能同等比例地改變數(shù)據(jù)點(diǎn)之間的距離。在攻擊群組的可疑度和正常群組的可疑度相差很小時，后續(xù)的檢測方法通常很難區(qū)分這兩種不同的群組。針對數(shù)據(jù)線性縮放處理的局限性，本文提出了數(shù)據(jù)指數(shù)縮放處理的方法。該方法通過設(shè)置一個指數(shù)，將可疑度作為底數(shù)，計算一個新的可疑度值，在不改變數(shù)據(jù)點(diǎn)分布順序的情況下使不同的兩數(shù)據(jù)點(diǎn)之間的距離增加或減少的比例不同。該方法可以有效地擴(kuò)大攻擊群組與正常群組之間的距離，使得后續(xù)的檢測方法更容易檢測出攻擊群組。

(8)

在最終判定攻擊群組之前，需要對區(qū)間可疑度做縮放處理。通過指數(shù)縮放處理，在不改變可疑度值原來分布順序的情況下，讓可疑度值不同程度地增加或減小，數(shù)值越大，增加或減少的程度就越大。本文通過設(shè)定一個縮放系數(shù)x作為指數(shù)對可疑度做縮放處理。該方法彌補(bǔ)了線性縮放只能線性的擴(kuò)大數(shù)據(jù)間距的缺陷，本文取x=2.1。

2.3.2非攻擊評分的排除

2.3.3攻擊群組的判定

區(qū)間可疑度越大，說明越有攻擊性，通過設(shè)定可疑度閾值，將大于該閾值的區(qū)間定位攻擊群組。采用K-means聚類自動設(shè)定閾值，由于區(qū)間可疑度值可能會有重復(fù)，因此我們對可疑度值進(jìn)行去重，之后利用K-means聚類對去重后的可疑度值進(jìn)行聚類，聚類數(shù)為2，然后選取可疑度均值最大的類別中的最小值作為閾值，最后將可疑度不小于該閾值的區(qū)間判定為攻擊群組。該方法的優(yōu)點(diǎn)是閾值可以根據(jù)數(shù)據(jù)集或數(shù)據(jù)量的不同自動確定。

由2.3.1～2.3.3節(jié)總結(jié)出判定攻擊群組的算法3，描述如下：

算法3 判定攻擊群組

輸入：區(qū)間可疑度集合IRBIAndSuss，系統(tǒng)評分中值rmid

輸出：攻擊群組集合AttGs

1.AttGs←?，SusValues←?

rmid) then

8. end if

9. end for

12. end for

13.SusValues←set(SusValues)

14. MAX_Values1,MIN_Values2←Kmeans(SusValues,2)

15.threshold←MIN(MAX_Values1)

19. end if

20. end for

returnAttGs

算法3主要包括3部分：第一部分(第1～3行)通過指數(shù)縮放處理區(qū)間可疑度，第二部分(第4～9行)過濾非攻擊評分，第三部分(第13～19行)利用K-means聚類方法判定攻擊群組。

算法3的時間復(fù)雜度分析如下：指數(shù)縮放處理區(qū)間可疑度(第1～3行)的時間復(fù)雜度為O(|U|·|I|)，刪除區(qū)間評分目的不同的行為(第4～9行)的時間復(fù)雜度為O(|U|2·|I|)，K-means聚類判定攻擊群組(第13～19行)的時間復(fù)雜度為O(|U|·|I|log(|U|·|I|))，因此算法3的時間復(fù)雜度為O(|U|2·|I|)。

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文使用Amazon和Netflix數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)來檢驗(yàn)算法的性能。Amazon數(shù)據(jù)集是由電商平臺Amazon.cn提供的真實(shí)數(shù)據(jù)，在該數(shù)據(jù)集中抽取了具有標(biāo)簽的5 055名用戶對17 610件產(chǎn)品的53 777條評分?jǐn)?shù)據(jù)，評分范圍為1～5分，表示用戶對產(chǎn)品的滿意程度。Netflix數(shù)據(jù)集是由電影網(wǎng)站netflix.com提供的真實(shí)數(shù)據(jù)，采用松散群組攻擊模型，攻擊類型為隨機(jī)攻擊和均值攻擊，攻擊規(guī)模和填充規(guī)模分別為10%和2.5%。

3.2 評價指標(biāo)

采用精確率J、召回率Z和F1值作為評價指標(biāo)，計算公式為

(9)

(10)

(11)

式中，C表示正確檢測的攻擊用戶數(shù)量，C0表示被錯誤地當(dāng)作攻擊用戶的數(shù)量，P表示數(shù)據(jù)集中所有攻擊用戶的數(shù)量。

3.3 對比實(shí)驗(yàn)分析

將IRBS算法與現(xiàn)有典型的6個攻擊檢測算法CoDetector[5]、CBS[6]、DeR-TIA[8]、PCA-VarSelect[9]、IRM-TIA[10]以及URGSSGD[13]進(jìn)行對比實(shí)驗(yàn)，如表2和表3所示。

表2 Amazon數(shù)據(jù)集下算法對比Tab.2 Comparisons of algorithms on Amazon datasets

表3 Netflix數(shù)據(jù)集下算法對比Tab.3 Comparisons of algorithms on Netflix datasets

本文的IRBS算法根據(jù)攻擊群組對目標(biāo)項(xiàng)目評分的“時間集中”特性，對項(xiàng)目評分序列交叉劃分評分區(qū)間。該方法不僅可以直接劃分候選群組，還減少了通過序列用戶分布的密度或通過固定時間窗口非交叉劃分區(qū)間所造成的影響，提高了候選群組的質(zhì)量。另外，根據(jù)攻擊群組“對目標(biāo)項(xiàng)目評分極端”的特性、個體行為相似性等特性對候選群組進(jìn)行檢測，提高了檢測質(zhì)量。通過對比結(jié)果發(fā)現(xiàn)，IRBS算法的檢測結(jié)果優(yōu)于其他幾種算法。

4 結(jié)論

本文提出了一種基于項(xiàng)目評分行為序列和雙聚類的群組攻擊檢測算法IRBS，與CoDetector相比，該算法不需要劃分訓(xùn)練集和測試集，更不會因?yàn)檎Ｓ脩艉凸粲脩舻谋壤箼z測結(jié)果受到影響；與CBS相比，該算法不需要事先標(biāo)記種子用戶；與URGSSGD相比，該算法不會過濾掉用戶，也不需要根據(jù)向量是否符合正態(tài)分布去檢測異常向量；與PCA-VarSelect相比，能夠更有效地檢測攻擊群組；與DeR-TIA相比，不會受限于用戶之間共同評分項(xiàng)目數(shù)量，而是根據(jù)攻擊群組的“時間集中”和“評分極端”特性檢測攻擊群組；與IRM-TIA相比，不會損失用戶信息從而影響檢測性能。

IRBS算法根據(jù)攻擊群組的“時間集中性”“目標(biāo)項(xiàng)目評分極端性”“同一群組中攻擊用戶個體特征相似性”以及雙聚類不斷對群組進(jìn)行檢測和篩選，從而確定攻擊群組。通過對Amazon數(shù)據(jù)集和Netflix數(shù)據(jù)集的檢測驗(yàn)證了該算法的有效性。

雖然該方法可以有效地檢測攻擊群組，但仍然需要人工提取特征，而人工提取的特征會使得特征覆蓋不全面，從而影響檢測結(jié)果。因此在未來工作中，擬采用生成對抗網(wǎng)絡(luò)不斷自動提高生成網(wǎng)絡(luò)的生成能力和對抗網(wǎng)絡(luò)的檢測能力，從而在訓(xùn)練過程中自動提取特征來提高檢測效果。