автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Методы построения графо-аналитических моделей функциональных программ

На правах рукописи

Лаздин Артур Вячеславович

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

Специальность - 05.13.12 "Системы автоматизации проектирования" (приборостроение)

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Санкт-Петербург 2009

003474431

Работа выполнена в Санкт-Петербургском Государственном университете информационных технологий, механики и оптики.

Научный руководитель доктор технических наук, профессор

Немолочнов Олег Фомич

Официальные оппоненты

доктор технических наук, профессор Арустамов Сергей Аркадьевич

кандидат технических наук Яковлев Юрий Александрович

Ведущее предприятие СПб ГЭУ «ЛЭТИ» им. В. И. Ульянова

(Ленина)

Защита диссертации состоится 16 июня 2009 г. в 15 часов 50минут на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49.

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

Автореферат разослан 15 мая 2009 г.

Учёный секретарь

диссертационного совета Д 212.227.05

В.ИЛоляков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Цель работа: создание методов построения графо-аналитических моделей программ в части декомпозиции управляющего графа исполняемого кода программы; разработка машинно-ориентированных алгоритмов формирования и представления в памяти ЭВМ этого графа. В соответствии с поставленной целью необходимо решить следующие основные задачи:

• разработать модель исполняемого кода функциональной программы;

• разработать метод формирования управляющего графа функциональной про1раммы на основе ее модели;

• разработать методы процедурной и структурной декомпозиции управляющего графа функциональной программы;

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

Научная новизна. В работе получены следующие существенные результаты:

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

• разработан метод процедурной декомпозиции управляющего графа исполняемого кода функциональной программы;

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

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

Внедрение результатов. Разработанная программная система формирования и декомпозиции управляющего графа функциональной программы используется в СПбГУ ИТМО на кафедре информатики и прикладной математики в рамках учебно-исследовательской САПР верификации и тестирования, для анализа результатов лабораторных работ по курсам «Системное программное обеспечение», «Программирование на языке ассемблера», «Технология программирования» для студентов специальности 230101 «Вычислительные машины, системы, комплексы и сети».

Апробация работы Основные результаты диссертационной работы докладывались и получили одобрение на Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств» (Орел, 1999), научно-технических конференциях профессорско-преподавательского состава ИТМО (С.-Петербург 1999, 2000, 2002, 2003 г.г.).

Публикации. По материалам диссертации опубликовано 10 работ.

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 82 наименований и приложения. Общий объем работы 142 страницы текста, диссертация содержит 2) рисунок и 9 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, определены цели и методы исследования.

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

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

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

• синтаксический контроль;

• контроль структурированности ПО;

• контроль правдоподобия программ;

• верификация ПО.

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

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

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

• функциональное тестирование; » структурное тестирование.

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

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

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

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

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

управления последовательностью исполнения (безусловные и условные переходы, команды вызова процедур и команды возврата). С точки зрения выполнения программы, действия процессора по обработке последовательности команд обработки данных - линейный участок -строго детерминированы: команды выполняются одна за другой. Для линейной программы в этом смысле можно выделить всего два состояния: точку запуска и точку останова. Другими словами можно сказать, что любой линейный участок Ж выполняется либо до точки останова программы либо до команды управления последовательностью команд (КУПК). -

При построении программы определяется точка входа - адрес первой выполняемой команды. Выход из ФП (завершение работы) может быть реализован произвольным количеством олераторов возврата, вызовов функций схц(), аЬоП(), использованием механизма исключительных ситуаций. Таким образом, можно говорить о некотором множестве точек выхода из программы.

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

ФП представляется ориентированным графом, вершинами которого будут:

• точка входа в ФП;

• множество точек выхода;

• команды передачи управления не являющиеся

элементами множества точек выхода.

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

Дугам этого графа соответствуют:

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

• безусловные переходы;

• условные переходы.

Дугам, соответствующим безусловным или условным переходам не соответствует ни одна выполняемая команда обработки данных. Особенностью дуг, связанных с условными переходами является то, что

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

Рис. 1. Типы и инцидентности вершин управляющего графа ФП.

На рис. 1. показаны возможные инцидентности вершин УГ ФП в зависимости от их функциональной принадлежности. Очевидно, что вершина, соответствующая точке входа (Твх) инцидентна единственной исходящей из нее дуге. Вершина, соответствующая одной из возможных точек выхода из программы (Твых) может быть инцидентна только входящим дугам. Вершины, соответствующие командам вызова процедур (САЬЪ) и безусловных переходов (1МР) инцидентны единственной исходящей дуге, причем типы этих дуг, в общем случае, отличны. Вершина, соответствующая командам условных переходов (.Гхх) инцидентна строго двум исходящим дугам. Для всех вершин, кроме соответствующей точке входа, допускается множественная инцидентность относительно входных дуг.

Для вершин, соответствующим командам вызова процедур и возврата из них, возможны два подхода интерпретации:

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

Линейный участок программы

— ►

Безусловный или условный переход

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

Рис. 2 Метод формирования управляющего графа ФП.

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

Граф ФП не может содержать петель и параллельных дуг

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

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

В диссертационной работе предложен рекурсивный алгоритм формирования списка КУПК по ИК ФП. В качестве параметров алгоритм получает адрес начала обработки и конечный адрес просмотра (для первого запуска алгоритма он принимает значение адреса последнего байта программы). Возвращаемое значение (адрес перехода, если Ар < AN, или адрес начала обработки в противном случае) заносится в переменную, хранящую An. Данный алгоритм может быть представлен следующим образом:

P(An,Ak) - if (4> < ¿n) then 4>[S; P(AP, AN)}, где (1)

Р - процедура формирования списка вершин графа;

Ац - адрес начала обработки (для первого вызова функции - адрес точки входа.);

Ак - конечный адрес просмотра;

Ар - адрес перехода;

Ч*- композиция базовых операторов 5 (операторы формирования списка вершин, не содержащие обращения к процедуре Р) и процедуры Р.

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

Для доказательства конечной глубины рекурсии введем функцию/(х), где х - множество переменных процедуры, такую, что при/00 < 0 алгоритм не осуществляет рекурсивного вызова. Определим х следующим образом: х = {ап, ар, апг}, где ст, ар, и апг - переменные, хранящие значения начального адреса Ан, адреса перехода АР и адреса начала загрузки программы. Тогда функция /(х) задается следующим соотношением:

ап-ар, если ап > ар]

/(х) = <! -1, если ар < апг', (2)

I, в противном случае.

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

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

Справедливость данной леммы основана на том, что любую линейную последовательность функциональных операторов можно объединить в составной оператор (блок) без потери семантики. Будем называть схему алгоритма нормализованной, если в ней любая композиция операторов представлена одной функциональной вершиной в соответствии с леммой. Доказывается теорема, в соответствии с которой сложность графа функциональной программы имеет тот же порядок, что и сложность нормализованной схемы исходного алгоритма описания задачи. Следовательно, можно говорить об «обозримости» УГ ФП, а равно о возможности его последующей программной обработки, например для автоматизации формирования тестов в соответствии с методом структурного тестирования ПО.

В третьей главе описываются предложенные методы структурной декомпозиции УГ ФП. В работе определены структурные части функциональной программы: процедуры и циклы, подлежащие декомпозиции, обоснована последовательность декомпозиции, определены цели декомпозиции. На первом этапе выделяются тела процедур, на втором этапе — тела циклоз.

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

В отличие от Ассемблера большинство современных языков программирования (С++, Си, Паскаль, Фортран) существенно ограничивают способы передачи управления к процедурам и выходам из них.

В данной работе под процедурой будет пониматься группа команд, предназначенная для решения локальной задачи, имеющая единственную точку входа, передача управления на которую может осуществляться только посредством выполнения команд вызова; выход из процедур осуществляется выполнением команд возврата. Другие способы входа и выхода из процедур запрещены. Наложенные ограничения позволяют существенно упростить поиск процедур оформленных по правилам, принятым в языках высокого уровня или с использованием директивы РКОС в языке Ассемблера. Для процедур выполняются соглашения о типе вызова и типе возврата: ближнему вызову соответствует ближний возврат, а дальнему - дальний. Команда возврата не обязательно должна быть последней в последовательности машинных инструкций процедуры, однако очевидно, что последней командой процедуры может быть либо команда возврата, либо команда передачи управления на инструкцию в теле процедуры. Если в коде программы будут находиться процедуры не соответствующие наложенным ограничениям, они будут рассматриваться как часть головной процедуры или функции( подобно функции тат() Си-программы). Для процедур, вход в которые был выполнен командой вызова, недопустимы переходы из тела процедуры.

В диссертационной работе были проанализированы возможные структуры процедур и на основе проведенного анализа предложен метод функциональной декомпозиции ЯК ФП предназначенный для выделения тел процедур. Метод разделен на два основных этапа: на первом этапе в списке узлов производится поиск всех обращений к процедурам, и несовпадающие адреса вызовов помешаются в список начальных адресов процедур. На втором этапе для каждого начального адреса производится поиск адреса последней команды процедуры для ее последующей локализации в рамках УГ ФП. В ходе формирования УГ для каждой процедуры локализуются найденные ошибки.

С целью поиска циклических участков ИК ФП и последующей ее структурной декомпозиции в диссертационной работы были проанализированы структуры циклических участков программ с учетом досрочных выходов из циклического участка (Ьгеак-ветви) и переходов к началу очередной итерации цикла (сопЬ'пие-ветви). Предложен метод поиска циклических участков программы с учетом вложенности циклов.

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

Необходимо наложить ограничения на структуры циклов подобно тому, как это было сделано для процедур. Запрещаются переходы из тела цикла к вершинам УГ ФП не принадлежащим телу цикла, как в направлении младших, так и старших адресов. Появление подобных переходов может быть вызвано неоправданным, для метода структурного программирования, использованием операторов goto. Подобное ограничение не влияет на такие широко распространенные приемы выхода из циклов, как принудительное прекращение итерации (continue-вегвь) в этом случае адрес перехода из тела цикла назад будет совпадать с адресом перехода для вершины перехода на очередную итерацию цикла. Запрещаются переходы в тело цикла из участков программы не принадлежащих циклическому участку.

Поиск циклов осуществляется в следующей последовательности -сначала составляется список адресов, вершин УГ ФП, из которых осуществляется переход назад (в направлении уменьшения адресов). Если найдено несколько переходов на один и тот же адрес, то вершина, имеющая самый старший адрес, рассматривается в качестве предполагаемого завершения цикла, а остальные - continue. Вершины, соответствующие continue-ветви удаляются из списка предполагаемых завершений циклов. Если есть переходы назад в тело предполагаемого цикла, то эти переходы, равно как и сам предполагаемый цикл, циклом не являются и удаляются из списка предполагаемых завершений циклов. Наличие подобных переходов lie согласуется с ранее определенными ограничениями. Затем определяется вложенность найденных циклов.

Предложенные в диссертационной работе методы функциональной декомпозиции позволяют существенно упростить представление и обработку УГ ФП.

В четвертой главе диссертационной работы приводится описание программной системы формирования УГ ФП. Система представляет собсЗ консольное приложение для ОС Windows NT/2000/XP и является программной реализацией разработанных в диссертационной рабоге алгоритмов. Разработана структура программной системы (см. рис. 3), описаны ее возможности. Дано описание состава модулей входящих в систему. В качестве объекта эксперимента выбрана ФП имеющая ИК в формате ехе-файла операционной системы MS-DOS, состоящий из команд процессора Pentium.

Программная система состоит из трех основных частей: зависимой от типа операционной системы, аппаратуры, для которых создана ФД и программно-аппаратно независимая. Первая часть включает в себя имитатор загрузчика, вторая - модули поиска команд управления потоком команд и дешифрации команда, а третья (независимая от типа аппаратуры и ОС) - модули формирования графа, его матричного представления и декомпозиции. Результатом работы первой части является независимый ни

от вида ОС, ни от типа процессора список вершин управляющего графа ИКФП.

В зависимости от указаний пользователя программная система формирует ряд файлов: неупорядоченный и упорядоченный списки КУПК, список вершин управляющего графа ИК ФП, матрицы смежности, инцидентности, достижимости, список, процедур, список циклов.

Рис. 3 Структура программной системы формирования и декомпозиции управляющего графа функциональной программы.

В приложении приведены примеры функциональных программ и результаты их обработки: полученные списки вершин УГ ФП, матрицы связности и инцидентности для полученных графов.

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

ЗАКЛЮЧЕНИЕ

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

2. Разработана модель представления исполняемого кода в виде ориентированного графа, вершинами которого являются команды управления последовательностью выполнения; и на ее основе предложен метод восстановления управляющего графа исполняемого кода программы.

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

4. Разработаны алгоритмы восстановления управляющего графа программы, в частности рекурсивный алгоритм формирования списка вершин отравляющего графа.

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

6. Разработана программная система восстановления и декомпозиции управляющего графа исполняемого кода программы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Лаздин А. В. Способы машинного представления графа переходов функциональной программы. // Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 с.94.

2. Лаздин А. В. Немолочнов О. Ф. Использование графа переходов функциональной программы для синтеза испытательных последовательностей. // Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 г. с. 94.

3. Лаздин А. В. Построение графа функциональной программы. Материалы Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств». Орел, 1999 с. 190.

4. Миндубаева Н. Н. Лаздин А. В. Поиск процедур по графу переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 26-31.

5. Логунова О. А. Лаздин А. В. Пухтеева Е. А. Рекурсивный • алгоритм формирования списка вершин графа переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 31-35,

6. Лаздин А. В. Немолочнов О, Ф. Функциональная программа как объект тестирования и верификации. Тез. докл. научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000 с. 6.

7. Лаздин А, В. Алгоритмы построения списка вершин графа программы. // Тез. докл. научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000. с. 7

8. Лаздин А. В., Немолочнов О. Ф. Оценка сложности графа функциональной программы / - Научно-технический вестник СПБ ГИТМО (ТУ). Выпуск 6. Информационные, вычислительные и управляющие системы // Гл. ред. В. Н. Васильев. СПб.: СПбГИТМО (ТУ), 2002.

9. Лаздин А. В., Немолочнов О. Ф. Метод построения графа функциональной программы для решения задач верификации и тестирования / - Научно-технический вестник СПБ ГИТМО (ТУ). Выпуск 6. Инфориационные, вычислительные и управляющие системы // Гл. ред. В. Н. Васильев. СПб.: СПб ГИТМО (ТУ), 2002.

10. Немолочнов О. Ф., Зыков А. Г., Лаздин А. В., Поляков В. И. Верификация в исследовательских, учебных и промышленных системах. // - Научно-технический вестник СПбГУ ИТМО. Выпуск 11. Актуальные проблемы анализа и синтеза сложных технических систем. Под ред. В. О. Никифорова. СПб: СПбГУ ИТМО, 2003, с. 146-151.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел.(812)233 4669 объем 1 п.л. Тираж 100 экз.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОДЫ КОНТРОЛЯ И АНАЛИЗА ПРОГРАММ.

1.1 Программа как объект исследования.

1.2 Методы контроля программ

1.2.1 Статический анализ программ

1.2.2 Динамический анализ программ. 18 1 2.3 Другие методы анализа

1.3 Место методов анализа в жизненном цикле ПО

1.4 Постановка задачи 38 Выводы

ГЛАВА 2. МЕТОД ВОССТАНОВЛЕНИЯ УПРАВЛЯЮЩЕГО ГРАФА

ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ ПО ЕЕ ИСПОЛНЯЕМОМУ КОДУ.

2.1 Формальные модели программ.

2.2 Типы и структуры исполняемых модулей.

2.2.1 Обобщенный формат команды процессора

2.2 2 Графовое представление исполняемого кода.

2.2.3. Графо-аналитическая модель исполняемого модуля.

2.3 Метод формирование управляющего графа функциональной программы.

2.4 Оценка степени сложности управляющего графа ФП. 67 Выводы

ГЛАВА 3. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ

УПРАВЛЯЮЩЕГО ГРАФА ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ.

3.1 Поиск процедур. Алгоритмы. 78 3.3. Поиск параметров процедур.

3.2 Поиск циклов. Алгоритмы.

3.4 Поиск параметров цикла.

3.5 Поиск инвариант цикла.

Выводы

ГЛАВА 4. ПРОГРАММНАЯ СИСТЕМА ВОССТАНОВЛЕНИЯ УПРАВЛЯЮЩЕГО

ГРАФА ФУНКЦИОНАЛЬНОЙ ПРОГРАММЫ.

4.1 Общая структура программной системы.

4.2 Модуль имитатора загрузчика.

4.3 Модули дешифрации и поиска КУПК

4.5 Модуль формирования и сортировки списка вершин

4.6 Модули поиска процедур и циклов

4.6 Модуль формирования матриц

4.7 Методика работы с программной системой

4 7 1 Чтение данных из заголовка исполняемого модуля.

4 7.2 Запись в файл дампа ИМ.

4.7.3 Дизассемблирование команд ИМ.

4.7.4 Формирование и сортировка предварительного списка вершин 117 4.7.5. Поиск адресов начала и конца всех процедур ИМ.

4.7.6 Поиск адресов начала и конца всех циклов ИМ и определение их вложенности.

4.7.7 Запуск программной системы 120 Выводы

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

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

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

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

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

Цель работы: создание методов построения графо-аналитических моделей программ в части декомпозиции управляющего графа исполняемого кода программы; разработка машинно-ориентированных алгоритмов формирования и представления в памяти ЭВМ этого графа. В соответствии с поставленной целью необходимо решить следующие основные задачи:

• разработать модель исполняемого кода функциональной программы;

• разработать метод формирования управляющего графа функциональной программы на основе ее модели;

• разработать методы процедурной и структурной декомпозиции управляющего графа функциональной программы;

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

Научная новизна. В работе получены следующие существенные результаты:

• разработан метод восстановления управляющего графа исполняемого кода функциональной программы, базирующийся на оригинальном представлении его вершин и дуг;

• разработан метод процедурной декомпозиции управляющего графа исполняемого кода функциональной программы;

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

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

Внедрение результатов. Разработанная программная система формирования и декомпозиции управляющего графа функциональной программы используется в СПбГУ ИТМО на кафедре информатики и прикладной математики в рамках учебно-исследовательской САПР верификации и тестирования для анализа результатов лабораторных работ по курсам «Системное программное обеспечение», «Программирование на языке ассемблер», «Технология программирования» для студентов специальности 230101 «Вычислительные машины, системы, комплексы и сети».

Апробация работы Основные результаты диссертационной работы докладывались и получили одобрение на Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств» (Орел, 1999), научно-технических конференциях профессорско-преподавательского состава ИТМО (С.-Петербург 1999, 2000, 2002, 2003 г.г.).

Публикации. По материалам диссертации опубликовано 10 работ.

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 72 наименований содержит 142 страниц текста, 21 рисунок и 9 таблиц.

Выводы.

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

2. Рассмотрен и описан функциональный состав разработанной программной системы. Система реализована на алгоритмическом языке высокого уровня С++ и содержит более 3000 строк кода.

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

ЗАКЛЮЧЕНИЕ

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

2. Разработана графо-аналитическая модель представления исполняемого кода в виде ориентированного графа, вершинами которого являются команды управления последовательностью выполнения; и на ее основе предложен метод восстановления управляющего графа исполняемого кода программы.

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

4. Разработаны алгоритмы восстановления управляющего графа программы, в частности рекурсивный алгоритм формирования списка вершин управляющего графа.

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

6. Разработана программная система восстановления и декомпозиции управляющего графа исполняемого кода программы.

1. Абрамов. С.А. Элементы анализа программ. -М.: Наука. 1986. 128с.

2. Андерсон Р. Доказательство правильности программ. -М.: Мир. -1982,- 168с.

3. Баранов С.Н., Домарацкий А.Н., Ласточкин Н.К., Морозов В.П., Практическая модель процесса разработки программных изделий. //Программные продукты и системы. 1998. N 4. с. 7-14.

4. Баскерт Р. Саати Т. Конечные графы и сети. М.: Наука. 1974. 368с.

5. Бейбер JI.P. Программное обеспечение без ошибок. М. Радио и связь, 1996. 173 с.

6. Бромберг И.А. Система контроля этапов жизненного цикла ПО // Открытые системы. 1998. N6. с. 47-52.

7. Буч Г. Объектно-ориентированное проектирование с примерами применения. М.: Конкорд, 1992.

8. Бурдонов И.Б., Демаков А.В., Косачев А.С., Максимов А.В., Петренко А.К. Формальные спецификации в технологиях обратной инженерии и верификации программ // Труды Института системного программирования Российской Академии наук. N 1, 1999.

9. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ,- М.: Мир, 1985. 332 с.

10. Ю.Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем. М.: Финансы и статистика, 1998.176с.

11. П.Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. М.: Мир, 1985. 406с.

12. Воас Д. Качество ПО: восемь мифов // Открытые системы. 1999. N9-10.

13. Вьюкова Н.И., Галатенко В.А., Ходулев А.Б. Систематический подход к программированию. М.: Наука. Гл. ред. физ.-мат. лит., 1988. 208 с.

14. Н.Гацко Г. Тестирование ПО как один из элементов системы качества // Открытые системы. 1998. N6.

15. Григорьев B.JI. i486. Архитектура и программирование. М.: ГРАНАЛ, 1993.- 338 с.

16. Грис. Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. - 544с.

17. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир. 1981. 366с.

18. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. 275с.

19. Калинин СВ., Туренко Д.Л. Построение дерева вызовов в задаче анализа исполняемого кода API Win32 // Труды научной конференции по радиофизике ННГУ, 2001г. с.357,358

20. Котляров В.П. CASE-технология и возможности современных CASE-средств в поддержке этапов проектирования программного проекта // Сметем, информат. 1995. N4. С. 272-303.

21. Коул Дженнифер, Горэм Томас, МакДональд Марк, Спарджеон Роберт. Принципы тестирования ПО // Открытые системы (Изд-во "Открытые системы"). 1998. № 2.

22. Кузнецов Б.П. Структура и сложность модулей циклических программ // Автоматика и телемеханика. 1999. N2.2 8. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. 1995. N6. с. 33-40.

23. Лаздин А.В. Способы машинного представления графа переходов функциональной программы. / Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 с.94.

24. Лаздин А.В. Немолочнов О.Ф. Использование графа переходов функциональной программы для синтеза испытательных последовательностей. / Тез. докл. XXX научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 1999 г. с. 94.

25. Лаздин А.В. Построение графа функциональной программы. Материалы Всероссийской научно-технической конференции «Диагностика веществ, изделий и устройств». Орел, 1999 с. 190.

26. Лаздин А.В. Немолочнов О.Ф. Функциональная программа как объект тестирования и верификации. Тез. докл. научно-техническойконференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000 с. 6.

27. Лаздин А.В. Алгоритмы построения списка вершин графа программы. / Тез. докл. научно-технической конференции профессорско-преподавательского состава СПб ГИТМО (ТУ), 2000. с. 7.

28. Л аз дин А.В., Немолочнов О.Ф. Оценка сложности графа функциональной программы / Научно-технический вестник СПБ ГИТМО (ТУ). Выпуск 6. Инфориационные, вычислительные и управляющие системы / Гл. ред. В.Н. Васильев. СПб.: СПбГИТМО (ТУ), 2002.

29. Лаздин В.П., Лаздин А.В. Измерение температуры по ИК-излучению с автоматическим учетом коэффициента черноты объекта измерения. // Тепловые режимы и охлаждение радиоэлектронной аппаратуры. 1998. N 1. с.55-60.

30. Липаев В.В. Качество программного обеспечения. -М.: ФиС, 1983. -263с.

31. Липаев В.В. Отладка сложных программ. Методы, средства, технология. -М.: Энергратомиздат, 1993. -384 с.

32. Липаев В В. Надежность программных средств. М.: СИНТЕГ, 1998, - 232 с.

33. Липаев В.В. Управление разработкой программных средств: Методы, стандарты, технология. М.: Финансы и статистика, 1993.

34. Липаев В.В. Проектирование программных средств. М.: Высшая школа, 1990

35. Липаев В.В. Тестирование программ. М.: Радио и связь, 1986 296 с.

36. Логунова О.А. Лаздин А.В. Пухтеева Е.А. Рекурсивный алгоритм формирования списка вершин графа переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 31-35.

37. Майерс Г. Искусство тестирования программ. М.: Мир, 1982. 212с.

38. Матвеев В.А., Молотков С.В., Зегжда Д.П.,Мешков А.В., Семьянов П.В., Шведов Д.В.Основы верификационного анализа безопасности исполняемого кода программ.Под редакцией проф. Зегжды П.Д. СПб.: СПбГТУ, 1994. 58 с.

39. Международные стандарты, поддерживающие жизненный цикл программных средств. М.: МП "Экономика", 1996.

40. Мельников И.А., Раабе А.С., Тамм Б.Г. Инструментарий машинной поддержки цикла жизни программного обеспечения. Обзор западных средств//Прикладная информатика. 1988. Вып. 14. С. 16-40.

41. Миндубаева Н.Н. Лаздин А.В. Поиск процедур по графу переходов функциональной программы. Сборник научных трудов молодых ученых и специалистов СПб ГИТМО (ТУ), 2000 с. 26-31.

42. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ. М.: Радио и связь, 1988.

43. Никифоров В.В., Домарацкий Я.А. Системное тестирование программных изделий. // Программные продукты и системы. 1998. N 4. с. 40-46.51.0ре О. Теория графов. -М.: «Наука», 1968. 352с.

44. Основы верификационного анализа безопасности исполняемого кода программ. / Матвеев В.А., Молотков С.В., Зегжда Д.П.,Мешков А.В., Семьянов П.В., Шведов Д.В. Под редакцией проф. Зегжды П.Д. СПб.: СПбГТУ, 1994. 58с.

45. Отладка систем управляющих алгоритмов ЦВМ реального времени. Под ред. В.В. Липаева. М.: - РиС, 1974. - 326с.

46. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. М.: "ДИАЛОГ-МИФИ", 1994. 288 с.

47. Поттосин И.В. О критериях добротности программ //Системная информатика. Вып.6. Новосибирск: Наука, 1998.

48. Потосин И.В. «Хорошая программа»: попытка точного определения понятия. //Программирование. 1997. N2. с. 3-17.

49. Пратт Т. Языки программирования: разработка и реализация. М.: Мир, 1979.-472с.5 8. Промышленные контроллеры фирмы "Matsushita". Matsushita Automation Controls.

50. Романюк С.Г. Оценка надежности программного обеспечения. // Открытые системы. 1994. N4. с.24-28.

51. Семьянов П.В. Автоматизация поиска неизвестных разрушающих программных средств в исполняемом коде. // Всероссийская научно-техническая конференция «Методы и технические средства защиты информации», тезисы докладов, СПбГТУ, 1995.

52. Сингер М. Мини-ЭВМ PDP-11: программирование на языке ассемблера и организация машины. М.: Мир, 1984. 272 с.

53. Требования и спецификации в разработке программ. М.: Мир, 1984. 344 с.

54. Хьюз Д., Мичтом Д. Структурный подход к программированию. М.: Мир, 1980.-С. 29-71.

55. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

56. Alur R., Henzinger Т., Pei-Hsin Но. Automatic symbolic verification of embedded systems //IEEE Trans, on Software Eng. 1996. N3.

57. Bell C.G., Gray J. What's next in high-performance computing? // Communications of the ACM (CACM). 2002. Vol. 45. No.2. P. 91-95.

58. Bell D., Morrey I., Pogh J. Software Engineering. A programming Approach. Prentice Hall, 1992. 338p.

59. Corbett J.C. Evaluating deadlock detection methods for concurrent software //IEEE Trans, on Software Eng. 1996. N2.

60. Humphery G. Managing the Software Process. Reading: Addison-Wesley, 1989.-494p.

61. IA-32 Intel® Architecture Software Developer's Manual Volume 1 г Basic Architecture http://developer.intel.ru/design/pentium4/manuals/245470.htm

62. Lowry M Analytic Verification and Validation for Space Missions. NASA Ames Research Center http://is.arc.nasa.gov/AR/projects/AtnVrf.html

63. Revised version of DP9126 Criteria of the Evaluation of Software Quality Characteristics. ISO TC97/SC7 #610. - Part 6.1. ПРИЛЖЕНИЯ