Институт системного программирования им. В.П. Иванникова РАН


Модели и алгоритмы в задаче проверки эквивалентности программ.

Авторы

Захаров В.А.

Аннотация

Проблема эквивалентности программ состоит в том, чтобы для произвольной заданной пары программ выяснить, имеют ли эти программы одинаковое поведение. Строгие определения терминов "программа" и "поведение", фигурирующих в этой формулировке, могут варьироваться, и поэтому проблема эквивалентности программ охватывает целый спектр задач проверки схожести разных видов поведения программ в различных моделях вычислений. Проблема эквивалентности возникает при решении ряда задач системного программирования и компьютерной безопасности, включая задачи оптимизации, реорганизации, обфускации и верификации программ, задачи обнаружения метаморфных и полиморфных вирусов, проверки стойкости криптографических протоколов и др. Чтобы установить как можно более общие алгоритмически вычислимые признаки функциональной эквивалентности программ, можно исследовать более сильные виды эквивалентности программ, которые включаются (в теоретико-множественном смысле) в отношение функциональной эквивалентности, не ограничивая при этом класс рассматриваемых программ. В рамках этого направления были построены многочисленные математические модели программ, обнаружены взаимосвязи между этими моделями программ и другими моделями вычислений, используемыми для решения различных прикладных задач (синтаксического анализа и трансляции формальных языков, моделирования систем управления и др.), созданы разрешающие алгоритмы, некоторые из которых нашли применение в системном программировании. В этой заметке приводится краткий обзор результатов исследований проблемы эквивалентности программ в различных моделях вычислений. Шестидесятилетний период исследования этой проблемы разделен на пять этапов. На каждом этапе выделены наиболее актуальные для того времени (по мнению автора) задачи, перечислены основные результаты их исследований.

Ключевые слова

программа, модель программы, проблема эквивалентности программ, разрешающий алгоритм, сложность

Издание

Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), 2012, Изд-во механико-математического ф-та МГУ Москва, с. 53-62.

Научная группа

Теоретическая информатика

Все публикации за 2012 год Все публикации