4. СамотестирующиЕся и самокорректирующиЕся программы

   1. Вводные замечания

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

Основополагающей работой в области проверки программ, использующих некоторые присущие им внутренние свойства для контроля результатов своей работы, следует считать, написанную в 1989 г., работу [BK], в которой были формализованы основные идеи построенияпрограммных чекеров. Соответствующие определениясамотестирующихся и самокорректирующихся программв 1993 г. были введены в работах [BLR,L1]. В свою очередь, методология самотестирования явилась результатом объединения трех основных идей из криптографии, вероятностных алгоритмов и тестирования программ [BK]. К ним относятся интерактивные системы доказательств и интерактивные системы доказательств с нулевым разглашением [GMR]. Кроме этого, большое значение имели работы М.О. Рабина по вероятностным вычислениям (см., например, [Ра]) и работа латышского математика Р. Фрейвалдса [F], написанная им еще в 1979 году. Он предложил простой и элегантный чекер для задачи умножения матриц, который можно также эффективно применить и для целочисленного умножения и для умножения полиномов.

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

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

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

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

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

Определим (эффективный)программный чекерC_для задачиследующим образом. Чекер C_^P(I,k) – является произвольной вероятностной машиной Тьюринга, удовлетворяющей следующим условиям. Для любой программыP(предположительно решающей задачу), выполняемой на всех входах задачи, для любого элементаIзадачии для любого положительногоk(параметра безопасности) имеет место:

• если программа Pне имеет дефектов, т.е.P(x)=(x) для всех входовxзадачи, тогдаC_^P(I,k) выдаст на выходе ответ «Норма» с вероятностью не менее 1-1/2^k;

• если программа Pимеет дефекты, т.е.P(x)(x) для всех входовxзадачи, тогдаC_^P(I,k) выдаст на выходе ответ «Сбой» с вероятностью не менее 1-1/2^k.

Самокорректирующаяся программа– это вероятностная программаC_f, которая помогает программеPскорректировать саму себя, если толькоPвыдает корректный результат с низкой вероятностью ошибки, то есть для любогоx,C_fвызывает программуPдля корректного вычисленияf(x), в то время как собственно самаPобладает низкой вероятностью ошибки.

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

Перед тем как перейти к более формальному описанию определений самотестирующихся и самокорректирующихся программ необходимо дать определение вероятностной оракульной программе (по аналогии с вероятностной оракульной машиной Тьюринга).

Вероятностная программа Mявляетсявероятностной оракульной программой, если она может вызывать другую программу, которая является исполнимой во время выполненияM. ОбозначениеM^Aозначает, чтоMможет делать вызовы программы A.

Пусть P- программа, которая предположительно вычисляет функциюf. ПустьIявляется объединением подмножествI_n, гдеnпринадлежит множеству натуральных чиселNи пустьD^p={D_nnN} есть множество распределений вероятностейD_nнадI_n. Далее, пустьerr(P,f,D_n) – это вероятность того, чтоP(x)f(x), гдеxвыбрано случайно в соответствии с распределениемD_nиз подмножестваI_n. Пусть- есть некоторый параметр безопасности. Тогда (₁,₂)-самотестирующейся программойдля функцииfв отношенииD^pс параметрами 0₁<₂ 1 - называется вероятностная оракульная программаT_f, которая для параметра безопасностии любой программыPна входеnимеет следующие свойства:

• если err(P,f,D_n)₁, тогда программаT_f^P выдаст на выходе ответ «норма» с вероятностью не менее 1-.

• если err(P,f,D_n)₂, тогда программаT_f^Pвыдаст на выходе «сбой» с вероятностью не менее 1-.

Оракульная программа C_fс параметром 0<1 называется-самокорректирующейся программойдля функцииfв отношении множества распределенийD^p, которая имеет следующее свойство по входуn,xI_nи. Еслиerr(P,f,D_n), тогдаC_f^P=f(x) с вероятностью не менее 1-.

(₁,₂,)-самотестирующейся/ самокорректирующейся программной парой для функцииfназывается пара вероятностных программ (T_f,C_f) такая, что существуют константы 0₁<₂<1 и множество распределенийD^pпри которыхT_f-есть (₁,₂)-самотестирующаяся программа для функцииfв отношенииD^pиC_f- есть-самокорректирующаяся программа для функцииfв отношении распределенияD^p.

Свойство случайной самосводимости.ПустьxI_nи пустьc>1 - есть целое число. Свойство случайной самосводимости заключается в том, что существует алгоритмA₁, работающий за время пропорциональноеn^O(1), посредством которого функцияf(x) может быть выражена через вычислимую функциюFотx,a₁,...,a_cиf(a₁),...,f(a_c) и алгоритмA₂, работающий за время пропорциональноеn^O(1), посредством которого по данномуxможно вычислитьa₁,...,a_c, где каждоеa_iявляется случайно распределенным надI_n в соответствии с D^p.