Устойчивость, линейная и единичная состоятельность
Пусть свойствоI выражается уравнением I(x1,...,xk)=0, где кортеж (áx1,...,xk) выбирается с распределением E из пространства Dk. Пара (I,E) характеризует семейство функций F, где fÎF тогда и только тогда, когда для всех (x1,...,xk) с ненулевой выборкой элементов кортежа из E, I f(x1,...,xk)=0. Базовой техникой самотестирования является идентификация свойства устойчивости для семейства функций F. Неформально (D,D¢)-устойчивость пары (I,E) для семейства функций G
реализует, что если для программы PÎG, свойство IP(x1,...,xk)=0 удовлетворяется с высокой вероятностью, когда áx1,...,xkñ выбрано с распределением E из Dk, тогда существует функция gÎFÇG, которая согласуется с P на большей части входов из D¢.
Рассмотрим некоторое свойство линейности (I,E), где свойство I f(x1,x2,x3) тождественно f(x1)+f(x2)=f(x3) и E означает (x1ÎRZp,x2ÎRZp,x1+x2). Пара (I,E) характеризует F={f(x)=cx½cÎZp} – множество всех линейных функций над Zp. В этом примере G – тривиальное множество всех функций и пара (I,E) устойчива для G.
Как только мы убедились посредством рандомизированных попыток, что программа Р удовлетворяет свойству устойчивости, можно переходить к тестированию программы на линейную и единичную состоятельность.
Существует два базовых теста для самотестирующихся программ – тест линейной состоятельности и тест единичной состоятельности [BLR]. Продемонстрируем построение таких тестов на примере следующей тривиальной модулярной функции. Пусть x,R – положительные целые, тогда fR(x)ºx (mod R), где R - фиксировано.
Пусть x1 и x2 случайно, равновероятно и независимо от других событий выбраны из ZR2n и x принимает значение: x:ºx1+x2(mod R2n). Необходимо отметить, что fR(x)º[fR(x1)+fR(x2)](mod R) – линейная функция по всем входам (аргументам). Тогда тест линейной состоятельности заключается в выполнении или не выполнении равенства: PR(x)º[PR(x1)+PR(x2)](mod R), а ошибка линейной состоятельности – есть вероятность того, что данный тест не выполнился.
Пусть z случайно выбрано из ZR2n в соответствии с распределением
