SynchroTrap : 一個月內檢測 200 萬欺詐帳戶

汪昊

haow85@outlook.com

互聯網上泛濫著各種欺詐行為。特別是社交網絡誕生以來，許多職業***和黑色產業鏈便通過欺詐行為謀生。一個常見的欺詐行為便是大量的同時虛假點贊行為，也就是會有大量的用戶在短期內大量地給同一個頁面點贊（Synchronized Attack）。針對這種特定的欺詐行為，學術界的研究者和工業界的工程師專門研究了一種叫做 SynchroTrap 的算法。這種算法被部署在 Facebook 和 Instagram 的系統中，在一個月的時間內檢測出了 200 萬欺詐帳戶和 1156 次大規模網絡***。

SynchroTrap 的算法非常簡單, 最根本的原理就是利用 Jaccard 相似性挑選出在某一個時間窗口內行為特別相近的那些用戶。

下面我們來直觀的感受一下 Synchronized Attack 和正常用戶行為之間的差異：

上圖中 (a) 顯示的是 Synchronized Attack ，可以看到大量的用戶在很短的時間區間內幾乎同時產生了某種行為；而圖中 (b) 的用戶行為更多的是一種隨機的分布。

為了更好的理解 Synchronized Attack 這種欺詐行為，我們先來看一下欺詐行為的經濟學約束條件：

1. 通常由于計算資源和運營成本的原因。欺詐用戶通常在有限的時間內控制大量的用戶。

2. 因為黑色經濟的原因，欺詐行為通常都是任務性質的，也就是有任務時間限制的。

為了更好的解決 Synchronized Attack 問題，我們首先定義“匹配”的概念。所謂匹配是指：

其中 U 是用戶 id ，C 是用戶的行為集合，而 T 是行為集合產生的時間。

定義用戶與用戶之間的 Jaccard 相似度為：

其中：

計算完用戶與用戶之間的相似性后，我們得到了一張以用戶為節點的圖。然后我們采用單鏈接凝聚層次聚類的方法對用戶進行聚類：

SynchroTrap 的時間復雜度是 O(rn^2)。

SynchroTrap 算法的原理非常的簡單, 把檢測 Synchronized Attack 問題

轉化成了聚類問題。聚類問題不可避免的需要涉及到點和點之間距離的計算，SynchroTrap 的作者用常用的相似性距離計算度量 Jaccard Distance 來表示點和點之間的距離。然后采用了凝聚層次聚類的方法進行了聚類。整個算法的過程非常的簡潔流暢。

上圖顯示的是在 11 周的時間里每周被檢測的用戶數。

原文：Uncovering Large Groups of Active Malicious Accounts in Online Social Networks 

原文作者：Qiang Cao , Xiaowei Yang , Jieqi Yu , Christopher Palow