~ ТЕСТИРОВАНИЕ И ВЕРИФИКАЦИЯ ПРОГРАММ И СИСТЕМ -
УДК 681.3.06
СМЕШАННЫЙ ОПТИМИЗАЦИОННО-КОМБИНИРОВАННЫЙ МЕТОД ПОСТРОЕНИЯ ПОКРЫВАЮЩИХ НАБОРОВ
© 2014 г. A.A. Петухов
Институт системного программирования РАН 109004 Москва, ул. А. Солженицына, 25 E-mail: ale.petuhov@gmail. com Поступила в редакцию 10.08.2013
Покрывающие наборы используются при генерации тестов для интерфейсов с большим количеством параметров. В работе описан новый метод построения однородных и неоднородных покрывающих наборов, основанный на соединении комбинаторных и оптимизационных методов. В широком классе частных случаев метод ускоряет построение наборов в несколько раз (зависит от частного случая) относительно известных широко применяемых оптимизационных методов. При этом, в большинстве случаев, размеры получаемых наборов остаются примерно такими же, как наборов, построенных другими оптимизационными методами, а в ряде частных случаев удалось получить наборы меньшие примерно на 5—15%. Анализируется область применения нового метода.
1. ВВЕДЕНИЕ
Одной из самых важных и трудоемких задач в области вычислительных систем является тестирование - анализ поведения тестируемой системы в конечном наборе специально создаваемых тестовых ситуаций. Чтобы обеспечить качество и полноту проводимых проверок, нужно иметь как можно больше тестов, но полное тестирование неосуществимо, поскольку число возможных ситуаций, в которых необходимо проверить поведение реальных систем, практически бесконечно. Поэтому на практике стараются выбрать небольшое количество тестовых ситуаций так, чтобы по поведению системы в этих ситуациях можно было судить о ее поведении в целом.
Часто возможные ситуации и сценарии поведения тестируемой системы классифицируются по некоторому набору факторов, характеристик или параметров, каждый из которых может принимать конечное множество значений. Различные ситуации соответствуют при этом всем возможным комбинациям значений выделенных факторов.
Примеры факторов, используемых при классификациях ситуаций:
• успешность / неуспешность выполнения некоторой операции;
•
та, где значением соответствующего фактора является выполнение ветки if или else в этом ветвлении;
•
ных вариантов) правила грамматики при тестировании основе грамматик [1, 2], значениями здесь являются возможные способы разрешения альтернативы;
биения на категории [3].
Во многих таких случаях для проведения качественного тестирования требуется проверить взаимодействие факторов между собой, их совместное влияние на поведение системы. Для выполнения такой проверки необходимо комбинировать значения факторов так, чтобы, с одной стороны, получить нужное качество тестирования, а с другой, не увеличить чрезмерно тестовый набор, поскольку полный перебор всех комбинаций факторов для реальных систем часто неосуществим или требует больших затрат.
В работах [4-9] описаны методы создания тестовых наборов на основе комбинаций значений факторов, включающих все возможные сочетания пар, троек или больших множеств значений различных факторов. Эти методы позволяют создавать небольшие в сравнении с полным перебором, но в то же время качественно тестирующие систему тестовые наборы при выполнении следующих условий:
• Есть некоторый вид ситуаций или воздействий на систему, имеющий довольно много параметров или факторов.
•
разбить на (небольшое) конечное число классов, таких, что все существенные изменения в поведении системы происходят только из-за изменения класса одного из параметров.
•
мы возникают в основном за счет сочетания небольшого количества факторов
При отсутствии дополнительной информации о зависимости между возможными ошибками и значениями параметров эти методы позволяют достаточно эффективно строить тестовые наборы, исследующие большое разнообразие ситуаций, иначе можно использовать такую информацию для построения более компактных нацеленных тестов.
Упомянутые методы генерации тестов используются при тестировании различных конфигураций аппаратуры и программного обеспечения: авиационных управляющих систем [10], операционных систем [10], пользовательских интерфейсов [1143], программных интерфейсов [4], коммуникационных систем [14-17]. В статьях [11, 12] даны ссылки на эмпирические исследования, где применялись описанные в данной работе методы, в том числе и для тестирования веб-браузера Мозилла [13]. В приведенных в статьях [11, 12] частных случаях большинство дефектов (до 70%) было обнаружено при помощи перебора комбинаций значений всего лишь двух параметров, а при переборе комбинаций большего числа значений параметров обнаружено еще больше ошибок. Стоит отметить также, что при таком тестировании число тестов существенно
меньше в сравнении с полным перебором всех возможных значений. В работе [18] показано, что комбинации пар факторов при тестировании дают покрытие кода до 80% при более-менее разумном выборе значений отдельных параметров.
Тестовый набор, покрывающий все пары, тройки или большие множества возможных значений параметров системы, однозначно отображается в матрицу, называемую покрывающим набором (covering array). Пусть есть к факторов, оказывающих влияние на работу системы, причем первый фактор может принимать щ различных значений, второй щ и т.д. k-ый фактор - Пк значений. Покрывающим набором глубины t называется матрица из к столбцов, таких, что в i-ом столбце стоят значения i-oro фактора, и любая комбинация возможных зна-t
в одной из ее строк. Поскольку сами значения факторов не важны, можно обозначать их числами от 0 до Ui-\. При описании тестов с помощью покрывающего набора, каждая строка покрывающего набора соответствует одному тесту, а присутствующее в ее г-ом столбце число соответствует номеру класса значений г-ro параметра. Это соответствие позволяет использовать математическую теорию покрывающих наборов для построения тестовых наборов.
Набор чисел (t; к, п1 ... Пк) принято называть конфигурацией покрывающего набора, а множество покрывающих наборов с такой конфигурацией обозначать CA(t; к, п1 ...Пк). Соответствующее формальное определение таково. Целочисленная матрица N х к, обозначае-A,
из CA(t; щ ...Пк) тогда и только тогда, когда Vi е [1..N], j е [1..кА е [0..щ - 1] & Vji,..., jt е [1..к] Vvi е [0..Щ1 - 1],..., vt е [О..щ-t -1] 3i е [1..N]Vq е [1..t]Aijq = Vq.
Покрывающий набор минимален, если не существует покрывающего набора такой же конфигурации, содержащего меньшее количество строк. Количество строк в минимальном покрывающем наборе конфигурации (t; к, п1 ... Пк) обозначается CAN(t; к, п1 .. .пк).
Если количества значений всех факторов совпадают, т.е. п1 = п2 = • • • = Пк = п, соответствующий покрывающий набор называется однород-
ним. Его конфигурация обозначается (t; k, n), множество таких наборов - CA(t; k, n).
Если количества значений нескольких факторов совпадают, т.е. ni = n2 = ... = np1, npi+i = np 1+2 = ■ ■ ■ = np2 и т.д, то для записи конфигурации покрывающего набора используется экспоненциальная нотация: CA(t; k, np^, np2 ...), где p1 + p2 + ■ ■ ■ = k.
Поскольку при построении тестов часто важно, чтобы их число было не слишком большим, удобно использовать минимальные или близкие к минимальным покрывающие наборы. В общем случае для задачи построения минимального покрывающего набора не найдено эффективных алгоритмов. В работе [19] с помощью сведения к задаче раскраски графа в три цвета доказано, что нахождение минимального набора для кон-(t; k, n)
дователи Lei и Tai [20] показали, что частная задача нахождения минимального набора для конфигурации (2; k, n) тоже NP-полна, используя сведение к задаче покрытия вершин графа.
Для размера минимальных покрывающих наборов известно [4, 21], что с ростом количества факторов, размер растет лишь логарифмически, что и обуславливает практическую полезность покрывающих наборов для построения небольших, но качественных наборов тестов. В работах [5-9, 22] можно найти оценки размеров покрывающих наборов для частных случаев, а также обширные таблицы с явным указанием размеров наборов для определенных конфигураций.
Исследования покрывающих наборов во многом сосредоточены на поиске минимальных наборов различных конфигураций и разработке эффективных (полиномиальных) алгоритмов построения покрывающих наборов близких к минимальным. Таких алгоритмов известно достаточно много, но они либо работают только для специфических конфигураций, либо дают для большинства конфигураций наборы, намного превосходящие минимальные.
В данной работе описан метод генерации однородных и неоднородных покрывающих наборов, основанный на анализе исходной конфигурации, для которой необходимо построить набор. Метод комбинирует известные методы, что позволяет использовать их сильные и слабые стороны в зависимости от частного случая. В рабо-
те подробно описан алгоритм, являющийся частным случаем общего метода, который сочетает комбинаторные и оптимизационные алгоритмы. Предложенный алгоритм позволяет в ряде частных случаев строить меньшие наборы за меньшее время.
2. СОЕДИНЕНИЕ КОМБИНАТОРНЫХ И ОПТИМИЗАЦИОННЫХ МЕТОДОВ ПОСТРОЕНИЯ ПОКРЫВАЮЩИХ НАБОРОВ
В работах [4-9] приведен обзор методов построения покрывающих наборов. Существующие алгоритмы построения покрывающих наборов можно классифицировать следующим образом.
1. Комбинаторные (прямые) алгоритмы используют соответствие между покрывающими наборами и другими комбинаторными схемами (наборами латинских квадратов, орбитами действий групп и пр.), чтобы построить покрывающий набор в тех случаях, когда соответствующая ему схема устроена достаточно просто.
2. Рекурсивные алгоритмы строят покрывающие наборы из покрывающих наборов для конфигураций с меньшими значениями характеристик (например, с меньшим количеством факторов или меньшей глубиной). При этом могут привлекаться и другие комбинаторные схемы (ортогональные наборы, разностные матрицы и пр.)
3. Редуцирующие алгоритмы строят покрывающие наборы за счет модификации и сокращения покрывающих наборов для конфигураций с большими значениями характеристик.
4. Оптимизационные алгоритмы рассматривают построение покрывающего набора к
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.