Вопрос для интервью: Honeypots и веб-сканеры

Question

Я недавно читал книгу в качестве подготовки к интервью и наткнулся на следующий вопрос:

Что вы будете делать, когда ваш сканер столкнется с горшком меда, который генерирует бесконечный подграф, по которому вы можете бродить?

Я хотел получить некоторые решения для этого вопроса. Лично я хотел бы, чтобы какая-то форма поиска ограничивала глубину, чтобы избежать непрерывного перемещения. Или, возможно, использовать какую-то форму машинного обучения для выявления закономерностей. Мысли? * * 1005

Answer 1

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

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

По вопросу интервью (об обнаружении бесконечных циклов):

Если они задают этот вопрос, кто-то хочет услышать ссылку на проблему Остановка

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

Answer 2

Вы можете ограничить количество найденных страниц. Конечно, есть проблема с этим .. что, если сайт действительно огромный? Википедия бесконечна? :)

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