Теория и практика защиты программ

Аппроксимирующие функции


Пусть для данной функции f и границы ошибки d, входа x, программа P(x) вычисляющая функцию f, приблизительно корректна, если

|P(x)-f(x)|£d. Это обозначается следующим образом: P(x)»df(x). Будем также считать, что Р(d,e) аппроксимирует функцию f на области D, если

|P-f|£d

на 1-e

элементах области D.

Исходя из работ [GLRSW,RS1], можно показать, как тестировать программы, которые вычисляют полиномы и функции, определенные теоремами сложения, когда выход программы, реализующей вычисления над этими полиномами или функциями является приблизительным. В этих работах также показано, как выполнить аппроксимирующие проверку, самотестирование и самокоррекцию полиномов и функциональных уравнений.

В таблице 4.3 показаны некоторые теоремы сложения для функциональных уравнений, где верна следующая форма f(x+y)=G[f(x),f(y)].

Таблица 4.3.

G[f(x),f(y)]

f(x)



f(x)+f(y)

Ax

tg Ax

ctg Ax

A th Bx

f(x)f(y)-

cos Ax

f(x)f(y)+

ch Ax

Кроме того, в ряде работ (см., например, упоминания в [EKR]) было показано, как строить аппроксимирующие чекеры для ряда модулярных и логарифмических операций, а также функций sin, cos, для умножения и инвертирования матриц, решения систем линейных уравнений и определения детерминантов. Также исследовались проблемы тестирования операций деления с плавающей точкой, одномерных полиномов степени до 9 включительно и многомерных полиномов, а также тестирования ряда других тригонометрических и гиперболических функций.



Содержание раздела