Pairwise testing: добиваемся оптимального покрытия различных тестовых комбинаций

В тестировании программ очень часто встаёт задача проверки комбинаций входных параметров, от которых зависит итоговый результат программы. Типичный пример - диалоговое окно печати файла: оно имеет множество настроек, полей ввода, различных взаимозависимых опций, от включения или выключения которых итоговый результат может сильно различаться. Если бы даже все опции имели только два режима работы (вкл/выкл), а всего опций было бы 10, то это уже даёт 2¹⁰ = 1024 их комбинаций.

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

1. Вкратце о Pairwise testing

Pairwise testing (all-pairs analysis, попарное тестирование или попарный анализ, анализ всех пар комбинаций) - это современная и эффективная методика тестирования, основанная на том предположении, что большинство дефектов возникает при взаимодействии не более двух факторов. Тестовые наборы, генерируемые при использовании данной методики охватывают все уникальные пары комбинаций факторов, что считается достаточным для обнаружения большего числа дефектов.

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

1. "Pairwise testing. Part 1 - Orthogonal Arrays" (ru) - вводная статья для ознакомления с примерами построения ортогональных массивов в целях тестирования.
2. "Pairwise testing. Part 2 - AllPairs Algorithm" (ru) - продолжение предыдущей статьи, в которой объясняется суть алгоритма allpairs.
3. "Pairwise Testing" (en) - подробная статья, в которой описан пример использования данной методики для выбора тестовых комбинаций из трёх параметров.
4. "Pairwise Testing: A Best Practice That Isn’t" (en) - статья, в которой рассматриваются преимущества использования методики попарного тестирования перед другими.
5. "Pairwise Testing in the Real World: Practical Extensions to Test-Case Scenarios" (en) - практикум от Микрософт по использованию методики Pairwise testing.
6. "All-pairs testing" (en) - статья в Википедии с описанием комбинаторного метода, лежащего в основе попарного тестирования.
7. "Метод попарного тестирования" (ru) - аналогичные примеры из области попарного тестирования, что и в источниках выше.

Для Pairwise тестирования используются алгоритмы основанные на построении ортогональных массивов или на All-Pairs алгоритме, которые опираются на теоретические исследования в области комбинаторных алгоритмов, алгоритмов дискретной математики и, в частности, латинских квадратов (см., например, М. Холл "Комбинаторика", М.: Мир, 1970, глава 13, стр. 261).

Ортогональный массив (ортогональная таблица) - это таблица L_m(kⁿ), где m - число строк, n - число столбцов (по числу входных параметров), k - количество вариантов для значений элементов таблицы, и обладающая следующими свойствами:

1. Любые два столбца таблицы содержат все комбинации значений этих столбцов.
2. Если какая-либо пара значений двух столбцов встречается несколько раз, то все возможные парные комбинации значений этих столбцов должны встретиться столько же раз.

В ортогональных массивах необязательно все столбцы должны иметь одинаковое количество значений. Существуют так называемые смешанные (mixed) ортогональные массивы. Например:

L₄(2³) – ортогональный массив с четырьмя строками, тремя столбцами (по количеству переменных), 2 означает, что все переменные принимают только два значения – 1 и 2.

L₁₈(2¹3⁷) – смешанный ортогональный массив с восемнадцатью строками, у которого один столбец со значениями 1 и 2, и семь столбцов со значениями 1, 2, 3.

Для тестирования с использованием ортогональных массивов выполняют следующие шаги:

1. Определяют переменные для входных данных в комбинациях. Например, это могут быть названия опций, параметров настроек, допустимых конфигураций оборудования и т. п.
2. Определяют значения, которые могут принимать переменные. Например, конкретные названия пунктов меню, числовые значения, названия операционных систем или баз данных и т. п.
3. Строят ортогональный массив, который имеет столбец для каждой переменной. Обычно для этого используется какая-либо программа, например, STATISTICA.
4. Каждая строка построенного массива интерпретируется как одна комбинация значений переменных для одного тестового случая.

All-Pairs Algorithm (алгоритм всех пар) - это комбинаторная методика, которая была специально создана для попарного тестирования. В её основе лежит выбор возможных комбинаций значений всех переменных, в которых содержатся все возможные значения для каждой пары переменных. Исходя из определения при этом будет получено меньшее число комбинаций, чем при использовании ортогональных массивов.

Для тестирования с использованием All-Pairs алгоритма выполняют следующие шаги:

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

Пример рассуждений по алгоритму All-Pairs, для выбора нужных строк с комбинациями, приведен под спойлером:

Понять алгоритм Pairwise тестирования All-Pairs можно из таблицы ниже. Её строки содержат 12 возможных комбинаций значений для трёх параметров. Каждый параметр задаётся в столбцах: первый параметр принимает значения из множества {0, 1}, второй - из {x, y, z}, третий - из {2, 3}. В этой таблице только зелёные строки будут выбраны при использовании алгоритма All-Pairs.

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

1. Наибольшее количество значений имеет 2-й параметр, начинаем считать комбинации с него. Переставляем второй столбец с первым. Каждое из значений x, y, z оставляем в итоговой таблице по 2 раза - столько, сколько значений у 1-го параметра, переставленного во 2-й столбец. Итого, всего 6 строк.
2. Во 2-й столбец должны попасть значения 1-го параметра, у которых для каждого дубля букв x, y, z повторяются оба возможные значения. Получаем все возможные комбинации пар значений 2-й и 1-й переменной (6 пар в шести строках).
3. Заполняем 3-й столбец. Для каждого дубля из 1-го столбца заполняем строки обеими значениями 3-го параметра.
4. Проверяем наличие всех возможных комбинаций пар значений для всех пар столбцов:
   2-й и 3-й столбцы: (0, 2), (1, 3) есть, но нет (0, 3), (1, 2). Поэтому в первых попавшихся строках поменяем 2 и 3 местами - они записаны в скобках. Сейчас для 1-го и 3-го параметров есть все пары. При этом и для 2-го и 3-го параметров получаются все 6 возможных пар (x, 2), (x, 3), (у, 2), (у, 3), (z, 2), (z, 3). Таблица заполнена. Хватило 6 строк.

Выпишем теперь полученные тройки, отбирая параметры по порядку, как они есть: (0, x, 2), (1, x, 3), (0, y, 3), (1, y, 2), (0, z, 2), (1, z, 3). Это те самые комбинации, что и в строках закрашенных зелёным, из таблицы выше.

Обычно на практике используют некоторые программные реализации этого алгоритма, так как вручную перебирать все пары достаточно трудоёмко.

2. Программная реализация All-Pairs алгоритма для Pairwise testing

Существует множество инструментов для реализации техники попарного анализа, например, с их списком можно ознакомиться по ссылке:
http://www.pairwise.org/tools.asp

В нашей команде автоматизаторов при разработке одной из систем тестирования широко применялся Python. Поэтому рассмотрим здесь пример использования в своих скриптах генератора комбинаций AllPairs, разработанного MetaCommunications Engineering для Python и реализующего одноименную методику. Скачать его можно здесь: http://sourceforge.net/apps/trac/allpairs/

После стандартной установки библиотеки AllPairs можно скопировать к себе в проект каталог <PYTHON_HOME>\Lib\site-packages\metacomm\ для упрощения импортов и переноса проекта на другие компьютеры.

Рассмотрим ещё одну задачу из области тестирования. Пусть требуется проверить работоспособность веб-сайта в различных конфигурациях браузеров, операционных системах и на платформах с различной разрядностью. Например, заданы четыре конкретные операционные системы: Windows XP SP 3, Windows 7 SP 1, Debian 7.1, Ubuntu 12.04, для двух разрядностей: x86, x64, и три браузера: chrome, firefox, safari.

При этом получаем: 4 x 2 x 3 = 24 конфигурации для тестовых наборов, которые требуется проверить в общем случае. Можно уменьшить число тестовых наборов при помощи AllPairs.

Входные данные для модуля AllPairs могут быть заданы как список списков из строк, значения которых однозначно характеризуют параметры для тестовых наборов. Для нашей задачи это могут быть просто названия параметров для конфигураций:
список возможных ОС:Windows XP SP 3, Windows 7 SP 1, Debian 7.1, Ubuntu 12.04,
список разрядностей:x86, x64,
список браузеров:chrome, firefox, safari.

Задание входных параметров в Python-коде и использование AllPairs для построения их комбинаций может выглядеть как в спойлере ниже (предполагается, что каталог ext, содержащий пакет metacomm, уже лежит рядом со скриптом allpairs.py).

Код скрипта allpairs.py:

# -*- coding: utf-8 -*-
#
# (c) Gilmullin Timur Mansurovich,  2013.

# Using AllPairs by MetaCommunications Engineering example.

from ext.metacomm.combinatorics import all_pairs2 as ap

def Generator(parameters):
    """
    Use generator which work on AllPairs-algorithm.
    Input:
    parameters - list of list of different parameters, that looks like this:
    [ [par1_val_1, par1_val_2, ...],
      [par2_val_1, par2_val_2, ...], ... ]
    Output:
    list of enumerate possible unique combinations, that looks like this:
    [ (0, [par1_val_1, ..., parK_val_K]), ...
      (N, [parX_val_X, ..., parY_val_Y]), ...]
    """
    combinations = list(enumerate(ap.all_pairs2(parameters)))
    return combinations


if __name__ == '__main__':
    # define list of list of different parameters:
    inputData = [
        ['Windows XP SP 3', 'Windows 7 SP 1', 'Debian 7.1', 'Ubuntu 12.04'],
        ['x86', 'x64'],
        ['chrome', 'firefox', 'safari']
        ]
    # get combinations and output it:
    outputData = Generator(inputData)
    with open('output.txt', 'w') as fH:
        for line in outputData:
            stringData = 'Combination {}:\t{}'.format(str(line[0]), str(line[1]))
            print(stringData)
            fH.write(stringData + '\n')

В скрипте каждая новая строка переменной inputData содержит список допустимых значений для отдельного параметра в тестируемых конфигурациях. После определения таким образом входных данных, нужно просто выполнить скрипт командой:
python allpairs.py

На выходе будет получен пронумерованный список строк вида:
Combination 0: ['Windows XP SP 3', 'x86', 'chrome'] ...
Как видим, комбинаций всего 12 - в два раза меньше, чем их полное число в общем случае. А если применить этот же алгоритм для примера в начале статьи, то вместо 1024 полных комбинаций, получим всего 8!

Затем полученные комбинации можно интерпретировать как тестовые случаи, например:
"Выполнить проверку работоспособности веб-сайта для конфигурации:
- ОС: Windows XP SP 3,
- разрядность системы: x86,
- браузер: chrome."

Скачать код скрипта allpairs.py для данной задачи можно по ссылке:
https://drive.google.com/file/d/0B-1rf8K04ZS5ZHJpdXRRd24zc0E/edit?usp=sharing
код на GitHub:
https://github.com/Tim55667757/AllPairs_example

Приложенный архив включает в себя каталог metacomm с библиотекой AllPairs, модуль allpairs.py с примером решения приведённой выше задачи и вывод результатов в файле output.txt.

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