Введение
Плохие актеры в Интернете часто притворяются тем, кем они не являются. Но если внимательно присмотреться к их действиям, можно увидеть, кто они на самом деле. В Smyte мы стремимся определить, кто эти злоумышленники, и остановить их, прежде, чем они смогут причинить вам или вашей компании значительный вред. В этом кратком посте мы исследуем один из этих методов: поиск по сходству.
Проблема
В Интернете существует большое количество псевдонимов злоумышленников, но относительно небольшое количество настоящих злоумышленников. Что я имею в виду? Рассмотрим спамера. Человек или компания, которые рассылают спам, на самом деле являются злоумышленниками. Спамер использует несколько псевдонимов, различающихся, возможно, адресом электронной почты и / или именем пользователя. Если мы внимательно посмотрим на поведение этих субъектов, мы сможем увидеть закономерности. Они используют один и тот же номер кредитной карты? Создавали ли они свои учетные записи на одном компьютере или примерно в одно время? И т. Д. Если да, то нам нужно только определить один псевдоним, а затем найти другие псевдонимы, которые демонстрируют аналогичное поведение.
Первоначальное решение
Нашим первоначальным решением этой проблемы было построение графа. Узлы на графике представляют объекты, такие как псевдонимы, адреса электронной почты, номера кредитных карт, IP-адреса для входа и т. Д. Мы соединяем узлы на графе ребрами, когда, например, мы видим псевдоним с помощью a Номер кредитной карты. Этот график отношений кодирует прошлое поведение всех участников.
Чтобы найти псевдонимы данного плохого актера, мы ищем в графе отношений один шаг от плохого актера до характеристики и еще один шаг назад к другому псевдониму. Это дает нам список возможных псевдонимов злоумышленника. Затем мы оцениваем псевдонимы в соответствии с силой связи. Например, если у нас есть два псевдонима, которые используют один и тот же номер кредитной карты, мы можем быть уверены, что они представляют одного и того же действительного злоумышленника.
На практике этот подход работает очень хорошо. Почему? Маскировка стоит дорого. Итак, чем дороже Smyte делает это для плохих актеров, тем меньше у них стимулов к работе. Сосредоточившись на поведении, мы находим и останавливаем плохих актеров.
Проблемы с первоначальным решением
Одна из проблем с нашим первоначальным решением состоит в том, что со временем поддерживать и искать в графе отношений может быть довольно дорого. Причина проста: он продолжает расти! Чем больше график, тем дороже его хранить и запрашивать в реальном времени, поскольку поиск в ширину - это операция O (n). Что еще хуже, сложно проводить такие обходы графа, поэтому мы не могли просто добавить новое оборудование для повышения производительности, помимо вертикального масштабирования уже имеющихся сегментов. В итоге мы не смогли включить этот анализ для наших более крупных клиентов.
Наше текущее решение
Чтобы решить проблему с пространством, нам нужно решение, которое не хранит все функции, но все же позволяет нам находить похожих участников с учетом их характеристик. С точки зрения абстрактной информатики, нам нужно отобразить многомерное пространство функций (например, 2 ² IP-адреса, 10 ″ номеров кредитных карт и т. Д.) В гораздо более низкоразмерное пространство, которое мы могли бы хранить. Нам нужен был способ поддерживать приближение графика характеристик.
Давайте на мгновение отойдем от абстракции графа отношений и рассмотрим вместо этого простую модель актора и набор действий, которые он предпринял. Псевдоним A вошел в систему с IP-адреса B. Псевдоним A использовал изображение C для своего аватара. Псевдоним A позже использовал кредитную карту D для совершения покупки. Мы можем представить A набором действий:
(LOGGED_IN_FROM_IP, B) (USED_IMAGE_AS_AVATAR, C) (USED_CREDIT_CARD, D)
Вместо того, чтобы размещать их на графике, мы создаем представление этих значений в массиве постоянного пространства. Всего с тремя действиями это довольно просто, но со временем список действий может неограниченно расти. С постоянным пространством мы не можем хранить неограниченное количество действий.
Предположим, что у нас есть массив из 64 значений с плавающей запятой, представляющий все действия, когда-либо предпринятые актором. Фактическое число 64 не важно. Важно то, чтобы он был а) постоянным и б) достаточно маленьким, чтобы мы могли хранить массив для каждого псевдонима без больших затрат.
Как бы мы отобразили действия в массиве? Мы прибегаем к одной из старых рабочих лошадок информатики - хешированию. Если мы хешируем каждое действие в несколько сегментов массива и увеличиваем или уменьшаем значение в сегментах в соответствии с типом действия (первая запись в кортеже действий) и значением действия (вторая запись в набор действий), то мы можем компактно представить действия. Конкретный вариант хеширования, который мы используем, известен как разреженная случайная проекция.
Учитывая два массива, представляющих два разных псевдонима, как мы можем сравнить их сходство? Если мы рассматриваем массивы как векторы в 64-мерном векторном пространстве, то мы можем использовать измерение угла между векторами. Это известно как косинусное подобие и легко вычисляется за постоянное время из двух векторов (если рассматривать длину вектора 64 как константу).
Поиск аналогичного поведения
У нас есть постоянное пространственное представление поведения, но у нас все еще есть проблема. Учитывая единственный вектор, как нам найти похожие векторы во времени, пропорциональном количеству похожих векторов? Ясно, что мы не можем просто сравнивать каждый вектор с данным вектором.
Говоря абстрактно, нам нужна структура данных, чтобы найти ближайших соседей в этом 64-мерном векторном пространстве. Кроме того, нам нужна структура данных для поддержки недорогих обновлений, когда мы получаем поток действий, выполняемых каждым актором. Нам также необходимо делать запросы в реальном времени по мере обновления структуры данных. Ой!
Чувствительный к местности лес хеширования
Выбранная нами структура данных - это лес хеширования, чувствительный к местности (LSH Forest). Название длинное, но основная концепция проста. Мы хэшируем каждый вектор из 64 чисел с плавающей запятой в корзину в соответствии со знаковым битом каждого числа с плавающей запятой. Фактически, мы квантуем каждое 32-битное число с плавающей запятой в один (знаковый) бит. Чтобы найти похожие элементы, мы ищем 64-битный вектор с плавающей запятой для актора запроса, квантуем его до 64-битных значений, а затем находим соответствующий сегмент. Для каждого элемента в этой корзине мы находим 64 вектора с плавающей запятой и вычисляем косинусное сходство между ними. Мы возвращаем товары с наивысшими баллами.
У этого поискового алгоритма высокая точность, но низкая запоминаемость. Другими словами, ЕСЛИ мы возвращаем товары, они похожи, но этот подход может не найти большинство похожих товаров.
С LSH Forest вместо поиска только в исходном сегменте запроса мы также ищем и оцениваем несколько хеш-сегментов рядом с исходным сегментом запроса. Здесь встречаются теория и практика. Неудачный выбор стратегии зондирования может дать правильный, но медленный ответ. Мы должны согласовать стратегию зондирования и реализацию хеш-таблицы, которые вместе обеспечивают хорошую производительность.
Постоянное и гибкое хранилище ключей и значений
В Smyte мы имеем дело с масштабом. У наших клиентов десятки, а иногда и сотни миллионов пользователей, многие из которых активны ежедневно. Нам нужна система хранения, которую можно масштабировать до такого же постоянного уровня. Мы могли бы сегментировать традиционную базу данных SQL по акторам со значительными затратами как с точки зрения эксплуатационных расходов, так и с точки зрения времени отклика. Однако нам нужно только хранилище ключей и значений. Мы могли бы использовать размещенное хранилище ключей и значений, такое как Amazon Dynamo, но размещенные сервисы несут расходы и страдают от сетевых задержек. Мы могли бы разместить свои собственные серверы Redis, но, как мы обсуждали ранее, Redis не подходит для наших нужд. Вместо этого мы выбрали RocksDB.
RocksDB, разработанный в Facebook, представляет собой высокопроизводительное, постоянное, встроенное хранилище ключей и значений. Разделив наши данные на несколько экземпляров RocksDB, мы можем получить как постоянство, так и высокую производительность при низких эксплуатационных расходах. Важно отметить, что RocksDB поддерживает последовательные запросы с очень высокой производительностью. Реализуя стратегию зондирования, которая в значительной степени полагается на последовательные запросы, мы получаем высокую производительность.
Рассмотрим один запрос для 64-битной корзины. Мы можем рассматривать 64-битное значение как ключ в полностью упорядоченном пространстве ключей, используя канонический (буквенно-цифровой) порядок, например с 5 битами:
… < 00001 < 00010 < 00011 < 00100 < 00101 < …
Если мы ищем сегменты 00010 (и 00100) в дополнение к 00011, мы знаем, что найденные нами элементы будут соответствовать как минимум по 3 (2) битам. Фактически верно, что минимальное количество битов соответствия строго уменьшается по мере удаления от первоначального зонда. Это легко увидеть, потому что это число ограничено снизу длиной самого длинного общего префикса. Если мы рассматриваем ключ (например, 000111) как путь в двоичном дереве, листьями которого являются элементы, то длина самого длинного общего префикса - это просто глубина ближайшего общего предка (nca). По мере удаления от начального листа это значение монотонно не уменьшается.
Из-за этого свойства префикса хеширование с учетом местоположения фактически использует несколько хеш-таблиц, где ключи каждой дополнительной хеш-таблицы представляют собой просто фиксированную перестановку ключей исходной хеш-таблицы. Это дает место для отзыва.
Наши расширения
Стандартный чувствительный к местности лес строится статически. Мы постепенно создаем свои в потоковом режиме. По мере поступления новых действий, связанных с актером / элементом, мы обновляем вектор с плавающей запятой 64, который представляет актера / элемента, и соответственно обновляем хэш-таблицы, используя механизм RocksDB для уплотнения для выполнения ленивых обновлений.
Срок действия
Со временем актеры уезжают. Чтобы решить эту проблему, мы помечаем каждый элемент и каждую запись в хеш-таблице датой истечения срока действия, которую мы (необязательно) обновляем при каждом добавлении нового действия к этому элементу. Мы используем функцию сжатия RocksDB для ленивой очистки просроченных записей.
Возрастное ослабление
Мы также (необязательно) придаем большее значение новым действиям. Мы делаем это, взвешивая действия в соответствии с их возрастом. Для этого мы применяем экспоненциальное затухание к значениям с плавающей запятой при обращении к ним.
Взвешивание важности
Некоторые действия больше указывают на схожесть, чем другие, например, предоставление номера кредитной карты. Следовательно, мы более серьезно взвешиваем такие действия с помощью простой трехуровневой схемы «высокий», «средний» и «низкий».
Частотное взвешивание
Некоторые действия менее указывают на схожесть, например, доступ к общему IP-адресу. Для подтверждения этого мы ведем (приблизительные) счетчики всех действий. Менее частые действия (среди всех участников для данного клиента) имеют больший вес, чем более частые действия.
Представление
Наше текущее решение разделяет элементы на несколько встроенных хранилищ RocksDB, принимая новые действия со скоростью более 91 000 действий в секунду на каждый сегмент. Используя функции поиска по префиксу RocksDB, мы можем хранить наборы данных от всех наших клиентов вместе без риска утечки.
Запросы транслируются во все шарды с каждым возвращением совпадений хранимых в нем элементов. Затем клиент объединяет эти частичные результаты в простую очередь приоритетов, чтобы выбрать наилучшие совпадения. Скорость чтения немного ниже, чем у записи из-за вычисления показателя сходства косинуса.
Вывод
Один из способов, с помощью которого Смайт останавливает плохих актеров, - это отслеживать их поведение и обнаруживать сходства. Комбинируя правильные алгоритмы с правильными реализациями, Smyte достигает высокой производительности при низких затратах. Посетите наш сайт, чтобы узнать больше.
