Семинар теоретического и экспериментального программирования имени В.А. Непомнящего

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

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

Более подробно будет рассмотрена статья "A Semantics of Structures, Unions, and Underspecified Terms for Formal Specification" (Louis Gauthier, Virgile Prevosto, Julien Signoles, 2024). В этой работе предлагается формализация семантики для части языка ACSL. ACSL - язык спецификации для C, используемый в наборе инструментов верификации Frama-C для аннотации кода. На момент начала работы семантика ACSL не была формально описана, что позволяло неоднозначно трактовать спецификации. Эта статья представляет собой первый этап формализации семантики на Coq. Приведённая семантика основана на семантикe языка C, предложенной в "The C Standard Formalized in Coq" (R. Krebbers, 2015). Наибольшее внимание в статье уделено описанию семантики равенства структур, объединений и логике обработки не полностью специфицированных термов, эти темы не были рассмотрены ранее в других статьях, посвящённых языкам спецификации.

Наконец-то и в России появились пока небольшие группы специалистов, применяющих формальные методы в производственном программировании. Назрела необходимость объединения специалистов для решения существующих проблем в сфере формальных методов на государственном уровне. Предлагаемая форма объединения – ассоциация специалистов, считающих формальные методы своей профильной дисциплиной.

В докладе будет представлен анализ по следующим аспектам:

• позиция научной дисциплины «Формальные методы» в системе наук;
• краткое определение формальных методов: понятия задачи, спецификации, верификации и т.д.
• области применения формальных методов;
• состояние исследований и применений формальных методов в нашей стране;
• проблемы обучения формальным методам;
• основные задачи развития дисциплины исходя из текущего состояния.

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