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

Вид материала

Содержание

Ломакина Любовь Сергеевна
Крылов Владимир Владимирович
Общая характеристика работы
Содержание работы
Автоматная модель класса
Основные результаты работы
Список опубликованных работ по теме диссертации

Подобный материал:

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

МАЛИНИН СЕРГЕЙ НИКОЛАЕВИЧ

ТЕСТИРОВАНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ НА ОСНОВЕ МОДЕЛИРОВАНИЯ КОНЕЧНЫМИ АВТОМАТАМИ

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

АВТОРЕФЕРАТ

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

кандидата технических наук

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

2010 г.

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

Научный руководитель:	доктор технических наук, профессор ^ Ломакина Любовь Сергеевна

Официальные оппоненты:	доктор технических наук, профессор ^ Крылов Владимир Владимирович
	кандидат технических наук Аристархов Василий Юрьевич

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

Защита диссертации состоится «4» марта 2010 года в 15 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. Р.Е. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

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

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

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

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

кандидат технических наук А.С. Суркова
^

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

Актуальность темы. Несмотря на сравнительно недавнее появление объектно-ориентированных (ОО) языков, таких как Smalltalk, Object Pascal, C++, Ada, объектно-ориентированное программирование (ООП) стало наиболее широко используемым стилем разработки программного обеспечения (ПО) в мире. ООП – методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования. ООП подразумевает событийную управляемость. Бертран Мейер, один из основателей ООП, определял объекты как “нечто имеющее идентичность, состояние, поведение”. С целью управления качеством ОО ПО необходимо решать задачи автоматизации тестирования, что требует разработки новых моделей, методов и алгоритмов, приспособленных к ОО ПО.

Фундаментальные теоретические и прикладные вопросы тестирования ПО изложены в работах В.В. Липаева, П.П. Пархоменко, В.И. Сагунова, G. Myers, B. Beizer, D. MacGregor, B. Boehm, C.V. Ramamoorthy и ряда других отечественных и зарубежных ученых. В качестве модели тестирования ПО в этих работах предлагается использовать управляющий граф программы. Однако, методы, разработанные для данной модели, хорошо зарекомендовали себя при тестировании традиционного (процедурного) ПО, но при непосредственном применении к ОО ПО имеют трудно решаемые проблемы.

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

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

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

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

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

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

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

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

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

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

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

Полученные в диссертационной работе результаты могут использоваться для решения практических задач тестирования ОО ПО событийно-управляемых систем, в том числе телекоммуникационных, систем контроля и управления физическими устройствами, а также для тестирования функциональности ПО с точки зрения пользовательского интерфейса. Результаты настоящей работы были использованы при разработке программ в ЗАО “Интел А/О”.

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

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

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

X Международной конференции «Фундаментальные и прикладные проблемы приборостроения и информатики» (Москва, 2007);
VII Международной конференции «НТИ-2007. Информационное общество. Интеллектуальная обработка информации. Информационные технологии» (Москва, 2007);
VII Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2008);
Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2008, ИСТ-2009)» (Нижний Новгород);
Международном симпозиуме «Интеллектуальные системы INTELS’08» (Нижний Новгород, 2008);
XIII Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2008);
ХII Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2008).

На конкурсе научных работ аспирантов X Международной конференции «Фундаментальные и прикладные проблемы приборостроения и информатики» (Москва, 2007) и VII Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2008) доклады автора были отмечены дипломами первой и третьей степени.

Публикации. По теме диссертации опубликовано 12 работ, в том числе 1 статья в журнале из перечня ВАК РФ, свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 128 наименований. Работа изложена на 118 страницах, содержит 11 таблиц и 15 иллюстраций.
^

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

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

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

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

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

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

атрибуты объектов данного класса (представленные структурой данных);
операции над атрибутами (методы).

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

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

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

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

Источниками сообщений могут служить:

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

Получение какого-нибудь сообщения является событием, при наступлении которого происходит переход к другому устойчивому состоянию (исполнение одной или нескольких операций в составе объекта и преобразование структуры данных). Исполнение операций приводит к генерации других сообщений. На рис. 2.1 показан пример потока сообщений между объектами двух классов List и Entry ОО программы записной книжки. Класс List имеет пять методов, три из которых генерируют сообщения к методам класса Entry. Например, при обращении к методу чтения списка ReadList генерируется сообщение объекту Entry для вызова метода чтения отдельной записи ReadEntry.

Рисунок 2.1 – Пример потока сообщений между двумя классами List и Entry

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

Пусть исследуется программный модуль или комплекс программ, состоящий из классов. Каждый класс может быть представлен как автомат, представляющий собой шестерку A=(X,V,Y,ϕ,ψ,v₀), где

X – множество входных символов (входной алфавит);
V – множество состояний автомата (внутренний алфавит);
Y – множество выходных символов (выходной алфавит);
ϕ  (X ×V) ×V – функция переходов;
ψ  (X×V) ×Y – функция выходов при той же области определения, что ϕ, т.е. Domψ = Domϕ;
v₀V – начальное состояние.

Элементы множества ϕ - называются переходами. Произвольный переход (x,v,v’)  ϕ обозначается

Автомат называется:

конечным, если множества X, V, Y конечны;
детерминированным, если функция переходов однозначна, т.е.

(x,v)Domϕ !v`V ϕ((x,v),v`), и тогда v`=ϕ(x,v).

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

Для исследования такого автомата строится ориентированный граф состояний (граф переходов) G=(V,E,λ,ρ), где V, E – соответственно множества вершин и дуг, а λ, ρ – функции инцидентности, определяющие для каждой дуги, соответственно, её начальную и конечную вершины.

λ:E→V и ρ:E→V.

Функции инцидентности λ и ρ определяют отношение Ω смежности дуг:

e1,e2E e1Ωe2 ≡ ρ(e1)=λ(e2).

На рис. 2.2 в качестве примера показана диаграмма переходов для устройства управления цифровых часов, имеющих две кнопки: “Переключение между режимами часы/минуты/секунды” и “Увеличить значение”. В состоянии 1 (установка часов) поступление входного символа a (нажатие кнопки переключения режима) вызывает переход к состоянию 2 (установка минут), тогда как событие b увеличивает текущее время (число часов), причем это происходит без изменения состояния.

Рисунок 2.2 – Диаграмма переходов автомата

Проведено исследование других особенностей ОО ПО:

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

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

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

Пусть G=(V,E,λ,ρ) - ориентированный граф состояний (граф переходов). Путем (маршрутом) P из вершины v₀ в v_t называется последовательность смежных дуг графа (e₀, ..., e_t) такая, что e_i_-1 Ω e_i при 1≤i≤t. Множество путей {P₁,…,P_R}, соединяющих вход и выход графа G с n вершинами назовем покрытием этого графа, если любая дуга лежит хотя бы на одном из путей данного множества. Покрытие с минимальным числом путей назовем минимальным покрытием графа.

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

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

Если заданный тест не прошел, то на наличие ошибок подозреваются все вершины графа, которые были активизированы, при этом результат тестирования обозначим через 1. Результаты проверок по набору тестов образуют вектор z_jZ.

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

В рамках диагностической модели состояние ПО можно описывать

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

, которые могут быть реализованы с вероятностями ρ(s_k), где n – количество вершин графа.

Таким образом, имеем информационный канал связи между множеством векторов состояний автомата и множеством результатов тестирования на специально организованном множестве тестов. Канал связи описывается матрицей проверок B, в которой строки соответствуют тестам, а единицы в строке – активизированным соответствующим тестом вершинам графа. Связь между вектором состояний автомата s_kS,

и результатом тестирования z_j описывается преобразованием (рис.3.1):

z_j=Bs_k.

S

Z

Рисунок 3.1 – Соответствие между векторами результатов тестирования и подмножествами векторов состояний автомата

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

,

где H(S) - количество информации, необходимое для однозначного определения вектора состояний автомата. Реально вектор z_j доставляет в среднем количество информации, равное взаимной информации:

.

Поскольку неопределенность (энтропия) H(Z/S) появления z_j при заданном s_k равна 0, то

.

При этом коэффициент К, определяемый по формуле

,

показывает, какую часть составляет доставляемое в среднем вектором z_j количество информации от количества информации H(S).

Решены следующие задачи оптимизации:

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

- определение глубины локализации при заданном множестве тестов.

Для решения указанных выше задач необходимо упорядочить тесты по количеству информации, которое они доставляют. Располагая упорядоченной последовательностью тестов, можно определить их минимальное подмножество, которое обеспечивает заданную глубину локализации, или максимизировать ее при заданном количестве тестов. Например, если необходимо обеспечить глубину локализации состояния с коэффициентом, равным K=0,94, то из диаграммы (рис.3.2) следует, что в качестве минимального множества тестов необходимо выбрать тесты с номерами 5,4,2,3. Аналогично решается обратная задача. Если из допустимого множества тестов имеется возможность использования только теста 3, то для обеспечения максимальной глубины локализации необходимо выбрать тесты с номерами 5,4,2,3, при этом коэффициент K примет максимальное значение, равное K=0,94.

Рисунок 3.2 – Диаграмма зависимости коэффициента K от номера очередного вводимого теста

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

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

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

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

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

Решение о векторе состояний автомата принимается по критерию максимума апостериорной вероятности:

где

– апостериорная вероятность.

Определение вектора s_k состояний автомата, при котором апостериорная вероятность

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

В четвертой главе (Практические аспекты тестирования объектно-ориентированного программного обеспечения) приведен пример практического применения предложенных методов и алгоритмов. Рассматривается программный комплекс, реализующий определение множества тестов и локализацию ошибок, успешно применяемый при тестировании класса видео декодера в ЗАО Интел А/О”.

Рисунок 4.1 – Интерфейс пользователя для определения наиболее вероятного вектора состояний автомата

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

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

^

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

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

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

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

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

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

Публикации в рекомендованных ВАК изданиях

Малинин, С.Н. Тестирование объектно-ориентированных программ моделированием конечными автоматами [Текст] / Малинин С.Н. // Журнал «Известия высших учебных заведений. Поволжский регион. Технические науки» (индекс – 36966). – Пенза: ПГУ – 2009. – №2. – С. 63-70.

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