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

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

РГВ од

* ^ ДЕК ¿кз

ГОРДИЕНКО Александр Владимирович

УДК 519.681.3

МАТЕМАТИЧЕСКИЕ МОДЕЛИ НАДЕЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ФУНКЦИОНАЛЬНОГО ТИПА

Специальность 05.13.16 — Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (технические науки)

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

Новочеркасск — 2000г.

Работа выполнена в Южно-Российском государственном техническом университете (Новочеркасский политехнический институт).

Научный руководитель — кандидат технических наук, доцент

A.Н.Иванченко

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

Г.ШХазанович — кандидат технических наук, доцент

B.Н.Землянухин

Ведущая организация — Южно-Российский региональный центр ш форматизации высшей школы «ЮГИНФО» Ростовского государственного уш верситета (г. Ростов-на-Дону)

Защита состоится 2000г. в часов на заседании диссерт;

ционного совета Д.063.30.04 в Южно-Российском государственном технич« ском университете.

346400, г.Новочеркасск, Ростовской области, ГСП-1, ул.Просвещения,

132.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан «£.» 2000г.

Ученый секретарь диссертационного совета канд. техн. наук, доцент Иванченко А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. В связи с широким применением вычислительной ехники важное значение приобрели проблемы качества программного обеспе-ения (ПО). Одной из основных составляющих качества ПО является его на-ежность, которая изучается специальной научной дисциплиной — теорией на-ежности программного обеспечения.

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

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

К ПФТ относятся программы (комплексы программ), которые можно оха-зктеризовать следующим образом:

1) процесс функционирования ПФТ может быть представлен статическим

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

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

3) ПФТ не содержит каких-либо автоматических средств динамическс коррекции невыявленных на этапе отладки ошибок в программах;

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

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

Различные аспекты программного обеспечения функционального ти исследовались в целом ряде диссертаций (Брябрин В.М., Демин А.Ю., Ж Ю.Е. и др.), в монографиях Борисова Ю.А., Горбунова-Посадова М.М., Матр сова М.М. и др. Теоретическим и практическим проблемам тестирования пр цедурного ПФТ посвящены диссертации Борзова Ю.В., Саркисяна A.A., Ш марова В.А. и др., монографии докторов технических наук Юсупова P.M., Г лонникова Р.И., Карповского Е.Я. и др. Проблемы тестирования объект! ориентированного ПФТ исследовались в диссертации Пинаева В.В.

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

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

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

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

Основные положения, выносимые на защиту:

е математическая модель структурного тестирования программ функционального типа;

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

• имитационная модель для экспериментальной оценки эффективности структурно-ориентированного критерия тестирования программ функционального типа;

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

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

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

па, является ЫР-полной по классу алгоритмической сложности;

• доказательство, что вероятностное тестирование ПФТ выполняется 1 наиболее тяжелом (в среднем) режиме в случае униформного операционной профиля программы;

• модификация известной математической модели ("модели Нельсона" для количественного расчета эффективности структурного тестирования ПФ' в контролируемых условиях; 4

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

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

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

• научно обоснованно оценивать достигнутый уровень тестированное! для оценки показателей безотказности ПФТ;

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

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

Достоверность результатов. Достоверность полученных результат ( подтверждается:

• материалами опубликованных отчетов о статистических и экспер ментальных исследованиях в области надежности и тестирования ПО, прон денных в нашей стране и за рубежом;

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

матическои техники и идей;

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

Внутреннее единство диссертации и круг рассмотренных в днссерта-ни вопросов. Представленная диссертация представляет собой работу, по-вященную решению одной крупной, замкнутой научной проблемы, вынесен-ой в заглавие диссертации. Все рассмотренные в диссертации задачи являются рганичными, естественно присущими составными частями этой большой и ножной проблемы. Ввиду сложности и многогранности исследуемой научной роблемы не все ее аспекты анализируются и исследуются в настоящей диссер-зции. Так, не рассматриваются вопросы корректности спецификаций ПФТ, по-фоения операционных профилей программ, проблемы, связанные с взаимо-ействием тестируемой ПФТ с окружающей программной средой и аппарат-ыми средствами вычислительной техники, вопросы борьбы с сознательными юнамеренными искажениями программ («компьютерные вирусы» и т.п.), про-чемы автоматической коррекции отказов и нарушений нормального функцио-ирования непосредственно во время работы ПФТ (fault-tolerance), проблемы уяснения правильности результатов отработки программы в процессе ее тес-фования («программные оракулы» и т.п.), некоторые другие вопросы. Объяс-яется это тем, что все перечисленные вопросы были предметом специального ^смотрения в ранее защищенных диссертациях в нашей стране и за рубежом, ээтому в приложении приведен список соответствующих диссертационных 160т, а в настоящей диссертации изложены материалы исследований только ;х вопросов по теме диссертации, которые до опубликования соответствую-;их работ автора еще не рассматривались в доступной автору научной литера-фе.

Реализация результатов работы. Разработанные в диссертации методы научные положения внедрены в РАО «ЕЭС России» (г.Москва); в ЮРГТУ ГПИ); на одном из крупных промышленных предприятий РФ. В Государст-

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

Апробация работы. Основные результаты работы и ее отдельные разде лы докладывались и обсуждались на Всесоюзной конференции «Программно! обеспечение АСУ» (г.Калинин, 1980г.); на Всесоюзной конференции «Синтез тестирование, верификация и отладка программ» (г.Рига, 1981г.); на Всесоюз ной конференции «Проблемы развития и использования ЭВМ общего назначе ния» (г.Минск, 1984г.); на семинарах научного совета АН УССР по проблем «Кибернетика» (г.Киев, ин-т кибернетики им. В.М.Глушкова, 1981г., ин-т автс матики, 1983г.); на Международной научно-технической конференции «Изме рения, контроль, информатизация» (г.Барнаул, 2000г.); на 2-ой Международно научно-технической конференции «Информационные технологии в моделирс вании и управлении» (Санкт-Петербург, 2000г.); на ежегодных научнс технических конференциях ЮРГТУ в период 1980 -1999 гг.

Публикации. Основные материалы диссертации отражены в 1 печатных работах.

Структура и объем работы. Диссертация содержит 162 страницы oi новного текста, 5 рисунков, 9 таблиц и состоит из введения, четырех глав, з; ключения, списка использованной литературы и приложения. Список литераг ры содержит 80 наименований. В приложение (в электронном виде на дискете 1/4") вынесен библиографический указатель, который включает свыше трех ti сяч наименований научных работ по проблематике диссертации (в основном f русском языке) и снабжен подробным иерархическим предметным указателе: содержащим более 250 рубрик, отдельно выделен тематический список отеч ственных диссертаций по надежности ПО и смежным вопросам (106 диссерт ций). Представляется, что данный библиографический указатель достаточ] полно отражает научные публикации на русском языке по тематике диссерт

ГТГ.т "ЭО rtnr- TIOTTUTJC* Пот Т.* U ГЧХПТТ П Г1Т1Т** Tlnfofvr рол fr\PTr\aVi»TTI. гюицлгтт тт

Ц1111 iiVV.lVrt'l'fV VJ .iwi .4 U VUflJJl W Jlllnt ilk.lbu 1 Wi'l VV1VU1 llJ LWLLIIWIU Д'

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

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

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

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

ЛМголной для любого критерия тестирования программ функционального ти-

I

[а, начиная с критерия СО (вершинное покрытие путями управляющего графа).

Для количественной характеристики уровня отлаженное™ программного |беспечения функционального типа вводятся следующие показатели: г, — юказатель тестированное™ ¿-й программы; г., — показатель тестированное™ 1ФТ в целом (специалисты по надежности ПО обычно интерпретируют вели-шну д = 1 - г как вероятность отказа программы при однократной отработке в лучае, когда на вход программы подано входное значение, выбранное случайном образом из множества допустимых входных значений по заданному опе-)ационному профилю); А'но — приведенная средняя наработка ПФТ до отка-а; Тп0 — средняя наработка ПФТ до отказа; г(Ы) — приведенная функция тдежности ПФТ; Л(г) — функция надежности ПФТ.

Пусть ПФТ состоит из п программ. Обозначим: Тр— среднее время от-)аботки одного рабочего цикла ПФТ "вход—выход"; f¡ — частота ннициалкза-вди г-й программы в расчете на один рабочий цикл ПФТ. Тогда задача оценки юказателей тестированное™ систем программного обеспечения функциональ-юго типа формулируется следующим образом в виде прямой и обратной задач в соответствии с традициями, сложившимися в научной литературе по теории мдежности):

Прямая задача: изгестиы (определены ранее) величины Тр, /, г. ц, ; = 1 ,п) составляющих ПФТ программных модулей, требуется оценить интегральные показатели тестированное™ ПФТ в целом.

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

Решение поставленной задачи дается во второй и третьей главах диссертации.

Во второй главе рассматриваются вопросы тестирования отдельных про грамм (программных модулей) функционального типа.

Обозначим: X, — множество всех допустимых входных значений про граммы А, : X] — совокупность тех х еЛГ, , на которых А, отрабатывает не верно; р,(х) — ряд распределения вероятностей, по которому элементы а- еХ подаются на вход программы А, («операционный профиль программы»); че рез \Х\ обозначается число элементов множества X.

По определению,

<?, = !/>,« (1

В частности, если р,{х) = рр(х) , где рр(х) —униформное распределени вероятностей на X, , то ^ =|А',"]/|А',| .

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

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

ти, исследованию этой проблемы посвящена диссертация D.Woit "Operational 'rofile Specification, Test Case Generation, and Reliability Estimation for Modules", 'h.D. Thesis, Queen's University, Kinston, Ontario, Canada, 1994). Во второй гла-1Ы настоящей диссертации теоретически обосновано, что по следующим принтам целесообразно осуществлять тестирование произвольной программы функционального типа с целью получения численной верхней границы на ветчину q, на униформном операционном профиле:

1) Режим тестирования ПФТ при униформном операционном профиле шляется в среднем наиболее тяжелым по сравнению с режимом тестирования 1ФТ на любом другом операционном профиле р,(х) ф рр(х). Это основывается на доказанной теореме: в соответствии с принятой в теории надежности интерпретацией величин qt усредненное значение средней наработки прмраммы до отказа по всем равномощным множествам X", минимально, когда Р,(х) = рр(х). Отсюда следует, что рассчитав величину Л'но для рр(х) по достаточно большой совокупности программ Ф, можно быть практически уверенным, что в любой области применения программы действительные значения .VH0 окажутся в среднем (т.е. усредненные по всей генеральной совокупности Ф) не хуже вычисленных априорных значений.

2) По известному значению gj эффективно вычисляется верхняя граница для оценки qi при любом заданном операционном профиле рАх) :

д,<Мв\Х,\д1 , (2)

где м0 =тахр,{х). В случае, если вычисленное по формуле (2) значение q,

хеХ,

получается значительно больше q,, то это означает, что при законе распределения вероятностей сравнительно небольшое множество элементов.!', имеют намного большие вероятности выбора, чем все остальные элементы х еХ, \ X, вместе взятые. В таком случае следует протестировать программу на всех входных значениях х еХ, , а затем повторить расчет по формуле (2), где в качестве Мй берется уже MQ = max pf(x) . Указанная процедура ведет к достаточно быстрому снижению величины д, .

Структурное тестирование отличается от функционального тестирование тем, что при его проведении учитывается явным образом структура тестируемой программы. Разработанная математическая модель структурного тестирования представляет собой модификацию модели, впервые предложенной Нельсоном, одновременно исследован оригинальный критерий структурного тестирования программ (впервые предложен в диссертации Правилыцикова П.А.) \ построена его математическая модель. Указанный критерий тестирования за ключается в следующем. Пусть имеется программа А ; I — ее структурна) граф-схема по передаче управления. Назовем два пути и 52 в I несущест венно различающимися (НСРП), если они различаются лишь числом повторе ний некоторых циклов. Множество всех реализуемых путей в I разбиваете) на классы Р1, где = 1, V , такие, что каждому классу Р1 принадлежат все пути несущественно различающиеся между собой, и только они. Обозначим чере: В] совокупность операторов программы А, принадлежащих хотя бы одном; пути 5 из Р, . Будем говорить, что класс Р) программы А протестирован, ее ли программа отработала по любому пути 5 из такому, что 5 покрывае' все операторы из BJ. Доказано, что тогда при принятых допущениях для дос тижения заданной верхней границы на показатель д, программы А требуете:

протестировать программу и = £ и1 раз (каждый класс FJ тестируется и] раз

до тех пор, пока не будет выполняться неравенство:

1<9,, о

где — суммарная вероятность прохождения по путям из класса ; QJ« — некоторые константы (зависящие от конкретного состава В-), которые опре деляются ниже.

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

окращенное множество классов НСРП-путей. Пусть для Ак (к = Гт) мощ-юсть множества НСРП-путей равна \>к, тогда справедливо следующее соот-юшение: v < max{v,,v2,..., v„). Эта процедура приводит к эффективному меньшению количества необходимых тестов для больших программ.

Разработана имитационная модель для экспериментальной количествен-юй оценки эффективности структурно-ориентированного критерия тестированы ПФТ. В математической форме это формулируется следующим образом. 7усть путь на управляющем графе программы R реализует функцию v = f(x},x2,...,x„) . Вследствие внесения ошибок в программу путь R изменяет-;я и получившийся в результате измененный путь R* реализует уже некоторую фугую функцию у = f'(xvx2,...,xn). Трсбустся определить вероятность О. что три случайном выборе вектора х > будет выполняться равенство

/(х) = /"(*) (содержательно это означает, что при тестировании программы на гесте х ошибка в программе останется не выявленной при тестировании).

Для решения сформулированной задачи использовался метод имитационного моделирования. Концептуально построенная в диссертации имитационная модель является вариацией метода, известного в специальной литературе под названием «метод мутационного тестирования программ» (mutation testing), который детально исследовался в целом ряде диссертационных работ. При разработке соответствующей имитационной модели учитывались опубликованные результаты экспериментальных работ и исследований природы и характера программных ошибок и их проявлений в реальных программных комплексах, в частности установленный в многочисленных программных экспериментах факт, что интегральные вероятностные характеристики поведения тестируемой программы при статистическом тестировании не зависят от природы конкретных программных ошибок (так называемый "coupling cffcct", впервые установленный экспериментально в середине 70-х годов профессором R.Demillo с сотрудниками и с тех пор многократно подтвержденный). Уместно отметить, что метод мутационного тестирования, положенный в основу разработанной имитационной модели, не только имеет прочную эмпирическую базу, накопленную за более чем 20 лет после его

13

за более чем 20 лет после его открытия, но и в последние годы получил теоретическое подтверждение и объяснение в ряде математических работ, в частности, в диссертации Shahomian Т.А. «Some programs need only be checked foi correctness on random inputs», Ph.D. Thesis in Computer Science, Berkeley University, USA, 1998.

В результате всестороннего исследования построенной имитационной модели было установлено, что величина Q зависит главным образом от набора элементарных функциональных операций, входящих в состав R *. В частности, для широко распространенного случая, когда в качестве элементарных функциональных операций используются только четыре арифметических действия с целочисленными операндами по модулю 2>6 , получено значение О <КГ3, £ для модуля 2" Q<К)"4.

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

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

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

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

п

олучены верхние границы для функционалов от оценок: ЛЩ,) <]Г /,с/, ;

¡-л

п

, где через М(дй) и П(д0) обозначены соответственно среднее зна-;ение и дисперсия оценки д0 . Применяя неравенство Чебышева, получим сле-

( 1 " V'2

[уюшую верхнюю границу: ц0 < У/,«, + -, где В — доверительная

" м >

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

л

?0 <]Г/л, • Для проверки полученной оценки было проведено имитационное

к)

моделирование на ЭВМ, результаты которого дали удовлетворительное совпа-книс с результатами теоретического расчета (в пределах, не превышающих 15%).

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

, / = Т, и ;где Т'

— среднее машинное время одного тестового испытания ¡'-й программы; через

роятностью ¡5, получены формулы: со, =

аЧх-р) 1п(1-<?.,)

Га] обозначается потолок числа а. При этом т = ——— (V у1/Т') . Показа

п

но, что ошибка приближения в последней формуле не превосходит ]Г т' .

1=1

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

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

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

1. Проведено исследование алгоритмической сложности проблемы го строения покрывающего множества тестов по различным критериям структур ного тестирования ПФТ, доказано что эта проблема является ЫР-полной д.; любого структурного критерия, начиная с критерия СО.

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

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

твующие аналитические выражения.

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

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

ПУБЛИКАЦИИ, ОТРАЖАЮЩИЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Гордиенко A.B. Вероятностный подход к определению надежности программ // Технология создания программных средств АСУ. — Калинин, 1980. — С.154-157.

2. Гордиенко A.B. Генерирование исходной информации для тестирования программного обеспечения АСУ ТП // Системы управления технологическими процессами. — Новочеркасск: НПИ, 1981. — С.58-64.

3. Гордиенко A.B. Расчет надежности программного обеспечения АСУ// Системы и технические средства подготовки операторов. — Новочеркасск: НПИ, 1981. —С.73-78.

4. Гордиенко A.B. О сложности проблемы автоматизации генерирования исходных данных для тестирования программ /7 Кибернетика. — 1982. — № 1. — С.123-124.

5. Гордиенко A.B. К вопросу об эффективности критерия тестирования программ по путям // Управляющие системы и машины. — 1982. —№ 2. — С.107-109.

6. Гордиенко A.B. Тестирование при оценке динамической корректности программ АСУ // Программирование.— 1982. — №6. — С.48-52.

7. Гордиенко A.B. Распределение вероятностей отказов при работе программного обеспечения ЭВМ // Изв. СКНЦ ВШ. Серия технических наук. — 1983, —№ 1, —С.54-56.

8. Гордиенко A.B. Определение оптимального числа испытаний составляю-

щих программ при тестировании системы программного обеспечения // Проблемы развития и использования ЭВМ общего назначения. — Минск, 1984. — С.85-86.

9. Гордиенко A.B. О выборе входного распределения при функциональном тестировании программ // Изв. вузов. Электромеханика. — 1985. — № 4. — С.114-116.

10. Гордиенко A.B. Имитационная модель надежности системы программного обеспечения // Программные средства как продукция производственно-технического назначения. — Калинин, 1985. — С.44-45.

11. Гордиенко A.B. Ошибки в межпрограммном интерфейсе: данные статистических исследований // Новочерк. политех, ин.: Новочеркасск. — 1991. — 27с. — Деп. в ВИНИТИ 09.01.92. — № 89-В92

12. Гордиенко A.B. Оценка вероятности отказа системы программного обеспечения при известных вероятностях отказа составляющих программ // Новочерк. политех, ин.: Новочеркасск. — 1992. — 27с. / Деп. в ВИНИТИ 29.10.92, —№3135-В92

13. Иванченко А.Н., Гордиенко A.B. Оптимизация функционального тестирования программ по стоимостному критерию // Изв. вузов. СевероКавказский регион. Технические науки. — 1997. — № 3. — С.24-27. -

14. Гордиенко A.B. О влиянии функциональной неоднородности составляющих программ на общую корректность системы программного обеспечение // Техника. Экономика. Культура. Юбилейный сборник научных трудов профессорско-преподавательского состава НГТУ. Ростов/Д: Изд-во "Гефест", 1998. — С.213-215.

15. Иванченко А.Н., Гордиенко A.B. Структурный подход к расчету количественной оценки безотказности работы системы программного обеспечения /, Изв. вузов. Электромеханика. — 1999. — № 4. — С.101-108.

16. Иванченко А.Н., Гордиенко A.B. Инженерный расчет количественной оценки безотказности работы системы программного обеспечения. // Изв. вузов. Северо-Кавказский регион. Технические науки. — 2000. — № 2. — С.24-28.

17. Иванченко А.Н., Гордиенко A.B. Измерения и контроль показателей безотказности программного обеспечения функционального типа // Материалы международной научно-технической конференции ИКИ-2000. — Барнаул, 2000. —С. 175-177. .

ВВЕДЕНИЕ.

1. ДЕТЕРМИНИРОВАННЫЙ И ВЕРОЯТНОСТНЫЙ ПОДХОДЫ К ТЕСТИРОВАНИЮ ПРОГРАММ.

1.1. Теоретическая сложность проблемы детерминированного тестирования программ.

1.2. Вероятностный подход к тестированию программ.

Модели надежности программного обеспечения.

1.3. Основные определения и формальная постановка решаемой задачи.

1.4. В ы в о д ы.

2. ВЕРОЯТНОСТНОЕ ТЕСТИРОВАНИЕ ОТДЕЛЬНЫХ ПРОГРАММ.

2.1. Теоретическое исследование метода функционального тестирования программ:.

2.2. Разработка модифицированного метода структурного тестирования программ.

2.3. Экспериментальное исследование структурно-ориентированного критерия тестирования программ.

2.4. Генерация исходной информации для тестирования программ.

2.5. В ы в о д ы.

3. РАСЧЕТ БЕЗОТКАЗНОСТИ СИСТЕМЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ФУНКЦИОНАЛЬНОГО ТИПА (ПФТ).

3.1. Верхняя оценка вероятности отказа ПФТ.

3.2. Оценка вероятности отказа ПФТ с учетом ограничения на функциональную неоднородность составляющих программ.

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

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

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

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

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

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

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

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

1) процесс функционирования ПФТ может быть представлен ориентированным графом, в котором вершины соответствуют отдельным программам-модулям, а дуги - возможным передачам управления между программами;

2) ПФТ функционирует либо на однопроцессорной ЭВМ в последовательном режиме работы, либо на слабо связанной вычислительной системе;

3) ПФТ не содержит каких-либо автоматических средств данамической коррекции невыявленных ошибок в программах.

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

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

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

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

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

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

Выводы

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

Полученные результаты хорошо согласуются с близкими экспериментальными исследованиями структурной сложности различных реальных программ, выполненных другими исследователями Шеуикег-90; В1ешап-92].

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

В результате проведенного тестирования было выявлено дополнительно свыше 20 дефектов в программах. Указанная АСУТП была внедрена на предприятии п/я А-3611. За время промышленной эксплуатации не было обнаружено ни одного дефекта в ее системе программного обеспечения, что может свидетельствовать о эффективности модифицированного метода структурного тестирования программ для получения качественного программного обеспечения.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Результаты исследований использованы при проверке программного обеспечения автоматизированной системы управлет ния участком намоточных станков. Результаты исследований моплггп Ачппг. тахгм/о т^пгтп ггх.'зтэотзгт ттпт* тгпптга'птг'о тглл'П'патгалрп лЛаг> печения других систем.

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов / Пер. с англ. М.: Мир, 1979.

2. Бешелев С.Д. Математико-статистические методы экспертных оценок / 2-е изд., перераб. и дополн. М.: Статистика, 1980

3. Бичевский Я.Я., Борзов Ю.В. Тестирование программ ЭВМ / Рига: Латв.гос.ун-т, 1985.

4. Блау С.А., Липаев В.В., Позин Б.А. Эффективность тестирования структуры программных модулей // Автоматика и телемеханика, 1984, 4, с. 139-148.

5. Бондарь Я.С., Катков В.Л. Система автоматической генерации тестов // Программирование, 1995, $ 6, с.27-35.

6. Боэм Б.У. Инженерное проектирование программного обеспечения / Пер. англ. М.: Радио и связь, 1985.

7. Братчиков И.Л. Синтаксис языков программирования. -М.: Наука, 1975.

8. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969.

9. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука, 1988

10. Воеводин В.В., Ким Г.Д. Машинные операции с точки зрения математика // Сб. работ Вычисл. Центра МГУ. Вып.26. -М.: Мзд.МГУ, 1977, с.31-35.

11. Глушков В.М., Вельбицкий И.М. Технология программирования и методы ее автоматизации // Управляющие системы и машины, 1976, .№ 6.

12. Гордиенко A.B. Вероятностный подход к определению надежности программ // Технология создания программных средств АСУ. -Калинин, 1980, с.154-157.

13. Гордиенко A.B. Генерирование исходной информации для тестирования программного обеспечения АСУ ТП // Системы управления технологическими процессами. Новочеркасск, 1981, с.58-64.

14. Гордиенко A.B. Расчет надежности программного обеспечения АСУ // Системы и технические средства подготовки операторов. -Новочеркасск, 1981, с.73-78.

15. Гордиенко A.B. О сложности проблемы автоматизации генерирования исходных данных для тестирования программ // Кибернетика, 1982, Sb I, с. 123-124.

16. Гордиенко A.B. К вопросу об эффективности критерия тестирования программ по путям // Управляющие системы и машины, 1982, № 2, с.107-109.

17. Гордиенко A.B. Тестирование при оценке динамической корректности программ АСУ // Программирование, 1982, № 6, с.48-52.

18. Гордиенко A.B. Распределение вероятностей отказов при работе программного обеспечения ЭВМ // Изв. СКНЦ ВШ. Серия технических наук, 1983, J6 I, с.54-56.

19. Гордиенко A.B. Определение оптимального числа испытаний составляющих программ при тестировании системы программного обеспечения // Проблемы развития и использования ЭВМ общего назначения. Минск, 1984, с.85-86.

20. Гордиенко A.B. О выборе входного распределения при функциональном тестировании программ // Изв. вузов. Электромеханика, 1985, № 4, C.II4-II6.

21. Гордиенко A.B. Имитационная модель надежности системы программного обеспечения // Программные средства как продукция проиеводотввыно-технического назначения. Калинин, 1985, с.44-45.

22. Гордиенко A.B. Ошибки в межпрограммном интерфейсе: данные статистических исследований // Деп. ВИНИТИ 09.01.92 Jfc 89-В92

23. Гордиенко A.B. Оценка вероятности отказа системы программного обеспечения при известных вероятностях отказа составляющих программ // Деп. ВИНИТИ 29.10.92 Jfc 3I35-B92

24. Гордиенко A.B. О влиянии функциональной неоднородности составляющих программ на общую корректность системы программного обеспечения // Техника. Экономика. Культура. Ростов/Д, 1998, с.213-215.

25. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ. М.: Мир, 1982

26. Зайцев A.B. Применение мутационного анализа при тестировании программ. Севастопольский приборостроительный ин-т, 1987. - 21с. //Деп. в УкрНИИНТИ » 1442-Ук87 .

27. Зайцев A.B. Надежность тестирования программ // Программирование, 1989, .№ 6, с.20-25.

28. Иванченко А.Н., Гордиенко A.B. Оптимизация функционального тестирования программ по стоимостному критерию // Изв. вузов. Северо-Кавказский регион. Техн. науки, 1997, ^ 3, с.24-27.

29. Иванченко А.Н., Гордиенко A.B. Структурный подход к расчету количественной оценки безотказности работы системы программного обеспечения // Изв. вузов. Электромеханика, 1999, 4, с.101-108.

30. Иванченко А.Н., Гордиенко A.B. Инженерный расчет количественной оценки безотказности работы системы программного обеспечения // Изв. вузов. Северо-Кавказский регион. Техн. науки, 2000, Ш 2, с.24-28.

31. Карповский Е.Я., Сагач В.В., Черыецкий A.A. Надежность алгоритмов управления. Киев: ТехнХка, 1983.

32. Кауфман A.B., Черноножкин С.К. Критерии тестирования и система оценки полноты набора тестов // Программирование, 1998, Jfe 6, с.44-59

33. Ковалев М.Я., Шафранский Я.М. Построение s-приближенных алгоритмов решения некоторых NP-полных задач // Теория и методы автоматизированного проектирования сложных системен автоматизация научных исследований. Минск, 1985, с. 15-18.

34. Корчемный Д.М. Ошибки в Си-программах. М., 1989. 33с. Деп. в ИНФОРМЭлектро N ДР4744-пр89.

35. Котляров В.П., Пинаев Д.В. Методы и средства автоматизации тестирования программного проекта / Учеб.пос. СПб: СПбГТУ, 1998

36. Липаев В.В. Надежность программного обеспечения. М.: Энергоатомиздат, 1981.

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

38. Липаев В.В. Надежность программных средств. М.: СИНТЕГ, 1998

39. Лонгботтом Р. Надежность вычислительных систем. / Пер. с англ. М.: Знергоатомиздат, 1985.

40. Майерс Г. Искусство тестирования программ. / Пер. с англ. М.: Финансы и статистика, 1982.

41. Надежность математического обеспечения в истинном масштабе времени. / Пер. с англ. языка научного отчета. Всесоюзный центр переводов научно-техн. литературы и документации. Перевод № А-34867. -М., 1977.

42. Отладка систем управляющих алгоритмов ЦВМ реального времени. / Под ред. Липаева В.В. М.: Сов. радио, 1974.

43. Пальчун Б.П., Юсупов P.M. Оценка надежности программного обеспечения. СПб.: Наука, 1994.

44. Пепеляев А.Н., Липин Ю.Н., Левитин Ф.И. Контроль достоверности информации в АСУП. М.: ЦМНТИХММНЕФТЕМАШ, 1975.

45. Позин Б.А. Методы структурного построения тестов для отладки управляющих программ // Программирование, 1980, Jfc 2, с.62-69.

46. Правильщиков П.А., Щепин B.C. Составление структурных программ в диалоговом режиме с одновременной генерацией те'стов // Автоматика и телемеханика, 1979, Л 8, с.129-138.

47. Проверка и утверждение программ реального времени. / Пер. с англ. Киев: Наукова думка, 1990.

48. Taxa X. Введение в исследование операций. В 2 кн. / Пер. с англ. М.: Мир, 1985.

49. Тейер Т., Липов М., Нельсон Э. Надежность программного обеспечения. / Пер. с англ. М.: Мир, 1981.

50. Тоценко В.Г., Александров A.B., Парамонов Н.Б. Корректность, устойчивость, точность программного обеспечения. Киев: Наукова думка, 1990

51. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.В. Функции алгебры логики и классы Поста. М.: Наука, 1966.

52. Alanko T.O., Smelianski R.L. On the calculation of control transition probabilities in a program // Information Processing Letters, 1986, v.22, N 5, p.273-276.

53. Bassiohi F., Spadafora I. An automated generator for compiler testing // IEEE Transactions on Software Engineering, 1982, y.8, N 4, p.343-353.

54. Bieman J.M., Schultz J.L. An empirical evaluation (and specification) of the all-du-paths testing criterion // Software Engineering Journal, 1992, v.7, N 1, p.43-51.

55. Bishop P.G., Pullen P.D. PODS revisited: A study of software failure behavior // 18th Fault Tolerance in Computing Conf., 1988, p.2-8.

56. Clarke L.A. A system to generate test data and symbolically execute programs // IEEE Transactions on Software Engineering, 1976, v.2, N 3, p.215-222.

57. Cooper K.D., Hall M., Kennedy K., Torczon L. Inter-procudaral analysis and optimization // Communications on Pure and Applied Mathematics, 1995, Vol.XLVIII, p.947-1003.

58. Demillo R.A., Lipton R.J., Sayward P. Hints on test data selection: Help for the practicing programmer // Computer, 1978, v.11, N 4, p.34-41.

59. Dunham J.R. Experiments in software reliability: Life-critical applications // IEEE Transactions on Software Engineering, 1986, v.12, N 1, p.110-123.

60. Duran J.W., Wiorkowski J.J. Quantifying software validity by sampling // IEEE Transactions on Reliability, 1980, v.29, p.141-144.

61. Duran J.W., Ntafos S.G. An evaluation of random testing // IEEE Transactions on Software Engineering, 1984, v.10, N 4, p.438-444.

62. Goodenough J.B. A survey of program testing issues //

63. Software Reliability. Maidenhead, 1977, vol.2, p. 135-154.

64. Horgan J.R., London S., Lyu M.R. Achieving software quality with testing coverage measures // Computer, 1994, v.27, N 9, p.60-69.

65. Howden W. functional Program Testing and Analysis. -New York: McGraw-Hill, 1987.

66. Jones C. Software metrics: good, bad, and missing // Computer, 1994, v.27, N 9, p.98-100.

67. Knight J.C., Ammann P.E. An experimental evaluation of simple methods for seeding program errors // 8th Intern. Conference on Software Engineering, 1985, p.337-342.

68. Knight J.C., Leveson N.G. An experimental evaluation of the assumption of independance in multiversion software // Transactions on Software Engineering, 1986, N 1, p.96-109.

69. Marshall A.C., Hedley D., Riddell I.J., Hennell M.A. Static dataflow-aided weak mutation analysis // Information and Software Technology, 1990, v.32, N 1, p.99-104.

70. Ostrand T.J., Balcer M.J. The category-partition method for specifying and generating functional tests // Communications of the ACM, 1988, v.31, N 6, p.676-686.

71. Nelson E. Estimating software reliability from test data // Microelectronics and Reliability, 1978, v.17, p.67-74.

72. Ntafos S.C., Hakimi S.L. On path cover problem In digraphs and applications to program testing // IEEE Transactions on Software Engineering, 1979, v.5, N 5, p.520-529.

73. Piwowarski P.M., Ohba M., Caruso J. Coverage measurement experience during function test // 15th Intern. Gonf. on Software Engineering, 1993, p.287-301.m

74. Ramamoorthy C.V., Bastani F.B. Software reliability status and perspectives // IEEE Transactions on Software Engineering, 1982, y.8f p.354-371.

75. Roca J.L. Normal approach on correctness software estimation // Microelectronics and Reliability, 1987, v.27, N 4, p.457-458.

76. Roca J.L. Testing hypotheses on correctness software estimation // Microelectronics and Reliability, 1988, v.28, N 4, p.511-512.

77. Shapiro E.Y. Algorithmic Program Debugging. MIT Press, 1982.

78. Wang H.S., Hsu S.R., Lin J.C. A generalized optimal path-selection model for structural testing // Journal of Systems and Software, 1989, v.10, N 1, p.55-63.

79. Weyuker E.J. The cost of data flow testing: An empirical study // IEEE Transactions on Software Engineering, 1990, v. 16, N 2, p.121-128.

80. Wohlin G., Koerner U. Software faults: spreading, detection, and costs // Software Engineering Journal, 1990, v.5, N 1, p.33-42.