Аналіз графа пристроїв: з'єднуємо крапки між сесіями

Коли один шахрай керує десятками акаунтів, окремо взяті акаунти виглядають легітимними. Кожен має унікальний email, правдоподібну IP-адресу, реалістичні патерни перегляду. Традиційна детекція на правилах перевіряє кожен акаунт незалежно й не знаходить нічого підозрілого. Зв'язки між акаунтами — спільні пристрої, перекриття сесій, спільні мережеві відбитки — невидимі для систем, що обробляють акаунти по одному.

Чому графи

Аналіз графа пристроїв змінює модель. Замість оцінювати акаунти незалежно, ми будуємо граф, де вузли — це пристрої, акаунти, IP-адреси та сесії, а ребра відображають спостережувані зв'язки: «цей пристрій використовувався для створення цього акаунта», «цю IP бачили з цим пристроєм», «ці два акаунти ділили cookie сесії». Граф розкриває структуру, яку плоскі таблиці показати не можуть.

Фрод-ринг, що використовує 50 акаунтів на 5 пристроях і 3 IP-адресах, утворює характерний кластер у графі. Щільність кластера — багато зв'язків усередині невеликої групи вузлів — є сильним сигналом. Легітимні користувачі рідко ділять пристрої з незнайомцями, а їхні зв'язки акаунт-пристрій утворюють розріджені деревоподібні структури, а не щільні кластери.

Архітектура графової бази даних

Ми використовуємо модель property graph із чотирма типами вузлів: Device (ідентифікується visitor ID), Account (ваш user ID), Network (IP-адреса + ASN) та Session (окрема подія ідентифікації). Ребра несуть метадані: часову позначку, оцінку впевненості та тип події.

Граф зберігається у спеціально створеному індексі суміжності, оптимізованому для обходів на 2 кроки. Коли надходить нова подія ідентифікації, ми вставляємо подію як вузол Session, з'єднуємо її з вузлами Device і Network та перевіряємо, чи має будь-який пов'язаний Account зв'язки з іншими пристроями. Ця операція вставки-й-запиту завершується менш ніж за 5 мс для графів обсягом до 10 мільйонів вузлів.

Спершу ми справді спробували Neo4j. У розробці на 100 тис. вузлів усе працювало чудово. Потім ми завантажили продакшен-дані — 500 млн вузлів — і запити Cypher, що займали 2 мс, почали займати 800 мс. David витратив тиждень на бенчмаркінг альтернатив, перш ніж ми побудували власний індекс суміжності на шардованому RocksDB. Іноді нудне кастомне рішення перемагає елегантне готове.

Алгоритми кластеризації

Ми застосовуємо до графа пристроїв два алгоритми кластеризації:

Зв'язні компоненти

Найпростіший підхід: знайти всі вузли, досяжні від заданого пристрою. Якщо Device A з'єднаний з Account 1 та Account 2, а Device B також з'єднаний з Account 2, то Device A і Device B перебувають в одній зв'язній компоненті. Це виявляє всі акаунти, що ділять будь-який транзитивний зв'язок через пристрій.

Зв'язні компоненти швидко обчислюються, але можуть давати дуже великі кластери, коли легітимні спільні пристрої (сімейні комп'ютери, бібліотечні термінали) створюють містки між непов'язаними акаунтами. Ми вирішуємо це зважуванням ребер — зв'язки через відомі спільні середовища отримують нижчу вагу.

Виявлення спільнот

Для тоншого аналізу ми запускаємо виявлення спільнот за Лувеном на зваженому графі. Цей алгоритм розбиває граф на спільноти, де зв'язки всередині спільноти щільні, а між спільнотами — розріджені. Фрод-ринги утворюють щільні спільноти, навіть коли з'єднані з ширшим графом через спільну інфраструктуру.

Алгоритм Лувена працює за час O(n log n), що робить його придатним для графів із мільйонами вузлів. Ми запускаємо його інкрементально — коли додаються нові ребра, ми оновлюємо приналежність до спільнот локально, а не переобчислюємо все розбиття.

Патерн із практики: виявлення фрод-рингу

Ігрова платформа інтегрувала наш API графа пристроїв для виявлення організованих фрод-рингів. Уже за перший тиждень граф виявив кластер зі 127 акаунтів, з'єднаних через 8 пристроїв і 4 IP-адреси. Акаунти створювалися протягом 3 місяців, кожен з унікальним email і реалістичним профілем. Детекція на правилах не позначила жодного з них.

Викривала структура графа: 127 акаунтів, що ділять 8 пристроїв, дають у середньому 15,8 акаунта на пристрій. Легітимні користувачі на цій платформі мають у середньому 1,2 акаунта на пристрій. Щільність кластера була у 47 разів вищою за базовий рівень — однозначний сигнал шахрайства.

Продуктивність у масштабі

Наш продакшен-граф пристроїв обробляє 2,3 мільярда вузлів і 8,1 мільярда ребер. Затримка вставки — 2,4 мс на p99. Обхід на два кроки (знайти всі акаунти, з'єднані з пристроєм будь-яким шляхом довжиною 2) завершується за 4,1 мс на p99. Оновлення виявлення спільнот обробляють 50 000 нових ребер за секунду.

Граф шардовано за хешем device ID на 12 вузлах, де кожен шард містить приблизно 190 мільйонів вузлів. Фактор реплікації 3 забезпечує доступність. Ми робимо знімок графа щогодини для аварійного відновлення та щоденно запускаємо повне переобчислення виявлення спільнот як перевірку узгодженості з інкрементальними оновленнями.

Інтеграція

Граф пристроїв доступний через два інтерфейси: API запитів у реальному часі для окремих пошуків (чи з'єднаний цей пристрій з іншими акаунтами?) та API пакетного експорту для аналітики (дай мені всі кластери з більш ніж N акаунтами). API реального часу розроблено для інлайн-рішень щодо шахрайства — запитуйте під час створення акаунта, щоб перевірити, чи бачив пристрій інші акаунти. Пакетний API живить робочі процеси розслідувань вашої команди даних.