Устранение мёртвого кода и свёртка циклов
В качестве третьего примера мы опишем анализ программы, запутанной одним из коммерческих запутывателей программ на Си. Распутывание программы состояло из следующих шагов.
-
Был построен граф потока управления запутанной программы. Вид графа показал, что запутанная программа имеет две ветки условного оператора, не отличающиеся структурой потока управления друг от друга. Каждая из веток состояла из повторяющегося 8 раз фрагмента, что позволило предположить, что при запутывании была выполнена развёртка цикла.
Поскольку запутанная программа была представлена на языке Си, и содержала некоторые конструкции, использованные специально для увеличения размера и затруднения восприятия программы, все избыточные конструкции (ключевое слово register, ключевое слово signed в типе signed int, ненужные приведения типов и ненужные скобки) были удалены. В результате размер программы сократился на 20 Кб.
Далее было проведено статическое устранение мёртвого кода, которое позволило уменьшить размер программы до 64 Кб.
Далее была выполнена минимизация количества локальных переменных. Запутанная программа определяла в начале функции около 800 локальных переменных, время жизни которых в функции было невелико. Был применён алгоритм минимизации количества переменных, который выявил всего 11 необходимых переменных. Лишние определения переменных были удалены. Новые переменные получили имена вида r_1, r_2 вместо использовавшихся в запутанной программе имён вида r_dddddd, где d - десятичная цифра. В результате всех преобразований размер программы сократился до 26 Кб.
Далее в программы были выполнены преобразования по свёртке цикла. Были идентифицированы точные границы итерации цикла; все тела итерации цикла были сопоставлены друг с другом, в результате определились места, зависящие от номера итерации; выражения, зависящие от номера итерации, были переписаны в виде, позволившем ввести переменную цикла. Данные шаги были проведены полуавтоматически с использованием простейших средств сравнения базовых блоков (на текстуальном уровне). Это преобразование привело к тому, что размер программы достиг 3.5 Кб.
На заключительном шаге, применив эквивалентные алгебраические преобразования и выявив принципы кодирования данных, программа была ещё более упрощена. Размер программы составил примерно 1.5 Кб, структура потока управления и структура данных, с которыми манипулировала программа, стали полностю очевидны. Текст распутанной программы приведен на рис. 6.
