Анализ специфических языковых конструкций и алгебраические преобразования
В качестве второго примера мы выбрали запутанную программу, которая существенно использует специфические языковые конструкции. Эта программа - победитель 1998 года международного конкурса запутанного кода на Си [12]. В конкурсе участвуют программы на языке Си, запутанные вручную. Победители выявляются в таких номинациях, как "самый предательский код на Си", "лучшее анти-использование ANSI C".
Рис. 4. Конвертер ASCII/код Морзе (автор Frans van Dorsselaer).
Программа выполняет перекодирование символов, считываемых со стандартного потока, из кода Морзе и обратно. Она имеет запутанную структуру графа потока управления, её внутренние таблицы закодированы. Для распутывания программы были проделаны следующие шаги:
Программа была оттранслирована во внутреннее представление. Умышленно трудновоспринимаемые идентификаторы (I, l) были переименованы в более простые a, b, c и т. д. Над программой во внутреннем представлении были выполнены некоторые эквивалентные алгебраические преобразования, например (a-1)[strlen(a)] было заменено на a[strlen(a)-1]. Анализ алиасов позволил установить, что только элемент a[0] изменяется в процессе работы программы, следовательно в вызовах функций strspn, memchr вместо массива a могут использоваться строковые литералы. Анализ доменов позволил определить, что выражения, записанные в условном операторе, могут принимать всего два или три значения. Решая Диофантовы уравнения, можно значительно упростить условия. В анализируемой программе далее были проведены анализ избыточных выражений (partial redundancy elimination), анализ нулевых выражений (zero-value analysis). Все это позволило разделить один внутренний цикл на два независимых цикла.
Рис. 5. Конвертер ASCII/MORSE после преобразований.
Программа из внутреннего представления была переведена обратно в Си, при этом был проведён структурный анализ графа потока управления для выявления циклов и представления их в высокоуровневой форме.
На рис. 5 приведён текст программы после всех описанных преобразований. Несмотря на то, что он стал больше, чем текст исходной программы, его структура стала намного проще и понятнее. После этого не составляет труда установить правила перекодирования кода Морзе в код ASCII и обратно.
Рис. 6. Распутанная программа решения задачи "8 ферзей"
Содержание раздела
