Эффективные алгоритмы проверки эквивалентности программ в моделях, связанных с обработкой прерываний.
Эффективные алгоритмы проверки эквивалентности программ в моделях, связанных с обработкой прерываний.
Авторы
Аннотация
Изучается стойкость обфускирующих преобразований вставки "мертвых" участков программного кода. Фрагмент программного кода называется "мертвым", если этот фрагмент выполняется по ходу некоторых вычислений (в отличие от недостижимых фрагментов), но выполненные команды (операторы) указанного фрагмента не оказывают никакого влияния на окончательный результат вычисления. Для оценки стойкости обфускирующих преобразований вставки "мертвых" фрагментов была исследована сложность проблемы эквивалентности в двух алгебраических моделях программ. В каждой из этих моделей операторы программы разбиты на два класса - основные операторы и "мертвые" операторы. В первой из этих моделей действует закон поглощения: каждый основной оператор подавляет результат выполнения любого "мертвого" оператора. Предложен алгоритм сложности $O(n^2\log n)$ решения проблемы эквивалентности в указанной модели. Во второй модели наряду с законом поглощения действует закон коммутативности основных операторов. Для второй модели также предложен алгоритм, проверяющий эквивалентность программ за время $O(n^4\log n)$. Таким образом, обфускация программ путем вставки "мертвых" операторов является нестойким обфускирующим преобразованием.
Ключевые слова
Издание
Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика, 2008, № 2, с. 33-41.
Научная группа
Все публикации за 2008 год
Все публикации