Способ генерации баз знаний для систем верификации программного обеспечения распределенных вычислительных комплексов и устройство для его реализации

Способ генерации баз знаний для систем верификации программного обеспечения распределенных вычислительных комплексов и устройство для его реализации

Иллюстрации

Показать все

Реферат

Изобретение относится к средствам автоматизации обучения и научных исследований и предназначено для использования в интерактивных системах автоматизации научно-исследовательских работ в процессе верификации (проверки, тестирования и т.п.) программного обеспечения (ПО) распределенных вычислительных комплексов (РВК).

Известны интерактивные системы автоматизации основных процессов научных исследований в процессе верификации (проверки, тестирования и т.п.) ПО РВК (см. например, DE 10247914 A1 (BOSCH GMBH ROBERT (DE)) 22.04.2004, G 09 В 9/08; DE 10141737 A1 (DAIMLER CHRYSLER AG (DE)) 03.04.2003, G 09 В 9/08; H 04 L 9/30; H 04 L 12/40; B 60 R 16/02; FR 2559599 A1 (GAUER BERNARD (FR)) 16.08.1985, G 09 В 9/08; GB 2366640 A (IBM) 13.03.2002 G 06 F 1/00; GB 2283341 (SOPHOS PLC (GB)) 03.05.1995 G 06 F 1/00; JP 2004302584 A (NIPPON ELECTRIC CO) 28.10.2004, G 09 В 9/08; JP 2004164617 A (MICROSOFT CORP) 10.06.2004, G 09 В 9/08). В основе работы вышеперечисленных систем использованы способы динамического или статического тестирования ПО. Вышеперечисленные технические решения позволяют для некоторых классов ПО избежать их некорректного исполнения, однако существенным недостатком таких решений является сложность выявления скрытых уязвимостей в исходном коде (ИК) ПО РВК, а также невозможность гарантировать правильность полученных результатов на ранних стадиях проектирования ПО РВК. При этом технические реализации статического способа анализа ПО, как правило, представляют различные модификации лексических сканеров ИК ПО и не позволяют осуществить глубокий анализ ни хода выполнения ПО РВК, ни содержания используемой памяти (например, массивов, переменных и т.п.).

В этой связи главный недостаток известных технических решений предопределен тем, что процессы верификации ПО РВК, как правило, представляют ненаблюдаемые/неуправляемые во времени процессы. При этом сам процесс поиска уязвимости в ИК ПО представляет в большей степени искусство, нежели какую-либо формализованную процедуру. При этом низкая производительность данного класса технических решений обусловлена потерей времени, затрачиваемого на формирование тестовых наборов данных, выбора количественных и качественных характеристик, позволяющих оценить уязвимость ИК ПО, определения входных данных определенных типов, в особенности строкового или процедурного типа, являющиеся наиболее распространенными в практике разработки ПО РВК.

Достижению требуемого технического результата во всех приведенных аналогах, включая соответствующий способ верификации ПО, препятствует то, что ни одно из них не может обеспечить полную наблюдаемость/управляемость за динамикой процесса генерации баз знаний на основных этапах верификации ИК ПО РВК систем автоматизации научно-исследовательских работ.

Задачей изобретения является расширение функциональных возможностей интерактивных процессов выполнения научно-исследовательских работ на основе автоматизации основных процессов генерации баз знаний для верификации ПО РВК, а также повышение точности и достоверности выявления уязвимостей в ИК ПО на основных этапах проектирования и сопровождения (аудита) программного кода сложных вычислительных систем и сетей.

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

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

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

Динамические массивы и соответствующие базы знаний трансформации или преобразования дерева исходного кода программного обеспечения в процессе верификации/разбора исходного листинга программы состоят в том, что если дерево с указанной вершиной соответствует определению и содержит внутри себя спецификатор ”extern”, то такое дерево удаляется, кроме этого, если дерево соответствует блочной инструкции, то каждое поддерево блочной инструкции с вершиной в ”ребенке” обрабатываемой вершины заменяется на список поддеревьев, соответствующих инструкциям в этой блочной инструкции.

Точки или участки уязвимости исходного кода ПО определяют на основе автоматического составления и решения линейных систем уравнений.

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

В качестве независимых каналов используют интерфейс последовательного порта или сетевой интерфейс.

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

При этом генерацию баз знаний осуществляют на основе использования аннотаций внешних функций ИК ПО РВК.

База знаний представляет набор правил или моделей протоколов верификации ИК ПО, обеспечивающих поддержку интерактивных процессов поиска уязвимости ПО.

Кроме этого, в процессе верификации ИК ПО осуществляют синтаксическую подсветку на экране блока видеоконтроля (БВ), предназначенного для визуализации (БВ) участков уязвимости ИК ПО, при этом используют граф (дерево разбора и т.п.) операторов ИК ПО во внутреннем представлении инструкций языка программирования.

Диагностику процесса верификации ИК ПО осуществляют на основе измерения длительности выполнения основных этапов (циклов и т.п.) поиска уязвимости и сопоставления полученных значений с ранее предписанными или предсказанными оценками показателя (степени, энтропии и т.п.) критичности уязвимости ИК ПО.

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

Для реализации предлагаемого способа генерации баз знаний предлагается интерактивное программируемое устройство (ИПУ) для систем верификации программного обеспечения распределенных вычислительных комплексов (СВПО РВК), содержащее аппаратно-программный блок (АПБ) лексического и семантического анализа/разбора, АПБ преобразования кода, АПБ анализа кода; АПБ процессорного управления, видео адаптер, интерфейсы жестких, гибких и оптических дисков, интерфейс последовательного порта, сетевой интерфейс и системную память, которые объединены системной шиной, при этом системная память содержит постоянное запоминающее устройство (ROM) и оперативное запоминающее устройство (RAM/ОЗУ), в ячейках оперативной памяти и жестких дисков размещают/записывают операционные системы, прикладные программы, базы данных и базы знаний, которые содержат листинги исходных программ, грамматику языка программирования (например, грамматику языка программирования Си), правила преобразования дерева разбора листинга программы, дерево разбора листинга программы, таблицу типов языка программирования, аннотации внешних функций, включающие их грамматику и семантику, код программ на языке внутреннего представления, условия корректности языка внутреннего представления исходного кода программы, условия проверки корректности подозрительных точек исходного кода программы, информационную базу, содержащую системы ограничений в виде алгебраических уравнений и неравенств, отчеты об обнаруженных уязвимостях программного кода, включающие:

указание на местоположение возможной уязвимости в исходном коде программы, которое содержит имя файла листинга программы, номер строки и номер позиции в строке программы в котором возможно переполнение буфера запоминающего устройства, контекст исходной программы, содержащий возможное переполнение (некоторую ”окрестность” потенциально опасной точки переполнения буфера запоминающего устройства);

указание причины переполнения буфера запоминающего устройства - значения исходных переменных, приводящих к возникновению уязвимости исходного кода программного обеспечения;

показатель или степень критичности обнаруженной уязвимости исходного кода программного обеспечения;

указание на перечень правил или алгоритмов для устранения уязвимости исходного кода программного обеспечения.

При этом аппаратно-программный блок процессорного управления, обеспечивающий синхронизацию основных режимов интерактивной верификации программного обеспечения распределенных вычислительных комплексов, содержит последовательно соединенные блок нормирующих преобразователей (БНП), модуль коммутатора, модуль аналого-цифрового преобразователя (АЦП), модуль формирования статических координат графоаналитического растра (МФСКГАР), блок видеоконтроля (БВ), импульсный регулятор (ИР) и модуль формирования динамической развертки графоаналитического растра (МФДРГАР), первый и второй информационные входы/выходы которого соединены соответственно с управляющими входами модуля коммутации и аналого-цифрового преобразователя, а третий, четвертый, пятый, шестой, седьмой и восьмой - с вторым, третьим, четвертым, пятым, шестым и седьмым информационными входами/выходами МФСКГАР, при этом второй вход блока видеоконтроля объединен с седьмым информационным входом/выходом МФСКГАР и восьмым информационным входом/выходом МФДРГАР.

Блок видеоконтроля (БВ) содержит модуль регистратора (МР), на выходе которого установлены маска, оптическая система и преобразователь оптического сигнала, выходом подключенный к управляющему входу блока динамической развертки.

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

Маска изготовлена так, что в пространстве ее координат (X, Y, Z) выделены области уязвимости ИК ПО и соответствующие значения могут быть определены на основе оценки степени уязвимости ИК ПО ВРК.

В качестве оценки степени уязвимости ИК ПО ВРК могут быть использованы значения энтропии состояния верифицируемого ИК ПО.

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

Предлагаемое изобретение поясняется чертежами.

На фиг.1 приведена структура интерактивного программируемого устройства (ИПУ) для систем верификации программного обеспечения распределенных вычислительных комплексов (СВПО РВК), содержащая аппаратно-программный блок (АПБ) лексического и семантического анализа/разбора (АПБ-А), АПБ преобразования кода (АПБ-В), АПБ анализа кода (АПБ-С), АПБ процессорного управления (АПБ-У), видеоадаптер, интерфейсы жестких, гибких и оптических дисков, интерфейс последовательного порта, сетевой интерфейс и системную память, которые объединены системной шиной, при этом системная память содержит постоянное запоминающее устройство (ROM) и оперативное запоминающее устройство (RAM/ОЗУ), в ячейках оперативной памяти и жестких дисков размещают/записывают операционные системы, прикладные программы, базы данных и базы знаний, которые содержат листинги исходных программ (D1), грамматику языка программирования (D2) (например, грамматику языка программирования Си), правила преобразования дерева разбора листинга программы (D3), дерево разбора листинга программы (D4), таблицу типов языка программирования (D5), аннотации внешних функций, включающие их грамматику и семантику (D6), код программ на языке внутреннего представления (D7), условия корректности языка внутреннего представления исходного кода программы (D8), условия проверки корректности подозрительных точек исходного кода программы (D9), информационную базу (D10), содержащую системы ограничений в виде алгебраических уравнений и неравенств, отчеты об обнаруженных уязвимостях программного кода (D11), включающие:

указание на местоположение возможной уязвимости в исходном коде программы, которое содержит имя файла листинга программы, номер строки и номер позиции в строке программы, в котором возможно переполнение буфера запоминающего устройства, контекст исходной программы, содержащий возможное переполнение (некоторую ”окрестность” потенциально опасной точки переполнения буфера запоминающего устройства);

указание причины переполнения буфера запоминающего устройства - значения исходных переменных, приводящих к возникновению уязвимости исходного кода программного обеспечения;

показатель или степень критичности обнаруженной уязвимости исходного кода программного обеспечения;

указание на перечень правил или алгоритмов для устранения уязвимости исходного кода программного обеспечения.

На фиг.2 приведен пример реализации аппаратно-программного блока (АПБ) лексического и семантического анализа/разбора (АПБ - А), в котором приняты следующие обозначения:

Обозначение	Описание
D1	База данных, содержащая листинги исходных программ (D1): набор файлов с исходными текстами (листингами) анализируемой программы
Вход 1: чтение файлов листингов программ
D2	База данных, содержащая грамматику языка программирования (D2): грамматика языка (правила лексического и синтаксического разбора)
Вход 1: чтение правил грамматики языка
D3	База знаний, содержащая правила преобразования дерева разбора листинга программы (D3): правила преобразования дерева
Вход 1: чтение правил преобразования дерева разбора
D4	База данных дерева разбора листинга программы (D4): дерево разбора после выполнения части А
Вход 1: сохранение дерева разбора
D5	База данных, содержащая таблицу типов языка программирования (D5): таблица типов после работы АПБ-А
Вход 1: сохранение таблицы типов
A.1	Блок проверки условия: остались ли листинги программ для разбора?
Выход 1: переход в случае истинности условия
Выход 2: переход в случае ложности условия
А.2	Вызов процедуры PARSE FILE аппаратно-программного модуля А1 ”Лексический и синтаксический разбор” для разбора очередного листинга программы. Работа данного модуля раскрыта на схеме, изображенной на фиг.3.
	Вход 1: прием управляющего сигнала
Выход 1: обращение на чтение к данным - файлам листингов программ
Выход 2: обращение на чтение к данным - грамматике языка программирования
Выход 3: обращение на запись к данным - дереву разбора листингов программ после выполнения модуля А1
Выход 4: обращение на запись к данным - таблице типов А.5 после выполнения модуля А1
Выход 5: передача управления и полученных результатов (дерево разбора и таблица типов) в следующий этап обработки А.3.
А.3	Вызов процедуры SIMPLIFY SYNTAX TREE аппаратно-программного модуля А2 ”Преобразование дерева разбора листингов программ к виду, пригодному для перевода во внутреннее представление” для обработки результатов выполнения результатов работы этапа А.2. Пример реализации процедуры SIMPLIFY SYNTAX TREE аппаратно-программного модуля А2 раскрыт на фиг.4.
Вход 1: передача управления и получение результатов выполнения процедуры PARSE FILE аппаратно-программного модуля А1
Выход 1: передача управления на вход А.1
Выход 2: обращение на чтение к данным - дереву разбора после выполнения аппаратно-программного модуля А1
Выход 3: обращение на чтение к данным - таблице типов после выполнения аппаратно-программного модуля А1
Выход 4: обращение на запись к данным - дереву разбора после выполнения - модуля А2
Выход 5: обращение на запись к данным - таблице типов после выполнения - модуля А2
Выход 6: обращение на чтение к базе данных D3
А.4	Данные - дерево разбора листингов программ после выполнения моду ля А 1.
Вход 1: обращение из модуля А1
Вход 2: обращение из модуля А2
А.5	Данные - таблица типов после выполнения модуля А1.
Вход 1: обращение из модуля А1
Вход 2: обращение из модуля А2
А.6	Данные - дерево разбора листингов программ после выполнения модуля А2.
Вход 1: обращение из модуля А2
Вход 2: обращение из модуля A3
А.7	Данные - таблица типов после выполнения аппаратно-программного
	модуля А2.
Вход 1: обращение из модуля А2
Вход 2: обращение из модуля A3
А.8	Вызов процедуры MERGE SYNTAX TREES аппаратно-программного модуля A3 ”Поддержка многофайловых проектов”. Пример реализации модуля A3 раскрыт на фиг.7.
Выход 1: передача управления
Выход 2: обращение на чтение к данным - дереву разбора после выполнения модуля А2
Выход 3: обращение на чтение к данным - таблице типов после выполнения модуля А2
Выход 4: сохранение итоговой таблицы типов
Выход 5: сохранение итогового дерева разбора

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

На фиг.3-7 приведены примеры реализации основных модулей АПБ-А.

На фиг.3 приведен пример реализации модуля А1 АПБ-А. Аппаратно программный модуль А1 обеспечивает режим ”лексического и синтаксического разбора исходных текстов программ”, перечень принятых обозначений имеет следующий вид:

Обозначение	Описание
А1.1	Разбиение исходного файла программы на поток лексем
Вход 1: прием управляющего сигнала
Выход 1: обращение на чтение к базе данных D1, содержащей листинги исходных программ
Выход 2: обращение на чтение к базе данных D2, содержащей грамматику языка программирования
Выход 3: передача управления
А1.2	Инициализация стека ОЗУ, после этой операции стек пуст
А1.3	Проверка условия: остались непрочитанные лексемы в потоке лексем?
	Выход 1: передача управления в случае, когда остались лексемы
Выход 2: передача управления в случае, когда весть поток лексем
уже обработан
А1.4	Извлечение лексемы из потока и помещение ее на вершину стека ОЗУ
А1.5	Инициация чтения синтаксических правил грамматики языка программирования, начиная с первого правила
А1.6	Проверка условия: остались непрочитанные синтаксические правила?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А1.7	Получение следующего синтаксического правила
Выход 1: передача сигнала управления
Выход 2: обращение на чтение к данным - грамматике языка
А1.8	Проверка условия: возможно ли применение правила к последовательности элементов на вершине стека?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А1.9	Замена последовательности элементов на вершине стека, подходящей под правило, на поддерево разбора, соответствующее правилу
А1.10	Проверка условия: синтаксическое правило соответствует введению нового типа?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
A1.11	Добавление записи в таблицу типов
Выход 1: передача управления
Выход 2: обращение на запись к данным - таблице типов после выполнения модуля А1.
A1.12	Проверка условия: в стеке ровно один элемент, соответствующий дереву разбора исходного текста?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
A1.13	Извлечение дерева разбора из стека
Выход 1: обращение на запись к данным - дереву разбора после выполнения модуля А1
Выход 2: передача управляющего сигнала

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

На фиг.4 приведен пример реализации модуля А2 АПБ-А. Аппаратно программный модуль А2 обеспечивает режим ”преобразования дерева разбора кода программы к виду, пригодному для перевода его во внутреннее представление”, перечень принятых обозначений имеет следующий вид:

Обозначение	Описание
А2.1	Вызов процедуры MARK SCOPES модуля А2 для корневой вершины дерева разбора. Пример реализации данной процедуры приведен на фиг.5.
Вход 1: прием управляющего сигнала
Выход 1: передача управления и результатов выполнения
Выход 2: обращение на чтение к данным - дереву разбора после выполнения модуля А1
Выход 3: обращение на чтение к данным - таблице типов после выполнения модуля А1
А2.2	Инициация обхода детей корневой вершины дерева разбора начиная с первой вершины-ребенка
А2.3	Условие: остались дети корневой вершины с типом ”определение функции”?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А2.4	Найти все объявления в поддереве, соответствующем телу функции, и переместить их таким образом, что они станут детьми текущей вершины с типом ”определение функции”
А2.5	Переход к обработке следующей вершины-ребенка корневой вершины
А2.6	Вызов процедуры TRANSFORM SYNTAX TREE модуля А2, раскрываемой на фиг.6.
Вход 1: передача управления
Выход 1: передача управления
Выход 2: обращение на чтение к данным - правилам преобразования дерева
Выход 3: обращение на запись к данным - дереву разбора после выполнения модуля А2
	Выход 4: обращение на запись к данным - таблице типов после выполнения модуля А2

Модуль А2 представляет процедуру ”SIMPLIFY SYNTAX TREE”, производящую надлежащее упрощение дерева разбора, результатом которого является дерево разбора и таблица типов, преобразование которых ко внутреннему представлению значительно проще по сравнению с преобразованием ”сырого” дерева разбора.

Схема процедуры ”SIMPLIFY SYNTAX TREE” представлена на фиг.4. В работе процедуры используются две внутренние рекурсивные процедуры ”MARK SCOPES” и ”TRANSFORM SYNTAX TREE”, осуществляющие, соответственно, пометку областей видимости объявлений и определений в дереве разбора и преобразование дерева разбора по заранее заданному набору правил.

На фиг.5 приведен пример реализации рекурсивной процедуры А2.1. ”MARK SCOPES”, при этом приняты следующие обозначения:

Обозначение	Описание
А2.1.1	Синтез дерева разбора и таблицы типов
Вход: прием управляющего сигнала
Выход 1: передача управления
Выход 2: обращение на чтение к данным - дереву разбора после выполнения модуля А1
Выход 3: обращение на чтение к данным - таблице типов после выполнения модуля А1
А2.1.2	Выбор: тип вершины?
Выход 1: передача управления в случае, если вершина имеет тип ”блочная инструкция” или ”определение функции”
Выход 2: передача управления в других случаях
А2.1.3	Добавление к вершине атрибута ”область видимости (scope)” с уникальным значением
А2.1.4	Все идентификаторы объявляемых переменных, находящиеся в поддереве обрабатываемой вершины, пометить атрибутом ”область видимости” с полученным значением на предшествующем шаге
А2.1.5	Инициализация обработки ”детей вершины” начиная с первой вершины - ”ребенка”
А2.1.6	Проверка условия: остались необработанные ”дети вершины”?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А2.1.7	Рекурсивный вызов процедуры MARK SCOPES модуля A3
Вход 1: прием сигнала управления
Выход 1: передача управления
Выход 2: обращение на чтение к данным - дереву разбора после выполнения модуля А1
Выход 3: обращение на чтение к данным - таблице типов после выполнения модуля А1

На фиг.6 приведен пример реализации рекурсивной процедуры А2.6. ”TRANSFORM SYNTAX TREE”, при этом приняты следующие обозначения:

Обозначение	Описание
А2.6.1	Инициализация обработки ”детей” корневой вершины дерева начиная с первой вершины - ”ребенка”
А2.6.2	Проверка условия: остались необработанные дети вершины? Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А2.6.3	Рекурсивный вызов процедуры TRANSFORM SYNTAX TREE модуля А2 для поддерева очередного ребенка обрабатываемой вершины
Вход 1: прием сигнала управления
Выход 1: передача сигнала управления
Выход 2: обращение на чтение к данным - правилам преобразования дерева
Выход 3: обращение на запись к данным - дереву разбора после выполнения модуля А2
Выход 4: обращение на запись к данным - таблице типов после выполнения модуля А2
А2.6.4	Сохранение полученного дерева разбора для вершины
Выход 1: передача управления
Выход 2: обращение на запись к данным - массиву результатов преобразования для детей вершины
А2.6.5	Инициализация процесса чтения правил преобразования дерева разбора, начиная с первого правила
А2.6.6	Проверка условия: остались непрочитанные правила преобразования?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А2.6.7	Прочесть очередное правило преобразования в D3
Выход 1: передача управления
Выход 2: обращение на чтение к данным - правилам преобразования дерева в D3
А2.6.8	Проверка условия: правило преобразования применимо?
Выход 1: передача управления в случае истинности условия
Выход 2: передача управления в случае ложности условия
А2.6.9	Формирования в ОЗУ временных данных: временный массив результатов - деревьев разбора для ”детей” обрабатываемой вершины
А2.6.10	Применение правила преобразования дерева к текущей вершине и набору деревьев разбора, хранимых во временном массиве результатов
Вход 1: прием сигнала управления
Выход 1: передача сигнала управления
Выход 2: обращение на чтение к данным - массиву результатов преобразования для ”детей” вершины
Выход 3: обращение на запись к данным - дереву разбора после выполнения модуля А2
Выход 4: обращение на запись к данным - таблице типов после выполнения модуля А2

На вход процедуры TRANSFORM SYNTAX TREE поступает дерево (или поддерево) разбора, на выходе получается результирующее преобразованное дерево разбора. Внутри процедуры происходит рекурсивный вызов этой процедуры и сохранение результатов (дерева разбора) выполнения этого вызова во временном массиве результатов, который размещается в ОЗУ.

При этом оригинальность предлагаемого способа трансформации или преобразования дерева в процессе верификации/разбора исходного листинга программы состоит в том, что если дерево с указанной вершиной соответствует определению и содержит внутри себя спецификатор ”extern”, то такое дерево удаляется, кроме этого, если дерево соответствует блочной инструкции, то каждое поддерево блочной инструкции с вершиной в ”ребенке” обрабатываемой вершины заменяется на список поддеревьев, соответствующих инструкциям в этой блочной инструкции.

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

Обозначения	Описание
А3.1	Инициализация результирующего дерева разбора и таблицы типов
A3.2	Проверка условия: остались деревья разбора для компоновки?
Выход 1: передача сигнала управления в случае истинности условия
Выход 2: передача сигнала управления в случае ложности условия
А3.3	Получение очередного дерева разбора
Выход 1: передача сигнала управления
Выход 2: обращение на чтение к данным - набору деревьев разбора после выполнения модуля А2
A3.4	Проверка условия: остались необработанные дети корневой вершины?
Выход 1: передача сигнала управления в случае истинности условия
Выход 2: передача сигнала управления в случае ложности условия
A3.5	Добавить поддерево, в котором корневой вершиной является очередной ”ребенок”, в результирующее дерево разбора таким образом, что корневая вершина добавляемого дерева окажется ”ребенком” корневой вершины результирующего дерева
Выход 1: передача сигнала управления
Выход 2: обращение на запись к данным D4 - дереву разбора после выполнения части А
А3.6	Проверка условия: остались таблицы типов для компоновки?
Выход 1: передача сигнала управления в случае истинности условия
Выход 2: передача сигнала управления в случае ложности условия
А3.7	Получение очередной таблицы типов
Выход 1: передача сигнала управления
Выход 2: обращение на чтение к данным - набору таблиц типов после
	выполнения модуля А2
А3.8	Добавление всех элементов из таблицы типов в результирующую таблицу типов
Выход 1: передача сигнала управления
Выход 2: обращение на запись к данным - таблице типов после выполнения части А

На фиг.8 приведен пример реализации аппаратно-программного блока (АПБ) преобразования кода (АПБ-В), обеспечивающего преобразование дерева разбора исходной программы к внутреннему представлению, при этом приняты следующие обозначения:

Обозначение	Описание
В1	Обращение к аппаратно-программному модулю В1 ”Встраивание функций”. Работа данного модуля раскрыта на схеме, изображенной на фиг.9.
Вход 1: прием сигнала управления
Выход 1: передача сигнала управления
Выход 2: обращение к базе данных D4 дерева разбора листинга программы
В2	Обращение к аппаратно-программному модулю В2 ”Разворачивания структур”. Работа данного модуля раскрыта на схеме, изображенной на фиг.11.
Вход 1: прием сигнала управления
Выход 1: передача сигнала управления
Выход 2: обращение к базе данных D5 таблиц типов языка программирования
В3	Обращение к аппаратно-программному модулю В3 ”Разворачивания выражений”. Работа данного модуля раскрыта на схеме, изображенной на фиг.12.
Вход 1; прием сигнала управления
Выход 1: передача сигнала управления
В4	Обращение к аппаратно-программному модулю В4 ”Преобразования к внутреннему представлению”. Работа данного модуля раскрыта на схеме, изображенной на фиг.13.
Вход 1: прием сигнала управления
	Выход 1: передача сигнала управления
Выход 2: сохранение в базе данных D7 программы на языке внутреннего представления
Выход 3: сохранение базы условий корректности в базе данных D8
Выход 4: сохранение базы соответствия условий корректности подозрительным точкам исходного кода в базе данных D9
Выход 5: обращение к базе знаний D6 аннотаций внешних функций
D4	База данных D4 дерева разбора листинга программы
Вход 2: обращение к дереву разбора листинга программы
D5	База данных D5 таблиц типов языка программирования
Вход 2: обращение к дереву разбора листинга программы
D6	База знаний D6 аннотаций внешних функций
Вход 1: обращение к базе аннотаций
D7	База данных D7 программ на языке внутреннего представления
Вход 1: сохранение программы на языке внутреннего представления
D8	Базы данных D8 условий корректности языка внутреннего представления исходного кода программы
Вход 1: сохранение базы условий корректности
D9	База знаний D9 условий проверки корректности подозрительных точек исходного кода программы
Вход 1: сохранение базы соответствия условий корректности подозрительным точкам исходного кода

На фиг.9 приведен пример реализации модуля В1 АПБ-В. Аппаратно программный модуль В1 (встраивание функций) обеспечивает режим модифицирования дерева разбора, которое находится в базе данных D4. Перечень принятых обозначений имеет следующий вид:

Обозначение	Описание
В1.1	Проверка условия: есть ли необработанные локальные переменные.
Выход 1: да
Выход 2: нет
Выход 3: обращение к дереву разбора программы
В1.2	Убрать вершину, помеченную как объявление переменной х, из детей вершины, помеченной как объявление функции f, добавить к дереву вершину, помеченную как объявление переменной x@f.
В1.3	Для всех потомков вершины-ребенка функции f, которые помечены
Обозначение	Описание
В1.4	как идентификаторы х заменить их на идентификаторы x@f.Вызов процедуры UF (разворачивание функций) для дерева разбора с выделенной вершиной, соответствующей функции main.
D4	Вход 1: прием сигнала управления
Выход 1: передача сигнала управления
База данных дерева разбора листинга программы программы
Вход 2: обращение к дереву разбора программы

На фиг.10 приведен пример реализации процедуры разворачивания функций (Unwinding Functions - UF). На вход процедуры подается дерево разбора с выделенной вершиной, соответствующей некоторой функции, на выходе получается дерево разбора. На фиг.10 приняты следующие обозначения:

Обозначение	Описание
UF.1	Добавить в стек (ОЗУ) вызовов имя вызываемой функции.
UF.2	Проверить условие: есть ли необработанные вызовы ф