УДК 681.3.06
А. В. М а з и н, Д. А. Щ е л к у н о в
ИССЛЕДОВАНИЕ И РАЗРАБОТКА НОВОГО
МЕТОДА ОБФУСКАЦИИ
Рассмотрен метод построения алгоритмов обфускации, обеспечи-
вающий повышенную стойкость программных продуктов и данных
от злоумышленников. Даны определения стойкости подпрограмм
по отношению к автоматическим средствам деобфускации, опре-
делены их функциональные свойства. Сформулирована и доказана
теорема о NP-полноте задачи деобфускации.
Ключевые слова:
кодирование информации, программа, криптография,
запутывание кода, алгоритм, оптимизация.
Теоретические аспекты запутывания кода по Бараку заключаются
в том, что вероятностный алгоритм
О
, рассматриваемый как машина
Тьюринга (ТМ), является обфускатором при выполнении следующих
трех условий [1]:
1.
Функциональность
. Для любой машины Тьюринга
М
алгоритм
О
(
М
)
вычисляет ту же функцию, что и
М
.
2.
Полиномиальное замедление
. Длина и время выполнения алго-
ритма
О
(
М
)
должны быть полиноминально больше аналогичных по-
казателей для
М
, т.е. существует такой полином
p
, что
|
O
(
M
)
|
< p
(
|
M
|
)
,
где
|
M
|
— размер программы
M
, а
|
O
(
M
)
|
— размер запутанной про-
граммы
О
(
М
)
, и если
М
заканчивает свою работу через
t
шагов при
определенном входе
x
, то
О
(
М
)
оканчивает свою работу за
p
(
t
)
шагов
при том же входе
x
.
3.
Свойство виртуальной Black-Box
. Для любой вероятностной ма-
шины Тьюринга PPT
A
найдется вероятностная машина Тьюринга
PPT
S
, такая, что для всех TM
M
справедливо
P r
[
A
(
O
(
M
)) = 1]
−
P r S
M
(1
|
M
|
) = 1
neg
(
|
M
|
)
,
где
P r
— вероятность соответствующего события,
neg
— бесконечно
малая величина.
Новый метод обфускации должен обладать следующими свойст-
вами:
•
возможностью работы с готовыми к запуску приложениями (ма-
шинное представление),
•
более высоким, чем у виртуальных машин, быстродействием при
схожем уровне защищенности,
•
возможностью импортирования в другие программные и аппа-
ратные платформы,
•
возможностью привязки графа потока управления запутанной
подпрограммы к некоторому внешнему ресурсу.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 93
