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

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

САВИН Александр Николаевич

ФОРМИРОВАНИЕ ТЕСТИРУЮЩИХ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ СЕТЕЙ ПЕТРИ-МАРКОВА

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

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

Тула 2009

о 3 ИДО 2309

003472015

Работа выполнена в ГОУ ВПО «Тульский государственный университет»

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

ЛАРКИН Евгений Васильевич

Официальные оппоненты:

- Ильин Анатолий Александрович, доктор технических наук, профессор.

- Евсюков Владимир Васильевич, кандидат технических наук, доцент.

Ведущее предприятие: ЗАО «Тульская лаборатория информационных и вычислительных технологий»

Защита состоится 50 июня 2009 года в 12— часов на заседании диссертационного совета Д 212.271.07 при ГОУ ВПО «Тульский государственный университет» (300600, Тула, проспект им. Ленина, 92) в аудитории 9-101.

С диссертацией можно ознакомиться в библиотеке Тульского государственного университета (300600, Тула, проспект им. Ленина, 92).

Автореферат разослан <?Э мая 2009 г.

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

доктор технических наук Данилкин Ф.А.

ВВЕДЕНИЕ

Актуальность темы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фундаментальной научной основой дайной диссертации послужили работы К. Петри, Дж.Питерсона, В.Е. Котова в области моделирования, A.A. Маркова, Д. Кнута в области теории алгоритмов, Е.С. Венгцель в области исследования случайных процессов, Б. Бейзера и Дж. Майерса в области тестирования.

Задачи исследований.

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

2. Описание особенностей и свойств случайных процессов, протекающих в тестируемой системе для определения ее параметрических характеристик.

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

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

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

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

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

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

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

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

4. Разработан метод тестирования программных комплексов в виде «черного ящика» и «стеклянного ящика» на основании модели в виде сети Петри-Маркова.

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

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

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

Положения, выносимые на защиту.

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

2. Формализация моделей тестирующих компонент в виде СПМ применительно к элементам схем алгоритмов программ, а также к сложным программным комплексам, таким как СУБД и многопользовательские системы обработки информации.

3. Алгоритм исследования эргодического свойства полумарковского процесса, протекающего в типовых СПМ, моделирующих тестирование исследуемых систем.

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

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

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

Апробация работы. Основные положения диссертации докладывались на конференциях и семинарах профессорско-преподавательского состава кафедры «Робототехника и автоматизация производства» ГОУ ВПО «Тульский государственный университет» в период с 2005 по 2008 год, на Всероссийской конференции инновационных проектов аспирантов и студентов по приоритетному направлению «Информационно-телекоммуникационные системы (Москва, ГНИИ ИТТ «Информика», 2005).

По теме диссертации опубликовано 10 работ, включенных в список литературы, в том числе: тезисы докладов на всероссийской конференции, 9 статей.

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

Во введении определены объект и предмет исследования, методы, используемые в диссертации, сформулированы основные положения, выносимые на защиту.

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

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

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

математический объект, есть множество 5 = .....5У} правил, каждое из

которых имеет вид: «-Д, = 0. Элементы множества

[ва,в1,...,вт\ являются атомами. Атом имеет следующий вид: Р(/„/2,...,/,), где Р - предикатный символ, а /,,«' = Пп - термы. Терм - это либо переменная,

либо константа, либо составной терм /(/,.....где / - функциональный

символ, а /,,./ = Пг - термы.

Запрос является целью выполнения программы. Запрос является атомарным предикатом или конъюнкцией атомарных предикатов и имеет синтаксис: <-С, л...дС„(т>0), где С,,/ = ПЗй - атомарные предикаты.

Семантика программы определяется через подстановки. Подстановка -это функция, действующая из множества X переменных в множество Т термов программы: ®:Х -*Т, при этом каждой переменной еX ставится в соответствие терм /, е Т.

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

1. Вычислимость атомов. Если е£,./'=0 для каждого атома

В, =Р{Л{1,>4..........'Л-,Л(',.'2.....0) из условия Р:Л'->{0,1} следует

/ХМ.....VI-ГХ, (1)

где К,Я - некоторые множества.

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

ЗВ1,В1,\^йт\йу<.т\В1<.В1 У! = ОГ, (2)

то В, - избыточное правило.

3. Конечность запросов. Для У<2=<-С, л...лС/ л...лС, .....£?„

так, что

й = б и ) является выводимым из <2„(/ = 1,2,...) и число и<°о. (3) В противном случае программа будет зацикливаться при вычислении запроса

е.

4. Непротиворечивость основной модели программы. Множество фактов безошибочной программы не должно быть противоречивым. Если для фактов 5, и

5,0^ = 0,3 ВшглВо;*0, (4)

то данная модель программы противоречива.

5. Использование допустимого объёма памяти. Если для программы выделен фиксированный объём памяти то для памяти, необходимой для переменных программы должно выполняться условие:

(5)

1=1

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

6. Обязательная инициализация всех переменных программы перед использованием в вычислении запросов. Для любого терма вида

/\х1,х1.....являющегося составляющим некоторого правила программы

5 существует подстановка ©: X -> Т, такая что

0{/(^,дг1(...,дг„))= /(©(л;-,©(*.)), и &(х,)е 7\/ = Пл. (6)

Указано, что модель безошибочной программы есть недостижимый идеал. Однако классификация свойств безошибочной программы позволяет определить классы ошибок как следствий нарушения приведенных свойств (1-6).

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

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

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

функцией над множеством переменных {Х^Хг,..,Хк}: 5(Л'„Л',.....Х„),

X, ={*,!,ха,...,хи },/ = ПЛ\ где Хц - переменные тестируемой программы. Регрессия при модификации программы заключается в том, что после внесения изменений результат работы модифицированной программы должен отличаться от результата исходной программы только в части исправления ошибок:

5(Х1,Х1..........Х„),

где 8 - исходная, а - модифицированная программа,

.....*/(;))* .....*до) .....•х/(,))е

где 5(5') - множество ошибочных значений программы.

Стрессовое тестирование, где для программы 5(Х„Хг.....Хы)

формируется вектор (лг,(,),дг2(0.....лг,0)), где каждое значение

хЛ) < т1п(лг7(1)^ > тах^,)). Критерием тестирования будет являться условие:

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

Тестирование «черного ящика», заключающееся в том, что при

некотором наборе параметров (*,(,), *2<о.....результат работы программы

5(^),л:2(1),...,дгд,)) с точностью до допустимой вероятности />,,0<д<1 принадлежит заранее определенному множеству значений:

■*»&)•••■■••*/(.))е >

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

Тестирование «стеклянного ящика», которое с математической точки зрения является реализацией принципа декомпозиции для метода тестирования «черного ящика». В данном случае имеется множество *■ = {/;./,..•■./.} отдельных задач подлежащих тестированию. Для каждой составляющей /, применимы те же методы, что используются для тестирования «черного ящика»:

). )>-,-*;(,)) е £■,(/)

Л^ко-^М.....*/(,))б£,(/г)-

/■(■*К<)>*2<0.....*/(,))'6 Е, (/,)

Сформулированы проблемы и недостатки современных методов реализации приведённых способов тестирования, существенными из которых являются отсутствие методов для моделирования параллелизма и отсутствие параметрических временных составляющих для анализа процессов, протекающих в исследуемых системах.

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

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

Сделан вывод о необходимости моделирования и управления тестовыми программами.

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

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

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

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

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

2. Формулировка методики построения модели тестирующей программы по модели тестируемой программы. Определение структурных и параметрических составляющих тестирующего процесса.

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

4. Построение методики определения начальных вероятностных характеристик тестирующей.

5. Определение конструктивных особенностей построения тестирующих программ из построенной модели.

Во втором разделе представлен метод моделирования тестирующих программ с использованием сетей Петри-Маркова.

Показано, что сеть Петри-Маркова, моделирующая систему тестирования, включет следующие структурные элементы:

1. Позиция а1 еЛ- оператор или последовательность операторов в алгоритме программы. В частности, позиция может моделировать путь 5 = в схеме алгоритма от стартового до одного из конечных операторов.

2. Примитивный переход z|eZ, /¿(/А)) = До,))=1 - переход к выполнению следующего оператора в алгоритме. Кроме того, в тестирующей программе примитивный переход - контрольная точка, которая применяется для измерения параметров тестируемой программы при завершении независимой тестовой проверки. Параметрами могут быть время или характеристики тестируемой программы, например: количество затрачиваемых ресурсов вычислительной системы. Если ¿{Ог (<!,))> 1, то примитивный переход позволяет осуществить выбор одной из тестовых траекторий в зависимости от заданной вероятности.

3. Элементарная подсеть Петри-Маркова (ЭППМ) П1(п)сП:Уг, еП,(п), - граф, эквивалентный функционально законченному участку алгоритма тестируемой прораммы, в том числе и всему алгоритму.

4. Тестовая траектория - некоторый путь £«(5„5,......¿г) в ЭППМ,

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

5. Элементарная подсеть Петри-Маркова Ц(п)~я,, упрощенная до позиции - тестовая траектория, при прохождении которой определенному набору некоторого класса входных параметров ставится в соответствие ровно один набор результирующих данных. Данная подсеть, функционально эквивалентна тестовой проверке.

6. Маркированная позиция ау е А, Да,) = 1 - активное состояние одного из операторов в данном фрагменте алгоритма.

7. Маркированная ЭППМ - ЭППМ, у которой хотя бы одна позиция маркирована: Г11(п): За/ е П,(п), ) = 1.

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

9. Непримитивный переход гуе2, VДол(г7))> 1-элемент, позволяющий моделировать синхронизацию или распараллеливание тестовых траекторий. Для синхронизирующего перехода е 2, //(/^(гЛ>1лДо<,(2у))<Д/я(ху)) дополнительно определяется функция

логических условий .....^;(<]);(г1)б(0,1) - булева функция, истинное

значение; которой разрешает продолжение потока тестирования. Такой переход позволяет моделировать, с одной стороны, декомпозицию тестовых проверок на элементарные составляющие, а с другой - тестирование параллельного выполнения нескольких траекторий. Распараллеливающий переход б 7, Д0Л(г,))>1лД/Л(г;))< Д^,)) функционально эквивалентен одновременному выполнению нескольких тестовых проверок.

Вектор состояний - вектор Е= ..., ..., &/), моделирующий текущее состояние процесса тестирования. Значения компонент вектора состояний е {0,1} и равны единице, если соответствующий компонент (позиция или непримитивный переход) в текущий момент маркирован, и нулю в противном случае. Дерево, узлами которого являются различные связанные между собой векторы состояний, определяет все возможные траектории в модели тестирующей программы.

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

Л/)=Лехр(-Л),

где А - среднее количество ошибок в единицу времени работы тестируемой программы.

Плотность распределения времени выполнения п тестовых проверок определяется и -кратной сверткой функции плотности распределения времени для одной проверки:

Л')=/Л') (7)

>

где <р(/)*у/(г)= |*9>(г)с(/-г)(/г -свертка.

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

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

/(')=£/-/<№'). (8) 1-1,

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

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

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

/ N+1 \ /ш / м

V "-1 ) /-1 I »=1

Составляющие выражения (9) определяются следующим образом.

1.1

1*1

/-м- Илш^м-

(П)

1=1 ,.1

. 1е(Т . т \

(12)

(13)

Приведены модели тестирования итераций, вероятностные характеристики которых сводятся к закономерностям (9-12).

Приведены исследования эргодического свойства полумарсовских процессов протекающих в сетях Петри-Маркова.

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

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

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

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

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

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

2. Булева функция логических условий открытия каждого непримигивного перехода сети должна быть представлена в виде ДНФ.

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

Третий раздел содержит описание способов применения аппарата сетей Петри-Маркова в задачах тестирования сложных программах комплексов.

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

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

п=^,г,1(г\А{г)}, л = Ц.....а„ь,я), г-{г„ъ.*,,*.}.

/(;:,) = Е,0{1Ь)= {я,,...,в,}, /Ы={о,.....«ДО^)-*, <14)

/(*> к.....а-'\0{ф Я, )=л,о(г,)=0,

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

Время выполнение одного тестового прогона в сети (14) определяется выражением:

где вероятности полушагов из позиций в,,...,а, в переходы г1 и гх определяются значениями дл и соответственно: =1У/ = С7, а /,(/) и

определяются выражениями (10) и (11) соответственно.

В случае тестирования «чёрного ящика» в структуру модели (14) добавляется параллельно-последовательный запуск моделей точек верификации, которые определяются в следующем виде: п=й..г,/(г),о(г)}; А = {а0,<ч,а1}, г =

7(г4Ь0,/(г,) = Д,/(г,И«а'}, 0(гь)--а,0(г1) = а',0(г,)= 0. 05)

Метод тестирования с помощью построенных моделей определяется следующей последовательностью шагов.

1. На стадии подготовки выполняется определённое программой и методикой испытаний число итераций N с эталонными данными и формируется статистика времён выполнения каждой тестируемой функции программного комплекса. Гистограммы Г,= Пт времени прохождения каждой точки верификации аппроксимируются с помощью законов распределения и для каждой позиции сети Петри-Маркова задается значение плотности распределения времени.

2. Определяется число итераций тестов с различными тестовыми данными, как функция от эталонного количества тестовых прогонов /(V). В простейшем случае /{Ы)=Ы.

3. Тесты запускаются на выполнение.

4. Если на j -й итерации модель попадает в состояние блокировки, то фиксируется вектор разметки а = (й(я),..., §(„),..., £/(„)). Определяется точка верификации, для которой Т, ¿{¡Г^Аж) в случае превышения времени ожидания. Иначе - выполнение пункта 7.

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

6. Если при выполнении тестов нештатная ситуация не повторяется, то предположение об ошибочности программного кода отвергается и выполняется возврат к пункту 3. Иначе переход к пункту 12.

7. Собирается статистика о времени пребывания перехода г. сети (14) в состоянии активности (Дг,)> 0).

8. Если обнаруживаются отклонения по времени от эталонных прогонов, то переход к пункту 9. Иначе переход к пункту 12.

9. Если отклонения повторяются регулярно, то делается предположение о необходимости корректировки исходной гистограммы времени выполнения; в статистические данные включаются результаты уже проведённых тестов и законы распределения корректируются. Переход к пункту 3.

10. Для каждого выявленного вектора состояний 2 заново выполняются тесты с соответствующим ему вектором параметров

(а,,аг.....аи) и проверяются гипотезы о неоптималыюм выполнении

программного кода.

11. Если на основании собранной во время тестов статистики гипотезы принимаются достоверными, то программное обеспечение признается ошибочным и возвращается на доработку.

12. Формируется протокол тестирования, фиксируются наборы начальных данных, при которых ошибки были выявлены.

Реализация описанного подхода позволяет автоматизировать процесс тестирования и уменьшить размерность задачи анализа результатов тестирования.

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

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

Приведен алгоритм запуска сети Петри-Маркова, реализующей данные тесты.

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

Показано, что решение задачи аппроксимации функции плотности распределения /(/) некоторой функцией д{иа,,...,ал) состоят в нахождении

параметров оптимальных по критерию минимального значения

ошибки аппроксимации и сводится к решению системы уравнений

XpSM

....."Л/Л^сг,.....ajMltiJ*

5а, ; " во,

..........

5а, { " да.

относительно а,. Ошибка аппроксимации в этом случае будет составлять минимальное значение е^.

На практике, параметры а,.....а1.....а, закона ijs{i,ai,...,ar...,a,),

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

?>(',«,.....а,.....а„)=Аехр(-Ж),

причем при Л=const выражения для композиций плотностей распределения получаются наименее трудоемкими.

Сами составляющие плотностей также являются экспоненциальными законами

/,(')=^ехР(~ f*A

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

чг <"/ _1

Y'Jj^f'V

где pt - вес соответствующего экспоненциального закона распределения.

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

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

В качестве тестируемой системы выбрана система контроля и обработки электронных платежных документов.

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

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

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

Система тестирования описана с помощью сети Петри-Маркова. Выделены необходимые элементы сети для имитационного моделирования.

Алгоритм, реализующий имитационное моделирование, описан в терминах тестируемой системы.

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

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

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

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

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

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

Результат внедрения разработанной методики в промышленную систему позволяет сформулировать следующие выводы.

1. При использовании методов моделирования систем тестирования с помощью аппарата сетей Петри-Маркова возрастает степень автоматизации тестов, что позволяет выполнить большее число тестов.

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

3. Существенно сокращается время, затрачиваемое на комплексное тестирование.

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

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

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

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

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

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

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

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

:5. Разработан метод моделирования систем автоматизированного тестирования с применением аппарата СПМ.

в. Предложены принципы декомпозиции модели тестирования для обеспечения распределения, распараллеливания процесса тестирования.

7. Разработаны модели в виде СПМ для тестирования отдельных компонентов профаммного обеспечения.

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

9. Создан метод тестирования распределенных процессов, представляемых в виде «черного и стеклянного ящика» для распределенных задач л систем управления реляционными базами данных.

10. Результаты диссертационной работы использованы в системе автоматизированного тестирования учетно-операционной системы РАБИС-2, эксплуатируемой в 37 регионах России, что позволило увеличить на 8% количество обнаруженных ошибок без функционального расширения тестов.

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

1. Савип А.Н. Принципы моделирования и построении систем автоматизированного тестирования параллельных процессов на примере сферы электронных расчетов. ВАК. // Известия ТулГУ. Сер. Технические науки. Вып.2. - Тула: ТулГУ, 2008. С. 306-31)9.

2. Котова Н.А., Савин А.Н. Модель конкуренции экономических субъектов // Приборы и управление. Вып. 4. - Тула: ТулГУ, 2006. С. 108 -112.

3. Ларкин Е.В., Савин А.Н. Моделирование процесса тестирования управляющих программ // Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. - Тула: ТулГУ, 2006. - С. 6 - 12.

4. Савин А.Н. Анализ возможностей применения сетей Петри для моделирования сложных систем // Приборы и управление: Сборник статей молодых ученых ТулГУ. - Тула: ТулГУ, 2004. С. 97-100.

5. Савин А.Н. Использование сетей Петри-Маркова в тестировании программных комплексов И Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. - Тула: ТулГУ, 2006. - С. 146 - 150.

6. Савин А.Н. Моделирование распределенного тестирования про1раммных комплексов(ПК) // Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. - Тула: ТулГУ, 2006. - С. 117-122.

7. Савин А.Н. Моделирование электронного обмена между кредитными организациями с помощью сетей Петри-Маркова // Приборы и управление. Вып. 4. - Тула: ТулГУ, 2006. - С. 188 - 195.

8. Савин А.Н. Описание процесса конкуренции экономических субъектов с помощью сетей Петри-Маркова // «Известия ТулГУ». Серия: Вычислительная техника. Информационные тенологаи. Системы управления. Том 1. Вып. 2. Системы управления. - Тула: ТулГУ, 2005.

9. Савин А.Н. О процессах, протекающих в сетях Петри-Маркова // Приборы и управление. Вып. 4. - Тула: ТулГУ, 2006. - С. 188 - 195.

Ш.Савин А.Н. Использование сетей Пегри-Марком в нагрузочном тестировании// Тез. докл. Всероссийской конференции инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» / Под ред. А.О. Сергеева. -М.: ГНИИ ИТТ «Информиха», 2005. - С. 115.

Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать ¿5 05 Формат бумаги 60x84 1/16 . Бумага офсетная. Усл.-печ. л. i Уч.-изд. л. <, С Тираж ЮС экз. Заказ C2.S Тульский государственный университет 300600, г. Тула, пр. Ленина, 92 Отпечатано в издательстве ТулГУ 300600, г. Тула, ул. Бовдина, 151

ВВЕДЕНИЕ.

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

1.1. Введение.

1.2. Принципы и методы проектирования программного обеспечения.

1.3. Современные проблемы разработки программного обеспечения.

1.4. Классификация типов тестирования ПО.

1.5. Обзор методов подготовки тестовых данных.

1.6. Обзор моделей, применимых к построению тестирующих программ.

1.7. Постановка задачи исследований.

1.8. Выводы.

2. Моделирование тестирующих программ.

2.1. Определение структурных составляющих сети Петри-Маркова в терминах задач тестирования.

2.2. Взаимосвязь между пространством параметров и тестирующей моделью.

2.3. Тестирование ввода данных.

2.4. Последовательный и параллельный подход к тестированию линейной последовательности операторов.

2.5. Тестирование предикатных функций.

2.6. Тестирование итераций в программе.

2.7. Свойства полумарковских процессов в однопереходных СПМ, моделирующих тестирующие программы.

2.8. Исследование процессов в типовых подсетях Петри-Маркова, используемых при моделировании тестирующих программ.

2.9. Выводы.

3. Построение моделей тестирования для сложных программных комплексов с помощью сетей Петри-Маркова.

3.1 Построение тестирующей модели с формированием дерева покрытия

3.2 Комплексная модель тестирующей программы.

3.3 Методика имитационного моделирования работы тестируемого ПО с применением аппарата СПМ.

3.4 Моделирование распределенного тестирования программных комплексов (ПК).

3.5 Общая методика применения сетей Петри-Маркова к задаче тестирования.

3.6 Аппроксимация композиции плотностей законом распределения.

4. Система автоматизированного тестирования программного комплекса обеспечения электронных расчетов.

4.1. Структура тестируемого комплекса.

4.2. Схема тестирующего комплекса.

4.3. Тестирование информационной безопасности.

4.4. Комплексное автоматизированное тестирование.

Актуальность темы.

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

В этой связи главенствующую роль в процессе создания программных средств начинает играть система их тестирования. Фактически, автоматизированная тестирующая система на отдельный программный продукт может значительно превосходить его по набору и сложности решаемых задач. Кроме этого, специфичность проблем, возникающих на этапе тестирования, обуславливает создание новых подходов к их формализации и математических методов их решения. [7, 16, 24] С другой стороны все это усиливает потребность в формировании новых подходов в технологиях проектирования программного обеспечения (ПО).

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

Параметрами программных средств, подлежащими тестированию, являются: область значений, область определения, быстродействие, объемы памяти, устойчивость, изменяемость, масштабируемость, переносимость, надежность и защищенность. [99,106]

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

Приведенные утверждения показывают необходимость построения математической модели системы автоматизированного тестирования [82], покрывающей большую часть (до 80 %) процессов, реализованных с помощью программных средств, что существенно повысит качество программного обеспечения.

Математическая модель должна иметь высокую степень приближения к тестируемой системе [29]. Кроме того, если назначение тестируемой системы заключается в обработке некоторого потока данных, то для повышения производительности целесообразно использовать метод распараллеливания входного потока, следовательно, исследуемая система обладает свойством параллелизма [8]. Параллелизм может наблюдаться при распределенном тестировании одного программного комплекса при проведении испытаний, при проверке многопользовательской работы с тестируемым продуктом, а также при проведении нагрузочных испытания для оценки устойчивости программного комплекса к нагрузкам [77, 85].

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

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

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

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

В качестве математического аппарата диссертационной работы выбрана структурно-параметрическая модель, называемая сетью Петри-Маркова [25, 26, 40, 41, 42, 43, 45], которая позволяет оценить временные характеристики параллельных процессов и построить программу и методику испытаний для сравнения ожидаемых и полученных в результате тестирования выходных данных. Кроме того, данная модель позволяет не только строить алгоритм работы тестируемой системы, но и исследовать свойства случайных процессов, протекающего в ней.

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

Фундаментальной научной основой данной диссертации послужили работы К. Петри, Дж.Питерсона, В.Е. Котова в области моделирования, A.A. Маркова, Д. Кнута в< области теории алгоритмов, Е.С. Вентцель в области исследования случайных процессов, Б. Бейзера и Дж. Майерса в области тестирования.

Задачи исследований.

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

2. Описание особенностей и свойств случайных процессов, протекающих в тестируемой системе для определения ее параметрических характеристик.

3. Создание методов, позволяющих представить взаимодействие моделируемых процессов в тестируемой системе в виде сети Петри-Маркова, расчет характеристик модели, исследование структурно-параметрических свойств построенной модели.

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

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

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

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

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

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

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

4. Разработан метод тестирования программных комплексов в виде «черного ящика» и «стеклянного ящика» на основании модели в виде сети Петри-Маркова.

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

Методы моделирования апробированы на примере системы автоматизированного тестирования электронных расчетов, которая реализована в виде конечного программного продукта на платформе Microsoft .Net 2.0.

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

Положения, выносимые на защиту.

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

2. Формализация моделей тестирующих компонент в виде СПМ применительно к элементам схем алгоритмов программ, а также к сложным программным комплексам, таким как СУБД и многопользовательские системы обработки информации.

3. Алгоритм исследования эргодического свойства полумарковского процесса, протекающего в типовых СПМ, моделирующих тестирование исследуемых систем.

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

Реализация и внедрение результатов. Предложенные в диссертации методы реализованы автором при разработке системы автоматизированного тестирования учетно-операционной системы региональной автоматизированной банковской информационной системы РАБИС-2.

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

Апробация работы. Основные положения диссертации докладывались на конференциях и семинарах профессорско-преподавательского состава кафедры «Робототехника и автоматизация производства» ГОУ ВПО «Тульский государственный университет» в период с 2005 по 2008 год, на Всероссийской конференции инновационных проектов аспирантов и студентов по приоритетному направлению «Информационно-телекоммуникационные системы (Москва, ГНИИ ИТТ «Информика», 2005).

По теме диссертации опубликовано 10 работ, включенных в список литературы, в том числе: тезисы докладов на всероссийской конференции, 9 статей.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов и заключения, изложенных на 133 страницах машино

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработан метод моделирования систем автоматизированного тестирования с применением аппарата СПМ.

6. Предложены принципы декомпозиции модели тестирования для обеспечения распределения, распараллеливания процесса тестирования.

7. Разработаны модели в виде СПМ для тестирования отдельных компонентов программного обеспечения.

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

9. Создан метод тестирования распределенных процессов, представляемых в виде «черного и стеклянного ящика» для распределенных задач и систем управления реляционными базами данных.

10. Результаты диссертационной работы использованы в системе автоматизированного тестирования учетно-операционной системы РАБИС-2, эксплуатируемой в 37 регионах России, что позволило увеличить на 8% количество обнаруженных ошибок без функционального расширения тестов.

1. Абдуллаев Д.А., Амирсаидов У.Б. Моделирование локальных вычислительных сетей с учетом вероятностно-временных характеристик // Автоматика и телемеханика. 1994. - № 3. С. 151-160.

2. Берж X. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.-319 с.

3. Васильев В.В. и др. Система специального математического обеспечения для моделирования параллельных процессов. // Управляющие системы и машины, 1987, № 5. -С. 50 55.

4. Васильев В.В., Кузьмук В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем. — Киев: Наукова Думка, 1990. 212 с.

5. Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2-е изд., стер. - М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 208 с. - (Пробл. науки и техн. прогресса).

6. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969. - 576 с.

7. Вирт. Н. Алгоритмы и структуры данных. М.: Мир, 1989. — 360 с.

8. Воеводин В.В. Математические модели и методы в параллельных процессах. — М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 296 с.

9. Гинзбург С. Математическая теория контекстно-свободных языков. -М.: Мир, 1970.-367 с.

10. Глушков. В.М., Летичевский A.A. Теория дискретных преобразователей // Избранные вопросы алгебры и логики. Новосибирск: ИМ СО АН СССР, 1973.-С. 5-39.

11. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980.-519 с.

12. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. — М. Радио и связь, 1983. — 272 с.

13. Гордеев A.B., Молчанов А.Ю. Применение сетей Петри для анализа вычислительных процессов и проектирования вычислительных систем: Учебное пособие. Л.: ЛИАП, 1988. - 78 с.

14. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения.— Москва: Мир, 1988. — 253 с.

15. Гэри Кобб, Крис Браун, Роберт Калбертсон. Быстрое тестирование. — М. Издательство «Вильяме», 2002. 384 с.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982. - 419 с.

17. Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. — М.:Мир, 1985. 332 с.

18. Джон Дж. Кемени, Дж. Лори Снелл. Конечные цепи Маркова. М., 1970.-272 с.

19. Дж. Хопкрофт, Р. Мотвани, Дж.Ульман. Введение в теорию автоматов, языков и вычислений. . М. Издательство «Вильяме», 2002. — 473 с.

20. Дэвенпорт Д. ,Сирэ И. ,Турнье Э. Компьютерная алгебра. —М.: Мир,1991.

21. Ершов А.П. Сведение задачи экономии памяти при составлении программ к задаче раскраски вершин графов // Докл. АН СССР. 1962. - Т.142, №4

22. Ершов А.П. Современное состояние теории схем программ // Проблемы кибернетики: Сб. статей. Вып. 27. — М.: Наука, 1973. С. 87 - 110.

23. Зыков A.A. Теория конечных графов. — Новосибирск: Наука, 1969. —543 с.

24. Игнатьев В.М., Ларкин Е.В. Анализ производительности ЭВМ: Учеб. пособие —Тул. гос. техн. ун-т. Тула, 1994. 104 с.

25. Игнатьев В.М., Ларкин Е.В. Временные характеристики алгоритмов в системах с прерываниями // Проектирование ЭВМ. Рязань: РГРТА. 1994. - С. 29 - 40.

26. Игнатьев В.М., Ларкин Е.В. Сети Петри-Маркова. Учеб. пособие. — Тул. гос. ун-т. Тула, 1997. — 163 с.

27. Канер Сэм и др. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений: Пер. с англ./Сэм Канер, Джек Фолк, Енг Кек Нгуен. К.: Издательство «ДиаСофт», 2001. - 544 с.

28. Касьянов В.Н. Методы оптимизации программ. Новосибирск: НГУ. 1984. 92 с.

29. Кауфман В.Ш. Языки программирования. Методические рекомендации М.00.279-87. М.: МГУ, НПО "Центрпрограммсистем": Калинин, 1988. -290 с.

30. Киндлер Е. Языки моделирования. — М.: Энергоатомиздат, 1985. —375 с.

31. Кнут Д. Искусство программирования на ЭВМ. Т. 2, Получисленные алгоритмы. — Москва: Мир, 1977.

32. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. — М.: Мир, 1969.

33. Королюк B.C., Турбин А.Ф. Полумарковские процессы и их приложения. Киев: Наукова думка, 1976. - 184 с.

34. Котова H.A., Савин А.Н. Модель конкуренции экономических субъектов // Приборы и управление. Вып. 4. Тула: ТулГУ, 2006. С. 108-112.

35. Котов В.Е., Сабельфельд В.К. Теория схем программ. — М.: Наука. Гл. ред. физ.-мат. лит., 1991. 248 с.

36. Котов В.Е. Сети Петри. /В.Е. Котов — М.: Наука. Главная редакция физико-математической литературы, 1984 — 160 с.

37. Котов В.Е. Теория параллельного программирования: прикладные аспекты // Кибернетика. 1974. - №1. - С. 1-16; №2. - С. 1-18.

38. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М.: Мир, 1978. - 432 с.

39. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов, М., «Энергия», 1970, 400с.

40. Ларкин E.B. Имитационное моделирование отказов-восстановлений с применением сетей Петри-Маркова // Вестник компьютерных и информационных технологий. № 12. - 2006. - С. 35 - 38.

41. Ларкин Е.В. К вопросу о расчете временных характеристик сетей Петри-Маркова // Известия ТулГу. Сер. Вычислительная техника. Автоматика. Управление. Т. 1. Вып. 1. Вычислительная техника. Тула: ТулГУ, 1997. - С. 68-75.

42. Ларкин Е.В. Моделирование параллельных систем одного класса // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 6. Вып. 3. Информатика. Тула: ТулГУ, 2000. - С. 92-97.

43. Ларкин Е.В. Некоторые случаи «соревнований» в многопроцессорных системах // Алгоритмы и структуры систем обработки информации. Тула: Тул-ГТУ, 1994.-С. 26-28.

44. Ларкин Е.В., Савин А.Н. Моделирование процесса тестирования управляющих программ // Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. Тула: ТулГУ, 2006. - С. 6 - 12.

45. Ларкин Е.В., Сабо Ю.И. Сети Петри-Маркова и отказоустойчивость авионики. Тула: Тул. гос. ун-т., 2004. - 208 с.

46. Ларкин Е.В. Сети Петри-Маркова для моделирования параллельных процессов // Приборы и приборные системы: Тезисы докладов. Тула: ТулГТУ, 1994.-С. 41.

47. Лескин A.A., Мальцев П.А., Спиридонов A.M. Сети Петри в моделировании и управлении. -Л.: Наука, 1989. -133 с.

48. Литвин В.Г., Ададышев В.П., Винниченко А.И. Анализ производительности мультипрограммных ЭВМ. — М.: Финансы и статистика, 1984. 159 е., ил.

49. Лорин Г. Распределенные вычислительные системы. М.: Радио и связь, 1984.-296 с.

50. Майерс Дж. Надежность программного обеспечения. -М.: Мир, 1987. -360 с.

51. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1985.-323 с.

52. Макконнелл С. Совершенный код. Мастер-класс / Пер. с англ. — М.: Издательско-торговый дом «Русская редакция»;СПб.: Питер, 2005.-896 стр.: ил.

53. Марков A.A. Теория алгоритмов // Труды Матем. ин-та им. В .А. Стеклова АН СССР, 1954. Т. 42. - 376 с.

54. Мартынюк В.В. Об анализе графа переходов для операторной схемы // ЖВМиМФ, 1965.-Т. 5, №2.-С. 298-310.

55. Мендельсон Э. Введение в математическую логику и теорию алгоритмов. -М., 1985.

56. Нариньяни A.C. Теория параллельного программирования: формальные модели // Кибернетика. 1974. - №3. - С. 1-15; №4. - С. 1-14.

57. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ/ Под ред. А.П. Ершова. — М.: Радио и связь, 1988. — 256 с.

58. Пийль Е.И. Матричное представление и объединение сетей Петри. // Сб.: Управление ресурсами в интегральных сетях. -М.: Наука, 1991. -С. 72 82.

59. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ.- М.: Мир, 1984. 264 е., ил.

60. Прангишвили И.В., Виленкин С .Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983. -312 с.

61. Рамбо Дж., Блаха М. UML 2.0 Объектно-ориентированное моделирование и разработка. 2-е изд. — СПб.: Питер, 2007. — 544 е.: ил.

62. Роббинс Дж. Отладка приложений для MS.NET и MS Windows. Русская Редакция; 2004. 736 с.

63. Роджерс С. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972, 624 с.

64. Савин А.Н. Анализ возможностей применения сетей Петри для моделирования сложных систем // Приборы и управление: Сборник статей молодых ученых ТулГУ. Тула: ТулГУ, 2004. С. 97-100.

65. Савин А.Н. Описание процесса конкуренции экономических субъектов с помощью сетей Петри-Маркова // «Известия ТулГУ». Серия: Вычислительная техника. Информационные тенологии. Системы управления. Том 1. Вып. 2. Системы управления. — Тула: ТулГУ, 2005.

66. Савин А.Н. Моделирование электронного обмена между кредитными организациями с помощью сетей Петри-Маркова // Приборы и управление. Вып. 4. Тула: ТулГУ, 2006. - С. 188 - 195.

67. Савин А.Н. О процессах, протекающих в сетях Петри-Маркова // Приборы и управление. Вып. 4. Тула: ТулГУ, 2006. - С. 188 - 195.

68. Савин А.Н. Использование сетей Петри-Маркова в тестировании программных комплексов // Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. Тула: ТулГУ, 2006. - С. 146 - 150.

69. Савин А.Н. Моделирование распределенного тестирования программных комплексов(ПК) // Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Т. 2. Вып. 3. Системы управления. Тула: ТулГУ, 2006. - С.117-122.

70. Савин А.Н. Принципы моделирования и построения систем автоматизированного тестирования параллельных процессов на примере сферы электронных расчетов. ВАК. // Известия ТулГУ. Сер. Технические науки. Вып.2. — Тула: ТулГУ, 2008. С. 306-309.

71. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычислительных систем / Под ред. О.И. Авена. М. : Наука, 1991. - 256 с.

72. Сильвестров Д.С. Полумарковские процессы с дискретным множеством состояний. М. Сов. Радио, 1980. - 272 с.

73. Сосонкин B.JL, Клепиков В.И. Принцип подчиненного управления в логических системах управления // Приборы и системы управления. 1995, № 12, с. 16—18.

74. Стерлинг JL, Шапиро Э. Искусство программирования на языке Пролог. М.: Мир, 1990. - 334 с.

75. Тадао Мурата. Сети Петри: Свойства, анализ, приложения. ТИИЭР, т. 77, № 4, апрель, 1989, -С. 41 85.

76. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. — М.: Советское радио, 1974. 200 с.

77. Фостер К. Ассоциативные параллельные процессоры. М.: Энергоиз-дат, 1981.-240 с.

78. Харари Ф. Теория графов. М.: Мир, 1973.-300 с.

79. Хоар Ч. Взаимодействующие последовательные процессы. М.:Мир, 1989.-264 с.

80. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974.-312 с.

81. Цанов В.А., Ташев Т.Д. Вопросы перехода от SDL-схем к сетям Петри при проектировании распределенных информационно-управляющих систем. // Сб.:. Управление ресурсами в интегральных сетях. -М.: Наука, 1991. -С. 83 94.

82. Шеннон Р. Имитационное моделирование систем искусство и наука. / Пер. с англ. под ред. Е.К. Масловского. М.: «Мир», 1978. - 418 с.

83. Шень А. Программирование. Теоремы и задачи. М.: МЦНМО, 2004, 296 е.: ил.

84. Ширяев А.Н. Вероятность. -М.: Наука, 1989. 576 с.

85. Элементы параллельного программирования/В.А. Вальковский, В.Е. Котов, А.Г.Марчук, H.H. Миренков. М.: Радио и связь, 1986. - 392 с.

86. Языки и параллельные ЭВМ. Москва: Наука. 1990. серия Алгоритмы и алгоритмические языки. 93 с.

87. Agarwal R. and Tanniru M., "A Petri-net approach or verifying the integrity of production systems", Int. J. Man-Machine Studies, vol. 36, no. 3, pp. 447 468, 1992.

88. Agerwala T. Putting Petri Nets to work // Computer. N 12. 1979. - Pp. 85-94.

89. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Reading, MA: Addison-Wesley. 1983. 417 p.

90. Backus J. Can Programming Be Liberated from von Neyman Style? A Functional Style and Its Algebra of Programs CACM, 1978, 21, n.8, P. 613-641.

91. Basili, V. R., and B.T. Perricone. Software errors and Complexity: An Empirical Investigation. Communications of the ACM 27, no.l (January). 1984 Pp 42 -52.

92. Brown A. R., and W.A. Sampson. Program Debugging. New York, NY: American Elsevier. 1973. — 317 p.

93. Cockburn, Alistair. Writing Effective Use Cases. Boston, MA: Addison-Wesley. 2000.- 278 p.

94. Conte S.D., Dunsmore H.E., and Shen V.Y. Software Engineering Metrics and Models. Menlo Park, CA: Benjamin. Cummings. 370 p.

95. Dunn Robert H. Software Defect Removal. New York, NY: McGraw-Hill. 1984.-357 p.

96. Feldbrugge F. Petri net overview 1986 // Lect. Notes Comput. Sci. 1987. Vol 255.-Pp. 20-61.

97. Ghosh S. Some comments on timed Petri nets // AFCET Journees sur les Resseaux de Petri. Paris: AFCET, 1977. - Pp 213-226.

98. Gorla N., Benander A.C., Benander B.A. Debugging Effort Estimation Using Software Metrics. IEEE Transactions on Software Engineering. SE-16, no. 2 (February), 1990. Pp 223-231.

99. Hasan Jeffrey, Kenneth Tu. Performance Tuning and optimizing ASP .Net Applications. Apress, 2003. 320 p.

100. Hassapis G. High level Petri nets modeling and analysis of VME-based multiprocessors // Microprocessors and microprogramming. -N. 4. 1993. - Pp 195204.

101. Hetzel Bill. The Complete Guide to Software Testing, 2d Ed. Wellesley, MA: QED Information Systems, 1988. 373 p.

102. Holiday M.A., Vernon M.K. A generalized Petri net model for performance analysis // IEEE Transactions on Software Engineering. Vol. 13. - 12. — 1987.-Pp. 1297-1310.

103. Jensen K. Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. —'Monographs in Theoretical Computer Science. — Springer- Verlag, 1992-1997.-320 p.

104. Kruchten Philippe. The Rational Unified Process: An Introduction, 2d Ed., Reading, MA: Addison-Wesley, 2000. 732 p.

105. Liu N.K. and Dillon Т., "An approach towards the verification of expert systems using nu-merical Petri nets", Int. J. of Intelligent Systems, vol. 6, pp. 255 -276, 1991.

106. Microsoft Corporation. Тестирование производительности Web-приложений Microsoft .Net/ Пер. с англ. — M.: Издательско-торговый дом «Русская редакция», 2003. 352 е.: ил.

107. Murata Т. Petri nets, marked graphs and circuit system theory // IEEE Circuits and System Society Newsletter. N.3. 1977. Pp. 2-12.

108. Myers Glenford J. The Art of Software Testing. New York, NY: John Wiley & Sons, 1979.-390 p.

109. Ntafos S.C., Hakimi S.L. On structured digraphs and program testing // IEEE Transactions on Computers. Vol. C-30. - N. 1. - 1981. - Pp. 67-71.

110. Nutt G. Evaluation Nets for Computer Systems Performance Analysis. FJCC PRESS, 1972, Vol. 41, Pt. 1, pp. 279 286.

111. Oswald H., Esser R., Mattmann R. An Environment for Specifying and Executing Hierarchical Petri Nets // IEEE 12th International Conference on Software Engineering, Nice. — IEEE, 1990. Pp 43-50.

112. Petri C.A. Introduction to general net theory // Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1980. - Pp. 251-260.

113. Schulmeyer G. Gordon. Zero Defect Software. New York, NY: McGraw-Hill, 1990.-217 p.

114. Sifakis J. Use of Petri nets for performancr evaluation // Proceedings of the third International Workshop on Modeling of Computer Systems. Amsterdam: TIWMCS. 1977. -Pp 75-93.

115. Tackett Buford D., Buddy Van Dören. Process Control for Error Free Software: A Software Success Story, IEEE Software, May, 1999. 143 p.

116. Whittaker James A. What Is Software Testing? And Why Is It So Hard? IEEE Software, January, 2000. Pp 70-79.

117. Youngs Edward A. Human Errors In Programming. International Journal of Man-Machine Studies 6, 1974. Pp 361-376.

118. Zahniser Richard A. A Massively Parallel Software Development Approach. American Programmer, January, 1992. Pp 34-41.