Скачиваний:
167
Добавлен:
02.05.2014
Размер:
300.54 Кб
Скачать
  1. Защита программ и забывающее моделирование на ram-машинах

    1. Основные положения

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

В этом разделе рассматриваются теоретические аспекты защиты программ от копирования.Эта задача защиты может сводиться к задаче эффективного моделирования RAM-машины(машины с произвольным доступом к памяти (см. приложение и [АХУ])посредством забывающей RAM-машины. Следует заметить, что основные результаты по данной тематике принадлежат О. Голдрайху и Р. Островски [GO,O] и эти исследования активно продолжаются в настоящее время.

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

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

      1. Центральный процессор, имитирующий взаимодействие

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

  • противник экспериментирует с оригинальным защищенным центральным процессором, который пытается выполнить зашифрованную программу, используя память;

  • противник экспериментирует с «поддельным» (фальсифицированным) центральным процессором.

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

При создании центрального процессора, который имитирует эксперименты, имеются две проблемы. Первая заключается в том, что необходимо скрывать от противника значения, сохраненные и восстановленные в/из памяти, и предотвращать попытки противника изменять эти значения. Это делается с использованием традиционных криптографических методов (например, методов вероятностного шифрования и аутентификации сообщений). Вторая проблема заключается в необходимости скрывать от противника последовательность адресов, к которым осуществляется доступ в процессе выполнения программы (здесь и далее это определяется как сокрытие модели доступа).

      1. Сокрытие модели доступа

Сокрытие оригинальной модели доступа к памяти – это абсолютно новая проблема и традиционные криптографические методы здесь не применимы.

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

Цель при решении задачи сокрытия модели доступа состоит в том, чтобы сделать невозможным для противника получить о программе что-либо полезное из модели доступа. В этом случае центральный процессор не будет выполнять программу обычным способом, - он будет заменять каждый оригинальный цикл «выборки/запоминания» многими циклами «выборки/запоминания». Это должно «запутывать» противника и предупреждать его от изучения оригинальной последовательности операций доступа к памяти, т.е. от фактической последовательности. Следовательно, противник не должен улучшить свои возможности по реконструкции оригинальной программы.

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

Предположим, что односторонние функции существуют и пусть k- параметр безопасности функции. Тогда существует эффективный способ преобразования программ в пары, состоящие из физически защищенного центрального процессора сkбитами внутренней защищенной памяти и соответствующей завуалированной программы такой, что центральный процессор имитирует взаимодействие с завуалированной программой, реализуемое за время, ограниченное poly(k). Кроме того, взаменtкоманд оригинальной программы будет выполняться менее чемtkО(1)команд завуалированной программы, а увеличение размера внешней памяти ограничивается факторомk.

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

Соседние файлы в папке Казарин О.В. Теория и практика защиты программ