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

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

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

Abstract

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

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

Edition

Proceedings of the Institute for System Programming, vol. 11 (in Russian), 2006, Стр. 61-82.

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

For citation

В.А. Захаров, К.С. Иванов. О проблеме логико-термальной эквивалентности последовательных программ с динамической памятью. . Proceedings of the Institute for System Programming, vol. 11 (in Russian), 2006, Стр. 61-82. .

Full text of the paper in pdf (in Russian) Back to the contents of the volume