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

УДК 004.054

005004670

V

Старолетов Сергей Михайлович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

- 1 ДЕК 2011

Новосибирск 2011

005004670

Работа выполнена в ФГБОУ ВПО «Алтайский государственный технический университет им. И.И. Ползунова»

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

Крючкова Елена Николаевна

Защита состоится 26 декабря 2011г. в 15.00 на заседании диссертационного совета ДМ 003.032.01 в Институте систем информатики им. А.П. Ершова Сибирского отделения РАН по адресу: 630090, Новосибирск, пр. Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИСИ СО РАН (пр. Академика Лаврентьева, 6).

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

доцент, доктор технических наук Рояк Михаил Эммануилович

доцент, кандидат физико-математических наук Рубан Анатолий Альбертович

Ведущая организация:

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

Автореферат разослан ноября 2011 г.

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

к. ф.-м.н. Мурзин Ф.А.

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

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

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

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

Разработаны методы описания модели для программной системы по принципу «код и модель-одно целое» в двух вариантах:

при наличии реализованного программного кода описание модели на разработанном языке встраивается в код системы (описание модели по коду);

- реализация программной системы при помощи объектно-ориентированной реализации модели в виде классов (проектирование системы как модели).

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

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

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

Объект исследования — современные многокомпонентные распределенные программные системы, многопоточные системы, системы, построенные на обмене сообщениями.

Актуальность темы. С ростом сложности программных систем возни-

кает проблема обеспечения достаточного уровня надежности разрабатываемого ПО, ошибки в котором могут нанести серьезный экономический ущерб и привести к жизненно-опасным ситуациям. Современные технологии программирования не могут обеспечить эффективных методов безошибочного проектирования ПО. В настоящее время на рынке нет удобных и эффективных продуктов для тестирования программ с использованием математических моделей, как нет и общепризнанных математических моделей для описания многокомпонентных распределенных систем. Большая работа проделана в исследовательском центре корпорации Microsoft профессором Ю. Гуревичем, ведутся исследования в научных центрах NASA и Bell labs, в России следует отметить работы института системного программирования РАН и кафедры технологий программирования СпбГУ ИТМО. Однако, практическая применимость для тестирования предлагаемых моделей в компаниях по разработке ПО невелика, что является следствием сложности предлагаемых моделей и низкой степенью их вовлечения в реальные процессы разработки. В связи с этим актуальным является комплексное исследование предметной области в сфере сложных многокомпонентных взаимодействующих программ, их моделирование и практическое применение построенной модели для верификации и тестирования ПО.

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

- адекватное описание различных классов распределенных программных систем;

возможность внедрения фазы описания модели в процесс разработки программного обеспечения;

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

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

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

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

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

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

объектно-ориентнрованную реализацию модели в виде классов на языке Java;

- инструменты для описания модели по принципу «код и модель -одно целое»;

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

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

сервер динамического тестирования и средства анализа результатов динамического тестирования;

средства для статического тестирования по модели. Компоненты интегрируются в свободную среду промышленной разработки программ Eclipse, получено авторское свидетельство N2009610226 от 11.01.2009 о регистрации в реестре программ для ЭВМ, также выполнена реализация и для среды Microsoft Visual Studio.

Апробация. Основные положения диссертации докладывались на следующих конференциях, конкурсах и семинарах: конференция-конкурс "Технологии Microsoft в теории и практике программирования" (Новосибирск, НГУ, 2007 и 2008 гг.); VI и VII Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых "Молодёжь и современные информационные технологии" (Томск, ТПУ, 2008 и 2009гг), V и VI Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Наука и молодёжь" (Барнаул, АлтГТУ, 2008 и 2009г.); Школа-семинар в Сибирском федеральном округе для участников (победителей) программы «Участник молодежного научно-инновационного конкурса» (Барнаул, АлтГТУ, 2008г.); Школа - семинар «Менеджмент технико-внедренческой деятельности» для победителей программы «У.М.Н.И.К.» 1 года (Томск, ТГУ, 2008); Конкурс IT проектов Алтайской торгово-промышленной палаты (Барнаул, 2008); VI и V Всероссийская научно-техническая конференция «Технологии Microsoft в теории и практике программирования» для студентов, аспирантов и молодых ученых Российской Федерации (Москва, МАИ, 2009, 2010); XII Региональная математическая конференция МАК-2009 (Барнаул, АлтГУ), также работа была представлена в сборниках конференций: XLVI Международная научно-студенческая конференция "Студент и научно-технический прогресс (Новосибирск, СО РАН, 2008), Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Научная сессия ТУСУР-2008" (Томск, ТУСУР, 2008); V Всероссийская конференция "Математическое моделирование и краевые задачи" (Самара, СамГТУ, 2008); X Международная Белорусская матема-

тическая конференция (Минск, БГУ, 2008).

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

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

Объем и структура работы. Диссертация состоит из введения, списка сокращений, трех глав, заключения и шести приложений. Список использованной литературы содержит 103 наименования, включая работы автора. Текст диссертации содержит 185 страниц машинописного текста, включая 46 рисунков, 2 таблицы.

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

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

2. Процесс разработки и тестирования на основе построенной модели.

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

4. Алгоритмы статического анализа свойств модели.

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

1 Автоматная стохастическая мультиагентная модель, позволяющая

моделировать поведение распределенных многокомпонентных

программных систем на разных уровнях абстракции

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

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

Компонент распределенной системы— это отдельный программный «проект» в терминах интегрированной среды разработки (IDE), программа, которая имеет свою логику работы и может взаимодействовать с другим компонентами. Компонент может находиться на отдельном узле в распределенной системе и указываться при проектировании на UML диаграмме развертывания.

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

• на уровне всей взаимодействующей системы - структурный автомат;

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

• на нижнем уровне - состояния, привязанные к реальному коду программного компонента, состояния могут группироваться в подавтоматы (например, логика работы потока задается подавтоматом) и рассматриваться как сверхсостояния.

Состояние s из множества состояний S относительно к коду компонента предлагается рассматривать как определяемую разработчиком последовательность {р,..,г} линий кода Src в исходном файле / еSrcFile, которая, по его мнению, отражает неделимое состояние системы в каждый момент времени:

.s = { U Src ß\f Е SrcFile ,вфайле / с линии рдо линииг

i=p...r

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

System=(Node, А', AstmclureJ, BoimdNodes, Msg, Res, CP (Л*), Asp).

Здесь:

Node - множество узлов распределенной системы;

BoundNodes - отображение, определяет расположение компонентов по узлам; А* - множество расширенных конечных автоматов, каждый из которых моделирует один компонент системы, для которой строится модель; A structured ~ структурный автомат, модель высокого уровня системы; Asp — множество аспектов, реализующих сквозную (общую) функциональность по принципам аспектно-ориентированного программирования. Аспект задается подавтоматом, точкой сопряжения для связи с подавтоматами, к котором он применяется, и способом применения (до, после, вместо). В работе доказывается теорема, что для автомата с аспектной группой существует эквивалентный автомат без аспектной группы с добавленными состояниями и переходами.

CP (А") - множество точек сопряжения между моделями компонентов и для связи с аспектами по принципу рукопожатия; Res - множество глобальных общих блокируемых ресурсов; Msg - множество глобальных посылаемых сообщений. Структурный автомат задается как четверка вида:

Astrucu,red=(Cn,bstructured,InputPm,I.).

Здесь:

Сп - состояния структурного автомата - компоненты моделируемой системы с учетом кратностей (кратность компонента — количество его одинаковых эк-

земпляров, работающих в распределенной системе);

^structured ~ функция переходов структурного автомата. В структурном автомате переход между состояниями-компонентами системы означает отсылку сообщения между ними. Функция 5structureJ определяет переход-отсылку сообщения в зависимости от компонента, номера сообщения, входа из множества InputPin, куда будет послано сообщение, и идентификатора сообщения из Z.

Каждый элемент множества А* представляет собой расширенный конечный автомат вида:

A = {S,s0,ö ,у ,Sßn,E, Msg '5Msg, ResRes), где Msg 'иRes' - соответственно локальные для компонента распределённой системы подмножества глобальных множеств Msg и Res.

Логика работы автомата А в общем случае определяется двумя функциями переходов:

• Недетерминированной функцией переходов б , она задает отображение:

S:SxDxPxNxTxMsg'xRes'x->

2Л (((Г х S) * uS) х Msg'xRes'). Находясь в состоянии из S кратности N по действию из D с вероятностью из Р в потоке из Г и по полученному сообщению из Msg', после установки блокировки ресурса на Res' модель системы недетерминированно переходит или в несколько состояний, создав несколько новых потоков из Т, или просто в следующее состояние в текущем потоке; при этом возможны отсылка сообщения из Msg' и разблокировка некоторого ресурса из Res'.

• Функцией переходов «по ребрам» у , определяющей возможность возникновения некоторого числа событий или исключительных ситуаций Е при переходе из состояния в состояние y:SxS—>E*.

• Операцией редукции, осуществляющий сворачивание потоков в один: join:{SxT)+->SxT.

Следует обратить внимание на то, что все действия в расширенном автомате связаны с некоторой вероятностью, и здесь мы говорим прежде всего о моделировании потока управления (control flow), но не потока данных (data flow). Использование вероятностей позволяет моделировать недетерминированное сложное поведение, учет всех особенностей которого слишком сложен. Предлагаемая модель построена таким образом, что при ее создании и описании компонента системы в некотором состоянии мы можем выбирать, будем ли мы абстрагироваться от условий и делать вероятностные недетерминированные переходы или учитывать, например, пришедшее сообщение и делать детерминированный переход в зависимости от описываемых факторов.

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

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

Компоненты системы, каждый из которых задан расширенным автоматом А , могут взаимодействовать друг с другом через:

- посылку и получение сообщений из множества Msg;

- блокировку, ожидание раблокировки и разблокировку общих ресурсов из Res;

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

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

A = (S .Trans ,Ор),

где Trans = S->SxE* - отображение, определяет переход с возможной генерацией событий, Ор= {fork, join, send .receive, block, unblock) XE - множество рассматриваемых ниже операций в расширенном автомате также с возможными связанными событиями. Под словом «операция» мы имеем ввиду логически обособленное действие по переходу из состояния расширенного автомата в его другое состояние с заданной вероятностью, выполняющее помимо перехода некоторые действия со множествами расширенного автомата. Операция является подмножеством функции перехода. Вводятся следующие операции:

• Создание потока fork:PxS->(SxT)+. Находясь в некотором состоянии из S с некоторой вероятностью Р компонент переходит в несколько состояний (хотя бы в одно), создав несколько потоков (элементы множества Г, при этом текущий поток является родителем для вновь созданных потоков и продолжает выполнятся вместе с ними).

• Ожидание завершения потоков

join:PX(SxTpareJx(SfmXTslaveYSXTparcnt. Здесь TparmteT - родительский поток, который осуществляет ожидание подчиненных потоков Ts/ave^T. Обобщенно, join:Px(SxTy-*SXT. Находясь в некотором состоянии в некотором потоке с вероятностью Р компонент начинает ожидать завершения некоторого количества потоков из множества Т (перехода их подавтоматов в заключительное состояние), и после этого переходит в новое состояние из S в своем потоке.

Посылка сообщения sendQ(bWy):SxTxP^{SxMsg)\'E. Компонент, находясь в состоянии из S в потоке из множества Т с некоторой

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

• Получение сообщения receive£ (5 V у):SXTXPXMsg->SVE. Компонент, находясь в состоянии из S в потоке из множества Т с некоторой вероятностью Р начинает ожидать сообщение Msg, и, получив его, переходит в новое состояние из S. При ошибке получения сообщения (например, по таймауту), генерируется событие из множества Е.

• Блокировка разделяемого ресурса

blockQ(b\>y)\SxTxNxPxRes->{SX\XRes)v Е. Находясь в состоянии из S в потоке из Г с некоторой кратностью N с вероятностью Р поток текущего компонента начинает блокировку ресурса из Res и при удачной блокировке переходит в новое состояние с кратностью равной 1. При неудачной блокировке поток зависает и ждет освобождения ресурса, при неуспешном ожидании может быть сгенерировано событие из Е.

• Разблокировка разделяемого ресурса

unblock£{5\/y):SxlXResXP->(SxNxRes)vE. Находясь в состоянии из S, владея заблокированным ресурсом Res и имея кратность состояния 1 (никакой другой поток не находится в данном состоянии) компонент с некоторой вероятностью Р осуществляет попытку разблокировки ресурса Res, при успешной разблокировке переходит в новое состояние с любой допустимой кратностью, при неуспешной - может генерировать событие из Е.

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

2 Процесс разработки н тестирования на основе предложенной

модели

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

Тестирование на основе модели предлагается проводить двумя способами:

Статическое тестирование (верификация и симуляция) по модели,

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

- Динамическое тестирование проводится на скомпилированной рабочей системе с целью проверки её поведения относительно построенной модели.

При обнаружении ошибки в процессе тестирования возможны варианты:

- допущена ошибка в программе, т.е. программа не соответствует описанной модели;

- несоответствующее поведение — это ошибка в описании модели, т.е. модель неправильно описывает систему.

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

Описание модели. Пусть имеется распределенная многокомпонентная

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

В данном исследовании как при отсутствии, так и при наличии кода системы предлагается строить модель по предлагаемому автором принципу -«код и модель — одно целое».

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

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

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

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

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

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

Утверждение 1. Представления автоматной стохастической мультиагентной модели системы в виде классов, на XML языке и её теоретико-множественное определение эквивалентны в описании взаимодействия.

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

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

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

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

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

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

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

Динамическое (on-line) тестирование предполагает построение динамической модели( Л/д„„) работающей системы и сравнение ее с описанной моделью причем, если МмЯМстат; То данный сеанс тестирования прошел успешно, иначе модели не соответствуют друг другу, что связано либо с найденными ошибками в программе, либо с ошибками в описании модели. Динамическое построение модели позволяет отследить момент начала несоответствия.

Комплексное построение модели всех компонентов системы осуществляется динамически на сервере системы тестирования с использованием протокола TCP/IP. Для обеспечения отсылки данных о проходящих событиях в

модели реализовано два метода:

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

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

В процессе тестирования после разворачивания тестируемой системы по тестовым узлам (BoundNodes), запуска сервера, задания для него активной статической модели мстат и начала взаимодействия, на сервере начинается построение динамической модели системы Мдт и ее сверка со статической.

Тестирование соответствия (conformance-testing) включает проверку следующих условий:

• Переход из заданного состояния в одно из заданных:

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

• Срабатывание событий и исключительных ситуаций. При переходах:

V AeA':S(A)=S8i\/sieS8iNexti{sl)HstmZS)=s>s1-+s2,s1eSlmt; при отсылке сообщений:

Mcma„'3msge Msg,BS^S.^S^s, send ^(bAy):SlxTxP-^(S2Xmsg)vE=> M^-.S^S^S^S^S^firstiA,);

при блокировке ресурса:

Mcmam3S1S2_blockQ{b\/y):SlXTxNXPxRes^(S2X\xRes)\'E=> Mdm.S^S2wS^S3,S3=first(AE).

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

• Соответствие модели верхнего уровня моделям нижнего уровня по сообщениям и кратностям:

V С,. -> с J, с, 6 Си, с j е Сп => Э msg = (s from, sK, msgid, type ,lxt), sftome A,,

Модель верхнего уровня (Л,,™*^) описывает возможные взаимодействия через отправку/прием сообщений, модели компонентов более низкого уровня описывают обмен конкретных сообщений между заданными состояниями. Если

заданный порядок обмена нарушен, регистрируется ошибка взаимодействия.

• Корректность создания и завершения потоков, кратности состояний

^ Т\ — Тк, fork: PxS/mt->(SixTi)x...x(SkxTt)=> N(S,) = M(Tl) = N(SMk)+\...N(Sk) = N(Tk)=N(Sf0J+l;

VTl..rkJom:(SlxTl)x...X{SkXTk)^SjomXTJ,,=>N(S1J = N(T]J = \

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

• Правильность отсылки и приема сообщений

V msg,send:PXSirom XTsmdХР^ (SMXnag) V £„„,_„„,, msg = (Sfll)m, St0, type, text) 3receive:PX Г„„,„ xSl0Xmsg-*S

received^ "^no^sent'

Для любого отправленного сообщения проверяется, дошло ли оно до получателя и правильно ли обрабатывается потеря сообщения.

• Критические секции, связанные с блокировкой внешних ресурсов

V S, S,>S>S2 S!:block(res), S2:unblock[res),res€Res=>N(S) = 1.

Если блокируется ресурс одним потоком /компонентом и производится попытка доступа к нему другим потоком/компонентом, то проверяется, что доступ к ресурсу имеет только его владелец. Кратность состояния в критической секции равна 1.

• Контроль возникающих блокировок - бесконечных ожиданий (deadlocks):

deadlock <=>3Tl,T1,Host{R2) = Ti,Host(R1)=T1,Ti^T2 block :T2XR2&block'.TixRl.

Дедлок — это бесконечное ожидания объектом Objl освобождения ресурса, когда захвативший этот ресурс Obj2 сам ожидает освобождения Objl. Цикл в графе ожидания ресурсов сигнализирует о наличии дедлока.

• Связность компонентов через точки сопряжения (соответствие состояний, в каких находится один компонент, состояниям, в которых находится другой компонент) не нарушается:

V CPiA^.A^^y SieS(Al)3S2eS(A2):3epeMnt,Sl(Al) = Sl&S,(A2)=S2 .

Если определены точки сопряжения, то проверяется, действительно ли выполняется соответствие связанных состояний.

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

Детальная трассировка посещенных состояний и примененных в процессе операций (StateTrace). В процессе тестирования запоминается информация о всех действиях в модели.

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

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

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

4 Алгоритмы статического анализа свойств модели

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

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

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

• Симуляция по модели.

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

а) случайная прогулка производится путем случайного выбора траектории поведения модели. Случайная прогулка осуществляется с учетом вероятностей переходов и операций;

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

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

• Анализ вероятностей.

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

а) Для подсчета вероятности достижения заданного состояния sx£S из начального, прежде всего, нужно обеспечить, чтобы одна из случайных траекторий работы системы проходила через нужное состояние sx. Это можно реализовать при помощи задания предиката, значение которого предполагается истинным во всех состояниях: staters,, (здесь state —глобальная переменная, в которой сохраняется текущее состояние, для каждого главного потока компонента и любого побочного потока она своя; в предикате используется переменная именно для того компонента и потока, в котором находится состояние sx), и запуска верификатора в режиме доказательства правильности, при этом данный предикат становится ложным при очередном выборе траектории с достижением состояния sx и верификатор возвращает данную траекторию как контр-пример. Далее, с этой траекторией, содержащей заход в состояние sx, запускается верификатор уже в режиме симуляции. Модель для верификатора генерируется таким образом, чтобы после каждого перехода или операции производился пересчет условной вероятности в каждый текущий момент. При достижении состояния sx выводятся накопленные вероятности текущего потока и всех его родительских, эти данные читаются из потока вывода верификатора и становятся доступными как результат.

б) Для подсчета вероятности достижения заданного состояния sx&S из другого заданного s}lGS необходимо действовать аналогично а), только необходимо установить траекторию, проходящую через оба состояния. Предикатом, который должен быть опровергнут, является (state Ф sy) U (G state Ф sx), где U — темпоральный оператор «до тех пор, пока», a G — темпоральный оператор «всегда». Сама вероятность вычисляется как частное накапливаемых вероятностей для sx и

• Проверка достижимости всех состояний.

Такая проверка осуществляется для каждого состояния s;ES, путем ожидания контр-примера для предиката (state !=s,). Если верификатор возвращает ошибку, то состояние s, достигается, при этом как контр-пример можно найти путь из начального состояния в s,.

• Проверка связности через точки сопряжения.

Связность через точки сопряжения - ожидаемый пользователем набор соответствий подавтомата (набора состояний) одного компонента или потока с подавтоматом (состояниями) другого. Пусть имеется точка сопряжения, связывающая некоторые логические наборы состояний А и В, ср^СР: {sA1,sA2,...sA„} {sBI, sB2,...sBm} . Тогда проверка связности представляет собой проверку предиката

G(( state A = sA, || state A = sA21].. state A = sA„)->( stateB==sB11| state B==sS21|.. state B== s Bm)). Здесь stateA и stateB — те состояния, которые идентифицируют либо текущее состояние потока main компонента, где находится группа состояний А или В соответственно, либо одного из побочных потоков, где эти группы состояний могут быть объявлены. При ошибке верификации выдается контр-прнмер,

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

• Проверка, что для каждое отправленное сообщение получено.

Для каждого сообщения генерируется своя переменная status __ message¡, которая может содержать два значения из перечисляемого типа sent (сообщение отправлено) и received (сообщение получено), изменение этих значений вставляется соответственно после отправки и после получения сообщения из канала. Предикат, истинность которого проверяется -

G(( status_message¡== sent)->F( status_message ¡ = received)), где G и F — темпоральные операторы соответственно «всегда» и «хотя-бы раз в будущем».

• Проверка, что каждый заблокированный ресурс разблокируется. Ресурсы res¡ задаются переменными, принимающими значение 1 (ресурс заблокирован) или 0 (ресурс разблокирован), предикат для проверки условия будет иметь вид G(( res== 1 )-> F (res, == 0)).

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

- Диаграмма сообщений (message sequence chart) — стандартная диаграмма языка UML, показывает изменение состояний процессов с течением времени и их связи через сообщения.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Проведен анализ предметной области, моделей распределенных программных систем и средств для тестирования по модели.

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

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

4. Разработан и реализован в виде прототипов (подключаемых модулей к промышленным средам разработки Eclipse и Visual Studio) комплекс программ для описания модели и проведения тестирования.

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

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Работы, опубликованные в журналах из перечня ведущих рецензируемых журналов ВАК Министерства образования и науки РФ:

1. Старолетов С.М. Проведение on-line тестирования программного обеспечения на основе построенной модели / Старолетов С.М., Крючкова Е.Н. // Ползуновский вестник № 2, 2010. - Барнаул: изд-во АлтГТУ, 2010. - с. 212-216.

2. Старолетов С.М. Динамическое тестирование распределенных систем на основе автоматных моделей. // Крючкова Е.Н., Старолетов С.М. Программная инженерия № 2, 2011. - М.: изд-во «Новые технологии», 2011. с. 22-27.

Другие работы по теме диссертации:

3. Старолетов С. М. Моделирование распределенных многокомпонентных программных систем и их тестирование на основе автоматных вероятностных моделей / Монография. С. М. Старолетов, Е. Н. Крючкова. - Барнаул : Изд-во АлтГТУ, 2011. -107 с. - ISBN 978-5-7568-0859-9

4. Staroletov S. Model of a program as multi-threaded stochastic automaton and its equivalent transformation to Promela model/ Ershov informatics conference. PSI Series, 8th edition. International workshop on Program Understanding. Proceedings. - N., 2011. p. 33-38

5. Старолетов С.М. Тестирование распределенных приложений на основе построения моделей / Е.Н. Крючкова, С.М. Старолетов // Прикладная информатика. - N 6(18), 2008, - М.: Market DS Publishing, с. 124-134.

6. Старолетов С.М. Применение моделей при тестировании программ / Е.Н. Крючкова, С.М. Старолетов // Ползуновский альманах. - Барнаул, 2008,- N° 4,- с. 16-21.

7. Старолетов С.М. Анализ моделирования оптимальных стратегий тестирования современных распределенных недетерминированных систем / Е.Н. Крючкова, С.М. Старолетов. Технологии Microsoft в теории и практике программировании. Конференция-конкурс работ студентов, аспирантов и молодых учёных. Тезисы докладов. - Н.: Оригинал 2, 2007. - с. 37-38.

8. Старолетов С.М. Конечный автомат с вероятностными переходами как модель распределённой программной системы/Е.Н. Крючкова, С.М. Старолетов. Математическое моделирование и краевые задачи: Труды пятой Всероссийской научной конференции с международным участием 4.4.: Информационные технологии в математическом моделировании.- Самара: СамГТУ, 2008. - с. 129.

9. Старолетов С.М. Математическая модель для тестирования программ/Е.Н. Крючкова, С.М. Старолетов. VI Всероссийская научно-техническая конференция студентов, ас-пирантови молодых ученых "Наука и молодежь - 2009". Секция «Информационные иобразовательные технологии». Подсекция «Программное обеспечение вычис-ли-тельной техники и автоматизированных систем». / Алт. гос. техн. ун-т им.И.И.Ползу-нова. - Барнаул: изд-во АлтГТУ, 2009. - с. 82-92.

10. Старолетов С.М. Методология тестирования программных систем на основе построения и анализа модели программы / Е.Н. Крючкова, С.М. Старолетов. Сборник трудов VII Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии». Томск, 25 - 27 февраля 2009 г., ч.1. Томск: Изд-во СПБ Графике, 2009. - с. 195-196.

11. Старолетов С.М. Моделирование связной функциональности многокомпонентных систем / Старолетов С.М., Крючкова Е.Н. Тр. VII Всерос. конф. студентов, аспирантов и молодых учёных Центральный регион. Москва, 21-22 апреля 2010г. - М.: Вузовская книга, 2010,- с. 62-63

12. Старолетов С.М. Модель для тестирования ПО / С.М. Старолетов. Материалы двенадцатой конференции по математике "МАК-2009". - Барнаул: Изд-во Алт. Ун-та, 2009.

- с. 84-86.

13. Старолетов С.М. Мультиагентная модель распределенной системы для проведения model-based testing современного ПО / С.М. Старолетов, E.H. Крючкова. Тр. VI Все-.рос. конф. студентов, аспирантов и молодых учёных. Центральный регион. Москва, 12 апреля 2009г. - М.: Вузовская книга, 2009. - с. 37.

14. Старолетов С.М. Некоторые аспекты тестирования распределенных систем с построением модели / E.H. Крючкова, С.М. Старолетов. Научная сессия ТУСУР-2008: Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. Томск, 5-8 мая 2008 г.: В пяти частях. 4.2. - Томск: В-Спектр, 2008.-с. 50-53.

15. Старолетов С.М. Разработка программного комплекса для тестирования недетерминированных распределённых систем с построением моделей / E.H. Крючкова, С.М. Старолетов // Ползуновский альманах. - Барнаул: изд-во АлтГТУ, 2008. - № 4. - с. 219220.

16. Старолетов С.М. Разработка системы тестирования распределенных приложений на основе математических моделей / С.М. Старолетов, E.H. Крючкова. Технологии Microsoft в теории и практике программирования. Конференция-конкурс работ студентов, аспирантов и молодых учёных. Тезисы докладов. - Н.:Оригинал 2, 2008. - 2 с.

17. Старолетов С.М. Реализация системы тестирования распределенных и многопоточных приложений на основе технологии МВТ / С.М. Старолетов, E.H. Крючкова. Измерение, контроль, информатизация. Международная научно-техническая конференция. Тезисы докладов. - Барнаул: изд-во АлтГТУ, 2011. - с. 16-20

18. Старолетов С.М. Свой взгляд на Model Based Testing распределенных недетерми-нированнных систем / Старолетов С.М., Крючкова E.H. Сборник трудов региональной конференции-конкурса (Северо-Западный регион) студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования 2009»Санкт-Петербург, 17-18 марта 2009. -Изд-во Политехи, ун-та, 2009. - с. 173.

19. Старолетов С.М. Тестирование недетерминированного программного обеспечение на основе моделей / С.М. Старолетов. Тезисы докладов Международной научной конференции "X Белорусская математическая конференция". Минск, 3-7 ноября 2008 года. -с. 90.

20. Старолетов С.М. Тестирование распределенных программ с построением модели программы в виде конечного автомата с вероятностными переходами / E.H. Крючкова, С.М. Старолетов. Материалы XLVI Международной научной студенческой конференции «Студент и научно-технический прогресс»:Информационные технологии. - Но-восиб. гос. ун-т. Новосибирск, 2008. - 2с.

21. Старолетов С.М. Тестирование распределенных систем с помощью построения моделей / E.H. Крючкова, С.М. Старолетов. Молодежь и современные информационные технологии. Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. Томск, 26 - 28 февраля 2008 г. - с. 159-161

Подписано в печать 15.11.2011 Печать - цифровая. Усл.п.л. 1,16.

Тираж 120 экз. Заказ 2011 - 734 Отпечатано в типографии АлтГТУ, 656038, г. Барнаул, пр-т Ленина, 46 тел.: (8-3852) 36-84-61 Лицензия на полиграфическую деятельность ПЛД №28-35 от 15.07.97 г.

Список использованных сокращений.

ВВЕДЕНИЕ.

ГЛАВА 1. ПРИМЕНЕНИЕ МОДЕЛЕЙ В ПРОЦЕССЕ РАЗРАБОТКИ ПРОГРАММ. ТЕСТИРОВАНИЕ НА ОСНОВЕ МОДЕЛЕЙ. МОДЕЛИ РАСПРЕДЕЛЕННЫХ ВЗАИМОДЕЙСТВУЮЩИХ СИСТЕМ.

1.1 Разработка, управляемая моделями.

1.2 Тестирование ПО сегодня.

1.3 Краткий обзор технологий тестирования.

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

1.4.1 Сети Петри.

1.4.2 Язык 8БЬ.

1.4.3 ЯзыкиМЬ.

1.5 Выводы к главе 1.

ГЛАВА 2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ СОВРЕМЕННЫХ РАСПРЕДЕЛЕННЫХ

НЕДЕТЕРМИНИРОВАННЫХ СИСТЕМ.

2.1 Модели в исследовании свойств алгоритма.

Проблема тестирования.

2.2 Распределенные недетерминированные взаимодействующие системы. Постановка задачи на тестирование.

2.3 Модель распределенных недетерминированных систем.

2.3.1 Конечный автомат.

2.3.2 Конечный автомат с вероятностными переходами.

2.3.3 Конечный автомат с вероятностными переходами и обработкой событий и исключений.

2.3.4 Расширение автомата для поддержки моделирования многопоточных приложений.

2.3.4.1 Параллелизм.

2.3.4.2 Операция создания потока и понятие кратности.

2.3.4.3 Операция ожидания потоков.

2.3.4.4 Обмен сообщениями.

2.3.4.5 Блокировка ресурсов.

2.3.5. Модель многокомпонентной системы высокого уровня.

2.3.6 Моделирование межкомпонентной связности.

2.3.7 Итоговая модель системы в виде взаимодействующих компонентов.

2.4 Предварительная оценка модели.

2.4 Выводы к главе 2.

ГЛАВА 3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ПРОЦЕССОВ

РАЗРАБОТКИ И ТЕСТИРОВАНИЯ НА ОСНОВЕ МОДЕЛЕЙ.

3.1 Представление автомата в виде состояний, переходов и операций.

3.2 Способы описания модели и ее соотношение с исходным кодом системы.

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

3.2.2 Описание модели при наличии кода.

3.3 О практической значимости и адекватности модели.

3.4 Процесс разработки и тестирования на основе моделей.

3.5 Статическая верификация модели.

3.6 Динамическое тестирование по модели.

3.6 Выводы к главе 3.:.

В настоящей диссертационной работе рассматриваются модель, методы и средства для проектирования и тестирования программных систем для параллельной и распределенной обработки данных согласно принципам МТЮ и МВТ.

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

Разработаны методы описания модели для программной системы по принципу «код и модель-одно целое» в двух вариантах:

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

• реализация программной системы при помощи объектно-ориентированной реализации модели в виде классов (проектирование системы как модели).

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

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

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

Объект исследования - современные многокомпонентные распределенные программные системы, многопоточные системы, системы, построенные на обмене сообщениями.

Актуальность темы. С ростом сложности программных систем возникает проблема обеспечения достаточного уровня надежности разрабатываемого ПО, ошибки в котором могут нанести серьезный экономический ущерб и привести к жизненно-опасным ситуациям. Современные технологии программирования не могут обеспечить эффективных методов безошибочного проектирования ПО. В настоящее время на рынке нет понятных и эффективных продуктов для тестирования программ с использованием математических моделей, как нет и общепризнанных математических моделей для описания многокомпонентных распределенных систем. Большая работа проделана в исследовательском центре корпорации Microsoft профессором Ю. Гуревичем, ведутся исследования в научных центрах NASA и Bell labs, в России следует отметить работы института системного программирования РАН и кафедры технологий программирования СпбГУ ИТМО. Однако практическая применимость для тестирования предлагаемых моделей в компаниях по разработке ПО невелика, что является следствием сложности предлагаемых моделей и низкой степенью их вовлечения в реальные процессы разработки. В связи с этим актуальным является комплексное исследование предметной области в сфере сложных многокомпонентных взаимодействующих программ, их моделирование и практическое применение построенной модели для верификации и тестирования ПО.

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

Основными требованиями к разрабатываемой модели являлись:

• адекватное описание различных классов распределенных программных систем;

• возможность внедрения фазы описания модели в процесс разработки программного обеспечения;

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

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

Научная новизна. В результате настоящего исследования разработаны:

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

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

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

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

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

Компоненты интегрируются в свободную среду промышленной разработки программ Eclipse, получено авторское свидетельство N2009610226 от 11.01.2009 о регистрации в реестре программ для ЭВМ, также реализована интеграция и в среду Microsoft Visual Studio.

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

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

1. Проведен анализ предметной области, моделей распределенных программных систем и средств для тестирования по модели.

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

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

4. Разработан и реализован в виде прототипов (подключаемых модулей для промышленной среды разработки Eclipse) комплекс программ для описания модели и проведения тестирования.

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

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

ЗАКЛЮЧЕНИЕ

1. Amstrong J. Programming Erlang: Software for a Concurrent World / J.Amstrong. Raleigh, North Carolina Dallas, Texas: The Pragmatic bookshelf, 2007.-519 p.

2. Baker P. Model-Driven Testing. Using the UML Testing Profile / P. Baker, Z. Dai, J. Grabowski, 0. Haugen, I. Schieferdecker, С. Williams. Berlin: Springer-Verlag, 2008. - 176p.

3. Barnett M. The Spec# Programming System: An Overview Электронный ресурс. / M. Barnett, К. Rustan, M. Leino, W. Schulte. Redmond, WA, USA: Microsoft Research, 2004. -21 p. Режим доступа- http://research.microsoft.com/ -leino/papers/krml 136.pdf.

4. Blass A. Abstract State Machines Capture Parallel Algorithms: Correction and Extension Электронный ресурс. / А. Blass, Y. Gurevich. USA: Microsoft Research, 2007 - 29 р. Режим доступа - http://www.math.lsa. umich.edu/~ablass/corr-final.pdf.

5. Boerger E. Abstract state machines. A method for high-level system design and analysis / E. Boerger E., R. Staerk. USA: Springer, 2003. - 448 p.

6. Böllert К. On Weaving Aspects / K. Bollert, A. Moreira, S. Demeyer. In Proceedings of the Workshop on Object-Oriented Technology (June 14 18, 1999) Eds. Lecture Notes In Computer Science, vol. 1743- London: Springer-Verlag, 1999.-p. 301-302.

7. Brown A. An introduction to Model Driven Architecture Электронный ресурс. / A. Brown. Режим доступа http://www.ibm.com/developerworks/rational/library/3100.html.

8. Gerth R. Concise Promela Reference Электронный ресурс. / Rob Gerth, 1997. Режим доступа http://spinroot.com/spin/Man/Quick.html.

9. Eclipse Modeling Framework Project (EMF) Электронный ресурс. / Режим доступа http://www.eclipse.org/modeling/emf/.

10. Eclipse.org home Электронный ресурс. / Режим доступа -http://eclipse.org/.

11. Extensible Markup Language (XML) 1.0 Электронный ресурс. / W3C Recommendation of 26 November 2008.

12. Gargantini A. Metamodel-based Simulator for ASMs Электронный ресурс. / A. Gargantini, E. Riccobene, P. Scandurra, Italy 21р. Режим доступа — http:// citeseerx.ist.psu.edu/viewdoc/download? doi= 10.1.1.153.2512&rep=repl &type=pdf.

13. Google Chrome: новый веб-браузер для Windows Электронный ресурс. Режим доступа http://www.google.com/chrome/index.html7hHru.

14. Graphical Modeling Project (GMP) Электронный ресурс. / Режим доступа http://www.eclipse.org/modeling/gmp/.

15. Gronback R. Eclipse Modeling Project: A Domain-Specific Language (DSL) Toolkit / R. Gronback. USA: Addison-Wesley Professional, 2009. - 736 p.

16. Hutton G. Programming in Haskell / G. Hutton. Cambridge: Cambridge University Press, 2007. - 170 p.

17. JavaTESK: Быстрое знакомство. Документация Электронный ресурс. / Режим доступа www.unitesk.ru.

18. JavaTM Platform Debugger Architecture (JPDA) Электронный ресурс. / Oracle Java SE Documentation. Режим доступа http://download.oracle.com/ javase/6/docs/technotes/guides/jpda/.

19. Knudsen J. Parsing XML in J2ME Электронный ресурс. / J. Knudsen. Sun developer network. Article. Режим доступа http://developers.sun.com/mobility/ midp/articles/parsingxml/.

20. Laddad, R. AspectJ in Action. Practical aspect-orientic programming/R. Laddad. USA: Manning Publications Co., 2003. - 513 p.

21. LINQ. .NET framework developer center Электроннный ресурс. / Режим доступа- http://msdn.microsoft.com/en-us/netframework/aa904594.aspx.

22. McConell S. Code complete. Second Edition / S. McConnel. USA: Microsoft press, 2004 - 960 p.

23. Microsoft Visual Studio Электронный ресурс. / Режим доступа -http://www.microsoft.com/visualstudio/ru-ru/default.mspx.

24. Object Management Group UML Электронный ресурс. / Unified modeling language. Режим доступа - http://www.uml.org/.

25. OMG Unified Modeling Language (OMG UML), superstructure Электронный ресурс. / OMG Document Number: formal/2009-02-02. Режим доступа — http://www.omg.org/cgi-bin/doc7formal/2009-02-02.pdf.

26. On-the-fly, LTL model checking with Spin Электронный ресурс. / Режим доступа — http://spinroot.com/spin/whatispin.html.

27. Reed R. Domain of use SDL and MSC Электронный ресурс. / R. Reed. Telecommunications Software Engineering Limited. Режим доступа http://sdl-forum.org/sdl2000present/sdl2000new.zip.

28. Schultz S. Overview of TTCN-3 Электронный ресурс. / S. Shultz. ETSI Secretariat. Режим доступа - http://www.ttcn-3.org/doc/ETSITTCN3 Tutorial.ppt.

29. Scmidt, D. Model-driven Engineering Электронный ресурс. / D. Scmidt. IEEE Computer Society, 2006. - 7 p. Режим доступа -http: / /www. cs. wustl. edu/ ~schmidt/PDF/GEI .pdf.

30. SDL Электронный ресурс. / Режим доступа http://sdl-forum.org/SDL/ index.htm.

31. State-Driven Game Agent Design Электронный ресурс. / Режим доступа — http://www.ai-junkie.com/architecture/statedriven/tutstatel .html.

32. Technical WAP 2.0 Электронный ресурс. / ОМА Technical section. Режим доступа http://www.openmobilealliance.org/tech/affiliates/wap/ technicalwap20-20021106.zip.

33. The Java ТМ Tutorials Электронный ресурс. / Sun microsystems, 19952008. Режим доступа — http://java.sun.com/docs/books/tutorial.

34. Turing A. On computable numbers, with an application to the Entscheidungsproblem / Turing A. Proceedings of the London Mathematical Society, Series 2, 42. London, 1936 - pp. 230-265.

35. UML Testing Profile. Version 1.0 Электронный ресурс. / Object management group. Режим доступа http://www.omg.org/docs/formal/05-07-07.pdf.

36. Zhayong W. Test Advanced Guide. Advanced topics on using Google С++ Testing Framework Электронный ресурс. / W. Zhayong. Режим доступа — http://c0de.g00gle.c0m/p/g00gletest/wiki/G00gleTestAdvancedGuide.

37. Бар P. Язык Ада в проектировании систем / Р. Бар. пер. с англ. М.: Мир, 1988.-315 с.

38. Бейзер Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и системы/ Б. Бейзер. Спб: Питер, 2004. - 320с.

39. Бек К. Расширения Eclipse. Принципы, шаблоны и подключаемые модули/К. Бек, Э. Гамма. М: Кудиц-образ, 2005. - 384 с.

40. Бек К. Экстремальное программирование: разработка через тестирование / К. Бек. СПб.: Питер, 2003. - 224 с.

41. Буч Г. Язык UML. Руководство пользователя / Г. Буч, Д. Рамбо, А. Джекобсон. М.: ДМК пресс, 2007. - 496 с.

42. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Второе издание Электронный ресурс. / Буч Г. Rational Санта-Клара, Калифорния. Режим доступа http://vmk.ugatu.ac.ru/book/buch/ index.htm

43. Вентцель Е.С. Теория случайных процессов и ее инженерные приложения / Е.С. Вентцель, JI.A. Овчаров. М.: Наука. Гл. ред. физ.-мат. Лит. - 1991,- 384 с.

44. Воробьёв Н. Числа Фибоначчи / H.H. Воробьёв. Популярные лекции по математике. М.:Наука, 1978.- 144 с.

45. Выдрин A.C. Стохастические матрицы и анализ защищённости автоматизированных систем / A.C. Выдрин, А. В. Михалёв. Фундаментальная и прикладная математика 2007, т. 13, выпуск 1. М.: МГУ, 2007 - с. 61-99.

46. Гордиенко A.B. Тестирование при оценке динамической корректности программ АСУ / A.B. Гордиенко // Программирование. 1982. - №6. - с. 4852.

47. Горнаков С.Г. Программирование мобильных телефонов на Java2 Micro Edition/С.Г. Горнаков. М.: ДМК Пресс, 2004. - 336 с.:ил.

48. Грязнов Е. Тонкий клиент Электронный ресурс. / Е. Грязнов. Мир ПК. Режим доступа- http://www.osp.ru/pcworld/2005/02/169733/p2.html

49. Гуров В. Исполняемый UML-из России Электронный ресурс. / В. Гуров, А. Нарвский, А. Шалыто. 7 с. Режим доступа - http://is.ifmo.ru/works/ umlrus.pdf

50. Дастин Э. Автоматизированное тестирование программного обеспечения. Внедрение, управление и эксплуатация / Э. Дастин, Д. Рэшка, Д. Пол. Перевод с англ. М.: ЛОРИ, 2003. - 567 с.

51. Зайцев И. М. Агентно-ориентированный подход к моделированию интеллектуальных распределённых систем / Зайцев И. М., Федяев О. И. Сб. — Донецк: ДонНТУ. 2008. - с. 337-338.

52. Иртегов Д.В. Событийно-ориентированные архитектуры. Программирование с использованием POSIX thread library /Д. В. Иртегов. -ООО «Сан Майкросистемс СПБ», 2006-2007.

53. Карпов Ю.Г. Model Checking. Верификация параллельных и распределенных программных систем / Ю.Г. Карпов. Спб.: БХВ-Петербург, 2010.- 552 с.

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

55. Крючкова E.H. Математическая логика и теория алгоритмов: Учебное пособие / Крючкова E.H. Алт. госуд. технич. ун-т. им. И.И. Ползунова. -Барнаул: Изд-во АлтГТУ, 2003. 275 с.

56. Кулямин В. В. Тестирование на основе моделей. Лекции Электронный ресурс. / В.В. Кулямин. Режим доступа http://panda.ispras.ru/~kuliamin/ lectures-mbt/.

57. Марков A.A. Теория алгорифмов /A.A. Марков// Тр. МИАН СССР, т. 42,- М., 1954.-с. 1-374.

58. Материалы конференции Microsoft Academic Days 2005 Russia. Электронный ресурс. / Режим доступа http://www.microsoft.com/Rus/ AcademicDays2005/Default.mspx.

59. Мемоизация (memoization) Электронный ресурс. / Режим доступа -http://www.seoliga.rU/category/.net/memoizaciyamemoization.shtml.

60. Минский М. Вычисления и автоматы / М. Минский, М.: Мир, 1971. -366 с.

61. Мышкис А.Д. Элементы теории математических моделей / А. Д. Мышкис. Изд. 3-е, исправленное. М.: КомКнига, 2007. - 192 с.

62. Нейгель К. С# и платформа .NET 3.0 для профессионалов / К. Нейгель, Б. Ивьен, Д. Глинн, М. Скиннер, К. Уотсон. Пер. с англ. М. ООО "И.Д. Вильяме", 2008. - 1376+416(на CD) с.

63. Новичков А. Метрики кода и их практическая реализация в Subversion и ClearCase Электронный ресурс. / А. Новичков, А. Шамрай, А. Черников. Режим доступа http://cmcons.com/articles/CCCQ/devmetrics/ merticspartl/.

64. Основы теории вероятностных автоматов. Бухараев Р. Г./ Р. Г. Бухарев. -М.: Наука. Главная редакция физико математической литературы. 1985. 288 с.

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

66. Пол С. XML. Проектирование и реализация / С. Пол. пер. с англ. М.: Лори, 2001.-506 с.

67. Рочкинд М. Программирование под UNIX / М. Рочкинд. 2-е изд. перераб. и под. перевод с англ. М.: Издательско торговый дом "Русская редакция"; СПБ.:БХВ-Петербург, 2005. - 704 с.:ил.

68. Савин Р. Тестирование Дот Ком, или Пособие по жестокому обращению с багами в интернет-стартапах/ Р. Савин. М: Дело, 2007. - 312с.

69. Серебряков В.А. Теория и реализация языков программирования

70. Электронный ресурс. / В. А. Серебряков, М. П. Галочкин, Д. Р. Гончар, М. Г. Фуругян. Лекция N4. Синтаксический анализ. Режим доступа -http: //www. intuit. ru/department/sa/pltheory/ 4/6. html.

71. Старолетов С.М. Модель для тестирования ПО / С.М. Старолетов. Материалы двенадцатой конференции по математике "МАК-2009". -Барнаул: Изд-во Алт. Ун-та, 2009. с. 84-86.

72. Старолетов С.М. Применение моделей при тестировании программ / Е.Н. Крючкова, С.М. Старолетов // Ползуновский альманах. Барнаул, 2008.-№4,- с. 16-21.

73. Старолетов С.М. Проведение on-line тестирования программного обеспечения на основе построенной модели / Старолетов С.М., Крючкова

74. E.H. // Ползуновский вестник № 2, 2010. Барнаул: изд-во АлтГТУ, 2010. - с. 212-216.

75. Старолетов С.М. Разработка программного комплекса для тестирования недетерминированных распределённых систем с построением моделей / E.H. Крючкова, С.М. Старолетов // Ползуновский альманах. Барнаул: изд-во АлтГТУ, 2008. - № 4. - с. 219-220.

76. Старолетов С.М. Тестирование недетерминированного программного обеспечение на основе моделей / С.М. Старолетов. Тезисы докладов Международной научной конференции "X Белорусская математическая конференция". Минск, 3-7 ноября 2008 года. с. 90.

77. Старолетов С.М. Тестирование распределенных приложений на основе построения моделей / E.H. Крючкова, С.М. Старолетов // Прикладная информатика. N 6(18), 2008, - М.: Market DS Publishing, с. 124-134.

78. Стелтинг С. Java без сбоев. Обработка исключений, тестирование, отладка / С. Стелтинг. Java Exception Handling, Testing and Debugging. -M. :Кудиц-Образ, 2005. 464 с.

79. Учебник по языку UML Unified Modeling Language, UML лекции и примеры, Case средства UML Электронный ресурс. / Режим доступа — http://www.uml-rus.ru.

80. Фаулер М. Рефакторинг. Улучшение существующего кода/ М. Фаулер. Символ-Плюс, 2008. 432 с.

81. Хемраджани А. Гибкая разработка приложений на Java с помощью Spring, Hibernate и Eclipse / А. Хемраджани. Пер. с англ. М.: ООО "И.Д. Вильяме", 2008. - 352 с.

82. Шаблон Observer Электронный ресурс. / Режим доступа -http://javatutor.net/articles/the-observer-pattern.

83. Щипак Ю. Win32 API. Эффективная разработка приложений / Ю. Щипак. СПб:Питер, 2006. - 576 с.

84. Якобсон А. Унифицированный процесс разработки программного обеспечения (RUP) / А. Якобсон, Г. Буч, Дж. Рамбо. USA:Addison-Wesley, 2002. - 493 с.