среда, 13 февраля 2013 г.

MBT Начало

Традиционный подход к автоматическим тестам выглядит примерно так - тестописатель изучает тестируемую систему и после этого руками пишет каждый отдельный сценарий для проверки искомой системы. Кто-то может написать тут гордое слово "handcrafted", а я называю это словом "handjob". А все потому, что обычно этот подход к созданию и написанию тестов страдает от двух проблем:
  • "Парадокс пестицида", описанный Борисом Бейзером в 1990-м году. Заключается он в том, что тесты все менее и менее эффективны в отлове багов, так как баги, для обнаружения которых эти тесты написаны, уже найдены и починены. Если же этого не происходит, то возникают серьезные вопросы к написанному коду и к рабочим процессам
  • Тесты статичны и их сложно менять, в то время как тестируемая система имеет свойство постоянно эволюционировать, обрастать новым функционалом и менять поведение старого. И тесты нужно менять каждый раз, когда функционал изменяет внешний вид программы или ее поведение. И с ростом сложности обновления тестов оправдывать чудовищные издержки на поддержку тестов становиться все сложнее.
Model-Based Testing данные проблемы практически полностью игнорирует, поскольку тесты создаются автоматически из точной модели приложения. Это сильно упрощает как поддержку уже существующих, так и генерацию новых, крайне полезных и гибких тестов.

Что такое модель?

Модель - это описание тестируемой системы. Формальная спецификация вполне сойдет. Модель должна быть сильно проще описываемой системы и как-то помогать нам понимать и предсказывать поведение тестируемого продукта.

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

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

Что такое Model-Based Testing?

Это довольно немолодая идея использовать формально описанные модели для того, чтобы сделать тестирование ПО более дешевым и простым занятием. Само Model-Based Testing это такая "продвинутая" техника тестирования через "черный ящик". У нее есть ряд бонусов перед традиционными методами:

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

Зоркий поклонник Agile может воскликнуть "эй! у нас есть BDD и оно покрывает первые три пункта и еще это спецификация!". Я же отвечу "нихрена подобного - ваши примеры станут нормальной спецификацией только тогда, когда короля Шака Зулу можно будет считать спецификацией на все человечество".

А теперь отбросим споры и посмотрим, как при помощи теории графов выбивать из модели то, что вам нужно для тестов.

Короткий ликбез по теории графов

Теория графов зародилась в 1736-м году в стареньком Прусском городе Кёнингсберге. Город стоял на двух берегах реки и попутно занимал еще и пару островов посреди этой самой реки. Жители этого города от безделья пытались придумать как посетить все семь мостов не проходя ни по одному дважды. Решали на практике, во время прогулок, и в теории, во время кухонных посиделок. Долгое время никто не мог доказать или опровергнуть возможность существования данного маршрута, пока не пришел зануда Эйлер и не испортил горожанам праздник.
Эйлер придумал изобразить каждый кусок суши как вершину графа, а мосты - ребрами графа.
И тут внезапно стало понятно, что нужного маршрута не существует. И все потому, что все вершины имеют нечетное число ребер. Ведь если у вершины четное число ребер, то гуляющий гражданин каждый раз заходя на этот кусок суши может выйти оттуда по новому мосту. Таким образом получается, что прогуляться по всем мостам не пересекая какой-то мост дважды не получится.

С тех пор граф, в котором все вершины имеют четное количество ребер называется "Эйлеровым Графом". А полный обход этого графа носит гордое имя "Эйлерова пути".

И после этого жителям Кёнингсберга пришлось найти себе другое развлечение. Только один китайский математик Мэй-Ку Куан все морочил себе голову этими мостами. А беспокоил его следующий вопрос:
Если нельзя построить маршрут так, чтобы каждый мост пересекался ровно один раз, то какое минимальное количество дополнительных пересечений моста нужно совершить для полного обхода.
А это уже сильно похоже на проблему, с которой встречаются почтальоны. Допустим, каждая вершина это почтовый ящик, куда нужно вкинуть писем. И, допустим, наш постальон должен вкинуть писем в каждый ящик не совершая лишних движений.

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

И в честь Куана эту задачку назвали "задачей китайского почтальона".

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

Тут мы введем еще один термин - орграф. Или ориентированный граф. Это такой граф, ребра которого можно пересекать только в указанном направлении. Направленные же ребра так же называются "дугами".

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

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

Причем тут тестирование?

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

Первое что захочет селать тестировщик - выполнить все возможные действия с тестируемой системой. Но как мы можем это выполнить эффективно? Тут сообразительному тестировщику в голову приходит задачка про таксиста из Нью-Йорка, которая просто слегка замаскировалась. И поскольку у нас уже есть модель тестируемой системы в виде графа, то нам нужно просто применить к ней подходящий алгоритм его обхода, который может быть сгенерирован автоматически.

С другой стороны, исполнение всех возможных действий это хорошо, но даже самый недалекий тест-менеджер понимает, что это банальное "покрытие состояний" в терминах тестирования сырого кода. Но у множителей есть одно неприятное свойство - у них, как правило, очень много "следующих" состояний у каждой вершины. Что же нам делать, если мы хотим проверить все возможные комбинации действий? Решения задач вроде задачи Китайского Почтальона не подходят, поскольку они гарантируют только посещение каждой дуги, но никак не посещение всех возможных комбинаций дуг.

Такой подход как раз активно использовался для тестирования конечных автоматов. К тому же это требование естественно вытекает из комбинаторной техники дизайна тестов под названием "все пары".

Решение предложил некий де Брюийн. Алгоритм выглядит примерно так:

  • Рисуем сбоку граф, где каждое ребро исходного графа является вершиной.
  • Там где у исходного графа дуга "1" входит в вершину, откуда выходит дуга "2" рисуем в свежеиспеченном графе дугу из вершины "1" в вершину "2".
  • Эйлеризуем полученный граф.
  • Рисуем Эйлеров путь на данном графе.
В принципе можно не напрягаться и просто сделать случайный обход графа. Что примечательно - такая стратегия достаточно устойчива к "парадоксу пестицида". С другой стороны, у любого мало-мальски сложного приложения довольно развесистый граф состояний, на которых можно потратить кучу времени, прежде чем получить хоть какое-то покрытие "случайным обходом".

Про то, зачем сюда добавляют Цепи Маркова, и как обычно решается распараллеливание таких тестов я напишу позже. А пока подведем краткие итоги.

Итого

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

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

И, поскольку Теория Графов позволяет нам работать непосредственно с моделью:
  • Новые обходы можно автоматически генерировать при изменении модели
  • Наши тесты могут легко и непринужденно меняться в рамках одной и той же модели
  • Различные алгоритмы обхода могут удовлетворять различным потребностям тестирования
  • Полученные алгоритмы обхода легко можно переиспользовать в совершенно новой среде

11 комментариев:

  1. Серега, ты - мегамозг! Тема конечно интересная. А ты знаешь, есть реальные примеры применения такой методы на практике? Сдается мне, начальные затраты тут перекрывают все преимущества. Обычно люди даже спецификацию на человеческом языке написать не могут, а тут предлагается разложить все действия пользователя на простейшие операции. Задача интересная с точки зрения математики, но не с точки зрения её решения инженерами, которые будут эту модель составлять :) Надо сначала эту работу автоматизировать

    ОтветитьУдалить
    Ответы
    1. Есть очень много примеров.
      Например некто Баранцев, говорил что они на этом тестировали у себя в институте всякие ядра линуксов. Вообще в академической среде довольно широко распространена эта игрушка.
      Вообще техника очень хорошо работает на програмных интерфейсах - проще формализовать, проще писать обвязки, можно строить модели из воздуха.
      Для GUI есть старый добрый http://crawljax.com/ который на тех же принципах построен. Его обкатывали на рекламных сервисах гугла - результаты на сайте можно поискать.
      Яндексовский роботестер так или иначе тоже MBT тул.
      Есть Гарри Робинсон (тестовый архитектор Bing), который за последние много лет применяет это добро внутри Microsoft (и для Google Maps ими же тестировал) на ура. Вот его сравнительно свежее интервью: http://model-based-testing.info/2012/03/12/interview-with-harry-robinson/
      Есть Виттакер (бывший глагне тестер за Chrome OS), который в свое время этим тоже занимался в MS и курировал все мало-мальски крупные коммуните по MBT.
      Вот граждане из финнского интела (если я все правильно помню) заопенсорсили (если интересно - могу сдать контакты): https://github.com/pablovirolainen/fMBT

      Примеров использования много. Оно широко известно в узких кругах. Но есть ньюанс - людям в массе своей проще валить лес топорами и пилами. И прорблема даже не в спецификации, т.к. в ряде случаев можно сравнительно легко реверс инжинирить спеки из тестируемого приложения (чуваки тестировавшие софт для curiosity так и сделали, в общем-то). Проблема в том, что тут нужна некоторая техническая и математическая база, а с ней у тестировщиков в массе своей бяда.

      Удалить
  2. Ответы
    1. Немного в другом виде, но да, есть.

      Удалить
    2. Надо будет на CodeFest поговорить. Очень хочется начать использовать но пока не представляю как...

      Удалить
  3. Хорошая статья, но ушел много в историю. Немного не сошлось с выводами.

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

    Ты когда-то пробовал применять какие-то инструменты для генерации WebDriver тестов, исходя из модели? Поделись впечатлениями

    ОтветитьУдалить
    Ответы
    1. Это не столько история, сколько краткий курс теории графов. Можно было, конечно, сразу с Цепи Маркова начать, но что-то мне подсказывает что публику незнакомую с вопросом это бы отпугнуло. У MBT и так одна из главных проблем это то, что практически все материалы по нему в лучшем случае выполнены в стиле научных публикаций, которые обычно пугают среднего ITшника (не только тестировщика).

      На WebDriver работает Crawljax. Он, собственно, автоматически строит граф приложения, а потом траверсится по нему. Но там есть несколько проблем. Первая - то что доки по нему это код и диссертации людей писавших этот Crawljax. Вторая - большая часть работы с ним это накрутка начальных настроек, а тут см. пункт первый.

      Яндексовский роботестер тоже на WebDriver'е работает, но он не столько про графы (хотя я считаю что рано или поздно про них тоже будет :)) и его в открытом доступе нет.

      ЗЫ: А что с выводами не так? Переход сильно резкий?

      Удалить
    2. Понял, спасибо за ответ. Будет чем заняться...

      Да, резко на выводы перепрыгнул, что я немного потерял суть статьи

      Удалить
  4. В аутсорсинге сейчас царят быстрые тесты на *unit - создал код, взял данные из библиотечки ресурсов (хорошо, если и код в библиотечку оформлен), тест готов. Что-то отвалилось, отвалились только несколько тестов - починить код или ресурс в библиотечке, и снова тест работает.
    А фреймворки создаются для разбиения монолитного кода на модули: application driver (дёргать AUT), infrastructure driver (оперировать инфраструктурой), дальше уровни "высокоуровневого" создания тестов, возможно, ещё выше - уровень BDD. Наиболее продвинутые аутсорсеры тоже создаёт фреймворки.

    MBT больше подходит для солидных многолетних проектов (дорого проводить серьёзное планирование для всякого проекта).

    А для "проектной" конторы историю я бы начал так "тестописатель изучает тестируемую систему и смежные продукты/системы, и, если возможно, бегло - остальные продукты конторы, и проектирует тесты в расчёте на использование в нескольких продуктах" (в идеале).

    ОтветитьУдалить
    Ответы
    1. Я никогда не работал в аутсорсинге :(

      Но какой-нибудь stateful протокол (или APIшечка аналогичная) заворачивается под MBT довольно быстро. Опять же - модель в ряде случаев довольно легко выдирается из SUT без какого-либо планирования. Пишете "краулер" для приложения и вуаля - заготовка модели для обработки напильником.

      А про фреймворки не соглашусь. Они возникают когда нужно что-то кроме "быстро наговнякать на коленке пару тестов". И вот у вас уже конструктор для создания тестов. Так проще писать и проще поддерживать.

      Удалить
  5. Отличная статья!
    Надеюсь, будет продолжение.
    Когда я занимался автоматизацией в Люксе мы как раз пытались построить MBT-фреймворк для QTP, используя описанные у Майкла Хантера принципы - http://www.thebraidytester.com/downloads/CaptureTheEssenceOfYourTestCases.pdf

    ОтветитьУдалить