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


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


Далее, пусть err(P,f,Dn) это вероятность того, что P(x) f(x), где x выбрано случайно в соответствии с распределением Dn из подмножества In. Пусть ? - есть некоторый параметр безопасности. Тогда (?1, ?2)-самотестирующейся программой для функции f в отношении Dp с параметрами 0 ?12 1 - называется вероятностная оракульная программа Tf, которая для параметра безопасности ? и любой программы P на входе n имеет следующие свойства:

    - если err(P,f,Dn)?1, тогда программа TfP выдаст на выходе ответ "норма" с вероятностью не менее 1-? .

    - если err(P,f,Dn)?2, тогда программа TfP выдаст на выходе "сбой" с вероятностью не менее 1-? .

Оракульная программа Cf с параметром 0 ? < 1 называется ?-самокорректирующейся программой для функции f в отношении множества распределений Dp, которая имеет следующее свойство по входу n,x In и ?. Если err(P,f,Dn)? , тогда CfP=f(x) с вероятностью не менее 1- ?.

(?1,?2,?)-самотестирующейся/ самокорректирующейся программной парой для функции f называется пара вероятностных программ (Tf,Cf) такая, что существуют константы 0 ?1 < ?2 ? < 1 и множество распределений Dp при которых Tf -есть (?1,?2)-самотестирующаяся программа для функции f в отношении Dp и Cf - есть ?-самокорректирующаяся программа для функции f в отношении распределения Dp.

Свойство случайной самосводимости. Пусть x In и пусть c > 1 - есть целое число. Свойство случайной самосводимости заключается в том, что существует алгоритм A1, работающий за время пропорциональное nO(1), по-средством которого функция f(x) может быть выражена через вычислимую функцию F от x, a1,...,ac и f(a1),...,f(ac) и алгоритм A2, работающий за время пропорциональное nO(1), посредством которого по данному x можно вычислить a1,...,ac, где каждое ai является случайно распределенным над In в со-ответствии с Dp.

Метод создания самотестирующейся расчетной программы с эффективным тестирующим модулем

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




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



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