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

УДК 681.3.068

Н.В.Василенко, В.А.Макаров МОДЕЛИ ОЦЕНКИ НАДЕЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

14 of the most famous models of software safety evaluation are reviewed. According to the review, there is no absolutely safe programme, as the absolutely safety degree can't be theoretically proved and therefore it can not be achieved.

1. Введение

В международном стандарте ISO 9126:1991 [1] надежность выделена как одна из основных характеристик качества программного обеспечения (ПО). Стандартный словарь терминов программного инжиниринга [2] определяет надежность программного обеспечения как способность системы или компонента выполнять требуемые функции в заданных условиях на протяжении указанного периода времени.

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

Модели надежности программных средств подразделяются на аналитические и эмпирические [4]. Аналитические модели дают возможность рассчитать количественные показатели надежности, основываясь на данных о поведении программы в процессе тестирования. Эмпирические модели базируются на анализе структурных особенностей программ.

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

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

2. Аналитические динамические модели

2.1. Модель Шумана

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

программе постоянно и в процессе тестирования может уменьшаться по мере того, как ошибки выявляются и исправляются (новые ошибки не вносятся).

Базовые понятия модели заимствованы из теории надежности аппаратных средств [5]. R(t) — функция надежности — вероятность того, что ни одна ошибка не появится на интервале от 0 до t.

F(t) — функция отказов — вероятность того, что ошибка появится на интервале от 0 до t.

F

dF

дО — плотность вероятности для F(t), / ^) =---------------=---------.

dt dt

z(t) — функция риска — условная вероятность того, что ошибка появится на интервале от 0 до t + Д, при условии, что до t ошибок не было. Если Т — время появления ошибки, то

... , РС < Т < t + Д0 F

z(t)At = P{t < Т < t + Д'Т > Л = —----------------- = —-------------—.

Р

Поделив обе части на Дt и устремив Д к 0, переходим к пределу

^ /

z (/) =----=---------------.

R(t) R(t) dt

Решая это дифференциальное уравнение относительно R(t) при начальном условии R(0) = 1, получим

( t л

R(t) = ехр| -1 z(x)dx

V 0 )

ОТ

4р — среднее время между отказами, t ср = | R(t )dt.

^ср V!^ср

0

В рассматриваемой модели автор предполагает, что значение функции z(t) пропорционально числу ошибок, оставшихся в ПО после израсходованного на тестирование времени т: z(t) = С • ег(т), где С — некоторая константа; t — время работы ПО без отказа; е г (т) — удельное число ошибок на одну машинную команду, оставшихся в системе после

ЕТ

времени тестирования т: е г (т) =--е с (т), где ЕТ — число ошибок до начала тестирова-

1Т

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

R(t, т) = ехр

С •! е~ - е с(т) )•t

'ср = 7Е~^------Т.

С{ т;- е с

Из величин, входящих в формулы (1) и (2), неизвестны начальное значение ошибок в ПО (ЕТ) и коэффициент пропорциональности С. Для их определения прибегают к следующим рассуждениям. В процессе тестирования собирается информация о времени и количестве ошибок на каждом прогоне, т.е. общее время тестирования т складывается из времени каждого прогона. Полагая, что интенсивность появления ошибок постоянна и равна X, а Л, — количество ошибок на /-м прогоне, можно вычислить

'ср =-^- <3>

Имея данные для двух различных моментов тестирования та и тъ, которые выбираются произвольно с учетом требования ес(тъ) > ес(та), можно сопоставить уравнения (2) и (3) при та и тъ и получить следующие выражения:

Е = 1Т (Ч • ес (та ) - Хтъ • ес (тъ )) С = Ч

ET t \

а 4 — — ес

1т

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

2.2. Модель Ла Падула

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

R(t) = R(t») — —, i = 1,2...,

i

где А — параметр роста; R(w) = limR(i) — предельная надежность ПО. Эти неизвестные величины автор предлагает вычислить, решив следующие уравнения:

= о,

i=1

Si — mi „ N Ai

—R(w) +—

Si i

z

Si — mi Ai Л 1

i i — R(w) +—I •-

= о,

, , ьч 5 / ) /

/=1 ьч 1 у

где 5 — число тестов на /-м этапе; т/ — число отказов во время /-го этапа; / = 1,2,... т.

Определяемый по этой модели показатель есть надежность ПО на /-м этапе:

Л

R(t) = R(xl)----, / = т +1, т + 2,...

/

2.3. Модель Джелинского — Моранды

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

Функция плотности распределения времени обнаружения /-й ошибки, отсчитываемого от момента выявления (/ - 1)-й ошибки, имеет вид

Р

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

X = С •

где N — число ошибок, первоначально присутствующих в программе; С — коэффициент пропорциональности.

Наиболее вероятные значения величин N и С определяются на основе данных, полученных при тестировании. Для этого фиксируют время выполнения программы до очередного отказа 'ь'2,'3,...,4. Значения N и С можно получить, решив систему уравнений

I (N - / +1)-1 ==—К-----------,

^ N +1-0 •К

С А

Т} к к

где 0=~ш; Л=1и;в=11 • ^

/=1 /=1

Чтобы получить числовые значения Х„ нужно подставить вместо N и С их возможные значения N и С . Рассчитав К значений по формуле (5) и подставив их в выражение (4), можно определить вероятность безотказной работы на различных временных интервалах.

2.4. Модель Шика — Волвертона

Это модификация модели Джелинского — Моранды для случая возникновения на рассматриваемом интервале более одной ошибки. При этом считается, что исправление ошибок производится лишь после истечения интервала времени, на котором они возникли. В основе модели Шика — Волвертона лежит предположение, согласно которому частота ошибок пропорциональна не только количеству ошибок в программах, но и времени тестирования, т.е. вероятность обнаружения ошибок с течением времени возрастает. Интенсивность обнаружения ошибок X; предполагается постоянной в течение интервала времени ^ и пропорциональна числу ошибок, оставшихся в программе по истечении (/ - 1)-го интервала; но она пропорциональна также и суммарному времени, уже затраченному на тестирование:

X/ = С(N - «¿-1)(Т--1 + 'г /2), где С — коэффициент пропорциональности; N — число ошибок, первоначально присутствующих в программе; п/-1 — число ошибок, оставшихся в программе по истечении (/ - 1)-го интервала; Т/-1 — суммарное время, затраченное на тестирование в течение (/ - 1) этапов; ti — среднее время выполнения программы в текущем интервале.

Остальные расчеты аналогичны расчетам модели Джелинского — Моранды.

2.5. Модель Муса

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

Считается, что на протяжении всего жизненного цикла ПО может произойти М0 отказов и при этом будут выявлены все N ошибки, которые присутствовали в ПО до начала тестирования. Общее число отказов М0 связано с первоначальным числом ошибок N0 соотношением N,3 = В • М 0, где В — коэффициент уменьшения числа ошибок. После тестирования, за время которого зафиксировано т отказов и выявлено п ошибок, можно определить коэффициент В: В = п / т.

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

2.6. Модель переходных вероятностей

Процесс тестирования ПО рассматривается как марковский процесс.

Пусть в начальный момент тестирования С = 0) в ПО было п ошибок. Предполагается, что в процессе тестирования выявляется по одной ошибке. Тогда последовательность состояний системы {п, п - 1, п - 2, п - 3,...} соответствует периодам времени, когда предыдущая ошибка уже исправлена, а новая еще не обнаружена. Последовательность состояний {т, т - 1, т - 2, т - 3,.} соответствует периодам времени, когда ошибки исправляются.

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

щих и последующих состояний системы, кроме состояний I и у. Вероятность перехода из состояния (п - к) к состоянию (т - к) есть Хп-к-А1 для к = 0,1,2., где X — интенсивность проявления ошибок.

Надежность ПО в данной модели определяется выражением

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

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

дает возможность оценить первоначальное число ошибок в программе N. Здесь £ — количество искусственно внесенных ошибок; п — число найденных собственных ошибок; V — число обнаруженных к моменту оценки искусственных ошибок.

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

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

ошибок; N — количество собственных ошибок, имеющихся в ПО до начала тестирования.

Использование этой модели предполагает проведение тестирования двумя группами программистов, использующими независимые тестовые наборы, независимо одна от другой. В процессе тестирования каждая из групп фиксирует все найденные ею ошибки. При оценке числа оставшихся в программе ошибок результаты тестирования обеих групп собираются и сравниваются. Положим, первая группа обнаружила N1 ошибок, вторая — Щ, а N12 — это ошибки, обнаруженные дважды (обеими группами). Если обозначить через N неизвестное количество ошибок, присутствовавших в программе до начала тестирования, то можно эффективность тестирования каждой из групп определить как

3. Аналитические статические модели

3.1. Модель Миллса

3.2. Модель Липова

N Б

п + V

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

п + V

; Б — общее количество искусственно внесенных

п

3.3. Простая интуитивная модель

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

В этой модели не используются параметры времени тестирования и учитывается только результат N испытаний, в которых выявлено N1 ошибок /-го типа. Модель использует изменяющиеся вероятности отказов для различных типов ошибок.

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

где N0 — число безотказных выполнений программы; N — общее число прогонов; К — ап-

при тестировании ошибки /-го типа.

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

Пространство элементарных событий в классической модели последовательности испытаний Бернулли содержит 2п точек, где п — число испытаний (в данном случае под испытанием подразумевается запуск программы). Каждый запуск программы имеет два исхода: правильный и неправильный. Обозначим вероятность неправильного исхода р, а вероятность правильного — (1 -р). Вероятность того, что из п запусков к приведут к неправильному результату, выражается формулой биномиального распределения:

где С(п,к) — число сочетаний. Вероятность р априори неизвестна, но по результатам запусков известны п и к. Величина В как функция р имеет максимум при р = к / п. В качестве меры надежности программы принимается величина

Данная модель при расчете надежности ПО учитывает вероятность выбора определенного тестового набора для очередного выполнения программы. Предполагается, что область данных, необходимых для выполнения тестирования программного средства, разделяется на к взаимоисключающих подобластей 2, і = 1,2,...,к. Пусть Рі — вероятность того, что набор данных Хі будет выбран для очередного выполнения программы. Если к моменту оценки надежности было выполнено N1 прогонов программы на Хі наборе данных и из них пі прогонов закончились отказом, то надежность ПО определяется равенством

Тогда

N =

3.4. Модель Коркорэна

а/, если Ni > 0, 0, если Ni = 0;

аі — вероятность выявления

3.5. Модель последовательности испытаний Бернулли

В(р, п,к) = С(п,к) • рк • (1 - р)п к,

Я = 1 - к / п = (п - к)/ п.

3.6. Модель Нельсона

4. Эмпирические модели 4.1. Модель сложности

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

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

4.2. Модель, определяющая время доводки программ

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

5. Вывод

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

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

1. ISO 9126:1991. Информационная технология. Оценка программного продукта. Характеристики качества и руководство по их применению. 186 с.

2. IEEE Std 610.12-1990, IEEE Standard Glossary of Software Engineering Technology (ANSI). 1283 с.

3. Романюк С.Г. // Открытые системы. 1994. №4 — www.osp.ru/os/1994/04/68.htm

4. Благодатских В.А., Волнин В.А., Поскакалов К.Ф. Стандартизация разработки программных средств: Учеб. пособие под ред. О.С.Разумова. М.: Финансы и статистика, 2003. 284 с.

5. Майерс Г. Надежность программного обеспечения. М.: Мир, 1980. 360 с.