Сборники трудов ИСП РАН


О проблеме логико-термальной эквивалентности последовательных программ с динамической памятью.

В.А. Захаров, К.С. Иванов.

Аннотация

Некоторые методы обфускации программ предусматривают использование аппарата указателей. Это обусловлено тем, что задача анализа программ, в которых используются указатели, относится к числу алгоритмически трудных задач. Для разработки методов анализа программ, использующих динамическую память, целесообразно ввести и исследовать строгую математическую модель, которая могла бы позволить проводить доказательство корректности полученных алгоритмов, оценивать их сложность и описывать с ее помощью обфускирующие и деобфускирующие преобразования.

В предложенной работе предпринята попытка создать такую модель на основе известной модели стандартных схем программ. В статье рассматривается расширенный вариант стандартных схем программ, обогащенных средствами работы с указателями и динамической памятью. Для предложенной модели рассмотрена задача проверки логико-термальной эквиавлентности, которая ранее была исследована для обычных стандартных схем программ. Показано, что проблема логико-термальной эквивалентности для схем программ с динамической памятью разрешима за полиномиальное время.

Издание

Труды Института системного программирования РАН, том 11, 2006, стр. 61-82.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома