Общие принципы создания двухмодульных вычислительных процедур и методология самотестирования
Пусть необходимо написать программу P для вычисления функции f так, чтобы P(x)=f(x) для всех значений x. Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью близкой к единице в корректности результата выполнения программы, хотя бы потому, что тестовый набор входных данных, как правило, не перекрывают весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ, которые позволяют оценить вероятность некорректности результата выполнения программы, то есть, что P(x)¹f(x) и корректно вычислить f(x) для любых x, в том случае, если сама программа P на большинстве наборах своих входных данных (но не всех) работает корректно.
Чтобы добиться корректного результата выполнения программы P, вычисляющей функцию f, нам необходимо написать такую программу Tf, которая позволяла бы оценить вероятность того, что P(x)¹f(x) для любых x. Такая вероятность будет называться вероятностью ошибки выполнения программы P. При этом Tf может обращаться к P как к своей подпрограмме.
Обязательным условием для программы Tf является ее принципиальное временное отличие от любой корректной программы вычисления функции f, в том смысле, что время выполнения программы Tf, не учитывающее время вызовов программы P, должно быть значительно меньше, чем время выполнения любой корректной программы для вычисления f. В этом случае, вычисления согласно Tf
некоторым количественным образом должны отличаться от вычислений функции f и самотестирующаяся программа может рассматриваться как независимый шаг при верификации программы P, которая предположительно вычисляет функцию f. Кроме того, желательное свойство для Tf
должно заключаться в том, чтобы ее код был насколько это возможно более простым, то есть Tf
должна быть эффективной в том смысле, что время выполнения Tf
даже с учетом времени, затраченного на вызовы P
должно составлять константный мультипликативный фактор от времени выполнения P. Таким образом, самотестирование должно лишь незначительно замедлять время выполнения программы P.
Пусть p
- означает некоторую вычислительную задачу и/или некоторую задачу поиска решения. Для x, рассматриваемого в качестве входа задачи, пусть p(x) обозначает результат решения задачи p. Пусть Р
– программа (предположительно предназначенная) для решения задачи p, которая останавливается (например, не имеет зацикливаний) на всех входах задачи p. Будем говорить, что Р имеет дефект, если для некоторого входа x задачи p имеет место P(x)¹p(x).
Определим (эффективный) программный чекер Cp
для задачи p следующим образом. Чекер CpP(I,k) – является произвольной вероятностной машиной Тьюринга, удовлетворяющей следующим условиям. Для любой программы P (предположительно решающей задачу p), выполняемой на всех входах задачи p, для любого элемента I задачи p и для любого положительного k (параметра безопасности) имеет место:
· если программа P не имеет дефектов, т.е. P(x)=p(x) для всех входов x задачи p, тогда CpP(I,k) выдаст на выходе ответ «Норма» с вероятностью не менее 1-1/2k;
· если программа P имеет дефекты, т.е. P(x)¹p(x) для всех входов x задачи p, тогда CpP(I,k) выдаст на выходе ответ «Сбой» с вероятностью не менее 1-1/2k.
Самокорректирующаяся программа
– это вероятностная программа Cf, которая помогает программе P
скорректировать саму себя, если только P
выдает корректный результат с низкой вероятностью ошибки, то есть для любого x, Cf
вызывает программу P для корректного вычисления f(x), в то время как собственно сама P обладает низкой вероятностью ошибки.
Самотестирующейся/самокорректирующейся программной парой называется пара программ вида (Tf,Cf). Предположим, что пользователь может взять любую программу P, которая целенаправленно вычисляет f и тестирует саму себя при помощи программы Tf.
Если P проходит такие тесты, тогда по любому x, пользователь может вызвать программу Cf, которая, в свою очередь, вызывает P
для корректного вычисления f(x). Даже если программа P, которая вычисляет значение функции f некорректно для некоторой небольшой доли входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления f(x) для любого x. Кроме того, если удастся в будущем написать программу P¢ для вычисления f, тогда некоторая пара (Tf,Cf) может использоваться для самотестирования и самокоррекции P¢ без какой-либо ее модификации. Таким образом, имеет смысл тратить определенное количество времени для разработки самотестирующейся/ самокорректирующейся программной пары для прикладных вычислительных функций.
Перед тем как перейти к более формальному описанию определений самотестирующихся и самокорректирующихся программ необходимо дать определение вероятностной оракульной программе (по аналогии с вероятностной оракульной машиной Тьюринга).
Вероятностная программа M является вероятностной оракульной программой, если она может вызывать другую программу, которая является исполнимой во время выполнения M. Обозначение MA означает, что M может делать вызовы программы A.
Пусть P - программа, которая предположительно вычисляет функцию f. Пусть I является объединением подмножеств In, где n принадлежит множеству натуральных чисел N и пусть Dp={Dn|nÎN} есть множество распределений вероятностей Dn
над In. Далее, пусть err(P,f,Dn) – это вероятность того, что P(x)¹f(x), где x
выбрано случайно в соответствии с распределением Dn из подмножества In. Пусть b - есть некоторый параметр безопасности. Тогда (e1,e2)-самотестирующейся программой для функции f в отношении Dp с параметрами 0£e1<e2 £1 - называется вероятностная оракульная программа Tf, которая для параметра безопасности b
и любой программы P на входе n имеет следующие свойства:
· если err(P,f,Dn)£e1, тогда программа TfP выдаст на выходе ответ «норма» с вероятностью не менее 1-b.
· если err(P,f,Dn)³e2, тогда программа TfP
выдаст на выходе «сбой» с вероятностью не менее 1-b.
Оракульная программа Cf с параметром 0£e<1 называется
e-самокорректирующейся программой для функции f в отношении множества распределений Dp, которая имеет следующее свойство по входу n, xÎIn и b. Если err(P,f,Dn)£e, тогда CfP=f(x) с вероятностью не менее 1-b.
(e1,e2,e)-самотестирующейся/ самокорректирующейся программной парой для функции f
называется пара вероятностных программ (Tf,Cf) такая, что существуют константы 0£e1<e2£e<1 и множество распределений Dp при которых Tf -есть (e1,e2)-самотестирующаяся программа для функции f в отношении Dp и Cf - есть e-самокорректирующаяся программа для функции 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.
