Информационная безопасность


Анализ специфических языковых конструкций и алгебраические преобразования


В качестве второго примера мы выбрали запутанную программу, которая существенно использует специфические языковые конструкции. Эта программа - победитель 1998 года международного конкурса запутанного кода на Си [12]. В конкурсе участвуют программы на языке Си, запутанные вручную. Победители выявляются в таких номинациях, как "самый предательский код на Си", "лучшее анти-использование ANSI C".

Рис. 4. Конвертер ASCII/код Морзе (автор Frans van Dorsselaer).

Программа выполняет перекодирование символов, считываемых со стандартного потока, из кода Морзе и обратно. Она имеет запутанную структуру графа потока управления, её внутренние таблицы закодированы. Для распутывания программы были проделаны следующие шаги:

  1. Программа была оттранслирована во внутреннее представление.
  2. Умышленно трудновоспринимаемые идентификаторы (I, l) были переименованы в более простые a, b, c и т. д.
  3. Над программой во внутреннем представлении были выполнены некоторые эквивалентные алгебраические преобразования, например (a-1)[strlen(a)] было заменено на a[strlen(a)-1].
  4. Анализ алиасов позволил установить, что только элемент a[0] изменяется в процессе работы программы, следовательно в вызовах функций strspn, memchr вместо массива a могут использоваться строковые литералы.
  5. Анализ доменов позволил определить, что выражения, записанные в условном операторе, могут принимать всего два или три значения. Решая Диофантовы уравнения, можно значительно упростить условия.
  6. В анализируемой программе далее были проведены анализ избыточных выражений (partial redundancy elimination), анализ нулевых выражений (zero-value analysis). Все это позволило разделить один внутренний цикл на два независимых цикла.

    Рис. 5. Конвертер ASCII/MORSE после преобразований.

  7. Программа из внутреннего представления была переведена обратно в Си, при этом был проведён структурный анализ графа потока управления для выявления циклов и представления их в высокоуровневой форме.

На рис. 5 приведён текст программы после всех описанных преобразований. Несмотря на то, что он стал больше, чем текст исходной программы, его структура стала намного проще и понятнее. После этого не составляет труда установить правила перекодирования кода Морзе в код ASCII и обратно.

Рис. 6. Распутанная программа решения задачи "8 ферзей"




- Начало -  - Назад -  - Вперед -



Книжный магазин