Введение к работе
Со времени разработки самых первых программ объемы и сложность разрабатываемых программных систем увеличились во много раз. Программное управление применяется во многих отраслях - начиная от обычных прикладных применений типа редактирования текстов до ответственных задач, например, управления ядерными реакторами, где цена ошибки может оказаться очень высокой.
Наиболее значимыми с точки зрения трудоемкости этапами жизненного цикла современных программных систем являются этапы верификации и поддержки, в том числе локализации и исправления найденных дефектов. Таким образом, снижение затрат на этих этапах существенно влияет на итоговую стоимость программного продукта и поэтому несомненно является актуальной задачей. Поэтому вопросам верификации и контроля качества программных систем всегда уделялось должное внимание со стороны научного сообщества — им посвящено множество исследований как отечественных, так и зарубежных ученых — В.В. Липаева, П.П. Пархоменко, В.И. Сагунова, В.Ю. Борзова, А.А. Шалыто, G.J. Myers, C.V. Ramamoorthy, Е.М. Clarke и других.
Существуют различные пути снижения стоимости поиска и устранения дефектов, в частности, автоматизация тестирования и поиск ошибок на ранних стадиях жизненного цикла. В настоящее время с целью выявления дефектов все чаще используются формальные методы верификации, основанные на статическом анализе и символьном выполнении программ.
В то же время применительно к программному обеспечению использование формальных методов сталкивается с определенными трудностями (хотя такие методы с успехом используются для верификации аппаратных средств), которые на данный момент полностью не решены. Связано это, в частности, с тем, что реализуемая программно обработка данных существенно сложнее, чем в случае аппаратных средств. В настоящее время ведутся активные исследования в области совместного использования формальных методов верификации и динамической верификации. К такому синтетическому подходу относится динамическое символьное выполнение (в англоязычных источниках получившее название concolic testing), получившее должное освещение в работах Koushik Sen (утилита CUTE), ученых из группы Microsoft Research - P. Godefroid, M. Levin (система Microsoft SAGE) и многих других. Вместе с тем в данной области остается ряд нерешенных проблем, поэтому исследования в области формальной верификации (в том числе формальной динамической верификации), несомненно, являются актуальными.
Целью работы является разработка базовой алгебраической модели программы и методов выбора множества тестовых воздействий, а также основанной на них системы автоматизации модульного тестирования, позволяющей снизить затраты на верификацию и поддержку программных систем.
Задачи работы
Для достижения поставленной цели требуется решение следующих задач:
-
анализ научных публикаций по теме исследования;
-
разработка алгебраической (базовой) модели программной системы;
-
разработка методов и алгоритмов выбора множества тестовых воздействий с целью достижения полного тестового покрытия;
-
программная реализация разработанных алгоритмов тестирования;
5. применение полученных результатов на практике.
Методы исследования
При разработке формальной модели программы и алгоритмов генерации тестовых воздействий используются методы из следующих разделов математики: методы дискретной математики (для анализа управляющих графов и выбора множества тестовых путей), методы компьютерной алгебры (для преобразования алгебраических выражений), методы теории компиляции (для построения модели и группировки машинных инструкций).
Научная новизна работы состоит в следующем:
-
Предложена новая базовая модель программной системы в виде множества связанных алгебраических выражений, независимая от языка программирования и по сравнению с существующими моделями позволяющая поставить в соответствие тестовым путям в программе условия их прохождения в символьном виде с учетом операций над указателями.
-
На основе предложенной модели разработан метод динамического символьного выполнения программы на уровне машинного кода программы и по сравнению с методами, работающими с исходными текстами, позволяющий упростить анализ программы и обрабатывать вызовы стандартных подпрограмм.
-
Разработаны алгоритмы выбора множества тестовых путей и определения соответствующих им тестовых воздействий, позволяющие достичь более полного тестового покрытия по сравнению с известными.
Обоснованность и достоверность результатов диссертационной работы обеспечены корректным использованием современного математического аппарата и подтверждены результатами вычислительных экспериментов.
Практическая ценность работы
На основе предложенных алгоритмов разработана система автоматизации модульного тестирования, позволяющая максимизировать достигаемое тестовое покрытие. Тем самым большее число ошибок может быть найдено на ранних стадиях жизненного цикла программного обеспечения, что приводит к снижению затрат на его стабилизацию. Система основана на динамическом
символьном выполнении программ на уровне машинных кодов и тем самым является независимой от используемых языков программирования.
Реализация результатов работы
Разработанные алгоритмы применяются в производственном процессе ООО «МФИ Софт», что подтверждается актом о внедрении, также используются в учебном процессе при подготовке магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ (Роспатент), свидетельство об официальной регистрации программы для ЭВМ №2013618486 от 10 сентября 2013 г.
Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». Номер государственной регистрации 01.2009.00405 от 28.01.09 - Н. Новгород: НГТУ), выполненной в рамках НИОКР «Диагностические и информационно-поисковые системы» (Номер регистрации 01201252337, интернет-номер И111112195013, руководитель работы Ломакина Л.С).
Апробация работы
Основные положения диссертации представлялись и докладывались на следующих научных конференциях:
Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011, ИСТ-2013)» (Нижний Новгород).
XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010).
IV Всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, 2010).
Нижегородской сессии молодых ученых (технические науки, 2011).
Международной молодежной конференции «Будущее технической науки» г. Н.Новгород, 2011 г., 2013 г.
X Международном симпозиуме «Интеллектуальные системы» INTELS'2012, г. Вологда, 2012 г.
XVII международной научно-практической конференции «Системный анализ в проектировании и управлении», г. Санкт-Петербург, 2013 г.
На защиту выносятся:
Базовая модель программной системы в виде множества связанных алгебраических выражений.
Диагностическая модель программной системы, включающая методы генерации тестовых воздействий и оценки полноты тестирования.
Метод тестирования программных систем на основе динамического символьного выполнения программ на уровне машинных инструкций.
Алгоритмы динамического символьного выполнения и выбора множества тестовых путей.
Публикации
По теме диссертационного исследования опубликовано 15 работ, в том числе 3 работы в рецензируемых научных изданиях, рекомендуемых ВАК, получено свидетельство о государственной регистрации программы для ЭВМ.
Структура и объем работы
Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложений. Общий объем работы 128 страниц текста, содержащего 19 рисунков и 3 таблицы. Список литературы содержит 102 наименования.
