大家好，我是小伍哥，今天給大家分享一個(gè)非常牛逼的算法，叫做SynchroTrap。

一、極致對(duì)抗下的風(fēng)控怎么做？

為了好理解，以淘寶刷單的風(fēng)險(xiǎn)對(duì)抗階段為例（各階段為假設(shè)，本人并未做過刷單的風(fēng)控）

第1階段：同設(shè)備，同地址，大量購買

第2階段：同設(shè)備、地址部分變化，大量購買

第3階段：設(shè)備變化，IP、支付等介質(zhì)有聚集，大量購買

第3階段：設(shè)備采用模擬器，變化IP，不同收貨地址，空包等虛假物流，大量購買

··· ···

第N階段：設(shè)備真實(shí)、IP真實(shí)、地址真實(shí)、物流真實(shí)、用戶真實(shí)... ...

?

所有的都是真實(shí)的，俗稱眾包刷單，這種怎么辦？

有人說，所有東西都真實(shí)，那不就是真實(shí)的成交了么，還管啥？非也。雖然信息都真實(shí)，但是購買意愿和目的不是真實(shí)，受刷單團(tuán)伙統(tǒng)一指使，嚴(yán)重破壞生態(tài)平衡，若不加管控，將導(dǎo)致劣幣驅(qū)逐良幣的現(xiàn)象，對(duì)平臺(tái)經(jīng)濟(jì)的持續(xù)發(fā)展產(chǎn)生毀滅性的打擊。

那遇到這種情況，我們風(fēng)控人員是不是就束手無策了呢？同樣也是非也。已經(jīng)有比較成熟的方法進(jìn)行挖掘。只是方法比較抽象，不是很好理解。讓我慢慢道來。

當(dāng)然這種方法，不僅僅用于刷單，任何薅羊毛行為、營銷作弊、刷評(píng)論、抖音刷點(diǎn)贊、刷粉絲，朋友圈刷榜單等風(fēng)險(xiǎn)類型都能用，且不依賴于任何介質(zhì)，只依賴行為特征。我在多個(gè)場(chǎng)景應(yīng)用，效果非常好。

如果你是風(fēng)控從業(yè)者，一定要研究該算法，做完升職加薪肯定沒問題?。?/span>

?

二、什么是SynchroTrap？

synchronized 同步的；Trap 陷阱，圈套，互聯(lián)網(wǎng)上泛濫著各種欺詐行為。特別是社交網(wǎng)絡(luò)誕生以來，許多職業(yè)黑客和黑色產(chǎn)業(yè)鏈便通過欺詐行為謀生。一個(gè)常見的欺詐行為便是大量的同時(shí)虛假點(diǎn)贊行為，也就是會(huì)有大量的用戶在短期內(nèi)大量地給同一個(gè)頁面點(diǎn)贊（Synchronized Attack）。針對(duì)這種特定的欺詐行為，學(xué)術(shù)界的研究者和工業(yè)界的工程師專門研究了一種叫做 SynchroTrap 的算法。這種算法被部署在 Facebook 和 Instagram 的系統(tǒng)中，在一個(gè)月的時(shí)間內(nèi)檢測(cè)出了 200 萬欺詐帳戶和 1156 次大規(guī)模網(wǎng)絡(luò)攻擊。

惡意賬戶在社交網(wǎng)絡(luò)、電商生態(tài)、外賣等業(yè)務(wù)上通常會(huì)有松散的同步行為進(jìn)行黑產(chǎn)活動(dòng)，行為上具有一定相似度。

基于攻擊者松散的同步行為和經(jīng)濟(jì)約束，構(gòu)建了惡意賬戶檢測(cè)系算法SynchroTrap，大流程如下：

• 基于用戶之間行為相似度構(gòu)建網(wǎng)絡(luò)

• 利用算法進(jìn)行圖分割+連通子圖查找發(fā)現(xiàn)團(tuán)伙

• 優(yōu)化實(shí)現(xiàn)大規(guī)模計(jì)算，對(duì)系統(tǒng)進(jìn)行持續(xù)監(jiān)控

?

三、攻擊者表現(xiàn)和經(jīng)濟(jì)約束

1、 Facebook上傳圖片攻擊行為

通過下圖可以看出而惡意用戶（圖a）行為較集中、持續(xù)，而且使用到的IP資源較少 。正常用戶（圖b）的行為比較隨機(jī)，且使用大量不同的IP（現(xiàn)在幾乎不存在IP相同的了，論文時(shí)期還比較多）

? ?

x軸是用戶上傳照片的時(shí)間，y軸代表用戶ID，點(diǎn)(x,y)代表某用戶在某時(shí)刻發(fā)生的上傳照片行為， 顏色代表此次行為使用的IP地址。

?

2、Instagram 用戶關(guān)注攻擊行為

下圖可以看出惡意用戶呈現(xiàn)“開關(guān)”的行為模式（只在某些時(shí)間點(diǎn)有行為）， 并且使用的IP有限制。

? ?

3、經(jīng)濟(jì)約束

分析為什么社交網(wǎng)絡(luò)中攻擊者趨向“松散同步”的行為，主要原因是受到資源和任務(wù)的約束

2.3.1 資源約束

攻擊者受物理計(jì)算（服務(wù)器）、網(wǎng)絡(luò)資源（IP地址）的成本約束，甚至從云服務(wù)器租用。并且制造虛假、養(yǎng)號(hào)以及維護(hù)管理賬戶會(huì)產(chǎn)生人工和運(yùn)營成本。

2.3.2 任務(wù)約束

收入來源明確需求的任務(wù)，比如在多少時(shí)間內(nèi)完成多少評(píng)論、贊、好友數(shù)?；竞芏嗳蝿?wù)都需要在規(guī)定的時(shí)間內(nèi)完成，因此，黑產(chǎn)任務(wù)，時(shí)間維度的同步很難規(guī)避，如果避開時(shí)間維度，成本將不可控。

?

四、挑戰(zhàn)及解決

1、可擴(kuò)展性

低信噪比：Facebook上有規(guī)模較大的用戶活動(dòng)數(shù)據(jù)（日活6億），惡意用戶只占其中很少的比例（每次攻擊數(shù)千用戶），會(huì)導(dǎo)致低信噪比，但是，難達(dá)到較高的檢測(cè)準(zhǔn)確率。

解決方法：根據(jù)攻擊者的經(jīng)濟(jì)約束，在檢測(cè)系統(tǒng)中引入下述約束約束在每個(gè)應(yīng)用級(jí)別（如FB、INS）、某個(gè)事件級(jí)別（關(guān)注、點(diǎn)贊）上進(jìn)行檢測(cè)。通過IP地址、被關(guān)注的賬戶、被點(diǎn)贊的頁面 分割用戶計(jì)算相似度。

計(jì)算壓力大：兩兩用戶做相似度計(jì)算，計(jì)算復(fù)雜度O(n^2)

解決方法：分而治之，將任務(wù)基于時(shí)間維度分成較小的任務(wù)，并行執(zhí)行， 然后聚合結(jié)果多個(gè)較小的計(jì)算結(jié)果以獲得一段時(shí)間的相似度。

2、準(zhǔn)確性

無監(jiān)督異常檢測(cè)往往容易受到準(zhǔn)確性的制約，通過了解攻擊者經(jīng)濟(jì)約束（業(yè)務(wù)經(jīng)驗(yàn)），并提煉出知識(shí)加入系統(tǒng)中提高準(zhǔn)確性。

另外提供了一組參數(shù)，針對(duì)實(shí)際場(chǎng)景調(diào)節(jié) 誤殺(false postive)和 召回 (false negative)

3、 適用不同場(chǎng)景

攻擊者會(huì)針對(duì)不同的功能（點(diǎn)贊、上傳照片）攻擊，對(duì)系統(tǒng)的要求是能夠擴(kuò)展適用不同的場(chǎng)景的攻擊。

包括分離個(gè)性化操作 和 通用操作， 以及對(duì)動(dòng)作進(jìn)行抽象，使得系統(tǒng)可以與特定OSN(online social network)獨(dú)立。

?

五、識(shí)別策略設(shè)計(jì)

1、用戶行為（user action）

時(shí)間軸上的一個(gè)垂直箭頭表示用戶在Online Social Network上的一種操作，不同類型的箭頭表示不同類型的操作（例如，點(diǎn)贊，轉(zhuǎn)發(fā)，評(píng)價(jià)、關(guān)注、上傳照片…）

通常每個(gè)用戶一天當(dāng)中的操作是不同的，如左圖，但是Malicious Accounts組織通常是接受了某個(gè)任務(wù)，需要在規(guī)定時(shí)間內(nèi)完成指定的操作，所以會(huì)出現(xiàn)右圖矩形框中的情況，他們?cè)跁r(shí)間軸上的箭頭是完全同步的。

2、按場(chǎng)景對(duì)行為分組

由于攻擊者的任務(wù)和操作約束，他們?cè)谔囟〞r(shí)間只會(huì)集中針對(duì)某個(gè)功能進(jìn)行攻擊，只會(huì)使用用戶行為空間中的子集行為。

故可以根據(jù)不同功能對(duì)行為分類，并在功能層次進(jìn)行檢測(cè)，例如按照“上傳照片”、“頁面點(diǎn)贊”將用戶進(jìn)行分組，每個(gè)組內(nèi)計(jì)算用戶之間相似度并進(jìn)行檢測(cè)。

這樣做的好處是：

降低信噪比：如果使用用戶整體行為進(jìn)行比較，可能會(huì)出現(xiàn)“維度災(zāi)難”，錯(cuò)過部分只針對(duì)某OSN功能的攻擊

降低計(jì)算成本：兩兩用戶計(jì)算相似度 是指數(shù)級(jí)別的開銷

?

3、數(shù)據(jù)說明及行為匹配

總結(jié)計(jì)算用戶相似度的字段：

UID：用戶ID

Timestamp：user action發(fā)生的時(shí)間戳

AppID：user action所屬功能類別，如發(fā)帖、評(píng)論、上傳照片等；

AssocID：user action作用對(duì)象ID，如某頁面、某USER、某照片；

IP address：user action發(fā)生時(shí)使用的IP地址

抽象帶時(shí)間戳的用戶行為（U為userID， T為動(dòng)作時(shí)間戳， C為約束對(duì)象）：

約束對(duì)象是各個(gè)屬性值的組合，例如限制在對(duì)同IP、點(diǎn)贊功能下、在某頁面上發(fā)生行為的用戶，進(jìn)行相似度計(jì)算 。

行為匹配：若在約束下，兩個(gè)用戶的行為發(fā)生的時(shí)間都落在預(yù)定義好的匹配窗口內(nèi)，那說明他們行為是匹配的：

4、用戶間相似度度量

基于Jaccard測(cè)量?jī)蓚€(gè)集合之間相似度，分為每個(gè)約束下的相似度和全局相似度。

4.3.1 約束下的相似度

設(shè) Ai 為用戶Ui的行為集合：Ai = {?U, T , C ?|U =Ui } ?

設(shè)為在約束Ck下用戶的行為集合：?= {?U, T , C ?|U =Ui , C =Ck }

則兩用戶i、j在約束Ck下的用戶相似度：

4.3.2 全局相似度

在有些約束下，用戶與操作對(duì)象的關(guān)聯(lián)可能只出現(xiàn)一次，例如安裝app，這樣jaccard相似度取值只有0/1。為了更好地表征用戶之間相似性，使用全局相似度（即綜合所有約束下的用戶間相似度）：

?

5、行為聚類

設(shè)定邊權(quán)重（共享的IP地址數(shù)量）閾值T，抽取G的子圖（邊權(quán)重w>=T）。對(duì)G作連通子圖聚類，得到k個(gè)連通圖。若連通圖的成員數(shù)大于M，那么對(duì)該連通圖進(jìn)一步作取子圖操作，但邊權(quán)重閾值從T變成了T+1。不斷迭代上述整個(gè)過程。

單鏈層次聚類（不推薦）

現(xiàn)有的聚類方案（如k-mean）不具有擴(kuò)展性，故使用單鏈層次聚類。大概的思路是：初始化：為每個(gè)節(jié)點(diǎn)指定一個(gè)簇逐步合并高相似度的簇，若兩個(gè)簇間用戶相似度最小值 超過某一個(gè)閾值，則合并。

層次聚類：https://mp.weixin.qq.com/s/QD_rpJ4Iyv8gp3SFVVVamA

?

?圖分割 + 連通子圖查找

由于單鏈層次聚類依賴自下而上構(gòu)建樹，還是難以并行

采用等價(jià)的圖分割+連通子圖查找方法：過濾低于某閾值的邊，然后執(zhí)行連通子圖算法

?

圖構(gòu)建 ? - 圖分割 ?- 聯(lián)通子集查找 - 子集評(píng)分 - 節(jié)點(diǎn)評(píng)分

過濾邊的方法：

F1：至少存在一個(gè)約束對(duì)象，對(duì)該約束對(duì)象用戶間相似度超過某個(gè)閾值：防范在單約束下的攻擊（如同IP地址）

F2：全局相似度超過某個(gè)閾值， 防范跨多個(gè)約束對(duì)象的攻擊場(chǎng)景。

?

六、并行化實(shí)現(xiàn)用戶間相似度計(jì)算

對(duì)于用戶的相識(shí)度計(jì)算，計(jì)算開銷是最大的問題，算法的工程問題主要是為了解決如何計(jì)算賬號(hào)相似度，由于【賬號(hào)對(duì)(i,j)的交集次數(shù)=賬號(hào)對(duì)(i,j)的并集次數(shù)-賬號(hào)i的行為次數(shù)-賬號(hào)j的行為次數(shù)】，并且賬號(hào)的行為次數(shù)非常好計(jì)算，因此主要問題是如何計(jì)算【賬號(hào)對(duì)(i,j)的交集次數(shù)】。

一個(gè)簡(jiǎn)單的方法是按照Constraint Object進(jìn)行partition，每個(gè)分區(qū)統(tǒng)計(jì)賬號(hào)對(duì)的共現(xiàn)次數(shù)，然后再進(jìn)行reduce操作，但是由于一些熱點(diǎn)Constraint Object的存在，該方法在大數(shù)據(jù)量的情況下很難跑的出來。

論文首先提出了一個(gè)減少計(jì)算量的方法，該方法是按照天來計(jì)算，再對(duì)多天進(jìn)行匯總。于是，現(xiàn)在的問題轉(zhuǎn)化為如何計(jì)算一天內(nèi)賬號(hào)對(duì)的交集次數(shù)。

1、按天為單位并行化

即按天比較用戶的日相似度，并將一定窗口內(nèi)的日相似度聚合，如下圖所示

?

用戶Ui在某天的行為：

用戶Ui、Uj按天計(jì)算、聚合相似度公式：

公式中最后個(gè)等號(hào)為什么成立？因?yàn)槠ヅ浯翱谑欠昼娂?jí)別或者一兩個(gè)小時(shí)，跨天的用戶行為匹配相對(duì)比較少，故等號(hào)近似成立。

?

2、每時(shí)級(jí)別重疊滑動(dòng)窗口的相似度計(jì)算

即使轉(zhuǎn)換成按天計(jì)算了，因?yàn)榭赡苣承┕睮P關(guān)聯(lián)的用戶量比較大（熱門IP可能每天關(guān)聯(lián)10w個(gè)用戶），可能天級(jí)別的計(jì)算也會(huì)發(fā)生數(shù)據(jù)傾斜，導(dǎo)致計(jì)算量異常大，所以還需要進(jìn)一步優(yōu)化計(jì)算邏輯。

論文解決這個(gè)問題的思路是這樣的，以2Tsim為時(shí)間窗大小進(jìn)一步對(duì)1天的時(shí)間周期進(jìn)行分組，每個(gè)組之間的計(jì)算可以并行化，于是算法可以進(jìn)一步提速：重疊滑動(dòng)窗口大小為Tsim（行為匹配窗口）的2倍，滑動(dòng)距離等于Tsim，并刪除重復(fù)計(jì)算：對(duì)在兩個(gè)連續(xù)的窗口任意一個(gè)中間部分（下圖陰影部分）禁用相似度計(jì)算。

假設(shè)Tsim=1H，那么時(shí)間段0-23可以分成(0,1)(1,2)...(22,23)這幾個(gè)組，每個(gè)組的時(shí)間跨度是2H，并且每個(gè)組與相鄰組之間有1個(gè)小時(shí)的重疊。對(duì)于每個(gè)組，統(tǒng)計(jì)賬號(hào)對(duì)發(fā)生同步行為的次數(shù)，并進(jìn)行聚合，得到結(jié)果A。

按照上述計(jì)算邏輯，有一種情況會(huì)重復(fù)計(jì)算，比如：一個(gè)賬號(hào)對(duì)的兩個(gè)同步行為發(fā)生在4點(diǎn)到5點(diǎn)之間，那么(3,4)和(4,5)都會(huì)對(duì)其計(jì)數(shù)一次。因此，還需要統(tǒng)計(jì)賬號(hào)對(duì)在(0)(1)...(23)這些組發(fā)生同步行為的次數(shù)，進(jìn)行聚合得到結(jié)果B，于是最終賬號(hào)對(duì)的交集次數(shù)為A-B。

這部分最抽象，比較難理解，理解了，直接SQL就能實(shí)現(xiàn)，我就是在SQL中完成的這個(gè)部分。

?

2、提高精確度

提供一組參數(shù)根據(jù)實(shí)際場(chǎng)景選擇不同取值，人為調(diào)整后來權(quán)衡誤殺和召回。

• Tsim：行為匹配窗口

• F1：每個(gè)約束相似度過濾閾值

• F2：全局相似度過濾閾值

• 匹配后計(jì)算額外的條件，比如行為匹配后，計(jì)算昵稱相似度

比如較大的動(dòng)作匹配窗口能夠?yàn)閮蓚€(gè)用戶找到更大的匹配動(dòng)作集，從而增加他們的相似度，

較大的相似度閾值減少了召回，降低了誤殺率。根據(jù)場(chǎng)景不同，窗口設(shè)計(jì)差異非常巨大，如在紅包、點(diǎn)贊等場(chǎng)景，窗口盡量設(shè)計(jì)的小，活動(dòng)持續(xù)時(shí)間短。商家領(lǐng)域，特別是針對(duì)養(yǎng)號(hào)類的商家，持續(xù)時(shí)間可能是月，甚至是年。

3、計(jì)算復(fù)雜度

• 沒約束全局相似度計(jì)算：O(rn^2),n為每個(gè)每日的活躍用戶數(shù)，r為每個(gè)用戶每天的動(dòng)作數(shù)

• 約束級(jí)別下相似度計(jì)算：O(rm^2)，m為每個(gè)約束對(duì)象下每日用戶數(shù)

• 連通子圖查找：O(n)

• 總復(fù)雜度O(rm^2+n)

?

?

七、檢測(cè)系統(tǒng)使用、評(píng)價(jià)和分析

1、不同場(chǎng)景約束設(shè)置

• 如果是資源受限的同步攻擊：在用戶登陸和照片上傳場(chǎng)景，使用IP地址+cookie作為約束。

• 任務(wù)約束的同步攻擊：在安裝app、點(diǎn)贊和刷關(guān)注場(chǎng)景，用appID、pageID、被關(guān)注者ID作為約束，并在一些場(chǎng)景使用全局相似性。

2、減少誤殺，影響用戶體驗(yàn)的設(shè)置

僅篩選出大型子圖，比如節(jié)點(diǎn)數(shù)超過200，這些往往都對(duì)應(yīng)大型攻擊。不會(huì)使惡意子圖中所有用戶操作都無效，而是僅禁止同一子圖中每個(gè)賬戶至少出現(xiàn)過一次的操作。

3、提取攻擊簽名

約束對(duì)象如IP、UA、cookies等可能濫用的，故可以作為攻擊簽名提煉出來，構(gòu)建近實(shí)時(shí)規(guī)則。

4、準(zhǔn)確率分析（抽樣）

5、惡意賬戶類型分布

6、增量分析

每個(gè)場(chǎng)景檢測(cè)到的欺詐增量明顯

7、攻擊用戶規(guī)模分布

?

8、攻擊者郵箱來源分析

9、攻擊者IP段分析

10、上線后效果

圖1:開始開始穩(wěn)定，后面下降原因可能是攻擊者發(fā)現(xiàn)無法通過這種方式攻擊，故停止了，后面一直穩(wěn)定說明有效檢測(cè)圖2是每個(gè)用戶被系統(tǒng)檢測(cè)到次數(shù)，可以發(fā)現(xiàn)存在部分用戶被檢測(cè)到超過2次，這個(gè)是因?yàn)閒b會(huì)對(duì)檢測(cè)到的用戶發(fā)送驗(yàn)證，部分攻擊者可能會(huì)通過驗(yàn)證從而發(fā)起新的攻擊

?

11、SybilRank分析

SybilRank應(yīng)該是對(duì)每個(gè)用戶在社交圈的地位進(jìn)行排名，通過SybilRank 對(duì)惡意用戶進(jìn)行排名，描繪社交價(jià)值，發(fā)現(xiàn)登陸操作中有40%為0分，說明他們沒有社交價(jià)值（孤島），故可能為虛假帳戶。雖然sybilrank對(duì)大部分惡意用戶排名都低，但也存在部分排名高的，這個(gè)可能是也操控（盜號(hào)）了部份正常社交的用戶上傳照片傳播給他們的朋友

六、課后思考

這篇文章是具有一定啟發(fā)性的，賬號(hào)對(duì)行為具有同步特征是惡意賬號(hào)行為聚集性的必然表現(xiàn)。這種賬號(hào)之間的聯(lián)系是非常強(qiáng)的，并且不需要依賴一些強(qiáng)關(guān)聯(lián)關(guān)系（如：共用設(shè)備等）。在這里，我就這篇論文會(huì)提出一些問題供大家思考或討論：

1、Single-linkage層次聚類、DBSCAN和連通圖算法有什么聯(lián)系，什么樣的聚類算法可以轉(zhuǎn)化為圖算法。

2、與論文中的做法相比，對(duì)Similairy Graph直接采用社區(qū)發(fā)現(xiàn)算法做團(tuán)體挖掘有什么優(yōu)劣。

3、對(duì)于那種行為數(shù)量異常多的Constraint Object如何處理。

4、對(duì)于LockStep欺詐行為檢測(cè)類算法，F(xiàn)RAUDAR、CopyCatch、CatchSync和SynchroTrap在適用場(chǎng)景上有什么不同。

大家有什么疑問，加我一起交流。

?

長(zhǎng)按關(guān)注公眾號(hào)? ?? ? ? ??長(zhǎng)按加作者好友
? ? ???