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



         

Общие принципы создания двухмодульных вычислительных процедур и методология самотестирования - часть 2


должно составлять константный мультипликативный фактор от времени выполнения 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.


Содержание  Назад  Вперед