Анализ запутанных программ
В данном разделе мы сопоставим методы запутывания, описанные в разделе 2, и методы анализа программ, рассмотренные в разделе 3. На основании этого сопоставления вводится новая мера устойчивости запутывающих преобразований, а именно.
| Метод запутывания | Метод распутывания |
| искажение имён переменных | переименование переменных |
| использование специфических языковых конструкций | упрощение специфических языковых конструкций |
| развёртка цикла | визуализация графа потока управления функции для выделения потенциальных кандидатов на свертку в цикл; выявление индуктивной переменной, что требует (интерактивного) сравнения базовых блоков и (интерактивных) эквивалентных преобразований выражений, причём при таких преобразованиях выражение может даже (незначительно) усложняться; свёртка цикла |
| использование уникальных переменных в базовых блоках | продвижение копий (статическое и статистическое), минимизация количества используемых переменных |
| введение детерминированного диспетчера | статистическое восстановление графа потока управления |
| введение недетерминированного диспетчера | сравнение трасс, полученных на одном и том же наборе входных данных |
| переплетение кода нескольких базовых блоков в один запутанный базовый блок | статистическое устранение мёртвого кода |
| введение непрозрачных предикатов | статистический анализ покрытия для выявления потенциальных непрозрачных предикатов, поиск по образцам известных непрозрачных предикатов, алгебраическое упрощение, доказательство теорем |
| все методы | свёртка констант, продвижение констант, продвижение копий, статическое устранение мёртвого кода - могут выполняться после каждого шага распутывающих преобразований |
Таблица 1. Методы запутывания программ и методы, которые могут применятся для их анализа.
запутывающее преобразование называется устойчивым относительно некоторого класса методов анализа программ, если методы этого класса не позволяют надёжно раскрыть данное запутывающее преобразование Перечисление некоторых методов запутывания программ с точки зрения методов их возможного распутывания дано в таблице 1.
| Преобразование | Сложность распутывания (необходимый тип анализа) | Автоматизируемость (тип распутывателя) |
| Удаление комментариев | Одностороннее преобразование | hh |
| Переформатирование программы | Синтаксический | автомат. |
| Удаление отладочной информации | Одностороннее преобразование | hh |
| Изменение имён идентификаторов | Синтаксический | полуавтомат. |
| Языково-специфические преобразования | Синтаксический | автомат. |
| Открытая вставка функций | Одностороннее преобразование | поддерж. |
| Вынос группы операторов | Синтаксический | автомат. |
| Непрозрачные предикаты и выражения | Синтаксический - статистический (зависит от вида предиката) | автомат. - поддерж. |
| Внесение недостижимого кода | Зависит от стойкости непрозрачных предикатов | автомат., полуавтомат. |
| Внесение мёртвого кода | Синтаксический - статистический | автомат., полуавтомат. |
| Внесение избыточного кода | Синтаксический - статистический | автомат., поддерж. |
| Внесение несводимости в граф | Статический, но зависит от стойкости непрозрачных предикатов | автомат., полуавтомат. |
| Устранение библиотечных вызовов | Одностороннее преобразование | поддерж. |
| Переплетение функций | Статический - статистический | автомат. - поддерж. |
| Клонирование функций или базовых блоков | Статический | автомат. - поддерж. |
| Развёртка циклов | Одностороннее преобразование | поддерж. |
| Разложение циклов | Статический | автомат. - поддерж. |
| Введение диспетчера | Статический - статистический | автомат., полуавтомат. |
| Локализация переменных в базовом блоке | Статический - статистическийе | автомат., полуавтомат. |
| Расширение области действия переменных | Статический - статистический | автомат., полуавтомат. |
В таблице 2 приведена классификация методов запутывания по отношению к требуемым методам анализа программ. В третьем столбце таблицы указана степень, в которой возможно автоматическое распутывание. Степень автоматизма оценивается по следующей шкале: автоматический - поиск в программе запутанных фрагментов и их распутывание возможны полностью автоматически; полуавтоматический - поиск в программе подозрительных фрагментов и их распутывание по отдельности выполняются автоматически, но пользователь должен подтвердить применение распутывающего преобразования; поддерживаемый - поиск в программе запутанных фрагментов и применение распутывающих преобразований требуют существенного участия человека, но процесс может быть поддержан специальными инструментальными средствами; неавтоматизируемый - автоматизация выполнения распутывающего преобразования принципиально затруднена.
Для некоторых видов запутывающих преобразований требуемые инструменты (синтаксические, статические, статистические) зависят от того, каким способом было реализовано преобразование. Например, непрозрачные предикаты могут быть самого разного вида, от простейших if(0), до очень сложных. Для анализа и устранения простейших непрозрачных предикатов достаточно инструментов уровня синтаксического анализа, которые работают автоматически, а для устранения сложных непрозрачных предикатов требуется статистический анализ, либо сложные инструменты, такие как полуавтоматический доказатель теорем. Поэтому некоторые ячейки таблицы содержат несколько необходимых видов анализа или несколько оценок автоматизируемости.
