Привет! Меня зовут Илья Кацев, и я представляю небольшое исследовательское подразделение в отделе тестирования в Яндексе. Вы уже могли читать о нашем экспериментальном проекте Роботестер — роботе, который умеет проделывать за тестировщика заметную часть рутинной работы.
Наша основная цель — изобрести принципиально новые подходы для нахождения ошибок в Яндексе. Я очень люблю порассуждать на тему того, какая часть работы в будущем ляжет на плечи роботов. Они уже отлично пишут спортивные репортажи и переносят грузы для солдат. И вообще мне кажется, что человеческий прогресс непосредственно зависит от того объема работы, который мы сможем передать роботам — у людей в этом случае появляется свободное время и они придумывают новые крутые штуки.
Есть такой тезис, сторонником которого я лично являюсь, — любую ошибку, которую может заметить неподготовленный пользователь, может обнаружить и робот. Именно это мы и попытались проверить. Но тут возникает вопрос: что именно человек считает ошибкой?
Искусственный интеллект пока никто не изобрёл (хотя Хокинг, например, считает, что это к лучшему), но кое-каких успехов нам удалось добиться. В этом посте я расскажу о том, как мы формулировали опыт, которым обладают тестировщики-люди и постарались научить ему наших роботов, и что из этого вышло.
Когда мы создавали Роботестера, перед нами стояла задача автоматизировать рутинную работу, на которую уходит время тестировщика. Мы научили алгоритм открывать веб-страницу, понимать, какие действия можно произвести с элементами, заполнять текстовые поля, нажимать кнопки и пытаться угадать, когда же произошла ошибка. Но у нас возникла проблема — оказалось, что с высокой достоверностью робот может обнаружить только самые тривиальные ошибки.
Дело в том, что принцип работы робота — проверять как можно больше страниц — приводил к большому числу тестов, а это означало, что точность определения ошибки становилась ключевым фактором. Мы подсчитали, что для проверки Яндекс.Маркета наш робот делал 800 000 различных проверок в сутки. Соответственно, если false positive rate проверок в среднем равен 0.001 (что кажется небольшим числом), то каждый день будет приходить отчет о якобы найденных 800 ошибках, которых на самом деле нет. Естественно, это никого не устраивает.
Следует отметить, что «фальшивые» сообщения об ошибках всегда случаются. Особенно, когда речь идет о веб-тестах, так как для них используется вспомогательные инструменты — могут быть проблемы с браузером, который использует робот, проблемы с интернетом, и так далее.
Есть весьма «чистые» проверки. Например, код ответа ссылки 404 с огромной вероятностью свидетельствует о том, что проблема есть. Пример проверки с низкой точностью — наличие в тексте буквосочетания « ,» (пробел и запятая). Действительно, когда между пробелом и запятой не подгрузились какие-то данные, такое буквосочетание свидетельствует об ошибках. Но иногда речь идет просто об опечатках. Особенно когда в область проверки попадает текст пользовательских комментариев или контенет из внешних источников. Поэтому для нахождения этих ошибок приходится проводить работу вручную, отделяя «настоящие» проблемы от «фальшивых».
В итоге, робот действительно полностью брал на себя часть работы тестировщиков (например, находил все битые ссылки), но совсем не всю. И мы задумались о том, как «добавить роботу интеллекта».
Традиционно в тестировании запускают тестируемую программу с какими-то заданными входными данными и сравнивают результаты с каким-то также наперед заданным «правильным» результатом. Он может быть задан вручную, или, скажем, сохраняться при запуске предыдущей версии программы (тогда мы сможем найти все различия между данной версией и предыдущей), но общий принцип все равно остается таким. По сути подход в целом здесь не меняется десятки лет, меняются только инструменты для реализации этих тестов.
Однако оказывается, что возможны принципиально иные подходы для определения того, что является ошибкой.
Мы изначально говорили о том, что робот должен научиться определять ошибки, которые может любой человек, необязательно профессиональный тестировщик данного сервиса.
Итак, где ошибка на этой странице?
Конечно, правильный ответ — среди пяти предложений снизу есть повторяющиеся. Чтобы понять, что это ошибка, не надо быть экспертом в Маркете — надо просто обладать минимальным здравым смыслом.
Другой пример.
Здесь в одном месте написано «нет в продаже», а в другом — указаны цены. Опять же абсолютно любой человек понимает, что это некорректная ситуация.
Еще один пример.
Это просто чистая страница. То есть у нее есть стандартные «шапка» и «футер», но нет никакого контента в середине.
Здесь и возникает ключевой вопрос — как человек понимает, что это ошибка? На каком механизме это основано?
Мы долго думали, и кажется, что ключевое слово здесь — опыт. То есть человек уже видел в своей жизни много веб-страниц, причем некоторые были ровно такого же типа. И именно из них у него сформировался некоторый шаблон. Этот шаблон может быть как очень общим («страница не должна быть пустой», «все результаты поиска должны быть различны»), или, наоборот, привязанным к данным страницам («два выделенных блока содержат или не содержат цифры одновременно»). То есть у него в голове уже сформировались эти правила и, как мы видим по данным примерам, они выглядят совсем несложными.
Таким образом, дальнейшая задача тут стала ясна — надо научиться автоматически извлекать эти правила, анализируя множество схожих или не очень схожих веб-страниц.
Видно, что сформулированные правила довольно просты, и, если бы мы научились их автоматически извлекать, то можно было бы формировать автотесты без участия человека. Например, роботу дается для анализа много страниц сервисов Яндекса, и он понимает, что на них на всех снизу есть ссылка «О компании». Соответственно этот факт формулируется как правило, и робот будет проверять его выполнение для новой версии сервиса или даже для другого сервиса.
Самое просто применение этой идеи такое: анализируем все страницы сервиса в продакшн, вычленяем такие «правила», а затем проверяем, выполняются ли они для новой версии того же сервиса.
Этот подход давным-давно всем известен. Он называется back-to-back тестирование и есть те, кто его использует. Однако такой метод хорошо применим лишь тогда, когда работа сервиса не должна заметно меняться от версии.
Давайте рассмотрим поисковую выдачу вчера и сегодня — результаты поиска и реклама рядом меняются. Онии зависят от региона пользователя, его предпочтений, времени суток, наконец. Соответственно, при непосредственном сравнении будет слишком много «мусора» (отметим, что в некоторых ситуациях и такой непосредственный метод допустим).
Здесь же мы развиваем нашу идею и осуществляем сравнение, «очищенное» от мусора, — мы сравниваем не сами страницы, а некоторые «модели» страниц.
Сформулировав общую идею, перейдем к тому, как же ее реализовывать. Наша задача — автоматически извлекать правила. Для понимания человеком они очень простые. Мы их формулируем на языке «блоков» — мы говорим о том, содержит определенная часть страницы какой-то элемент или нет, присутствует ли на странице определенный блок, и так далее. Для человека страница делится на них естественным образом — вот форма авторизации, вот поисковая форма (и в ней подблоки — строка поиска, кнопка «найти»). Однако робот «видит» перед собой html-код, и ему совершенно непонятно, какая часть этого кода образует блок.
Мы решили четко сформулировать понятие блока. То есть сначала мы решили понять для себя, что же мы, люди, называем блоком. Давайте посмотрим, какие бывают блоки.
1. Постоянные. Весь блок целиком присутствует на каждой странице).
2. Меняющиеся. Какой-то тэг присутствует на каждой странице, но внутри него каждый раз все меняется.
3. Однотипные блоки на одной странице.
4. Однотипные, но разные по сути блоки на одной странице.
При этом на разных страницах один и тот же блок может стоять на разных местах.
То есть для нас «блок» — это некая часть страницы, которая при её изменении остается более-менее постоянной. Например, человек легко понимает, что формы из пункта 2 (см. выше) — это частные случаи «одной и той же оранжевой формы», но при этом содержание формы меняется.
Отдельную проблему представляют собой несколько схожих блоков, идущих подряд. Иногда это именно «несколько однотипных блоков», а иногда — набор объектов разных типов, и тогда хочется понять, какого типа объекты вообще там встречаются.
В первую очередь нам нужен какой-то способ помечать уже выделенный блок на каждой странице. Традиционный xpath (например,
Поэтому мы сначала убираем числа из xpath'а (получая
Теперь давайте искать блоки. Если представлять html-код как дерево, то наша задача — искать стабильные пути из корневой вершины (стабильность здесь означает, что путь мало меняется при изменении страницы). Алгоритм построения множества таких стабильных путей — это основная часть нашего инструмента. Строили мы его «методом проб и ошибок». То есть мы модифицировали алгоритм и смотрели на результат. Алгоритм я опишу ниже, а пока расскажу о совершенно неожиданной проблеме — мы внезапно поняли, что не знаем, как изображать, какие блоки выделились на странице.
Действительно — блок выглядит по-разному на разных страницах. Нам хотелось получать отчет в виде чего-то, похожего на страницу, разбитую на блоки. Но какой из вариантов блока брать? Мы раз за разом натыкались на случаи, когда к нам в отчет попадал пустой или малоинформативный вариант. Нужно было как-то компактно показать все варианты на одной и той же странице. Одному из разработчиков пришла в голову удачная идея — сделать как, например, сделанона порносайтах в сервисе Coub: при наведении мышки на видео там сменяются кадры оттуда. Мы сделали ровно то же самое — если навести указатель мышки на блок, то блок этот начинает «мигать», показывая, как он выглядит на разных страницах. Это оказалось очень удобным.
В итоге «модель страницы» выглядит примерно так (см. ниже). Можно посмотреть на нее и сразу понять, какие блоки выделились.
Теперь насчет алгоритма. Базовый алгоритм выглядит следующим образом:
Большим достоинством алгоритма является то, что он линейно зависит как от числа элементов первой страницы, так и от количества страниц.
Однако как мы скоро выяснили, есть места, где алгоритм срабатывает плохо. Например, вот для этих блоков (isbn, автор и так далее):
Как html-элементы они совершенно одинаковы, отличаются только порядковым номером. Но сразу же ясно, что этот номер ничего не означает — на примере выше ISBN то второй, то первый. Поэтому нам стало ясно, что единственный способ отличать такие элементы — по тексту внутри. Поэтому мы изменили алгоритм следующим образом: в самом начале ищем места, где у элемента есть несколько потомков, отличающихся только текстом. Тогда мы собираем схожие элементы потомков со всех страниц, а затем кластеризуем их по тексту так, чтобы на каждой странице было не более одного представителя каждого кластера.
Были и другие улучшения алгоритма, но они могут быть вам не так интересны, так как связаны с яндексовой спецификой. Даже описанный сейчас алгоритм достаточно хорошо сработает на большинстве наборов страниц.
Итак, проанализировав структуру страниц из обучающей выборки, выделив блоки и поняв, какие блоки на скольких страницах присутствуют, можно формулировать правила следующих типов:
Можно в принципе извлекать и более сложные закономерности, но мы этим пока не занимались.
Для каких же блоков мы формируем условие первого типа? Для тех, которые встречаются на достаточно большой доле страниц. Определяется эта доля специальным параметром, который мы называем confidence level. Неправильно устанавливать этот параметр равным единице — так, как мы хотели делать изначально, по двум причинам:
Мы этот уровень значимости варьируем в зависимости от стабильности среды, на которой мы обучаем наш инструмент. Уменьшая значение параметра, можно «убирать» эффект нестабильности среды. Однако если сильно уменьшить этот параметр, то инструмент начнет выделять дополнительные неправильные закономерности. Например, если у 96% товаров есть цена, а у 4% написано «нет в продаже», то при установке параметра в 0.95 страницы с «нет в продаже» будут помечены как ошибочные. По дефолту confidence level равен 0.997.
Помимо условий на наличие/отсутствие блоков мы автоматически генерим условия на текст внутри каждого блока. Условия формируются в виде регулярных выражений. Например, на блок с годом издания на такой странице
будет следующая регулярка:
Год издания: [0-9]{4}
Или даже такая:
Год издания: (19|20)[0-9]{2}
При этом сам этот блок помечен как необязательный. То есть проверяется следующее — что если такой блок есть, то в нем после слов «год издания» написано 4 цифры или даже, что написаны 4 цифры, первые две из которых 19 или 20. Примерно такой тест написал бы и человек.
Если резюмировать, наш инструмент умеет следующее: по набору страниц мы извлекаем правила определенного типа, которые выполняются для заданного процента этих самых страниц. Как же с помощью этого искать баги? Есть два пути.
Фактически во втором случае мы получаем то же самое, что и при наличии регрессионных автотестов. Однако в нашем случае есть большое, даже огромное достоинство, — код этих тестов не надо писать и поддерживать! Как только выложили новую версию сервиса, я нажимаю кнопку «перестроить все» и через несколько минут готова новая версия «автотестов».
В качестве эксперимента по внедрению мы использовали этот подход при запуске турецкой версии Маркета. Эксперты по тестированию написали список необходимых кейсов и какие проверки делать на каких страницах. Мы краулером отобрали много страниц сервиса и разделили их на группы — страницы результатов поиска, страница категории и так далее. Дальше для каждой группы страниц автоматически построили вышеописанные правила и вручную проверили, какие из указанных проверок действительно осуществляются. Оказалось, что около 90% проверок сгенерилось автоматически. При этом ожидаемые трудозатраты на написание автотестов были около трех человеконедель, а нашим инструментом все получилось сделать и настроить за один день.
Конечно, это не означает, что теперь любые тесты могут быть сформированы во много раз быстрее. Например, наш инструмент пока умеет автоматически создавать только статичные тесты (без динамических операций с элементами страницы).
Сейчас мы заняты внедрением МТ на различных сервисах Яндекса, чтобы как раз и получить точный ответ на вопрос, какую часть человеческой работы выполняет данный инструмент. Но уже очевидно, что совсем немалую.
Как я и говорил, проекты Роботестер и Magic Tester — экспериментальные и делаются в исследовательском подразделении отдела тестирования. Если вы старшекурсник и вам интересно попробовать себя в наших задачах, приходите к нам на стажировку.
Наша основная цель — изобрести принципиально новые подходы для нахождения ошибок в Яндексе. Я очень люблю порассуждать на тему того, какая часть работы в будущем ляжет на плечи роботов. Они уже отлично пишут спортивные репортажи и переносят грузы для солдат. И вообще мне кажется, что человеческий прогресс непосредственно зависит от того объема работы, который мы сможем передать роботам — у людей в этом случае появляется свободное время и они придумывают новые крутые штуки.
Есть такой тезис, сторонником которого я лично являюсь, — любую ошибку, которую может заметить неподготовленный пользователь, может обнаружить и робот. Именно это мы и попытались проверить. Но тут возникает вопрос: что именно человек считает ошибкой?
Искусственный интеллект пока никто не изобрёл (хотя Хокинг, например, считает, что это к лучшему), но кое-каких успехов нам удалось добиться. В этом посте я расскажу о том, как мы формулировали опыт, которым обладают тестировщики-люди и постарались научить ему наших роботов, и что из этого вышло.
Роботестер. Первый подход
Когда мы создавали Роботестера, перед нами стояла задача автоматизировать рутинную работу, на которую уходит время тестировщика. Мы научили алгоритм открывать веб-страницу, понимать, какие действия можно произвести с элементами, заполнять текстовые поля, нажимать кнопки и пытаться угадать, когда же произошла ошибка. Но у нас возникла проблема — оказалось, что с высокой достоверностью робот может обнаружить только самые тривиальные ошибки.
Дело в том, что принцип работы робота — проверять как можно больше страниц — приводил к большому числу тестов, а это означало, что точность определения ошибки становилась ключевым фактором. Мы подсчитали, что для проверки Яндекс.Маркета наш робот делал 800 000 различных проверок в сутки. Соответственно, если false positive rate проверок в среднем равен 0.001 (что кажется небольшим числом), то каждый день будет приходить отчет о якобы найденных 800 ошибках, которых на самом деле нет. Естественно, это никого не устраивает.
Следует отметить, что «фальшивые» сообщения об ошибках всегда случаются. Особенно, когда речь идет о веб-тестах, так как для них используется вспомогательные инструменты — могут быть проблемы с браузером, который использует робот, проблемы с интернетом, и так далее.
Есть весьма «чистые» проверки. Например, код ответа ссылки 404 с огромной вероятностью свидетельствует о том, что проблема есть. Пример проверки с низкой точностью — наличие в тексте буквосочетания « ,» (пробел и запятая). Действительно, когда между пробелом и запятой не подгрузились какие-то данные, такое буквосочетание свидетельствует об ошибках. Но иногда речь идет просто об опечатках. Особенно когда в область проверки попадает текст пользовательских комментариев или контенет из внешних источников. Поэтому для нахождения этих ошибок приходится проводить работу вручную, отделяя «настоящие» проблемы от «фальшивых».
В итоге, робот действительно полностью брал на себя часть работы тестировщиков (например, находил все битые ссылки), но совсем не всю. И мы задумались о том, как «добавить роботу интеллекта».
Как робот догадается об ошибке?
Традиционно в тестировании запускают тестируемую программу с какими-то заданными входными данными и сравнивают результаты с каким-то также наперед заданным «правильным» результатом. Он может быть задан вручную, или, скажем, сохраняться при запуске предыдущей версии программы (тогда мы сможем найти все различия между данной версией и предыдущей), но общий принцип все равно остается таким. По сути подход в целом здесь не меняется десятки лет, меняются только инструменты для реализации этих тестов.
Однако оказывается, что возможны принципиально иные подходы для определения того, что является ошибкой.
Мы изначально говорили о том, что робот должен научиться определять ошибки, которые может любой человек, необязательно профессиональный тестировщик данного сервиса.
Итак, где ошибка на этой странице?
Конечно, правильный ответ — среди пяти предложений снизу есть повторяющиеся. Чтобы понять, что это ошибка, не надо быть экспертом в Маркете — надо просто обладать минимальным здравым смыслом.
Другой пример.
Здесь в одном месте написано «нет в продаже», а в другом — указаны цены. Опять же абсолютно любой человек понимает, что это некорректная ситуация.
Еще один пример.
Это просто чистая страница. То есть у нее есть стандартные «шапка» и «футер», но нет никакого контента в середине.
Здесь и возникает ключевой вопрос — как человек понимает, что это ошибка? На каком механизме это основано?
Мы долго думали, и кажется, что ключевое слово здесь — опыт. То есть человек уже видел в своей жизни много веб-страниц, причем некоторые были ровно такого же типа. И именно из них у него сформировался некоторый шаблон. Этот шаблон может быть как очень общим («страница не должна быть пустой», «все результаты поиска должны быть различны»), или, наоборот, привязанным к данным страницам («два выделенных блока содержат или не содержат цифры одновременно»). То есть у него в голове уже сформировались эти правила и, как мы видим по данным примерам, они выглядят совсем несложными.
Таким образом, дальнейшая задача тут стала ясна — надо научиться автоматически извлекать эти правила, анализируя множество схожих или не очень схожих веб-страниц.
Видно, что сформулированные правила довольно просты, и, если бы мы научились их автоматически извлекать, то можно было бы формировать автотесты без участия человека. Например, роботу дается для анализа много страниц сервисов Яндекса, и он понимает, что на них на всех снизу есть ссылка «О компании». Соответственно этот факт формулируется как правило, и робот будет проверять его выполнение для новой версии сервиса или даже для другого сервиса.
Самое просто применение этой идеи такое: анализируем все страницы сервиса в продакшн, вычленяем такие «правила», а затем проверяем, выполняются ли они для новой версии того же сервиса.
Этот подход давным-давно всем известен. Он называется back-to-back тестирование и есть те, кто его использует. Однако такой метод хорошо применим лишь тогда, когда работа сервиса не должна заметно меняться от версии.
Давайте рассмотрим поисковую выдачу вчера и сегодня — результаты поиска и реклама рядом меняются. Онии зависят от региона пользователя, его предпочтений, времени суток, наконец. Соответственно, при непосредственном сравнении будет слишком много «мусора» (отметим, что в некоторых ситуациях и такой непосредственный метод допустим).
Здесь же мы развиваем нашу идею и осуществляем сравнение, «очищенное» от мусора, — мы сравниваем не сами страницы, а некоторые «модели» страниц.
Блоки
Сформулировав общую идею, перейдем к тому, как же ее реализовывать. Наша задача — автоматически извлекать правила. Для понимания человеком они очень простые. Мы их формулируем на языке «блоков» — мы говорим о том, содержит определенная часть страницы какой-то элемент или нет, присутствует ли на странице определенный блок, и так далее. Для человека страница делится на них естественным образом — вот форма авторизации, вот поисковая форма (и в ней подблоки — строка поиска, кнопка «найти»). Однако робот «видит» перед собой html-код, и ему совершенно непонятно, какая часть этого кода образует блок.
Мы решили четко сформулировать понятие блока. То есть сначала мы решили понять для себя, что же мы, люди, называем блоком. Давайте посмотрим, какие бывают блоки.
1. Постоянные. Весь блок целиком присутствует на каждой странице).
2. Меняющиеся. Какой-то тэг присутствует на каждой странице, но внутри него каждый раз все меняется.
3. Однотипные блоки на одной странице.
4. Однотипные, но разные по сути блоки на одной странице.
При этом на разных страницах один и тот же блок может стоять на разных местах.
То есть для нас «блок» — это некая часть страницы, которая при её изменении остается более-менее постоянной. Например, человек легко понимает, что формы из пункта 2 (см. выше) — это частные случаи «одной и той же оранжевой формы», но при этом содержание формы меняется.
Отдельную проблему представляют собой несколько схожих блоков, идущих подряд. Иногда это именно «несколько однотипных блоков», а иногда — набор объектов разных типов, и тогда хочется понять, какого типа объекты вообще там встречаются.
В первую очередь нам нужен какой-то способ помечать уже выделенный блок на каждой странице. Традиционный xpath (например,
/html/body/div[1]/table[2]/tbody/tr/td[2]/div[2]/ul/li[3]/span/a) плохо подходит потому, что числа в нем могут меняться — один и тот же блок может быть третьим или пятым по счету. В зависимости от того, какие еще блоки есть (см. последние два примера).Поэтому мы сначала убираем числа из xpath'а (получая
/html/body/div/table/tbody/tr/td/div/ul/li/span/a вместо /html/body/div[1]/table[2]/tbody/tr/td[2]/div[2]/ul/li[3]/span/a) и получаем намного более стабильный вариант соответствия (то есть данный блок будет подпадать под xpath на любой странице), однако менее точный — то есть одному и тому же xpath'у теперь, конечно, может соответствовать несколько элементов. Для уменьшения этой неточности мы в описание каждого tag'а добавляем значения некоторых его атрибутов. Атрибуты мы просто руками разделили на более и менее стабильные. Например, атрибут id часто генерится заново при загрузке страницы, то есть он для нас совершенно неинформативен. Например, для блока, рассмотренного сверху, получилось такое описание: другой ipath<body>
<div class="b-max-width">
<table class="l-head">
<tbody>
<tr>
<td class="l-headc">
<div class="b-head-search" onclick="return {name:'b-head-search'}">
<div class="b-head-searchwrap b-head-searcharrow">
<form class="b-search">
<table class="b-searchtable">
<tbody>
<tr>
<td class="b-searchinput">
<span class="b-form-input b-form-input_is-bem_yes b-form-input_size_16 i-bem" onclick="return {'b-form-input':{name:'b-form-input'}}">
<span class="b-form-inputbox">
<text src="Тип процессора Turion II">
Теперь давайте искать блоки. Если представлять html-код как дерево, то наша задача — искать стабильные пути из корневой вершины (стабильность здесь означает, что путь мало меняется при изменении страницы). Алгоритм построения множества таких стабильных путей — это основная часть нашего инструмента. Строили мы его «методом проб и ошибок». То есть мы модифицировали алгоритм и смотрели на результат. Алгоритм я опишу ниже, а пока расскажу о совершенно неожиданной проблеме — мы внезапно поняли, что не знаем, как изображать, какие блоки выделились на странице.
Действительно — блок выглядит по-разному на разных страницах. Нам хотелось получать отчет в виде чего-то, похожего на страницу, разбитую на блоки. Но какой из вариантов блока брать? Мы раз за разом натыкались на случаи, когда к нам в отчет попадал пустой или малоинформативный вариант. Нужно было как-то компактно показать все варианты на одной и той же странице. Одному из разработчиков пришла в голову удачная идея — сделать как, например, сделано
В итоге «модель страницы» выглядит примерно так (см. ниже). Можно посмотреть на нее и сразу понять, какие блоки выделились.
Алгоритм выделения блоков
Теперь насчет алгоритма. Базовый алгоритм выглядит следующим образом:
- Выбираем одну страницу из набора.
- Собираем с первой страницы все максимальные пути из корневой вершины в другие.
- Затем для каждого отобранного пути пытаемся проложить его на всех страницах.
Если получилось проложить часть пути, отличающуюся по длине хотя бы на 4, добавляем в множество путей эту самую часть.
Если почти получилось проложить весь путь (не дошли на 1-3 тега), то заменяем путь в наборе на этот обрубленный вариант. - В результате полученные пути и соответствуют блокам. Дальше из них легко выбрать те, которые есть на всех страницах, или, скажем, на 95% страниц.
Большим достоинством алгоритма является то, что он линейно зависит как от числа элементов первой страницы, так и от количества страниц.
Однако как мы скоро выяснили, есть места, где алгоритм срабатывает плохо. Например, вот для этих блоков (isbn, автор и так далее):
Как html-элементы они совершенно одинаковы, отличаются только порядковым номером. Но сразу же ясно, что этот номер ничего не означает — на примере выше ISBN то второй, то первый. Поэтому нам стало ясно, что единственный способ отличать такие элементы — по тексту внутри. Поэтому мы изменили алгоритм следующим образом: в самом начале ищем места, где у элемента есть несколько потомков, отличающихся только текстом. Тогда мы собираем схожие элементы потомков со всех страниц, а затем кластеризуем их по тексту так, чтобы на каждой странице было не более одного представителя каждого кластера.
Были и другие улучшения алгоритма, но они могут быть вам не так интересны, так как связаны с яндексовой спецификой. Даже описанный сейчас алгоритм достаточно хорошо сработает на большинстве наборов страниц.
Генерация правил
Итак, проанализировав структуру страниц из обучающей выборки, выделив блоки и поняв, какие блоки на скольких страницах присутствуют, можно формулировать правила следующих типов:
- Блок А обязательно должен присутствовать на странице.
- Блоки А и Б должны присутствовать одновременно.
- Блоки А и Б не могут присутствовать одновременно.
Можно в принципе извлекать и более сложные закономерности, но мы этим пока не занимались.
Для каких же блоков мы формируем условие первого типа? Для тех, которые встречаются на достаточно большой доле страниц. Определяется эта доля специальным параметром, который мы называем confidence level. Неправильно устанавливать этот параметр равным единице — так, как мы хотели делать изначально, по двум причинам:
- Одна из 100 страниц обучающей выборки может не открыться (по таймауту, например), и в результате ни одного условия об обязательном наличии блока не выделится.
- Среди страниц обучающей выборки случайно могут встретиться страницы с ошибками.
Мы этот уровень значимости варьируем в зависимости от стабильности среды, на которой мы обучаем наш инструмент. Уменьшая значение параметра, можно «убирать» эффект нестабильности среды. Однако если сильно уменьшить этот параметр, то инструмент начнет выделять дополнительные неправильные закономерности. Например, если у 96% товаров есть цена, а у 4% написано «нет в продаже», то при установке параметра в 0.95 страницы с «нет в продаже» будут помечены как ошибочные. По дефолту confidence level равен 0.997.
Помимо условий на наличие/отсутствие блоков мы автоматически генерим условия на текст внутри каждого блока. Условия формируются в виде регулярных выражений. Например, на блок с годом издания на такой странице
будет следующая регулярка:
Год издания: [0-9]{4}
Или даже такая:
Год издания: (19|20)[0-9]{2}
При этом сам этот блок помечен как необязательный. То есть проверяется следующее — что если такой блок есть, то в нем после слов «год издания» написано 4 цифры или даже, что написаны 4 цифры, первые две из которых 19 или 20. Примерно такой тест написал бы и человек.
Магия на практике
Если резюмировать, наш инструмент умеет следующее: по набору страниц мы извлекаем правила определенного типа, которые выполняются для заданного процента этих самых страниц. Как же с помощью этого искать баги? Есть два пути.
- Считать, что поведение, встречающееся достаточно редко, — ошибка. Это спорный тезис, однако много раз удавалось найти функциональные баги именно таким путем. Тогда достаточно проанализировать большое количество страниц на сервисе и отметить те, которые не похожи на остальные. В любом случае этот путь не подойдет, если, условно говоря, «все сломалось». Поэтому обычно мы используем другой подход.
- Собирать страницы из версии N сервиса (обычно просто из production), строить по ним правила. Затем брать много страниц из версии N+1 сервиса (обычно это просто testing) и проверять на них выполнение этих правил. Получается понятный список всех отличий версий N и N+1.
Фактически во втором случае мы получаем то же самое, что и при наличии регрессионных автотестов. Однако в нашем случае есть большое, даже огромное достоинство, — код этих тестов не надо писать и поддерживать! Как только выложили новую версию сервиса, я нажимаю кнопку «перестроить все» и через несколько минут готова новая версия «автотестов».
В качестве эксперимента по внедрению мы использовали этот подход при запуске турецкой версии Маркета. Эксперты по тестированию написали список необходимых кейсов и какие проверки делать на каких страницах. Мы краулером отобрали много страниц сервиса и разделили их на группы — страницы результатов поиска, страница категории и так далее. Дальше для каждой группы страниц автоматически построили вышеописанные правила и вручную проверили, какие из указанных проверок действительно осуществляются. Оказалось, что около 90% проверок сгенерилось автоматически. При этом ожидаемые трудозатраты на написание автотестов были около трех человеконедель, а нашим инструментом все получилось сделать и настроить за один день.
Конечно, это не означает, что теперь любые тесты могут быть сформированы во много раз быстрее. Например, наш инструмент пока умеет автоматически создавать только статичные тесты (без динамических операций с элементами страницы).
Сейчас мы заняты внедрением МТ на различных сервисах Яндекса, чтобы как раз и получить точный ответ на вопрос, какую часть человеческой работы выполняет данный инструмент. Но уже очевидно, что совсем немалую.
Как я и говорил, проекты Роботестер и Magic Tester — экспериментальные и делаются в исследовательском подразделении отдела тестирования. Если вы старшекурсник и вам интересно попробовать себя в наших задачах, приходите к нам на стажировку.
