И.М. Галкин

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

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

Процесс реализации анализаторов программ распадается на две относительно самостоятельные задачи:

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

- статический и/или динамический анализ построенных моделей (представлений).

Представлениями программы, используемыми при структурном тестировании, являются:

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

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

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

Работы в области создания подобных средств, получивших в русскоязычной литературе название "системы (автоматизации) построения трансляторов" (С[А]ПТ), а в англоязычной (в буквальном переводе) "генераторы (компиляторы) компиляторов", активно велись в 70-80-х гг. в эру господства мэйн-фреймов. Достаточно высокая "наукоемкость" проблемы, а также тогдашняя ограниченность средств поддержки разработки программ предопределили исследовательский характер большинства разработок этого периода, по крайней мере на территории бывшего СССР [2]. Несомненный теоретический интерес, в том числе с точки зрения архитектуры системы, представлял проект генератора компиляторов [3], описанный на специализированном языке XPL. Впоследствии, в эпоху персональных компьютеров, наибольшее признание получила система YACC [4], а также некоторые ее развития, в частности система BISON [5]; из относительно недавних разработок следует отметить исследовательскую разработку PCCTS [6], поддерживающую весьма изощренный формат входных грамматик.

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

Новая версия системы реализована на языке C++ в среде C++ Builder и функционирует в операционной среде Windows для персональных компьютеров. Архитектурно система состоит из двух компонентов:

1) транслятора с описания языка программирования в форме Бэкуса-Наура в соответствующие синтаксические таблицы;

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

Наряду с прежним механизмом поддержки действий, задаваемых пользователем, предполагавшим связывание действий с номерами синтаксических правил, поддерживается и принятый в системе YACC механизм поддержки действий посредством их указания непосредственно за правилами в файле, содержащем описание грамматики входного языка. Этот механизм исключает ошибки в связывании действий и правил в случае изменения входной грамматики. Более того, реализована поддержка YACC-формата описания входной грамматики, что позволяет использовать имеющиеся описания грамматик для YACC без изменений.

Несколько уступая упомянутым ранее системам в гибкости, данная система имеет и ряд несомненных достоинств: во-первых, она поддерживает другой класс грамматик (смешанного предшествования (2,1;1,1), в то время как YACC и BISON поддерживают контекстно-свободные LALR(1)-грамматики, а PCCTS - LL(1)-грамматики), а значит, в отдельных случаях данная система может оказаться более предпочтительной; во-вторых, ее ядро открыто для пользователя, а следовательно, при использовании средств отладки он не окажется внутри неизвестных ему ассемблерных модулей, как это случается при использовании, скажем, YACC; в-третьих, данная система имеет перспективу специализации в области автоматизации моделирования программ.

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

2) как средства поддержки моделирования и инструментирования программ; в данном контексте планируется продолжать работы по автоматизации построения представлений программ и визуализации графовых моделей, в более широком смысле данная система может быть также ориентирована на построение семантической сетевой модели программы в рамках подхода к анализу программ, описанного в [8, 9].
Литература
1. Evaluation Criteria for Information Technology Security. - ISO/IEC 15408: 1999(E).

2. Вооглайд А.О., Серебряков В.А. Применение систем автоматизации построения трансляторов // Прикладная информатика. – М.: Финансы и статистика, 1989. - Вып.15. – С. 72-90.

3. McKeeman W.M., Horning J.J., Wortman D.B. A compiler generator. – Prentice-Hall, Englewood Cliffs, N.J. – 1970. – 527 p.

4. Johnson S.C. Yacc - Yet Another Compiler-Compiler. - Bell Laboratories, Murray Hill, N.J. – 1978.

5. Donnelly C., Stallman R. BISON: the YACC-compatible Parser Generator. – Free Software Foundation, Cambridge. - 1992.

6. Parr T.J., Dietz H.G., Cohen W.E. PCCTS 1.00: The Purdue Compiler Construction Tool Set // SIGPLAN Notices. - 1992. – 27. - № 2. - Pp. 88-165.

7. Галкин И.М., Образкова Н.Л., Романов В.М. Система построения трансляторов МАРС-СПТ // Управляющие системы и машины. - 1983. – № 6. - С. 68-70.

8. Галкин И.М. Использование семантических сетей для моделирования и анализа программ // Управляющие системы и машины. - 1991. - № 5. - С. 55-61.

9. Galkin I.M. A Knowledge-Based Approach to Program Testing and Analysis // Proc. of 12th International Conference on Computer Safety, Reliability and Security (SAFECOMP'93). – Pp. 207-216.
Институт технической

кибернетики НАН Беларуси,

г.Минск

<Примечание:

Статья опубликована в сборнике научных трудов ИТК НАНБ