1. Предпосылки

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

1.1 Введение в автоматическую генерацию тестов

Технология автоматической генерации тестов (Automated Testing Generation), также называемая технологией AIG (Automated Input Generation). Традиционные методы автоматизации, такие как Record & Replay, полагаются на тестировщиков, которые пишут тестовые сценарии. В то же время по мере изменения требований к тестированию тестировщикам необходимо тратить определенное количество времени на поддержку и корректировку соответствующих тестовых сценариев. По сравнению с методом записи и воспроизведения, абстрагирование общих служб, от которых зависят действия тестирования, и использование автоматического способа генерации операций, требуемых действиями тестирования, может значительно снизить рабочую нагрузку по написанию и обслуживанию сценариев тестирования.

В настоящее время типичными технологиями ATG являются:

• Анализ программы (Code-Based Testing);
• Генерация тестов на основе моделей(модельно-ориентированное тестирование);
• Комбинаторное тестирование;
• Генерация тестов на основе поиска(тестирование на основе поиска), Sapienz в Facebook;
• Адаптивное случайное тестирование;

Рисунок 1. Введение в технологию ATG

Их основная логика сосредоточена на том, «как генерировать» тестовую логику. Взяв в качестве примера MBT, страницу в процессе тестирования графического интерфейса (тестирование клиента) можно определить как состояние.Используя дерево графического интерфейса, соответствующее странице, мы можем извлечь более значимые операции, например, из состояния1 в состояние3 можно попасть через событие3 , а состояние1 может быть достигнуто из состояния2 через событие2. Таким образом, задача, порожденная тестом, трансформируется в задачу обхода ориентированного графа. Инструменты случайного тестирования, такие как Monkey, часто беспокоят разработчиков из-за отсутствия высокоуровневого представления Log:

(1) тестовую последовательность, сгенерированную Monkey, непросто описать вариантами использования в виде документов;

(2) Ошибка воспроизведена с трудом, и отсутствуют подробные шаги для воспроизведения.

1.2 Инструменты автоматизированного тестирования

Технология ATG для приложений в основном включает две категории.

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

Во-вторых, мы также можем выполнять тестирование методом «черного ящика» на основе информации о графическом интерфейсе приложения. Этот тип теста не требует получения исходного кода приложения. Нам нужно только отслеживать информацию о пользовательском интерфейсе страницы мобильного телефона в процессе тестирования и выполнять внедрение действий для обеспечения непрерывного интерактивного тестирования. Инструмент Fastbot, описанный в этой статье, использует этот подход.

Другие популярные инструменты автоматизированного тестирования «черного ящика» включают: Sapienz от Facebook, который использует генетические алгоритмы и подход на основе поиска для создания тестовых случаев; Dynodroid от Georgia Tech, который рассматривает приложение как серию исполняемых действий и генерирует тестовые последовательности по очереди. ; и упомянутый выше инструмент случайного тестирования Monkey, поставляемый с Android. Кроме того, инструменты Droidbot и Humanoid, разработанные Пекинским университетом, также используют тестирование графического интерфейса на основе моделей, в котором Humanoid имитируется на основе поведения пользователя, а Droidbot абстрагирует страницы и действия в графические модели и использует традиционные алгоритмы DFS и BFS для построения графиков. , обход для достижения высокого охвата.

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

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

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

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

В этой статье основное внимание будет уделено интеллектуальной системе тестирования, разработанной ByteDance: Fastbot, которая представляет собой набор интеллектуальных сервисов тестирования графического интерфейса на основе моделей (MBT). Мы трансформируем тестовую задачу в задачу поиска обхода приложения и построения модели ориентированного графа. В то же время клиентская и серверная стороны разделены для реализации совместного выполнения тестовых задач графического интерфейса несколькими машинами на большом количестве устройств. Выполняйте мониторинг информации графического интерфейса и отчетность, а также ввод действий на стороне клиента, построение модели и принятие решений о действиях на стороне сервера, а также разрабатывайте несколько наборов алгоритмов, которые соответствуют направленному обходу направленного графа на основе формулы UCB, избегая ситуации локального бесконечные циклы, значительно увеличивающие возможности покрытия и эффективность тестирования.

2. Принцип конструкции Fastbot

2.1 Рабочий процесс Fastbot

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

Рисунок 2. Рабочий процесс Fastbot

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

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

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

2.2 Введение в модель Fastbot

Как упоминалось выше, мы абстрагируем информацию GUI страницы в состояние в модели и абстрагируем выполняемое действие в действие в модели, используя состояние в качестве узла графа и действие в качестве края графа. , соединение образует модель ориентированного кольцевого графа. На рис. 3 показан частичный пример направленного ориентированного графа, где пунктирные стрелки обозначают действия, соединяющие узлы.

Рисунок 3. Частичный пример ориентированного ориентированного графа

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

Рисунок 4. Общий пример модели ориентированного циклического графа

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

3. Введение в Fastbot AI-Core

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

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

Чтобы добиться более эффективного исследования обхода, мы используем различные эвристические алгоритмы обхода в ядре Fastbot AI, и в следующем разделе будут представлены три репрезентативных алгоритма.

3.1 Одношаговый или N-шаговый алгоритм UCB

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

В модели Fastbot приоритету государства отдается более сложная формула расчета. Для каждого действия мы сначала определяем базовый приоритет в соответствии с его типом действия, а затем добавляем приоритет доступа в зависимости от того, было ли оно посещено и насыщено ли оно.Сумма двух составляет приоритет действия. Исходя из этого, приоритет состояния исходит из накопления приоритетов всех исполняемых действий под страницей.

Формула 1 представляет собой одношаговую формулу UCB, в которой левый элемент является элементом приоритета, а правый элемент — элементом счетчика доступа. Эти два элемента складываются вместе для получения комбинированного значения UCB, которое используется в качестве критерия выбора для Действие. Рисунок 5 иллюстрирует легенду для формулы 1. Под текущим узлом Sc для посещенного Действия: A1-A3 мы знаем его целевой узел, и формула 1 используется для вычисления значения UCB Действия, Для других непосещенных Действия мы не знаете, что такое целевой узел, тогда примите приоритет самого действия в качестве результата UCB, обычно приоритет самого действия выше, чем значение UCB после нескольких посещений, поэтому мы все равно будем отдавать приоритет непосещенным действиям. .

Рисунок 5. Пример схемы одношагового алгоритма UCB

Одношаговый алгоритм UCB менее трудоемкий, а после введения статьи баланса количество посещений хорошо предотвращается возникновение локальных петель и более децентрализовано принятие решений о действиях. Недостатком этого алгоритма является то, что он рассматривает только оптимальные действия UCB в пределах текущего шага, а если учитывать все исполняемые действия в пределах N шагов, то результаты выбора могут быть разными. С этой целью мы также вводим N-шаговый алгоритм UCB, который проходит текущее действие и все выполняемые действия в пределах N-1 шагов после действия, умножает приоритет всех действий на коэффициент затухания и накапливает конечный результат. текущее значение UCB для действия. Формула N-шагового алгоритма UCB задается уравнением 2:

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

3.2 Алгоритм MTree

Однако, будь то одношаговый алгоритм UCB или N-шаговый алгоритм UCB, используется только информация в пределах одного шага или N шагов, а не информация обо всей модели. Обратное распространение на модели не может пройти гладко из-за существования циклов. Мы надеемся достичь глобального направленного распространения и передать информацию о недавно посещенной странице на всем пути к начальному узлу. При переопределении нового действия мы хотим, чтобы каждый узел на пути обновлялся. Поэтому мы рассматриваем возможность адаптации модели ориентированного ориентированного графа к древовидной структуре, чтобы избежать помех, вызванных петлями. Узел дерева представляет состояние в модели.В узле мы сохраняем действие предыдущего шага, записываем состояние предыдущего шага в качестве родительского узла и записываем состояние, которое может быть достигнуто на следующем шаге, как дочерний узел. Приоритет каждого дочернего узла после использования алгоритма MTree определяется уравнением 3:

3.3 Алгоритм NStepQ

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

4. Эффект использования Fastbot

Чтобы проверить эффективность инструмента, мы сравнили Fastbot с несколькими другими аналогичными инструментами для тестирования, в том числе родным Monkey, который поставляется с Android, Droidbot, разработанным Пекинским университетом, и Humanoid, который имитирует поведение человека. В эксперименте участвовало несколько приложений, включая Toutiao, Douyin и т. д., 1 час/3 часа, одно устройство/несколько устройств и другие параметры. Производительность Fastbot значительно превосходила другие инструменты. В таблице 1 показано сравнение каждого инструмента при запуске приложения Toutiao на одном устройстве. Видно, что Fastbot показал лучшую производительность на одном устройстве, а охват Android-активности и охват кода в одно и то же время лучше, чем у других инструментов. .

Кроме того, по мере увеличения количества устройств возможности Fastbot для совместной работы на нескольких компьютерах будут приносить более значительные преимущества в производительности. В таблице 2 показано увеличение покрытия кода каждым инструментом при параллельном подключении трех устройств.Можно увидеть, что при параллельном подключении трех устройств покрытие кода Fastbot увеличивается с 19% на одном компьютере до 35%, увеличение на 84%; Напротив, улучшение Droidbot и Humanoid составляет всего 20,41% и 24,97%, когда три машины работают параллельно, а Monkey также имеет улучшение покрытия кода на 45,79%.

Благодаря мощным возможностям облачных вычислений ByteDance мы можем запустить до 500 устройств для совместной работы в одной задаче, при этом гарантируя, что сервер не вызовет проблем с OOM. В целом видно, что с увеличением количества устройств охват в единицу времени также постоянно улучшается.

Кроме того, разные алгоритмы AI-Core также будут приводить к разным эффектам обхода. На рисунке 6 показано сравнение скорости охвата Fastbot при параллельной работе 20 устройств, при этом вводится понятие Эффективность Действий, которая измеряется путем деления неповторяющихся Действий на общее количество выполненных Действий для дальнейшего наблюдать за эффектом алгоритма

Желтой линией показан алгоритм обхода в глубину, видно, что после кратковременного увеличения охвата кривая DFS практически перестает расти. Из данных об эффективности действий видно, что традиционный алгоритм DFS быстро попадает в локальный цикл и больше не запускает новые действия.

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

Затем мы сосредоточимся на четырех алгоритмах в ядре Fastbot-AI. Синие и черные линии показывают влияние одношагового алгоритма UCB и N-шагового алгоритма UCB на направленный ориентированный граф соответственно. Видно, что одношаговый УКБ имеет быстрый темп роста, а Действие эффективное, но выносливость слабая. Напротив, из-за более высокой продолжительности одношагового N-шагового UCB рост скорости покрытия на ранней стадии будет самым медленным в алгоритме AI-core, но на более позднем этапе, когда скорость покрытия одношаговой UCB имеет тенденцию к насыщению, N-шаг UCB использует его для обнаружения шагов N. Способность ценных узлов в сети может достигать более высокого верхнего предела.

Зеленая линия показывает алгоритм Q-Learning, его эффективность действия самая низкая среди четырех алгоритмов, но производительность покрытия выше, чем у одноэтапных и многоэтапных алгоритмов UCB, поскольку он улавливает характеристики State-Action, которые легко запускает новые действия, и большое количество реализует.

Красной линией показан алгоритм MTree, который обеспечивает глобальное обратное обновление путем обрезки направленного ориентированного графа в древовидную структуру Этот алгоритм обеспечивает наилучший эффект покрытия и имеет самую высокую эффективность действий.

Рисунок 6. Сравнительная таблица покрытия алгоритма

5. Резюме

В настоящее время Fastbot широко используется для тестирования стабильности и совместимости клиентских продуктов byte. Ежедневно запускалось более 300 задач, в среднем в день обнаруживалось более 5000 сбоев, при этом более 100 новых зафиксированных сбоев. Благодаря возможностям Fastbot мы можем исправить большинство сбоев до релиза, чтобы обеспечить удобство работы онлайн-пользователей. В то же время Fastbot играет важную роль основного сервиса во всем процессе DevOps. Мы считаем, что все больше и больше интеллектуальных инструментов тестирования значительно улучшат отечественную традиционную индустрию тестирования.

6. Присоединяйтесь к нам

ByteDance Quality Lab — это группа теоретических исследований инженерной эффективности и предварительных исследований технологий в составе ByteDance. Основываясь на передовой технологии искусственного интеллекта, мы предоставляем более эффективные услуги по тестированию качества программного обеспечения и инженерной эффективности за счет технологических инноваций в области машинного обучения и глубокого обучения. На пути к тому, чтобы стать лучшей в мире командой интеллектуальных инструментов, мы надеемся привнести более интеллектуальные средства в область качества.

Здесь вы можете использовать технологию НЛП, чтобы играть в интеллектуальное обслуживание клиентов, реализовать диалог между машинами и людьми и повысить эффективность работы; вы также можете использовать машинное зрение и обучение с подкреплением для создания тестовых роботов с супервозможностями и использовать их в тысячах тестов. роботов. Проверьте свой алгоритм на устройстве, вы также можете практиковать теории тестирования в различных учебниках, чтобы помочь бизнесу повысить эффективность тестирования. Комбинированное тестирование, программный анализ и точное тестирование ждут вас для изучения, вы также можете сотрудничать с лучшие институты в стране и за рубежом Обменивайтесь и сотрудничайте с учеными со всего мира, чтобы исследовать больше возможностей в области разработки программного обеспечения. Приглашаем всех проницательных людей присоединиться к нам. Электронная почта для доставки резюме:tech@bytedance.com; Тема письма: Имя - Годы работы - Лаборатория качества .