Математические модели оценки надежности ПО.

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

Математические модели надежности программ можно разбить на группы по следующим признакам:

· Вид «функции риска», определяющей временную структуру появления ошибок в программе;

· Сложность разработки программы;

· Способы «посева» ошибок и оценки числа исходных ошибок по соотношению исходных и внесенных;

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

Модели, основанные на использовании функции риска

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

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

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

2. Все ошибки в программе равновероятны и не зависят друг от друга.

3. Все ошибки имеют одинаковую степень важности.

4. Время до следующего отказа программы распределено экспоненциально.

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

6. R(t) = const в промежутке между любыми двумя соседними моментами обнаружения ошибок.

Согласно этим предположениям, функция риска будет представлена как:

В этой формуле t – это произвольный момент времени между обнаружением (i-1)-й и i-й ошибок; K – неизвестный коэффициент масштабирования; B – начальное количество оставшихся в программе ошибок (также неизвестное). Таким образом, если в течении времени t было обнаружено (i-1) ошибок, это означает, что в программе еще остается B-(i-1) необнаруженных ошибок. Полагая, что

и используя предпосылку 6, а также равенство (13.2), можно заключить, что все X_i имеют экспоненциальное распределение

и плотность вероятности отказа, соответственно, равна

Тогда функцию правдоподобия (согласно предпосылке 2) можно записать как

или, переходя к логарифму функции правдоподобия, имеем

(13.2)

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

(13.3)

(13.4)

Из формулы (13.3) получается оценка максимального правдоподобия для K

(13.5)

Подставляя выражение (13.5) в (13.4), находим нелинейное уравнение для вычисления –оценки максимального правдоподобия для B

(13.6)

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

(13.7)

где

Поскольку имеют смысл лишь целочисленные значения , функции из выражения (13.7) можно рассматривать только для целочисленных аргументов. Более того, , поскольку n ошибок с программе уже обнаружено. Таким образом, оценка максимального правдоподобия для B может быть получена с помощью вычисления начальных значений функций f_n(m) и g_n(m) для m=n+1, n+2…, и анализа разницы |f_n(m)-g_n(m)|.

Поскольку правая и левая части выражения (13.7) одинаково монотонны, это порождает проблему единственности решения, а также проблему его существования. Конечное решение в области существует тогда и только тогда, когда выполняется неравенство

(13.8)

В противном случае оценка максимального правдоподобия будет Условие (13.8) можно переписать в более удобном виде

(13.9)

где A – то же самое выражение, что и в формуле (13.7). Необходимо отметить, что, A является интегральной характеристикой n встретившихся в программе за время тестирования ошибок, и представляет (в статистическом смысле) набор интервалов X_i между ошибками.

Рассмотрим пример использования модели Джелинского-Моранды, в котором она применяется к следующим экспериментальным данным: в течение 250 дней было обнаружено 26 ошибок, интервалы между обнаружением которых представлены в таблице 13.1. Для этих данных мы имеем n=26 и . Условие (13.9) выполняется, и, таким образом, оценка максимального правдоподобия имеет единственное решение. В таблице 13.2 представлены начальные значения функций, входящих в уравнение (13.7), для множества аргументов

Наилучшим решением для уравнения (13.7) является m=32 (соответствующая строка в таблице дает минимальное значение разницы функций по модулю, то есть максимально приближает ее к нулю, что нам и требуется), то есть = m-1=31. Из выражения (13.5) находим = 0.007.

Среднее время (время, оставшееся до обнаружения (n+1)-й ошибки) есть инвертированная оценка интенсивности для предыдущей ошибки:

В этом примере, , и время до полного завершения тестирования

Таблица 10. Интервалы между обнаружением ошибок.

I	Xi	I	Xi	i	Xi	i	Xi

Таблица 11. Значения функций.

m
	3.854	2.608	1.246
	2.891	2.371	0.520
	2.427	2.172	0.255
	2.128	2.005	0.123
	1.912	1.861	0.051
	1.744	1.737	0.007
	1.608	1.628	-0.020
	1.496	1.532	-0.036

Простая экспоненциальная модель.

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

Продифференцируем обе части этого уравнения по времени:

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

(13.10)

Если рассмотреть начальные значения N(0)=0, R(0)=KB, то решением уравнения (3.10) будет

(13.11)

Оценки параметров К и В можно получить аналогично модели Джелинского-Моранды и затем с помощью оценки функции риска можно спрогнозировать ситуацию на следующие этапы отладки.

Модель Шика-Уолвертона.

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

Модель основана на следующих предположениях:

1. Все ошибки в программе равновероятны и независимы друг от друга.
2. Все ошибки считаются одинаково серьезными.
3. Исправление ошибок происходит без внесения в программу новых ошибок.

Функция риска для данной модели:

В этой формуле Xi - время между моментом обнаружения (i-1)-й ошибки до текущего момента .

Вероятность безотказного функционирования программы на интервале Xi равна:

,

что дает плотность вероятности отказа

Модели Липова

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

1. Все ошибки равновероятны и независимы друг от друга.

2. Все ошибки считаются одинаково серьезными.

3. Интенсивность обнаружения ошибок постоянна на всем интервале тестирования.

4. На i-том интервале тестирования обнаруживается ошибок, но только из них исправляется.

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

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

(13.12)

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

Геометрические модели

В этом разделе рассмотрен пример геометрической модели, предложенной П. Б. Морандой и являющейся модификацией модели Джелинского-Моранды.

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

1. Общее количество ошибок в программе неограниченно;

2. Ошибки встречаются с разной вероятностью;

3. Процесс обнаружения ошибок не зависит от самих ошибок;

4. Интенсивность обнаружения ошибок изменяется по закону геометрической прогрессии, но между моментами обнаружения ошибок интенсивность постоянна.

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

где t – временной интервал между обнаружением (i-1)-ой и i-той ошибок. Начальное значение этой функции R(0) = D, и функция риска убывает со скоростью геометрической прогрессии (0<K<1) по ходу процесса обнаружения ошибок. Скорость изменения R(t) пропорциональна инвертированному значению константы K:

что приводит к убыванию шага изменения R(t) в процессе обнаружения ошибок. Таким образом, более поздние ошибки труднее обнаружить, и они оказывают меньшее влияние на уменьшение потока ошибок, чем предыдущие ошибки. Если снова положить (временной интервал между обнаружением (i-1)-ой и i-той ошибок), тогда, согласно второму и третьему предположению, Xi распределены экспоненциально с плотностью распределения

Эта модель не позволяет определить, сколько ошибок осталось в ПО, но с ее помощью можно найти его "уровень чистоты". “Уровень чистоты” - это отношение

(13.13)

Оценка максимального правдоподобия для этого значения будет

Модель Шнейдевинда

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

1. Использовать данные об ошибках на всех интервалах;

2. Не рассматривать данные об ошибках, обнаруженных на первых (s-1) интервалах, и использовать только данные с s-того по m-тый;

3. Использовать суммарное количество ошибок, обнаруженных с первого по (s-1)-ый интервал, т.е. , и отдельные ошибки с s-того по m-тый интервалы.

Подход 1 предлагается использовать в тех случаях, когда для предсказания будущего состояния ПО необходимы данные со всех интервалов тестирования. Подход 2 – когда есть причины полагать, что произошел некий перелом в процессе обнаружения ошибок, и только данные последних m – (s-1) интервалов имеет смысл учитывать в прогнозах на будущее. И наконец, подход 3 является компромиссом между первыми двумя подходами.

Модель основана на следующих предположениях:

1. Количество ошибок на интервале тестирования не зависит от количества ошибок на остальных интервалах;

2. Количество обнаруженных ошибок убывает от одного интервала к другому;

3. Все интервалы тестирования имеют одинаковую длину;

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

Лекция 14. Модели, основанные на методе "посева" и разметки ошибок, и модели на основе учета структуры входных данных

Методы оценки надежности программ, основанные на моделях "посева" и разметки ошибок, рассмотрены на примере трех моделей: Милза, Бейзина и простой эвристической модели. Согласно методике, предложенной Милзом, программа изначально “засевается” известным количеством некоторых ошибок - M. Главное предположение модели в том, что "засеянные" ошибки распределены таким же образом, как и естественные ошибки программы, и, следовательно, вероятность обнаружения для "засеянной" ошибки такая же, как и для естественной. После этого начинается процесс тестирования ПО. Пусть во время тестирования было обнаружено (m+v) ошибок, из которых m ошибок было искусственно "засеяно", а v ошибок содержалось в ПО изначально. Тогда, согласно методу максимального правдоподобия, начальное количество ошибок в программе можно оценить следующим образом: .

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

Теперь рассмотрим модель Бейзина. Пусть программный продукт содержит Nk команд. Из этих Nk команд произвольно выбираются n команд, и в каждую из этих n команд заносится ошибка. После этого для тестирования случайным образом выбирается r команд. Если в процессе тестирования было случайным образом обнаружено m “засеянных” и v естественных ошибок, это означает, что, согласно методу максимального правдоподобия, начальное количество ошибок в программе можно оценить следующим образом:

где скобками ][ обозначена целая часть числа.

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

Теперь рассмотрим простую эвристическую модель. Эта модель была предложена Б. Руднером. Она позволяет избавиться от главного недостатка модели Милза. Здесь тестирование производится параллельно, двумя независимыми группами разработчиков ПО.

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