Чтобы проверить выполнимость булевой формулы, необходимо
проверить еe значение некоторое число раз, т.е. необходимо прове-
рить значения существенных составляющих булевой формулы. Таким
образом, можно утверждать, что задача выполнимости булевой форму-
лы сводится к задаче определения существенности ее составляющих
(т.е., по сути, проверить существенность функциональных свойств в
нашем контексте определений) [4].
С учетом изложенного выявили, что задача определения суще-
ственности функциональных свойств в равенстве (13)
NP
-полна.
Итак, подведем итогприведенным теоретическим соображениям.
Во-первых, как доказал Барак в своих работах, обфускация в общем
случае невозможна, так как существует класс программ, для которых
условие Black-Box невыполнимо. Во-вторых, даже если запутываемая
подпрограмма не включена в класс программ, неподверженных обфус-
кации по Бараку, то сгенерированный автоматически алгоритм запу-
тывания, при условии выполнения равенства (7) будет либо сводиться
к равенству (11), что по вполне понятным причинам нежелательно,
либо к системе (8). Следует особо подчеркнуть, что сводимость к
системе (8) вовсе не означает, что “взлом” будет тривиальным, ведь
функциональные свойства
π
0
, π
1
. . . π
n
могут быть реализованы под-
программами с достаточно высокими метриками сложности.
Однако, как уже было указано ранее, единожды проведенный ста-
тический или полустатический анализ запутанного кода позволит вы-
явить основное функциональное свойство подпрограммы и опреде-
лить его составляющие. Впоследствии возможно создание автомати-
ческих или полуавтоматических средств, позволяющих производить
полную или частичную оптимизацию (деобфускацию). В любом слу-
чае, эффект Black-Box при этом не проявляется.
Добавление глобального (по отношению к исследуемой подпро-
грамме) контекста обеспечит гораздо более высокую стойкость запу-
танного кода по отношению к существующим алгоритмам оптими-
зации. Усложнится при этом и статический (полустатический) ана-
лиз подпрограммы. Если следовать при этом ряду рекомендаций по
построению запутывающих преобразований, то можно существенно
снизить вероятность построения деобфускатора, работающего за по-
линомиальное время.
Следует заметить особо, что приведенная доказанная ранее теоре-
ма справедлива только в том случае, если нет существенных различий
в подпрограммах, реализующих истинные и фальшивые функциональ-
ные свойства. Например, если инструкции исходной подпрограммы в
качестве операндов имели числа с плавающей точкой, а добавленные
инструкции работают только с целыми числами, то в данной ситуации
100 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
