Метод создания самотестирующейся расчетной программы с эффективным тестирующим модулем
В качестве расчетной программы рассматривается любая программа, решающая задачу получения значения некоторой вычислимой функции. При этом под верификацией расчетной программы понимается процесс доказательства того, что программа будет получать на некотором входе истинные значения исследуемой функции. Иными словами, верификация расчетной программы направлена на доказательство отсутствия преднамеренных и/или непреднамеренных программных дефектов в верифицируемой программе.
В данном случае предлагается метод создания самотестирующихся программ для верификации расчетных программных модулей [КС2]. Данный метод не требует вычисления эталонных значений и является независимым от используемого при написании расчетной программы языка программирования, что существенно повышает оперативность исследования программы и точность оценки вероятности отсутствия в ней программных дефектов.
Пусть для функции Y = f (X) существует пара функций (gc, hc)Y таких, что:
Y = gc (f (a1), ..., f (ac)),
X = hc (a1, ..., ac).
Легко увидеть, что если значения ai
выбраны из In в соответствии с распределением Dp, тогда пара функций (gc, hc)Y обеспечивает выполнение для функции Y = f (X) свойства случайной самосводимости. Пару функций (gc, hc)Y будем называть ST-парой функций для функции Y = f (X).
Предположим, что на ST-пару функций можно наложить некоторую совокупность ограничений на сложность программной реализации и время выполнения. В этом случае, пусть длина кода программ, реализующих функции gc и hc , и время их выполнения составляет константный мультипликативный фактор от длины кода и времени выполнения программы P.
Предлагаемый метод верификации расчетной программы P
на основе ST-пары функций для некоторого входного значения вектора X* заключается в выполнении следующего алгоритма. (Всюду далее, если осуществляется случайный выбор значений, этот выбор выполняется в соответствии с распределением вероятностей Dp).
Алгоритм ST
1. Определить множество
2. Вызвать программу P для вычисления значения
3. Вызвать c раз программу P для вычисления множества значений
4. Определить значения
5. Если
Таким образом, данный метод не требует вычисления эталонных значений и за одну итерацию позволяет верифицировать корректность программы P на (n+1) значении входных параметров. При этом время верификации можно оценить как
где ti
и tx - время выполнения программы P при входных значениях ai и X* соответственно;
tg и
и множества 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 раза.