Институт системного программирования им. В.П. Иванникова РАН


К вопросу об обфускации конечных автоматов.

Авторы

Варновский Н.П., Захаров В.А., Кузюрин Н.Н., Шокуров А.В.

Аннотация

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

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

Издание

Материалы IX международной конференции «Интеллектуальные системы и компьютерные науки» (23-27 октября 2006 г.), 2006, Изд-во механико-математического ф-та МГУ Москва, том 1, с. 127-130.

Научная группа

Теоретическая информатика

Все публикации за 2006 год Все публикации