Анализ данных Краулеры и мошенничество в поисковых системах

План лекции Задачи и архитектура поисковых роботов Алгоритм обхода ссылок Обманы поисковых систем – Doorway, cloaking – Поиск дубликатов Основная задача: получить представление о краулерах и видах обмана поисковых систем

Характеристики веба Характеристики веба: Децентрализация Неструктурированность информации Нет контроля авторства Общая неоднородность страниц

Доверие источнику Каждый пользователь имеет свое представление об авторитетности документа Задача поисковика – определять общую степень доверия документу (статический ранг)

Веб-граф Каждый документ ссылается на другие Ссылка документа A на документ B говорит о связи авторитета А и В.../wiki/IBMibm.com * Но на самом деле ссылки с Википедии не влияют на ранг, чтобы не было войны правок

Виды ссылок Полустепень захода – количество входящих ссылок (обычно 8-15) Полустепень исхода – количество исходящих ссылок

Цель краулера Быстро и эффективно собрать как можно больше полезных веб-страниц вместе со ссылками, которые их объединяют

Характеристики краулера Качество – больше внимания полезным ресурсам, система приоритетов Свежесть – гарантия, что индекс содержит самые последние представления о страницах

Характеристики краулера Распределенность – можно искать несколькими роботами Масштабируемость – увеличение производительности за счет роста полосы пропускания и числа машин Расширяемость – индексация новых типов данных, протоколы и т.д.

Характеристики краулера Распределенность – можно искать несколькими роботами Масштабируемость – увеличение производительности за счет роста полосы пропускания и числа машин Расширяемость – индексация новых типов данных, протоколы и т.д.

Компоненты краулера Очередь на скачивание URL Модуль DNS Анализатор URL (выявление шаблона, фильтры) Анализ документов-дубликатов Базы: URL, шаблонов URL, контрольных сумм документов

Компоненты краулера веб DNS качалка индексатор cksumшаблоныURLs анализ, фильтры очередь на скачивание

Алгоритм работы 1.В очередь добавляется начальное количество URL 2.Страницы по этим ссылкам поочередно скачиваются 3.Проверка документа на уникальность 4.Поиск ссылок на скачанных страницах 5.Ссылки добавляются в очередь 6.Перейти к шагу 2

Проблемы краулера DNS – узкое место, так как DNS lookup часто синхронны (нужно ждать ответа на каждый запрос). Не все серверы могут выдержать индексацию Можно попасть в ловушку для робота (spider trap)

Очередь на скачивание Правила формирования очереди: С одним хостом в каждый момент времени только одно соединение Между последовательными соединениями с одним хостом должно пройти время Часто обновляемые полезные веб- страницы должны возникать чаще в очереди

Очередь на скачивание Правила формирования очереди: С одним хостом в каждый момент времени только одно соединение Между последовательными соединениями с одним хостом должно пройти время (вежливость) Часто обновляемые полезные веб- страницы должны возникать чаще в очереди

Очередь на скачивание Модули формирователя очереди: Фронтальные очереди (F) – распределение приоритетов Тыльные очереди (D) – вежливость Назначение приоритета основано на частоте обновления страницы и количестве попадания в список на скачивание

Очередь на скачивание 1.Модуль назначения приоритетов берет URL из базы и отправляет в одну из F очередей 2.Модуль смещения выбора берет из очередей F в соответствии с приоритетами 3.Маршрутизатор тыльных очередей формирует очереди D по приоритетам 4.Из очередей D ссылки поступают в качалку

Очередь на скачивание Получение приоритетов Смещение фронтальной очереди Маршрутизатор тыльной очереди Модуль выбора из тыльной очереди …… качалка

Хранение ссылок Нужно для сервисов: искать ссылки на сайт, искать в пределах сайта и т.д. ID документа ID документов по исходящим ссылкам 231, 2, 5, … 42… ……

Обман поисковых систем Мотивация обмана: привлечение пользователя к действиям, интересным владельцу страницы отсутствие желания удовлетворить информационные потребности пользователя

Цели обмана Фишинг – получение аккаунтов популярных сайтов, денег, реквизитов кредитных карт и т.д. Реклама – получение прибыли с баннеров на странице Заражение компьютера пользователя – получение ботнета

Обман поисковой системы Минимальные затраты: Doorway Cloaking Скрытый текст на страницах Spider trap Продвинутые методы: Автоматическая генерация контента

Дорвеи Дорвей – страница оптимизированная под несколько запросов, но не имеющая информационной ценности Цель дорвеев: имитировать переход пользователя на продвигаемый сайт Можно создавать цепи дорвеев, которые продвигают друг друга

Методы борьбы Найти перенаправляющий код Определить, есть ли что-то кроме баннеров на странице Смоделировать представление страницы и проанализировать расположение объектов

Дорвеи сейчас Большинство поисковиков хорошо отличают дорвеи от обычных сайтов Генераторы дорвеев основаны на цепях Маркова (последовательности случайных событий) На дорвеях до сих пор кто-то зарабатывает

Клоакинг Клоакинг – подмена содержимого страницы для обычного пользователя и поисковой системы Цель: для поисковиков выглядеть как полезный сайт, а для пользователей – как спам Эффективно в сочетании с другими видами спама

Проблемы клоакинг Методы определения поискового робота: IP Мета-данные запроса (user agent) Простые методы борьбы: Использование прокси, обновление IP Смена user agent

Невидимый текст Невидимый текст – текст, незаметный для пользователя, но распознающийся поисковым роботом Обычно содержит текст для регулирования веса ключевых слов Метод борьбы: анализ CSS страницы

Ловушка для паука Spider trap – динамическое создание страниц и статических по виду URL на них для зацикливания поискового робота Робот индексирует страницы и сам же провоцирует появление новых (больше страниц в индексе – больше шансов попасть в результаты поиска)

Методы борьбы Корректное формирование очереди Не индексировать слишком много новых страниц с одного хоста Искать шаблон генерации новых страниц

Клонирование сайтов Создание копий сайтов для целей: Получить схожий ранг авторитета (копирование контента) Фишинг (копирование интерфейса) Борьба с фишингом – хранение базы шаблонов потенциальных для фишинга сайтов

Поиск дубликатов Виды дубликатов: Есть точные копии текстов Есть тексты, в которых вручную или автоматически изменены слова на синонимы Есть автоматически сгенерированные тексты (~шизофазия)

Точные копии документов Для быстрой проверки копий достаточно создать базу контрольных сумм (fingerprint)блоков документов Достоинство: Скорость работы Недостатки: Малая эффективность для текстовых данных

Нечеткие дубликаты Нечеткие дубликаты: Измененные символы, даты, слова Частичное заимствование (или плагиат) Рерайт

Шинглирование Шингл – небольшая последовательность терминов в документе Обычная длина шингла – 4 термина Чем больше шингов, тем менее оригинален текст

Алгоритм шинглов 1.Документ разбивается на шинглы 2.Каждый шинг хешируется (сопоставляется с контрольной суммой) 3.Множество всех шинглов документа: S(d) 4.Сходство двух документов по метрике Жаккара:

Генераторы текстов Особенности: Уникальность ~100%! Польза ~0% Тексты обычно генерируются с помощью цепей Маркова

Цепи Маркова (пример)

Методы борьбы Составление статистики связности слов: Частота встречаемости последовательности слов Вычисление количества пар диапазонов функции Cor:

Методы борьбы Сравнение значений со значениями текстов: