ИНСТРУМЕНТАЛЬНАЯ ПОДДЕРЖКА ФОРМАЛЬНОЙ ВЕРИФИКАЦИИ ПРОГРАММ, НАПИСАННЫХ НА ЯЗЫКЕ ФУНКЦИОНАЛЬНО-ПОТОКОВОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ | Научно-инновационный портал СФУ

ИНСТРУМЕНТАЛЬНАЯ ПОДДЕРЖКА ФОРМАЛЬНОЙ ВЕРИФИКАЦИИ ПРОГРАММ, НАПИСАННЫХ НА ЯЗЫКЕ ФУНКЦИОНАЛЬНО-ПОТОКОВОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ

Перевод названия: A TOOLKIT FOR SUPPORTING FORMAL VERIFICATIONOF PROGRAMS IN THE FUNCTIONAL DATA-FLOWPARALLEL PROGRAMMING LANGUAGE

Тип публикации: статья из журнала

Год издания: 2015

Идентификатор DOI: 10.14529/cmse150205

Ключевые слова: functional data-flow parallel programming, Pifagor programming language, programs formal verification, toolkit for supporting formal verification, функционально-потоковое параллельное программирование, язык программирования Пифагор, верификация программ, инструментальные средства для поддержки формальной верификации

Аннотация: Работа посвящена разработке архитектуры инструментальных средств для поддержки формальной верификации функционально-потоковых параллельных программ на языке Пифагор. Используемый метод формальной верификации - дедуктивный анализ на базе исчисления Хоара. Процесс доказательства корректности программы представляется в виде дерева, каждый узел которого - информационный граф программы в котором дуги размечены формулами на языке спецификации. Корнем дерева является исходная тройка Хоара: информационный граф с предусловием и постусловием. В работе рассматриваются основные преобразования, применяемые к информационному графу программы: разметка дуг, эквивалентное преобразование, расщепление, свертка программы. Посредством данных преобразований исходная тройка модифицируется и в конечном счете сводится к набору формул на языке спецификации, истинность которых будет свидетельствовать о корректности программы. Предложена архитектура системы поддержки формальной верификации функционально-потоковых параллельных программ, которая позволяет строить дерево доказательства. Представлена реализация этой системы, описана ее основная функциональность. The article is devoted to the architecture development of the toolkit for supporting formal verification of functional data-flow parallel programs in the Pifagor Language. The method ofdeduction based on Hoare logic is used for formal verification. A proof process is considered asa tree where each node is a program data-flow graph, whose edges are marked with formulasin a specification language. The tree root is the initial Hoare triple, namely the program data-flow graph with a precondition and a postcondition. In this article basic transformations of thedata-flow graph are considered: edge marking, equivalent transformation, splitting, folding of theprogram. By means of these transformations the initial triple is being transformed and finally isreduced to a set of formulas in the specification language. If all of these formulas are identicallytrue, then the program is correct. Architecture of the toolkit for supporting formal verification offunctional data-flow parallel programs is proposed, which allows to construct a proof three. Theimplementation of the toolkit is introduced and its main functionality is considered.

Ссылки на полный текст

Издание

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика

Выпуск журнала: Т. 4, 2

Номера страниц: 58-70

ISSN журнала: 23059052

Место издания: Челябинск

Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Южно-Уральский государственный университет (национальный исследовательский университет)

Авторы

Вхождение в базы данных

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.

Вы можете отметить интересные фрагменты текста, которые будут доступны по уникальной ссылке в адресной строке браузера.