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

RAM-машина как пара интерактивных машин


Далее рассматривается модель RAM как пара интерактивных машин с ограниченными ресурсами, и даются два базовых понятия: понятие защиты программ и понятие моделирования на забывающей RAM-машине.

В данном разделе RAM-машина представляется как две интерактивные машины: центральный процессор (ЦП) и модуль памяти (МП). Задача исследований сводится к изучению взаимодействия между этими машинами. Для лучшего понимания необходимо начать с конкретизации (для целей данного раздела) определения интерактивной машины Тьюринга.

Интерактивная машина Тьюринга

– многоленточная машина Тьюринга (см. приложение), имеющая следующие ленты:

·

входная лента «только-для-чтения»;

·          выходная лента «только-для-записи»;

·          рабочая лента «для-записи-и-для-чтения»;

·          коммуникационная лента «только-для-чтения»;

·          коммуникационная лента «только-для-записи».

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

в первые ½y½ ячеек ее рабочей ленты. В случае если ½y½>w, выполнение приостанавливается немедленно. В начале каждого раунда, машина читает следующий c-битный блок с коммуникационной ленты «только-для-чтения». После некоторого внутреннего вычисления, использующего рабочую ленту, раунд завершается записью с битов на коммуникационную ленту «только-для-записи». Работа машины может завершиться в некоторой точке с копированием префикса ее рабочей ленты на выходную ленту машины.

Теперь можно определить ЦП и МП как интерактивные машины Тьюринга, которые взаимодействуют друг с другом, а также можно ассоциировать коммуникационную ленту «только-для-чтения» ЦП




с коммуникационной лентой «только-для-записи» МП

и наоборот. Кроме того, и ЦП, и МП будут иметь одну и ту же длину сообщений, то есть, параметр с, определенный выше. МП будет иметь рабочую ленту размером, экспоненциальным от длины сообщений, в то время как ЦП будет иметь рабочую ленту размером, линейным от длины сообщений. Каждое сообщение может содержать «адрес» на рабочей ленте МП и/или содержимое регистров ЦП.

Далее используем k как параметр, определяющий и длину сообщений, и размер рабочих лент ЦП и МП. Кроме того, длина сообщений будет равна k+2+k', а размер рабочей ленты будет равен 2kk', где k'=O(k).

Для каждого kÎN определим MEMk как машину IТМ(k+2+O(k),2kO(k)), работающую точно так, как определено выше. Рабочая лента разбивается на 2k

слов, каждое размером O(k). После копирования входа на рабочую ленту машина MEMk

становится машиной, управляемой сообщениями. После получения сообщения (i,a,v), где iÎ{0,1}2={«запомнить»,«выборка»,«стоп»}, aÎ{0,1}k и vÎ{0,1}O(k), машина MEMk

работает следующим образом.

Если i=«запоминание», тогда машина MEMk копирует значение v из текущего сообщения в число а рабочей ленты.

Если i=«выборка», тогда машина MEMk посылает сообщение, состоящее из текущего содержания слова а

(на рабочей ленте).

Если i=«стоп», тогда машину MEMk копирует префикс рабочей ленты (как специальный символ) на выходную ленту и останавливается.

Далее, пусть для каждого kÎN определим CPUk как машину IТМ(k+2+O(k),O(k)), работающую точно так, как определено выше. После копирования входа на свою рабочую ленту, машина CPUk выполняет вычисления за время, ограниченное poly(k), используя рабочую ленту, и посылает сообщение, полученное в этих вычислениях. В следующих раундах CPUk

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


Число шагов каждого вычисления на рабочей ленте ограничено фиксированным полиномом от k.

Единственная роль входа ЦП заключается в инициализации регистров ЦП, и этот вход в дальнейшем может игнорироваться. «Внутренние» вычисления ЦП в каждом раунде соответствует элементарным операциям над регистрами. Следовательно, число шагов, принимаемых в каждом таком вычислении, является фиксированным полиномом от длины регистра (которая равна O(k)). Теперь можно определить RAM-модель вычислений, как семейство RAMk-машин для каждого k.

Определение 5.1. Для каждого kÎN определим машину RAMk

как пару (CPUk, MEMk), где ленты «только-для-чтения» машины CPUk

совпадают с лентами «только для записи» машины MEMk, а ленты «только-для-записи» машины CPUk

совпадают с лентами «только-для-чтения» машины MEMk. Вход RAMk – это пара (s,y), где s - вход (инициализация) для CPUk и у – вход для MEMk. Выход машины RAMk по входу (s,у), обозначаемый как RAMk(s,у), определен как выход MEMk(y) при взаимодействии с CPUk(s).

Для того, чтобы рассматривать RAM-машину как универсальную машину, необходимо разделить вход у машины MEMk

на «программу» и «данные». То есть, вход у

памяти разделен (специальным символом) на две части, названные программой (обозначенной П) и данными (обозначаемыми x).

Пусть RAMk и s фиксированы и у=(П,х). Определим выход программы П на входных данных х, обозначаемый через П(x) как RAMk(s,у). Определим время выполнения П на данных х, обозначаемое через tП(x), как сумму величины (½у½+½П(x)½) и числа раундов вычисления RAMk(s,у). Определим также размер памяти программы П

для данных х, обозначаемый через sП(x) как сумму величины ½у½

и числа различных адресов, появляющихся в сообщениях, посланных CPUk к MEMk в течение работы RАМk(s,у).

Легко увидеть, что вышеупомянутая формализация непосредственно соответствует модели вычислений с произвольным доступом к памяти.Следовательно, «выполнение П на х» соответствует раундам обмена сообщениями при вычислении RAMk(×,(П,х)). Дополнительный член ½y½+½П(x)½ в tП(x) поясняет время, потраченное при чтении входа и записи выхода, в то время как каждый раунд обмена сообщениями представляет собой единственный цикл в традиционной RAM-модели. Член ½y½ в sП(х) объясняет начальное пространство, взятое по входу.


Содержание раздела