【51CTO.com快譯】自從有互聯(lián)網(wǎng)以來(lái)，網(wǎng)絡(luò)上便流傳著各種垃圾和惡意信息。應(yīng)對(duì)各種垃圾，作弊乃至欺詐信息成了各個(gè)互聯(lián)網(wǎng)公司必須解決的問(wèn)題。特別是隨著各種社交網(wǎng)絡(luò)網(wǎng)站的興起，反作弊和互聯(lián)網(wǎng)安全成為了研究界和工業(yè)界都面臨的挑戰(zhàn)。各大互聯(lián)網(wǎng)公司都成立了專門的反作弊團(tuán)隊(duì)，應(yīng)對(duì)每天出現(xiàn)的反作弊情況。

[[204459]]

反作弊中最常用到的技術(shù)之一就是圖論算法，反作弊問(wèn)題經(jīng)常可以歸約為圖論問(wèn)題。例如可以利用 SVD 分解圖的鄰接矩陣的方法，還可以利用圖遍歷算法進(jìn)行反欺詐檢驗(yàn)。具體到金融領(lǐng)域，圖論算法可以用來(lái)進(jìn)行風(fēng)控和失聯(lián)修復(fù)方面的工作。

作為全球***的社交媒體網(wǎng)站，F(xiàn)acebook 一直在設(shè)法積極應(yīng)對(duì)網(wǎng)站上的欺詐和作弊行為。CopyCatch 是 Facebook 2013 年發(fā)表在知名國(guó)際會(huì)議 WWW 上的反作弊論文，講述了 Facebook 處理一類叫作 Lockstep 欺詐行為的算法。

Lockstep 行為是指存在這樣的頁(yè)面，大量的用戶都在較短的時(shí)間窗口內(nèi)給這個(gè)頁(yè)面點(diǎn)過(guò)贊。檢測(cè) Lockstep 行為也就變成了檢測(cè)這樣的用戶和頁(yè)面的集合。下面我們就來(lái)看一下 Facebook 是如何設(shè)計(jì)反作弊算法的：

首先構(gòu)建一個(gè)二部圖。二部圖的節(jié)點(diǎn)有兩類：一類是用戶，另一類是 Facebook 的頁(yè)面。當(dāng) Facebook 的用戶給某個(gè)頁(yè)面點(diǎn)贊時(shí)，便會(huì)在代表用戶的節(jié)點(diǎn)和代表頁(yè)面的節(jié)點(diǎn)之間構(gòu)建一條邊。Lockstep 行為可以用如下數(shù)學(xué)公式來(lái)描述：

這個(gè)問(wèn)題本身可以轉(zhuǎn)化為在二部圖中檢測(cè)二部核(Bipartite Core)的問(wèn)題。檢測(cè)二部核問(wèn)題本身是 NP-hard 問(wèn)題，因此需要設(shè)計(jì)近似算法來(lái)解決這個(gè)問(wèn)題。Facebook 把這個(gè)問(wèn)題設(shè)計(jì)為***化問(wèn)題。

首先重新定義一下問(wèn)題描述：

這個(gè)問(wèn)題可以歸約為如下***化問(wèn)題：

其中 L 代表用戶點(diǎn)擊頁(yè)面的時(shí)間矩陣，c 是欺詐用戶發(fā)生欺詐行為的中心向量，而 P’ 是欺詐頁(yè)面集合。這個(gè)***化問(wèn)題的實(shí)質(zhì)是: 選擇聚類中心 c 和頁(yè)面子空間 P’ 來(lái)***化聚類中給定的時(shí)間窗口內(nèi)用戶和用戶喜歡行為的數(shù)量。解決該問(wèn)題采用迭代的算法，算法的***步是選定聚類中心 c ，算法的第二步是根據(jù) c 來(lái)選定 P’。算法的框架如下所示：

其中 UpdateCenter 函數(shù)的流程如下：

UpdateCenter 函數(shù)的基本思想是在當(dāng)前聚類中心的 范圍內(nèi)重新選擇聚類中心，使得新的聚類中心能夠覆蓋更多的用戶和更多的點(diǎn)贊行為。

FindUsers 函數(shù)的流程如下：

FindCenter 函數(shù)的流程如下：

FindCenter 函數(shù)的基本思想是將二部圖中與某個(gè)頁(yè)面關(guān)聯(lián)的用戶根據(jù)頁(yè)面點(diǎn)贊時(shí)間進(jìn)行排序，然后考察在給定時(shí)間窗口內(nèi)用戶子集合的點(diǎn)贊行為的***值。將新的聚類中心點(diǎn)設(shè)置為用戶子集合的中心。

UpdateSubspace 函數(shù)的流程如下：

UpdateSubspace 函數(shù)的基本思想是考察當(dāng)前欺詐頁(yè)面子集合之外的頁(yè)面，看是否存在欺詐可能性更高的頁(yè)面(也就是關(guān)聯(lián)欺詐用戶是當(dāng)前欺詐頁(yè)面對(duì)應(yīng)用戶的超集)，如果存在，則將當(dāng)前頁(yè)面替換為新頁(yè)面。

作者提供了 Map-Reduce 版本如下：

CopyCatch算法的收斂速度很快，在 Facebook 的數(shù)據(jù)集上大約10個(gè)迭代算法就可以收斂：

Facebook 的 CopyCatch 算法思路和實(shí)現(xiàn)均較為簡(jiǎn)單, 并且經(jīng)過(guò)線上運(yùn)行確認(rèn)算法效果滿足線上要求, 是非常優(yōu)秀的算法。雖然算法發(fā)表距離今天已經(jīng)有一段時(shí)間，但是仍然具有現(xiàn)實(shí)的參考意義。

CopyCatch 算法用到了圖論的相關(guān)知識(shí)。截至今天，圖論已被廣泛的應(yīng)用在反欺詐/反作弊/信息安全等領(lǐng)域。熟練的掌握?qǐng)D論相關(guān)知識(shí)已經(jīng)成為大數(shù)據(jù)和人工智能從業(yè)者的必備技能。希望本文能夠給互聯(lián)網(wǎng)行業(yè)的相關(guān)從業(yè)者提供寶貴的經(jīng)驗(yàn)。

原文標(biāo)題：CopyCatch : Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks

作者：Alex Beutel , Wanhong Xu , Venkatesan Guruswami , Christopher Palow , Christos Faloutsos

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