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

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

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

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

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

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

Институт Системного Программирования

Российской Академии Наук

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

БУРДОНОВ Игорь Борисович

Теория конформности для функционального

тестирования программных систем

на основе формальных моделей

специальность 05.13.11 –

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

АВТОРЕФЕРАТ

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

доктора физико-математических наук

Москва - 2008

Работа выполнена в Институте Системного Программирования РАН.

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

профессор

Евтушенко Нина Владимировна

доктор физико-математических наук,

профессор,

Крюков Виктор Алексеевич

доктор физико-математических наук,

профессор

Подловченко Римма Ивановна

Ведущая организация: факультет Вычислительной Математики и

Кибернетики МГУ им. М.В. Ломоносова

Защита диссертации состоится «21» мая 2008 г. в 15 часов на заседании диссертационного совета Д.002.087.01 при Институте Системного Программирования РАН по адресу:

109004, Москва, Б. Коммунистическая 25, Институт Системного Программирования РАН, конференц-зал.

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

Автореферат диссертации разослан «__» __________ 2008 г.

Ученый секретарь диссертационного совета /С.П.Прохоров/
кандидат физико-математических
наук

Содержание:

Актуальность исследования 4

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

Область исследования 9

Проблематика 17

Цели и задачи исследования 26

Методологическая и теоретическая основа исследования 29

Научная новизна исследования 30

Практическая значимость работы 32

Апробация результатов исследования 33

Публикации 35

Структура и объём работы 35

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

Заключение 51

Публикации автора по теме диссертации 57

Актуальность исследования

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

Однако, чем шире распространяется использование компьютеров, чем более важные и ответственные задачи возлагаются на их «плечи», тем выше становится цена ошибок в программно-аппаратных средствах. Только в США потери от этих ошибок составляют от 20 до 60 млрд. долларов ежегодно, причём около 60% убытков терпят конечные пользователи. Складывается ситуация, когда производители выпускают, а потребители вынуждены оплачивать заведомо бракованный товар. Но дело не только в материальном ущербе: некорректное поведение компьютерных систем способно вызвать дезорганизацию управления государством, привести к техногенным и экологическим катастрофам, поставить под угрозу жизнь и здоровье людей.





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

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

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

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

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

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

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



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

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

Решению этой задачи посвящена данная диссертация.

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

В работе рассматривается класс конформностей типа редукции, основанных на наблюдаемом поведении и параметризуемых семантикой тестового взаимодействия при функциональном тестировании. Семантика определяется набором допустимых тестовых воздействий и возможных ответных наблюдений над поведением системы. Наблюдения бывают двух типов: наблюдение внешнего действия, выполняемого реализацией, и, в некоторых случаях, наблюдение отказа – отсутствия действий. В начестве основной модели в диссертации выбрана система помеченных переходов (Labelled Transition System – LTS).

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

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

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

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

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

Область исследования

Тестирование на основе формальных моделей

Тестирование на основе формальных моделей – это новая дисциплина, сложившаяся последние десятилетия на стыке теории и практики информационных технологий. Это актуальное направление во многом опирается на работы различных исследователей, выполненные в 80-х и в 90-х годах прошлого века и посвященные проблемам тестирования телекоммуникационных протоколов. Самые первые же статьи, которые с полным правом можно отнести к этой области, появились еще в конце 60-х – начале 70-х годов. Тем не менее, серьезный практический и массовый интерес к результатам в этой области возник только на рубеже веков, в связи с востребованностью эффективных методов контроля и обеспечения качества сложных программных и программно-аппаратных систем в индустрии. Тестирование на основе моделей начинает применяться в промышленных компаниях. Первые же успехи (и, в не меньшей степени, первые неудачи) сделали разработку формальных методов тестирования чрезвычайно актуальными на сегодняшний день.

Основная идея тестирования на основе моделей вполне прозрачна: поскольку сложная система не поддается проверке «в лоб», создайте сначала более простую ее модель, описав в ней только то, что для вас важно на данном этапе, а затем стройте тесты только на основании полученной модели. Такой подход хорошо работает на практике, если саму модель и набор тестов удаётся строить по частям (инкрементально), постепенно отражая в модели набор свойств реальной системы и, соответственно, расширяя охват тестами различных аспектов работы системы. Как возможность такой инкрементальной разработки моделей и тестов, так и конкретные техники, используемые при этом, существенно зависят от самого вида применяемых моделей, и от того, какие имеются возможности по управлению тестируемой системой и наблюдению ее поведения.

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

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

 В диссертационной работе модель-2

Рис.1

В диссертационной работе модель тестируемой системы называется реализационной моделью или (для краткости) реализацией, модель требований – спецификацией, а их соответствие – (модельной) конформностью.1 При тестировании (в отличие от аналитической верификации) предполагается, что реализационная модель не задана или слишком сложна для анализа. Поэтому основной задачей является генерация по заданной спецификации модельных тестов, назначение которых – проверить конформность любой реализационной модели из рассматриваемого класса. Эта проверка основана на модели взаимодействия реальной системы с её окружением. Такую модель, как сказано выше, называют семантикой взаимодействия. Вводится модельное отношение «реализация проходит тест». Набор тестов принято называть полным, если реализация проходит каждый тест из набора тогда и только тогда, когда она конформна спецификации. После того, как тесты созданы, они транслируются в реальные тестовые программы, которые, взаимодействуя с реальной системой, устанавливают её соответствие или несоответствие исходным требованиям. Эта схема работы основана на следующих предположениях: во-первых, адекватны модели объектов (реализация и спецификация) и отношений (конформность и семантика взаимодействия), во-вторых, правильно выполняются преобразования (генерация модельных тестов и их трансляция в реальные тестовые программы).



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 

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







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

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