Разработанный метод обфускации подразумевает добавление фаль-
шивого алгоритма к истинному алгоритму в целях максимального за-
труднения выявления истинного алгоритма в чистом виде. На практике
наиболее ценным является свойство стойкости к автоматическим алго-
ритмам оптимизации или деобфускации. Этим свойством имеет смысл
заменить более строгое свойство Black-Box по Бараку. Формально это
свойство выглядит так [2]:
P r
[
OptA
lg(
O
(
M
)) = 1]
neg
(
|
M
|
)
,
(1)
где
OptAlg
— оптимизирующий алгоритм.
Такое свойство означает, что запутанная подпрограмма
О
(
М
)
счи-
тается стойкой к алгоритму оптимизации, если в результате приме-
нения преобразований
OptAlg
по отношению к подпрограмме
О
(
М
)
исходная подпрограмма
М
не будет восстановлена [3]. Оптимизиру-
ющий алгоритм
OptAlg
должен являться детерминированной ТМ и
находиться в классе сложности
P
. Если
OptAlg
является недетерми-
нированной ТМ, то распознавание языка
О
(
М
)
за полиномиальное
время — вполне разрешимая задача. По сути дела, это накладывает
обязательность интерактивности процесса оптимизации запутанного
кода и данных, а также подразумевает то, что алгоритм
OptAlg
дол-
жен лежать в классе
NP
. Неформально говоря, условие (1) означает,
что достаточно обеспечить невозможность создания автоматическо-
го алгоритма деобфускации (оптимизации) для класса запутывающих
преобразований
O
.
С учетом изложенного приведем следующие определения.
Определение 1.
Запутанная подпрограмма является оптимизацион-
но стойкой, если не существует алгоритма оптимизации этой подпро-
граммы, лежащего в классе сложности
Р
.
Определение 2.
Запутанная подпрограмма
О
(
М
)
является оптими-
зационно стойкой по отношению к алгоритму оптимизации
OptAlg
,
если справедлива формула (1).
В принципе, определение, заданное формулой (1), можно сделать
менее строгим, всего лишь ограничив универсальность алгоритма
OptAlg
:
if
(
P r
[
OptAlg
(
O
(
M
)) = 1]
> neg
(
|
M
|
))
,
(
P r
[
OptAlg
(
O
(
M
))=1]
≈
P r
[
OptAlg
(
O
(
M
))=1])
neg
(
|
M
|
)
.
(2)
В данном случае
O
(
M
)
— это еще одно применение алгоритма
O
по отношению к подпрограмме
M
, а
O
(
M
)
— это применение ал-
горитма
O
по отношению к подпрограмме
M
, отличающейся от
M
.
Таким образом, даже если возможно построить алгоритм оптимиза-
ции
OptAlg
, то он будет актуален только для конкретной подпрограм-
мы
O
(
M
)
.
94 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
