ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ =
УДК 681.3.06
ОБЗОР МЕТОДОВ ПОСТРОЕНИЯ ПОКРЫВАЮЩИХ
НАБОРОВ
© 2011 г. В.В. Кулямин, А.А. Петухов Институт системного программирования РАН 109004 г. Москва, ул. Солженицына, 25 E-mail: kuliamin@ispras.ru Поступила в редакцию 03.10.2010 г.
Работа представляет собой обзор методов построения покрывающих наборов, используемых при генерации тестов для интерфейсов с большим количеством параметров. Анализируются область применения этих методов и использующиеся в них алгоритмы. Указывается ряд их характеристик, включая временную сложность и оценку требуемой памяти. В работе приводятся прямые, рекурсивные, оптимизационные, генетические алгоритмы, а также алгоритмы поиска с возвратом, используемые для построения покрывающих наборов. В работе представлены эвристики, позволяющие сократить наборы без потери полноты, и очерчиваются области применимости этих эвристик.
1. ВВЕДЕНИЕ
Высокая сложность современных программных систем и важность решаемых ими задач делают актуальной проблему проверки правильности работы таких систем, т.е. получения подтверждения того, что во всех возможных ситуациях они работают в соответствии с требованиями к ним. Для такой проверки чаще всего используется тестирование - анализ поведения тестируемой системы в конечном наборе специально создаваемых тестовых ситуаций.
Чтобы обеспечить качество и полноту проводимых проверок, нужно иметь как можно больше тестов, но полное тестирование неосуществимо, поскольку число возможных ситуаций, в которых необходимо проверить поведение реальных систем, практически бесконечно. Поэтому на практике стараются выбрать небольшое количество тестовых ситуаций так, чтобы по поведению системы в этих ситуациях можно было судить о ее поведении в целом. Обычно при этом тестовые ситуации разбиваются на классы эквивалентности, так, чтобы поведение тестируемой системы в рамках
одного класса менялось слабо, а при переходе между классами - достаточно сильно. После этого полнота тестирования определяется как степень покрытия тестами выделенных классов ситуаций. В ходе выполнения тестов анализируется поведение системы и проводится проверка на его соответствие требованиям.
Поскольку тестирование должно быть ограничено, количество выделяемых классов всегда конечно. Однако оно может быть слишком большим для эффективного проведения тестирования в рамках заданного проекта. Часто возможные ситуации и сценарии поведения тестируемой системы классифицируются по некоторому набору факторов, характеристик или параметров, каждый из которых может принимать конечное множество значений. Различные классы ситуаций соответствуют при этом всем возможным комбинациям значений выделенных факторов.
Примеры факторов, используемых при классификациях ситуаций:
• успешность или неуспешность выполнения некоторой операции;
• ветвление в коде тестируемого компонента,
значением соответствующего фактора является выполнение ветки if или else в этом ветвлении;
• альтернатива (выбор из нескольких возможных вариантов) правила грамматики при тестировании на основе грамматик [1,2], значениями здесь являются возможные способы разрешения альтернативы;
• категория, при тестировании на основе разбиения на категории [3].
Во многих таких случаях для проведения качественного тестирования требуется проверить взаимодействие факторов между собой, их совместное влияние на поведение системы. Для выполнения такой проверки необходимо комбинировать значения факторов так, чтобы, с одной стороны, получить достаточно аккуратное тестирование, а с другой, - не увеличить чрезмерно тестовый набор, поскольку полный перебор всех комбинаций факторов для реальных систем обычно требует слишком больших затрат.
В данной работе рассматриваются методы создания тестовых наборов на основе комбинаций значений факторов, включающих все возможные сочетания пар, троек или больших множеств значений различных факторов. Такие методы успешно применялись для тестирования систем различных типов (см. работы [2,4-8]). Они позволяют создавать небольшие, в сравнении с полным перебором, но в то же время качественно тестирующие систему тестовые наборы при выполнении следующих условий.
• Есть некоторый вид ситуаций или воздействий на систему, имеющий довольно много параметров или факторов.
• Значения каждого из параметров можно разбить на (небольшое) конечное число классов, таких, что все существенные изменения в поведении системы происходят только из-за изменения класса одного из параметров.
• Известно, что ошибки в поведении системы возникают в основном за счет сочетания не-
большого количества факторов, определяемых значениями используемых параметров.
При отсутствии дополнительной информации о зависимости между возможными ошибками и возможными значениями параметров эти методы позволяют достаточно эффективно строить тестовые наборы, исследующие большое разнообразие ситуаций, иначе можно использовать такую информацию для построения более компактных нацеленных тестов.
Рассмотрим в качестве примера тестирование пользовательского интерфейса системы перевода денежных средств WebMoney. Этот интерфейс доступен для любого современного браузера и разных операционных систем. Наиболее распространённой операцией в рамках этой системы является перевод денег с одного кошелька на другой с помощью интерфейса WM Keeper Light. Эта операция выполняется при таких часто используемых действиях пользователя в сети, как оплата мобильной связи или Интернета, покупка товара в интернет-магазине. На работу этой операции может оказать влияние несколько факторов. В качестве наиболее существенных из них выберем объём передаваемой суммы, необходимость конвертировать валюту, тип кошелька, с которого идёт платёж, способ аутентификации пользователя в системе WebMoney, браузер и операционную систему пользователя.
В качестве возможных значений этих параметров на основе документации по интерфейсу WM Keeper Light [9] выберем следующие (Таблица 1).
Если теперь попробовать составить все возможные комбинации значений факторов, получится 3 х 2 х 4 х 4 х 3 х 5 = 1440 тестов. Это немного, но, например, выполнение их всех вручную потребует значительных затрат.
Эмпирические исследования [7, 8, 10] утверждают, что в подобных случаях большинство ошибок (до 70%) связано с определенными комбинациями значений всего лишь двух параметров. В других работах [11] показано, что комбинации пар факторов при тестировании дают покрытие кода до 80% при более-менее разумном выборе значений отдельных
Таблица 1. Значения параметров для тестирования перевода денег с одного кошелька на другой с
помощью интерфейса WM Keeper Light.
Передаваемая Нужна ли Тип кошелька, Браузер Способ Операционная
сумма конвертация валюты с которого идет платеж аутентификации система
< 100 руб. Не нужна WMR рубли Internet Explorer Сертификат X.509 Windows XP
100 - 10000 руб. Нужна WMZ доллары Mozilla Firefox Enum-авторизация Windows Vista
> 10000 руб. WME евро Opera Логин и пароль Debian Ubuntu
WMU гривны Google Chrome Linux SUSE
Linux RedHat
параметров. Иными словами, если тесты будут содержать все возможные комбинации пар значений параметров, большая часть ошибок будет ими выявлена. При этом можно задействовать все пары значений различных факторов в небольшом наборе тестов. Минимальное количество таких тестов для данного примера равно 20, поскольку имеется 20 возможных сочетаний типов кошельков и операционных систем. Набор из такого количества тестов действительно можно построить, используя техники, описанные в данной работе (пример см. в таблице 2).
Можно попробовать составить тестовый набор так, чтобы он по-прежнему оставался небольшим, но содержал уже все различные тройки значений параметров. Для приведённого примера потребуется не менее 80 = 5 х 4 х 4 тестов, что все же существенно меньше, чем 1440. Используя описанные ниже методы, можно получить и такой набор. При таком тестировании может быть обнаружено ещё больше ошибок [7, 10].
Данная работа посвящена обзору различных методов построения тестов, использующих все пары, тройки и большие множества значений параметров. Раздел 2 содержит определение покрывающих наборов и основные сведения о них. Раздел 3 посвящен собственно обзору, за ним следует заключение.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Тестовый набор, покрывающий все пары, тройки или большие множества возможных
сочетаний значений параметров системы, соответствует математическому понятию покрывающего набора (covering array).
Пусть есть k факторов, оказывающих влияние на работу системы, причем первый фактор может принимать ni различных значений, второй n2 и т.д. k-ый фактор - n^ значений. Покрывающим набором глубины t называется матрица из k столбцов, таких, что в i-ом столбце стоят значения i-ого фактора, и любая комбинация возможных значений любых t факторов встречается хотя бы в одной из ее строк.
Поскольку сами значения факторов не важны, можно обозначать их числами от 0 до ni — 1. Набор чисел (t; k, ni ... n^) принято называть конфигурацией покрывающего набора, а множество покрывающих наборов с такой конфигурацией обозначать CA(t; k, n1 ... nk). Соответствующее формальное определение таково: целочисленная матрица N х k, обозначаемая далее A, является покрывающим набором из CA(t; ni ... nk) тогда и только тогда, когда
Vi е [1..N], j е [1— k] Aij е [0..nj — 1] & Vji,..., jt е [1..k] Vvi е [0..nji — 1],..., vt е [0..j — 1] 3i е [1..N]Vq е [1..t]Aijq = vq.
В конфигурации (t; k, ni ... ) число t называется глубиной набора, k - количеством параметров или факторов, а ni - количеством значений i-го параметра. Все числа t, k, ni, ... nk назовем характеристиками конфигурации. Покрывающий набор глубины t иногда называют также t-покрывающим
Таблица 2. Минимальный набор тестов для интерфейса WM Keeper Light.
< 100 руб. Не нужна WMR рубли Internet Explorer Сертификат Х.509 Windows XP
100-10000 руб. Нужна WMZ доллары Mozilla Firefox Enum-авторизация Windows XP
> 10000 руб. Не нужна WME евро Opera Логин и пароль Windows XP
100-10000 руб. Нужна WMU гривны Google
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.