Общее описание алгоритма «Квадратного корня»

Интуитивно, чтобы полностью скрыть виртуальную модель доступа, мы должны скрыть следующее:

к каким виртуальным ячейкам осуществляется доступ и в каком порядке?

сколько раз к конкретной виртуальной ячейке осуществляется доступ (в случае, если к ней обращались)?

В первом случае достаточно каким-либо образом «перемешать» память так, чтобы противник не знал, какой фактический адрес памяти соответствует данному виртуальному адресу. Во втором случае, мы должны убедиться, что к любой («перемешанной») локальной памяти осуществляется доступ более одного раза. Высокоуровневые шаги моделирования следующие.

Алгоритм КК

1. Инициализация:

Первые m+

 слов при моделировании

RAM-машины расположены так, чтобы содержать m виртуальных адресов (к которым оригинальная RAM-машина обращается в процессе выполнения) и

 «фиктивных» слов (см. рис.5.1). Оставшиеся  слов распределены так, чтобы обслужить дополнительную («краткосрочную») память. Здесь и далее эта память обозначается зщт. (см. рис. 5.1).

2. Моделирование шагов RAM-машины: До тех пор пока моделирование RAM-машины не остановится, выполнить. (Моделирование выполняется за периоды, каждый из которых состоит из

 шагов оригинальной/моделируемой машины). В каждом таком периоде выполняются следующие шаги.

2.1. Случайно переставить содержимое ячеек от 1 до m+

. То есть необходимо равномерно выбрать перестановку p

над целыми числами от 1 до m+

 и забывающим образом переместить содержимое виртуального слова i в фактическое слово pi. Необходимо подчеркнуть, что память зщт (т.е., ячейки от (m++1) до (m+2)) не участвует в этом случайном перемешивании. Таким образом, фактические адреса от 1 до m+называются перемешанной памятью.

2.2. Моделировать

 виртуальных операций доступа к памяти оригинальной RAM-машины. В процессе моделирования мы сохраняем значения виртуальных операций доступа, восстановленных и модифицированных в течение текущего периода в памяти зщт. Так как размер памяти зщт равняется числу возможных операций доступа в одном периоде, можно хранить все значения, восстановленные в течение текущего периода в памяти зщт.


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

-     сканируется вся память зщт и проверяется, находится ли содержимое виртуального слова i в одном из слов памяти зщт. Подчеркнем, что здесь мы обращаемся к каждой ячейке памяти зщт в предопределенном порядке независимо от того, находится ли там виртуальное слово, которое нам надо;

-     в случае, если i-тое виртуальное слово не найдено в памяти зщт, мы восстанавливаем его из фактического слова p(i), которое является текущей ячейкой i-того виртуального слова в течение этого периода;

-     в противном случае (т.е., в случае, если i-тое виртуальное слово найдено в памяти зщт), мы получаем доступ к следующему «фиктивному слову» в перемешанной памяти (например, мы обращаемся к фактическому адресу p(m+j), где j

- число шагов, моделируемых в текущем периоде);

-     в любом случае модифицируемое значение для i-той виртуальной ячейки записано (забывающим образом) в память зщт

посредством сканирования заново всех слов памяти зщт.

3. Модифицировать перемешанную память. В конце периода, используются значения, сохраненные в памяти зщт

для модификации забывающим образом содержимого перемешанной памяти.

Перед тем как приступить к деталям реализации вышеупомянутых шагов, сделаем несколько замечаний относительно того, почему они составляют забывающее моделирование. Далее покажем, как осуществить доступ к памяти на шаге 1 фиксированным образом а, следовательно, независимо от входа и виртуальной модели доступа оригинальной

RAM-машины. Различают два типа операций доступ к памяти, выполненных на шаге 2: полное сканирование памяти зщт (т.е., осуществление доступа к каждому из слов дважды на каждую виртуальную  операцию   доступа)    и



осуществление доступа к   ячейкам перемешанной памяти во время каждого периода. Для каждых возможных  виртуальных операций доступа, последние  фактических операций доступа равномерно распределены среди всех  подмножеств {1,...,m+}, где распределение вероятностей индуцировано выбором перестановки p. Таким образом, фактический доступ, выполняемый на шаге 2, не открывает никакой информации относительно виртуальных операций доступа, выполняемых в этом шаге. Легко увидеть, что шаг 3 не создает никаких новых трудностей, поскольку он может быть сделан при выполнении операций фактического доступа на шагах 1 и 2 в обратном порядке.


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

---