Алгоритм ST

Алгоритм 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 и th1 время определения значения функции 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 раза.

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

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

y = fAM (x) = Ax modulo M.

Выбор данной функции обусловлен тем, что она является одной из основных функций в различных теоретикочисловых конструкциях, например, в схемах электронной цифровой подписи, системах открытого распределения ключей и т.п. Это, в свою очередь, демонстрирует возможность применения предложенного метода при исследовании расчетных программ, решающих конкретные прикладные задачи. Кроме того, очевидно, что данная функция обладает свойством случайной самосводимости, а исходя из результатов работы [62] можно показать, что для данной функции существует (1/288, 1/8)самотестирующаяся программа.

Для экспериментальных исследований была выбрана программа EXP из библиотеки базовых криптографических функций CRYPTOOLS [33], которая реализует функцию дискретного возведения в степень (размерность переменных и констант не превышает 64 байтов). Была разработана интегрированная оболочка для проведения верификации, включающая интерфейс с пользователем и программные процедуры, реализующие некоторую совокупность проверочных тестов. Экспериментальные исследования состояли из определения временных характеристик процесса верификации на основе использования STпары функций и определения возможности обнаружения предложенным методом преднамеренно внесенных программных ошибок. Для этого были определены следующие STпары функций:

В процессе исследований менялась используемая STпара функций и варьировалась размерность параметров A, M и аргумента X. Результаты экспериментов полностью подтвердили приведенные выше временные зависимости (технические результаты исследований авторы в данной работе опускают).

Исследование возможности обнаружения предложенным методом преднамеренно внесенных ошибок заключалось в написании программы EXPZ. Спецификация для программ EXP и EXPZ одна и та же, отличие же заключается в том, что программа EXPZ содержит программную закладку деструктивного характера. Преднамеренно внесенная закладка при исследованиях гарантировала сбой работы программы вычисления значения функции y = fAM (x) = Ax modulo M (то есть обеспечивала получение непраильного значения функции) примерно на каждой восьмой части входных значений экспоненты x.

Было проведено свыше 2000 экспериментов [33]. Все входные значения, на которых произошел сбой программы, были обнаружены, что в дальнейшем подтвердилось проверочными тестами, основанными на использовании малой теоремы Ферма и теореме Эйлера. Этот факт, в свою очередь, экспериментально показал, что программа, реализующая алгоритм ST, является (1/8,1/288)самотестирующейся программой.

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


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок