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

Общие положения

Принцип самотестирования программы. Пусть требуется написать программу Р для вычисления функции / так, чтобы Р (х) = Дх) для всех значений х. Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью близкой к единице в корректности результата выполнения программы, хотя бы потому, что тестовый набор входных данных, как правило, не перекрывает весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ, которые позволяют оценить вероятность некорректности результата выполнения программы, т. е. вероятность того, что Р (х) ^Дх), и корректно вычислить Дх) для любых х в том случае, если сама программа Р на большинстве наборах своих входных данных (не на всех наборах) работает корректно.

Чтобы добиться корректного результата выполнения программы Р, вычисляющей функцию /, нам необходимо написать такую программу Д, которая позволяла бы оценить вероятность того, что Р (х) ф Дх) для любых х. Такая вероятность будет называться вероятностью ошибки выполнения программы Р. При этом Д может обращаться к Р как к своей подпрограмме.

Обязательным условием для программы Д является ее принципиальное временное отличие от любой корректной программы вычисления функции/в том смысле, что время выполнения программы Д, не учитывающее время вызовов программы Р, должно быть значительно меньше, чем время выполнения любой корректной программы для вычисления/. В этом случае, вычисления согласно Д некоторым количественным образом должны отличаться от вычислений функции / и самотестирующаяся программа может рассматриваться как независимый шаг при верификации программы Р, которая предположительно вычисляет функцию/. Кроме того, желательное свойство для Д должно заключаться в том, чтобы ее код был, насколько это возможно, более простым. Таким образом, программа Гу должна быть эффективной в том смысле, что время выполнения Гу даже с учетом времени, затраченного на вызовы Р, должно составлять константный мультипликативный фактор от времени выполнения Р. Итак, самотестирование должно лишь незначительно замедлять время выполнения программы Р.

Пусть п означает некоторую вычислительную задачу и/или некоторую задачу поиска решения. Для х, рассматриваемого в качестве входа задачи, пусть я (х) обозначает результат решения задачи к. Пусть Р — программа (предположительно предназначенная) для решения задачи я, которая останавливается (например, не имеет зацикливаний) на всех входах задачи л. Будем говорить, что Р имеет дефект, если для некоторого входа х задачи я имеет место Р (х) Ф я (х).

Эффективный программный чекер С_л для задачи я определим следующим образом. Чекер С/ (/, /с) является произвольной вероятностной машиной Тьюринга, удовлетворяющей следующим условиям. Для любой программы Р (предположительно решающей задачу л), выполняемой на всех входах задачи л, для любого элемента I задачи я и для любого положительного к (параметра безопасности) имеет место следующее:

• • если программа Р не имеет дефектов, т. е. Р (х) = л (х) для всех входов х задачи я, тогда С/ (/, /с)выдаст на выходе ответ «Норма» с вероятностью не менее 1—½^к;
• • если программа Р имеет дефекты, т. е. Р (х) Ф л (х) для всех входов х задачи я, тогда СТ (/, /с)выдаст на выходе ответ «Сбой» с вероятностью не менее 1—½^к.

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

Самотестирующейся/самокорректирующейся программной парой называется пара программ вида (Гу, Су). Предположим, что пользователь может взять любую программу Р, которая целенаправленно вычисляет/ и тестирует саму себя при помощи программы Гу. Если Р проходит такие тесты, тогда по любому х пользователь может вызвать программу Су, которая, в свою очередь, вызывает Р для корректного вычисления/(х). Даже если программа Р вычисляет значение функции/некорректно для некоторой небольшой доли входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления /(х) для любого х. Кроме того, если удастся в будущем написать программу Р' для вычисления/, тогда некоторая пара (Гу, Су) может использоваться для самотестирования и самокоррекции Р' без какой-либо ее модификации. Таким образом, имеет смысл тратить определенное количество времени для разработки самотестирующейся/самокорректирующейся программной пары для вычислительных функций, используемых в прикладных программах.