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



         

Преобразования, защищающие программное обеспечение


Определим компиляторы, которые по данной программе П, производят пару (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. Далее даются основное определение для задачи защиты программ.


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