О.В. Казарин, В.Ю. Скиба
2
довательно, обнаружения в ней программных ошибок и дефектов де-
структивного типа. Пространственно-временную сложность тестирую-
щего модуля для таких программ составляет константный мультипли-
кативный фактор от сложности самой защищаемой программы. Следо-
вательно, весь процесс самотестирования/самокоррекции подобного
рода достаточно эффективен.
Рассмотрим
содержание задачи разработки самотестирующихся
и самокорректирующихся программ и их сочетаний
.
Пусть необходимо написать программу
Р
для вычисления функ-
ции
f
так, чтобы
Р
(
x
) =
f
(
x
) для всех значений
x
(все формальные
определения самотестирующихся и самокорректирующихся про-
грамм можно найти в работах О.В. Казарина, В.Ю. Скибы [3, 5]).
Один из методов решения данной проблемы заключается в со-
здании так называемых самокорректирующихся и самотестирующих-
ся программ, которые позволяют оценить вероятность некорректно-
сти результата выполнения программы, т. е.
P
(
x
)
f
(
x
), и корректно
вычислить
f
(
x
) для любых
x
, в случае, если сама программа
P
на
большинстве наборов своих входных данных (но не всех) работает
корректно.
Чтобы добиться корректного результата выполнения программы
P
, вычисляющей функцию
f
, необходимо написать такую программу
T
f
, которая позволила бы оценить вероятность того, что
P
(
x
)
f
(
x
)
для любых
x
. Такая вероятность будет называться
вероятностью
ошибки
выполнения программы P. При этом
T
f
может обращаться к
P
как к своей подпрограмме. Обязательным условием для программы
T
f
является ее принципиальное
временнóе отличие
от любой коррект-
ной программы вычисления функции
f
, в том смысле, что время вы-
полнения программы
T
f
без учета вызовов программы P должно быть
значительно меньше, чем время выполнения любой корректной про-
граммы для вычисления
f
. В этом случае вычисления согласно ин-
струкциям
T
f
некоторым количественным образом должны отличать-
ся от вычислений функции
f
и самотестирующаяся программа может
рассматриваться как независимый шаг при верификации программы
P
, которая предположительно вычисляет функцию
f
. Кроме того, же-
лательное свойство для программы
T
f
должно заключаться в том,
чтобы ее код был, насколько это возможно, более простым и отли-
чался бы от кода тестируемой программы для вычисления
f
. И более
того, желательно, чтобы программа
T
f
была эффективной в том
смысле, что время выполнения
T
f
даже с учетом времени, затрачен-
ного на вызовы
P
, должно составлять лишь константный мультипли-
кативный фактор от времени выполнения
P
. Таким образом, самоте-
стирование должно лишь незначительно замедлять время выполне-
ния программы
P
.
