Игры со спамом

Новое программное обеспечение, которое использует теорию игр, позволяет не просто защищаться от спама, но быть на шаг впереди.

© 2001 Imagine Entertainment Спам-фильтры защищают компьютерные системы от обилия назойливой рекламы и фишинговых сообщений, а специальное ПО распознает атаки на сервер и отличает легальные операции с кредитными картами от фальшивых. Разработка программ для обеспечения безопасности является непростым делом, поскольку в рядах спамеров, равно как и тех, кто занимается мошенничеством с кредитными картами, имеются специалисты, целенаправленно создающие средства для обхода защитных механизмов.

Традиционные методы борьбы со спамом

До настоящего времени спамеры удерживали лидерство, владея инициативой в этом негласном соревновании, в то время как их противники могли лишь реагировать на уже обнаруженные уловки. Примером может служить появление особой разновидности нежелательных рассылок — этот период разработчики антиспамовых фильтров назвали «Великое сражение со спамом через рассылку изображений 2006 года». Применявшиеся до этого времени защитные инструменты использовали три механизма — классификацию текстовой информации, черные списки IP-адресов и черные списки известных спам-сообщений. Однако они оказались бессильны перед новым видом спама.

Фильтры текстовых сообщений анализируют корреспонденцию, в которой наряду со спамом есть и вполне легальные письма, и определяют для каждого слова так называемый «показатель спама». Значение последнего всякий раз увеличивается, если спам-рассылка содержит соответствующее слово. Когда при анализе сообщения этот показатель превышает определенное значение, оно классифицируется как спамовое.

В черные списки IP попадают серверы с отсутствующими механизмами идентификации, поскольку они регулярно используются для рассылки назойливой рекламы. IP-адреса, о которых известно, что интернет-провайдеры выделяют их домашним пользователям, также внесены в эту базу.

Черные списки известных рекламных писем позволяют блокировать наиболее популярные варианты нежелательных сообщений. Они обновляются с помощью системы Honeypots — специальных адресов электронной почты, предназначенных исключительно для получения спама.

Разработчики средств для рассылки навязчивой рекламы смогли справиться с подобными защитными механизмами. Важную роль в этом сыграли так называемые ботнеты, позволяющие объединять зараженные вирусами ПК в гигантские сети. Владельцы таких систем могут управлять множеством «зомбированных» компьютеров. По команде все узлы сети загружают образец «бессмысленного текста с вероятностной грамматикой», который инициирует создание спамовых сообщений. После этого каждый из зараженных ПК генерирует и рассылает небольшое количество писем, соответствующих данному образцу.

Таким образом злоумышленники обходят три классических механизма защиты от спама. Поскольку чаще всего рассылки не похожи друг на друга, черные списки известных спамовых сообщений становятся бесполезными. А за счет того, что с каждого компьютера отправляется лишь небольшое число писем, преодолевается защита посредством черного списка IP-адресов. Фильтры, использующие анализ текстовой информации, нейтрализуются с помощью атак Good Word: образцы содержат поля, в которые помещены случайным образом подобранные, но кажущиеся вполне нормальными фрагменты текста. Для слов, имеющих высокий спамовый показатель, изобретаются нестандартные, но при этом узнаваемые способы написания (например, «V1@gra»). Но полностью перехитрить фильтры, основанные на анализе текстовой информации, позволил спам в виде изображений. Такие программы, как Reactor Mailer, автоматически преобразуют текст в картинки, которые могут быть случайным образом индивидуализированы.

Теория игр против спама

На помощь разработчикам защитных механизмов приходит теория игр. Она предполагает создание математических моделей для изучения оптимальных стратегий в играх с несколькими участниками. В нашем случае ими являются провайдер электронной почты с одной стороны и распространитель спама — с другой. У каждого из них есть цель, которая может быть выражена с помощью критериев оптимизации: поставщик услуг e-mail желает отфильтровать максимальный объем спама, не блокируя при этом отправку нормальных сообщений. А распространитель назойливой рекламы хочет предельно увеличить свой доход — например, за счет поступления заказов на медикаменты или в результате того, что получатели рассылок оставляют данные о своих счетах на фишинговых сайтах. Хотя цели игроков не вполне противоположны, они находятся в неразрешимом противоречии друг с другом.

Обе стороны обладают своими стратегиями и приемами. Выражаясь математическими терминами, каждый располагает определенным игровым пространством. Например, провайдер может с помощью фильтра, работающего на основе анализа текстовой информации, присваивать отдельным словам спамовый показатель. Распространитель рекламы, в свою очередь, может варьировать образец, в соответствии с которым составляются сообщения, или изменять содержание писем и способ написания слов. Игровые пространства участников этого состязания — в отличие, скажем, от шахмат — не конечны: поставщик услуг может присвоить каждому слову в качестве спамового показателя любое возможное число, а распространитель спама способен изобрести любой возможный способ написания слов. Кроме того, обоим игрокам известно содержание разосланных в прошлом спамовых сообщений и результаты их фильтрации — эти сведения они присовокупляют к своим размышлениям относительно данной проблемы. Согласно теоретической модели, теперь они должны одновременно перейти на использование новых фильтра и, соответственно, образца для спамовой кампании. В этом и заключается отличие от классической процедуры, согласно которой игроки должны реагировать только на действия противника.

И все-таки, существует ли оптимальная для обеих сторон стратегия в случае с классификационной игрой по электронной почте? Эффективность спам-фильтра зависит от стратегий, выбираемых распространителем навязчивой рекламы, и того, как он изменяет образец своих сообщений. При этом доход от спамовой кампании обуславливается показателями, присваиваемыми фильтром содержащимся в сообщениях формулировкам. Все эти данные невозможно знать заранее — их стоит рассматривать как совокупность вероятных вариантов внутри игрового пространства. Поэтому размышления об оптимальной стратегии приводят обоих игроков к бесконечной рекурсии: «Если он думает, что я думаю о том, что он думает…»

Решение проблемы

Гениальное решение такой дилеммы нашел в 1950 году математик Джон Нэш (в фильме «Игры разума» его сыграл Рассел Кроу), за что в 1994-м получил Нобелевскую премию по экономике. Если оба игрока ведут себя рационально, то каждый стремится к достижению своей цели, которая максимизирует его выигрыш. Когда оба участника полагаются на то, что противник будет вести себя разумно, устанавливается однозначное равновесие Нэша, которое представляет собой оптимальную стратегию для обоих игроков. Одностороннее отклонение от этого равновесия ведет к уменьшению выигрыша. Равновесие Нэша является решением описанной выше проблемы, связанной с бесконечной рекурсивной последовательностью, однако оно возможно лишь в том случае, если фильтр защищающейся стороны и прибыль атакующей соответствуют определенным математическим параметрам, что требует доказательства.

Для этого игру переформулируют с помощью математического приема, называемого постановкой задачи нулевой точки. Специальная функция измеряет, какой дополнительный выигрыш может получить каждая из двух сторон, если отклонится от своей стратегии.

С помощью так называемой градиентной технологии для пошаговой оптимизации можно найти нулевую точку данной функции. Это и является решением: в случае равновесия Нэша никто из игроков не может улучшить собственный результат путем изменения своей стратегии.

Что это означает на практике? Вместо того чтобы по-прежнему отлаживать процесс присвоения спамовых индексов, с чем очень хорошо справлялись технологии прошлого, новый фильтр Нэша использует градиентный метод для установления равновесия Нэша. Если тренировать обычный фильтр и фильтр Нэша специальными файлами, а затем одновременно включить их, то поначалу они будут работать примерно с одинаковой эффективностью. Скорость поступления спамовых сообщений, которые не распознает классический механизм, увеличивается по мере его использования и через месяц-три составляет величину, многократно превышающую исходный показатель. Таким образом, распространителю спама удается обмануть его новыми трюками. Фильтр Нэша, напротив, остается работоспособным в течение продолжительного периода. Он предвидит возможные варианты написания сообщений и распознает их в качестве признаков спама. Лишь по истечении достаточно длительного времени требуется актуализировать фильтр Нэша с помощью новых тренировочных файлов.

Следующим шагом будет повышение эффективности математической процедуры оптимизации, которое сделает фильтр Нэша пригодным для коммерческого использования — в частности, хостинг-провайдерами.

Что такое равновесие Нэша?

Гонка вооружений в условиях равновесия Нэша «Игру» между спамером и провайдером (а в конечном итоге — пользователем) можно сравнить со взаимодействием вора и его потенциальной жертвы. Если обе стороны владеют различными технологиями атаки и, соответственно, защиты от нападения, то с точки зрения теории игр это приводит к «гонке вооружений». Атакующий может пойти прямым путем, который приведет к победе только в случае плохой защиты, или же инвестировать средства в атаку, которая даже при оптимальной обороне будет успешной. При достижении равновесия Нэша жертва готовится к трудно отразимому нападению, которое впоследствии осуществляет вор. Если игрок в одностороннем порядке отклоняется от этой стратегии, его выигрыш уменьшается.

В реальном мире это обычно выглядит так: спамер совершенствует свою технологию, на это реагирует провайдер, который также развивает меры защиты. В теории игр, напротив, обе стороны выбирают стратегию одновременно. В этом заключается мощь нового фильтра Нэша: он сокращает время реагирования провайдера, поскольку заранее вычисляет возможные действия спамера. Тем самым удается сразу добиться равновесия Нэша, которое не обеспечивает идеальной защиты от спама, но представляет собой оптимальный вариант.

Результат применения нового фильтра Нэша

Точность в случае с 65 000 официальных электронных сообщений Исследовательская группа из Потсдамского университета проверила точность, с которой новый фильтр Нэша распознает спам, и сравнила ее с показателями одного из классических средств. Для этого оба инструмента вначале «тренировались» на 6000 спамовых сообщений, а затем на обработку были отправлены 65 000 официальных и 40 000 частных писем. Со временем эффективность распознавания падала, поскольку спамеры постоянно запускали в оборот новые образцы. Однако фильтр Нэша отчасти предполагал их наличие, поэтому на протяжении всего испытательного периода его показатели оставалась на более высоком уровне, и отправить его на повторную «тренировку» пришлось значительно позже.

Точность в случае с 40 000 частных электронных сообщений