Незаконченная статья о спаме

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

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

    Итак, что называем спамом?

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

    Массовость – основной признак спама. Что характерно, спамеры не оригинальны в таком подходе. Они лишь следуют пути, отработанному природой за миллионы лет эволюции.

    Простой подсчет показывает, что каждое дерево кедра дает в среднем за свою жизнь один миллион жизнеспособных семян. Однако число деревьев на нашей планете не увеличивается, значит, уровень естественного отбора составляет примерно один из миллиона. Именно такой уровень обеспечивает полноценное воспроизводство и устойчивость вида. (http://kedr.forest.ru/culture.html)

    Например, у скумбрии (Scomber scombrus) за первые 50-70 суток жизни личинок гибнет около 99,9996% особей. Таким образом, из миллиона выметанных яиц (а одна самка скумбрии производит за раз до полумиллиона мелких икринок, которые плавают в толще воды) до половозрелости могут дожить всего несколько особей. Тем не менее скумбрия остается весьма обычной рыбой, что подтверждается и наличием ее на прилавках рыбных магазинов. (http://elementy.ru/news/430696)


    С один ряд с ними мы можем поставить и спамеров, которые в стремлении доставить письмо получателю делают ставку на массовость. И, что самое печальное, этот подход себя оправдывает.

    По имеющимся данным, процент пользователей, которые совершали покупки рекламируемые в спам-сообщениях (например, по линку «Click here», которое встречается в большинстве сообщений), в 2005 году составлял 11% (http://www.technewsworld.com/story/44655.html), в 2006 – около 6% (http://www.yale.edu/its/email/spam/whyspam.html), а в 2008 – 29% (http://www.marshal.com/pages/newsitem.asp?article=748&thesection=news).
    Это совершенно невероятное число, но учитывая, что в последнем исследовании было опрошено всего 622 человека, результаты, скорее всего далеки от точных. Но даже если этот результат завышен – это все равно сотни и тысячи людей, которые каждый день доказывают, что спам приносит доход своим хозяевам.

    С другой стороны, есть и цифры совершенно иного характера (http://habrahabr.ru/blogs/spam/44353/) – «Реальный CTR спама составляет 0,000008%». Вероятно, также это не вся правда жизни. Но доход все равно есть.

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

    Каким бывает спам (http://ru.wikipedia.org/wiki/Спам)



    Любая спамерская рассылка преследует определенную цель — иначе затраты на нее
    просто теряют всякий смысл. В зависимости цели меняется и содержание писем.

    Подавляющее большинство спам-сообщений – это реклама (для сравнения – фишинговые письма или письма с вирусами в сумме составляют не более двах процентов от общего числа спама).

    Среди рекламных объявлений наиболее популярны (статистика за сентябрь): Спам «для взрослых» — 28%, «Медикаменты; товары и услуги для здоровья» — 19%, «Образование» — 12%, «Реплики элитных товаров» — 6%, «Отдых и путешествия» — 6%.

    Реклама собственно спамерских услуг в последнее время плавает вокруг отметки в 5%.

    Полюбуйтесь, что спамеры сами говорят о спаме:
    «Некоторым кажется, что рассылка спама – это неэтичный метод рекламы, но как
    показывает практика, многие хотя бы из любопытства просматривают письма такого
    рода. И обязательно среди них находится потенциальный клиент,
    заинтересовавшийся предложением. Поскольку рассылка спама – достаточно
    недорогая услуга, многие заказчики, оценив эффективность такого рычага
    воздействия на потенциальных потребителей, становятся постоянными заказчиками и
    рекомендуют такой способ рекламы другим коллегам.» (http://www.direct-mail-reklama.ru)


    Распространение



    Технически, спам распространяется в основном по электронной почте. Недостатки почтовых протоколов, разработанных в конце прошлого века, простота реализации программного обеспечения для массовой рассылки, доступность баз адресов дают здесь широкое поле для деятельности. Например, любой начинающий может почитать FAQ о спаме forum.antichat.ru/thread58130.html или получить более или менее сносный ответ на интересующий вопрос forum.antichat.ru/thread72829.html.

    Собственно рассылка в процессе технического прогресса также изменялась – от прямых рассылок самими спамерами до взлома компьютеров пользователей и создания специализированных ботнетов (http://www.viruslist.com/ru/spam/info?chapter=156608519)

    В последнее время получили распространение спам по IM, на форумах и блогах. Например, на www.xakep.ru есть заметка под названием «Microsoft занимает 5-е место в списке самых терпимых к спаму провайдеров»

    Пример с одноклассниками. Лично мне приходило сообщение от одноклассника.
    Привет, помоги пожалуйста, денег на счету нет(проголосуй за меня пожалуйста, отправь смс на номер 3649 c текстом «XX 222761» ( 10 рублей стоит)


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

    Проблемы, которые вызывает спам



    Основные виды вреда, наносимого спамом (http://beskov.ru/2006/05/16/spam-harm/).

    1. Нагрузка на сетевые каналы — согласно последним данным, порядка 80%
    пересылаемых в интернете писем являются спамом и вирусами. Повышенная нагрузка
    приводит к повышенным рискам сбоя и затратам на передачу заведомо ненужных
    данных.
    2. Забивание места на почтовых серверах — во многих случаях спам может определяться и удаляться, но это происходит далеко не всегда.
    3. Нагрузка на вычислительные мощности почтовых серверов, занятых спамофильтрацией.
    4. Затраты обслуживающего персонала на настройку серверов, очистку от спама и настройку антиспам-фильтров. (потери рабочего времени)
    5. Забивание места на машинах пользователей — если пользователь использует программу-клиент для сбора почты, то во многих случаях спам приходит прямо на машину и хранится там до его удаления.
    6. Затраты пользователя на просмотр и удаление спама из своего ящика.

    В частности, за период 15 – 21 сентября 2008 г. www.spamtest.ru/document.html?context=15946&pubid=208050461 для спама составила 80,5%

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

    Для России общий ущерб всех жертв спама переваливает за 200 млн. долл. в год, а доход спамерских компаний, по самым нескромным оценкам, может составлять до нескольких
    миллионов долларов в год.

    Борьба со спамом



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

    По способу настройки методы можно условно разделить на локальные и распределенные. Распределенные методы позволяют «учиться на чужих ошибках».

    У любого метода противостояния спаму можно выделить ряд характеристик, по которому мы эти методы будем оценивать и сравнивать.

    — Эффективность. Самый главный параметр. Выражается в процентах. Определяется, как процент корректно определенных и спрятаны от пользователя спам-сообщений. Если от ста отнять это значение, то получим параметр под названием «ложно-негативные» срабатывания, то есть процент спам-сообщений, которые все же доходят до пользователя.
    — Ложно-позитивные срабатывания. «Чистые» письма, определенные как спам или не дошедшие до пользователя.
    — Влияние на сетевые каналы (насколько метод позволяет снизить нагрузку за счет уменьшения количества спам-сообщений).

    Итак, вкратце перечислим главные методы борьбы со спамом. К блокированию относятся:

    «Черные» списки. Кардинально решает проблему трафика, его получается снизить примерно наполовину. Однако эффективность такого метода далека от идеала – если фильтр удаляет около 50 процентов спама, то доля удаляемых реальных сообщений – около 30 процентов. Очень вредит честным компаниям.

    В качестве другой крайности – белые списки, которые игнорируют все остальную почту. Проблему трафика не решает. Эффективность 100% :) Ложно-позитивная составляющая, к сожалению, также стремится с этому пределу.

    Также существую «серые» списки как следующая ступень в эволюции черных списков:
    Метод серых списков основан на том, что «поведение» программного обеспечения, предназначенного для рассылки спама отличается от поведения обычных почтовых серверов, а именно, спамерские программы не пытаются повторно отправить письмо при возникновении временной ошибки, как того требует протокол SMTP. Точнее, пытаясь обойти защиту, при последующих попытках они используют другой релей, другой обратный адрес и т. п., поэтому это выглядят для принимающей стороны, как попытки отправки разных писем. www.redcom.ru/isp/ispNews/netNews/ni1170203597
    Уровень ложно-позитивных срабатываний снижается до нескольких процентов, что весьма неплохо.

    Все методы, перечисленные далее, относятся в фильтрации.

    Официально следующая группа методов названия не получила. Такие методы на вопрос, является ли письмо спамом, отвечают по косвенным признакам, по поведению писем.

    Существуют такие разновидности:

    Вакцинация: сервер доставляет немедленно письмо только одному пользователю, который может сообщить, что это спам (например, кликнув по какой-нибудь кнопке в интерфейсе своего почтового клиента). Сервер «обучит» свой основной фильтр, и вредное письмо не попадет во вторую волну доставки. Иногда называется методом «голосования».

    Ловушка (honeypot). Метод, кстати, (не знаю, впервые или нет) был предложен К. Касперски в его книге «Записки исследователя компьютерных вирусов». Создается определенное число «случайных» почтовых ящиков, не принадлежащих реальным пользователям. Спамеры находят этот адрес либо где-то специально засвеченным на каком-нибудь форуме, либо просто перебором букв (abc@mosglavprodsnab.com). Исходя из того, что реальная почта никогда не приходит на такой ящик, с почти стопроцентной уверенностью можно сказать, что это – спам. На практике – «В тестах PC Magazine сервис SkyScan показал уровень обнаружения спама в 96% при доле ложных срабатываний 0.48%» (http://www.lexa.ru/articles/distributed-antispam-2.html)

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

    Кстати, все эти методы дают эффект только при применении распределенной архитектуры. В частности Спаморез пользуется таким сервисами, как Razor и DCC для определения массовости писем.

    Основной путь противодействия таким системам – «рандомизирование» — рассылка копий оригинала, каждая из которых отличается весьма незначительно – порядком или набором слов. С этим вполне успешно можно справиться, вычисляя контрольную сумму не от всего содержимого, а от какой-то части, либо случайно выбранных слов, либо одним из многочисленных алгоритмов нечеткого сравнения текстов.

    Фильтрация на основе содержимого письма.

    Эвристический метод. Создается набор шаблонов, с которыми сравнивается контент. В основном, это делается при помощи регулярных выражений. Требует невероятных затрат по поддержанию в актуальном состоянии. Эффективность – около 70-80%, много ложно-негативных срабатываний.

    Методы искусственного интеллекта. Мне на сегодняшний день известно только о том, что Spam Assassin назначает оценку письму с помощью алгоритмов нейронных сетей.

    Статистические методы, как уже понятно из названия, не заостряют внимание на
    смысле слов в емейлах. То есть, совершенно неважно, в каком контексте
    используется слово «sex»- реклама ли это интимных товаров, или графа «пол» в
    анкете соискателя. Методы основаны на вычислении вероятности того, что письмо
    является спамом. Основной способ вычисления — формула Байеса
    (http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%B0)

    Основополагающим трудом в области фильтрации является статья Пола Грэма «A plan
    for spam» (http://paulgraham.com/spam.html), а также ее продолжение — paulgraham.com/better.html. (Практически любая статья, в которой
    встречается слово «спам», ссылается на Грэма.)

    В общих чертах, для определения спама необходимо
    — разбить текст на слова (в случае емейл-сообщения сюда должна входить и тема письма, и какая-то часть заголовков). Конкретно слова – это частный случай разбиения текста на части, которые называются «токены». Например, различными методами нарезки текста можно противостоять «замусориванию» текста.
    — находится частота встречаемости токенов в спам-сообщениях (хранится в базе, создается в процессе «обучения» фильтра)
    — выбирается репрезентативная выборка (Грэм выбирал 15 самых часто встречающихся).
    — по формуле Байеса вычисляется вероятность того, что письмо – это спам.
    — если вероятность превосходит некое пороговое значение (80-90%), то письмо отфильтровывается и автоматически уходит в папку «Спам».

    [формула] Слово X встречается в сообщениях, помеченных как спам в 95%, Y — в
    60%.

    Вероятность того, что письмо — спам: P(SPAM) = P(X) * P(Y) / (P(X) * P(Y) — (1-P(X)) * (1-P(Y))) = 0.95 * 0.6 / (0.95 * 0.6 + 0.05 * 0.4) = 0.57 / (0.57 +
    0.02) = 0.966.

    Слово X встречается в сообщениях, помеченных как спам в 50%, Y — в
    60%.

    Вероятность того, что письмо — спам: P(SPAM) = P(X) * P(Y) / (P(X) * P(Y) — (1-P(X)) * (1-P(Y))) = 0.5 * 0.6 / (0.5 * 0.6 + 0.5 * 0.4) = 0.3 / (0.3 +
    0.2) = 0.6.


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

    Скрытые модели Маркова, метод, основанный на существенно более сложном
    математическом аппарате. Используется как вспомогательный метод для поиска
    «почти» похожих текстов. К сожалению, является палкой о двух концах — кроме
    задачи распознавания отлично справляется и с генерацией текста. Кроме спам-сообщений, генерированные сообщения активно используется, например, в живом журнале.

    Эффективность статистических методов сильно зависит от того, что подается на вход. Например, наивный подход, когда в алгоритм передаются все слова, разделенные пробелами или переходом строки, жестоко обламывается, если все пробелы заменить на подчеркивания. Или же написать «Виагра», потом номер телефона, а потом – три страницы текста из «Войны и Мира» мелким шрифтом.

    «Нарезка» текста на части (их называют «токены») может производится по-разному, но общая часть у них одна: текст «нарезается» на части, которые представляют собой комбинации слов. Например, алгоритм OSB (Orthogonal Sparse Bigram) нарежет фраза «Вы – интернет будущего» так –
    — Вы интернет *
    — Вы * будущего
    — * интернет будущего.
    О сравнении классификаторов можно немного почитать тут: www.esi.uem.es/~jmgomez/papers/sigir07.pdf. Также будет полезно узнать о проекте, целиком посвященному задаче классификации текстов – CRM114 — crm114.sourceforge.net/wiki/doku.php?id=documents

    Что дальше?



    Нужно взять лучшее от всех методов, избавившись от недостатков. То есть, например, объединять вакцинацию и автоматическую фильтрацию.

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

    Вывод



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

    Комментарии 2

      +2
      > Кроме формулы байеса, также используется распределение хи-вадрат. Это
      > распределение, хорошо только тем, что зависит только от разрядов (отрезков
      > области определения), и позволяет оценить отклонение не только от равномерного, а от
      > распределения любого вида. (Вот это мне и самому не очень понятно. Было бы здорово услышать внятное объяснение).
      скорее всего имелось в виду отличие хи-квадрат теста от t-теста, в котором используется «нормальное распределение» (normal distribution)
      т.к. в реальности не все данные распределены «нормально», то считается, что хи-квадрат тест (chi-square) лучше моделирует данные
        +1
        Замечательная статья. Почему бы ее не выложить в соответствующий блог?

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое