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

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

Петров Кирилл Владимирович

и03054Э7,8

Автоматизированная система моделирования логических неисправностей для тестирования вычислительных процессов

Специальность05 13.12-Системы автоматизации проектирования (приборостроение)

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

Санкт-Петербург 2007

003054978

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики

Научный руководитель

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

Немолочнов Олег Фомич

Официальные оппоненты

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

Гатчин Юрий Арменакович

кандидат технических наук Суханов Андрей Вячеславович

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

ФГУП "Санкт-Петербургское ОКБ "Электроавтоматика"

Защита диссертации состоится 17 апреля 2007 года в 15 часов 50 минут на заседании диссертационного совета Д 212 227 05 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу 197101, Санкт-Петербург, Кронверкский пр , д 49

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО

Автореферат разослан 16 марта 2007 г

Ученый секретарь совета Д 212 227 05

И л -у к т н-> Доцент Поляков Владимир Иванович

Общая характеристика работы Актуальность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Создание на основе разработанных методов автоматизированной системы, позволяющей оценивать и повышать эффективность тестирования, данная система будет являться подсистемой учебно-исследовательской САПР верификации и тестирования вычислительных процессов

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

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

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

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

В работе получены следующие научные результаты, выносимые на защиту

1) Предложен новый критерий оценки качества тестовых наборов - критерий покрытия простых логических неисправностей в условиях-предикатах вычислительных процессов

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

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

4) На основе перечисленных методов предложен алгоритм работы автоматизированной системы моделирования неисправностей, являющейся частью учебно-исследовательской САПР верификации и тестирования вычислительных процессов, и используемой для проверки и повышения эффективности тестирования

Практическое значение работы состоит в следующем

1) Дан пример использования логических неисправностей определенного вида для оценки качества тестовых наборов

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

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

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

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

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

Результаты, полученные в диссертации, используются на практике в учебном процессе кафедры Информатики и Прикладной Математики СПбГУ ИТМО, а также в ФГУП "Санкт-Петербургское ОКБ "Электроавтоматика"

Апробация диссертации

Основные положения диссертационной работы докладывались на XXXIV научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2005), II конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2005), XXXV научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2006), III конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2006)

Публикации

По теме диссертации опубликованы 5 печатных работ, в том числе три статьи в научных сборниках и две статьи в трудах научных конференций

Структура диссертации

Диссертация состоит из введения, четырех глав и заключения Общий объем диссертации составляет 159 страниц Список литературы содержит 71 наименование Работа иллюстрирована 28 рисунками

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

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

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

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

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

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

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

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

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

(Л, >

Л

Программа

Вычиаите1ь 1

Вычис. гите гьныи процесс

1 АО Мщу

■ АПЛ

2 АО, к!т э \nJutnp

щ—— ля ■

еГ 3 АО, \jjump

I "

г

Рис 1 Концептуальная модель вычислительного процесса

Концептуальная модель вычислительного процесса, порождаемого программой при интерпретации ее команд вычислителем (процессором), показана на рис 1

Здесь X - множество независимых переменных (параметров) программы, R и R' - множества вычисляемых переменных, соответственно, предыдущие и последующие их значения Вычисления начинаются в одной из точек входа (Тт) и заканчиваются в одной из точек выхода (Тм)

Передача управления между командами программы осуществляется командами условной (lflump) и безусловной (Jump, inJump) передачи управления (команда inJump осуществляет последовательную передачу управления от команды к команде по счетчику текущего адреса исполняемой команды и тем самым реализует исполнение линейных участков)

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

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

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

Значения переменных из R и R' могут различаться до начала вычислительного процесса и совпадают после его окончания Для значений любой переменной г е R и г' е R' можно установить следующие соотношения

г г'

X |IFR| } итеративное

р |RFR| 1 вычисление рекуррентное

р Р | определенного

X X ) хранение неопределенного

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

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

Логическая неисправность - искажение логики работы программы В выходных данных логическая неисправность будет проявляться в виде ошибки

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

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

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

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

- неисправность, при которой всегда происходит переход по указанному в команде адресу,

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

В первом случае условие перехода становится тождественно истинным (Cond = Т), во втором - тождественно ложным (Cond =F) Неисправности первого рода будем обозначать mTCo„d, а второго, соответственно, m'w, (рис 2)

а) б) в)

Рис 2 Моделирование неисправностей в команде условного перехода

а) ifJump без неисправностей

б) ifJump с неисправностью m[onl, соответствующая Cond s f

в) ifJump с неисправностью mTUmd, соответствующая Cond = г

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

Если тестовая последовательность, качество которой мы оцениваем, не выявит исчезновение дуги, т е среди выходных данных не будет ошибочных, то ее следует дополнить набором, подобранным специально с целью обнаружения внесенной неисправности Можно утверждать, что полнота контроля всех неисправностей такого вида будет определять полноту контроля всех разветвлений вычислительного процесса программы Следовательно, покрытие моделируемых неисправностей в условиях-предикатах будет являться не менее сильным критерием оценки качества тестовых наборов, чем покрытие ветвей ВП Критерий такого рода представляется достаточно сильным для использования в учебно-исследовательской САПР

Рис 3 Схема алгоритма прямого моделирования логических неисправностей

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

Л общ

где Ктт - коэффициент покрытия моделируемых неисправностей, ^чроч ~ число моделируемых неисправностей, проверяемых данным множеством тестовых наборов,

^общ - общее число моделируемых неисправностей

Схема алгоритма прямого моделирования логических неисправностей изображена на рис 3

В качестве простого примера рассмотрим ациклический вычислительный процесс, содержащий три условия-предиката (УП А, В, С) Входными данными для него будут коэффициенты квадратного уравнения (а Ь, с), а результатом работы -0 или 1 в зависимости от того, существуют ли у такого уравнения вещественные корни

Условия-предикаты УП А а = 0, УП В ¿ = 0, УП С Ьг - 4ас >= 0

[рт,при ЛВч~АС~ Выходная переменная г = < _ _ , (2)

[да, при АВ V АС

гдеда г = о и да г = 1

Построим исследуемый вычислительный процесс в виде графо-аналитической модели (рис 4)

Рис 4 Графо-аналитическая модель вычислительного процесса программы, определяющей наличие вещественных корней квадратного уравнения

Существуют две формулы вычисления г - РИЛ и РЯ2 Построим для двух соответствующих путей комплексное кубическое покрытие А'С(г') с, А В С г г' /(

А'С(г') =

1 1 X X \FR\\ /, = АВ

0 х 1 X \FR2\ /2 = АС

(3)

где А, В, С - условия-предикаты, значения координат кубов, равное "1", соответствует проходу УП по ветви Т, равное "О" - по ветви F и - отсутствию УП на рассматриваемом пути,

г - предыдущее значение выходной переменной,

г'- новое значение выходной переменной, вычисленное по формуле FR1 или по формуле FR2,

I, - путь через граф ВП

Далее, придадим конкретные значения переменным а, Ь, с и поведем моделирование неисправностей В итоге будет построен контрольный пример для теста Т(г')

Т(г') =

t, а b с г' г" г ~ *г 'г •г" „Л Т т **rm-rm1 1,

h 0 0 5 0 0 1 0 1 0 0 /, = АВ

h 1 4 0 1 1 1 1 1 1 0 1г = АС

(4)

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

Г Р

г А,. ,г < - результаты работы ВП с соответствующими неисправностями Итак, при использовании данных тестовых наборов получены оба возможных результата работы программы — 0 и 1 Однако из сравнения результатов работы ВП без неисправностей (г}) с результатами работы ВП с различными внесенными

неисправностями следует, что

г = г " и

следовательно,

неисправности mTÀ,mTB и m[ не проверяются данным тестом, К„.

N.,

N.

общ

05

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

Т(г') =

m I /и tttn tHt /я

г 'г г "г ' г

0 0 5 0 0 1 0 1 0 0 /, = АВ

h 1 4 0 1 1 1 1 1 1 0 l2 =ÂC

h 1 1 2 0 1 0 0 1 1 0 /, =ÂC

14 0 4 1 1 1 1 0 1 1 1 i4 = A В

(5)

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

V 6

г* проа ^ 1

максимально возможного значения л„„„ = —— = — = 1

ли, 6

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

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

Напомним принципы создания автоматизированной системы, предназначенной для проверки эффективности тестирования такого рода программ

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

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

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

Критерий покрытия моделируемых неисправностей не менее сильный, чем критерий покрытия ветвей на уровне машинного кода Подобное качество критерия представляется достаточным для того, чтобы использовать данный критерий при тестировании учебно-исследовательских программ Время работы системы будет небольшим для программ, содержащих относительно малое число условных переходов, а именно такими в своем абсолютном большинстве и являются учебно-исследовательские программы Действительно, время работы системы (1СШ) определяется прежде всего временем работы ВП (//;„) и количеством моделируемых неисправностей, которое в свою очередь равно удвоенному количеству команд условного перехода (Ы1р,тр) в программе, порождающий тестируемый ВП

'( ИМ К ^ЕП^фмтр (6)

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

3) Общий алгоритм работы системы должен быть относительно легко реализуемым и при этом эффективным

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

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

В третьей главе диссертации рассматривается проблема моделирования логических неисправностей в циклах

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

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

Метод имитации опасных неисправностей состоит в следующем Вместо замены fflump, которая является прерывающей для данного цикла, на команду безусловного перехода, нужно будет вставить в машинный код программы, порождающей тестируемый ВП, другую команду Jump, сразу вслед за рассматриваемой lflump Эта команда безусловного перехода будет содержать адрес нового фрагмента, добавляемого в исполняемый файл программы

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

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

Рис 5 Исходный цикл (слева) и цикл с имитируемой неисправностью т'„ (справа)

Рис 6 Схема алгоритма выбора метода моделирования

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

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

Таким образом, этот метод является универсальным, но и наиболее затратным по времени моделирования неисправностей

На рис 6 приведена схема алгоритма, с помощью которого следует производить выбор метода

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

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

При этом собственно системой моделирования неисправностей решаются следующие задачи

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

- поиск команд условного перехода, в которые будут вноситься неисправности,

- выбор методов моделирования,

- внесение неисправностей,

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

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

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

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

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

- исправление программы, порождающей исходный вычислительный процесс,

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

Рис 7 Схема алгоритма управления входными последовательностями в процессе

тестирования

Заключение

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

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

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

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

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

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

- разработан алгоритм выбора метода моделирования конкретной неисправности

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

Публикации по теме работы

1 Петров К В , Немолочнов О Ф , Зыков А Г , Поляков В И , Кулагин В С Логические неисправности вычислительных процессов программ // Труды 9-й научно-технической конференции Теория и технология программирования и защиты информации Применение вычислительной техники - СПб СПбГУ ИТМО, 2005 С 2-3

2 Петров К В Метод верификации подпрограмм, написанных на языке высокого уровня // Вестник II межвузовской конференции молодых ученых Сборник научных трудов /Подред В Л Ткалич Том 1 - СПб СПбГУ ИТМО, 2005 С 41-45

3 Петров К В Моделирование логических неисправностей в циклах вычислительных процессов программ // Научно-технический вестник СПбГУ ИТМО Выпуск 25 Исследования в области информационных технологий / Гл ред ВН Васильев-СПб СПбГУ ИТМО, 2006 С 221-227

4 Петров К В , Немолочнов О Ф , Зыков А Г , Поляков В И Моделирование простых логических неисправностей вычислительных процессов программ // Научно-технический вестник СПбГУ ИТМО Выпуск 32 Информационные технологии Теория, методы, приложения / Гл ред В Н Васильев - СПб СПбГУ ИТМО, 2006 С 113-118

5 Петров К В , Немолочнов О Ф , Зыков А Г, Поляков В И Учебно-исследовательская САПР верификации и тестирования вычислительных процессов программ // Научно-технический вестник СПбГУ ИТМО Выпуск 32 Информационные технологии Теория, методы, приложения / Гл ред В Н Васильев-СПб СПбГУ ИТМО, 2006 С 127-128

Тиражирование и брошюровка выполнены в учреждении

«Университетские телекоммуникации»

197101, Санкт-Петербург, Саблинская ул, 14

Тел (812) 233 4669 Объем 1 у п л

Тираж 100 экз

Список используемых сокращений и обозначении

Введение.

Глава 1. Современные методы оценки качества тестирования.

1.1 Вст)иление.

1.2 Анали* покрьпия кода.

1.2.1 Определение АПК.

1 2.2 Исходные посылки АПК.

1.2.3 Вазовые критерии покрытия

1.2.4 Прочие критерии.

1.2.5 Сравнение покашелей.

1 3 Мугационное тестирование.

1.3.1 Описание метода МТ.

1.3.2 Затраты на мутационное тестирование.

1.3.3 Генерация тестовых данных, основанная на ограничениях.

1.3.4 Улучшения в технологии М Г.

1.3.5 Новый процесс МГ.

Актуальность проблема тки диссертационной работы

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

Сфуктурное тестирование программного продукта может быть сведено к тестированию вычислительного процесса (ВП), порождаемого программой при интерпретации её команд вычислительной машиной [3]. Вычислительный процесс задае1ся в виде фафо-аналитической модели (ГАМ); под ГАМ при этом понимается описание вычислительного процесса в виде вершин, содержащих аналитические формулы, и дуг, образующих связи между вершинами [4, 5].

Во время тестирования ВП следует каким-либо образом оценить контролирующие свойства используемых входных наборов, т. е. провести анализ качества тестов. Одним из решений данной задачи является создание автоматизированной системы, проверяющей эффективность тестирования ВП. Такою рода система была разработана в рамках данной диссертации. Эта система является составной частью учебно-исследовательской системы авюматизированною проектирования (САПР), используемой для автоматизации тестирования и верификации вычислительных процессов [6].

Для оценки качества структурного тестирования были в свое время предложены разнообразные критерии покрытия тестируемого кода, в частности, покрытия операторов, ветвей, путей и т. д. Позднее был предложен меюд мутационного тестирования, который, однако, в широком смысле также является подвидом анализа покрытия кода [7, 8].

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

Текст программы, порождающей тестируемый ВП, анализируется на уровне исходного языка высокою уровня (ЯВУ); для сбора нужной статистической информации необходима перекомпиляция, во время которой в программу вносится некоторая дополнительная информация - например, флаги, с помощью которых потом можно было бы восс1ановить путь исполнения. Следовательно, такие системы проверки качества тестирования должны тесно взаимодействовать с компиляторами для всех возможных ЯВУ, на которых пишутся программы, порождающие тестируемые ВП [9].

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

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

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

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

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

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

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

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

2) Разработка методов анализа и модификации машинного кода, позволяющих применять новый кршерий качества тесювых наборов и достигать при этом максимальной производительности рабош автоматизированной системы, оценивающей эффективное п> тестирования вычислительных процессов;

3) Создание на основе разработанных методов автомашзированной системы, позволяющей оценивать и повышать эффективность тестирования; данная система будет являться подсистемой учебно-исследовательской САПР верификации и тестирования вычислительных процессов.

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

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

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

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

1) Предложен новый критерий оценки качества тестовых наборов -критерий покрытия простых логических неисправностей в условиях-предикатах вычислительных процессов.

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

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

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

Практическое значение работы состоит в следующем.

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

2) Реализована и внедрена в учебный процесс автоматизированная система моделирования неисправностей, являющаяся подсистемой учебно-исследовательской САПР и призванная реша1ь ряд задач при проведении тестирования ВП. Полезность данной системы определяется возможностью сопоставления моделируемых неисправностей и используемых 1есювых входных наборов; такое сопоставление позволяет, в частное ж, выполняп, следующее:

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

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

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

Кра1Кое содержание работы по главам

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

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

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

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

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

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

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

Результаты работы исходного В11 будут выведены в следующем виде. Эталонные результаты:

Т1 -15

Т2 -1

ТЗ О Т4

Т5 -4

Тб 3

Для всех шести тестовых наборов получены правильные результаты. Теперь необходимо провести моделирование неисправностей. Для этою следует ответить «Да» на вопрос

ПРОДОЛЖАТЬ РАБОТУ? Д-Да, Н-Нет т. е. нажать «Д».

После моделирования неисправностей будут выведены следующие результаты.

Команды ¡Яитр и неисправности:

0040102Е ,1ЬЕ Вне тТ Прямое мод. Кол-во наборов = 1(6) тЕ Прямое мод. Кол-во наборов = 3(6)

00401038 ЗЕ Вне тТ Прямое мод. Кол-во наборов = 1(6) шЕ Прямое мод. Кол-во наборов = 1(6) 00401061 ^Е Вне тТ Прямое мод. Кол-во наборов = 2(6) шЕ Прямое мод. Кол-во наборов = 1(6)

004 010 6А Л, Вне шТ Прямое мод. Кол-во наборов = 2(6) шЕ Прямое мод. Кол-во наборов = 1(6)

00401073 аЫЕ Вне шТ Прямое мод. Кол-во наборов = 1(6) шЕ Прямое мод. Кол-во наборов = 1(6)

КПМН =1.0

ТПН:

T1 l.mT, 2.mT

Т2 З.шТ, 4.mT, 5.mF

ТЗ l.mF

Т4 l.mF, З.гпТ, 4.mT, 5.тТ

Т5 2.mF, 3.mF

Т6 l.mF, 4.mF

4.6 Системные требования и время работы

Автоматизированная система MIIJ1H реализована в виде консольного приложения Windows, и требования к производительности персонального компьютера, на который должна быть установлена автоматизированная система, не являются высокими. Однако следует помнить, что при относительно большом количестве моделируемых неисправностей и/или относительно длительном времени работы тестируемого BII в тестируемых ВП предпочтительнее, разумеется, использование высокопроизводительного компьютера.

Минимальные системные требования:

- процессор Intel PII 233 МГц;

- оперативная память 32 Мб;

- операционная система Windows 98.

Согласно формуле (2.36), время работы автоматизированной системы МПЛН можно оценить следующим образом: tcm ^2tmNlßumpNT. Для большей точности следует добавить еще время на тестирование исходною 13П без неисправностей; в итоге получаем следующее. с\ш Ä hu (2Nlßumr + \)NT (4.3)

Для примера приведем временные параметры работы системы на персональном компьютере с частотой процессора 900 МГц (ВП содержит цикл Ц1 и в общей сложности 6 условий-предикатов). я„ *0.09с, i/Jump =

10, (4>4)

2^ + 1)^=11,70 6-,

Ш= 13,83 с

Понятно, что в тех случаях, когда приходится использовать метод отладки для борьбы с возникшими бесконечными циклами, на время работы системы будет влиять уже значение таймаут (см. 3.1.6). Запретим использовать метод имитации опасных неисправностей в предыдущем примере и выберем в качестве таймаута tu = 1 с. = 0,09 с, — 1 с,

N =6

Ритр и»

Л^=10, (4-5) ш^фитр^т 20,80 с, щ ~ 23,95 с

Заключение

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

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

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

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

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

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

-разработан алгоритм выбора метода моделирования конкрепюй неисправности.

4) На основе предложенных методов моделирования неисправностей была разработана автоматизированная система, позволяющая оценивать и повышать эффективность тестирования; данная система является подсистемой учебно-исследовательской САПР верификации и тестирования вычислительных процессов.

Основные положения диссертационной работы докладывались на XXXIV научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2005); II конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2005); XXXV научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2006); III конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2006).

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

Автоматизированная система моделирования простых ло1ических неисправностей, разработанная в рамках диссертации, используется на практике в учебном процессе кафедры Информатики и Прикладной Математики СПбГУ ИТМО, а также в ФГУП «Санкт-Петербургское ОКБ «Электроавтоматика».

1. Канер С., Фолк Дж., Нгуен Енг. Тестирование программною обеспечения. К.: ДиаСофт, 2000. - 544с.

2. Липаев В.В. Обеспечение качества программных средств. Методы и сгандарты. М.: Синтег, 2001. - 380с.

3. Немолочнов О.Ф., Зыков А.Г., Лаздин A.B., Поляков В.И. Верификация в исследовательских, учебных и промышленных системах. // Научно-технический вестник. СПб.: СПбГИТМО(ТУ), 2003.

4. Графы и алгоритмы. Структуры данных. Модели вычислений: Учебник / В.Б. Алексеев, В.А. Таланов. М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2006. - 320с.

5. Goodenough J.В., Gerhart S.L. Toward a Theory of Test Data Selection // IEEE Transactions on Software Engineering, 1975, SE 1, №2, p. 156-193

6. Ntafos S.C. A Comparition of Some Structural Testing Strategies // IEEE 1 ransaction on Software Engineering. 1988. - Vol. SE - 14, №6. pp 868-874

7. Beizer В. Software Testing Techniques ITP, 1990. - 550 pp.

8. Zhu H., Hall P.A.V., May J.H.R. Software unit test coverage and adequacy. ACM Computing Survey, pp. 366-427, 1997.

9. Липаев В.В. Тестирование программ. М.: Радио и связь, 1986.296с.

10. Макгрегор Дж., Сайке Д. Тестирование объектно-ориентированного программного обеспечения. К.: Диасофг, 2002. - 432с.

11. Майерс Г. Искусство тестирования программ. М.: Финансы и статистика, 1982.- 176с.

12. Hunt A., Thomas D. The Pragmatic Programmer. Addison-Wesley, 1999

13. Li, Y.Y. Structural test cases analysis and implementation. 42nd Midwest Symposium on Circuits and Systems, 8-11 August, 1999, Volume 2, pp. 882-885.

14. Morell L. A Theoiy of Fault-Based Testing. // IEEE Trans. Software Eng., Vol.16, No.8, August 1990, pp.844-857.

15. Ammann P., Black P. A specification-based coverage metric to evaluate test sets. In Proceedings of the 4th IEEE International Symposium on I Iigh Assurance Systems and Engineering, 1999.

16. Основы тестирования программною обеспечения: Учебное пособие / В.П. Котляров, Т.В. Коликова. М.: Интернет-Универсшет Информационных 1ехноло1 ий; БИНОМ. Лабораюрия знаний, 2006. - 265с.

17. Pressman, R.S. Software engineering: A practitioner's approach. McGraw-Hill, NY, 1996.

18. Винниченко И.В. Автоматизация процессов тестирования СПб.: Питер, 2005. - 203с.

19. Perry W. Effective methods for software testing. John Wiley & Sons, NY, 1995.

20. Roper M. Software Testing. London, McGraw-Hill Book Company, 1994

21. McCabe T.J., Schulmeyer G.G. System Testing Aided by Structured Analysis (A Practical Experience) // COMPSAC'82. Proc. IEEE Comput. Soc. 6th1.ternational Computer Software and Appl. Conference (Chicago, 111, Nov. 8-12, 1982).-pp. 523 -528

22. Chilenski J.J., Miller S.P. Applicability of Modified Condition/Decision Coverage to Software Testing. Software Engineering Journal, September 1994, Vol. 9, No. 5, pp. 193-200.

23. Hayhurst K.J., Veerhusen D.S., Chilenski J. J., Rierson L.K. A Practical Tutorial on Modified Condition/Decision Coverage, Report NASA/TM-200I-210876, NASA, USA, May 2001.

24. Борзов Ю.В., Уртанс Г.Б., Шимаров B.A. Выбор путей программы для построения тестов // УСиМ. 1989. - N. 6 - с.29-36

25. Woodward M.R., Hedley D., Hennell M.A. Experience with Path Analysis and Testing of Programs // IEEE Transactions on Software Engineering, Vol. SE-6, No. 3, pp. 278-286, May 1980.

26. Константайн JI., Локвуд JI. Разработка программного обеспечения. -СПб.: Питер, 2004. 592с.

27. Брукс Ф. Мифический человеко-месяц или как создаю 1ся программные системы. СПб.: Символ-Плюс, 1999. - 304с.

28. Boehm В. Software Engineering Economic/ Prentice-Hall, Inc, N. J. 1981.- 767 pp.

29. Marick B. How to Misuse Code Coverage. International Conference and Exposition on Testing Computer Software, June 1999.

30. Shimarov V.A. Definition and quantitative estimation of testing criteria // Software Quality Concern for people. Proceedings of the Fourth European Conference on Software Quality. October 17-20, 1994, Basel, Switzerland. Pp 350-360

31. Offutt J., Practical Mutation Testing. // Twelfth International Conference on Testing Computer Software, pages 99-109, Washington, DC, June 1995

32. Offutt J., Lee A., Rothermel G., Untch R., Zapf Ch. An Experimental Determination of Sufficient Mutant Operators. // ACM Transactions on Software Engineering Methodology, 5(2):99-l 18, April 1996.

33. King K.N. A Fortran Language System for Mutation-Based Software Testing. Software Practice and Experience, 21(7):686-718, July 1991.

34. Offutt J. Investigations of the Software Testing Coupling Effect. // ACM Transactions on Software Engineering Methodology, 1(1):3-18, January 1992

35. Budd T.A. Mutation Analysis of Program Test Data. PhD thesis, Yale University, New Haven CT, 1990.

36. DeMillo R., Offutt J. Constraint-Based Automatic Test Data Generation. // IEEE Transactions on Software Engineering, 17(9):900-910, September 1991.

37. Andrews J.H., Briand L.C., Labiche Y. Is Mutation an Appropriate Tool for Testing Experiments? // Proc. IEEE International Conference on Software Engineering, St. Louis, Missouri, pp.402-411, 2005.

38. Howden W.E. Weak mutation testing and completeness of test sets. // IEEE Transactions on Software Engineering, 8(4):371-379, July 1982.

39. Offutt J., Lee S.D. An Empirical Evaluation of Weak Mutation. // IEEE Transactions on Software Engineering, 20(5):337-344, May 1994

40. Untch R., Harrold M.J., Offutt J. Mutation Analysis Using Program Schemata. 1993 International Symposium on Software Testing and Analysis, pages 139-148, Cambridge, Massachusetts, June 1993.

41. Untch R. Mutation-based software testing using program schemata. In Proceedings of the 30th ACM Southeast Regional Conference, Raleigh, NC, April 1992.

42. Offutt J., Rothermel G., Zapf. Ch. An Experimental Evaluation of Selective Mutation. // Fifteenth International Conference on Software Engineering, pages 100-107, Baltimore, Maryland, May 1993.

43. Offutt J., Pan J. Automatically Detecting Equivalent Mutants and Infeasible Paths. The Journal of Software Testing, Verification, and Reliability, Vol 7, No. 3, pages 165-192, September 1997.

44. Wong W.E. Mutation Testing in the New Century, Kluwer Academic Publishers, ISBN 0-7923-7323-5, 2001.

45. Offutt A.J., Untch R.H. Mutation 2000: Uniting the Orthogonal. Proc. Mutation, San Jose, CA, USA, pp. 45-55, October, 2000.

46. Kim S., Clark J.A., McDermid J.A. Investigating the Effectiveness of Object-Oriented Testing Strategies with the Mutation Method. Software Testing, Verification and Reliability, vol. 11 (3), pp. 207-225, 2001.

47. Итерационно-рекурсивная модель вычислительных процессов, порождаемых программами / Немолочнов О.Ф., Зыков А.Г., Поляков В.И., Сидоров А.В., Осовецкий Л.Г. // Изв. ВУЗов. Приборостроение. 2005. Т 48, №12, С. 14-20

48. Немолочнов О.Ф. Методы технической диагностики / Методическое пособие.-Л.: ЛИТМО, 1977.

49. Проектирование цифровых вычислительных машин / С.А. Майоров, Г.И. 11овиков, О.Ф. Немолочнов и др. / Под ред. Майорова С.А. М.: Высш. шк., 1972.-344 с.

50. Норенков И.П. Основы автоматизированного проектирования: Учеб. Для вузов. 2-е изд., перераб. и дои. М.: Изд-во МГ'ГУ им. Н.Э. Баумана, 2002. -336 с.

51. Карибский В.В., Пархоменко П.П., Согомонян Е.С., Халчев В.Ф. / Основы технической диагностики. Кн.1.- М.: Энергия, 1976

52. Armstrong D.B. On Finding a Nearly Minimal Set of Fault Detecting Tests for Combinational logic Nets, IEEE Trans., EC-15, 1966.

53. Roth I.P. Diagnosis of Automata Failures: A Calculus and A Method. IBM Journal of Res. And Dev., 10, 1966.

54. Графы и их применение. Комбинаторные алгоритмы для программистов: Учебное пособие / Н.И. Костюкова. М.: Интернет-Универсиге1 Информационных технологий; БИНОМ. Лаборатория знаний, 2007.-311 с.

55. Offutt J., Craft М. Using Compiler Optimization Techniques to Detect Equivalent Mutants. The Journal of Software Testing, Verification, and Reliability, 4(3): 131-154, September 1994

56. Керниган Б., Ричи Д. Язык Си. М.: Финансы и статистика, 1990.

57. Harrold M.J. Using data flow analysis for testing. Technical Report 93112, Department of Computer Science, Clemson University, 1993.

58. I Iecht M.S. Flow Analysis of Computer Programs. Elsevier, Amsterdam,1977.

59. Herman P.M. A Data Flow Analysis Approach to Program Testing // Australian Computer Journal. 1976. - Vol. 8, № 3. pp. 92-96

60. Kennedy K.W. A survey of data flow analysis techniques. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 1, pp 5-54. Prentice-Hall, 1981.

61. Бейбер P. Программное обеспечение без ошибок. M.: Радио и связь, 1996.

62. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.

63. Фролов А.В., Фролов Г. В. Microsoft Visual С++ и MFC. Программирование для Windows 95 и Windows NT. M.: ДИАЛОГ-МИФИ, 1996.-288 с.

64. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976. - 736 с.

65. Петров К.В. Метод верификации подпрограмм, написанных на языке высокою уровня. // Вестник II межвузовской конференции молодых ученых. Сборник научных трудов. / Под ред. B.J1. Ткалич. Том 1,- СПб.: СПбГУ ИТМО, 2005. С. 41-45