СИСТЕМЫ И СПОСОБЫ ОБНАРУЖЕНИЯ СПАМА С ПОМОЩЬЮ СИМВОЛЬНЫХ ГИСТОГРАММ
SYSTEMS AND METHODS FOR SPAM DETECTION USING CHARACTER HISTOGRAMS

УРОВЕНЬ ТЕХНИКИ
[0001] Изобретение относится к способам и системам для классификации электронных сообщений, и в частности к системам и способам для фильтрации незапрашиваемых коммерческих электронных сообщений (спама).
[0002] Незапрашиваемые коммерческие электронные сообщения, известные также как спам, составляют значительную часть трафика коммуникационных линий во всем мире, что оказывает воздействие на службы по обмену сообщениями посредством компьютеров и телефонов. Спам может принимать многие формы, от незапрашиваемых сообщений электронной почты до спамовых сообщений, замаскированных под комментарии пользователей на различных Интернет-сайтах, например на сайтах блогов и социальных сетей. Спам отнимает ценные аппаратные ресурсы и оказывает воздействие на производительность, при этом он воспринимается многими пользователями коммуникационных услуг и/или Интернета как раздражающий и назойливый.
[0003] В случае спама в электронной почте можно использовать программное обеспечение, выполняемое на компьютерной системе пользователя или провайдера услуг электронной почты, для классификации сообщений электронной почты как спам или как не спам и даже для проведения разграничений между разными видами спамовых сообщений (например, предложения продуктов, контент для взрослых, аферы, организуемые по электронной почте). Затем спамовые сообщения могут направляться в специальные папки или удаляться.
[0004] Подобным образом можно использовать программное обеспечение, выполняемое на компьютерных системах провайдера контента, для перехватывания мошеннических сообщений, отправленных на Интернет-сайт, и для предотвращения отображения соответствующих сообщений или для отображения предупреждений пользователям веб-сайта о том, что соответствующие сообщения могут представлять собой спам.
[0005] Для идентификации спамовых сообщений было предложено несколько подходов, включая сопоставление исходного адреса сообщения со списками известных адресов нарушителей или доверенных адресов (получивших специальное название «черный список» и «белый список», соответственно), поиск определенных слов или моделей слов (например, рефинансирование, Viagra, акции) и анализ служебных заголовков сообщений. Способы выделения/сопоставления признаков часто используются в сочетании с методами автоматической классификации данных (например, с байесовской фильтрацией, нейронными сетями).
[0006] Спам часто поступает в виде быстрой последовательности групп сходных сообщений, известных также как волны спама. Форма и содержание спама может меняться существенным образом от одной волны спама к другой, поэтому успешности обнаружения будут способствовать способы и системы, способные быстро распознавать и реагировать на новые волны спама.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
[0007] Согласно одному из аспектов способ включает в себя: использование компьютерной системы для получения целевой строки, которая образует часть электронного сообщения; определение критерия пригодности строки согласно целевой строке; и предварительную фильтрацию совокупности ссылочных строк по критерию пригодности строки для формирования группы строк-кандидатов. В ответ на отбор строк-кандидатов компьютерную систему используют для выполнения первого сравнения между символьной гистограммой целевой строки и символьной гистограммой строки-кандидата из группы строк-кандидатов и второго сравнения между временной отметкой электронного сообщения и временной отметкой строки-кандидата. Компьютерная система определяет, является или нет электронное сообщение спамом, по результату первого сравнения и второго сравнения.
[0008] Согласно другому аспекту компьютерная система включает в себя по меньшей мере процессор, запрограммированный так, чтобы: получать целевую строку, которая образует часть электронного сообщения; определять критерий пригодности строки, соответствующий целевой строке; и выполнять предварительную фильтрацию совокупности ссылочных строк по критерию пригодности строк для формирования группы строк-кандидатов. Процессор дополнительно запрограммирован так, чтобы выполнять, в ответ на отбор строк-кандидатов, первое сравнение между символьной гистограммой целевой строки и символьной гистограммой строки-кандидата из группы строк-кандидатов и второе сравнение между временной отметкой электронного сообщения и временной отметкой строки-кандидата. Процессор дополнительно запрограммирован так, чтобы определять, является или нет электронное сообщение спамом, по результату первого сравнения и второго сравнения.
[0009] Согласно еще одному аспекту способ включает в себя: использование компьютерной системы для получения электронного сообщения; в ответ на получение электронного сообщения - извлечение целевой строки из электронного сообщения; передачу целевой строки антиспам-серверу; и в ответ на передачу целевой строки - получение целевой метки, указывающей на то, является или нет электронное сообщение спамом, причем целевую метку определяют на антиспам-сервере. Определение целевой метки включает в себя: использование антиспам-сервера для определения критерия пригодности согласно целевой строке; предварительную фильтрацию совокупности ссылочных строк согласно условию критерия для формирования группы строк-кандидатов; в ответ на отбор строк-кандидатов - выполнение первого сравнения между символьной гистограммой целевой строки и символьной гистограммой строки-кандидата из группы строк-кандидатов и второго сравнения между временной отметкой электронного сообщения и временной отметкой строки-кандидата; и определение целевой метки по результату первого сравнения и второго сравнения.
[0010] Согласно еще одному аспекту способ включает в себя: использование компьютерной системы для получения целевой строки, которая образует часть электронного сообщения; определение критерия пригодности строки согласно целевой строке; предварительную фильтрацию совокупности ссылочных строк по критерию пригодности строки для формирования группы строк-кандидатов. В ответ на отбор строк-кандидатов способ предусматривает использование компьютерной системы для определения межстрочного расстояния, отделяющего целевую строку от строки-кандидата из группы строк-кандидатов, при этом межстрочное расстояние определяют по числу употреблений выбранного символа в целевой строке и числу употреблений выбранного символа в строке-кандидате. Способ также включает в себя определение по межстрочному расстоянию, является или нет электронное сообщение спамом.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[0011] Изложенные выше аспекты и преимущества настоящего изобретения будут более понятными при прочтении следующего подробного описания со ссылками на чертежи, на которых:
[0012] на фиг. 1 изображена иллюстративная антиспам-система согласно некоторым вариантам осуществления настоящего-изобретения;
[0013] на фиг. 2 изображена иллюстративная конфигурация аппаратного обеспечения серверной компьютерной системы согласно некоторым вариантам осуществления настоящего изобретения;
[0014] на фиг. 3-А изображена иллюстративная транзакция по обнаружению спама, осуществляемая между клиентским компьютером и антиспам-сервером, согласно некоторым вариантам осуществления настоящего изобретения;
[0015] на фиг. 3-В изображена иллюстративная транзакция по обнаружению спама, осуществляемая между контент-сервером и антиспам-сервером, согласно некоторым вариантам осуществления настоящего изобретения;
[0016] на фиг. 4 изображен иллюстративный целевой индикатор целевого сообщения, при этом индикатор включает в себя целевую строку и дополнительные данные для идентификации спама, согласно некоторым вариантам осуществления настоящего изобретения;
[0017] на фиг. 5 изображена схема иллюстративного множества приложений, выполняемых на антиспам-сервере, согласно некоторым вариантам осуществления настоящего изобретения;
[0018] на фиг. 6 изображена иллюстративная символьная гистограмма, связанная с целевой строкой и вычисленная для группы классов символов, согласно некоторым вариантам осуществления настоящего изобретения;
[0019] на фиг. 7 изображено иллюстративное приложение-детектор спама, работающее на антиспам-сервере, показанном фиг. 1, согласно некоторым вариантам осуществления настоящего изобретения;
[0020] на фиг. 8 изображена группа кластеров, представленных в гиперпространстве признаков, где каждый кластер включает в себя коллекцию подобных элементов, согласно некоторым вариантам осуществления настоящего изобретения;
[0021] на фиг. 9 изображена иллюстративная последовательность этапов, выполняемых детектором спама, показанным на фиг. 7, согласно некоторым вариантам осуществления настоящего изобретения;
[0022] на фиг. 10-А изображен результат компьютерного эксперимента, включающего в себя определение времени вычислений для генерации символьных гистограмм для совокупности тестовых строк в виде функции от количества различных символов в тестовых строках;
[0023] на фиг. 10-В изображен результат компьютерного эксперимента, включающего в себя определение времени вычислений для генерации символьных гистограмм для совокупности тестовых строк в виде функции от длины строки в тестовых строках;
[0024] на фиг. 10-С изображен результат компьютерного эксперимента, включающего в себя определение времени вычислений для расчета множества межстрочных расстояний для коллекции тестовых строк в виде функции от количества различных символов в тестовых строках;
[0025] на фиг. 10-D изображен результат компьютерного эксперимента, включающего в себя определение времени вычислений, необходимого для расчета множества межстрочных расстояний для коллекции тестовых строк в виде функции от длины строки в тестовых строках;
[0026] Фиг. 11, где изображена точечная диаграмма, связывающая длину строки с индикатором временной отметки для коллекции реальных комментариев в блогах, включающих в себя как спам, так и не спам;
[0027] на фиг. 12 изображен график зависимости количества различных символов от индикатора временной отметки для коллекции реальных комментариев в блогах, включающих в себя как спам, так и не спам.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
При ознакомлении с приведенным ниже описанием необходимо иметь в виду, что все упоминаемые соединения между конструкциями могут представлять собой прямые рабочие соединения или опосредованные рабочие соединения, осуществляемые через промежуточные конструкции. Множество элементов включает в себя один или более элементов. Любое упоминание элемента следует понимать как относящееся по меньшей мере к одному элементу. Группа элементов включает в себя по меньшей мере два элемента. Если это не оговаривается отдельно, этапы любого описываемого способа не обязательно должны выполняться точно в описанном порядке. Первый элемент (например, данные), полученный из второго элемента, охватывает первый элемент, равный второму элементу, а также первый элемент, сгенерированный в результате обработки второго элемента и, возможно, другие данные. Определение или принятие решения по параметру охватывает определение или принятие решения по указанному параметру и, возможно, по другим данным. Если не указано иное, индикатором некоторой величины/данных может быть сама эта величина или сами эти данные, или же некоторый индикатор, отличный от этой величины/данных. Компьютерные программы, описанные в некоторых вариантах осуществления настоящего изобретения, могут быть автономными программными сущностями или же частями (например, подпрограммами, объектами кода) других компьютерных программ. Если не указано иное, термин «спам» не ограничивается спамом в электронной почте и охватывает также такие электронные сообщения, как, например, ненадежный или незапрашиваемый коммерческий контент, генерируемый пользователями, в том числе в виде комментариев в блогах, обсуждения на форумах, статей на вики-сайтах, откликов покупателей, сообщений на сайтах социальных сетей, мгновенных сообщений, а также телефонных SMS- и MMS-сообщений. Машиночитаемые носители охватывают постоянные носители информации, например магнитные, оптические и полупроводниковые носители (например, жесткие диски, оптические диски, устройства флэш-памяти, динамические запоминающие устройства с произвольной выборкой), а также линии связи, например электропроводные кабели и каналы волоконно-оптической связи. Согласно некоторым вариантам осуществления настоящее изобретение включает в себя, помимо прочего, компьютерные системы, содержащие аппаратные средства, запрограммированные для выполнения описанных в этом документе способов, а также машиночитаемые носители, на которых закодированы команды для выполнения способов, описанных в этом документе.
[0028] Приведенное ниже описание иллюстрирует варианты осуществления изобретения путем примера и не имеет ограничительного смысла.
[0029] На фиг. 1 изображена иллюстративная антиспам-система согласно некоторым вариантам осуществления настоящего изобретения. Система 10 включает в себя группу контент-серверов 12а-b, антиспам-сервер 16 и группу клиентских систем 14а-b. Контент-серверы 12а-b могут представлять собой веб-серверы, на которых размещают и/или которые доставляют онлайн-контент, например, среди прочих, личные и корпоративные веб-сайты, блоги, сайты социальных сетей, сайты онлайн-развлечений. Другие контент-серверы 12а-b могут представлять собой серверы электронной почты, обеспечивающие доставку электронных отправлений клиентским системам 14а-b. Клиентские системы 14а-b могут представлять собой компьютеры конечных пользователей, каждый из которых имеет процессор, память и накопитель и работает в операционной системе, например Windows, MacOS или Linux. Некоторые клиентские компьютерные системы 14а-b могут представлять собой мобильные вычислительные и/или коммуникационные устройства, например планшетные компьютеры, мобильные телефоны или карманные персональные компьютеры. В некоторых вариантах осуществления клиентские системы 14а-b могут представлять отдельных пользователей или же несколько клиентских систем могут принадлежать одному и тому же пользователю. Антиспам-сервер 16 может включать в себя одну или более компьютерных систем. Контент-серверы 12а-b, клиентские системы 14а-b и антиспам-сервер 16 соединены сетью 18. Сеть 18 может быть территориально распределенной сетью, как, например, Интернет, при этом части сети 18 могут также включать в себя локальную вычислительную сеть (LAN).
[0030] На фиг. 2 изображена иллюстративная конфигурация аппаратного обеспечения серверной компьютерной системы, например антиспам-сервера 16. В некоторых вариантах осуществления сервер 16 включает в себя процессор 20, блок 22 памяти, множество устройств 24 хранения и контроллер 26 коммуникационного интерфейса, соединенные между собой множеством шин 28.
[0031] В некоторых вариантах осуществления процессор 20 включает в себя физическое устройство (например, многоядерную интегральную схему), конфигурированное для выполнения вычислительных и/или логических операций с множеством сигналов и/или данных. В некоторых вариантах осуществления такие логические операции передают процессору 20 в форме последовательности команд процессора (например, в машинном коде или в другом виде программного обеспечения). Блок 22 памяти может включать в себя машиночитаемый носитель (например, запоминающее устройство с произвольной выборкой), в котором хранятся данные/сигналы, полученные или сгенерированные процессором 20 в ходе выполнения команд. Устройства 24 хранения включают в себя машиночитаемые носители, обеспечивающие энергонезависимое хранение, чтение и запись команд программного обеспечения и/или данных. Иллюстративные устройства 24 хранения включают в себя магнитные и оптические диски, полупроводниковые (например, флэш-память) устройства памяти, а также съемные носители, например диски CD и/или DVD и накопители. Контроллер 26 коммуникационного интерфейса обеспечивает возможность соединения системы сервера 16 с сетью 18 и/или с другими машинами/компьютерными системами. В типичном случае контроллеры 26 коммуникационного интерфейса включают в себя сетевые адаптеры. Шины 28 в совокупности представляют собой группу системных и периферийных, шин, шин микропроцессорных наборов и/или всех прочих схем, обеспечивающих взаимосвязь устройств 20-26 системы сервера 16. Например, шины 28 могут включать, среди прочих, «северный мост», соединяющий процессор 20 с памятью 22, и/или «южный мост», соединяющий процессор 20 с устройствами 24-26.
[0032] В некоторых вариантах осуществления каждая клиентская система 14а-b включает в себя приложение для чтения документов (например, веб-браузер, программу для чтения электронной почты, медиа-проигрыватель), которое может представлять собой компьютерную программу, используемую для дистанционного доступа к данным, хранящимся на контент-серверах 12а-b. Когда пользователь обращается к онлайн-документу, например к веб-странице, или получает электронное сообщение, например сообщение электронной почты, данные, связанные с документом/сообщением, передаются через части сети 18, находящиеся между соответствующим контент-сервером и клиентской системой 14. В некоторых вариантах осуществления приложение для чтения получает данные документа, преобразует их в визуальную форму и показывает их пользователю. Некоторые варианты осуществления приложения для чтения могут также дать пользователю возможность взаимодействовать с отображаемым контентом. В случае электронной почты клиентская система 14а-b может включать в.себя специализированное программное обеспечение, конфигурированное для классифицирования входящей электронную почты по отдельным категориям из группы категорий (например, спам, надежные сообщения, другие разнообразные классы и подклассы).
[0033] В некоторых вариантах осуществления контент-серверы 12а-b конфигурированы для получения контента, сгенерированного пользователем (например, статей, записей в блогах, загрузок медиафайлов, комментариев и т.д.) из группы пользователей, и для организации, форматирования и доставки такого контента третьим лицам по сети 18. Часть сгенерированных пользователем данных, полученных серверами 12а-b, может содержать электронные сообщения, которые могут включать в себя незапрашиваемые сообщения (спам). Примерами таких электронных сообщений, называемых далее «целевые сообщения» или «целевые отправления», являются, среди прочего, сообщения электронной почты, комментарии в блогах, сообщения на сайтах социальных сетей и комментарии, отправленные на веб-сайты развлечений и/или новостей.
[0034] В некоторых вариантах осуществления контент-серверы 12а-b могут включать в себя компоненты программного обеспечения, конфигурированные для обработки целевых сообщений, полученных от пользователей, с целью обнаружения спама. При обнаружении спамовые сообщения (например, мошеннические комментарии в блогах и т.п.), могут блокироваться и/или может предотвращаться их отображение на соответствующем веб-сайте. Программное обеспечение для обработки спама может выполняться на контент-серверах 12а-b в виде сценариев, выполняемых со стороны сервера. Такие сценарии могут быть интегрированы в виде подключаемых модулей в более крупные пакеты сценариев, например в виде подключаемого модуля (модулей) для таких платформ для онлайн-публикации, как Wordpress или Drupal. В некоторых вариантах осуществления в целях обнаружения спама серверы 12а-b могут быть конфигурированы для выполнения совместной транзакции по обнаружению спама с антиспам-сервером 16, как подробно описано ниже.
[0035] В некоторых вариантах осуществления антиспам-сервер 16 конфигурирован для выполнения совместной транзакции по обнаружению спама с контент-серверами 12а-b и/или клиентскими системами 14а-b. На фиг. 3-А изображен иллюстративный обмен данными между сервером 16 и клиентской системой 14 в варианте осуществления, конфигурированном для обнаружения спама в электронной почте. Клиентская система 14 может получать сообщения электронной почты от почтового сервера по сети 18. После получения сообщения электронной почты клиентская система 14 может отправить целевой индикатор 40, который включает в себя данные для идентификации спама, связанные с сообщением электронной почты, на антиспам-сервер 16 и может получить в ответ целевую метку 50, указывающую на то, является ли соответствующее сообщение электронной почты спамом. Клиентская система 14 затем может поместить сообщение в подходящую категорию сообщений (например, спам или надежное сообщение электронной почты).
[0036] На фиг. 3-В изображен иллюстративный обмен данными между антиспам-сервером 16 и контент-сервером 12 в варианте осуществления, конфигурированном для обнаружения спама, сгенерированного пользователем и полученного сервером 12, например, среди прочих, спама в блоге или спама, опубликованного на сайте социальной сети. После получения целевого сообщения, например, в результате отправки пользователем комментария на веб-сайт, размещенный на сервере 12, сервер 12 может отправить целевой индикатор 40, который включает в себя данные для идентификации спама, извлеченные из целевого сообщения, на антиспам-сервер 16 и получить в ответ целевую метку 50, указывающую на то, является ли целевое сообщение спамом.
[0037] На фиг. 4 изображен иллюстративный целевой индикатор целевого сообщения согласно некоторым вариантам осуществления настоящего изобретения. Целевой индикатор 40 включает в себя идентификатор 41 объекта (например, ярлык, хеш-код), уникально идентифицирующий целевое сообщение, и целевую строку.42, которая включает в себя текстовую часть целевого сообщения, например текстовую часть комментария в блоге. В некоторых вариантах осуществления целевая строка 42 включает по существу весь текст целевого сообщения. Если целевое сообщение включает в себя несколько текстовых частей, то целевая строка 42 может включать в себя конкатенацию текстовых частей; в альтернативном варианте для каждой текстовой части может быть получена отдельная целевая строка 42. В некоторых вариантах осуществления. целевая строка 42 включает в себя отрезок текстовой части целевого сообщения, отрезок, имеющий предварительно заданную длину строки (например, 128 последовательных символов).
[0038] Некоторые варианты осуществления целевого индикатора 40 помимо целевой строки 42 могут включать в себя другие данные для идентификации спама, соответствующие целевому сообщению. В примере на фиг. 4 целевой индикатор 40 включает в себя индикатор 44 имени пользователя, указывающий на имя (например, личное имя, псевдоним, никнейм, логин, имя аватара, маркер имени и т.п.), предоставленное отправителем целевого сообщения, индикатор 46 адреса, указывающий место отправки (например, исходный IP адрес) целевого сообщения, и временную отметку 48, указывающую на момент в реальном времени (например, дату и время), когда целевое сообщение была отправлено.
[0039] В некоторых вариантах осуществления целевая метка 50 может включать в себя уникальный код объекта, например уникальный код 41, и индикатор статуса наличия спама в целевом сообщении. Целевая метка 50 эффективно указывает на то, является ли целевое сообщение спамом, в соответствии с оценкой, выполненной антиспам-сервером 16, как подробно описано ниже.
[0040] На фиг. 5 изображена схема иллюстративного множества приложений, выполняемых на антиспам-сервере 16, согласно некоторым вариантам осуществления настоящего изобретения. Приложения включают в себя детектор 32 спама и программу 34 связи, связанную с детектором 32 спама. Приложения 32 и 34 могут представлять собой автономные компьютерные программы или же быть частями более крупных пакетов программного обеспечения, реализующих, например, такие услуги в области компьютерной безопасности, как обнаружения вредоносных программ. В некоторых вариантах осуществления на антиспам-сервере 16 размещают также базу 30 данных (БД) антиспама. В альтернативном варианте база данных антиспама может находиться на компьютерной системе, отличной от сервера 16, но связанной с сервером 16 через сеть 18, или же на машиночитаемом носителе, связанном с сервером 16.
[0041] База 30 данных антиспама включает в себя хранилище информации, относящейся к сетевому спаму. В некоторых вариантах осуществления база 30 данных включает в себя совокупность символьных гистограмм, при этом каждая гистограмма рассчитана для некоторого электронного сообщения, как описано ниже. База 30 данных может включать в себя данные по электронным сообщениям, как являющимся, так и не являющимся спамом, например по комментариям в блогах, комментариям, опубликованным на сайтах социальных сетей и т.д. Помимо данных о гистограммах, каждая запись, хранящаяся в базе 30 данных, может включать в себя дополнительную информацию, например строку 42 из соответствующего целевого сообщения, индикатор времени, например, временную отметку 48, и индикаторы длины строки, количество различных символов и показатель строки в строке 42; иллюстративные применения таких величин описаны ниже. В некоторых вариантах осуществления для каждой символьной гистограммы в базе 30 данных может храниться индикатор приписывания кластера, указывающий на кластер сообщений, которому соответствующая строка приписана в данный момент: В базе 30 данных может также храниться структура данных, включающая в себя группу идентификаторов, например идентификатор 41 объекта, при этом каждый идентификатор объекта уникальным образом связан с электронным сообщением, а также отображение, связывающее каждую символьную гистограмму с целевым сообщением, для которого она была рассчитана, что обеспечивает возможность выборочного подбора гистограммы в базе 30 данных детектором 32 спама, как показано ниже.
[0042] На фиг. 6 изображена иллюстративная символьная гистограмма, вычисленная для целевой строки 42, согласно некоторым вариантам осуществления настоящего изобретения. Целевая гистограмма 60 включает в себя множество чисел, при этом каждое число указывает на число употреблений каждого отдельного символа в целевой строке 42. Например, целевая гистограмма для «Mississippi» включает число 1 для символа «М», число 4 для символа «i», число 4 для символа «s» и число 2 для символа «р». В некоторых вариантах осуществления символы сгруппированы в несколько отдельных классов 62 символов, например, среди прочего, «нижний регистр», «верхний регистр», «цифры» и «специальные символы». В разных вариантах осуществления количество и состав различных классов символов может быть различным.
[0043] В некоторых вариантах осуществления программа 34 связи конфигурирована для управления связью с клиентскими системами 14а-b и/или контент-серверами 12а-b. Например, программа 34 может устанавливать соединения по сети 18, отправлять и получать такие данные, как целевые индикаторы и целевые метки в клиентские системы 14а-b и контент-серверы 12а-b и от них.
[0044] На фиг. 7 изображена схема иллюстративного детектора спама, работающего на сервере 16, согласно некоторым вариантам осуществления настоящего изобретения. Детектор 32 спама включает в себя программу 36 управления гистограммами и средство 38 кластеризации, соединенное с программой 36 управления гистограммами. Детектор 32 спама может получать целевой индикатор 40 целевого сообщения от программы 34 связи (см. фиг. 5 и 3-А-В) и ссылочную гистограмму 64 из базы 30 данных, при этом он, в свою очередь, выводит целевую метку 50 в программу 34 связи для отправки клиентской системе 14 или контент-серверу 12, которые инициировали соответствующую транзакцию по обнаружению спама.
[0045] В некоторых вариантах осуществления программа 36 управления гистограммами конфигурирована для получения целевого индикатора 40 от программы 34 связи, вычисления целевой гистограммы 60 по данным целевого индикатора 40, выполнения процесса предварительной фильтрации для определения множества пригодных ссылочных гистограмм 64, выборочного подбора ссылочных гистограмм 64 в базе 30 данных и передачи гистограмм 60 и 64 средству 38 кластеризации для сравнения гистограмм и приписывания кластера. Действие программы 36 управления гистограммами подробно описано ниже со ссылкой на фиг. 9.
[0046] В некоторых вариантах осуществления анализ целевого отправления выполняют в гиперпространстве признаков сообщений путем анализа расстояний между вектором признаков, соответствующим целевому сообщению, и множеством представительных векторов, каждый из которых определяет отдельную коллекцию (кластер) сообщений. На фиг. 8 изображены три иллюстративных кластера 70а-с сообщений, образованных соответственно векторами 74а-с признаков, в простом двухмерном пространстве признаков с двумя осями d1 и d2. В некоторых вариантах осуществления настоящего изобретения оси d1 и d2 соответствуют различным признакам символьной гистограммы. Например, ось d1 может соответствовать символу «М», а ось d2 - символу «s». Далее строка «Mississippi» может быть представлена в виде вектора признаков (1, 4), в котором учитывается, что «М» встречается один раз, тогда как «s» встречается четыре раза в соответствующей строке. Две строки, имеющие сходные символьные гистограммы, располагаются вблизи друг другу в этом иллюстративном гиперпространстве признаков: в приведенном выше примере «Mississippi», и «Missiomimpossible» имеют в этом пространстве. идентичные векторы. В некоторых вариантах осуществления каждый кластер 70 сообщений состоит из сообщений, которые занимают по существу небольшую область гиперпространства признаков, что означает, что все элементы кластера имеют сходные векторы признаков, т.е. сходные символьные гистограммы.
[0047] В некоторых вариантах осуществления средство 38 кластеризации конфигурировано для поддержания коллекции кластеров 70 сообщений, которая представляет собой совокупность электронных сообщений, полученных сервером 16 на протяжении истории накопления данных и сгруппированных в кластеры по принципу подобия. Некоторые кластеры 70 могут представлять собой отдельные волны спама, каждая из которых включает в себя копии или варианты одного и того же спамового сообщения, отправленного множеству клиентов и/или опубликованного на множестве веб-сайтов. В идеальном случае кластер сообщений состоит из идентичных или почти идентичных целевых строк. Средство 38 кластеризации дополнительно конфигурировано для получения целевой гистограммы 60 и приписывания целевого сообщения, представленного гистограммой 60, кластеру сообщений, на который оно больше всего похоже по принципу подобия гистограмм. Чтобы выполнять приписывание кластера, средство 38 кластеризации получает от программы 36 управления гистограммами множество ссылочных гистограмм 64, причем каждая гистограмма 64 является представителем кластера, и сравнивает гистограммы 60 и 64, чтобы определять, какой кластер сообщений лучше всего подходит для целевой гистограммы 60. Более подробно работа средства 38 кластеризации описана ниже со ссылкой на фиг. 9.
[0048] На фиг. 9 изображена иллюстративная последовательность этапов, выполняемых детектором 32 спама (фиг. 7). в рамках транзакции по обнаружению спама, согласно некоторым вариантам осуществления настоящего изобретения. На этапе 102 детектор 32 спама получает целевой индикатор 40 от клиентской системы 14 или контент-сервера 12 через программу 34 связи. Далее, на этапе 104 детектор спама извлекает целевую строку 42 в соответствии с целевым индикатором 40 и вычисляет символьную гистограмму 60 целевой строки 42. Этап 104 может также включать в себя вычисление нескольких параметров целевой строки 42, например длины строки и/или количества различных символов, которые будут использованы для предварительной фильтрации коллекции кластеров сообщения на этапе 106. В некоторых вариантах осуществления на этапе 106 детектор 32 спама выполняет операцию предварительной фильтрации, чтобы выбирать, в соответствии с множеством условий предварительной фильтрации, подмножество кластеров строк-кандидатов из полной коллекции, поддержание которой осуществляется средством 38 кластеризации. За счет отбора лишь (небольшого) подмножества кластеров для выполнения сравнения гистограмм детектор 32 спама может эффективно уменьшить вычислительные затраты.
[0049] В некоторых вариантах осуществления детектор 32 спама может выбирать подмножество кластеров-кандидатов с учетом длины строки. Длину строки в целевой строке 42 сравнивают с длиной строки в представителе каждого кластера или со средней длиной строки в элементах соответствующего кластера. Кластер может быть выбран в качестве кандидата для сравнения гистограмм в том случае, если типичная для него длина строки заключена в пределах заданного порога по отношению к длине строки в целевой строке 42.
[0050] Альтернативным критерием предварительной фильтрации является количество различных символов. Например, строка «Mississippi» имеет 4 различных символа: М, i, s и р. Для каждого кластера количество различных символов в целевой строке 42 сравнивают с количеством различных символов в элементе, представляющем соответствующий кластер, или со средним количеством различных символов в элементах кластера, при этом кластеры, имеющие количество различных символов, сходное с целевой строкой 42, выбирают в качестве кандидатов для сравнения гистограмм.
[0051] В некоторых вариантах осуществления предварительная фильтрация может проходить в соответствии с показателем строки, вычисляемым следующим образом:
i
i
где индекс i обозначает номер символа строки, p обозначает индикатор положения i-го символа во множестве всех символов (например, ASCII кодсоответствующего символа) и w обозначает вес символа для соответствующего символа. В некоторых вариантах осуществления символы разделены на несколько классов, например на классы 62, показанные на фиг. 6, среди которых - буквы в нижнем регистре, буквы в верхнем регистре, цифры и специальные символы. Веса w(i) могут быть идентичными в пределах одного класса символов, однако при этом могут различаться от одного класса к другому. Например, вес, связанный с некоторым специальным символом, может быть выше, чем вес буквы в нижнем регистре. Для каждого кластера показатель [1] строки в целевой строке 42 сравнивают с показателем строки в элементе, представляющем соответствующий кластер, или со средним показателем строки в кластере, при этом кластеры, имеющие сходные с целевой строкой 42 показатели строки, выбирают в качестве кандидатов для сравнения гистограмм.
[0052] В некоторых вариантах осуществления критерии предварительной фильтрации могут быть объединены. Например, может быть выбрано первое подмножество кластеров сообщений по принципу сходства показателей строки; затем из первого подмножества кластеров выбирают второе подмножество, причем каждый кластер имеет сходные с целевой строкой 42 длину строки и количество отдельных символов.
[0053] Выбрав множество кандидатов для сравнения гистограмм, для каждого выбранного кластера детектор 32 спама может передать программе 36 управления гистограммами команду на выборочный подбор ссылочной гистограммы 64 в базе 30 данных, которая соответствует сообщению, представляющему соответствующий кластер. Далее для каждого выбранного кластера выполняют циклическую последовательность этапов 108-116. На этапе 108 детектор спама может проверить, проходили ли уже все выбранные кластеры процедуру сравнения гистограмм. Если да, то детектор 32 спама переходит к этапу 118, описанному ниже. Если нет, то на этапе 110 оценивают следующий кластер. На этапе 112 целевую гистограмму 60 сравнивают со ссылочной гистограммой 64.
1
2
[0054] В некоторых вариантах осуществления этап 112 включает в себя вычисление множества межстрочных расстояний, указывающих на степень сходства между гистограммами 60 и 64. В некоторых вариантах осуществления межстрочное расстояние между двумя строками s и s может быть выражено следующей формулой:
1
2
i
1
2
<mrow><msubsup><mi>N</mi><mn>1</mn><mi>i</mi></msubsup></mrow>
<mrow><msubsup><mi>N</mi><mn>2</mn><mi>i</mi></msubsup></mrow>
где индекс i обозначает номер символа в подмножестве символов, общих для строк s и s, w - вес символа для i-го символа,
обозначает число употреблений i-го символа в строке s и где
обозначает число употреблений i-го символа в строке s. Альтернативно межстрочное расстояние выражается следующим образом:
1
2
i
i
где индекс i обозначает номер символа в подмножестве символов, имеющихся только в s, но не в s, w - вес i-го символа и с - заданная независимая от символа постоянная. Как описано выше, веса w могут быть приписаны символу или приписаны классу (например, специальным символам в отличие от букв в нижнем регистре). Использование весов, приписываемых символам, может иметь тот смысл, что некоторые символы используются чаще, чем другие при намеренном запутывании текста, т.е. в способе, который часто используют спамеры и который предусматривает замену определенных символов в тексте другими символами (например, «vi4gra»), чтобы избежать обнаружения спама. Если приписывать относительно маленькие веса символам, которые используются при таком запутывании, то полученные запутыванием версии целевой строки могут выглядеть весьма сходными между собой по межстрочному расстоянию, а потому все они будут правильно идентифицированы как спам. Величина с может использоваться как параметр настройки: если с слишком мало, то две достаточно различающиеся строки могут быть ошибочно признаны сходными; если с слишком велико, то небольшие различия между строками могут быть избыточно усилены.
[0055] В некоторых вариантах осуществления может вычисляться комбинированное межстрочное расстояние:
2
Кроме того, поскольку D не коммутативно, альтернативное межстрочное расстояние определяется следующим образом:
1
2
3
3
4
[0056] В некоторых вариантах осуществления этап 112 (фиг. 9) включает в себя вычисление D(T,R) и/или D(T,R), где Т обозначает целевую строку 42, а R обозначает ссылочную строку, связанную со ссылочной гистограммой 64. В альтернативном варианте детектор спама может вычислять D(Т,R), D(Р,Т), и/или D(T,R). Далее, на этапе 114 определяют, имеется ли соответствие между целевой гистограммой 60 и ссылочной гистограммой 64.
1
1
1
2
1
2
3
1
2
3
3
3
4
4
i
[0057] В некоторых вариантах осуществления при сопоставлении гистограмм требуется, чтобы межстрочное расстояние было меньше, чем заданный порог. Например, при сопоставлении гистограмм может быть необходимым, чтобы либо D<t, либо D<t или же u D u D были меньше соответствующих пороговых величин. В альтернативном варианте при сопоставлении гистограмм требуется, чтобы D=D+D<t. В еще одном варианте осуществления для успешного соответствия может требоваться, чтобы и D(Т,R), и D(Р,Т) были меньше пороговой величины, или чтобы выполнялось условие D<t. Пороговые величины t могут быть независимыми от сравниваемых строк или они могут изменяться в соответствии с длиной строки и/или с количеством различных символов в целевой строке 42. В некоторых вариантах осуществления используются более высокие пороговые величины в случае сравнительно более длинных строк или строк со сравнительно большим количеством различных символов.
[0058] Если соответствие между гистограммами 60 и 64 обнаружено, то детектор 32 спама переходит к этапу 116, на котором соответствующий кластер сообщения отмечают как пригодный для принятия целевой строки 42. Если гистограммы не соответствуют друг другу, то детектор 32 спама возвращается на этап 108. Когда все кластеры сообщения, выбранные на этапе 106, будут оценены путем сравнения гистограмм, на этапе 118 определяют, пригодны ли какие-либо кластеры для принятия целевой строки 42. Если да, то на этапе 122 детектор 32 спама может вычислить для каждого пригодного кластера индикатор подобия строки и кластера, указывающий на то, насколько целевая строка 42 подобна всем элементам соответствующего кластера. Иллюстративный индикатор подобия строки и кластера для каждого пригодного кластера включает в себя набор тех элементов кластера, у которых ссылочные гистограммы 64 соответствуют целевой гистограмме 60.
[0059] Далее на этапе 124 выполняют собственно приписывание целевой строки 42 тому кластеру сообщений, с которым она наиболее сходна. В некоторых вариантах осуществления целевую строку 42 приписывают кластеру с самым высоким индикатором подобия строки и кластера, определенным на этапе 122. Средство 38 кластеризации может обновлять данные о приписывании кластеров, чтобы отразить добавление нового элемента кластера, при этом запись с целевой строкой 42 может быть внесена в базу 30 данных. В некоторых вариантах осуществления этап 124 включает в себя также определение множества параметров-идентификаций спама, связанных с кластером, который принимает целевое сообщение. Например, в некоторых вариантах осуществления могут вычисляться промежутки времени, проходящие между последовательными временными отметками в рамках одного и того же кластера. Такие параметры могут быть сохранены в отношении каждого кластера и могут использоваться, чтобы определять автоматически (без контроля со стороны человека-оператора), включает конкретный кластер спам или надежные сообщения и можно ли полагать, что конкретный кластер, вероятно, представляет собой волну спама.
[0060] Если ни один из кластеров не был признан пригодным для принятия целевого сообщения (этап 118), что указывает на то, что целевая строка 42, вероятно, отличается от любой из уже хранящихся в базе данных, то на этапе 120 средство 38 кластеризации может создать новый кластер, единственным элементом которого будет целевое сообщение, и может сохранить запись с целевым сообщением в базе 30 данных.
[0061] На этапе 126 детектор 32 спама может определять целевую метку 50, идентифицирующую целевое сообщение, как спам или как надежное. В некоторых вариантах осуществления решение, является ли целевое сообщение спамом, принимается в соответствии с приписыванием целевой строки 42 кластеру. Если строка 42 приписывается кластеру, состоящему преимущественно из спамовых сообщений, то целевое отправление также может получить метку «спам».
[0062] В некоторых вариантах осуществления метку 50 определяют в соответствии с определенными признаками для идентификации спама элементов кластера, которому было приписано целевое отправление. Одним таким, признаком для идентификации спама являются временные отметки 48. Приписывание многочисленных новых элементов за короткий промежуток времени может служить признаком того, что соответствующий кластер содержит волну спамовых сообщений. В некоторых, вариантах осуществления детектор 32 спама может определять промежуток времени, проходящий между группой временных отметок, связанных с элементами кластера, например самый короткий промежуток времени, в пределах которого данному кластеру было приписано 6 элементов, при этом когда этот промежуток времени уменьшается ниже заданного порога, соответствующий кластер помечают как спам. В некоторых вариантах осуществления сосчитанное число элементов кластера может использоваться в качестве признака для идентификации спама: при получении кластером избыточного числа элементов, превышающего заданное число элементов, соответствующий кластер может быть помечен как спам.
[0063] Иллюстративные системы и способы, описанные выше, обеспечивают возможность обнаружения антиспам-системой незапрашиваемых сообщений в виде сгенерированного пользователем контента в Интернете в форме комментариев в блогах, комментариев, опубликованных на сайтах социальных сетей и т.д., а также контента в виде сообщений электронной почты, мгновенных сообщений и телефонных SMS- и MMS-сообщений.
[0064] В некоторых вариантах осуществления компьютерная система извлекает целевую строку символов из электронного сообщения, например комментария в блоге, передает ее на антиспам-сервер и получает от антиспам-сервера индикатор того, является или нет соответствующее электронное сообщение спамом. Если электронное сообщение является спамом, то компьютерная система может блокировать, отправлять в карантин, удалять или любым иным способом ограничивать отображение электронного сообщения и/или может выводить предупреждение пользователю.
[0065] Антиспам-сервер определяет, является или нет электронное сообщение спамом по частоте употреблений определенных символов в целевой строке. Символьную гистограмму целевой строки вычисляют и сравниваются с гистограммами, вычисленными для совокупности электронных сообщений, которая может включать в себя отправления, как являющиеся, так и не являющиеся спамом. В способах и системах, описанных в настоящем изобретении, используется то наблюдение, что две сходных строки всегда имеют сходные символьные гистограммы. Поэтому нахождение соответствия между гистограммой целевой строки и другой гистограммой, вычисленной для ссылочной строки, может быть признаком того, что целевая строка сходна со ссылочной строкой. В этом случае антиспам-сервер может определять, является ли электронное сообщение спамом, в зависимости от того, указывает ли ссылочная строка на спам, например, принадлежит ли ссылочная строка кластеру электронных сообщений, помеченных как спам.
[0066] Однако существует множество ситуаций, в которых очень сходные гистограммы принадлежат двум различным строкам. Чтобы избежать ложной положительной идентификации, при принятии решения, являются ли две строки сходными, могут рассматриваться другие признаки целевой строки, например временная отметка.
[0067] Сравнение гистограмм не может считаться надежным способом идентификации сходства строк, когда длина строки превышает определенный порог. В предельном случае очень длинных строк все строки имеют весьма сходные гистограммы, которые просто указывают на естественную частоту употребления каждого символа в соответствующем языке. Поэтому системы и способы, описанные здесь, в наибольшей степени подходят для анализа коротких строк, появляющихся в таких электронных сообщениях, как сообщения в блогах и комментарии на сайтах социальных сетей, например Facebook и Twitter.
[0068] Дополнительной проблемой для обнаружения спама путем сравнения строк является намеренное запутывание, когда спамеры могут заменять определенные символы в сообщении другими символами (например, Vi4gra), чтобы избежать обнаружения. Проблему намеренного запутывания строк можно решить путем использования веса, который приписывается отдельно каждому символу, и путем определения межстрочного расстояния с учетом числа и веса каждого из символов, как в формулах [2-3]. Веса, приписываемые символам, обеспечивают возможность настраивания чувствительности сравнения строк. В некоторых вариантах осуществления символы могут группироваться по категориям (например, буквы, цифры, специальные символы), при этом все символы, в категории получают одинаковый вес, характеризующий данную категорию. С помощью такого группирования можно решить проблему намеренного запутывания текста, поскольку, например, запутывание с использованием случайных букв более распространено, чем запутывание текста другими типами символов. Когда определенные символы используются для запутывания в большей степени, чем другие символы, приписывание им сравнительно небольшого веса эффективно уменьшает межстрочное расстояние между двумя версиями одной и той же строки, полученными запутыванием, что приводит обе эти строки к более сходному виду.
[0069] В некоторых вариантах осуществления настоящего изобретения совокупность организовывают в группу кластеров, при этом каждый кластер записей содержит сходные строки. Вместо выполнения сравнений гистограмм по всем записям совокупности, кластеризация обеспечивает возможность сравнивать целевую строку только с одной целевой строкой, представляющей кластер, что значительно уменьшает вычислительные затраты.
[0070] Кластеризация может также облегчить автоматическое (неконтролируемое) обнаружение спама. В отличие от обычных способов кластеризации, в которых классификация сообщений в целом осуществляется при помощи контролируемого обучения классификатора, например, на обучающей совокупности, предварительно рассортированной на группу заданных классов сообщений, в некоторых вариантах осуществления настоящего изобретения выполняется динамическая кластеризация, когда статус наличия спама (т.е. спам или не спам) в кластерах или в сообщениях заранее неизвестен. Кластер может быть автоматически идентифицирован как представляющий собой спам, если в нем накапливается определенное число элементов за короткий промежуток времени.
[00,71] В компьютерном эксперименте совокупность из 22000 комментариев в блогах была классифицирована по кластерам согласно некоторым вариантам осуществления настоящего изобретения. Расчеты выполнялись на компьютерной системе, оборудованной процессором Pentium 4 (3 ГГц) и 1,5 Гб оперативной памяти, в среде Ubuntu OS 10.04. Для классификации потребовалось время вычисления, составляющее приблизительно 5 минут 00 секунд, при этом было получено 1741 кластеров сообщений, имеющих более одного элемента кластера (в среднем 4,13 сообщений на кластер). Для сравнения, обычная система кластеризации, в которой используется алгоритм сопоставления, основанный на хешировании и выполняемый на той же аппаратной платформе, создала 1617 кластеров, имеющих более одного элемента, за 7 минут 07 секунд времени вычислений при среднем количестве 4,26 комментария в кластере.
[0072] На фиг. 10-A-D показаны результаты компьютерного эксперимента, выполненного с коллекцией тестовых строк, у которых длина строки варьировалась приблизительно от 25 до 5500 символов. Использовалась та же аппаратная конфигурация, что и выше. На фиг. 10-А показано время, затраченное для генерации символьных гистограмм, в виде функции количества различных символов в тестовых строках. На фиг. 10-В показано время, затраченное для генерации символьных гистограмм, в виде функции длины строки в тестовых строках. Время вычислений для каждой гистограммы, варьировалось от нескольких микросекунд до приблизительно одной миллисекунды, при этом наблюдалась приблизительно линейная корреляция между длиной строки и временем.
[0073] На фиг. 10-С показано время, затраченное для вычисления множества межстрочных расстояний, в виде функции количества различных символов в тестовых строках, а на фиг. 10-D показан график зависимости с теми же данными, представленными в виде функции длины строки в тестовых строках. Вычисление межстрочных расстояний выполнялось на основании определения числа символов согласно формулам [2-3] и составило от нескольких микросекунд до приблизительно 500 микросекунд.
[0074] На фиг. 11 изображен график зависимости длины строки от индикатора временной отметки для коллекции из 8676 реальных комментариев в блогах, включающих в себя как спам, так и не спам. На фиг. 12 изображен график зависимости количества различных символов от индикатора временной отметки для другой коллекции из 5351 реальных комментариев в блогах, включающих в себя как спам, так и не спам. Как фиг. 11, так и фиг. 12 указывают на кластеризацию спамовых сообщений в соответствии с временными отметками и длиной строки, обеспечивающую автоматическую идентификацию спама, как описано выше.
[0075] Специалисту в данной области техники понятно, что описанные выше варианты осуществления могут быть изменены различными способами без выхода за рамки объема правовой охраны настоящего изобретения. Соответственно, объем правовой охраны изобретения определяется пунктами приведенной ниже формулы изобретения и их юридическими эквивалентами.