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


Эффективные алгоритмы для современных информационных систем.

Начало проекта – 2014 год.

С помощью отношения подобия значительно упрощается верификация и тестирование программ, улучшается понимание программ, упрощается их разработка. Опыт исследования и решения многих задач анализа программ (проверка эквивалентности программ, обфускация программ, верификация программ) показывает, что качество и результативность алгоритмов проверки подобия программ можно значительно повысить за счет применения более глубоких методов семантического анализа программ, использующих модели и алгоритмы из алгебры и теории автоматов.

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

Также была изучена и решена еще одна задача анализа и преобразования программ, относящаяся к области реорганизации (рефакторинга) программ. Цель реорганизации программы состоит в том, чтобы за счет эквивалентных преобразований, сохраняющих функциональные свойства программы, привести ее к такому виду, который облегчает понимание программы, имеет более простую структуру, меньший размер, лишен избыточных конструкций и в частности, облегчает обнаружение и устранение клонов (совокупности фрагментов программы, осуществляющих «похожие» преобразования данных). Упрощение программного кода путем замены нескольких фрагментов программы вызовом одной и той же процедуры или макроса сокращает размер программы и облегчает ее понимание и упрощает тестирование и анализ программы, поскольку однородные ошибки, присущие фрагментам одного и того же клона, можно обнаружить и устранить при анализе поведения одной процедуры.


Проект выполняется в рамках программы фундаментальных исследований отделения Математических Наук РАН «Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения».

Исполнитель

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

Перейти к списку всех проектов