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


О перспективах решения задачи обфускации компьютерных программ.

Авторы

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

Аннотация

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

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

Ключевые слова

обфускация программ, стойкость обфускации, криптосистема, декомпиляция

Издание

Труды конференции (МаБИТ-03) , Москва, 22-24 октября 2003 г, 2003, Московский Центр Непрерывного Мватематического Образования Москва, с. 344-352.

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

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

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