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

»1 л р q 'q о

{g. i V йкадвккя imyic УкршсжжоЯ OOP

Ордзка Явншэ йистигуг trafispss'Mai шаки & U. ГЛТЕЕОЕА

■ i

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

ХЛДЖИШШИС Хрксантос Ставру

УДК 681.3.06(043)

ИЙСРМАЩИЕСШ СРЗДСХаА Д2П АНАША

н ошровозйкшя ОРОГШШОГО овгажчЕкня

05.25.05 - Автоматизированные информационные системы

Автореферат • диссертации на соискание ученой степени кандидата технических наук

Киев. 1988

Работа выполнена в Киевском институте инженеров гражданской авиации имени 60-летия СССР

Научные руководители: доктор технических наук, профессор НАГОРНЬЙ Л. Я кандидат физико-математических наук, доцент БЕЗРУКОВ Е Н

Официальные оппоненты: Доктор технических наук, профессор ДОЕГЯМО л.

кандидат технических наук, доцент ДВОРЦИН В. И.

Ведущее учреждение: Киевский ордена Ленина политехнический институт

Защита состоится "2£_ " ^игис^^ 1989 г. в 14 часов на заседании Специализированного совета К 016.45.05 по присуждению ученой степени кандидата технических наук при Институте кибернетики АН УССР по адресу 252207, Киев-207, проспект Академика Глушкова, 20.

С диссертацией можно ознакомиться в научно-техническом архиве института .

*

Автореферат разослан " алчете, 1989 г.

Ученый секретарь специализированного совета

РЕВЕНКО В. Л.

1 сщда мршщрмсш» работы

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

Работы по созданию Ш, позволяющих анализировать потек управ- <■ нйя и поток данных программ ведутся в основном в двух направде-ях: первое из них основаш на теоретико-графовой модели програм-I, а второе - на использовании средств специализированной СУБД.'

Сув^ствукиие ИС рассматриваемого класса ориентированы в ос-BHOtf на работу в среде операционных систем (ОС) больших вычисли-льных машин. Учитывая все более широкое внедрение - персональных М в практику проектно-конструкторских и научно-исследовательских бот, разработка новых ИС для этого класса машин, является особо туальной.

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

1. Исследовать основные направления создания эффективных ИС ализа потока управления и потока данных сложных ПК и провести итический анализ функциональных и сервисных возможностей этих ИС. 1

наметить пути их улучшения.

г. Разработать метод анализа управляющего графа программы, зволяюший исследовать, кроме классических . (-IF-THEH-ELSE, -WHILE, DO-UNTIL и т.д.), другие структуры управления, и создать его основе экспериментальную ИС анализа потока управления ПК.

3. Разработать экспериментальную ИС анализа потока данных эграммы, основанную на использовании средств специализированной БД.

Методы исследований и научная швиаиа. Для решения поста: ..:н-х задач используются теория гамаков, основные разделы теории афов и СУБД реляционного типа.

Нэвые научные результаты диссертационной работы ааг-яюч'-шгои эдующем:

1. Предложен метод декомпозиции управлящзго графа программы на гамаки - подграфы с одним входом и одним выходом, и на его рс-нове разработан анализатор логической структуры программы, позволяющий выявить в графе управления, кроме классических структур управления ( IF- THEN-ELSE, DO-WILE, DO-UNTIL и т.д.), другие типы структур управления, в частности кванты или простые гамаки.' Данный метод может также быть использован при разработке алгоритмов, ориентированных на параллельные вычислительные системы:----

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

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

Достоверность результатов подтверждена в ходе опытной эксплуатации разработанных авторам систем на ЭВМ типа IBM PC/XT и актам! внедрения.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались: на республиканском семинаре "Распараллеливание алгоритмов и построение вычислительных структур для моделирования сложных электронных схем и систем" (Киев, июнь 1988); на Х-ой отчетной научно-технической конференции профессорско-преподавательского состава КНИГА (Киев, апрель 1989); на городском семинаре "Системное программирование" (Киев, май 1989).

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

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

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

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

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

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

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

Наиболее важной составной часть» больсих ПК является база ^ данных. Выделены три основных подхода к созданию базы данных, содержащей сведения о программкой обеспечении:

- применение обычных текстовых файлов;

- применение промьшэнной СУЩ;

- применения специализированной СУБД.

Анализ функциональных и сервисных возможностей сущрстЕукилх в СССР и за рубексм ИС обработки Ш показал:

1) большинство из них ориентировано на работу в среде ОС больших ЗШ;

. 2) из-за попытки -охвата широкого спектра проблем эти МС становятся чрезмерно сложными, что ведет к потере эффективности их< применения при реоешга частных задач;

3) рассмотренные ИС ориентированы на обработку ОЭ, созданного на одном конкретном языке, что затрудняет, а иногда делает невозможным их применение для обработки программ на других языках.

Вторая глава посвядана созданию информационной системы, основанной на теоретико-графовой модели программ.

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

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

информацией через последовательные файлы. Исходным файлом для ана- . лиэатора является листинг ассемблерной программы микропроцессор* INTEL 8086/8083. Следует отметить, что анализатор, может бшь щ-ио ■

поставлен к анализу логики любого языка, например FORTRAN 4, или Си. Это достигается заменой модуля GRAPH86, осушэствляюадзго построение графа управления по протоколу трансляция программы. Вжодсм GRAPH86 является структура смежности орграфа. ЬЗоию использовать анализатор, задавая ка вход следующих фаз анализатора структуру смежности, построенную вручную. Указанная структура сдазш.ости является исходным файлом модулей построения деревьев upe- и пост-до— минирования - PREDTREE и POSTDTREE соответственно. Данные деревья имеют непосредственное отношение к гамакам, поскольку любой гашк имеет вход в дереве предошщирования и выход в дереве постдоминирования. Входная веряина гамака является предоминатором а выходная вершина - постдоминаюром всех вершш гамака Sato пре- и пост доминирования поступая? на вход модуля нахождения списков потенциальных гамаков - РОТНАМАК. Шлучевкда списки, поступает на вход модуля выделения реальных гамаша --QROLLIN, .работавдзго с помощью метода свертки. Последним модулем анализатора является классификатор типов гамаков, полученных на выходе модуля Q&CLLIN - CLASSIFY.

Модуль GRAPH86 предназначен для построения графа управления по протоколу трансляции ассемблера MASM КБ-COS (листинг). Для построения графа управления програкш распознается строки, содержащие типовые структуры управления, т.е. команды условного и безусловного переходов, команды циклов, а также метет. Бее остальные команды ассемблера, находящиеся маяду командами управления, не анализируются. Для представления графа в ЭВМ выбрана матрица смежности.

Модуль PREDTREE предназначен для построения дерева предокини-рования ориентированного графа, заданного с помощью структуры смежности. Дерево предошкирования предстазиет собой двумерный массив, у которого номера строк соответствуют номерам ворсин орграфа, а элементы строк— комэрам верняк, для которых номар строки является непосредственным йредзШЙаторои. Нулевые элементы какой-либо строки означают, что данная вершина не является предоми-натором какой-либо другой вершины.

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

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

Модуль РОЭТОТКЕЕ предназначен для построения дерева постдоми-пированиа орг{)а^а, заданного с пеыопгыо структуры смежности. Дерево с? поетдо'дюировашя представляет собой двунэраий массив, у которого номера строк соответствует номерам вершин орграфз, а элементы строк - номерам верзин, для которых вашр строга является непосредственным псстдонииатсрэм. Иулевыз элементы какой-либо строки озйачают, ч'го р-ерси;:а с ко?,юром строки не является постдоикиатором какой-либо другой верами.

Построение дерева■постдомиаировапия ссув;ествл;стен аналогично дереву предоылнироволйя. Здесь таклэ поочередно удаляется одна вершина га орграф и проверяется уставке досягаемости выходной вершины от оставвз&ся в орграфе вериги. Слисок вериин, недостигах>-пшх выходную вершину, и являемся искомой строкой дерева постдсыи-нирования первого этапа. В' этом случае поиск в глубину начинается с той вершиной, для которая осуг^гствляется проверка условия досягаемости.

ШДуль РОТНАК!АК предназначен для нахождения всех потенциальных гамаков орграфа программы по заданным деревьям пре- и пост доминирования. Становится очевидным, что количество потенциальных гамаков зависгст от того насколько этот узел находится ближе к корню дерева. На выходе этого модуля получаем два списга потенциальных гамаков (предоминирования и постдоманироваиия), которые поступают на вход модуля ОРШЛМ.

Для выделения .гамаков орграфу из списка потенциальных, используется метод свертки. Данный метод заключается в том, что в списках потенциальных гамаков выбирается простой гамак. Гамак свертывается в' одну вершину и процесс повторяется до тех пор, пока рассматриваемый орграф не упростится до двух вершин. Нумерация вершин, заменявидх свертываемый гамак, начинается с числа (М П, где N - максимальный номер вершины орграфа до текущей свертки. тенццальный гамак является реальным, если он имеет один вход и один выход. В данной реализации разрешается переход от вервины (фокуса) к входу гамака.

Структура смежности Y

from next other

1 2 3 4 - 2 3 А б 5

б 6 7 8 9 10 11 12 13 6 7 8 2 11 13 13 13 9 10 12 no) "(nV (J)

Список гамаков, найденных анализатором

Ко Вершны гамака фокус тип гамака

14 9, 11, 12 13 if-then-else

16 3,. 4, 5 6 if-then-else

16 15, 16 7 sequence

17 2, 16 7 sequence

18 17, 8, 10, 7, 14 13 undefined

19 1, 18 13 sequence

е

s

Рис, I. Пример обработки анализатором управляющего rpafa

6

Модуль CLASSIFY предназначен для классификации гамаков или 1ределения типа структур управления орграфа, полученных на выходе >дулй QROLLIN.

Анализатор NEATANAL реализован на персональной ЭВМ типа. IBM !/ХГ и требует порядка 50 К памяти. В качестве языка программиро-1ния использован Си (компилятор TURBO-С v. 1.5). В качестве опе-щиовной системы использована КБ-DOS v. 3.2, однако эксплуатиро-1ться данная система может и в среде K6-WIND0WS.

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

На базе анализатора NEATANAL разработана экспериментальная ИС NEATMAP, .позволяющая провести анализ потока- управления сложного : В системе NEATMAP используются спускающиеся меню, аналогичные ни систем Turbo С и dBASE III Plus, что облегчает ее освоение и пользование. Данная, система состоит из пяти основных модулей, ждый из которых соответствует одноименному режиму работы:

1. Мэдуль PACK/UNPACK осуществляет упаковку и разпаковку уп-вляющего графа листинга программы. Процесс упаковки подразумевав преобразование элементарных функциональных блоков (гамаков) к иному, распаковка - наоборот.

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

3. Издуль INF0TEXT выводит на экран полный текст листинга ¿граммы.

4. Модуль FULLGRAPH строит управляющей граф листинга програм-, подлежащей анализу.

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

Система NEATMAP реализована с помощью графических средстз яаыка Turbo С v. 1.5 с использованием операционной системы tfi-DOi v. 3.2 и требует порядка 60 К памяти.

разработка сложных ПК вызывает особенные трудности. К ним относятся:

- параллельная разработка ПО и аппаратной части;

- обработка данных в реальном масштабе времени;_

- необходимость частой модификации До;

- разработка драйверов для нестандартных устройств.

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

реляционной модели базы данник.

В третьей главе рассматриваются вопросы разработки методов и создания ИС для статического анализа потока данных программы, основанной на использовании реляционной СУБД.

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

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

Далее приводится описание экспериментальной ИС статического анализа потока данных ПК - NEATBASE, созданной »втором на базе СУБД dBASE III Plus.

Для каждой программы создаются четыре отношения: ■

1) ТЕХГ: <номер строки> «исходный текст> <тип оператора>;

2) VARIABLE: <имя переменной <тип переменной»;

3) OPERATION: «номер строки> <имя переменной» <тип операции»;

4) KODULE: <код модуля» <имя модуля,, комментарий».

\е, <номар строки» - четырехзначный номер строки в исходном текс-.>; «исходный текст» - строка исходного текста, состоящая из одно-j оператора языка Си;

<тип оператора» - в данной реализации система отличает три '.па операторов:

sssien-присвоения, например: х=у+1; int z=3; 1++; и т.д. dsclare-обьявления, например:, int х; unsigned у; и т. д. central-контроля, например: goto loop; if(x»y) и т. д. <имя п&згменной» - 32-символьная строка, начинающаяся всегда ¡гквой;

«тип переменной» - один из основных типов переменных языка Си! паг, short, int, long, float, double;

«тип операции» - в данной реализации система отличает пять ,шов операми:

déclaré - объявления (см. выше);

read - чтения например, в операторе z-x+y; переменные х и у ¡лаются;

write - записи например: х=1; int х»1; и т.д. update -, переопределения например: i++; 1=1-1; и т. д. control - контроля (см. выше); <код модуля» - одна латинская буква A-Z; ■ «имя модуля, коментарий» - символьная строка, не превышаются 2 символов.

Для упрощения взаимодействия с системой NEATBASE некоторые зновные запросы вынесены в меню и ответы на них пользователь мо-эт получить без составления соответствующей программы1на внутрен-ем языке dBASE III Plus.

Главное меню системы NEATBASE (рис. Z). предоставляет пользо-ателю возможность выбора одного из 8-ми режимов работы или опций, ля выбора одной из них достаточно нажать клавишу соответсвуюшую □меру опции с последующем нажатием клавиши <Enter».

Главное меню системы NEATBASE

1. Формирование отношений 2. Список идентификаторов программ 3. Фрагмент исходного текста программ

4. Список переменных программ В. Срез операторов с заданными переменными 6. Срез операторов заданного типа 7. Срез операторов заданного типа над заданными переменными ' 8. HELP

Рис. 2. Главное меню системы NEATBASE

В опциях 3, 5, 6, 7 предусматривается возможность выбора дл; анализа базы данных одного модуля, группы модулей или всех модулей. Цри вводе типа операции и типа оператора система сама переводит их.в строчные буквы. Аналогично при вводе букв A-Z при выборе кода модуля, система переводит их в прописные. В режиме "Срег операторов с заданными переменными" если вместо имени переменной, нажимается клавиша <Enter>, система автоматически переходит в ре-жйм выбора модуля.

Для получения подсказки необходимо нажать функциональную клавишу <F1>. При атом в правом верхнем углу экрана открывается окно и на нем начинает выводиться текст подсказки. Если требуется прерывание вывода полного текста ответа на запрос или подсказки, достаточно нажать клавишу <Del>. -

Для получения справочной информации по требуемому фрагменту текста, идентификатору или списку идентификаторов какого-либо моду ля( ей) достаточно выбрать соответствующие опции главного меню системы. \

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

Зтвет на этот аапрос можно получить с помощью опции "Срез операто-эов заданного типа". Знание операторов, в которых для заданной переменной выполняется заданная операция, облегчает понимание потока цанных. Кроме того, возможно получение информации о выполнении лю-5ой операции над какой-либо переменной. Для этой цели используется 'Срез операторов заданного типа над заданными переменными".

Результаты обработки запросов пользователя система может выдавать в одно из окон экрана или на печатающее устройство.

Система NEATBASE предназначена для использования в среде (¡Б-WJNDOWS и может работать совместно с любым многооконным редактором. Такая реализация NEATBASE способствует повышению производительности труда программиста за счет облегчения процесса поиска информации и одновременного редактирования текстов модулей.

Система NEATBASE предлагается в двух модификациях: откомпилированная в виде .ехе файла и в исходном тексте на внутреннем языке dBASE III Plus. Откомпилированный вариант требует порядка 170 К памяти.

Хотя dBASE III Plus является сравнительно примитивной СУБД, фактически Лшованной на обычных однородных файлах, ее использование наряду с очевидными недостатками (неэффективность, отсутствие полей переменной длины) имеет и определенные преимущества. Прежде всего, благодаря своей популярности, она знакома большинству программистов, работающих на персональных ЭВМ. Поэтому обучение языку запросов не требуется и пользователь может самостоятельно составлять достаточно сложные запросы к базе данных.

Далее в главе рассматривается вопрос развития реляционного подхода к аналиау ПО, связаного с переходом к обьектно-ориентиро-ванному представлению информации. Представление информации о программе как совокупности объектов имеет два преимуиэства:

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

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

ЗАШЕОЧШШЕ

Основные результаты диссертационной работы заключаются в сведущем:

1. Предложен метод декомпозиции управляющего графа программы на гамаки и на его основе разработан анализатор логической структуры программы, позволяющий выявить в графе управления, кроме -классических—структур—упряшшиия тяких. как IF-THEN-ELSE, DO-WHILE, DO-UNTIL, CASE и т. д,, другие типы структур управления, так называемые кванты или простые гамаки.

2. Разработана ИС визуализации потока' управления программ центральной компонентой которой, является анализатор логической структуры программа. '

3. Рааработана экспериментальная ИС для обработки Ш, осног ванная на использовании СУБД реляционного типа и позволяющая' провести статический анализ потока данных.

В приложении вынесены исходные тексты систем NEATАНAL, NEATMAP и NEATBASE.

Основные положения диссертации опубликованы в следующих работах. ,

1. Безруков Н. Н., Хаджияннис X С. Вопросы организации повторного использования программного обеспечения для систем диагностирования авиационного оборудования // Автоматизация процессов тех-' нического обслуживания и ремонта авиационного.оборудования.

Киев: КИИГА, 1088. - С. 58-63.

2. Хаджияннис X С. Анализатор логической структуры программы // Эксплуатация программного обеспечения вычислительных систем реального времени, построенных на базе -микро и мини ЭВМ. -

Киев: КИИГА, 1Q88. - С. 25-32.

3. Хаджияннис Х.С. Информационная система для анализа и визуализации структурных программ - NEATMAP // Экспертные системы для анализа и реконструкции программного обеспечения вычислительных систем реального времени. - Киев: КИИГА, 1989. - С. 43-51.

\z