【51CTO.com快譯】隨著互聯(lián)網(wǎng)的蓬勃發(fā)展和互聯(lián)網(wǎng)用戶的不斷增長，各種互聯(lián)網(wǎng)網(wǎng)站面臨著各種各樣的技術(shù)挑戰(zhàn)。出于不同的非法動機，許多用戶選擇采用欺詐行為謀取經(jīng)濟利益。各種常見的互聯(lián)網(wǎng)欺詐行為包括短時間內(nèi)大量點擊頁面的行為(Lockstep)等。

為了應(yīng)對互聯(lián)網(wǎng)行業(yè)內(nèi)泛濫的欺詐行為，各大高校和互聯(lián)網(wǎng)公司紛紛推出了自己設(shè)計的算法。Facebook 推出了著名的 CopyCatch 和 SynchroTrap 算法。知名學(xué)府卡耐基梅隆大學(xué)也發(fā)表了一系列反欺詐算法的論文。我們下面分享的論文來自卡耐基梅隆大學(xué)，論文名稱是 Spotting Suspicious Link Behavior with fBox : An Adversarial Perspective。

作者首先指出了反欺詐譜分析算法的弊端。譜分析算法通常采用 SVD 算法對圖的鄰接矩陣進行分解，并選擇特征值較大的向量對應(yīng)的特征來進行反欺詐。譜分析算法通常能發(fā)現(xiàn)較大的和密度較高的欺詐團伙，但是對于規(guī)模較小的和隱蔽性較強的欺詐團伙通常無能為力，例如下圖：

這幅圖展示了譜分析算法在 Twitter 的社交網(wǎng)絡(luò)數(shù)據(jù)集合上可以檢測許多明顯的欺詐行為，卻對坐標(biāo)原點處的隱蔽性較強的欺詐行為無能為力。

作者采取了對抗式的算法來檢測欺詐行為，首先考察了什么樣的欺詐行為可以躲過流行的譜分析算法。譜分析算法通常會對圖的鄰接矩陣做 SVD 分解并且利用前 K 大特征值設(shè)計算法。設(shè)第 K 大特征值為，通常特征值小于 k 的欺詐行為都能躲過譜分析算法。

具體的，假定有c 個用戶，每個人從具有 f 個欺詐賬戶的欺詐網(wǎng)絡(luò)購買了 s 個欺詐行為， 攻擊者能夠控制的行為是鄰接矩陣的一個 f * c 子矩陣?？梢宰C明如果對這個 f * c 進行 SVD 分解得到的最大的特征值小于，則攻擊者可以躲過譜算法的檢測。

攻擊者可以利用的攻擊方式主要有以下三種：簡單注入(Naive Injection)、階梯注入(Staircase Injection)、隨機圖注入(Random Graph Injection)。

三種常見的攻擊注入方式如上圖所示。三種攻擊注入方法的最大特征值均可通過計算得到公式。針對三種攻擊注入方式的算法偽代碼如下圖所示：

因為隱蔽的攻擊不會反映在前 K 大的特征向量中，因此作者利用來重構(gòu)鄰接矩陣節(jié)點的出度。隱蔽的攻擊基本不會貢獻值給重構(gòu)的節(jié)點的出度，因此較小的重構(gòu)值通常意味著隱蔽的攻擊。用這種方法可以計算出欺詐用戶的集合。類似的，可以通過重構(gòu)鄰接矩陣的入度的方式檢測隱蔽攻擊的物品集合。

fBox 和 SpokeEigen 等譜算法是互補的關(guān)系。fBox 通常能夠捕捉較隱蔽的和規(guī)模較小的欺詐行為，而 SpokeEigen 等算法捕捉的通常都是較為明顯直觀的欺詐行為。從 fBox 等算法可以看出 SVD 分解在欺詐檢驗領(lǐng)域的重要性。在人工智能發(fā)展洶涌澎湃的今天，掌握基礎(chǔ)的線性代數(shù)等知識也是非常重要的。

原文標(biāo)題：Spotting Suspicious Link Behavior with fBox : An Adversarial Perspective，作者：Neil Shah , Alex Beutel , Brian Gallagher , Christos Faloutsos

【51CTO譯稿，合作站點轉(zhuǎn)載請注明原文譯者和出處為51CTO.com】