Ещё о тестировании в Яндексе роботами

С точки зрения тестирования, Яндекс — это тысячи человеко-часов работы по проверке большого количества сервисов. Функциональности много, сценариев взаимодействия — миллионы. Мы стараемся сделать так, чтобы люди занимались только сложными и интересными задачами, а всю рутинную работу можно было бы поручить роботу.

В идеале именно робот должен проверять, что в результате простой загрузки страницы или сложного взаимодействия с формой ввода не возникает никаких вылетающих наружу исключений, “NaN”, “undefined” или пустых строк на месте подгружаемых данных. Экспериментальный проект по созданию и внедрению такого робота имеет кодовое название “Роботестер”.

Мы уже рассказывали, как реализовали его и научили работать с формами. Сегодня речь пойдёт о том, как наш робот старается найти максимальный объем функциональности сервиса, а затем и «понять» его.

Когда-то каждый сайт представлял собой статическую страницу, контент которой формировался с помощью одного запроса к серверу. Сейчас же многие сайты можно отнести к категории Rich Internet Applications (RIA): они стали намного интерактивнее и их содержимое меняется в зависимости от поведения пользователя на странице. Веб-приложения отличаются от традиционных сайтов использованием таких технологий, как Javascript и AJAX, которые позволяют значительно менять вид и содержимое приложения без изменения адреса в браузере.

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

В самом общем виде можно представлять себе сайт в виде графа состояний и искать подходы, как посетить все вершины в графе или хотя бы их максимальное количество. Но в таком виде задача является малоосмысленной — даже у простого сервиса Яндекса количество состояний настолько велико, что можно считать его бесконечным. Например, ввод каждого нового запроса в поисковое поле и нажатие кнопки «найти» ведет нас на новое состояние. То есть их как минимум столько же, сколько можно ввести различных поисковых запросов. Поэтому мы используем стандартный для тестирования подход, когда состояния делятся на сравнительно небольшое число классов. Например, множество страниц с результатами поиска разумно будет разделить на такие группы: отсутствие результатов, небольшое количество результатов, несколько страниц результатов. Все классы должны быть заданы каким-либо отношением эквивалентности, после чего мы пытаемся проверить как минимум по одному представителю данного класса. Но как научить этому Роботестер?

Мы поступили следующим образом. Все-таки разделили задачу на две части: «краулером страниц» мы обходим сайт по ссылкам, отбирая определеннное количество страниц, а затем на каждой из отобранных страниц запускаем «краулер форм», который по алгоритму, описанному нами ниже, изменяет страницу и останавливается только перейдя на новую. Так мы поступили потому, что у этих двух краулеров несколько разные задачи: если максимальная «глубина» переходов по ссылкам редко бывает больше 5-6, то чтобы перейти к новой странице с помощью форм, иногда надо совершить сотню-другую действий. В качестве примера вы можете посмотреть на форму создания кампании в Яндекс.Директе, которую вы увидите после авторизации. Поэтому разумно использовать разные алгоритмы обхода.

Конечно, бывают как устаревшие сайты, где почти нет разумных элементов (там фактически сработает только первый краулер), так и, наоборот, современные RIA, где url страницы может вообще не меняться (тогда будет работать только второй краулер). Тем не менее, у нас получилась довольно гибкая система, которую легко настроить практически для любого сервиса.

Как устроен краулер страниц

Итак, первая наша задача — отобрать те страницы, на которых будет запускаться краулер форм. Как получить набор этих «входных точек»? Сначала мы вообще решили, что его можно составлять вручную. Приведем в качестве примера небольшой список страниц:

• market.yandex.ru/catalogmodels.xml?CAT_ID=160043&hid=91491 — мобильные телефоны, поиск по параметрам;
• market.yandex.ru/guru.xml?CMD=-RR=9,0,0,0-VIS=70-CAT_ID=160043-EXC=1-PG=10&hid=91491 — мобильные телефоны, расширенный поиск;
• market.yandex.ru/model.xml?modelid=8478341&hid=91491 — страница товара;
• market.yandex.ru/product/8478341/reviews/add?retpath=http://market.yandex.ru/product/8478341/reviews — форма, в которой нужно оставлять отзыв.

Как видно, адрес страницы содержит большое число параметров. Если какой-либо из параметров изменяется, ссылка становится некорректной. Кроме того, появляются новые классы страниц, а некоторые из них — устаревают. Поэтому нам стало ясно, что надо уметь динамически составлять и поддерживать список страниц, которые необходимо протестировать.

Предположим, граф страниц нашего сайта имеет вид, представленный на рисунке:

Пусть каждое ребро графа — это переход по ссылке. Такой инструмент, как CrawlJax, начинает идти с одной вершины всеми возможными путями. Этот способ обхода сайта может работать очень долго. Мы же решили, что будем действовать по-другому: отберем “точки входа” в графе (зеленые вершины на рисунке) таким образом, чтобы в идеале набор зеленых вершин стал 1-сетью. Как правило, в этом случае точки входа — это страницы с формами, а доступные на расстоянии 1 страницы — это результат поиска. Таким образом, для тестирования сайта нам достаточно найти точки входа, выполнить на них различные действия и проверить на ошибки страницы, на которые мы перешли. Стоит отметить, что большинство страниц 1-окрестности какой-либо точки входа идентичны по функциональности, поэтому тестировать можно не всех представителей такой окрестности.

Итак, чтобы протестировать сайт, робот должен иметь список некоторых его страниц.

Веб-краулер — достаточно стандартная и очень широко освещенная задача. В классической интерпретации краулеру требуется найти как можно больше страниц. Чем больше страниц, тем больше индекс, тем качественнее поиск. В контексте нашей задачи, к краулеру такие требования:

• Должна быть возможность осуществлять краулинг за разумное время.
• Краулер должен отбирать как можно более отличающиеся по структуре страницы.
• Количество страниц, которые нужно тестировать, на выходе должно быть ограничено.
• Краулер должен собирать со страницы даже те ссылки, которые загружаются динамически (изначально не содержатся в коде страницы).
• Должна быть возможность поддерживать авторизацию, регионозависимость и другие настройки сервисов Яндекса.

Требование №1: время
Бывает необходимо контролировать длительность процесса тестирования. Допустим, необходимо выкатить релиз и хочется быстро проверить основную функциональность. Длительность краулинга можно поставить в некоторые рамки при помощи ограничения на глубину и количество посещенных страниц.

Требование №2: покрытие
Второе требование вытекает из необходимости покрыть тестами как можно большую функциональность за как можно меньшее время. Очевидно, что на контент-сервисе есть классы экивалентных (по функциональности) страниц. Кластеризовать такие страницы можно, ориентируясь на URL страницы и ее html-код. Мы разработали способ, позволяющий быстро и достаточно качественно разделять такие страницы на кластеры.

Мы используем два типа расстояний между страницами:

• UrlDistance отвечает за различие урлов. Если длина двух урлов одинаковая, то расстояние между урлами обратно пропорционально количеству совпавших символов. Если длина разная, то расстояние пропорционально разности длин.
• TagDistance отвечает за различие html-кода страниц. Расстояние между двумя DOM-деревьями — разность количества одноименных тегов.

Стоит обратить внимание, что реализация второго требования должна быть согласована с первым требованием. Допустим, нам нужно отобрать страницы для тестирования сайта Яндекс.Маркет. Предположим, с каждой страницы ведет N ссылок и нас интересует глубина краулинга K. Чтобы сравнить все страницы, нам придется загрузить html-код О(N^K) страниц. На это может уйти немало времени, учитывая, что ссылок, ведущих с каждой страницы контентного сайта, может быть 20-30. Такой способ нам не подходит. Будем фильтровать страницы не в самом конце, а на каждом шаге.

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

• Первый этап фильтрации: сравниваем урлы по UrlDistance, оставляя L наиболее отличающихся.
• Второй этап фильтрации: загружаем html-код L наиболее отличающихся по метрике UrlDistance страниц и сраниваем их при помощи TagDistance.

Таким образом, нам нужно загрузить код только для O(L·K) страниц. При всех данных упрощениях процесса фильтрации страниц, качество получающихся «точек входа» нас устраивает!

Требование №3: количество тестируемых страниц
Реализация третьего требования позволит нам ограничивать количество страниц, на которых будут проведены тесты. Грубо говоря, мы говорим роботу «отбери N самых отличающихся по функциональности страниц и протестируй их».

Требование №4: учитывать динамически загружаемый контент
Собрать ссылки даже с блоков, загружаемых динамически, и переходить только по визуально доступным ссылкам (моделирование поведения человека) позволяет WebDriver.

Требование №5: контекст
Чтобы учитывать контекст вроде региона или прав пользователя (различная выдача, различный функционал), краулер должен уметь работать с куками. Например, вы знали, что даже главная страница Яндекса в разных регионах может быть различной?

Итак, мы выполнили все указанные требования и получили возможность быстро и эффективно находить как можно больший объем функциональности сайта. Робот нашел «точки входа». Теперь необходимо посетить 1-окрестность, или, проще говоря, провзоимодействовать с формой.

Краулер форм

Чтобы протестировать функционал сайта, нужно уметь им воспользоваться. Если начать бездумно кликать на всё подряд и вводить любые значения в текстовые поля ввода (как вводить не любые) то качественно протестировать форму за разумное время не получится. Например, с такими формами на Яндекс.Директе, как на рисунке ниже, взаимодействовать достаточно сложно.

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

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

Простой случай. Полей ввода фиксированное количество, и они не изменяются, то есть не зависят друг от друга. Данная задача достаточно популярна и широко освещена. Мы, например, используем программу с красивым названием Jenny.

Она принимает на вход желаемую глубину покрытия и набор чисел, отвечающих за количество вариантов в каждом поле ввода. Рассмотрим пример небольшой формы. Допустим, нас интересует покрытие степени 2 для формы из трех полей ввода, каждое из которых имеет два варианта. Инструкция по заполнению будет выглядеть так:

Число — это номер поля ввода, буква — номер варианта, который нужно выбрать. Покрытие степени N означает, что если зафиксировать любые N столбцов, то в них встретятся все возможные комбинации.

Сложный случай. Форма динамическая и количество полей ввода изменяется. Например, по результату заполнения первых трех полей появляется четвертое и пятое поле ввода, либо сразу же появляется кнопка «отправить». В качестве модели такой формы подходит «граф состояний». Каждая вершина графа — это состояние формы. Оно может измениться за счет удаления поля ввода из формы, изменения значения поля ввода или добавления нового.
Мы сформулировали несколько некритичных для нас допущений, при которых должен работать алгоритм:

• Удаляются поля ввода достаточно редко, поэтому такой случай мы не рассматриваем.
• Если при заполении поля A изменилось поле B, то нужно произвести топологическую сортировку полей ввода, получив порядок, при котором мы сначала будем заполнять А, а потом — B, если B зависит от А. На практике мы считаем, что вышестоящие (имеено по физическому расположению на странице) элементы не зависят от нижестоящих.
• Если в результате взаимодействия появилось новое поле ввода, то мы считаем, что оно зависит только от одного из предыдущих полей ввода. В действительности это не так, однако это допущение существенно упрощает задачу.

Переход в другую вершину осуществляется посредством изменения состояния одного поля ввода.

Допустим, изначально форма состоит из элементов A₁…A_n. Для каждого A_i выполним:

• Пробуем повзаимодействовать с A_i всеми возможными способами. Пусть этих способов k штук.
• Зафиксируем те элементы B_i1…B_ik, которые появлялись при различных заполнениях Ai.
• Рекурсивно повторить процедуру для каждого из B_ij.

При таком подходе алгоритм может работать очень долго, поскольку количество способов взаимодействия будет расти экспоненциально от числа элементов. Для того чтобы краулинг формы мог закончился в обозримом будущем, перебор всех возможных способов взаимодействия осуществляется только для элементов, находящихся на глубине не более 2, а для всех остальных выбираем одно случайное значение. Такой подход необходим для тестирования форм, у которых необходимо заполнение некоторого количества обязательных полей.

Алгоритм

Допустим, изначально форма состоит из элементов A₁…A_n. Для каждого A_i выполним:

1. Пробуем повзаимодействовать с Ai всеми возможными способами. Пусть этих способов k штук.
2. Зафиксируем те элементы Bi1…Bik, которые появлялись при различных заполнениях Ai.
3. Для каждого элемента Bij, пока не дойдем до конца заполнения формы, выполним:
3.1. Провзаимодейтсвуем с элементом Bij всеми возможными способами.
3.2. С каждым элементом, который становится доступен при заполнении Bij, взаимодействуем единственным случайным образом.

Оптимальное покрытие генерируется из расчета, что А_i — выпадающий список, у которого вариантов столько, сколько из него путей до уровня 3.

Приведем конкретный пример.

Из вершины A₁ пять путей до уровня 3, из вершины A₂ — четыре и из вершины A₃ тоже четыре. Соответственно, можно представить А₁ как выпадающий список с пятью полями, а А₂ и А₃ — с четырьмя. Следовательно запускать Jenny робот будет с аргументами «5 4 4».

Мы научили робота находить функционал сервиса и бездумно (относительно человека) пользоваться им. Конечно, не стоит ожидать, что в ближайшее время он зарегистрируется в Яндекс.Директе, самостоятельно создаст рекламную компанию для себя любимого и прославится на весь мир, хотя он уже умеет создавать проекты на внутреннем сервисе (правда они, как ни странно, пока не выстрелили :)). Однако мы от него этого и не ждем! Он заполняет формы грамотно и до конца. Мы ждем от него качественного тестирования веб-интерфейсов, и эти наши ожидания он оправдывает.