Безопасность программного обеспечения компьютерных систем

Ао ротек: центр удаленного мониторинга ротек.

Методы создания самотестирующихся


Алгоритм ST

Определить множество A*={a1*,...,ac*} такое, что X*=hc{a1*,...,ac*} , где a1*,...,ac* выбраны случайно из входного подмножества In.

Вызвать программу P для вычисления значения Y0*=f(X*)

Вызвать c раз программу P для вычисления множества значений {f(a1*),...,f(ac*)}

Определить значения Y1*=gc{f(a1*) ,...,f(ac*)}

Если Y0*=Y1* , то принимается решение, что программа P корректна на множестве значений входных параметров {X*,a1*,...,ac*} в противном случае данная программа является некорректной.

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

где ti и tx - время выполнения программы P при входных значениях ai и X* соответственно;

tg и th-1 - время определения значения функции gc и множества A* соответственно:

TP (X) - временная (не асимптотическая) сложность выполнения программы P;

Kgh (X, c)- коэффициент временной сложности программной реализации функции gc и определения A* по отношению ко временной сложности программы P (по предположению он составляет константный мульти-пликативный фактор от TP (X), а его значение меньше 1). Для традиционного вышеуказанного метода тестирования время выполнения и сравнения полученного результата с эталонным значением составляет:

где tie и txe - время определения эталонных значений функции Y = f (X) при значениях ai и X* соответственно (в общем случае, не может быть меньше времени выполнения программы).

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

Так как, коэффициент Kgh < 1, а c 2, то получаем относительный вы-игрыш по оперативности испытания расчетных программ указанного типа (обладающих свойством случайной самосводимости) более чем в 1.5 раза.

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

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




Начало  Назад  Вперед



Книжный магазин