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

Целесообразность управления надежностью обосновывается следующим:

• необходимостью достижения разумного компромисса между объемом памяти и времени выполнения.

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

• для оценки завершения тестирования

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

4.4.1. Модели надежности по по структуре времени

МОДЕЛЬ ДЖЕЛИНСКОГО - МОРАНДЫ

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

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

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

3. каждая ошибка имеет один и тот же порядок серьезности;

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

5. ПО функционирует в среде, близкой к реальным условиям;

6. Ошибки постоянно корректируются без внесения в ПО новых

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

В соответствии с этими допущениями можно функцию риска представить в следующем виде:

K[B – (i - 1)

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

Полагая и используя допущение 7, можно утверждать, что все Xi имеют экспоненциальное распределение:

P(Xi) = exp{ - K [B – (i - 1)] Xi},

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

exp{ - K [B – (i - 1)] Xi}

Тогда функция правдоподобия (согласно допущению 2)

Оценка максимального правдоподобия для К:

Нелинейное уравнение для оценки максимального правдоподобия величины :

Прежде чем пытаться решать уравнение, его можно упростить:

Итак, получение оценки для сводится лишь к вычислению начальных значений функций и для m+n+1, n+2, … и анализу разности . Обе функции в этой области являются монотонно убывающими. Для это очевидно, а для существует рекуррентное соотношение, позволяющее легко вычислить,

Получить конечное решение в области возможно тогда и только тогда, если

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

Необходимо отметить, что величина А является как бы интегральной характеристикой проведенных наблюдений за n ошибками ПО и заменяет (в статистическом смысле) набор интервалов между ошибками. Если величина А достаточно большая, то полученная оценка приближается к n – числу обнаруженных к данному моменту ошибок. Это создает радужное впечатление о том, что процесс тестирования близок к завершению, тогда как в действительности B может быть больше n.

Рассмотрим пример использования изложенного метода в применении к данным этапа отладки одной программной системы. В течение 250 дней было найдено 26 ошибок; интервалы, зафиксированные между ошибками, приведены в табл. 1. Для приведенных данных n=26 и

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

Таблица 1

i	Xi	i	Xi	i	Xi		m	f26(m)	g26(m, A)	f26(m)- g26(m, A)
1	9	8	8	15	4		27	3.854	2.608	1.246
2	12	9	5	16	1		28	2.891	2.371	0.520
3	11	10	7	17	3		29	2.427	2.172	0.255
4	4	11	1	18	3		30	2.128	2.005	0.123
5	7	12	6	19	6		31	1.912	1.861	0.051
6	2	13	1	20	1		32	1.744	1.737	0.007
7	5	14	9				33	1.608	1.628	-0.020
Примечание. Принятые обозначения: i – номер ошибки; Xi – время между ошибками, дни.							34	1.496	1.532	-0.036

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

ПРОСТАЯ ЭКСПОНЕНЦИАЛЬНАЯ МОДЕЛЬ

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

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

Введем следующие обозначения: С учетом этих обозначений уравнение можно записать в виде:

Логарифмируем обе части этого равенства и переходя к дискретному времени t_i , получим систему уравнений

Эту систему можно записать в векторно-матричном виде

AX=C.

где

Решением системы будет:

или, используя подробную запись,

.

Рассмотрим пример применения этой модели. В примере использован фрагмент дневника внесения изменений в реально разработанное ПО. Объем этого ПО, выражений в числе строк программного кода (использован язык Ассемблера), составлял 32 K . Временной дискрет был принят равным одному месяцу. При тестировании подсчитывалось, сколько ошибок было выявлено в течение каждого из 20 месяцев , составляющих часть этапа комплексной откладки (табл.2). Из табл. 2 видно, что за первый месяц интенсивность составляла 53 ошибки в месяц, за второй- 74 ошибки в месяц и т.д.

Таблица 2 Таблица 3

	R		R		R		R			R	R
1	53	6	50	11	24	16	34		21	9	4
2	74	7	14	12	36	17	23		22	8	9
3	38	8	43	13	46	18	11		23	7	11
4	21	9	69	14	11	19	1		24	7	9
5	27	10	48	15	28	20	10		Сумма	31	33

В результате расчетов найдены следующие оценки для параметров и функции риска: = 713, = 0,097.

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

.

На основании этой зависимости был сделан прогноз на следующие четыре месяца откладки (порядковые номера – 21, 22, 23, 24 – табл. 5). Отладка и тестирование ПО продолжались, и были получены очередные значения интенсивности ошибок R . Как видно из табл.3, прогноз достаточно хорошо подтвердился

Можно определить время, потребное для снижения интенсивности появления ошибок до одной за месяц:

.

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

МОДЕЛЬ ШИКА - УОЛВЕРТОНА

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

Допущения, лежащие в основании модели, выглядят так:

1. появление ошибок равновероятно и независимо;

2. все ошибки имеют одинаковую степень серьезности;

3. ПО работает в условиях, близких к реальным;

4. ошибки корректируются без введения новых.

Функция риска для этой модели имеет следующий вид:

где - время тестирования, прошедшее от момента обнаружения (i-1) ошибки до текущего момента .

Для вероятности безотказной работы имеем следующее выражение:

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

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

Применим теперь рассмотренную модель к данным предыдущего примера.

где

.

Для n = 26 табл. 2 получается =231 826; A 22,477.

В табл. 4 сведены начальные значения для m>= n + 1. Нетрудно убедится, что навязка монотонно возрастает, не имея минимума модуля для конечных знаний m. Поэтому модель Шика-Уолвертона можно считать неадекватной рассматриваемым данным. Кроме такого вывода, условие существования решения необходимо дополнить верхней границей , лежащей, очевидно, между A и A . Численные расчеты на ЭВМ приводят к значению (для n = 26), при котором навязка становится величиной одного знака.

Таблица 4

m
27	3,854	5,748	-1,894
28	2,891	4,708	-1,817
29	2,427	3,986	-1,559
30	2,128	3,456	-1,328
…	…	…	…
60	0,574	0,693	-0,119

МОДЕЛИ ЛИПОВА

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

1. все появления ошибок равновероятны и независимы;

2. все ошибки имеют один порядок серьезности;

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

4. ПО работает в условиях, близких к реальным;

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

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

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

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

Система уравнений для нахождения оценок максимального правдоподобия для B:

;

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

.

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

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

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

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

где

Интегральная характеристика для второй модели Липова есть

и составляет для n=26, что больше . Также как и в случае применения модели Шика-Уолвертона к рассматриваемым данным, осмысленного решения уравнений (2.25) нет и вторая модель Липова неприменима.