Анализ графа устройств: как связать точки между сессиями

Когда один мошенник управляет десятками аккаунтов, по отдельности каждый из них выглядит легитимно. У каждого свой уникальный 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 мс. Дэвид потратил неделю на бенчмаркинг альтернатив, прежде чем мы построили собственный индекс смежности на шардированном 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 обеспечивает доступность. Мы делаем снимок графа ежечасно для аварийного восстановления и запускаем полный пересчёт выявления сообществ ежедневно как проверку согласованности с инкрементальными обновлениями.

Интеграция

Граф устройств доступен через два интерфейса: real-time API запросов для отдельных проверок (связано ли это устройство с другими аккаунтами?) и API пакетного экспорта для аналитики (дай мне все кластеры с более чем N аккаунтами). Real-time API рассчитан на инлайновые решения по фроду — запрос во время создания аккаунта, чтобы проверить, видело ли устройство другие аккаунты. Пакетный API питает рабочие процессы расследований вашей команды данных.