Лабораторная работа №4 / qual4

Санкт-Петербургский Государственный Электротехнический Университет

(ЛЭТИ)

кафедра МО ЭВМ

Отчет по лабораторной работе №4

Оценка параметров надежности программ по временным моделям обнаружения ошибок

Выполнил студент группы 1382, ФКТИ

Пухкал И.

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

1 Постановка задачи

2

1. Постановка задачи

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

1.Сгенерировать массивы данных {Хi}, где Xi — длительность интервала времени между обнаружением (i − 1)-ой и i-ой ошибок (i [1, 30]), в соответствии с:

• равномерным законом распределения в интервале [0, 20]; при

этом cреднее время между ошибками будет E = 10, σ = 20 = 5.8.

√

2 3

• экспоненциальным законом распределения (E = 10, σ = 10)

W(y) = be−by , y ≥ 0, b = 0.1

•релеевским законом распределения ((E = 8 π/2, σ = 8 2 − π/2))

	y		y2
W (y) =		e−	2c2	, y ≥ 0, c = 8
	c2

2.Для каждого из 3-х массивов {Хi} оценить значение первоначального числа ошибок в программе B. При этом для каждого закона использовать 100%, 80% и 60% входных данных (то есть в массивах {Х i} использовать 30, 24 и 18 элементов). Кроме того, если B > n, оценить

значения средних времен Xj , j = n + 1, n + 2 . . . , n + k до обнаружения k ≤ 5 следующих ошибок.

Модель Джелинского-Моранды основана на следующих предположени-

ях:

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

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

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

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

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

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

2 Выполнение работы

3

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

R(t) = K(B − (i − 1))

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

2. Выполнение работы

2.1. Переход от равномерного закона распределения

К экспоненциальному

Если ti (0, 1] — очередное значение процесса, подчиняющегося равномерному закону распределения, то для получения значения процесса, подчиняющегося экспоненциальному закону (zi)

ti

zi = λe−λx dx = −e−λx t0i = −e−λti + 1

0

ti = −λ1 ln (zi − 1)

К релеевскому

Если ti (0, 1] — очередное значение процесса, подчиняющегося равномерному закону распределения, то для получения значения процесса, подчиняющегося экспоненциальному закону (zi)

	ti		2		2	ti		t2
	zi =	c2 e−		dx = −e−			= −e−		+ 1
			2c2		2c2	0		2c2
		x	x		x			i

0

ti = c −2ln(1 − zi)

2.2.Оценка первоначального числа ошибок в программе

2.2.1. 100 %

Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.

2 Выполнение работы																										4
Равномерное распределение
1,0		1,0		1,0			2,0				2,0			2,0
3,0		3,0		4,0			5,0				7,0			7,0
8,0		8,0		8,0			9,0				9,0			9,0
9,0		9,0		10,0			11,0				13,0			13,0
13,0		13,0		15,0			16,0				17,0			17,0
												n = 30;			n + 1							= 15, 5
												in	2
								A =									= 20, 64 > 15, 5
												n=1(iXi)
												i=1(Xi)
Рассмотрим функции fn(m) и gn(m, A) (m > n).
																	n					1
												fn(m) =
																						m i
																i=1						−
												gn(m, A) =										n
																				m − A
	m		fm		gm(A)				|fm − gm(A)|
	31		3,99		2,89						1,1
	32		3,03		2,64						0,39
	33		2,56		2,43						0,13
	34		2,26		2,24						0,01
	35		2,03		2,09						0,05
	Наименьшая разность (0,01) достигается при значении m = 34.
												ˆ	= 33 ошибок
												B
						ˆ		=							n											= 0, 010
						K				(Bˆ + 1) xi − i · xi

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	=	1		≈ 34 дней
Xn+1			ˆ ˆ
		K(B − n)

И время до полного завершения тестирования:

	1	4	1
ttst =		i=1		≈ 185 дней
	Kˆ		i

Таким же образом можно определить время до обнаружения (n+2)-й и так далее ошибок. Сведем эти данные в таблицу.

Номер ошибки	Через дней
31	34
32	50
33	101

2 Выполнение работы					5
Экспоненциальное распределение
0,51	0,51	0,51	1,05	1,05	1,05
1,63	1,63	2,23	2,88	4,31	4,31
5,11	5,11	5,11	5,98	5,98	5,98
5,98	5,98	6,93	7,99	10,5	10,5
10,5	10,5	13,86	16,09	18,97	18,97

A = 22, 11 > 15, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

m fm		gm(A)	|fm − gm(A)|
31	3,99	3,37	0,62
32	3,03	3,03	0,01
33	2,56	2,75	0,2

Наименьшая разность (0,01) достигается при значении m = 32.

ˆ = 31 ошибок

B

ˆ = 0 018

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 57 дней
Xn+1

И время до полного завершения тестирования:

ttst = 57 дней Больше ошибок по модели не ожидается.

Рэлеевское распределение
2,56	2,56	2,56	3,67	3,67	3,67
4,56	4,56	5,34	6,07	7,43	7,43
8,09	8,09	8,09	8,75	8,75	8,75
8,75	8,75	9,42	10,11	11,59	11,59
11,59	11,59	13,32	14,35	15,58	15,58

A = 19, 38 > 15, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

m fm		gm(A)	|fm − gm(A)|
31	3,99	2,58	1,41
32	3,03	2,38	0,65
33	2,56	2,2	0,36
34	2,26	2,05	0,2
35	2,03	1,92	0,11
36	1,86	1,8	0,06
37	1,72	1,7	0,02
38	1,61	1,61	0,0
39	1,51	1,53	0,02

Наименьшая разность (0,0) достигается при значении m = 38.

2 Выполнение работы

6

ˆ = 37 ошибок

B

ˆ = 0 007

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 21 дней
Xn+1

И время до полного завершения тестирования:

ttst = 376 дней Сведем данные по ошибкам в таблицу.

Номер ошибки	Через дней
31	21
32	24
33	29
34	36
35	48

2.2.2. 80 %

Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.

n = 24; n + 1 = 12, 5 2

Равномерное распределение
1,0	1,0	1,0	2,0	2,0	2,0
3,0	3,0	4,0	5,0	7,0	7,0
8,0	8,0	8,0	9,0	9,0	9,0
9,0	9,0	10,0	11,0	13,0	13,0

				A = 16, 47 > 12, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
	m	fm	gm(A)	|fm − gm(A)|
	25	3,78	2,81	0,96
	26	2,82	2,52	0,3
	27	2,35	2,28	0,07
	28	2,06	2,08	0,02
	29	1,84	1,92	0,07
	Наименьшая разность (0,02) достигается при значении m = 28.
				ˆ
				B = 27 ошибок

ˆ = 0 015

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

2 Выполнение работы	7
ˆ	= 23 дней
Xn+1

И время до полного завершения тестирования:

ttst = 124 дней Сведем данные по ошибкам в таблицу.

Номер ошибки	Через дней
25	23
26	34
27	68

Экспоненциальное распределение
0,51	0,51	0,51	1,05	1,05	1,05
1,63	1,63	2,23	2,88	4,31	4,31
5,11	5,11	5,11	5,98	5,98	5,98
5,98	5,98	6,93	7,99	10,5	10,5

A = 17, 1 > 12, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

m fm		gm(A)	|fm − gm(A)|
25	3,78	3,04	0,74
26	2,82	2,7	0,12
27	2,35	2,43	0,07
28	2,06	2,2	0,14

Наименьшая разность (0,07) достигается при значении m = 27.

ˆ = 26 ошибок

B

ˆ = 0 026

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 19 дней
Xn+1

И время до полного завершения тестирования:

ttst = 57 дней Сведем данные по ошибкам в таблицу.

	Номер ошибки				Через дней
		25				19
		26				38
Рэлеевское распределение
2,56		2,56	2,56		3,67		3,67		3,67
4,56		4,56	5,34		6,07		7,43		7,43
8,09		8,09	8,09		8,75		8,75		8,75
8,75		8,75	9,42		10,11		11,59		11,59

2 Выполнение работы

8

				A = 15, 23 > 12, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
	m	fm	gm(A)	|fm − gm(A)|
	25	3,78	2,46	1,32
	26	2,82	2,23	0,59
	27	2,35	2,04	0,31
	28	2,06	1,88	0,18
	29	1,84	1,74	0,1
	30	1,68	1,63	0,05
	31	1,54	1,52	0,02
	32	1,43	1,43	0,0
	33	1,34	1,35	0,01
	Наименьшая разность (0,0) достигается при значении m = 32.
				ˆ
				B = 31 ошибок

ˆ = 0 009

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 15 дней
Xn+1

И время до полного завершения тестирования:

ttst = 281 дней Сведем данные по ошибкам в таблицу.

Номер ошибки	Через дней
25	15
26	18
27	22
28	27
29	36

2.2.3. 60 %

Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.

					n = 18;		n + 1	= 9, 5
					2
Равномерное распределение
1,0	1,0	1,0	2,0	2,0	2,0
3,0	3,0	4,0	5,0	7,0	7,0
8,0	8,0	8,0	9,0	9,0	9,0
					A = 12, 62 > 9, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

2 Выполнение работы				9
	m fm		gm(A)	|fm − gm(A)|
	19	3,5	2,82	0,67
	20	2,55	2,44	0,11
	21	2,1	2,15	0,05
	22	1,81	1,92	0,11

Наименьшая разность (0,05) достигается при значении m = 21.

ˆ = 20 ошибок

B

ˆ = 0 027

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 18 дней
Xn+1

И время до полного завершения тестирования:

ttst = 55 дней Сведем данные по ошибкам в таблицу.

	Номер ошибки				Через дней
		19				18
		20				37
Экспоненциальное распределение
0,51		0,51	0,51		1,05	1,05		1,05
1,63		1,63	2,23		2,88	4,31		4,31
5,11		5,11	5,11		5,98	5,98		5,98

A = 12, 94 > 9, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

m fm		gm(A)	|fm − gm(A)|
19	3,5	2,97	0,53
20	2,55	2,55	0,0
21	2,1	2,23	0,13

Наименьшая разность (0,0) достигается при значении m = 20.

ˆ = 19 ошибок

B

ˆ = 0 054

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 19 дней
Xn+1

И время до полного завершения тестирования:

ttst = 19 дней Больше ошибок по модели не ожидается.

3 Заключение					10
Рэлеевское распределение
2,56	2,56	2,56	3,67	3,67	3,67
4,56	4,56	5,34	6,07	7,43	7,43
8,09	8,09	8,09	8,75	8,75	8,75

A = 11, 51 > 9, 5

Рассмотрим функции fn(m) и gn(m, A) (m > n).

m fm		gm(A)	|fm − gm(A)|
19	3,5	2,4	1,09
20	2,55	2,12	0,43
21	2,1	1,9	0,2
22	1,81	1,72	0,1
23	1,61	1,57	0,04
24	1,45	1,44	0,01
25	1,33	1,33	0,01
26	1,22	1,24	0,02

Наименьшая разность (0,01) достигается при значении m = 25.

ˆ = 24 ошибок

B

ˆ = 0 014

K ,

Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:

ˆ	= 12 дней
Xn+1

И время до полного завершения тестирования:

ttst = 178 дней Сведем данные по ошибкам в таблицу.

Номер ошибки	Через дней
19	12
20	15
21	18
22	24
23	36

3.Заключение

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

Установлено, что:

•наименьшее число ошибок ожидается при распределении интервалов времени по экспоненциальному закону;

•равномерное распределение интервалов дает величину ожидаемых ошибок большую, чем экспоненциальное, но меньшую, чем рэлеевское;