Работаем с 2009 года Более 450 успешных проектов Санкт-Петербург
8 (999) 849-91-09

Методика обнаружения хиджакинга с использованием ссылочных алгоритмов

Ян-чу Чен, Масаши Тоёда, Масару Кицурэгава Институт технических наук, Токийский Университет. Кампус Комаба 4-6-1, Мэгуро-ку, Токио, 153-8505, Япония

Аннотация

В настоящей работе мы предлагаем методику идентификации сайтов, чья гиперссылочная структура подверглась хиджакингу. Такие сайты сами по себе являются надежными, однако их содержимое ссылается на неблагонадежных соседей. Для того чтобы их обнаружить мы оцениваем показатель надежности интернет-ресурса, а также изучаем то, как на нем была реализована технология хиджакинга с целью цитирования некачественного ссылочного окружения. Показатель надежности оценивается исходя из разницы между положительной и негативной (спам) оценками, рассчитанных двумя модифицированными версиями классического алгоритма Google PageRank. Мы определяем два показателя, оценивающих вероятность того, что какой-либо сайт подвергся хиджакингу на основании распределения надежности цитируемого им ссылочного окружения. Производительность данных показателей хиджакинга сравнивается на крупномасштабном интернет-архиве, описанном на японском языке. Результаты демонстрируют, что наилучшая производительность достигается с использованием показателя, рассматривающего как надежных, так и неблагонадежных соседей, не ограничивающегося исследованием только неблагонадежного ссылочного окружения, как это происходит в ином случае.

1. Введение

В 2008 году поисковая система Google проиндексировала 1 триллион URL-адресов [1]. Найти необходимую для себя информацию из столь огромного веб-пространства без помощи систем информационного поиска представляется практически невозможным. Поскольку примерно половина пользователей поисковых машин просматривают только первую пятерку возвращенных результатов в предложенном им перечне сайтов [2], сами интернет-ресурсы стремятся получить как можно более высокие позиции для привлечения пользователей и получения дохода. Учитывая данную ситуацию, нет ничего удивительного в появлении такого явления как поисковый спам, который пытается увеличить видимость сайтов посредством применения различных нечестных приемов. Обычно поисковые спамеры используют две основные техники, одна из которых относится к содержимому ресурса (текстовой спам), а вторая — к гиперссылочной структуре (ссылочный спам). Текстовой спам манипулирует, как явствует из названия, текстовым содержимым страниц посредством повторения определенных ключевых фраз, не связанных с основным контентом документа, а также посредством заполнения мета-секций или текстовых анкоров гиперссылок нерелевантными ключевыми словами. Ссылочный спам манипулирует гиперссылочной структурой веба, вводя в заблуждение такие ссылочные алгоритмы ранжирования информации, как Google PageRank [5]. Поскольку подобные алгоритмы рассматривают исходящую ссылку в качестве одобрения целевой страницы, спамеры создают так называемые спам-фермы [6], то есть некоторое множество плотносвязанных между собой веб-сайтов, основное предназначение которых заключается в централизации показателей гиперссылочной авторитетности на раскручиваемом спам-ресурсе. Кроме того, спамерам также необходимо, чтобы их спам-фермы цитировались сторонними авторитетными интернет-сайтами, поскольку изолированные линкофармы вряд ли привлекут внимание систем информационного поиска таким образом, чтобы им были присвоены ранжирующие оценки. Отсюда, цитирование нормальным сайтом некачественного ресурса, ссылка на который создается без согласия вебмастера нормального веб-сайта, называется ссылочным хиджакингом (от англ. hijack — захват, ограбление, рейд). Спамеры могут реализовать хиджакинг посредством размещения комментариев в блогах, досках объявлений и форумах в которых возможно прямое цитирование их спам-сайтов; посредством скупки освободившихся доменных имен, а также задействованием в общей схеме спонсирующих веб-сайтов. В случае использования ссылочного хиджакинга для цитирования крупных линкофармов, он оказывает существенное воздействие на алгоритмы гиперссылочного ранжирования. В настоящей работе мы предлагаем новый метод для идентификации сайтов, подвергшихся хиджакингу. Подавляющее большинство предыдущих исследований фокусировалось на детекции и пессимизации поискового спама и, насколько нам известно, среди них не было ни одной работы, посвященной вычислению ссылочного хиджакинга, что может оказаться крайне важным в следующих ситуациях:

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

Для того чтобы идентифицировать хиджакинг, мы должны рассмотреть характеристики надежности (trustworthiness) сайта, подвергшегося хиджакингу, а также цитируемого им гиперссылочного окружения. Предположим, что существует путь между нормальными и некачественными ресурсами. По мере продвижения по заданному пути, в соответствии с нашими ожиданиями, на каждом шаге показатель надежности сайта будет уменьшаться до тех пор, пока на некотором конкретном узле он не окажется ниже предельно допустимого порогового значения. Такое может наблюдаться в том случае, если нормальный сайт ссылается на некачественный интернет-ресурс. Кроме того, это свидетельствует о том, что вероятней всего на нормальном сайте был реализован хиджакинг с целью цитирования неблагонадежного ссылочного окружения. Мы оцениваем надежность сайта, используя две модифицированные версии классического алгоритма Google PageRank, рассчитывающих положительные и негативные (спам) оценки заданного интернет-ресурса. Положительная оценка (white score) распространяется исключительно из исходной выборки нормальных сайтов, а негативная оценка (spam score), соответственно, только из исходной выборки некачественных сайтов. Мы рассматриваем тот или иной ресурс в качестве надежного в том случае, если ему присваивается высокая положительная оценка и, наоборот, низкая негативная оценка. Иными словами, надежность представляет собой разницу между положительными и негативными оценками заданного интернет-ресурса. Мы определяем два показателя, оценивающих вероятность того, что какой-либо трастовый сайт подвергся хиджакингу на основании распределения надежности цитируемого им ссылочного окружения. Производительность указанных показателей наличия хиджакинга (hijacked scores) сравнивается с использованием крупномасштабного интернет-архива, описанного на японском языке. Полученные результаты демонстрируют, что наилучшая производительность достигается с использованием показателя, рассматривающего как надежных, так и неблагонадежных соседей нашего с вами сайта, а не ограничивающегося исследованием только неблагонадежного ссылочного окружения, как это происходит в ином случае. Далее мы классифицируем сайты, подвергшиеся хиджакингу, по нескольким типам его реализации, а также отслеживаем исходящие с них гиперссылки для того, чтобы проверить, сможем ли мы, следуя по ним, найти новые некачественные ресурсы. Мы также сравниваем две различные пары положительных и негативных оценок.

Оставшаяся часть настоящей работы организованна следующим образом. В Разделе 2 мы делаем обзор фундаментальной теории Google PageRank и гиперссылочного спама. В Разделе 3 вводится модифицированные версии алгоритма PageRank, а также несколько подходов, позволяющих вычислять или пессимизировать ссылочный спам. В Разделе 4 представляется наша методология по вычислению сайтов, подвергшихся хиджакингу. Раздел 5 сообщает результаты наших экспериментов. Наконец, заключение и соответствующие выводы представлены в Разделе 6.

2. Фундаментальная теория

2.1 Веб-граф

Весь веб можно представить в виде ориентированного графа. Мы можем обозначит веб как G = (V,E), где V является набором узлов, а E — набором ориентированных ребер <p,q>. Узел v может считаться страницей, хостом или сайтом. Каждый узел имеет некоторое число входящих (inlinks) и исходящих (outlinks) гиперссылок. In(p) представляет собой набор узлов, ссылающихся на p (цитирующее p ссылочное окружение), а Out(p) — набор узлов, на которые ссылается p (цитируемое p ссылочное окружение). Мы будем использовать n для описания ||V||, общего числа узлов на веб-графе.

2.2 Алгоритм PageRank

Алгоритм Google PageRank [5] является одним из наиболее известных алгоритмов ссылочного ранжирования. Основная идея, положенная в этот замечательный алгоритм, заключается в том, что интернет-страничка рассматривается авторитетной в том случае, если на нее ссылает множество других авторитетных страниц. Данное рекурсивное определение может быть представлено в матричном выражении следующего вида:

, где p является скор-вектором PageRank, T — матрицей переходных вероятностей. T(p,q) составляет 1/||Out(q)|| в том случае, если существует ссылка из узла q, ведущая на узел p; в противном случае 0. Коэффициент затухания α< 1 (обычно 0.85) необходим нам для гарантированной сходимости, а также ограничения эффекта утечки ранга (rank sink). d является равномерным распределением случайного вектора. Вместо того, чтобы следовать по исходящим со страницы гиперссылкам, мы можем прибегнуть к операции телепортации с заданного документа на любую другую страницу в соответствии с распределением d.

2.3 Гиперссылочный спам

После оглушительного успеха Google, использовавшего PageRank в качестве своего основного алгоритма ранжирования, данный алгоритм стал основной мишенью гиперссылочных спамеров, занимавшихся продвижением сайтов в органическом поиске новой поисковой машины. Z. Gyongyi и др. [6] провели исследование ссылочного спама и предложили оптимальную гиперссылочную структуру, максимизирующую голосующую способность линкофарма. Ссылочная ферма состоит из целевого документа и стимулирующих страниц (boosting pages). Все стимулирующие страницы голосуют за целевой документ в целях увеличения авторитетности последнего. Затем, целевая страница распространяет увеличившуюся оценку PageRank обратно своим саппортерам. К этому времени члены ссылочной фермы также могут увеличить собственные оценки PageRank. В качестве дополнительного элемента к выстраиваемой внутренней гиперссылочной структуре, спамеры также создают внешние входящие ссылки с ресурсов, расположенных за пределами их линкофармов не только для лучшей индексации узлов со стороны поисковых машин, но и для передачи большей голосующей способности целевому документу. Для того чтобы НЕ-спам страницы осуществляли цитирование спам-документов, применяются различные техники хиджакинга. Спамеры могут заниматься рассылкой обратных ссылок на свои некачественные ресурсы или оставлять комментарии в постах, которые также будут содержать в себе исходящие гиперссылки на некачественные документы. Освободившиеся домены также могут быть приобретены спамерами с целью последующего использования в своих манипулятивных целях. Кроме всего перечисленного, спамеры могут использовать спонсорские схемы, при которых на сайте спонсируемого сайта размещается реклама некачественных ресурсов. Обратите внимание, что крупные блог-платформы поддерживают, а системы информационного поиска рекомендуют использовать такие контрмеры, как «nofollow», который является значением атрибута rel тега «a» (rel=»nofollow»), в случае применения которого гиперссылка игнорируется алгоритмами ссылочного ранжирования [15]. Однако на сегодняшний день все еще существует целый ряд достаточно популярных интернет-сервисов, которые не поддерживают подобного рода инструменты, а такие технологии хиджакинга как скупка освободившихся доменных имен вообще не может быть пресечена посредством данного тега «nofollow».

3. Предыдущие работы

3.1 Алгоритмы TrustRank и Anti-TrustRank

Для улучшения алгоритма PageRank, в работе [8] Gyongyi и др. представили алгоритм доверия TrustRank. Основная интуиция, положенная в алгоритм TrustRank состоит в том, что хорошие документы редко цитируют спам-страницы. В методологии TrustRank в качестве исходного набора создается перечень высоконадежных интернет-страниц, каждой из которых присваивается ненулевая начальная доверительная оценка, в то время как всем прочим документам назначается нулевое значение. В результате, хорошие страницы получают более высокие доверительные оценки, а спам-страницы — более низкие. Матричное выражение TrustRank следующее:

,где t является скор-вектором TrustRank; α — коэффициентом затухания (0.85), а dτ — вектором распределения случайного перехода, где

Для обнаружения спам-страниц Krishnan и др. предложили алгоритм недоверия Anti-TrustRank [11]. Anti-TrustRank начинает распространять свои оценки из исходного набора не хороших, а некачественных страниц. Каждой спам странице из исходного набора назначается показатель Anti-TrustRank, который распространяется прочим документом по входящим гиперлинкам.

3.2 Core-based PageRank

Core-based PageRank был предложен Gyongyi и др. в работе [10]. Скор-вектором Core-based PageRank p’ является:

,где вектором распределения случайного перехода dv является:

Core-based PageRank отличается от алгоритма TrustRank вектором случайной телепортации. Core-based PageRank использует распределение случайного перехода 1/n, который нормализован по количеству всех веб-сайтов, вместо 1/||S||. В текущей работе мы используем два типа оценок core-based PageRank:

Z. Gyongyi и др. упоминали core-based PageRank со спамовым исходным набором в работе [10]. Для того чтобы определить некачественные станицы, авторы указывали на усреднение PR+ и PR (например, посредством вычисления средней взвешенной). Однако эта точка зрения отличается от нашей. Мы полагаем, что PR+ и PR должны рассматриваться по отдельности, и для обнаружения практик хиджакинга необходимо изучать изменения в этих оценках через ссылки, которые появляются после прохождения по спам-гиперссылкам.

3.3 Другие подходы

С целью детекции и пессимизации некачественных интернет-ресурсов было также предложено ряд подходов, о которых мы вкратце расскажем в этом подразделе. Для того, чтобы пессимизировать спам-страницы и повысить сопротивляемость алгоритма PageRank, в работе [9] Wu и др. исследовали возможность дополнения классической модели TrustRank таким подходом, который предусматривал более представительный тематический набор сайтов в исходной выборке веб-страниц. Они рассчитали оценку TrustRank для каждой темы с целью решения проблемы смещения TrustRank в сторону наиболее крупных интернет-сообществ. Для вычисления ссылочного спама Benczur и др. ввели SpamRank [12]. Алгоритм SpamRank инспектирует распределение оценок PageRank по всем входящим гиперссылкам, ведущих на целевую страницу. В том случае, если распределение оказывает ненормальным, SpamRank расценивает целевой документ как спам и, соответственно, оштрафовывает его. Gyongyi и др. [10] предложили учитывать ссылочную массу некачественных страниц (spam mass), то есть меру того, сколько голосов получает страница по тем гиперссылкам, которые ведут со спам-документов. Saito и др. для вычисления веб-спама использовали графовый алгоритм [13]. Они извлекли спам-хосты посредством разложения компоненты сильной связанности и использовали их в качестве исходного набора для последующего разделения спам- и НЕ-спам хостов. Du. и др. [7] обсуждали воздействие хиджакинга на ссылочные фермы. Они ввели расширенную версию оптимального линкофарма Z. Gyongyi. В своем исследовании они указали на то, что предположение, сделанное в работе [6], касающееся утечки ранга, наблюдаемой в случае хиджакинга является постоянной и может быть опущено. Несмотря на то, что Du и др. рассматривали технологию хиджакинга, они не исследовали его особенности, а также сам момент вычисления, что существенно отличается от вклада нашей работы. Как мы уже упоминали, не смотря на существование ряд различных подходов к вычислению ссылочного спама, практика хиджакинга до сих пор еще нигде не была подробно изучена. В текущей работе, мы предлагаем новый подход обнаружения сайтов, подвергшихся хиджакингу, а также гиперссылок созданных с применением данной манипулятивной техники. Посредством использования нашего метода, мы ожидаем внести вклад в новые технологии обнаружения спама и улучшить производительность существующих ссылочных алгоритмов ранжирования.

4. Обнаружение ссылочного хиджакинга

На основании изменений в надежности сайта, подвергшегося хиджакингу, а также цитируемого им гиперссылочного окружения, мы определяем показатель наличия хиджакинга. Для оценки надежности сайта мы используем положительные и негативные (спам) оценки интернет-ресурса. В качестве положительной оценки мы можем использовать TrustRank и core-based PageRank, рассчитанного по положительному исходному набору. В качестве негативной (спам) оценки мы можем использовать Anti-TrustRank и core-based PageRank, рассчитанного по негативному (спамовому) исходному набору. На основании положительных и негативных оценок, мы определяем надежность сайта как относительный траст RT, которой определяется как:

, где RT(p), White(p) и Spam(p) представляют собой относительный траст p, положительную оценку p и негативную (спам) оценку p соответственно. В том случае, если RT(p) оказывается выше нулевого значения, p с большей вероятностью является нормальным. В противном случае, если RT(p) оказывается выше нулевого значения, p с большей вероятностью является спамом. Использование логарифмических значений в положительной и негативной оценках объясняется тем, что оценки PageRank подчинены степенному закону распределения. Предельно-допустимое пороговое значение δ вводится для уменьшения возможного эффекта, могущего возникнуть вследствие различия в размерах исходных выборок, применяющихся для расчета положительной и негативной (спам) оценки. Модифицированные версии алгоритма PageRank назначают начальное значение только эталонным сайтам таким образом, что общее количество оценок, которые будут задействованы в пропагации, отличается в зависимости от количества сайтов-образцов в каждой выборке. В том случае, если количество эталонных нормальных сайтов окажется меньшим по сравнению с эталонными спам-ресурсами, тогда мы получим такой результат, при котором нормальный сайт s может получить более низкую оценку White(s), нежели чем Spam(s). Для того чтобы решить эту проблему, мы отлаживаем значение δ. Если мы используем положительное значение δ, мы рассматриваем оценку White(s) нормального сайта s как более высокую, чем его Spam(s). С другой стороны, когда мы используем негативное значение δ, нормальный сайт может иметь более низкую оценку White(s), чем его Spam(s). На практике, для достижения лучшей производительности, значение δ устанавливается около нуля. Используя RT можно разделить гиперссылочное окружение процитированное подверженным хиджакингу сайтом p на набор из нормальных сайтов nOut(p) и на набор спам-сайтов sOut(p).

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

Для каждого такого сайта-кандидата h мы рассчитываем показатель наличия на нем хиджакинга. Было разработано два различных показателя того, что сайт подвергся хиджакингу. В первом случае мы фокусируемся на том цитируемом гиперссылочном окружении веб-сайта, подвергшегося хиджакингу, которое по всей вероятности является спамом. Это основывается на том предположении, что в случае хиджакинга, интернет-ресурс может ссылаться на достаточно большое количество спам-сайтов по причине того, что его одолевают всевозможные спамеры. Следовательно, показатель наличия хиджакинга растет как и средний |RT| интернет-сайтов в массе sOut(h). Показатель наличия хиджакинга для первого случая Hs может быть описан следующим образом:

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

Во втором случае мы рассматриваем не только то ссылочное окружение сайта, подвергшегося хиджакингу, на которое он ссылается и которое по всей вероятности является спамом, но и тех соседей по Сети, что, скорее всего, являются нормальными веб-сайтами. Можно предположить, что данный сайт ссылается на нормальные интернет-ресурсы равно как и на некачественные по той простой причине, что изначально он также был нормальным. На этом основании, в расчете показателя наличия хиджакинга используется средний RT как с определенной долей вероятности нормальных, так и некачественных соседей по Сети. Для отладки воздействия нормальных и спам ресурсов, которые цитируются заданным сайтом, мы вводим весовой параметр γ. Показатель наличия хиджакинга для второго случая Hns(h) описывается следующим образом:

Нns(р) возрастает как усредненные значения |RT| процитированных нормальных сайтов и спам-ресурсов. Когда усредненные значения |RT| либо нормальных, либо некачественных ресурсов становятся низкими, показатель Hns(h) уменьшается поскольку сайт h может быть как спамом, так нормальным сайтом. В том случае, если мы используем большее значение γ, мы усиливаем |RT| тех соседей по Сети, что вероятней всего являются нормальными по сравнению с теми ссылками, что, скорее всего, ведут на некачественные сайты. Если же мы используем 0 значение для γ, Hns(h) превратится в наш первый показатель Hs(h).

5. Эксперименты

Для того чтобы оценить нашу методологию мы выполнили эксперименты с использование мгновенных снимков ссылочного состояния крупномасштабного интернет-архива, описанного на японском языке, который был отсканирован в 2004 году. Для положительных и негативных (спам) оценок были использованы оценки core-based PageRank RR+ и PR соответственно. После того, как на основании положительных и негативных (спам) оценок было получено значение RT для каждого интернет-сайта, мы рассчитали два типа показателей наличия хиджакинга, а также сравнили точность их работы в задачах обнаружения спама. Кроме того, мы исследовали вопрос, касающийся возможности обнаружения вновь возникающих некачественных сайтов с помощью наблюдения за теми интернет-ресурсами, что подверглись хиджакингу.

5.1 Набор данных и исходная выборка

Итак, для того, чтобы оценить наш алгоритм мы выполнили серию экспериментов с использованием мгновенного снимка (snapshot) гиперссылочного состояния крупномасштабного интернет-архива, описанного на японском языке. Мы осуществляли обход японского веба начиная с 1999 года и на 2010 год наш архив содержит более 10 млрд. страниц. Для нашего эксперимента мы взяли документы, отсканированные в мае 2004 года. Наш агент накопления данных использует метод обхода веб-графа, основанный на поиске в ширину [14], за тем исключением, что он фокусируется на страницах, описанных на японском языке. Страницы, не относящиеся к доменной зоне .JP, собираются только в том случае, если написаны на японском языке. В задачах фильтрации документов, не относящихся к японскому вебу, мы рассматриваем весь сайт как отдельный элемент. Процесс сканирования прекращается в том случае, если при индексации первых нескольких страниц, относящегося к какому-либо веб-сайту, не было обнаружено ни одного документа, описанного на японском языке. Следовательно, наш набор данных содержит в себе довольно приличное количество страниц, описанных на английском или других языках. Процент документов, описанных на японском, оценивается в 60%. Текущий мгновенный снимок гиперссылочного состояния включает в себя 96 млн. интернет-страниц и 4.5 млрд. ссылок. Мы используем невзвешенный веб-граф на уровне сайтов, в котором узлы представляют собой интернет-сайты, а ребра — существующие гиперссылки между страницами на различных сайтах. Для конструирования графа сайтов, с каждого интернет-ресурса мы выбрали репрезентативную страницу, которая имела 3 или более входящих гиперссылок с других сайтов и чей URL-адрес имел трехуровневую вложенность (например, http: //A/B/C/). Те интернет-страницы, которые имели меньшую вложенность сокращались до одного сайта. Ребра между двумя веб-сайтами создаются в том случае, если между их страницами существуют гиперссылки, которые связывают эти два ресурса. Граф сайтов был сконструирован по данным нашего мгновенного снимка ссылочного состояния, включившего в себя 5.8 млн. интернет-сайтов и 283 млн. гиперссылок. В своих экспериментах мы называем этот набором данных веб-графом. Для расчета положительных и негативных (спам) оценок мы создали положительный и отрицательный исходный набор. Эталонные сайты отбирались мануальными и автоматическими способами. Для создания положительного исходного набора мы учли методологию, описанную в работах [8] и [10]. Мы рассчитали оценки PageRank по всем веб-сайтам и выполнили ручной отбор первой 1000 сайтов с наиболее высокой голосующей способностью. Хорошо известные сайты (например, Google, Yahoo! и Bing), сайты авторитетных университетов, а также хорошо обслуживаемые корпоративные сайты (Ресурсы таких авторитетных компаний, как adobe.com и microsoft.com безусловно включались в наш положительный исходный набор. Прочие сайты проходили ручную проверку по серии снапшотов, начиная с 2004 года по настоящее время. В том случае, если ресурс не был замечен в манипуляциях содержимым и обслуживался прежним владельцем, мы также добавляли его в наш положительный исходный набор) были выбраны в качестве положительного исходного набора. После осуществленной ручной проверки, 389 сайтов были помечены как надежные. В дополнение к ним, были также учтены интернет-сайты, имеющие такие специфические URL-адреса, как .GOV (правительственные сайты США) и .GO.JP (правительственные сайты Японии). В итоге, мы имели 40396 надежных ресурса. Для негативного (спамового) исходного набора мы также выбрали сайты с высоким показателем PageRank и проверили их вручную. Веб-сайты, содержащие множество несвязанных ключевых фраз, а также гиперссылок, переадресующих на некачественные интернет-ресурсы; содержащих невидимый текст и отправляющих пользователя с каждого пункта меню на различные домены, рассматривались нами как спам. После выполненной мануальной инспекции мы имели 1182 некачественных сайта. Кроме того, мы использовали спам-ресурсы, которые были распознаны в ходе исследования в работе [13]. Saito и др. получили этот крупный спамовый набор посредством выполнения следующих шагов. Для начала они разложили веб по компонентам сильной связанности (SCC — сокращение от англ. Strongly Connected Components), опираясь на то предположение, что спам-сайты формируют SCC. Крупные компоненты сильной связанности, за исключением самой большой, были расценены ими как спам. Для вычисления некачественных веб-ресурсов в крупнейшей SCC или ядре, Saito и др. изучили клики максимального размера. Те клики, чей размер был меньше, чем 40 извлекались из ядра, и среди них было обнаружено порядка 8000 спам-сайтов. Наконец, они использовали данные некачественные ресурсы в качестве достоверного спамового исходного набора и расширили его с применением техники минимального разреза для разделения гиперссылок между спам и НЕ-спам сайтами. Поскольку их методология вычисления спама показала высокую точность, мы использовали их спам-ресурсы для пополнения нашего негативного (спамового) исходного набора. Итого, в общей сложности наш исходный спамовый набор включал в себя 580325 сайта.

5.2 Типы хиджакинга

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

Тип сайта Количество сайтов
Хиджакинг 465
Норма 345
Спам 576
Неизвестно 6
Всего 1392

Таблица 1. Количество сайтов-образцов каждого типа

Техника хиджакинга была идентифицирована на сайтах, составляющих 33% от общего числа интернет-ресурсов; эти 454 сайта были разделены нами на 8 типов следующим образом:

Типы сайтов, подверженные хиджакингу Количество сайтов
Блоги и доски объявлений 117
Освобожденные домены, купленные спамерами 78
Сайты-клиенты хостинговых компаний, поддерживающие хиджакинг 64
Цитирующие освобожденный домен, купленный спамерами 60
Сайты-каталоги ссылок 55
Цитирующие спам-сайт по ошибке 51
Рекламирующие спам-сайты 30
Сервера статистики 10
Итого 465

Таблица 2. Типы сайтов, подверженные хиджакингу

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

5.3 Подбор параметров

Для подбора штрафующего λ и весового γ параметра (см. Раздел 4) были получены показатели наличия хиджакинга для 1392 эталонных сайтов, описанных в подразделе 5.2. Нами были исследованы типы первых 300 интернет-ресурсов; для того чтобы рассчитать показатель наличия хиджакинга по всем веб-сайтам, мы выбрали те значения параметров, при которых была продемонстрирована наилучшая точность. Для расчета положительных и негативных (спам) оценок мы использовали оценки core-based PageRank. Как в случае с Hs, так и при Hns, лучшая точность достигалась при λ равным 60. Мы обнаружили, что в том варианте, когда значение λ превышало 60, количество спам-сайтов в топе практически не изменялось. Доля нормальных сайтов с высоким показателем наличия хиджакинга оставалась стабильной, вне зависимости от параметра λ. Для подбора весового параметра γ для Hns мы исследовали количество сайтов, подвергшихся хиджакингу, среди топ 300 интернет-ресурсов с высоким показателем Hns, рассчитанного с использование различных значений γ и δ.

γ / δ -5 -4 -3 -2 -1 0 1 2 3 4
0.0 (Hs) 100 99 100 109 121 144 166 171 161 144
0.3 110 114 129 144 167 179 170 159 141 138
0.4 112 120 140 165 177 189 163 151 139 133
0.5 114 125 159 177 189 187 159 146 140 133
0.6 139 161 181 196 189 183 151 144 136 133
0.7 168 188 205 200 182 171 152 148 136 132
0.8 185 198 193 179 169 165 150 146 135 130
0.9 189 187 177 159 154 150 142 143 135 134

Таблица 3. Количество интернет-ресурсов, подвергшихся хиджакингу, входящих в топ 300 сайтов-образцов с наибольшим показателем Hns, полученного с учетом различных значений δ и γ. Параметр λ установлен на 60.

Как показано в Таблице 3, точность повышается с уменьшением значения δ и увеличением значения γ. Это означает, что если мы выбираем некоторый веб-сайт s в качестве кандидата с реализованным хиджакингом, даже если его White(s)

5.4 Оценка

С учетом оценок core-based PageRank и тех параметров, что были описаны в подразделе 5.3, мы рассчитываем показатели Hs и Hns по всем веб-сайтам.

Результат для Hs. Для параметра δ, установленного в диапазоне от +1 до +4 мы выбрали топ 200 сайтов с наибольшим значениями показателя Hs и вручную классифицировали их по следующим категориям: хиджакинг, нормальный сайт, спам и сайт с неизвестным содержимым (Ручная маркировка сайтов является дорогим и трудоемким занятием. Прежде чем отнести сайт s к хиджакингу, мы, сперва, решаем, классифицировать ли его как спам или как нормальный интернет-ресурс. В том случае, если веб-сайт оказывается нормальным, мы все равно должны проверить цитируемых им соседей по Сети на предмет наличия спама уже среди них. Если среди его ссылочного окружения будет обнаружен некачественный ресурс, тогда мы должны исследовать вопрос природы проставленной на него гиперссылки, то есть, создана ли она спамером или веб-мастером. В том случае, если мы оцениваем веб-ресурс, который размещается на домене, который был приобретен владельцем сайта после своего освобождения, нам необходимо проинспектировать прошлые мгновенные снимки его ссылочного состояния. Только тогда, когда в своем прошлом ресурс был нормальным, а на текущем этапе своего развития стал классифицироваться как спам, пусть даже цитируемый нормальными веб-сайтам, мы определяем его как некачественный ресурс, размещенный на освобожденном домене, который был куплен спамером для своих манипулятивных целей). Детали отражены в Таблице 4. Наилучшая точность в 44.5% достигается при δ=+3. Штрафующий параметр λ установлен на 60.

δ 1 2 3 4
Хиджакинг 55 75 89 65
Норма 3 4 25 78
Спам 132 109 79 50
Неизвестно 10 15 7 7
Всего 200 200 200 200
Точность 22.5% 37.5% 44.5% 32.5%

Таблица 4. Полученная точность при использовании Hs с различными значениями δ.

Результат для Hns. С учетом параметра δ, установленного в диапазоне от -4 до -1, мы рассчитали показатель Hns и снова выполнили оценку топ 200 сайтов, получивших наибольшее его значение. Как описано в Таблице 5, наилучшая точность в 70% при определении веб-сайтов, подвергшиеся хиджакингу, достигается при δ=-3. Данный результат превосходит тот случай, когда используется Hs с точностью детекции в 25.5%. Штрафующий параметр λ здесь также установлен на 60, а весовой параметр γ=0.7.

δ -4 -3 -2 -1 0
Хиджакинг 138 140 139 128 110
Норма 25 25 36 47 72
Спам 37 33 23 22 16
Неизвестно 0 2 2 3 2
Всего 200 200 200 200 200
Точность 69% 70% 69.5% 64% 55%

Таблица 5. Полученная точность при использовании Hns с различными значениями δ.

Можно отметить, что по мере увеличения δ, количество нормальных сайтов также возрастает, что отражено в Таблицах 4 и 5. Это объясняется тем, что при более высоким значении параметра δ сайт должен иметь более высокую положительную оценку, чтобы быть заподозренным в хиджакинге. Аналогично, по мере уменьшения значения параметра δ, доля спам-сайтов также уменьшается. Это означает, что наш алгоритм добавляет сайты с относительно высокой спам-оценкой в набор ресурсов, подозреваемых в применении хиджакинга. Выявленные при наилучшей производительности Hns 140 сайтов, подвергшихся хиджакингу, были классифицированы по различным типам данной мошеннической техники. Все детали приведены в Таблице 6. Среди всех типов манипуляций, доминирующим по-прежнему остается хиджакинг в блогах и досках объявлений, за которыми следуют сайты, размещенные на хостинге. Обратите внимание, что нам посчастливилось обнаружить несколько веб-сайтов, размещенных на освободившихся доменных именах, которые были приобретены спамерами и которые, с нашей точки зрения, представляются крайне полезными в задачах обнаружения вновь создаваемых спам-сайтов (см. подраздел 5.6).

Типы сайтов, подвергшиеся хиджакингу Количество сайтов
Блоги и доски объявлений 48
Освобожденные домены, купленные спамерами 19
Сайты-клиенты хостинговых компаний, поддерживающие хиджакинг 30
Цитирующие освобожденный домен, купленный спамерами 13
Сайты-каталоги ссылок 8
Цитирующие спам-сайт по ошибке 18
Рекламирующие спам-сайты 0
Сервера статистики 3
Итого 140

Таблица 6. Анализ веб-сайтов, подвергшихся хиджакингу, которые были обнаружены посредством использования Hns при δ = −2,λ = 60 и γ = 0.7.

5.5 Сравнение различных пар оценок

Мы вычислили показатели наличия хиджакинга, используя попарное сравнение оценки, присвоенной алгоритмом TrustRank и Anti-TrustRank с последующим анализом производительности. Однако показатель точности оказался намного хуже, чем в случае использования пары core-based PageRank. Для того, чтобы выяснить причины столь сильного разрыва в показателе точности, мы проинспектировали каждую пару оценок сайтов, подвергшихся хиджакингу, что были описаны нами в подразделе 5.2.

Рисунок 1. Попарное сравнение оценок TrustRank и Anti-TrustRank

Рисунок 2. Попарное сравнение оценок Core-based PR+ и Core-based PR

На рисунке 1 и 2 продемонстрированы результаты. Как для оси абсцисс, так и для оси ординат была использована логарифмическая шакала. Можно заметить, что попарное сравнение оценок core-based PageRank сайтов, подвергшихся хиджакингу, демонстрирует линейную зависимость по сравнению с парами TrustRank и Anti-TrustRank. Поскольку сайты, подвергшиеся хиджакингу, с высокой оценкой PR обнаруживаются на Рисунке 2, мы проверили их мануально и обнаружили, что каждый из них представляет собой некачественный сайт, который был создан спамером на освободившихся доменных именах, некогда принадлежавших нормальным веб-сайтам, для реализации технологии хиджакинга. Коэффициент корреляции Пирсона пары core-based PageRank составляет 0.73 в том случае, если опустить оценки некачественных сайтов, созданных на освобожденных доменах. Однако коэффициент корреляции пары TrustRank и Anti-TrustRank составляет 0.1, что является достаточно низким показателем. Обратите внимание на то обстоятельство, что наилучшая точность обнаружения хиджакинга достигается в том случае, если мы используем отрицательное значение δ (см. подраздел 5.4), не подразумевающее хиджакинг как таковой, который имеет более высокую спам-оценку нежели чем положительную. Таблица 3 и 4 демонстрирует, что большинство сайтов, подвергшихся хиджакингу, идентифицируются уже при δ=0, что свидетельствует о том, что хиджакинг, более вероятно, имеет высокую или схожую положительную оценку как и его спам-оценка.

5.6 Обнаружение спам-сайтов посредством следования по гиперссылкам, ведущих с ресурсов, подвергшихся хиджакингу

Для того чтобы подтвердить нашу гипотезу, касательно того, что наблюдение за сайтами, подвергшиеся хиджакингу, может помочь нам идентифицировать спам, мы случайным образом выбрали 6 сайтов из выборки тех ресурсов, на которых была реализована технология хиджакинга (см. подраздел 5.2): два блога, две доски объявлений и два сайта, созданных на ранее освобожденных доменах. Указанные три типа хиджакинга были выбраны нами по той простой причине, что на них, как мы предполагаем, реализовать данную манипулятивную технологию не составит большого труда, а также потому, что они могут постоянно использоваться спамерами. От каждого сайта s мы изымаем некоторый веб-документ p, который ссылается более чем на один интернет-ресурс, имеющего отрицательное значение RT, а также низкую положительную и высокую отрицательную (спам) оценку, нежели чем сам веб-сайт s. Для всех выбранных хиджакинг-документов мы извлекаем их гиперссылочное окружение по данным мгновенных снимков ссылочного состояния за 2005 и 2006 гг., которое в 2004 году еще ими не цитировалось. Для нашей оценки мы мануально проверяем появившиеся за данные период гиперссылки на предмет наличия или отсутствия в содержимом цитируемых ими страниц поискового спама. В том случае, если страница является спамом, тогда веб-сайт, ее содержащий, также расценивается нами как некачественный. В том случае, если среди нескольких обнаруженных страниц, относящихся к одному сайту, хотя бы единственная оказалась некачественной, тогда весь интернет-ресурс классифицируется нами как спам. (Необходимо отметить, что мы опускали из рассмотрения те интернет-страницы, которые не загружались или были описаны на таком языке, который не мог быть распознан).

Год 2005 2006 Итого
Исх. ссылки спам / всего спам / всего спам / всего (%)
Доска объявлений 1 64 / 68 23 / 25 87 / 93 (93.5%)
Доска объявлений 2 12 / 13 0 / 0 12 / 13 (92.3%)
Блог 1 0 / 4 0 / 13 0 / 17 (0%)
Блог 2 73 / 73 0 / 0 73 / 73 (100%)
Сайт, созданный на освобожденном домене 1 1964 / 1981 4 / 8 1968 / 1989 (98.8%)
Сайт, созданный на освобожденном домене 2 1 / 1 21 / 21 22 / 22 (100%)

Таблица 7. Количество спам-сайтов в 2005 и 2006 гг, обнаруженных посредством наблюдения за гиперссылками, ведущих со страниц на которых была реализована технология хиджакинга.

Как вы можете видеть из Таблицы 7, практически все обнаруженные за указанный период новые веб-сайты, которые цитировались ресурсами, подвергшиеся хиджакингу, оказались некачественными. Мы полагаем, что посредством наблюдения за сайтами, которые созданы на ранее освобожденных доменах, можно обнаружить очень большое количество поискового спама в том случае, если они включается в непрерывно прогрессирующую ссылочную ферму. Заметим, что новые исходящие ссылки на спам-документ не создавались на Блоге 2. По всей видимости, автор блога просто не удалил ссылочный хиджакинг в тех своих старых постах, что относились к 2004 году.

6. Заключение

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

Ссылки:

[1] The Offcial Google Blog, googleblog.blogspot.com/2008/07/we-knew-web-was-big.html

[2] S. Nakamura, S. Konishi, A. Jatowt, H. Ohshima, H. Kondo, T. Tezuka, S. Oyama, K. Tanaka, ”Trustworthiness Analysis of Web Search Results”, Proc. 11th European Conference on Research and Advanced Technology for Digital Libraries. Budapest, Hungary, 2007.

[3] A. Ntoulas, M. Najork, M. Manasse, and D. Fetterly, ”Detecting Spam Web pages through Content Analysis”, Proc. of 15th International Conference on World Wide Web. Edinburgh, Scotland, UK, 2006.

[4] D. Fetterly, M. Manasse and M. Najork, ”Spam, Damn Spam, and Statistics: Using Statistical Analysis to Locate Spam Web Pages”, Proc. 7th International Workshop on the Web and Databases. Paris, France, 2005.

[5] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.

[6] Z. Gyongyi and H. Molina, ”Link Spam Alliance”, In : 31st International Conference on Very large Data Bases, Trondheim, Norway, 2005.

[7] Y. Du, Y. Shi, X. Zhao, ”Using Spam Farm to Boost PageRank”, In : 3rd International Workshop on Adversarial Information Retrieval on the Web. Banff, Alberta, Canada, 2007.

[8] Z. Gyongyi, H. Garcia-Molina and J. Pedersen, ”Combating Web spam with TrustRank”, In : 30th International Conference on Very Large Data Bases. Toronto, Canada, 2004.

[9] B. Wu, B, V. Goel, B. D. Davison, ”Topical TrustRank: Using Topicality to Combat Web Spam”, In : 15th International Conference on World Wide Web. Edinburgh, Scotland, UK, 2006.

[10] Z. Gyongyi, P. Berkhin, H. Garcia-Molina and J. Pedersen, ”Link Spam Detection Based on Mass Estimation”, In : 32nd international conference on Very Large Data Base. Seoul, Korea, 2006.

[11] V. Krishnan, R. Raj, ”Web Spam Detection with Anti-TrustRank”, In : 2nd International Workshop on Adversarial Information Retrieval on the Web. Edinburgh, Scotland, UK, 2006.

[12] A. Benczur, A. K. Csalogaґny, T. Sarloґs, M. Uher, ”SpamRank-fully automatic link spam detection”, In : 1st International Workshop on Adversarial Information Retrieval on the Web. Chiba, Japan, 2005.

[13] H. Saito, M. Toyoda, M. Kitsuregawa and K. Aihara, ”A Large-scale Study of Link Spam Detection by Graph Algorithms”, In : 3rd International Workshop on Adversarial Information Retrieval on the Web. Banff, Alberta, Canada, 2007.

[14] M. Najork and J. L. Wiener. ”Breadth-first Crawling Yields High-quality Pages”, In : 10th international conference on World Wide Web, Hong Kong, China, 2001.

[15] The Offcial Google Blog, googleblog.blogspot.com/2005/01/preventing-comment-spam.html

Ян-чу Чен

Ян-чу Чeн получила степень бакалавра в области Компьютерных Наук и Инженерного дела Сеульского Национального Университета (Южная Корея) в 2005 году. В 2008 году она получила степень магистра в области Информационной Инженерии Факультета Информатики и Коммуникаций Токийского Университета, в котором она по настоящее время является кандидатом в доктора философских наук. Ее интересы включают веб-майнинг и интернет-анализ.

Масаши Тоёда

Масаши Тоёда является доцентом Института Промышленных Наук Токийского Университета, Япония. Он получил степень бакалавра, степень магистра и Доктора Философии в области Компьютерных Наук Токийского Технологического Института (Япония) в 1994, 1996 и 1999 гг. соответственно. Он работал в Институте Промышленных Наук Токийского Университета в качестве специально назначенного доцента с 2004 по 2006 год. Его исследовательские интересы включают веб майнинг, пользовательские интерфейсы, визуализация информации и визуальное программирование. Он является членом ACM, IEEE CS, IPSJ и JSSST.

Масару Кицурэгава

Масару Кицурэгава на данный момент является Профессором и Директором Центра Слияния Информации в Институте Промышленных Наук Токийского Университета. Он получил степени бакалавра и магистра по специальности Инженерной Электроники в Токийском Университете в Японии в 1978 и 1980 году, соответственно. В том же университете он получил степень Доктора Наук по Информационной Инженерии в 1983. На данный момент его исследовательские интересы охватывают разработку баз данных, веб-майнинг, архитектуру систем хранения данных, параллельный дата-майнинг/обработка баз данных, концепцию Цифровой Земли и обработку транзакций. Он занимал должность сопредседателя IEEE ICDE (Международная Конференция по Разработке Данных) в 2005 году; выступал в качестве члена правления VLDB и председателя ACM SIGMOD (Япония). Профессор Кицурэгава является членом IPSJ и IEICE (Япония) и директором DBSJ. Он член IEEE CS.

Перевод материала «A Method for Detecting Hijacked Sites by Web Spammer using Link-based Algorithms» выполнил Константин Скоморохов

Полезная информация по продвижению сайтов:

Перейти ко всей информации