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

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

БАЗИН АЛЕКСАНДР СЕРГЕЕВИЧ

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ТЕСТИРОВАНИЯ ПРОГРАММНЫХ КОМПЛЕКСОВ НА ОСНОВЕ ПРИНЦИПА ДЕКОМПОЗИЦИИ

Специальность 05.13.01. - «Системный анализ, управление и обработка информации (в науке и промышленности)» по техническим наукам

АВТОРЕФЕРАТ

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

1 3 ЛЕК 2012

Нижний Новгород, 2012 г.

005057114

005057114

Работа выполнена на кафедре «Вычислительные системы и технологии» федерального государственного бюджетного образовательного учреждения высшего профессионального образования Нижегородский государственный технический университет им. Р.Е.Алексеева.

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

Ломакина Любовь Сергеевна

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

Федосенко Юрий Семенович

кандидат технических наук Волков Владимир Георгиевич

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

и диагностики технических систем, г. Нижний Новгород («НИЦ КД»).

Защита диссертации состоится «27» декабря 2012 года в 11-00 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан «27» ноября 2012 года.

Ученый секретарь диссертационного совета

A.C. Суркова

Общая характеристика работы

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

Вопросам измерения, контроля, обеспечения надежности и качества программных средств посвящено большое количество работ В.В. Липаева, П.П. Пархоменко, П.А. Правилыцикова, В.И. Сагунова, Я.Я. Осис, G. Myers, C.V. Ramamoorthy и ряда других отечественных и зарубежных ученых.

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

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

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

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

Задачи работы.

Достижение поставленной цели предполагает решение следующих задач:

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

- разработка базовой модели программного комплекса;

- разработка диагностической модели программного комплекса;

- программная реализация разработанных алгоритмов тестирования;

- применение полученных научных результатов на практике.

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

Научная новизна работы состоит в следующем:

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

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

3. Разработаны алгоритмы декомпозиции и локализации ошибок в программном комплексе, которые повышают эффективность тестирования комплекса по сравнению с известными методами.

Практическая ценность и рекомендации по использованию результатов.

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

4

обеспечение высокого уровня надежности производимых программных продуктов.

Реализация результатов работы.

Разработанные в диссертационной работе модели и автоматизированная система тестирования внедрены и используются в производственном процессе одного из проектов компании «МЕРА НН», что подтверждается актом о внедрении. Они также используются в учебном процессе с магистрантами направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». № государственной регистрации 01.2009.00405 от 28.01.09 - Н. Новгород: НГТУ), выполненной в рамках НИОКР «Диагностические и информационно - поисковые системы» (№ регистрации 01201252337, интернет-номер И111112195013, руководитель работы Ломакина J1.C.).

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

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

1.Базовая модель программного комплекса, описывающая программный комплекс как систему;

2.Диагностическая модель программного комплекса, включающая методы и алгоритмы решения задач тестирования комплекса;

3.Метод независимого и параллельного тестирования модулей комплекса, основанный на использовании утилиты CUTE.

5

Апробация работы. Основные положения диссертации и результаты диссертационной работы представлялись и докладывались на следующих научных конференциях:

-Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011)» (Нижний Новгород);

-XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010);

-XIV Международной конференции «Фундаментальные и прикладные проблемы приборостроения и информатики» (Москва, 2011);

-XI Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2012);

-XVI Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2012).

Публикации. По теме диссертации опубликовано 12 работ, в том числе 3 статьи в рецензированных изданиях, свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложений. Общий объём работы 116 страниц текста, содержащего 22 рисунка и 7 таблиц. Список литературы содержит 96 наименований.

Содержание работы

Во введении дана общая характеристика работы, обоснована актуальность

выбранной темы и сформулированы цель и задачи исследования.

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

Во второй главе (Базовая модель программного комплекса) предложена базовая (математическая) модель представления программного комплекса как системы.

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

Многие задачи анализа программ, возникающие при оптимизации, трансляции, тестировании и т.д., значительно упрощаются, если их рассматривать на граф-моделях. В основе моделей лежит управляющий граф программы. Орграф С = (X, И) называется управляющим графом (р-графом, графом переходов), если выполнены следующие условия:

1) граф С не содержит параллельных дуг;

2) в множестве вершин графа выделена одна вершина х - вход графа;

3)в множестве вершин графа выделена хотя бы одна вершина I - выход графа;

4) каждая вершина хе X достижима из входа

5) каждая вершина хе X достигает выхода V,

Каждой программе можно поставить в соответствие два графа, определяемые двумя типами связей, существующими в программе: управляющими (логическими) и информационными. Между операторами (2 и 5 существует управляющая связь, если оператор (2 передает управление оператору 5 (возможно, при выполнении некоторых условий). Между операторами <2 и Я существует информационная связь, если оператор Б использует значения некоторых переменных, определяемых оператором £?.

На основании этих связей строятся соответствующие ориентированные графы - управляющий граф и информационный граф. Вершины графов соответствуют операторам программы. Дуги управляющего графа соответствуют управляющим связям, а дуги информационного графа -

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

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

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

Для примера рассмотрим программу, содержащую следующие пользовательские процедуры:

1. main

2. cliooseBehaviour

3. waitForMessage

4. sendTraffic

5. handleReceivedMessage

6. handleMgmtMessage

7. handleDataMessage

Передача управления в данной программе между процедурами происходит

следующим образом:

1. "main"-> "chooseBehaviour";

2. "chooseBehaviour" -> "waitForMessage";

3. "chooseBehaviour" -> "sendTraffic";

4. "waitForMessage" -> "handleReceivedMessage";

5. "handleReceivedMessage" -> "handleMgmtMessage";

6. "handleReceivedMessage" -> "handleDataMessage";

7. "handleMgmtMessage" -> "ImndleRoutinglnfoMessage";

8. "handleMgmtMessage" -> "handleSystemReq";

9. "handleDataMessage" -> "sendAck";

10. "handleRoutinglnfoMessage" -> "sendAck";

8

5. handleRoutinglnfoMessage

9. handleSystemReq

10. sendAck

11. se?id2Network

12. sendData

13. sendMgmtMessage

11. "НапсИеЗуметИес)" -> "скоозеВектюиг";

12. "$епс!Аск" -> "яепй2Ые1\\югк";

13. "зепсКгафс"-> "БепсЮша";

14. "хепйТга/Ас" -> "sendMgmtMessage";

15. "хепеЮаШ" -> "$епс12Ые1ъюгк";

16. "sendMgmtMessage" -> "5еп(12МеП\>огк";

17. "$еп(12Ме1могк" -> "скоозеВекауюиг";

Управляющий граф для данной программы с учетом предложенной степени детализации приведен на рис. 1.

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

Рис. 1. Управляющий граф программы

Алгоритм 2.1

1) Для синтаксического анализа структуры программного комплекса необходимо установить компиляторы GCC и Perl;

2) Исходный код программного комплекса компилируется с помощью GCC с опцией "-dr", результатом данной операции являются дамп-файлы с расширением RTL (Register Transfer Language). Дамп-файлы (RTL файлы) содержат информацию о структуре программного комплекса в определенном формате, которая может быть использована для построения управляющего графа комплекса.

3) Информация о вызовах процедур комплекса, содержащаяся в RTL файлах, извлекается с помощью скрипта, написанного на языке программирования Perl.

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

Рассмотрим работу Алгоритма 2.1 на следующем примере:

1) Программа состоит из 3 файлов: main.c, client.c, server.c.

2) Исходный код программы компилируется с помощью GCC с опцией "-dr":

# gee -dr main.c client.c server.c

Результатом данной операции являются следующие файлы: main.c.Ol.rtl, client.c.Ol.rtl, server.c.Ol.rtl.

3) Информация о вызовах процедур программы, содержащаяся в RTL файлах, извлекается с помощью Perl скрипта:

# rtl2callgraph main.c.01 .rtl client.c.Ol.rtl server.c.Ol.rtl

Результатом этой операции является диаграмма вызовов процедур в программе: digraph callgraph {

"main" -> "chooseBehaviour" [style=solid]; "chooseBehaviour" -> "waitForMessage" [style=solid]; "chooseBehaviour" -> "sendTraffic" [style=solid]; "waitForMessage" -> "handleReceivedMessage" [style=solid]; "kandleReceivedMessage" -> "handleMgmtMessage" [style=solid];

10

"IiandleReceivedMessage" -> "handleDataMessage" [style=solid]; "handleMgmtMessage" -> "liandleRoutinglnfoMessage" [style=solid]; "handleMgmtMessage" -> "handleSystemReq" [style=solid]; "handleDataMessage" -> "sendAck" [style=solid]; "handleRoutinglnfuMessage" -> "sendAck" [style=solid]; "handleSystemReq" -> "chooseBehaviour" [style=solid]; "sendAck" -> "send2Network" [style=solid]; "sendTraffic" -> "sendData" [style=solid]; "sendTraffic" -> "sendMgmtMessage" [style-solid]; "sendData" -> "send2Network" [style=solid]; "sendMgmtMessage" -> "send2Network" [style=solid];

"send2Network" -> "chooseBehaviour" [style=solid]; }

4) Полученная информация о вызовах процедур в программе определяет управляющий граф программы. Управляющий граф для данного примера изображен на рис I.

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

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

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

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

11

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

Рассмотрим задачу разбиения управляющего графа программного комплекса С=(Х,1Г) на модули ), Xj с Л' ,(/,€£/, г"е /=/1,2,...,/г/, где

п — количество модулей, на которое разбивается программный комплекс. Совокупность модулей Р(О) называется разбиением графа С—(Х,1}), если VGi е Р(С)[в, * 0 Л/е/.

е * => X, П X; =

=Осци> п и}, = о V и, п и} = и у )], и ,■<?,.=б (1)

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

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

В выражении (1) множество I! у является подмножеством ребер и ц е V,

попадающих в разрез (сечение) между модулями С, и графа (7.

Обозначим \lfjj \= Ку и назовем его количеством соединительных ребер модулей G¡ и графа <7. Количество соединительных ребер всех модулей комплекса равно:

Задачей разбиения графа С=(Х,и) является нахождение такой совокупности модулей, чтобы количество соединительных ребер графа С удовлетворяло заданному критерию оптимальности.

Пусть граф б разбит на С[,С2,...С„ модулей. В соответствии с этим разбиением множество ребер и графа С можно представить в виде

(3)

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

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

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

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

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

процедурами /7 и /2, а «популярность» процедуры /4 равна единице, т.к. вызывается только процедурой/2.

Рис. 2 «Популярность» процедур в комплексе

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

Алгоритм декомпозиции программных комплексов (Алгоритм 3.1) работает следующим образом:

1) Строим граф «популярности» процедур комплекса - взвешенный направленный граф С = (X, Ц) с множеством вершин X = 5, где 5 - множество процедур комплекса и направленные дуги множества и обозначают передачу управления между процедурами в комплексе. Вес каждой дуги равен «популярности» вызываемой процедуры (т.е. «популярности» процедуры, соответствующей вершине назначения дуги).

2) Вычисляем значение с, равное средней «популярности» процедур в

п

2>

комплексе. На первой итерации алгоритма с ■

, где п - количество

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

3) Удаляем вершины в графе «популярности» процедур, для которых «популярность» соответствующей процедуры выше выбранной средней «популярности» процедур с, образуя граф С.

4) В полученном графе С находим вершины, для которых полустепень захода равна нулю.

5) В графе С находим множества вершин, достижимых из каждой вершины с нулевой полустепенью захода, если достижима хотя бы одна вершина найденное множество вершин и вершина из которой они достижимы объединяются в модуль. Вершины, которые выделяются в модули, удаляются из графа С и С. Если не достижима ни одна вершина из найденной вершины, найденная вершина удаляется из графа С.

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

Продемонстрируем пример работы алгоритма 3.1.

1) Рассмотрим граф «популярности» процедур С, изображенный на рис. 3.

"17" 13

временно удаляем вершины в графе С, для которых «популярность» соответствующей процедуры выше выбранной средней «популярности»

2) Вычисляем значение средней «популярности» процедур с=2 (

) и

Рис. 3. Граф «популярности» процедур в

процедур с=2. Удаляем вершины 2 и 13, так как «популярность» соответствующих процедур равна трем. Получаем граф С (рис. 4).

Рис. 4. Граф С, полученный на первой итёрации алгоритма 3)В полученном графе С находим вершины, для которых полустепень захода равна нулю, такими вершинами являются 1,3 и 10. В графе С находим множества вершин, достижимых из найденных вершин 1,3 и 10. Из вершины 1 не достижима ни одна вершина графа С, удаляем эту вершину из графа С. Из

С

вершины 3 достижимы вершины 4,5,6,7,8,9 - объединяем вершины 3,4,5,6,7,8,9 в модуль и удаляем их из графов G и С. Из вершины 10 достижимы вершины 11 и 12 -объединяем вершины 10,11,12 в новый модуль и удаляем их из графов G и G'. Граф С'пуст.

4) В результате предыдущих шагов в графе G осталось всего 3 вершины -1,2,13 (рис. 5). В графе С находим вершины, для которых полустепень захода равна нулю, такими вершинами являются 1 и 13. В графе G находим множества вершин, достижимых из найденных вершин 1 н 13. Из вершины 1 достижима вершина 2, объединяем вершины 1 и 2 в модуль и удаляем из графа G. Осталась единственная нерассмотренная вершина 13, из нее не достижима ни одна вершина графа G, но, тем не менее, мы выделяем ее в отдельный модуль.

Рис. 5. Граф С, полученный на последней итерации алгоритма

Таким образом, 1раф «популярности» С был разбит на 4 модуля (рис. 6).

G

v

Рис. 6. Результат разбиения графа на модули

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

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

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

Для автоматизированной генерации тестов предлагается использовать утилиту CUTE (а Concolic Unit Testing Engine for С), разработанную на факультете The Department of Computer Science университета University of Illinois at Urbana-Champaign, являющуюся наилучшим решением проблемы модульного тестирования с использованием автоматизированной технологии генерации тестов. Утилита CUTE доступна на сайте http://osl.cs.uiuc.edu/~ksen/cute. Данная утилита реализует символьное выполнение программ. Также CUTE позволяет обозревать все возможные пути исполнения программы и предоставляет статистику покрытия кода тестируемой программы тестами.

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

В четвертой главе (Вычислительный эксперимент. Практическая реализация) приведен пример практического применения предложенного

18

алгоритма тестирования программных комплексов. Проводится вычислительный эксперимент над программным комплексом Open SIP, который представляет собой открытую реализацию протокола установления сеанса (Session Initiation Protocol - SIP), встроенного во многих IP телефонах.

Реализация данного комплекса на языке программирования С доступна на сайте http://www.gnu.org/sofuvare/osip/osip.htinl. Для тестирования была использована версия продукта 2.2.1, исходный код комплекса состоит примерно из 30,000 строк программного кода. Проводилось тестирование программного кода, отвечающего за кодирование и декодирование сообщений SIP протокола, данный фрагмент кода состоит из 57 процедур (-10,500 строк программного кода).

Построив управляющий граф для данного комплекса, можно увидеть, что 44 из 57 процедур мало «популярны» - вызываются лишь одной или двумя другими процедурами, 8 процедур вызываются 3-5-ю другими процедурами, и 5 процедур очень «популярны», вызываются 7-20-ю разными процедурами.

Алгоритм 3.1 выделил 7 модулей в данном комплексе. Далее тестирование полученных модулей проводилось утилитой CUTE, которая генерировала до 101/0 различных входных данных для каждого модуля, в результате чего было обнаружено несколько ошибок в реализации протокола SIP, которые могли повлечь к неожиданному завершению работы комплекса. Покрытие исходного кода комплекса тестами составило 85% для данного примера.

Для подтверждения эффективности разработанного алгоритма декомпозиции программных комплексов был проведен следующий эксперимент. Описанный выше программный комплекс был разделен на модули разными алгоритмами (случайное разбиение на N частей (rN на рис. 7), алгоритм Kernighan-Lin (KL на рис. 7), алгоритм Fiduccia-Mattheyses (FM на рис. 7), алгоритм 3.1 (срЗ на рис. 7)) и далее полученные модули тестировались программой CUTE, генерировалось 1000 различных входных данных для каждого модуля. В процессе тестирования велась статистика тестового покрытия исходного кода.

Результат эксперимента можно представить в виде графика:

к 0.9 -

я • срЗ

н

§0.7

♦ РМ

о '•А

♦кь

"ВТ""'

£0,6

* гЗб ф г46 г3.1 * г41

♦ гб

г21

"4"г26

«0.4

ю '

О $ Ю И 21) 25 30 35 40 45 5Ь ¿5 ¿0 Количество выделенных модулей

Рис. 7. Тестовое покрытие исходного кода комплекса

♦ г!6

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

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

В заключении изложены основные научные и практические результаты диссертационной работы.

Приложение содержит

• акт о внедрении разработанной автоматизированной системы тестирования программных комплексов в производственный процесс компании «МЕРА НН»,

• акт о внедрении результатов диссертационной работы в учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева,

• свидетельство о государственной регистрации программы для ЭВМ.

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

В ходе теоретических и экспериментальных исследований, выполненных в

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

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

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

3) Разработана диагностическая модель программного комплекса, включающая методы и алгоритмы решения задач тестирования, а именно:

• алгоритм разбиения программного комплекса на модули;

• метод независимого и параллельного тестирования модулей комплекса, основанный на использовании утилиты CUTE.

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

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

6) Результаты диссертационной работы внедрены в производственный процесс компании «МЕРА НН» и учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева

Список опубликованных работ по теме диссертации Публикации в рецензируемых изданиях

[1] Базин, A.C. Тестирование программных комплексов на основе принципа декомпозиции [Текст] / A.C. Базин // Журнал «Вестник Нижегородского государственного университета». - Нижний Новгород - 2011. - №4. - С. 185189.

[2] Базин, A.C. Иерархическая декомпозиция программных комплексов с целью их тестирования [Текст] / JI.C. Ломакина, A.C. Базин II Журнал «Системы управления и информационные технологии» / ИЛУ РАН, ВГТУ, № 2.2 (48), М.Воронеж, 2012. С. 263-268.

[3] Базин, A.C. Автоматизированное тестирование программных комплексов [Текст] / A.C. Базин // Труды НГТУ. Серия «Системы обработки информации и управления» - Т. 97. - Вып. 4. - Н.Новгород: НГТУ. - 2012. - С. 73-81.

Публикации в других изданиях

[4] Базин, A.C. Диагностика программных систем на основе принципа декомпозиции [Текст] / A.C. Базин // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009)», 17 апреля 2009 г. - Н. Новгород: НГТУ, 2009. - С.265.

[5] Базин, A.C. Многоуровневый декомпозиционный подход при диагностировании программных комплексов [Текст] / A.C. Базин // Материалы 15-й Международной открытой научной конференции «Современные проблемы информатизации». - Воронеж: ВГТУ, 2010. - С. 409-412.

[6] Базин, A.C. Разработка модели и алгоритма тестирования программных комплексов на основе декомпозиционного подхода [Текст] / A.C. Базин // Материалы Международной научно-технической конференции

«Информационные системы и технологии (ИСТ-2010)», 23 апреля 2010 г. -Н.Новгород: НГТУ, 2010. - С.300.

[7] Базин, A.C. Автоматизированное тестирование программных комплексов [Текст] / A.C. Базин // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2011)», 22 апреля 2011 г. - Н.Новгород: НГТУ, 2011. -С.316.

[8] Базин, A.C. Алгоритмы декомпозиции программных комплексов для их тестирования [Текст] /Л. С. Ломакина, A.C. Базин // Научные труды XIV Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения и информатики. Книга «Информатика и информационная безопасность», 3-7 октября 2011 г. - Москва: МГУПИ, 2011.-С.68-73.

[9] Базин, A.C. Тестирование программных комплексов [Текст] / A.C. Базин, Л.С. Ломакина // Материалы XI Международной научно-технической конференции «Будущее технической науки», 18 мая 2012 г. — Н. Новгород: НГТУ, 2012. - С.27-28.

[10] Базин, A.C. Системный подход в тестировании программных комплексов [Текст] / Л.С. Ломакина, A.C. Базин II Труды XVI Международной научно-практической конференции «Системный анализ в проектировании и управлении», 27-29 июня 2012 г. - Санкт-Петербург: СПб. ГПУ, 2012. - С. 128129.

[11] Базин, A.C. Диагностика технических и программных систем с использованием современных информационных технологий [Текст] (научный руководитель Л.С. Ломакина) / А.Н. Вигура, A.C. Базин, В.П. Губернаторов и др. // Отчет по НИР № государственной регистрации 01.2009.00405 от 28.01.09 -Н. Новгород: НГТУ. - 127 с.

[12] Базин, A.C. Декомпозиция программных комплексов / Л.С. Ломакина, A.C. Базин // Свидетельство об официальной регистрации программ для ЭВМ № 2011614382. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 3 июня 2011 г.

Подписано в печать 21.11.2012. Печать офсетная. Уч.-изд.

Формат 60x84 '/16. Бумага офсетная, л. 1,0. Тираж 80 экз. Заказ 739.

Нижегородский государственный технический университет им. P.E. Алексеева.

Типография НГТУ. Адрес университета и полиграфического предприятия: 603950, г. Нижний Новгород, ул. К. Минина, 24.