Преобразования, защищающие программное обеспечение
Определим компиляторы, которые по данной программе П, производят пару (f,Пf), где f - случайно выбранная функция и Пf – завуалированная программа, которая соответствует П и f. Здесь имеется в виду оракульная RAM-машина, которая на входе (Пf,х) и при доступе к оракулу f, моделирует выполнение П на данных х так, чтобы это моделирование «защищало бы» оригинальную программу П.
Далее даются определения компиляторов
как набора преобразований программ в программно-оракульные пары, которые при выполнении оракульных RAM-программ являются функционально эквивалентными выполнениям оригинальных программ.
Определение 5.5. Компилятор, обозначаемый через C, является вероятностным отображением, которое по входу целочисленного параметра k
и программы П для RAMk возвращает пару (f,Пf) так, чтобы:
f:{0,1}O(k)®{0,1} – случайно выбранная функция;
½Пf½=O(½П½);
для k'=k+O(log k) существует оракульная RAMk' -машина такая, что для каждой П, каждой f и каждого xÎ{0,1} инициируется RAMk' на входе (Пf,x) и при доступе к оракулу f обеспечивает выход П(x).
Оракульная RAMk' -машина отличается от RAMk-машины в том, что RAMk' имеет доступ к оракулу, в то время как RAMk
нет. Понятно, что RAMk'
имеет большую память, а именно RAMk' -машина состоит из 2k'=poly(k)2k
слов, в то время как память RAMk
состоит из 2k слов.
Компиляторы, как определено выше, преобразовывают детерминированные программы в завуалированные программы, которые выполняются на вероятностных RAM-машинах. Теперь непосредственно обратимся к определениям компилятора, защищающего программное обеспечение.
Оракул спецификации для программы П – это оракул, который на запрос x возвращает тройку (П(x),tП(x),sП(x)).
Отметим, что tП(x) и sП(x) обозначает время выполнения и пространственные размеры программы П на данных x. Далее даются основное определение для задачи защиты программ.
В этом определении ADV будет рассматриваться и как вмешивающийся, и как невмешивающийся противник.
Определение 5.6. Для данного компилятора C и противника ADV, компилятор C защищает программное обеспечение от противника ADV, если существует вероятностная оракульная машина М, удовлетворяющая следующим условиям:
(М функционирует примерно за то же самое время, как и ADV) Существует полином p(·) такой, что для каждой строки a время выполнения М на входе (k',½a½) (с учетом доступа к случайному оракулу) было ограничено p(k')T, где T обозначает время выполнения ADV при экспериментировании с RAMk' на входе a;
(М с доступом к оракулу спецификации обеспечивает выход почти идентичный выходу ADV после экспериментирования с результатами работы компилятора)
Для каждой программы П статистическое расстояние между следующими двумя распределениями вероятностей ограничено 2-k'.
Распределение выхода машины ADV при экспериментировании с
Распределение выхода оракульной машины М на входе (k',O(½П½)) и при доступе к оракулу спецификации для П. Распределение берется над пространством вероятностей состоящим из всех возможных результатов подбрасываний монеты машины М с равномерным распределением вероятностей.
Компилятор C обеспечивает слабую защиту программ, если C защищает программы против любого невмешивающего противника. Компилятор C
обеспечивает доказуемую защиту программ от вмешательства, если C
защищает программы против любого вмешивающего противника.
Далее приведем определения затрат на защиту программ. Необходимо напомнить, что для простоты, мы ограничиваем время выполнения программы П
следующим условием: tП(x)>½П½+½x½ для всех x.
Определение 5.7. Пусть C - компилятор и g:N®N – некоторая целочисленная функция. Затраты компилятора C на большинстве аргументов g, если для каждой П, каждого xÎ{0,1}*
и каждой случайно выбранной f
требуемое время выполнения RAMk'
на входе (Пf,x) и при доступе к оракулу f
ограничены сверху g(T)T, где T=tП(x).