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

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

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

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

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

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

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

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

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

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

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

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