авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

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

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

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

Специальность 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 и ряда других отечественных и зарубежных ученых. В качестве модели тестирования ПО в этих работах предлагается использовать управляющий граф программы. Однако, методы, разработанные для данной модели, хорошо зарекомендовали себя при тестировании традиционного (процедурного) ПО, но при непосредственном применении к ОО ПО имеют трудно решаемые проблемы.



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

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

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

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

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

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

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

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

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

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

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

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». № государственной регистрации 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.

 1 – Пример потока сообщений-0

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

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

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

  • X – множество входных символов (входной алфавит);
  • V – множество состояний автомата (внутренний алфавит);
  • Y – множество выходных символов (выходной алфавит);
  • (X V) V – функция переходов;
  • (XV) Y – функция выходов при той же области определения, что , т.е. Dom = Dom;
  • v0V – начальное состояние.

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

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

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

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

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

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

:EV и :EV.

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

e1,e2E e1e2 (e1)=(e2).

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

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

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

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

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

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

Пусть G=(V,E,,) - ориентированный граф состояний (граф переходов). Путем (маршрутом) P из вершины v0 в vt называется последовательность смежных дуг графа (e0,..., et) такая, что ei-1 ei при 1it. Множество путей {P1,…,PR}, соединяющих вход и выход графа G с n вершинами назовем покрытием этого графа, если любая дуга лежит хотя бы на одном из путей данного множества. Покрытие с минимальным числом путей назовем минимальным покрытием графа.

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

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

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

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

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



Pages:   || 2 |
 

Похожие работы:










 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.