Analýza grafu zařízení: propojování stop napříč relacemi

Když jediný podvodník ovládá desítky účtů, jednotlivé účty vypadají v izolaci legitimně. Každý má unikátní e-mail, věrohodnou IP adresu, realistické vzorce procházení. Tradiční pravidlová detekce kontroluje každý účet nezávisle a nenajde nic podezřelého. Vazby mezi účty — sdílená zařízení, překrývající se relace, společné síťové otisky — jsou pro systémy, které zpracovávají účty po jednom, neviditelné.

Proč grafy

Analýza grafu zařízení mění model. Namísto nezávislého vyhodnocování účtů budujeme graf, kde uzly jsou zařízení, účty, IP adresy a relace a hrany představují pozorované vazby: „toto zařízení bylo použito k vytvoření tohoto účtu“, „tato IP byla viděna s tímto zařízením“, „tyto dva účty sdílely cookie relace“. Graf odhaluje strukturu, kterou ploché tabulky odhalit nedokážou.

Podvodná skupina, která používá 50 účtů na 5 zařízeních a 3 IP adresách, tvoří v grafu výrazný shluk. Hustota shluku — mnoho vazeb v rámci malé skupiny uzlů — je silný signál. Legitimní uživatelé sdílejí zařízení s cizími lidmi jen zřídka a jejich vazby účet–zařízení tvoří spíše řídké, stromovité struktury než husté shluky.

Architektura grafové databáze

Používáme model property grafu se čtyřmi typy uzlů: Device (identifikované pomocí visitor ID), Account (vaše user ID), Network (IP adresa + ASN) a Session (jednotlivá identifikační událost). Hrany nesou metadata: časové razítko, skóre spolehlivosti a typ události.

Graf je uložen v účelově postaveném indexu sousednosti optimalizovaném pro dvouskokové průchody. Když dorazí nová identifikační událost, vložíme ji jako uzel Session, propojíme ji s uzly Device a Network a zkontrolujeme, zda má některý propojený Account vazby na jiná zařízení. Tato operace vložení a dotazu se dokončí pod 5ms pro grafy až s 10 miliony uzlů.

Nejdřív jsme skutečně zkusili Neo4j. Ve vývoji se 100K uzly fungoval skvěle. Pak jsme nahráli produkční data — 500M uzlů — a Cypher dotazy, které trvaly 2ms, začaly trvat 800ms. David strávil týden benchmarkováním alternativ, než jsme postavili vlastní index sousednosti nad shardovaným RocksDB. Někdy nudné, vlastní řešení porazí to elegantní z police.

Shlukovací algoritmy

Na graf zařízení aplikujeme dva shlukovací algoritmy:

Connected Components

Nejjednodušší přístup: najít všechny uzly dosažitelné z daného zařízení. Pokud je Device A propojeno s Account 1 a Account 2 a Device B je také propojeno s Account 2, pak jsou zařízení A a B ve stejné souvislé komponentě. To identifikuje všechny účty, které sdílejí jakoukoli tranzitivní vazbu na zařízení.

Connected components se počítají rychle, ale mohou produkovat velmi rozsáhlé shluky, když legitimní sdílená zařízení (rodinné počítače, knihovní terminály) vytvářejí můstky mezi nesouvisejícími účty. Řešíme to vážením hran — vazby přes známá sdílená prostředí dostávají nižší váhu.

Detekce komunit

Pro jemnější analýzu spouštíme na váženém grafu detekci komunit metodou Louvain. Tento algoritmus rozdělí graf na komunity, kde jsou vazby uvnitř komunity husté a vazby mezi komunitami řídké. Podvodné skupiny tvoří těsné komunity i tehdy, když jsou k širšímu grafu připojeny přes sdílenou infrastrukturu.

Algoritmus Louvain běží v čase O(n log n), což jej činí praktickým pro grafy s miliony uzlů. Spouštíme jej inkrementálně — když jsou přidány nové hrany, aktualizujeme přiřazení komunit lokálně, místo abychom přepočítávali celé rozdělení.

Vzor z praxe: detekce podvodné skupiny

Herní platforma integrovala naše API grafu zařízení, aby detekovala organizované podvodné skupiny. Během prvního týdne graf odhalil shluk 127 účtů propojených přes 8 zařízení a 4 IP adresy. Účty byly vytvářeny v průběhu 3 měsíců, každý s unikátním e-mailem a realistickým profilem. Pravidlová detekce neoznačila ani jeden z nich.

Prozradila je struktura grafu: 127 účtů sdílejících 8 zařízení dává průměr 15,8 účtu na zařízení. Legitimní uživatelé mají na této platformě průměrně 1,2 účtu na zařízení. Hustota shluku byla 47× nad základní hodnotou — jednoznačný signál podvodu.

Výkon ve velkém měřítku

Náš produkční graf zařízení zvládá 2,3 miliardy uzlů a 8,1 miliardy hran. Latence vložení je 2,4ms na p99. Dvouskokový průchod (najít všechny účty propojené se zařízením přes libovolnou cestu délky 2) se dokončí za 4,1ms na p99. Aktualizace detekce komunit zpracují 50 000 nových hran za sekundu.

Graf je shardován podle hashe device ID napříč 12 uzly, přičemž každý shard drží přibližně 190 milionů uzlů. Replikační faktor 3 zajišťuje dostupnost. Graf snímkujeme každou hodinu pro zotavení po havárii a denně spouštíme úplný přepočet detekce komunit jako kontrolu konzistence oproti inkrementálním aktualizacím.

Integrace

Graf zařízení je přístupný přes dvě rozhraní: real-time dotazovací API pro jednotlivé lookupy (je toto zařízení propojeno s jinými účty?) a dávkové exportní API pro analytiku (dej mi všechny shluky s více než N účty). Real-time API je navrženo pro inline rozhodování o podvodech — dotaz během vytváření účtu, aby se ověřilo, zda zařízení vidělo jiné účty. Dávkové API zásobuje vyšetřovací workflow vašeho datového týmu.