автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод редукции тестового набора для интеграционного тестирования

На правах рукописи

Кичигин Дмитрий Юрьевич

МЕТОД РЕДУКЦИИ ТЕСТОВОГО НАБОРА ДЛЯ ИНТЕГРАЦИОННОГО ТЕСТИРОВАНИЯ

Специальность 05.13.11-математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

а

Москва-2010

1 7 ИЮН 2010

004603984

Работа выполнена в Институте системного программирования РАН.

Научный руководитель: доктор физико-математических наук

Петренко Александр Константинович

Официальные оппоненты: доктор технических наук, профессор,

Позин Борис Аронович кандидат физико-математических наук Иванов Денис Владимирович

Ведущая организация: Научно-исследовательский институт системных

исследований РАН

Защита диссертации состоится «17» июня 2010 г. в 15 часов на заседании диссертационного совета Д.002.087.01 при Институте системного программирования РАН по адресу:

109004, Москва, А.Солженицына 25, Институт системного программирования РАН, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан «15» мая 2010 г.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

Прохоров С.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Для решения этой проблемы используется подход, известный как редукция тестового набора, и заключающийся в отборе набора тестов меньшего размера, но при этом, желательно, с неменьшей способностью обнаруживать ошибки, чем у исходного набора тестов. Традиционные способы редукции набора тестов заключаются в «отсеивании» тестов из первоначального набора таким образом, чтобы сохранялся уровень его адекватности в терминах некоторого выбранного критерия адекватности. Для оценки адекватности набора тестов, большинство существующих методов используют метрики адекватности, основывающиеся на статическом анализе и/или инструментировании исходного текста ПО, что обусловливает их ограничения:

1. Неприемлимость использования для программного обеспечения большого объема. Инструментирование исходного кода может быть достаточно нетрудоемким для программного обеспечения, состоящего из нескольких модулей, однако инструментирование исходного кода для ПО, состоящего из нескольких тысяч модулей, гораздо более сложная и затратная процедура.

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

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

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

1. Исследовать виды взаимодействия между модулями ПО и типичные для этих видов интеграционные ошибки;

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

3. Разработать метод редукции регрессионного тестового набора, основанный на сравнении моделей процесса взаимодействия, построенных на информации, полученной при прогоне тестового набора;

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

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

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

Enterprise Desktop vl0.2 анализ структуры интерфейсов системного и прикладного программного обеспечения, показал, что доля таких интерфейсов составляет порядка 96% от общего числа программных интерфейсов, что подтверждает широкую область применения предлагаемого метода. Кроме того, проведенные исследования подтвердили, что данный метод также может быть успешно адаптирован к интерфейсам функций, содержащих не только скалярные параметры и указатели, но и любые другие параметры.

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

Апробация работы и публикации. Результаты работы докладывались:

- Seventh International Andrei Ershov Memorial Conference «Perspectives of System Informatics» (PSI'09), Новосибирск, 2009.

- на секции Software Testing международной конференции SYRCoSE 2007 (The First Spring Young Researchers Colloquium on Software Engineering), Москва, 2007.

- на научном семинаре Института Системного Программирования РАН, Москва, 2006, 2007,2009.

- на научном семинаре The Knowledge Management Research Group, Loughborough University, Loughborough, United Kingdom, 2005. Результаты диссертации опубликованы в 4 печатных работах. Структура и объем работы. Диссертация состоит из введения, 3 глав, заключения, списка литературы и 1 приложения. Список литературы включает 86 названий. Общий объем диссертации составляет 141 страницу. Объем приложения составляет 7 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются особенности редукции набора тестов для регрессионного интеграционного тестирования и также рассматриваются существующие методы редукции набора тестов.

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

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

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

Вторая глава посвящена описанию разработанного метода редукции набора тестов для интеграционного тестирования.

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

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

10

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

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

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

взаимодействия) как множество всех возможных последовательностей длины К, встречающихся в трассе взаимодействия между модулями А и В на тесте /.

Для построения модели взаимодействия используется техника «скользящего окна» с размером К (размер окна соответствует длине выделяемых последовательностей). Согласно этому подходу, выделение последовательностей происходит следующим образом: в качестве первой последовательности из трассы выбираются К идущих подряд интерфейсных функций, начиная с первой функции в трассе; в качестве второй последовательности выбираются К идущих подряд интерфейсных функций, начиная со второй функции; и так далее, пока не будет пройдена вся трасса. В качестве примера построения модели взаимодействия модулей, рассмотрим следующую трассу интерфейсных функций:

тогда результатом выделения последовательностей с помощью скользящего окна размера 4 будет следующее множество последовательностей, являющееся моделью взаимодействия (Рис.1):

Бэреп й-еаё &еас1 &еас! йеасЗ Г^лтНе ГсЬэе

йэреп &еас! &еас! Ггеас! й-еас! Л1озе Аэреп &еас! &еас1 Ггеас! &еас! Ротке ГсЬэе Гореп &еас! Агеас! fread йгеас! £\угИе ^ЬБе

Гореп &еас! й~еас1 &еас! &еаё Ротке Гс1оБе

йзреп &еас! &еас! &еас! Леас! йгеас! &еас1 &еа<1 й-еас) &еас! Ггеас! fwrite

&еас1 &еас1 Ротке &1озе

Рис.1. Построение модели взаимодействия модулей.

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

8{M\,Mi) = П[ Е ГИ/*"/*')]* П t Z ГРО'/")] (*)

jisA/I к=\ sizMi леД/i к-\

где Мх,Мг ~ модели взаимодействия; si,s2 - последовательности интерфейсных функций, входящие в состав моделей; К - длина последовательности интерфейсных функций; fu - вызов интерфейсной функции, имеющий порядковый номер к в последовательности ¡¡; SifjJ-J -функция, задающее отношение эквивалентности между вызовами функций ft и f2, и определяемое с помощью формулы:

л

( т^'),если c?(name(/i),name(/2)) =1

8(Ш = -

( о, если 5(name(/i), паше(/2)) =о где fif2 - вызовы функций; х,-,у^ i = 1..п - значения параметров функций /; и f2 соответственно; name(/) ~ имя функции f; J(name(/i),name(/2)) - функция, задающая отношение эквивалентности для имен функций, и равная 1 если имена функций совпадают и 0 в противном случае. В качестве отношений эквивалентности для значений параметров функций используются следующие отношения:

- Скалярные номинальные параметры: 6(х,у), где 5- отношение равенства;

- Скалярные числовые параметры: 8(х,у) = ¿(interval (х),interval (у)), где <^interval(x), interval^)) - отношение равенства (совпадения) между интервалами, которым принадлежат значения параметров;

- Указатели: 5(р\,рг) = 1, если р: = NULL и р2 = NULL, либо если pt != NULL ир2\- NULL; в любых других случаях 5(pi, р2) = 0;

- Другие типы: 5(х,у) = 1.

Формулируется и доказывается теорема о том, что отношение, заданное формулой (*), является отношением эквивалентности, а именно, удовлетворяет свойствам рефлексивности, симметричности и транзитивности, в дальнейшем используемым в алгоритме редукции.

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

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

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

Описанный выше алгоритм редукции обладает вычислительной сложностью, максимальная оценка которой составляет 0(Г2 х Л^2* х К), при этом максимальный объем памяти, используемой для хранения модели в памяти компьютера, составляет 0(Г х х К), где: Т - количество тестов; К -длина последовательности интерфейсных функций; N - количество интерфейсных функций. Для улучшения этих показателей была проведена оптимизация метода, заключающаяся в том, что табличное представление модели взаимодействия было заменено древовидным, при котором модель взаимодействия представляется в форме дерева, где каждой последовательности вызовов интерфейсных функций соответствует путь в дереве от корня до одного из листовых узлов. Такое представление позволило уменьшить сложность алгоритма до 0(Т2 х К), а

максимальный объем используемой памяти до О (Г х (./У*41 - Л')/(ЛГ -1)).

После описания метода редукции приводятся условия применения, методика применения, и область применимости предложенного метода.

В конце главы приводится описание экспериментального исследования предложенного метода. Экспериментальное исследование включало три серии экспериментов, целями которых являлись:

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

- Оценка влияния длины последовательности вызовов функций (параметр К) на работу метода и оценка затрат ресурсов при работе алгоритма редукции;

- Исследование адаптируемости метода для учета параметров функций других типов.

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

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

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

отражает в процентном выражении способность сокращенного набора тестов обнаруживать ошибки по сравнению с исходным набором тестов.

Для оценки вышеперечисленных характеристик предложенного метода редукции и для его сравнения с методами случайной редукции и редукции пустых трасс была проведена серия экспериментов на ряде тестовых наборов, сгенерированных из тестов тестового набора GNU Assembler. В Таблице 1 приведены основные результаты эксперимента.

Анализ результатов проведенных экспериментов продемонстрировал высокую эффективность метода: коэффициент сокращения исходных тестовых наборов составлял в среднем 52%, при этом коэффициент обнаружения ошибок сокращенных наборов не уменьшался и составлял 100% от уровня исходных наборов. Предложенный метод по совокупности характеристик превзошел методы случайной редукции и редукции пустых трасс: метод был на 20% эффективнее метода случайной редукции в части обнаружения ошибок, и на 42% эффективнее метода редукции пустых трасс в части сокращения исходного набора тестов.

Индикатор Исходный набор Предложенный метод Метод редукции пустых трасс Метод случайной редукции

Размер набора (в среднем) 60 26 54 26

Коэффициент сокращения (в среднем, в %) - на 52% на 10% на 52%

Количество обнаруженных ошибок (в среднем) 16 16 16 12

Коэффициент обнаружения ошибок (в среднем, в % от кол-ва ошибок, обнаруженных исходным набором) 100% 100% 100% 80%

Таблица 1. Результаты эксперимента.

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

Six,у) = S{lengfKx),lengtHy))

где: х, у — строковые параметры; length(x) - длина строки х.

Для сравнения характеристик оригинального и модифицированного методов была проведена серия экспериментов на ряде тестовых наборов, также сгенерированных из тестов тестового набора GNU Assembler, где в качестве тестируемого взаимодействия были выбраны модули, большинство интерфейсных функций которых содержало строковые параметры. В Таблице 2 приведены результаты сравнения характеристик оригинального и модифицированного метода:

Индикатор До модификации После модификации

Коэффициент сокращения (в среднем, в %) на 88% на 79%

Коэффициент обнаружения ошибок (в среднем, в % от количества обнаруженных исходным набором ошибок) 91% 100%

Таблица 2. Результаты эксперимента.

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

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

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

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

Для оценки влияния длины последовательностей интерфейсных функций К проведено сравнение характеристик различных модификаций метода, со значениями К, равными 1,2,3,6,10, и 15. Результаты сравнения приводятся в Таблице 3:

Индикатор \ Длина К 1 2 3 6 10 15

Коэффициент сокращения (в среднем, в %) 74% 61% 57% 54% 52% 45%

Коэффициент обнаружения ошибок (в среднем, в % от кол-ва ошибок, обнаруженных исходным набором) 92% 99% 100% 100% 100% 100%

Время работы (в среднем) 2 сек 5 сек 9 сек 27 сек 1.2 мин 6.5 мин

Объем используемой памяти (Мб, в среднем) 9.6 9.7 9.8 10.6 12.2 15.3

Таблица 3. Результаты эксперимента.

Результаты эксперимента подтвердили, что бОльшая длина последовательностей функций К улучшает способность метода обнаруживать ошибки. Но, при этом, уменьшает коэффициент сокращения набора тестов и увеличивает затраты ресурсов на проведение тестирования. Аналогично, меньшая длина последовательностей ухудшает способность метода обнаруживать ошибки, и, одновременно, увеличивает коэффициент сокращения набора тестов и уменьшает затраты ресурсов на проведение тестирования. Результаты показали, что при значениях К больше 6, таких как 10 и 15, использование метода становилось достаточно затратным: значительно возрастают временные затраты на проведение редукции, что, однако, не приводит к увеличению уровня обнаружения ошибок, так как коэффициент обнаружения ошибок уже достиг 100%. Также было замечено, что для тестируемых программ коэффициент обнаружения ошибок достигает 100% уже при К = 3, однако бОльшие значения К, такие как 6, добавляют «запас прочности» методу при незначительном увеличении затрат ресурсов.

В третьей главе приведены результаты апробации метода редукции набора тестов и программная реализация метода редукции.

Апробация разработанного метода редукции проводилась на задаче сокращения индустриального тестового набора LSB Application Battery. Тестовый набор LSB Application Battery используется в процессе

сертификации Линукс-подобных операционных систем на соответствие спецификации Linux Standard Base (LSB) и предполагает достаточно высокую степень интерактивного взаимодействия с пользователем. Для проведения апробации использовалась версия 3.1 набора LSB Application Battery, которая представляет собой коллекцию из 15 общеиспользуемых приложений. Проведение тестирования с помощью этой версии набора занимает около двух часов на машине с конфигурацией Intel Pentium 4-М CPU 2.00 GHz / 448 MB RAM.

При проведении апробации, в дополнение к основным характеристикам методов редукции, таким как коэффициент редукции набора тестов и коэффициент обнаружения ошибок, также был оценен выигрыш временных затрат на проведение тестирования, который дает использование сокращенного набора тестов при выполнении на нем тестируемого программного обеспечения. Результаты апробации предложенного метода на наборе LSB Application Battery представлены в Таблице 4:

Индикатор Исходный набор Сокращенный набор

Размер сокращенного набора (кол-во тестов) 81 9

Коэффициент сокращения 9 раз

Кол-во обнаруженных ошибок 6 6

Изменение уровня обнаружения ошибок 0%

Время выполнения 1 час 58 минут 10 минут

Коэфф. сокращения времени выполнения 11.8 раз

Время работы метода редукции 1 минута

Выигрыш по времени 1 час 47 минут /10.7 раз

Таблица 4. Результаты апробации метода.

Результаты апробации подтвердили высокую практическую ценность метода: в результате работы метода было достигнуто сокращение исходного тестового набора в 9 раз, что привело к сокращению времени тестирования с помощью сокращенного набора тестов в 11.8 раз (до 10 минут). Затраты на работу метода редукции составили 1 минуту, таким образом суммарная экономия времени от использования метода редукции составила 1 час 47 минут или 10.7 раз от времени тестирования с помощью исходного набора тестов. При этом способность тестового набора обнаруживать ошибки не уменьшилась: сокращенный тестовый набор обнаруживал столько же ошибок, сколько и исходный тестовый набор.

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

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

1. Архитектура программной реализации позволяет достаточно легко адаптировать реализацию метода для работы с программным обеспечением, выполняемым в различных операционных системах/средах выполнения, таких как Linux/UNIX, MS Windows, .NET, Java и др.;

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

3. Реализация модуля анализа взаимодействий позволяет собирать трассы взаимодействий интегрируемых модулей за один проход, во время

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

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

В заключении представлен обзор результатов, полученных в рамках

настоящей диссертационной работы.

Основные результаты работы

В работе были получены следующие основные результаты, которые

выносятся на защиту:

1. Разработана новая модель процесса взаимодействия модулей на основе метода «скользящего окна» по трассе вызовов интерфейсных функций;

2. Предложено и обосновано отношение эквивалентности между процессами взаимодействия модулей на основе предложенной модели и дано формальное доказательство его корректности;

3. Разработан новый метод редукции регрессионного тестового набора, основанный на сравнении моделей процесса взаимодействия, построенных по трассе вызовов интерфейсных функций;

4. Разработана экспериментальная система, реализующая метод редукции тестового набора.

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

Результаты диссертации опубликованы в работах:

[1] Кичигин Д.Ю. Метод редукции тестового набора для регрессионного интеграционного тестирования. // Журнал РАН «Программирование», Номер 5,2009, С. 57-69.

[2] Dmitry Kichigin. A Method for Test Suite Reduction for Regression Testing of Interactions between Software Modules. II In Proceedings of PSI'09, Novosibirsk, 2009. LNCS, Springer: Volume 5947/2010 pp. 177-184, 2010.

[3] D. Kichigin. Test Suite Reduction for Regression Testing of Simple Interactions between Two Software Modules. // In Proceedings of Spring Young Researchers Colloquium on Software Engineering (SYRCoSE 2007). Volume 2, ISP RAS. pp. 31-37,2007.

[4] Кичигин Д.Ю. Об одном методе сокращения набора тестов. // Сборник трудоцв ИСП РАН, том 13, часть 1, М: ИСП РАН, 2007, С.79-92.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡0О экз. Заказ № ЯЗ

ВВЕДЕНИЕ.

Регрессионное интеграционное тестирование.

Актуальность.

Цель работы.

Структура и краткое содержание работы.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ.

Редукция набора тестов для регрессионного интеграционного тестирования программного обеспечения.

Регрессионное тестирование программного обеспечения.

Выборочное регрессионное тестирование.

Классификация методов выборочного регрессионного тестирования.

Выборочное регрессионное интеграционное тестирование программного обеспечения.

Обзор методов редукции набора тестов в контексте задач регрессионного интеграционного тестирования.

Метрики адекватности тестовых наборов.

Методы, использующие метрики обнаружения ошибок.

Методы, использующие структурные метрики.

Выводы.

ГЛАВА 2. ПРЕДЛАГАЕМЫЙ МЕТОД.

Класс рассматриваемых взаимодействий и интеграционные ошибки.

Обоснование и формулировка метода.

Общая характеристика метода.

Модель взаимодействия между двумя модулями на тесте.

Алгоритм редукции набора тестов.

Отношение эквивалентности между моделями взаимодействий.

Адаптируемость метода для учета параметров других типов.

Оптимизация метода.

Сбор трасс взаимодействий.

Условия применения метода.

Методика применения метода.

Область применимости метода.

Экспериментальное исследование.

Организация экспериментального исследования.

Исследование основных характеристик метода.

Исследование адаптируемости метода для учета параметров функций других типов.

Оценка влияния размера окна на работу метода и оценка затрат ресурсов при работе метода.

Выводы.

ГЛАВА 3. АПРОБАЦИЯ НА ТЕСТОВОМ НАБОРЕ LSB APPLICATION

BATTERY.

Тестовый набор LSB Application Battery.

Экспериментальное исследование метода на задаче сокращения тестового набора LSB Application Battery.

Цели исследования.

Тестируемое взаимодействие.

Условия проведение эксперимента.

Проведение эксперимента.

Результаты.

Программная реализация.

Архитектура.

Схема работы.

Адаптируемость к другим средам выполнения и для учета других типов параметров.

Выводы.

РЕГРЕССИОННОЕ ИНТЕГРАЦИОННОЕ ТЕСТИРОВАНИЕ

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

Одним из основных процессов, направленным на обеспечение корректности взаимодействия модулей при создании и последующих модификациях программного обеспечения, является проведение интеграционного и, особенно, регрессионного интеграционного тестирования. Регрессионное интеграционное тестирование должно осуществляться регулярно в ответ на внесение модификаций в ПО и, в этом случае, способно надежно обеспечивать корректность интеграции модулей: Для проведения регрессионного интеграционного тестирования должны использоваться специализированные интеграционные тесты, целью которых является проверка взаимодействия интегрируемых модулей. Однако на практике создание таких тестов достаточно сложно и трудоемко, поэтому распространенным подходом является использование существующих регрессионных тестов, изначально созданных для модульного и системного тестирования. Такой подход позволяет сэкономить ресурсы на создании специализированных регрессионных интеграционных тестов, однако является неэффективным: так как используемые в этом случае регрессионные тесты изначально не создавались специально для интеграционного тестирования, на практике только часть таких запускаемых тестов тестирует взаимодействие между интегрируемыми модулями, а оставшаяся часть тестов работает «вхолостую», лишь потребляя ресурсы. Ситуация значительно усугубляется в случае регрессионного интеграционного тестирования крупных программных комплексов: как правило регрессионные тесты для такого программного обеспечения достаточно сложны и требуют больших ресурсов, что значительно увеличивает потери ресурсов на запуске тестов, не тестирующих требуемое взаимодействие между интегрируемыми модулями.

АКТУАЛЬНОСТЬ

Для решения обозначенной выше проблемы используется подход, известный как редукция набора тестов, и заключающийся в выборе из исходного набора подмножества тестов, специально фокусирующегося на тестировании межмодульных взаимодействий. Редукция набора тестов ставит своей целью отбор набора тестов меньшего размера для тестирования выбранного взаимодействия между модулями, но при этом, желательно, с такой же, как и у исходного набора тестов, способностью обнаруживать интеграционные ошибки в выбранном взаимодействии. Традиционный подход к редукции набора тестов заключается в «отсеивании» тестов из первоначального набора таким образом, чтобы сохранялся уровень его адекватности в терминах некоторого выбранного критерия адекватности. Для оценки адекватности набора тестов, большинство существующих методов используют метрики адекватности, основывающиеся на статическом анализе и/или инструментировании исходного текста ПО, что обусловливает их ограничения:

1. Непрактичность использования для программного обеспечения большого объема. Инструментирование исходного кода может быть достаточно нетрудоемким для программного обеспечения состоящего из нескольких модулей, однако инструментирование исходного кода для ПО, состоящего из нескольких тысяч модулей, гораздо более сложная и затратная процедура. Эта особенность делает редукцию набора тестов непрактичной для ПО большого объема [52].

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

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

ЦЕЛЬ РАБОТЫ

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

1. Исследовать виды взаимодействия между модулями ПО и типичные для этих видов интеграционные ошибки;

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

3. Разработать метод редукции регрессионного тестового набора, основанный на сравнении моделей процесса взаимодействия, построенных на информации, полученной при прогоне тестового набора;

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

СТРУКТУРА И КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Диссертационная работа состоит из 3 глав. В первой главе рассматривается понятие регрессионного тестирования, заключающегося в повторном тестировании программного обеспечения с целью убедиться, что внесенные изменения не привели к неожидаемым эффектам, и необходимость проведения регрессионного тестирования в процессе сопровождения программного обеспечения. Отмечается, что важной особенностью регрессионного тестирования является наличие существующего набора тестов. Формулируются принципы выборочного регрессионного тестирования и показывается перспективность этого подхода для повышения эффективности регрессионного тестирования, достигаемого вследствие уменьшения затрат ресурсов, требуемых для достижения целей регрессионного тестирования. Также приводится классификация методов редукции набора тестов для проведения выборочного тестирования, и рассматриваются принципы оценки таких методов. После этого подробно рассматриваются особенности выборочного тестирования при проведении регрессионного интеграционного тестирования с использованием бинарных программных компонент, в частности, делается вывод о том, что в реальных крупных системах встречается дополнительное ограничения на доступ к исходному коду таких компонент, что, в свою очередь, предъявляет дополнительные требования к методам редукции набора тестов. После этого приводится детальный обзор существующих методов редукции набора тестов для регрессионного интеграционного тестирования. Отмечается, что в литературе встречается мало методов редукции для интеграционного тестирования. Большинство методов редукции набора тестов для интеграционного тестирования является адаптацией существующих методов для модульного тестирования. Показывается, что используемые методами метрики покрытия основываются на анализе исходного кода, вследствие чего для работы методов редукции требуется наличие исходного кода тестируемого программного обеспечения. В результате показывается, что традиционные методы сокращения набора тестов оказываются неадекватны для случая интеграционного тестирования в условиях ограничений на доступ к исходному коду программного обеспечения.

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

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

Описание модели процесса взаимодействия начинается с определения основных используемых терминов: таких как понятие интерфейсной функции, трассы взаимодействия двух модулей на тестовом варианте, и последовательности интерфейсных функций длины К. Интерфейсными функциями называются функции, входящие в состав программного интерфейса модуля программного обеспечения. Трассой взаимодействия модулей А и В на тесте t называется последовательность записей, каждая из которых соответствует вызову интерфейсной функции модуля В модулем А при выполнении тестируемого программного обеспечения на тесте t. Последовательностью интерфейсных функций длины К называется любая непрерывная последовательность вызовов интерфейсных функций длины К, встречающаяся в трассе взаимодействия. После этого определяется модель процесса взаимодействия модулей на тесте t (далее по тексту модель взаимодействия) как множество всех возможных последовательностей длины К, встречающихся в трассе взаимодействия между модулями А и В на тесте t.

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

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

После этого приводится описание проведенной оптимизации метода редукции. Описанный выше метод редукции обладает вычислительной сложностью, максимальная оценка которой составляет: 0(Т2 х N2K х К), при этом максимальный объем памяти, используемой для хранения модели в памяти компьютера, составляет: 0(Г х NK х К), где: Т - количество тестов; К -размер окна; N - количество интерфейсных функций. Для улучшения этих показателей была проведена оптимизация метода, заключающаяся в том, что табличное представление модели взаимодействия было заменено древовидным, при котором модель взаимодействия представляется в форме дерева, где каждой последовательности вызовов интерфейсных функций соответствует путь в дереве от корня до одного из листовых узлов. Такое представление позволило уменьшить сложность алгоритма до О (Г2 х NK х log(A^) х К) , а

NK+X -N максимальный объем используемой памяти до 0(Т х —~—~—).

После описания метода редукции приводятся условия применения, методика применения, и область применимости предложенного метода.

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

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

Основные результаты диссертационной работы, выносящиеся на защиту, заключаются в следующем:

1. Разработана новая модель процесса взаимодействия модулей на основе метода «скользящего окна» по трассе вызовов интерфейсных функций;

2. Предложено и обосновано отношение эквивалентности между процессами взаимодействия модулей на основе предложенной модели и дано формальное доказательство его корректности;

3. Разработан новый метод редукции регрессионного тестового набора, основанный на сравнении моделей процесса взаимодействия, построенных по трассе вызовов интерфейсных функций;

4. Разработана экспериментальная система, реализующая метод редукции тестового набора.

Разработанный в работе метод редукции тестового набора значительно расширяет область применения методов редукции наборов тестов, делая их применимыми при регрессионном тестировании взаимодействий с участием готовых программных компонент, поставляемых без исходного кода. Практическая ценность предлагаемого метода доказана успешным применением метода для редукции набора тестов для регрессионного тестирования взаимодействий осуществляемых через интерфейсы функций со скалярными параметрами и указателями. Проведенный на примере вычислительной системы на базе распространенной операционной системы SUSE Linux Enterprise Desktop vl0.2 анализ структуры интерфейсов системного и прикладного программного обеспечения, показал, что доля таких интерфейсов составляет порядка 96% от общего числа программных интерфейсов, что подтверждает широкую область применения предлагаемого метода. Кроме того, проведенные исследования подтвердили, что данный метод также может быть успешно адаптирован к интерфейсам функций, содержащих не только скалярные параметры и указатели, но и любые другие параметры.

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

Данные результаты опубликованы в 4 печатных работах [83,84,85,86].

ЗАКЛЮЧЕНИЕ

1. Владимиров М.А. Критерии полноты тестового покрытия в генетических алгоритмах генерации тестов // Труды Института системного программирования РАН. Том 9. 2006. сс.57-66.

2. Епифанов Н.А. Методы Реализации Регрессионного Тестирования по Расширенным Тестовым Наборам // Диссертация на соискание учёной степени кандидата технических наук, Санкт-Петербургский Государственный Политехнический Университет, Санкт-Петербург, 2003.

3. Иванников В.П., Петренко А.К. Задачи верификации ОС Linux в контексте ее использования в государственном секторе // Труды Института системного программирования РАН. Ноябрь, 2006, сс. 9-14.

4. Кострикин А.И. Введение в алгебру. Основы алгебры // М. Наука. 1994. 320с.

5. Котляров В. П., Епифанов И. А., Некрасов А. О., Коликова Т. В. Основы современного тестирования программного обеспечения, разработанного на С# // СПб., СПбГТУ, Нестор, 2003, 86с.

6. Котляров В.П., Коликова Т.В. Основы тестирования программного обеспечения // М.: Интернет-Университет Информационных Технологий, БИНОМ. 2006. 285с.

7. Курош А.Г. Лекции по общей алгебре // Издание второе. М.Наука.1973. 400с.

8. Лаврищева Е.М., Петрухин В.А. Методы и средства инженерии программного обеспечения: Учебник // МФТИ (ГУ), Москва. 2006.

9. Липаев В. В. Тестирование программ // М., Радио и связь, 1986.

10. Липаев В. В., Позин Б.А., Штрик А.А. Технология сборочного программирования // Под ред. В.В.Липаева. М., Радио и связь, 1992.

11. Майерс Г. Надежность программного обеспечения (пер. с англ. под ред. В.ШКауфмана) //М.:Мир, 1980. 360с.

12. Майерс Г. Искусство тестирования программ (пер. с англ.) // М.: Финансы и Статистика, 1982. 178с.

13. Петренко А., Петренко О., Бритвина Е., Грошев С., Монахов А. Тестирование на основе моделей // Открытые Системы. #09, 2003, сс. 41-47.

14. Силаков Д. В. Текущее состояние и перспективы развития инфраструктуры LSB // Труды Института системного программирования РАН. 2007.

15. Шимаров В. А. Тестирование программ: цели и особенности инструментальной поддержки // Программное обеспечение ЭВМ / АН БССР, Институт математики, Минск, 1994, № 100, сс. 19-43.

16. Abdullah К., Kimble J.E.Jr., White L.J. Correcting for unreliable regression integration testing // ICSM 1995: pp. 232-241.

17. American National Standards Institute. Programming Language C. ANSI standard X3.159-1989 // ANSI, December 1989.

18. ANSI/IEEE Std 829-1998, IEEE Standard for Software Test Documentation // The Institute of Electrical and Electronics Engineers, New York, 1998.

19. ANSI/IEEE Std 610.12-1990, IEEE Standard Glossary of Software Engineering Technology // The Institute of Electrical and Electronics Engineers, New York, 1990.

20. Bentley W.G., Miller E.F. CT coverage initial results // Softw. Quality J. 2, 1, 1993. pp. 29-47.

21. Bible J., Rothermel G., Rosenblum D.S. A comparative study of coarse- and fine-grained safe regression test-selection techniques // ACM Transactions on Software Engineering and Methodology (TOSEM), v. 10 n.2, April 2001, p. 149183.

22. Budd T.A., Lipton R.J., Sayward F.G., DeMillo R.A. The design of a prototype mutation system for program testing. In Proceedings of National Computer Conference, 1978. pp. 623-627.

23. С library to perform Input/Output operations. http://www.cplusplus.com/reference/clibrary/cstdio/

24. Christmansson J., Chillarege R. Generation of an Error Set that Emulates Software Faults Based on Field Data// FTCS'26, Sendai, Japan, 1996, pp. 304313.

25. Cornett S., Code Coverage Analysis, 2002 http://www.bullseye.com/coverage.html

26. Cotroneo D., Natella R., Pecchia A., Russo S. An Approach for Assessing Logs by Software Fault Injection // Suppl. Proc. IEEE International Conference on Dependable Systems and Networks, 2009, A15-A20.

27. Delamaro M.E., Maldonado J.C., Mathur, A.P. Interface Mutation: an approach to integration testing // IEEE TSE, Vol. 27, No. 3, March 2001, pp.228-247.

28. DeMillo R.A., Lipton R.J., Sayward F.G. Hints on test data selection: Help for the practising programmer// Computer 11, April 1978. pp.34-41.

29. DeMillo R.A., Guindi D.S., McCracken W.M., Offutt A.J., King, K.N. An extended overview of the Mothra software testing environment // In Proceedings of SIGSOFT Symposium on Software Testing, Analysis and Verification 2, July, 1988. pp. 142-151.

30. Documentation for GNU Assembler 2.17, 2006. http://sourceware.org/binutils/docs-2.17/as/index.html

31. Duraes J.A., Madeira H.S. Emulation of Software Faults: A Field Data Study and a Practical Approach // IEEE Transactions on Software Engineering, Vol.32, No. 11, Nov. 2006, pp. 849-867.

32. Elbaum S., Malishevsky A.G., Rothermel G. Prioritizing test cases for regression testing // Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, Portland, Oregon, United States, August, 2000, pp. 102-112.

33. Filesystem Hierarchy Standard, http://www.pathname.com/fhs/

34. Forrest S., Hofmeyr S.A., Somayaji A., Longstaff T.A. A Sense of Self for Unix Processes // IEEE Symposium on Computer Security and Privacy, Los Alamos, CA, 1996, pp.120-128.

35. FSF/UNESCO Free Software Directory Website, GNU Binutils Collection of binary utilities, 2006. http://directory.fsf.org/GNU/binutils.html

36. GCCXML Website, http://www.gccxml.org/

37. Gettys J., Scheifler R.W. Xlib С Language X Interface, XWindow System Standard, X Version 11, Release 6.7. http://www.x.org/docs/Xl 1/xlib.pdf

38. GNU С Library, GNU Project, Free Software Foundation (FSF), Inc. http://ftp.gnu.org/gnu/glibc/

39. Goodenough, J. B. and Gerhart, S. L. Toward a theory of test data selection // IEEE Trans. Softw. Eng. SE-3 (June). 1975.

40. Gourlay, J. A mathematical framework for the investigation of testing // IEEE Trans. Softw. Eng. SE-9, Nov. 1983, pp. 686-709.

41. Harrold M.J., Soffa M.L. Selecting and Using Data for Integration Testing // IEEE Softw. 8, 2 (Mar. 1991), 1991, pp.58-65.

42. Harrold M.J., Gupta R., Soffa M.L. A methodology for controlling the size of a test suite // ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, July 1993, pp.270-285.

43. Hiller M., Christmansson J., Rimen M., An experimental comparison of fault and error injection // In Proceedings of the IEEE International Symposium on Software Reliability Engineering (ISSRE '98), 1998, pp. 369-378.

44. Hoftneyr S.A., Forrest S., Somayaji A. Intrusion Detection using Sequences of System Calls // Journal of Computer Security, 6, 1998, pp. 151-180.

45. Howden W. E. Reliability of the path analysis testing strategy // IEEE Trans. Softw.Eng. SE-2, Sept. 1976, pp. 208-215.

46. Hunt G., Brubacher D. Detours: binary interception of Win32 functions // Proceedings of the 3rd USENIX Windows NT Symposium, Seattle, WA, July 1999, pp. 135-143.

47. Java(TM) Virtual Machine Tool' Interface (JVM TI) http://java.sun.c0m/javase/6/d0cs/techn0tes/guides/jvmti/

48. Jin Z., Offutt J. Integration testing based on software couplings. // In Proceedings of the Tenth Annual Conference on Computer Assurance (COMPASS 95), Gaithersburg, MD: IEEE Computer Society Press, June 1995, pp. 13-23.

49. Jin Z., Offutt J. Coupling-based criteria for integration testing // The Journal of Software Testing, Verification, and Reliability, 8(3), September 1998, pp. 133154.

50. Jones J.A., Harrold MJ. Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage //IEEE Transactions on Software Engineering, vol. 29, no. 3, Mar. 2003, pp. 195-209.

51. Kim J. M., Porter A., Rothermel G. An empirical study of regression test application frequency // Proceedings of the 2000 International Conference on Software Engineering, 2000, pp. 126-135.

52. Kim Y.W. Efficient use of code coverage in large-scale software development // Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, IBM Press, 2003, pp. 145-155.

53. King K.N., Offutt A.J. A Fortran language system for mutation-based software testing // Softw. Pract. Exper. 21,7 (July), 1991, pp. 685-718.

54. Leung H., L. White. A study of integration testing and software regression at the integration level // Int. Conf. on Sofware Maintenance, (San Diego), 1990, pp. 290-301.

55. Leung H. K. N., White L, J. A cost model to compare regression test strategies // Proceedings of the Conference^ Software Maintenance, 1991, pp. 201 208.

56. Linux Standard Base Desktop Specification 3.1.0 // Free Standards Group. April 24, 2006. http://refspecs.linux-foundation.Org/LSB3.l.0/

57. Linux Standard Base (LSB) pages // The Linux Foulzehl elation http://www.linuxfoundation.org/en/LSB

58. Linux Standard Base Application Battery pages // The Linux FouLmL<3.ation http://www.linuxfoundation.org/appbat/

59. LSB Database Home pages // The Linux Fouceilelation http://ispras.linuxfoundation.org/index.php/LSBDatabaseHome

60. Ma X., He Z., Sheng В., Ye C. A Genetic Algorithm for Test-Suite Re<±Txcrtion // 2005 IEEE International Conference on Systems, Man and Cybernetics^ "Vol 1 Oct. 2005, pp: 133- 139.

61. Madeira H., Vieira M., Costa D. On the Emulation of Software F^ojQts by Software Fault Injection // Proc. Int'l Conf. Dependable Systems and N^srtrvvorks (DSN '00), 2000, pp. 417-426.

62. McCabe T.J. A complexity measure // IEEE Transactions on Software Engineering, SE-2, #4, 1976, p.308-320.

63. McMaster S., Memon A. Call Stack Coverage for Test Suite Reduction /V ICSM 21st IEEE International Conference on Software Maintenance (ICSM'O-ST^ 2005 pp.539-548.

64. McMaster S., Memon A., Call Stack Coverage for GUI Test-Suite Redxxction // Proceedings of the 17th International Symposium on Software Reliability Engineering, November, 2006, p.33-44.

65. Pietrek M. The .NET Profiling API and the DNProfiler Tool // MSDN IVTeigazine,

66. Dec. 2001, http://msdn.microsoftxoni/msdrmiag/issues/0l/l2/hood/defaTjtILl:.aspx

67. Rapps S., Weyuker E.J. Selecting Software Test Data Using Data. Flow Information // IEEE Transactions on Software Engineering, vol. II, no. -4э ДрГ 1985, pp. 367-375.

68. Rothermel, G. Efficient, effective regression testing using safe test selection techniques. Ph.D. Dissertation // Clemson University, Clemson, SC. 1996.

69. Rothermel, G., Harrold M. J. Analyzing regression test selection techniques // IEEE Trans. Softw. Eng. 22, Aug. 1996, pp. 529-551.

70. Rothermel G., Harrold M.J., von Ronne J., Hong C. Empirical studies of test-suite reduction // Journal of Software Testing, Verification, and Reliability, V. 12, no. 4, December, 2002.

71. Rountev A., Kagan S., Sawin J. Coverage criteria for testing of object interactions in sequence diagrams // In Fundamental Approaches to Software Engineering, LNCS 3442, 2005, pp. 282-297.

72. Shimarov V. A. Definition and quantitative estimation of testing criteria // Software Quality Concern for people. Proceedings of the Fourth European Conference on Software Quality. October 17-20, Basel, Switzerland, 1994, pp. 350 -360.

73. SUSE Linux Enterprise pages, www.novell.com/linux/

74. Warrender C., Forrest S., Pearlmutter B. Detecting Intrusions Using System Calls: Alternative Data Models // IEEE Symposium on Security and Privacy, IEEE Computer Society, Oakland, CA, 1999, pp. 133-145.

75. Willmor D., Embury S.M. A Safe Regression Test Selection Technique for Database-Driven Applications' // Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM'05), September 2005, pp.421-430.

76. Wong W.E., Horgan J.R., London S.A., Mathur A.P. Effect of test set minimization on faults detection effectiveness // Proceedings of the 17"' International Conference on Software Engineering, 1995, pp. 41 50.

77. X.Org Foundation. Releases / Download page. http://www.x.org/wiki/Releases/Download

78. Zhu H. Adequate Testing of Computer Software // An Online Book on Software Testing. August 1995, http://cms.brookes.ac.uk/staff/HongZhu/testbookweb/chOO.html.

79. Zhu H., Hall P.A.V., May J.H.R. Software Unit Test Coverage and Adequacy // ACM Computing Surveys, Vol.29, No.4, December 1997, pp.366-427.

80. Кичигин Д.Ю. О применении подходов Data Mining для обнаружения вторжений // Программные системы и инструменты. Тематический сборник № 4, ВМиК МГУ, 2003 год, сс. 122-134

81. Kichigin D. Test Suite Reduction for Regression Testing of Simple Interactions between Two Software Modules // In Proceedings of Spring Young Researchers Colloquium on Software Engineering (SYRCoSE 2007). Volume 2, ISP RAS, 2007, pp. 31-37.

82. Кичигин Д.Ю. Об одном методе сокращения набора тестов // Сборник трудов ИСП РАН. М: ИСП РАН, 2007, сс.79-92.

83. Кичигин Д.Ю. Метод редукции тестового набора для регрессионного интеграционного тестирования // Журнал РАН «Программирование», Номер 5, 2009, сс. 57-66.

84. Dmitry Kichigin. A Method for Test Suite Reduction for Regression Testing of Interactions between Software Modules // Springer-Verlag, Lecture Notes in Computer Science, Volume 5947, 2010, pp. 177-184.