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

Российская Академия Наук Институт Системного Программирования

УДК 681,3.06 На правах рукописи

Архипова Мария Викторовна

АВТОМАТИЧЕСКАЯ ГЕНЕРАЦИЯ ТЕСТОВ ДЛЯ СЕМАНТИЧЕСКИХ АНАЛИЗАТОРОВ ТРАНСЛЯТОРОВ

Специальность 05.13.11 -математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2006

Работа выполнена: в Институте Системного Программирования Российской Академии Наук.

Научные руководители:

доктор физико-математических наук, Петренко Александр Константинович

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

доктор физико-математических наук, Серебряков Владимир Алексеевич

кандидат физико-математических наук, Александров Александр Леонидович

Ведущая организация:

Научио-исследоватсл ьски й вычислительный центр Московского Государственного Университета

Защита диссертации состоится « 10 » ноября_2006 г. в 23- часов на

заседании диссертационного совета Д.002.087.01 при Институте Системного Программирования РАН по адресу:

109004, Москва, Б, Коммунистическая 25, Институт Системного Программирования РАН, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Института Системного Программирования РАН.

Автореферат разослан <<•£_»

ЫГЛТМ 2006 г.

Ученый секретарь диссертационного совета кандидат фкз.-мат. наук

/Прохоров С.Ш

Общая характеристика работы

Актуальность работы

Транслятор — это обобщающее название для обширного класса программ, оперирующих формальными текстами. В качестве примера трансляторов в первую очередь следует упомянуть компиляторы и интерпретаторы с языков программирования, которые получают на вход программы и переводят их в машинный код. Различные XML-процессоры, предназначенные для разбора хmi-документов, также решают задачу трансляции. Примерами трансляторов являются браузеры, трансформирующие тексты на языке HTML в команды "рисования" в экранной области памяти, текстовые процессоры с возможностями форматирования, трансформирующие описания форматированного текста в команды "рисования" или вывода на устройство печати, серверы SQL СУБД, транслирующие запросы на языке SQL в последовательность низкоуровневых операций с базой данных.

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

Одним из методов достижения высокого качества и надежности разрабатываемых трансляторов является тестирование. Трансляторы

3

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

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

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

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

1 Под семантическими правилами в данной paixm: ланнмаютсн правила статической семантики формального языка пли контекстные условия. Вопросы, касающиеся динамической семакпош входного языка (если rnoiu имеется), выходят за предехы дайной работы.

1 Hanford K.V. Automatic generation of Wit cases U IBM System Journal 1970,9. N 4. P. 242-257.

FurdoraP. A sentence generator for testing parsers It Behavior and Information Technology. 1972. 12. N 3. P. 366-S7J,

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

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

9 Kossotctev Д. S., Kiitter P., Posypkm M. A., Automated Generation of Strictly Confouning Tests Based on Formal Specification of Dynamic Semantics of the Programming Language // Programming and Computing Software. 2004,30. N 4. P. 218-229.

4 Knuth D. E. Semantics of Context-Free Languages H Mathematical Systems Theory. 1968, 2. N 2. P. 117-14«.

Цели и задачи работы

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

Для достижения этой цели необходимо решить две задачи:

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

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

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

2. разработать метод генерации позитивных и негативных тестовых входных данных, которые бы:

• в отличие от известных методов не использовали фильтрацию (селекцию) семантически корректных тестов среди множества всех синтаксически корректных;

• позволил строить тесты, нацеленные на проверку корректности анализа семантических правил в семантическом анализаторе транслятора.

Методы исследования

На различных этапах решения поставленных задач применялись различные методы исследования: методы формальных спецификаций программ н методы тестирования программных систем на основе моделей.

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

язык TreeDL*, являющийся аналогом таких нотаций как ASN. 16 и ASDL7, Для реализации генератора тестов для семантического анализатора использовался язык Java и среда разработки приложений Eclipse.

Научная новизна

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

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

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

• разработан язык SRL (Semantic Relation Language), предназначенный для описания входных данных для генератора семантических тестов.

Практическая значимость работы

Предложенные формализм описания статической семантики (язык SRL) и метод генерации тестов могут эффективно использоваться для генерации тестов в реальных программных проектах.

Язык SRL позволяет задавать исходные данные для генераторов тестов компиляторов реальных языков программирования и для процессоров других

1 Демздоа А. В. Описание Tiee Description Language [HTML] (htm^mreeforEe.net/proiectsftreedD. 1 ITL'-T Recommandation X.680. Information Technology - Abstract Svntax Notation One (A.SN.i}: Spécification of Basic Notation // ïr.trrDational Télécommunication Union. 2002.

' Wang D. C, Appel A. W, KomJ.L., Serrât S, The Zéphyr Abstract Syntax Description Langujgc il In Piocee«JiDg3 of the USENIX Conftttnce on Domain-Specifk Languagei. Santa Baibaia, Califomi», USA: USENtX Association. 1997. P. 213-223.

текстовых нотаций, используемых в практическом программировании, например: HTML, XML и других нотаций. Язык SRL и метод генерации тестов были использованы в проектах, где требовалось тестировать процессоры процедурных и объектно-ориентированных языков, реализаций текстовых протоколов отвечающих требованиям из группы стандартов MPEG-2, языков спецификаций. Во всех проектах было продемонстрировано, что SRL является эффективным средством описания статической семантики для построения тестов целевых языковых процессоров.

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

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

На основе предложенного метода разработан инструмент STG (Semantic Test Generator) для автоматической генерации тестовых входных данных для семантических анализаторов. Из результатов практического использования STG следует, что предлагаемый подход имеет преимущества по сравнению с другими методами генерации. Проводилось сравнение скоростных характеристик STG с гипотетической схемой генерации, базирующейся на массовой генерации и последующей фильтрация, и с генератором семантически корректных тестов, разработанным М-Посыпкиным®. Сопоставление показало, что скорость STG как минимум на порядок выше. Апробация SRL и STG в реальных проектах позволяет

' Посыпкнн М. А. Применение формальных методов для тестирования компиляторов. Диссертационная работа на соискание степени кандидата фиэнко-мятемагичесия наук. М.: ИСП РАН. 2004.

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

Апробация работы и публикации

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

Основные положения работы докладывались на следующих конференциях и семинарах:

• на Первой Всероссийской научной конференции "Методы и средства обработки информации", МГУ, октябрь 2003 г.

• на Второй Всероссийской научной конференции "Методы и средства обработки информации", МГУ, октябрь 2005 г.

• на семинарах Института Системного Программирования РАН, 20032005 гг.

• на семинарах ВЦ РАН, май-июнь 2005 г.

Структура и объем работы

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

Содержание работы

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

Завершается введение описанием практической апробации предложенного метода и кратким описанием содержания диссертационной работы.

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

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

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

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

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

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

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

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

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

Рассмотрим некоторый синтаксически н семантически корректный текст р, написанный на языке Ь, порожденном однозначной контекстно-свободной грамматикой (7. Тексту р взаимно однозначно соответствует дерево вывода

Напомним, что деревом вывода называется дерево, корень которого помечен стартовым символом, а каждый узел — грамматическим символом или символом €, соответствующим пустой цепочке токенов. Внутренний узел и его дочерние узлы соответствуют продукции, причем узел соответствует левой части продукции, а потомки - правой.

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

* ^йЛсЬтапп В. А, 1о«« В. Т(9вОЕ АКЗОЬ 60 сотрПегз, Яойшаге Ргасйсе аж1 «срепетсе. 1972. 6. N2. Р. 261270.

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

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

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

Граф атрибутной Новый граф семантической

зависимости зависимости между

вершинами дерева

Рис. 1 Графы втрвбутиой в семантической зависимости

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

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

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

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

Следовательно, множество контекстных условий можно описать в виде системы формул, состоящих из предикатов, заданных на множестве вершин деревьев

Если множество вершин 11(1) некоторого дерева г, соответствующего синтаксически корректному тексту, является решением этой системы при условии, что каждое правило принимает значение "истина", тогда текст, соответствующий дереву I будет также и семантически корректен.

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

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

Далее вводятся некоторые понятия, основными среди которых являются конструктивная грамматика, контекстные условия в конструктивной грамматике.

Конструктивной грамматикой называется пара (О, С), где <7 — это однозначная КС-грамматика, а С-это множество контекстных условий.

Контекстные условия задаются на множестве вершин деревьев вывода, соответствующих текстам, порожденным грамматикой О, и принимают один из трех видов (1НЗ).

Т»б. 1 Типы коатекстаы! условий в конструктаввов грамматике

Типы контекстных условий Выражения, задающие контекстные условна

Правило разрешимое в пределах одного узла (one-node) R(u)*Plr/u) =>F(u, и) О)

Многие-ко-многим (many-to-many) R(u, v)=(u * v л Ptr/u) л F(u, v)) (2)

Один-ко-многим (one-to-many) Я(и)^(Р^(и)=>3/(и v)aF(u, v))) (3)

Здесь и, V - это вершины дерева ¡еМ(С), Ри(и), Р^и, V) - это предикаты, описывающие положения и типы вершин и и V, к которым должно применяться данное контекстное условие, Г(и, у) - это предикат, задающий требования на поддеревья, с корнями в вершинах и и V соответственно. В общем виде положение вершины V может зависеть от вершины и, поэтому положение V описывается двуместным предикатом Р/и, у), который для некоторых условий может вырождаться в одноместный предикат Ру(у), когда положение V не зависит от вершины и.

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

Тип Формулы F(n, v) Описание

Equal (ЭхеЩГ) ^Ptrgjs ublrtt fa) лЗуе U(Г) Л Pire гuhtrtt(y)) (1* == Т) Р- формулы, описывающие положение вершин, Т- поддерево с корнем в вершине х, V- поддерево с корнем в вершине у, 11(1")-множество вершин поддерева с корнем в вершине и, и(Т")-множество вершин поддерева с корнем в вершине V.

unequal (Зх eU(T") '^flrg_su bint (х) лЗуе ЩГ) Л P,TC_**btrét(y)) Р- формулы, описывающие положение вершин, 7*- поддерево с корнем в вершине х, V- поддерево с корнем в вершине у, и(7*)-множество вершин поддерева с корнем в вершине и, ЩТ")-множество вершин поддерева с корнем в вершине V.

present (ЭхеЩГ) Л Р trg_s»btrtt(x)) =>(3у<= V(T) APjre_tubtrit(y)) Если в поддереве с корнем в вершине и существует вершина х, тогда в поддереве с корнем в V должна существовать вершинаИ(Т"}-множество вершин поддерева с корнем в вершине и, ЩТ*)-множество вершин поддерева с корнем в вершине V.

absent (3xeV(T) (~3у eU(T) Если в поддереве с корнем в вершине и существует вершина*, тогда в поддереве с корнем в V не должна существовать вершина у, 17(7")-множество вершин поддерева с корнем в вершине и, 17(1")-множество вершин поддерева с корнем в вершине V.

Отдельно задается предикат Р(и, у) для контекстных условий

проверяющих приводимость типов.

Положение Р вершины и в дереве ( задаются при помощи следующих формул.

Таб. 3 Атомарные одноместные формулы в коне тру кти ввой грамматике

№ Атомарные одвоместяые предикаты, описыяаюшяе положение кершнн Предикат истинен, если—

1. Л(и) вершина и помечена грамматическим символом А.

2. Ф) вершина и помечена с.

3. Ь(и) вершина и имеет имя Ь.

Далее приводятся атомарные двуместные формулы: Таб. 4 Атомарные двуместяые формулы в конструктивное грамматике

Л Атомарные двумепиые предикаты, описывающие положение вершин Предикат истинен, если..

1. рагеп((и, V) V - непосредственно родительская вершина вершины и.

2. *В(и,у) V - ближайшая по отношению к вершине и родительская вершина, помеченная грамматическим символом В.

3. <п.В(и, у) V - вершина помечена грамматическим символом В и находится на глубине меньше я от вершины и.

4. <=п.В(и, v) у - вершина помечена грамматическим символом В и находится на глубине не больше и от вершины, удовлетворяющей формуле Р.

5. >п.В(и, V) V - вершина помечена грамматическим символом В и находится на глубине больше п от вершины и.

6. >=п.В(и, V) V - вершина помечена грамматическим символом В и находится на глубине не меньше п от вершины и.

№ Атомарвыс двуместные предикаты, описывающие положевве в ер ошв Предикат нст»в*н, еслн„

7. п.б(и, у) V - вершина помечена грамматическим символом в и находится на глубине и от вершины и.

8. oö.b(u, v) V - вершина помечена грамматическим символом в и находится на любой глубине от вершины».

Комбинируя введенные атомарные предикаты и их отрицания можно получить другие формулы, применяя правило (4).

f-U J-e.«

Все остальные формулы, задающие требования на положение и тип вершин, строятся из атомарных формул и формул, полученных по правилу (4), с помощью применения правил (5), (б), где loO, Pt - атомарные предикаты из Таб. 3 и Таб. 4 или предикат, полученный по формуле (4).

¿-м >«м

V-J.i

Далее приводятся примеры описания правил статической семантики, в том числе для языка Java, с использованием приведенного формализма.

Для того чтобы на практике задавать контекстные условия предложенного вида, разработан язык SRL (Semantic Relation Language)10. Язык SRL представляет собой сокращенную запись, приведенного ранее формализма. Более подробное описание SRL приводится в четвертой главе.

Далее во второй главе приводится пример описания правил статической семантики на языке SRL.

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

" Грамматика языка SRL приводится в Приложений А.

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

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

Критерии базируются на понятии покрытия тестовыми текстами контекстных условий. Поскольку формулы, задающие контекстные условия, бывают одноместные и двуместные сформулировано два определения. Первое определение дано для контекстных условий типа (1) и (3). Текст на входном языке Ь покрывает контекстное условие Я (и)=> Р'(и, у),

если для дерева Г, соответствующего этому тексту выполняется следующее БигеЩ1)\Р'п(и). Второе определение дается для контекстных условий

типа (2): текст на входном языке Ь покрывает контекстное условие Л "(и, л Р^ (и)л у)), если для дерева I, соответствующего

этому тексту выполняется следующее Би", у"е1/(1)| Р^ (и") /V Р^(и'У),

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

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

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

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

Рассмотрим труппу правил, содержащую тексты, нарушающие контекстное условие Л. Тогда все тесты, принадлежащие к этой группе, удовлетворяют контекстным условиям, заданным в модифицированной SRL-спецификации, в которой без изменений присутствуют все (кроме требования К) контекстные условия входного языка, и, плюс, еще одно правило, представляющее собой контекстное условие, выполнение которого будет означать нарушение правила R. Такое правило называется мутацией контекстного условия R и обозначать^.

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

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

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

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

В качестве внутреннего представления генерируемых тестов используются (абстрактные) синтаксические деревья, которые описываются при помощи языка TreeDL11 {Tree Description Language), разработанного группой RedVerst ИСП РАН1г.

Для описания правил статической семантики используется язык SRL.

11 Деиаксэ А. В. Описание Ttee Description Language (HTML] tTirtp^/Mureefotge.nefproiect.'iftreedn.

11 RedVerst [HTML] fhttp://www.ispras.ni/-RedVer5^.

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

Контекстное условие, на проверку которого направлен тест р, называется первичным контекстным условием (или первичным правилом) данного текста р.

Базовым множеством Ш контекстных условий дерева %€М(0) называется множество таких контекстных условий, посылки в которых принимают значение "истина " на дереве и то есть

Д'={Д'(к) € | Эи' е и(0: («')}

и{Л'(и,V)е\Эи",V' еЩ)Р^ (V)}.

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

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

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

81. Из множества БЯ^ц всех контекстных условий языка Ь выбирается непомеченное контекстное условие К и помечается. .Далее условие Я

называется первичным правилом. Если такого контекстного условия нет, то КОНЕЦ генерации, иначе перейти на следующий шаг.

Б2. Для первичного правила Я строится множество всех первичных деревьев с учетом ограничения глубины рекурсии. Описание построения первичных деревьев приводится во второй части третьей главы.

$3. Из множества первичных деревьев, построенных на предыдущем шаге, выбирается непомеченное дерево (рГ(™>> и помечается. Если такого дерева нет, то 81.

Э4. Первичное поддерево 1Рптту, выбранное на предыдущем шаге, достраивается минимальным образом до синтаксически полного дерева то есть продолжается раскрытое нетерминалов до тех пор, пока это позволяет грамматика языка. Достраивание дерева минимальным образом осуществляется за счет построения всех возможных дочерних вершин, помеченных £.

Б5. Для синтаксически полного дерева /, полученного на предыдущем шаге, строится базовое множество контекстных условий Л*. Этот шаг подробно описывается во второй части третьей главы.

Бб. Для того чтобы убедиться в семантической корректности текста в силу критерия семантической корректности необходимо и достаточно проверить удовлетворяет ли текст контекстным условиям из соответствующего базового множества. Проверяется, истинны ли базовые правила для данного дерева то есть верно ли следующее Уи, уеЩО И=й. (&(и)) л Щи, у)), где Кь тп - это

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

57. Если все базовые правила истинны на множестве 11(0, то осуществляется переход к шаху иначе в дереве I производятся

изменения, не затрагивая первичного дерева, такие, чтобы все базовые правила были всегда истинны. Если удалось произвести требуемые изменения в дереве, то осуществляется переход к шагу S6, иначе дерево I объявляется семантически неразрешимым и осуществляется переход к шагу S3. Этот шаг также подробно описывается во второй части третьей главы.

S8. Базовые контекстные условия для дерева / истинны на множестве 1/(0• Дерево t отображается в текст на входном языке. Построенный текст будет удовлетворять всем синтаксическим и контекстным требованиям соответствующего языка. Осуществляется переход к шагу S3.

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

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

• семантические правила, связанные с механизмом наследования в объектно-ориентированных языках;

• правила, требующие проверки дополнительных условий;

• правила, описывающие условия при которых нельзя использовать некоторые синтаксические конструкции;

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

Приводятся описания конструкций SRL и подробные примеры их использования.

Диссертационная работа содержит 4 приложения.

В приложении Л приводится полная грамматика языка SRL в виде EBKF.

В приложении В приводится полная грамматика модельного языка Loo, обладающего объектно-ориентированными свойствами.

В приложении С приводится формальное описание семантики языка ¿оо ко языке SRL.

В приложении D содержит формальное описание семантических правил на языке SRL для замкнутого подмножества языка Java 1.5, охватывающего работу:

• с декларациями пакетов, классов, полей, методов, параметризованных классов;

• с выражениями: присваивание, арифметические операции, вызов метода и другими;

• с операторами: операторами циклов, оператором условного перехода и другими.

Основные результаты работы

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

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

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

проверку корректности анализа семантических правил в семантическом анализаторе транслятора,

3. Реализован генератор входных данных для тестов, основанный на разработанном методе.

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

Публикации

1. Архипова (Напрасникова) М.В. Автоматическая генерация семантических тестов для трансляторов // Метода и средства обработки информации. Труды первой Всероссийской научной конференции/ Под ред. Королева Л Д. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В Ломоносова, 2003. С. 448453.

2. Штейкберг Б Л., Архипова (Напрасникова) MJ3. Минимальное множество контрольных дуг при тестировании программных модулей // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Ростов-на-Дону: Ростовский государственный университет, 2003. № 4, С. 15-18,,

3. Архипова М.В. Генерация тестов для модулей проверки статической семантики в трансляторах // Труды Института Системного Программирования/ Под ред. чл.-корр. РАН Иванникова В.П. М.: Институт Системного Программирования РАН, 2004. 8. № 1. С. 59-76.

4. Архипова М.В. Конструктивное описание правил статической семантики языков программирования // Методы н средства обработки информации. Труды первой Всероссийской научной конференции/ Под ред. Королева Л Д. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 2005. С. 323-329.

5. Архипова MJ3. Генерация тестов для семантических анализаторов. Препринт. М.: Институт Системного Программирования РАН, 2005. 25 с.

6. Архипова М. В. Генерация тестов для семантических анализаторов // Вычислительные методы и программирование. 2006. 7. С. 55-70. [PDF] (Tittp://num-meth.srcc.msu.su/2humal/tom 2Q06/pdf/v7r206.pdf).

Принято к исполнению 04/10/2006 Исполнено 0J/10/2006

Заказ № 706 Тираж: 100 экз.

Типография «11 -й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (495)975-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

1 ГЕНЕРАЦИЯ ТЕСТОВ ДЛЯ АНАЛИЗАТОРОВ КОНТЕКСТНЫХ УСЛОВИЙ ТРАНСЛЯТОРОВ: СОВРЕМЕННОЕ СОСТОЯНИЕ.

1.1 Обзор методов генерации тестов для трансляторов.

1.2 Основные принципы проектирования набора тестов для анализатора контекстных условий транслятора.

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

1.4 Анализ результатов генерации тестов с использованием классических атрибутных грамматик.

2 КОНСТРУКТИВНОЕ ОПИСАНИЕ СТАТИЧЕСКОЙ СЕМАНТИКИ ФОРМАЛЬНЫХ ЯЗЫКОВ.

2.1 Неформальное описание идеи.

2.2 Конструктивное описание семантики.

2.3 Критерий покрытия.

2.3.1 Критерий покрытия для позитивных тестов.

2.3.2 Критерий покрытия для негативных тестов.

3 СЕМАНТИЧЕСКИ УПРАВЛЯЕМАЯ ГЕНЕРАЦИЯ ТЕСТОВЫХ ВХОДНЫХ ДАННЫХ.

3.1 Представление данных.

3.2 Генерация входных данных для позитивных тестов на основе конструктивного описания статической семантики.

3.2.1 Построение первичных поддеревьев.

3.2.2 Обеспечение семантической корректности тестовых текстов.

3.3 Генерация негативных тестовых входных данных на основе конструктивного описания статической семантики.

4 SRL: ОПИСАНИЕ НЕТРИВИАЛЬНЫХ КОНТЕКСТНЫХ УСЛОВИЙ.

4.1 Контекст семантического правила.

4.2 Семантические правила с фильтрами.

4.3 Зависимые семантические правила.

4.4 Описание объектов семантического правила посредством задания пути

4.5 Семантика типов.

4.6 Семантические ограничения на синтаксис.

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

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

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

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

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

Для решения близкой задачи, задачи генерации входных данных для тестирования лексического и синтаксического анализаторов, разработан ряд хорошо зарекомендовавших себя методов автоматической генерации тестов [10-13 и др.], тесты для семантических анализаторов трансляторов, как правило, разрабатываются вручную. Методы, полученные в результате проведенных теоретических исследований в области тестирования семантических анализаторов, не получили широкого применения на

1 Под семантическими правилами в данной работе понимаются правила статической семантики формального языка или контекстные условия Вопросы, касающиеся динамической семантики входного языка (если таковая имеется), выходят за пределы данной работы практике [14-20 и др.], что частично объясняется более высокой сложностью описания статической семантики по сравнению с описанием синтаксиса формальных языков .

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

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

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

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

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

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

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

• разработать методики генерации позитивных и негативных тестовых входных данных.

Под позитивными и негативными тестовыми входными данными в контексте данной работы понимается следующее (см. Рис. 1).

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

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

- синтаксические корректные

- синтаксические некорректные

- семантические корректные позитивные тестовые входные данные)

- семантические некорректные (негативные тестовые входные данные)

Рис. 1 Тесты для анализатора контекстных условий

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

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

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

Текс! построить деревья вывода, которые затем можно было бы отобразить в тексты на формальном языке. Ясно, что наиболее удобным способом описания синтаксических правил является BNF и его производные. Нерешенным остается вопрос, каким образом описать правила статической семантики для генератора?

Наиболее широко используемый формальный метод описания правил статической семантики - это атрибутные грамматики [1, 2]. Атрибутные грамматики (АГ) удобны для решения задачи семантического анализа текстов. Так как одной из целей поставленной задачи является разработать метод целенаправленной генерации текстов на входном языке, то использовать атрибутные грамматики для описания семантических правил для генерации семантически корректных и некорректных текстов нельзя из-за их неконструктивной природы. Необходимо описать требования на семантическую корректность генерируемых текстов в каком-то конструктивном виде, который облегчит целенаправленную генерацию и позволит уменьшить непроизводительные затраты. Будем называть описание правил статической семантики в таком виде конструктивной грамматикой.

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

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

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

Граф атрибутной зависимости Граф семантической зависимости

Рис. 2 Графы атрибутной и семантической зависимости

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

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

Теперь необходимо ответить на вопрос: как на основе семантики, заданной конструктивной грамматикой, целенаправленно построить

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

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

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

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

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

Рис. 3 Синтаксически неполное дерево вывода

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

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

6 Более подробно типы семантических отношений («многие-ко-многим», «один-ко-многим», «один-ко-одному» и «разрешимое в пределах одного узла») рассматриваются во второй главе

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

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

Для конструктивного задания правил статической семантики формальных языков был разработан язык SRL (Semantic Relation Language). Конструкции SRL в декларативной манере позволяют описывать правила статической семантики, задавая при этом тип правила (один из трех) и предикаты на вершины дерева вывода, удовлетворяющие требованиям контекстных условий.

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

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

7 Метод построения семантически некорректных текстов подробно описывается во второй главе

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

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

На основе предложенного метода разработан инструмент STG (<Semantic Test Generator) для автоматической генерации тестов для семантических анализаторов. Проводилось сравнение скоростных характеристик STG с гипотетической схемой генерации, базирующейся на массовой генерации и последующей фильтрации, и с генератором семантически корректных тестов, разработанным М. Посыпкиным [42]. Сопоставление показало, что скорость STG в первом случае выше на 3 порядка, во втором - на 1 порядок.

С помощью реализованных в рамках работы над диссертацией инструментов для автоматической генерации тестов для семантических анализаторов были получены тестовые наборы для языка С, для анализатора XML-текстов, соответствующих подмножеству описаний, заданных в стандарте MPEG-21 [43]. Также разработана часть тестового набора для анализатора контекстных условий языка Java, позволившая обнаружить ошибки в компиляторе, разрабатываемом в рамках промышленного проекта.

По теме диссертации опубликовано 6 работ, отражающих основные научные результаты диссертации:

1. Архипова (Напрасникова) М.В. Автоматическая генерация семантических тестов для трансляторов // Методы и средства обработки информации. Труды первой Всероссийской научной конференции/ Под ред. Королева JI.H. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 2003. С. 448-453.

2. Штейнберг Б.Я., Архипова (Напрасникова) М.В. Минимальное множество контрольных дуг при тестировании программных модулей

8 Критерии подробно описываются во второй главе Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Ростов-на-Дону: Ростовский государственный университет, 2003. № 4. С. 15-18.

3. Архипова М.В. Генерация тестов для модулей проверки статической семантики в трансляторах // Труды Института Системного Программирования/ Под ред. чл.-корр. РАН Иванникова В.П. М.: Институт Системного Программирования РАН, 2004. 8. № 1. С. 59-76.

4. Архипова М.В. Конструктивное описание правил статической семантики языков программирования // Методы и средства обработки информации. Труды второй Всероссийской научной конференции/ Под ред. Королева JI.H. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 2005. С. 323-329.

5. Архипова М.В. Генерация тестов для семантических анализаторов. Препринт. М.: Институт Системного Программирования РАН, 2005. 25 с.

6. Архипова М. В. Генерация тестов для семантических анализаторов // Вычислительные методы и программирование. 2006. 7. С. 55-70. [PDF] (http://num-meth.srcc.msu.su/zhurnal/tom 2006/pdf/v7r206.pdf).

Основные положения работы докладывались на следующих конференциях и семинарах:

• на Первой Всероссийской научной конференции "Методы и средства обработки информации", МГУ, октябрь 2003 г.

• на Второй Всероссийской научной конференции "Методы и средства обработки информации", МГУ, октябрь 2005 г.

• на семинарах Института Системного Программирования РАН, 2003-2005 гг.

• на семинарах ВЦ РАН, май-июнь 2005 г.

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

Заключение

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

С целью практического применения полученных результатов был разработан язык SRL (Semantic Relation Language) для описания правил статической семантики формальных языков и инструмент STG (Semantic Test Generator) для автоматической генерации тестов для семантических анализаторов.

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

Затем был получен тестовый набор для анализатора XML-текстов, соответствующих подмножеству описаний, заданных в стандарте MPEG 21 [43] (см. Таб. 20).

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

Таб. 20 Сравнительная таблица результатов применения метода

С XML Java

Процент покрытых страниц стандарта - 70 % -69%

Объем БЯТ-спецификации (строк) 10196 147 3319

Кол-во тестов -10000 -52 -11000

Общий объем ~ 10 Mb -161 Kb -11 Mb

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

Таб. 21 Сравнительная таблица результатов применения метода

Параметры генератора БТв Объем сгенерированн ого тестового набора (тестов)

Кол-во продукционных правил Кол-во семантических правил Глубина рекурсии Глубина итерирования Кол-во тестов для одного правила

440 276 1 2 1 276

1 2 все -20000

2 2 все ~1000000

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

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

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

3. Реализован генератор входных данных для тестов, основанный на разработанном методе.

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

1. KnuthD.E. Semantics of Context-Free Languages // Mathematical Systems Theory. 1968. 2. N 2. P. 127-146.

2. KnuthD.E. Semantics of Context-Free Languages: Correction // Mathematical Systems Theory. 1971. 5. N 1. P. 95-96.

3. Описание Yacc и Lex HTML.(http://dinosaur.compilertools.net/).

4. Kastens U. Attribute Grammars as a Specification Method // Proceedings of the International Summer School on Attribute Grammars. Lecture Notes in Computer Science. Vol. 545. NewYork-Heidelberg-Berlin: Springer-Verlag, 1991. P. 16-47.

5. Kurt M. Bischoff. Ox: An attribute-grammar compiling system based on yacc, lex and c: User reference manual HTML. (http://citeseer.ist.psu.edu/bischoff93ox.htmn.

6. F. Pagan. Formal Specification of Programming Languages: A Panoramic Primer. Prentice Hall. 1981. 256 p.

7. Kenneth Slonneger, Barry L. Kurtz. Formal, Syntax and Semantics of Programming Languages: A Laboratory Based Approach, 1st edition. London:Addison-Wesley Longman Publishing Co. Inc. 1994. 637 p.

8. A. S. Kossatchev, M. A. Posypkin. Survey of compiler testing methods // Programming and Computing Software. 2005. 31. N 1. P. 10 -19.

9. A. Boujarwah, K. Saleh. Compiler test case generation methods: a survey and assessment // Journal of Information and Software Technology. 1997. 39. N 9. P. 617-625.

10. HanfordK.V. Automatic generation of test cases // IBM System Journal. 1970.9. N 4. P. 242-257.

11. Purdom P. A sentence generator for testing parsers // Behavior and Information Technology. 1972.12. N 3. P. 366-375.

12. Wichmann B.A., Jones B. Testing ALGOL 60 compilers // Software -Practice and experience. 1976. 6. N 2. P. 261-270.

13. Celentano A., Crespi Reghezzi S., Delia Vigna P., Ghezzi C., Granata G., Savoretti F. Compiler Testing using a Sentence Generator // Software Practice and Experience. 1980. 10. N 11. P. 897-918.

14. Duncan A.G., Hutchison J.S. Using Attributed Grammars to Test Designs and Implementation // In Proceedings of the 5th international conference on Software engineering. Piscataway, NJ, USA: IEEE Press, 1981. P. 170-178.

15. Franco Bazzichi and Ippolito Spadafora. An Automatic Generator for Compiler Testing // IEEE Transactions on Software Engineering. 1982. 8. N4. P. 343-353.

16. J. Harm. Automatic test program generation from formal language specifications // Rostocker Informatik-Berishte. 1997.20. P. 33-56.

17. Emin G.un Sirer, Brian N. Bershad. Using production grammars in software testing // In Proc. 2nd conference on Domain-specific languages. New York, NY, USA: ACM Press, 1999.1-13.

18. Hoare C.A.R., Wirth N. An axiomatic definition of the programming language PASCAL // Acta Informatica. 1973.2. N 4. P. 335-355.

19. Lee JAN Computer Semantics. Van Nostrand Co., New York, 1972.

20. Lucas P., Lauer P., Stigleitner H. Method and notation for the formal definition of programming languages. IBM Technical Report 25.087. Vienna :IBM Lab., 1968.

21. Lucas P., Walk K. On the formal description of PL/1 // Annual Review in Automatic Programming. 1969. 6. N 3. P. 105-182.

22. Wegner P. The Vienna Definition Language // Computer Surveys. 1972.4.N1.P. 5-63.

23. Демаков A.B., Зеленова C.A., Зеленов C.B. Тестирование парсеров текстов на формальных языках // Программные системы и инструменты: Тематический сборник факультета ВМиК МГУ. Вып. 2. М: ВМиК МГУ, 2001. С. 150--156.

24. А.Ахо, Р.Сети, Д.Ульман. Компиляторы: принципы, технологии, инструменты. Москва-Санкт-Петербург-Киев: Вильяме, 2001. 767 с.

25. А.В.Демаков. TreeDL. HTMLl(http://sourceforge.net/proiects/treedl).

26. RedVerst. HTML.(http://ww.ispras.m/~RedVerst/).

27. Information Processing Open Systems Interconnection - Specification of Abstract Syntax Notation One (ASN.l) // International Organization for Standardization and International Electrotechnical Committee, 1987. International Standard 8824.

28. Information Technology Abstract Syntax Notation One (ASN.l): Specification of Basic Notation // International Telecommuncation Union, 1995. ITU-T Recommendation X.680.

29. Wang D. C., Appel A. W., Korn J. L., Serra C. S. The Zephyr Abstract Syntax Description Language // In Proceedings of the USENIX Conference on Domain-Specific Languages. Santa Barbara, California, USA: USENIX Association. 1997. P. 213-228.

30. Кристофидес H. Теория графов. Алгоритмический подход. М.: Мир, 1978.215 с.

31. Yuri Gurevich. Abstract State Machines: An Overview of the Project, "Foundations of Information and Knowledge Systems", Springer Lecture Notes in Computer Science, volume 2942 (2004), pages 6-13.

32. James Gosling, Bill Joy, Guy Steele, Gilad Bracha. The Java Language Specification, Third Edition, ISBN 0-321-24678-0.

33. Paulc Jorgensen. Software Testing: A Craftsman's Approach. CRC Press, 2nd edition (June 26,2002).

34. Boris Beizer. Black-Box Testing : Techniques for Functional Testing of Software and Systems. John Wiley & Sons, Inc., 1995.

35. Brian Marick. Craft of Software Testing: Subsystems Testing Including Object-Based and Object-Oriented Testing. Prentice Hall PTR (November 28,1994).

36. Cem Kaner. Lessons Learned in Software Testing. Wiley; 1st edition (December 15,2001)

37. Model-Based Testing of Reactive Systems : Advanced Lectures (Lecture Notes in Computer Science). Springer; 1 edition (August, 2005)

38. M.A. Посыпкин. Применение формальных методов для тестирования компиляторов. Диссертационная работа на сосискание степени кандидата физико-математических наук. ИСП РАН. Москва, 2004.

39. MPEG-21. http://www.iso.ch/iso/en/prods-services/popstds/mpeg.html

40. Robert М. Poston. Automating Specification-Based Software Testing : Institute of Electrical & Electronics Enginee (June, 1996)

41. Напрасникова M.B. Автоматическая генерация семантических тестов для компиляторов, Первая Всероссийская научная конференция "Методы и средства обработки информации", МГУ, октябрь 2003 г.

42. Архипова М.В. Генерация тестов для модулей проверки статической семантики в компиляторах, сборник трудов ИСП, Том 8, часть 1,2004г., стр. 59-76

43. Архипова М.В. Конструктивное описание правил статической семантики языков программирования, Вторая Всероссийская научная конференция "Методы и средства обработки информации", МГУ, октябрь 2005 г., стр. 323-329

44. Роберт Калбертсон, Крис Браун, Гэри Кобб. Быстрое тестирование, М., Издательский дом Вильяме, 2002.

45. Компилятор полного стандарта языка С++ как ядро систем разработки программного обеспечения. Под ред. А.Г. Сергеева Приложение к журналу "КомпьюЛог" № 3, 2000 г.

46. ISO/IEC 9126-1:2001. Software engineering — Software product quality — Part 1: Quality model.

47. ISO/IEC TR 9126-2:2003 Software engineering — Product quality — Part 2: External metrics.

48. ISO/IEC TR 9126-3:2003 Software engineering — Product quality — Part 3: Internal metrics.

49. ISO/IEC TR 9126-4:2004 Software engineering — Product quality — Part 4: Quality in use metrics.

50. STG Reference. http://unitesk.com/papers/sematesk/STG-reference-draft-l.O.pdf

51. J.J. Chilenski and S.P. Miller. Applicability of modified condition/decision coverage to software testing. Software Engineering Journal, pp. 193-200, September 1994.

52. Борисова M.B., Морозова T.A., Петренко A.K. Чацкина T.A. Тестирование компиляторов на основе формальной модели языка // Препринт ИПМ, N 45,1992, 15 стр.

53. Свами М., Тхуласираман К. Графы, сети и алгоритмы//М.: «Мир», 1984, 335-338.