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


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


При этом под верификацией расчетной программы понимается процесс доказательства того, что программа будет получать на некотором входе истинные значения исследуемой функции. Иными словами, верификация расчетной программы направлена на доказательство отсутствия преднамеренных и (или) непреднамеренных программных дефектов в верифици-руемой программе.

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

Пусть для функции 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-пары функций.

Предположим, что на ST-пару функций можно наложить некоторую совокупность ограничений на сложность программной реализации и время выполнения. В этом случае, пусть длина кода программ, реализующих функции gc и hc , и время их выполнения составляет константный мультип-ликативный фактор от длины кода и времени выполнения программы P. Предлагаемый метод верификации расчетной программы P на основе ST-пары функций для некоторого входного значения вектора X* заключа-ется в выполнении следующего алгоритма. (Всюду далее, если осуществ-ляется случайный выбор значений, этот выбор выполняется в соответствии с распределением вероятностей Dp).




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



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