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

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

ВИГУРА АНТОН НИКОЛАЕВИЧ

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

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

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

31 ОКТ 2013

Нижний Новгород — 2013 г.

005536959

005536959

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

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

руководитель: Ломакина Любовь Сергеевна

Официальные Орлов Юрий Федорович,

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

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

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

Волков Владимир Георгиевич,

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

ООО «МЕРА НН», руководитель проекта

Научно-исследовательский центр контроля и диагностики технических систем, г. Нижний Новгород («НИЦ КД»).

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

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. Р.Е. Алексеева Автореферат разослан « // » Ои^-^^Р 2013 года. Ученый секретарь ^ /

диссертационного совета Суркова Анна Сергеевна

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

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

Наиболее значимыми с точки зрения трудоемкости этапами жизненного цикла современных программных систем являются этапы верификации и поддержки, в том числе локализации и исправления найденных дефектов. Таким образом, снижение затрат на этих этапах существенно влияет на итоговую стоимость программного продукта и поэтому несомненно является актуальной задачей. Поэтому вопросам верификации и контроля качества программных систем всегда уделялось должное внимание со стороны научного сообщества — им посвящено множество исследований как отечественных, так и зарубежных ученых — В.В. Липаева, П.П. Пархоменко, В.И. Сагунова, В.Ю. Борзова, А.А. Шалыто, G.J. Myers, C.V. Ramamoorthy, Е.М. Clarke и других.

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

В то же время применительно к программному обеспечению использование формальных методов сталкивается с определенными трудностями (хотя такие методы с успехом используются для верификации аппаратных средств), которые на данный момент полностью не решены. Связано это, в частности, с тем, что реализуемая программно обработка данных существенно сложнее, чем в случае аппаратных средств. В настоящее время ведутся активные исследования в области совместного использования формальных методов верификации и динамической верификации. К такому синтетическому подходу относится динамическое символьное выполнение (в англоязычных источниках получившее название concolic testing), получившее должное освещение в работах Koushik Sen (утилита CUTE), ученых из группы Microsoft Research - P. Godefroid, M. Levin (система Microsoft SAGE) и многих других. Вместе с тем в данной области остается ряд нерешенных проблем, поэтому исследования в области формальной верификации (в том числе формальной динамической верификации), несомненно, являются актуальными.

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

Задачи работы

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

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

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

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

4. программная реализация разработанных алгоритмов тестирования;

5. применение полученных результатов на практике.

Методы исследования

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

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

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

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

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

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

Практическая ценность работы

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

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

Реализация результатов работы

Разработанные алгоритмы применяются в производственном процессе ООО «МФИ Софт», что подтверждается актом о внедрении, также используются в учебном процессе при подготовке магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ (Роспатент), свидетельство об официальной регистрации программы для ЭВМ №2013618486 от 10 сентября 2013 г.

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

Апробация работы

Основные положения диссертации представлялись и докладывались на следующих научных конференциях;

• Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011, ИСТ-2013)» (Нижний Новгород).

• XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010).

• IV Всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, 2010).

• Нижегородской сессии молодых ученых (технические науки, 2011).

• Международной молодежной конференции «Будущее технической науки» г. Н.Новгород, 2011 г., 2013 г.

• X Международном симпозиуме «Интеллектуальные системы» 1ЫТЕЬ8'2012, г. Вологда, 2012 г.

• XVII международной научно-практической конференции «Системный анализ в проектировании и управлении», г. Санкт-Петербург, 2013 г.

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

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

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

• Метод тестирования программных систем на основе динамического символьного выполнения программ на уровне машинных инструкций.

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

Публикации

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

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

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

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

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

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

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

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

1. определение полноты тестирования;

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

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

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

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

• мониторинга метрик качества в рамках систем непрерывной интеграции.

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

С целью решения данной задачи разработаны методы, основанные на символьном выполнении. Современные системы используют динамическое символьное выполнение, при котором одновременно производится выполнение программы «в числах» и «в символах», и численные значения данных используются в том случае, когда символьные не могут быть определены. Данный подход лежит в основе систем CUTE, CREST и Microsoft SAGE, причем CUTE и CREST работают на уровне исходного текста (на языке С), a SAGE — на уровне машинных кодов х86. Отметим, что существующие системы не позволяют обрабатывать в символьном виде операции разыменования указателей, что ограничивает их применимость. Кроме того, системы CUTE и CREST не поддерживают обработку взаимодействия инструментируемого и

неинструментируемого кода (например, стандартных подпрограмм), а SAGE является закрытым проектом и недоступна для экспериментов.

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

Во второй главе (Базовая модель программной системы) рассмотрены модели, на которых основано динамическое символьное выполнение — модель исполнителя и алгебраическая модель программы на основе базисных блоков. Приведено определение алгебраического выражения и алгоритмы преобразования выражений.

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

Будем исходить из следующих предположений:

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

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

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

Expr=Termsu{(o,a):oeOp,a<aExpr"">{°]) ,

где Expr — множество выражений, Term — множество термов, Ор — множество возможных операций, arity:Op-*U - отображение, определяющее для каждой операции количество аргументов.

На уровне машинных инструкций ЭВМ оперирует рациональными числами — константами и располагающимися по определенным адресам в памяти переменных. Исходя из этого, определим множество термов следующим образом: Term=QUAddrxTypes , где Л£&Л-с1Чи{0] — множество допустимых адресов, Types — множество примитивных типов данных.

Для дальнейшего анализа следует ввести две модели:

1. модель исполнителя (машины, исполняющей программу);

2. модель выполняемой программы.

Модель исполнителя. Исполнитель представляет собой абстрактную машину фон Неймана, в которой инструкции и обрабатываемые данные расположены в общем адресном пространстве, на каждом шаге выполнения исполняется одна инструкция, на которую указывает выделенный регистр PC (программный счетчик). Модель исполнителя определяет адресное пространство и допустимые операции над данными. Введем для удобства обозначение пустого кортежа X, которое в дальнейшем будем использовать для записи отсутствия объекта по определенному адресу памяти.

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

1. конкретная память - отображение val: AddrxTypes-*О, ставящее в соответствие каждой переменной, располагающейся по данному адресу и имеющей заданный тип, ее численное значение (которое будем в дальнейшем называть конкретным значением);

2. символьная память — отображение sym:AddrxTypes-* ЕхргиЩ, ставящее в соответствие каждой переменной, располагающейся по данному адресу и имеющей заданный тип, ее символьное значение;

3. входные переменные, определяемые отображением input: AddrxTypes-*Terms. Входные переменные непосредственно доступны для изменения в процессе тестирования.

Операции над данными

Все инструкции разделены на два класса: инструкции с побочными эффектами (все инструкции, модифицирующие значения в памяти) и инструкции - ветвления, осуществляющие передачу управления на заданный адрес в зависимости от значения некоторой ячейки памяти.

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

ins-{(addr, expr,bt ,bf))S Addr XExpr xAddrXAddr ,

где addr — адрес инструкции, expr — выполняемое выражение, bt — адрес следующей инструкции в случае истинности значения е, bf — адрес следующей инструкции в случае ложности значения е. Для ветвлений ЫфЬ/ , для прочих

инструкций bt=bf. Пусть ins(addr) есть инструкция, располагающаяся по адресу addr.

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

1. Операция присваивания а=Ь.

2. Операция ветвления: ifia), проверяющая условие а, и при его истинности осуществляющая переход по адресу btrue, иначе — по адресу bfalse.

3. Арифметические и логические операции, унарные и бинарные (+, *, Г).

4. Операции сравнения (= =, !=, <, >, <=, >=).

5. Операция разыменования указателя derefia, t), возвращающая значение, сохраненное по адресу а и имеющее примитивный тип U

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

Модель программы

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

выполнение. Обозначим множество базисных блоков программы через ВВ,

00

причем В В a ins'= U ■ i=0

Обозначим адрес входного базисного блока через entry, а адрес выходного базисного блока через exit, также обозначим через contains(bb.insn) факт принадлежности инструкции insn блоку ЬЬ. Программу будем представлять в виде тройки Р=( ВВ, entry, exit). Состояние исполнителя в каждый момент времени определяется адресным пространством, значением программного счетчика и текущими значениями переменных: U=( Addr, PC, val, sym).

На рис. 1 наглядно изображены модель исполнителя и модель программы для следующего простого фрагмента программы:

i = j; // ВВ1 <—- PC

if (i < S) {

i += i * 2; // BB2

} else { i *= s; // ВВЗ

)

return i;

Модель программы:

ВВ={ВВ1, ВВ2, ВВЗ,ВВ4);

M/=((l,(=,(i.y)).2.2).(2,(ir,(<.i.i)).10,20));

/Ш=((10, ( = ,(/,(+.(/.(*.(/. 2)))))), 30,30));

ВВЗ=((20, ( = ,(/,(*,(<■ s)))). 30,30));

ВВ4=(( 30, ( = , [ret, i ), exit, exit ) )).

Здесь ret — регистр, в который помещается возвращаемое значение, а exit — адрес точки выхода.

Подстановка значений является одной из основных операций, производимых при символьном выполнении. Как было показано ранее, для каждой переменной veAddrxTypes в памяти может быть определено два значения — конкретное val(v) и символьное îjto(v). Данные значения неизвестны на этапе построения модели и определяются только на этапе тестовых запусков.

Исполнитель

Программный счетчик (PC)

Конкретная память

addr

val

Символьная память

addr

sym

Входные переменные

addr

input

Программа

вв\

addr expr bt bf

1 i=j 2 2

2 ij(i<s) 10 20 <

*

ВВ2

addr expr bt bf

10

ВВЗ

addr expr bt bf

20

Рис. 1. Модель программы и модель исполнителя

Отметим, что символьные значения переменных могут определяться и использоваться не во всех случаях:

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

символьном виде или не поддерживается системой автоматизации тестирования.

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

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

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

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

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

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

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

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

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

хут(а)=\;

сопс(а),

.тоА.?/: Ехрг -»Ехрг; лг<б5((а)= сопс(Ь),

а € Тегтз,

а^.Ехрг /\a-ideref ,(£>)).

(о,(.5и6л(а,),...,5мЬл(о„))), аеЕхргАа-(о ,(а> ...,а„)).

участкам, базисным блокам и т.п.), а дуги — передачам управления между этими операторами. УГП имеет строго одну входную и одну выходную вершину.

Таким образом, будем задавать управляющий граф кортежем G={V ,E,s,e,w),seV ,ееУ, где VEJnsn - множество вершин, ЕеУхУ -множество дуг, s - входная вершина, е - выходная вершина, w — отображение, ставящее в соответствие вершинам и дугам графа их вес.

Управляющий граф может быть получен на основе базовой модели программы следующим образом:

v=[i;ie lnsn Л 3 bbeBB: contains (bb,i); Е={{и ,v)-bt(u)=Wbf{u)=v}; s=i:ie lnsn Л addr {i)=start; e=i: i 6 lnsn Л addr (i)=end.

Путь P в графе может быть представлен как упорядоченная

последовательность вершин: p=(Vl>v2.....v,,.„, vJ;PeV'. Для каждой вершины и

дуги управляющего графа определим вес w(v), представляющий собой число прохождений по данной вершине или дуге в ходе тестирования программы:

м>:Ки£-*ЛГи[0) .

Пример базовой модели и построенного по ней управляющего графа приведен на рис. 2 (веса дуг не приведены).

int max(int *а, int s) { int m = *a, *e = a + s; while (a < e) { if (*a > m) m = *a;

-H-a;

}

return m;

}

BB1:

(0, m = *a, 1, 1), (1, e = a + s, 2,2),

BB2: 1

(2, if (a<e), 3, 6). (3, if(dere%)<-m), 6, 5), (4, m = dereffa), 6, 6)

BB4: (6, ret =

m, 0, 0)

BB3: (5, a = a + 1,2, 2)

Исходный текст Базовая модель Управляющий граф

Рис. 2. Базовая модель и управляющий граф

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

(е:ееЯлн,(е)>0]|

И

Данное значение будем использовать в качестве критерия полноты тестирования (целью является достижение значения Сь= 1).

Генерация тестовых воздействий

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

13

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

Пусть Inputs={а:aeTermsAinptit{a)*k] - множество входных переменных программы. Тогда тестовым воздействием будем называть отображение вида test-.Inputs-* Q, ставящее входным переменным их начальные конкретные значения. Каждому тестовому воздействию соответствует некоторый путь Р в управляющем графе программы. Множеству тестовых воздействий Tests={testl,test1,...,testJ , таким образом, соответствует некоторое множество путей Paths и значение критерия полноты тестирования, в частности, покрытия ветвей Сь.

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

Рис. 3. Схема структурного тестирования

Данная схема отражает как автоматические, так и ручные варианты тестирования, и содержит следующие элементы:

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

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

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

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

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

р=(у,,у2.....v,,): сопс1(Р)=сопсЦу1)лсопсЦу1)л...лсопЫ(у„).

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

Условия прохождения путей определяются с помощью динамического символьного выполнения. Для описания его алгоритма введем обозначения: «<—» - операция присваивания, « ° » - операция конкатенации, уа1(у) - конкретное значение результата вычисления выражения у.

Рис. 4. Блок-схема алгоритма динамического символьного выполнения

Результатами работы алгоритма являются: пройденный тестовый путь p=(msn,,insn2,...,insn,i), обновленные веса дуг управляющего графа (тестовое покрытие), условия прохождения каждой из вершин тестового пути cond(insri).,

условие прохождения тестового пути cond(P)= Acond(insn), символьные

значения переменных по окончании выполнения программы (функция пути)

sym .

ВВ val sym

PC-i ►10 а = Ь + с 11 11

11 if(a> 0) 20 12

а а X

Ь 20 Ъ X

с 1 с х+у

X 0 X X

У 1 У У

РС= 10: a = ¿ + c-а = 20+х+у

У ч

val =20; val = 1; val(a) «-21;

sym = X: sym = x+y; sym(a) *— 20+.x+,v;

conc = 20. conc = x+y. cond( 10) <— 1.

PC «—11: if(a> 0)-i/(20+x +v>0)

/ 4

val = 21; val = 0; cond( 11)«- 20+x+y>0.

sym = 20+x+y; sym = X.; conc = 20+x+y. conc = 0.

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

Блок-схема алгоритма приведена на рис. 4. На рис. 5 наглядно изображено символьное выполнение двух последовательно расположенных машинных инструкций — инструкции присваивания и инструкции ветвления. По завершении символьного выполнения на основе полученных данных о покрытии и условии прохождения текущего пути осуществляется выбор следующего тестового пути. Предположим, что при некотором тестовом запуске был пройдет тестовый путь P=(v,, v2,..., v„), и были определены условия прохождения его вершин cond(v,). Чтобы определить тестовое воздействие, приводящее к прохождению некоторого альтернативного тестового пути, нам нужно:

• Найти непокрытую дугу e=(vk,v¡) в управляющем графе, начальная вершина которой v, принадлежит пути Р. Поскольку все дуги рассматриваемого пути были покрыты при предыдущем тестовом запуске, v't не может принадлежать Р — т. е. дуга е может начинаться только в инструкции ветвления.

• Найти нарушающее условие с в виде конъюнкции условий прохождения вершин пути Р от начальной до vk включительно и инверсии условия вершины vtt,. Инверсия последнего условия требуется, чтобы управление в инструкции ветвления vk передавалось по альтернативной дуге е .

16

• Найти тестовое воздействие, решив нарушающее условие.

Алгоритм выбора тестовых путей

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

1. Выполняется построение управляющего графа программы G(V,E,s,e,w), причем перед выполнением тестирования веса всех дуг принимаются равными нулю. Инициализируется множество всех пройденных путей Paths = 0.

2. Производится выполнение программы для произвольного тестового воздействия, при этом определяется пройденный путь P=(v|tv2,...,v„) и

Я

условие его прохождения cond{P)= Acond(vj). Путь добавляется в множество Paths.

3. В каждом из путей в Paths выполняется поиск дуги с нулевым весом (с помощью алгоритма поиска в глубину). Если непокрытых дуг нет, достигнуто максимальное значение Сь= 1, и тестирование завершается.

3.1. Найдена дуга e=(vt,vt*) в некотором пути Q=(v,,v2,..., vt.....v„,).. В

4-1

этом случае вычисляется условие c=cond(vt)A{ A cond(vj)).

j=i

3.2. Найденное решение обрабатывается граничным решателем с целью поиска подходящего тестового воздействия. Если тестовое воздействие было найдено, производится тестовый запуск программы с определением нового пути Р (добавляемого в множество Paths), весов w и условий cond.

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

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

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

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

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

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

2. Подсчет покрытия кода (покрытие строк и ветвей) без необходимости сборки специальных исполняемых образов.

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

4. Сохранение дампов трасс выполнения программы с целью отложенного анализа и локализации дефектов.

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

6. Поддержка различных аппаратных архитектур ЭВМ. Система поддерживает все архитектуры, для которых реализована трансляция кода в Valgrind (х86, AMD64, POWER, ARM).

Тест-драйвер запуск f

тестовое воздействие

Тестируемая программа

Valgrind 11

| Декомпиляция

Базисные блоки (VEX IR)

Вставка инструментального кода

Модифицированная программа

Выполнение

......f......

Выходные данные

I

«1 it g? i i i i t t » • i

l! i i i i

¡as i i i * i t i

Разделяемая память:

- инструкции;

- ветвления;

- события;

- конкретные значения переменных;

- символьные значения переменных;

Дамп истории

выполнения

программы

Тест-оракул: проверка выходных данных

Отчет о тестировании

Модуль анализа —Запись дампа |

Оценка покрытия строк кода

Отслеживание работы с памятью

Построение управляющего графа

Оценка покрытия ветвей

Символьное выполнение 3=

Оптимизатор: выбор тестовых воздействий

| Тестовые воздействия "|

Рис. 6. Архитектура системы 18

Система состоит из трех модулей — инструментального модуля, модуля анализа и тест-драйвера, связанных между собой разделяемой памятью (рис. 6).

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

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

Эксперимент 1. Модульное тестирование

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

• сортировка методом выбора главного элемента (sort);

• сортировка указателей методом выбора главного элемента (psort);

• модифицированные варианты с добавленным ветвлением вида /У(я[/']==13);

• вычисление частичной суммы числового ряда (series);

• быстрая сортировка, реализованная вручную (qsort);

• быстрая сортировка из стандартной библиотеки С (qsort_std) -выполнялось тестирование обратного вызова функции сравнения;

• вставка и последующее удаление элементов в черно-красное дерево (rbtree) из реализации std::set в GNU libstdc++;

В процессе тестирования определялось достигнутое покрытие ветвей. Результаты (достигнутое покрытие ветвей С4 и число тестовых воздействий N, при котором достигнуто указанное покрытие) приведены в таблице 1.

Тест случайное тестирование CREST разработанная система

N сь N с» N с,

sort 4 1 4 1 4 1

psort 4 1 4 1 4 1

sort* 4 0,93 9 0,93 4 1

psort* 4 0,94 9 0,94 4 1

series - 0 8 1 6

qsort 13 0,94 8 1 5 1

qsort_std 3 1 - 0 3 1

rbtree 13 1 - 0 6 1

Таблица 1. Результаты сравнительных экспериментов

Интерпретация результатов следующая. Примеры sort и psort оказались достаточно простыми для достижения полного покрытия кода для всех трех методов. В программах sort* и psort* система CREST не смогла найти добавленное ветвление из-за отсутствия поддержки операций с указателями. В примере series достичь полного покрытия удалось только с помощью символьного выполнения из-за строгого условия входа в подпрограмму, которое при случайном тестировании никогда не выполнялось, при этом разработанная система достигла полного покрытия ветвей меньшим числом тестов. Аналогичная ситуация наблюдается в примере qsort (сложные условия ветвлений не могут быть проверены полностью случайным тестированием). Примеры qsort и rbtree система CREST выполнить не смогла, разработанная же в настоящей работе система показывает в целом лучшие результаты, чем случайное тестирование.

Эксперимент 2. Интеграционное дизайн-тестирование

В качестве эксперимента производилось тестирование одного из компонентов самой системы автоматизации тестирования — граничного решателя, основанного на генетическом алгоритме, а также его графического интерфейса пользователя. Компонент написан на C++/Qt4, состоит из примерно 20 тысяч строк исходного текста (с учетом транслятора символьных условий, базовых библиотек и графического интерфейса), графический интерфейс предоставляет следующую функциональность:

• Ввод и компиляцию в машинный код целевой функции в виде алгебраического выражения.

• Минимизацию значения целевой функции с помощью генетического алгоритма с использованием распараллеливания.

• Визуализацию результатов оптимизации и графиков изменения целевой функции в зависимости от итерации.

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

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

Эксперимент 3. Тестирование производительности

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

Тип запуска Производительность, БМ1Р8 Время выполнения одной итерации, мкс

Без инструментирования 6587 0,09

ОСС^соу 5591 0,10

Уа^ппс! (только рекомпиляция) 1504 0,39

Уа^ппс! (тешсЬеск) 166 3,43

Покрытие ветвей, инструментирование каждой инструкции 64,1 8,88

Покрытие ветвей, оптимальное инструментирование 544 1,05

Запись дампа, оптимальное инструментирование 547,2 1,04

Отслеживание памяти (помеченные участки) 45,5 12,6

Отслеживание памяти (все операции) 11,8 48,0

Динамическое символьное выполнение 11,7 48,6

Таблица 2. Результаты синтетического теста

Результаты синтетического теста наглядно показывают превосходство в плане производительности инструментирования на уровне исходных текстов (GCC/gcov). Динамическая рекомпиляция в Уа^ппс! приводит к падению производительности в 4-5 раз даже без вставки инструментального кода — данные накладные расходы являются платой за гибкость динамических методов

инструментирования. Для сравнения приведена производительность, достигнутая встроенным инструментом Уа^ппс! тетсЬеск.

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

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

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

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

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

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

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

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

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

5. Результаты диссертационной работы внедрены в производственный процесс ООО «МФИ Софт» и учебный процесс подготовки магистрантов

направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых изданиях

[1] Вигура, А.Н. Анализ и тестирование программ на основе алгебраической модели [Текст] / А.Н. Вигура // Журнал «Вестник Нижегородского государственного университета». — Нижний Новгород — 2011. — № 5(1). — с. 189196.

[2] Вигура, А.Н. Модели и методы тестирования программных систем на основе алгебраического подхода [Текст] / Ломакина Л.С., А.Н. Вигура // Журнал «Системы управления и информационные технологии». — Воронеж, 2013. — №2.1(52).— с. 157-161.

[3] Вигура, А.Н. Тестирование программных систем на основе динамического символьного выполнения [Текст] / А.Н. Вигура // Журнал «Научно-технический вестник Поволжья». - 2013. - №4. - с. 133-136.

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

[4] Вигура А.Н. Диагностика технических и программных систем с использованием современных информационных технологий [Текст] (научный руководитель Л.С. Ломакина) / А.Н. Вигура, A.C. Базин, В.П. Губернаторов и др. // Отчет по НИР No государственной регистрации 01.2009.00405 от 28.01.09 - Н. Новгород: НГТУ,- 127 с.

[5] Вигура, А.Н. Структурное тестирование программных систем на основе принципа минимального покрытия [Текст] / А.Н. Вигура // Материалы Международной научно - технической конференции «Информационные системы и технологии (ИСТ-2009)», 17 апреля 2009 г. - Н. Новгород: НГТУ, 2009. - с. 259-261.

[6] Вигура, А.Н. Автоматизация тестирования программного обеспечения на основе символьного выполнения [Текст] / А.Н. Вигура // Материалы 15-й Международной открытой научной конференции «Современные проблемы информатизации». - Воронеж: ВГТУ.2010.-С. 414-418.

[7] Вигура, А.Н. Разработка метода и алгоритма тестирования программных систем на основе алгебраического подхода [Текст] / А.Н. Вигура // Материалы Международной научно- технической конференции «Информационные системы и технологии (ИСТ-2010)», 17 апреля 2010 г. - Н. Новгород: НГТУ, 2010. - с. 298-299.

[8] Вигура, А.Н. Система семантического анализа текстов программ [Текст] / А.Н. Вигура // Материалы конференции «XVI Нижегородская сессия молодых ученых. Технические науки», 17 апреля 2011 г. — Н. Новгород: Гладкова O.A., 2011.-с. 173-176.

[9] Вигура, А.Н. Использование генетических алгоритмов для генерации тестов программ [Текст] / А.Н. Вигура // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2011)», 17 апреля 2011 г.-Н. Новгород: НГТУ, 2011.-с. 319.

[10] Вигура, А.Н. Генерация тестовых наборов для программ на основе заданных ограничений на входные данные [Текст] / А.Н. Вигура // Материалы XII Международной научно-технической конференции «Будущее технической науки», 24 мая 2011 г. - Н. Новгород: НГТУ, 2011. - с. 44-45.

[11] Вигура, А.Н. Автоматизация поиска тестов программ на основе генетического алгоритма [Текст] / А.Н. Вигура // Интеллектуальные системы: Труды Десятого международного симпозиума / под ред. К.А. Пупкова. - М.: РУСАКИ, 2012, с. 184-187.

[12] Вигура, А.Н. Автоматизация тестирования программных систем на основе динамического символьного выполнения [Текст] / А.Н. Вигура // Труды XVII Международной научно-практической конференции «Системный анализ в проектировании и управлении», 1-3 июля 2013 г. — Санкт-Петербург: СПб. ГПУ, 2013.-с. 77-84.

[13] Вигура, А.Н. Автотрассировка программ на основе динамической рекомпиляции [Текст] / А.Н. Вигура // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2013)», 19 апреля 2013 г. -Н. Новгород: НГТУ, 2013.-е. 16-17.

[14] Вигура, А.Н. Определение тестовых покрытий программ на основе динамической рекомпиляции [Текст] / А.Н. Вигура // Материалы XII Международной научно-технической конференции «Будущее технической науки», 24 мая 2013 г. - Н. Новгород: НГТУ, 2013. - с. 41-42.

[15] Вигура, А.Н. Система автоматизации тестирования программ на основе динамического символьного выполнения / А.Н. Вигура // Свидетельство об официальной регистрации программы для ЭВМ №2013618486. Зарегистрировано в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ (Роспатент) от 10 сентября 2013 г.

Подписано в печать 10.10.2013. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Зак. 721.

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, г. Нижний Новгород, ул. Минина, 24.

а / , w !

Нижегородский государственный технический университет

им. Р.Е. Алексеева

04201 453 531

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

ВИГУРА Антон Николаевич

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

05.13.01 - «Системный анализ, управление и обработка информации (в науке и

промышленности)» (технические науки)

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

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

Нижний Новгород - 2013

Введение......................................................................................................................4

Глава 1. Обзор существующих ¡методов верификации программных систем и постановка задачи..................................................................................................9

1.1. Методы верификации программных систем................................................10

1.2. Тестирование программных систем.............................................................15

1.4. Уровни и методы тестирования.....................................................................16

1.5. Состав систем автоматизации тестирования...............................................20

1.6. Оценка тестового покрытия и динамический анализ программ................21

1.7. Динамический анализ программ...................................................................22

1.8. Генерация тестовых воздействий..................................................................27

1.9. Символьное выполнение................................................................................29

1.11. Компьютерная алгебра и символьные алгоритмы.....................................34

1.12. Выводы и постановка задачи.......................................................................37

Глава 2. Базовая модель программной системы...............................................38

2.1. Алгебраические выражения..........................................................................39

2.2. Анализ выражений........................................................................................43

2.3. Общие обозначения........................................................................................44

2.4. Модель исполнителя.......................................................................................45

2.5. Модель программы.......................................................................................47

2.6. Построение базовой модели программы......................................................53

2.7. Подстановка значений и конкретизация.......................................................56

2.8. Преобразования выражений..........................................................................57

2.9. Выводы............................................................................................................61

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

3.1. Граф-модель программы................................................................................64

3.2. Построение управляющего графа программы.............................................67

3.3. Матричные и списковые представления графов.........................................68

3.4. Структурные критерии полноты тестирования...........................................70

3.5. Методы выбора тестовых воздействий........................................................72

3.6. Динамическое символьное выполнение.......................................................77

3.7. Выбор тестовых путей...................................................................................81

3.8. Выбор тестовых воздействий........................................................................84

3.9. Инструментирование......................................................................................86

3.10. Выводы..........................................................................................................90

Глава 4. Практическая реализация и вычислительные эксперименты.......91

4.1. Реализация системы автоматизации тестирования.....................................91

4.2. Практический пример модульного тестирования.......................................97

4.3. Сравнительные эксперименты....................................................................103

4.3. Тесты производительности..........................................................................107

4.4. Интерактивное дизайн-тестирование программной системы..................110

4.5. Выводы..........................................................................................................113

Заключение.............................................................................................................114

Библиографический список.................................................................................116

Приложения............................................................................................................128

*

Введение

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

Наиболее значимыми с точки зрения трудоемкости этапами жизненного цикла современных программных систем являются этапы верификации и поддержки, в том числе локализации и исправления найденных дефектов. Таким образом, снижение затрат на этих этапах существенно влияет на итоговую стоимость программного продукта и поэтому несомненно является актуальной задачей. Поэтому вопросам верификации и контроля качества программных систем всегда уделялось должное внимание со стороны научного сообщества — им посвящено множество исследований как отечественных, так и зарубежных ученых — В.В. Линаева, П.П. Пархоменко, В.И. Сагунова, В.Ю. Борзова, G.J. Myers, C.V. Ramamoorthy, Е.М. Clarke и других.

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

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

существенно сложнее, чем в случае аппаратных средств. В настоящее время ведутся активные исследования в области совместного использования формальных методов верификации и динамической верификации. К такому синтетическому подходу относится динамическое символьное выполнение (в англоязычных источниках получившее название concolic testing), получившее должное освещение в работах Koushik Sen (утилита CUTE), ученых из группы Microsoft Research - P. Godefroid, M. Levin (система Microsoft SAGE) и многих других. Вместе с тем в данной области остается ряд нерешенных проблем, поэтому исследования в области формальной верификации (в том числе формальной динамической верификации), несомненно, являются актуальными.

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

Задачи работы

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

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

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

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

4. программная реализация разработанных алгоритмов тестирования;

5. применение полученных результатов на практике.

Методы исследования

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

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

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

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

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

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

Практическая ценность работы

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

Реализация результатов работы

Разработанные алгоритмы применяются в производственном процессе ООО «МФИ Софт», что подтверждается актом о внедрении, также используются в учебном процессе при подготовке магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева.

Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ (Роспатент).

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

Апробация работы

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

• Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011, ИСТ-2013)» (Нижний Новгород).

• XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010).

• IV Всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, 2010).

• Нижегородской сессии молодых ученых (технические науки, 2011).

• Международной молодежной конференции «Будущее технической науки» г. Н.Новгород, 2011 г., 2013 г.

• X Международном симпозиуме «Интеллектуальные системы» ГЫТЕЬ8'2012, г. Вологда, 2012 г.

• XVII международной научно-практической конференции «Системный анализ в проектировании и управлении», г. Санкт-Петербург, 2013 г.

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

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

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

• Метод тестирования программных систем на основе динамического символьного выполнения программ на уровне машинных инструкций.

Публикации

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

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

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

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

В настоящее время актуальной является проблема контроля и обеспечения надежности программных систем. Как известно, надежность любой вычислительной системы обусловлена двумя факторами — надежностью аппаратного обеспечения и надежностью программ, управляющих аппаратным обеспечением [1]. При этом, хотя для диагностирования аппаратных средств разработаны эффективные методы, позволяющие выявлять дефекты и формально обосновывать их отсутствие [2, 3], аналогичная задача для программ в полной мере не решена. Постоянное усложнение используемых на практике в различных отраслях промышленности программных систем привело к разработке разнообразных методов верификации [4] и к активным исследованиям как в области верификации и тестирования, так и в области синтеза надежных и контролепрпгодных программ [5, 6, 7].

Известно, что более половины стоимости программного продукта приходится на его верификацию и поддержку [8]. Как следствие, основным способом контроля качества программных систем в настоящее время является тестирование — компромиссное решение в плане трудоемкости и эффективности нахождения дефектов, причем сложность современных программных систем приводит к необходимости декомпозиции программных систем и выполнения тестирования на различных уровнях (модульное, интеграционное, системное тестирование), а также к необходимости автоматизации этих видов тестирования с целью снижения затрат на верификацию.

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

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

1.1. Методы верификации программных систем

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

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

Все разнообразие методов верификации можно разделить на следующие группы [4]:

1. экспертиза;

2. статические методы (поиск ошибок по шаблонам, проверка правил корректности);

3. формальные методы (например, методы автоматического доказательства теорем, проверка моделей, символьное выполнение);

4. динамические методы (тестирование, мониторинг и профилирование);

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

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

Достоинством таких методов является сравнительная простота: например, элементарный статический анализ присутствует в компиляторах. Например, статический анализатор Clang [9] позволяет обнаруживать, в частности, такие ошибки, как некорректную работу с указателями, с динамическим распределением памяти (утечки памяти и повторное освобождение).

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

Формальные методы позволяют проверить соответствие программы некоторой формальной спецификации. Достоинством является возможность находить сложные ошибки, недостатком — высокая трудоемкость. Формальные методы применимы только к тем свойствам, которые выражены формально в рамках некоторой математической модели, а также к тем артефактам, для которых можно построить адекватную формальную модель. Соответственно, для использования таких методов в проекте необходимо затратить значительные усилия на построение формальных моделей. К тому же, построить такие модели и провести их анализ могут только специалисты по формальным методам, которых не так много, и чьи услуги стоят достаточно дорого. Построение формальных моделей нельзя автоматизировать, для этого всегда необходим человек. Анализ их свойств в значительной мере может быть автоматизирован, и сейчас уже есть инструменты, способные анализировать формальные модели промышленного уровня сложности, однако чтобы эффективно пользоваться ими часто тоже требуется очень специфический набор навыков и знаний (в специфических разделах математической логики и алгебры). Тем не менее, в ряде областей, где последствия ошибки в системе могут оказаться чрезвычайно дорогими, формальные методы верификации активно используются в силу своей способности обнаруживать сложные ошибки, на практике не выявляемые экспертизой или тестированием [4].

Формальные методы верификац�