Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

2004 г.

Автоматическая генерация позитивных и негативных тестов для тестирования фазы синтаксического анализа

С.В. Зеленов, С.А. Зеленова

Труды Института Системного Программирования РАН, 2004 г.

Аннотация

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

Введение

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

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

Для очень многих языков программирования существует формальное описание синтаксиса – описание грамматики языка в форме BNF, а для тех языков, для которых существуют только эталонные компиляторы (например, COBOL), делаются активные попытки построить такое описание (см. [9, 10, 14]). BNF языка является одновременно и спецификацией функциональности синтаксического анализа, таким образом, в этой области наиболее привлекательным является тестирование на основе спецификаций (см. [17]). Существование формального описания позволяет автоматизировать процесс построения тестов, что существенно снижает трудозатраты, а систематичность тестирования повышает доверие к его результатам.

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

Предлагаемые другими авторами методы являются вероятностными (см. [7, 13, 11, 12]) и не описывают критериев покрытия, и потому для них возникает вопрос остановки генерации тестов, который решается, например, с помощью введения вероятностей появления правил и уменьшения этих вероятностей при каждом новом появлении правила в выводе. В любом случае завершение работы алгоритма за конечное время является проблемой. Кроме того, произвольность остановки генерации нарушает систематичность тестирования.

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

В работе [8] высказано предположение, что если имеется генератор предложений языка из грамматики (генератор позитивных тестов для синтаксического анализатора), то для генерации негативных тестов для синтаксического анализатора можно использовать метод мутационного тестирования (mutation testing)1 (см. [6, 15]). Идея состоит в том, что в исходную грамматику вносятся изменения (мутации) для получения грамматик, описывающих близкие, но не эквивалентные исходному языки. Эти мутированные грамматики подаются на вход генератору тестов для получения потенциально негативных тестов. Общие проблемы данного подхода состоят в следующем:

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

В настоящей работе описаны критерии покрытия, нацеленные на алгоритмы синтаксического анализа. Такой подход представляется оправданным, поскольку тестовые наборы строятся для тестирования синтаксических анализаторов, и эффективность тестового набора должна оцениваться исходя из характеристик, относящихся к тестируемым компонентам (т.е. синтаксическим анализаторам), таких как, например, покрытие функциональности или кода. Данная методика разработана в рамках общего модельного подхода к тестированию компиляторов (см. [2, 3, 4]). Мы рассматриваем известные алгоритмы синтаксического анализа в качестве алгоритмов, моделирующих поведение синтаксического анализатора. Как уже говорилось, в литературе практически отсутствуют работы, посвященные генерации негативных тестов. Настоящая работа призвана закрыть этот пробел.

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

1. Предварительные сведения

В этом разделе мы приводим некоторые сведения из теории синтаксического анализа. Более подробное изложение приведенных фактов можно найти в известной книге А. Ахо, Р. Сети и Д. Ульмана (см. [5]).

Грамматика формального языка задается четверкой G = (T,N,P,S), где

  • T – множество терминальных символов или токенов;
  • N – множество нетерминальных символов;
  • P – список правил грамматики;
  • S – стартовый символ грамматики.
Множество предложений формального языка, задаваемого грамматикой G, будем обозначать G.

Дадим несколько определений.

Расширением грамматики G (или просто расширенной грамматикой) называется грамматика G' = (T,N',P',S'), где S' – новый нетерминальный символ, а к множеству правил добавлено правило S' → S.

Сентенциальной формой будем называть последовательность грамматических символов – нетерминалов и токенов. Далее, греческими буквами из начала алфавита (α, β, γ, δ, ...) мы будем обозначать какие-либо сентенциальные формы. Пустую сентенциальную форму будем обозначать через ε.

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

Пример. Рассмотрим следующую грамматику:

S → AB

A → cd

B → eCf

C → Ae

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

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

Пример. Пусть грамматика та же, что и в предыдущем примере. Форма AeCf, как мы уже заметили, является правосентенциальной. В ней есть две подпоследовательности символов Ae и eCf, которые могут быть свернуты в нетерминалы C и B соответственно. Однако основой является только последовательность eCf, так как сентенциальная форма CCf невыводима из стартового символа. ►

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

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

Пример. Правило вывода A → XYZ дает 4 пункта: A → •XYZ, A → X•YZ, A → XY•Z и A → XYZ•. ►

Базисным называется пункт с точкой не у левого края правой части правила, а также пункт S' → •S в расширенной грамматике.

Замыканием множества пунктов I (обозначается closure(I)) называется наименьшее множество пунктов, содержащее I в качестве подмножества такое, что для всякого пункта A → α•Bβ∈ I и любого правила B → γ пункт B → •γ лежит в closure(I).

Для пары (I,X), где I некоторое множество пунктов грамматики G, а X – символ грамматики (терминал или нетерминал), определим функцию goto(I,X) – замыкание множества всех пунктов A → αX•β таких, что A → α•Xβ ∈ I.

Рассмотрим расширенную грамматику G' = (T,N',P',S'), где N' = N∪{S'}, P = P∪{S' → S}. Пусть I0 = closure({S' → •S}). Начиная с I0, строится система множеств пунктов I0,...,IN так, что для всякой пары (Ik,X), где k = 0,...,N и X – символ грамматики, существует индекс j = 0,...,N такой, что goto(Ik,X) = Ij. Эта система пунктов называется канонической системой множеств пунктов. Используя каноническую систему I0,...,IN, можно построить конечный автомат V, распознающий активные префиксы, если в качестве состояний sj взять канонические множества Ij, а переходы задать с помощью функции goto.

Широко известны два класса алгоритмов синтаксического анализа: LL-анализ и LR-анализ (см. [5]). LL-анализатор с помощью диаграммы переходов или таблицы разбора строит левый вывод предложения целевого языка. Нерекурсивная реализация LL-анализатора использует стек и таблицу разбора. Изначально в стеке находится символ конца строки $ и стартовый символ грамматики. На каждом шаге рассматривается символ на вершине стека X и текущий входной символ a. Действия анализатора определяются этими двумя символами:

  • если X = a = $, то анализатор прекращает работу и сообщает об успешном завершении разбора;
  • если X = a ≠ $, анализатор удаляет из стека символ X и переходит к следующему символу входного потока;
  • если X является нетерминалом, анализатор ищет такую альтернативу раскрытия символа X, для которой символ a является допустимым первым символом. После того, как требуемая альтернатива найдена, символ X в стеке заменяется обратной последовательностью символов альтернативы. Например, если искомая альтернатива X → ABC, то анализатор заменит X на вершине стека на последовательность CBA, т.е. на вершине стека окажется символ A. Конфликты, возникающие в процессе поиска альтернатив, могут разрешаться, например, с помощью “заглядывания вперед”, т.е. просмотра нескольких входных символов вместо одного.
Анализатор завершает работу, когда на вершине стека оказывается символ конца строки $.

Рассмотрим теперь LR-анализатор, построенный на основе стека. У такого LR-анализатора имеются две основные операции:

  • перенос символа из входного потока в стек;
  • свертка нескольких последовательных символов на вершине стека в некоторый нетерминал.
Работа анализатора происходит так, что в стеке все время находится активный префикс некоторой правосентенциальной формы. При переносе символа и свертке на вершину стека кладется символ состояния sj конечного автомата V, кодирующий текущий активный префикс. LR-анализатор принимает решение о переносе или свертке, исходя из пары (символ sj, текущий токен входного потока). Анализатор завершает работу, когда в стеке оказывается стартовый символ грамматики.

2. Описание методики

2.1 Позитивные и негативные тесты для синтаксического анализатора
В данной работе парсером мы называем булевскую функцию, заданную на множестве последовательностей токенов и принимающую значение “истина”, если последовательность является предложением данного формального языка, и “ложь” – иначе. Конечно, реальные парсеры могут иметь дополнительную функциональность (например, помимо булевского значения выдавать дерево разбора или идентификацию ошибки), но здесь мы такую функциональность не рассматриваем.

Позитивный тест для парсера – это последовательность токенов, на которой парсер выдает вердикт “истина”, т.е. последовательность токенов, являющаяся предложением целевого языка.

Негативный тест для парсера – это последовательность токенов, на которой парсер выдает вердикт “ложь”, т.е. последовательность токенов, не являющаяся предложением целевого языка.

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

Рассмотрим грамматику G = (T ,N,P,S). Для каждого грамматического символа X ∈T ∪N, определим множество UX вхождений символа X в грамматику G. Это множество состоит из всех пар

(правило p ∈P, номер i символа в правиле p)

таких, что символ, стоящий на i-ом месте в правой части правила p является грамматическим символом X. Пару (p,i) ∈UX будем называть вхождением символа X в правило p.

Пусть t – токен. Для каждого вхождения u ∈Ut, u = (p,i), p = X → αtβ токена t в грамматику G можно построить множество Fu токенов t'∈T таких, что существует вывод

Здесь греческие буквы обозначают некоторые субсентенциальные формы, т.е. последовательности нетерминалов и токенов. Если в грамматике G существует вывод SγXγαt предложения, оканчивающегося токеном t, то будем считать, что множество Fu содержит пустую последовательность ε ∈Fu.

Через Ft будем обозначать объединение множеств Fu для токена t:

Иными словами, множество Ft – это множество токенов, каждый из которых допустим для токена t в качестве следующего.

В дальнейшем нас главным образом будет интересовать дополнение к множеству Ft в множестве T ∪{ε}. Будем обозначать это дополнение через

Теорема 1. Последовательность токенов, содержащая подпоследовательность tt', где t'∈ t, не является предложением языка, описываемого грамматикой G.

Доказательство. Очевидно из построения множества t. ►

Для последовательности токенов α = t1...tn такой, что существует вывод Sβαγ, можно определить множество токенов такое, что если t'∈ , то не существует вывода Sβαt'γ. Тогда любая последовательность βαt'γ, где t'∈ , не является предложением языка, описываемого грамматикой G.

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

2.2 Критерии покрытия
Как видно из описания LL- и LR-анализаторов, основной момент их работы – принятие решения о дальнейших действиях на основании некоторых неполных данных (прочитанной части входного потока). Для LL-анализатора ситуации выбора соответствует пара (нетерминал на вершине стека, текущий входной символ), а для LR-анализатора – пара (символ состояния конечного автомата на вершине стека, текущий входной символ). Отсюда возникают следующие критерии покрытия для позитивных тестовых наборов:

(PLL)     Покрытие всех пар

(нетерминал A, допустимый следующий токен t),

где пара (A,t) считается покрытой тогда и только тогда, когда в тестовом наборе существует последовательность токенов, являющаяся предложением целевого языка, имеющая вывод SαAβαtγβ. Иными словами, LL-анализатор, обрабатывая эту последовательность, получит ситуацию, когда на вершине стека будет находиться символ A, а текущим входным символом будет токен t. Модификация этого критерия для расширенной формы BNF грамматики была сформулирована в работе [1].

(PLR)     Покрытие всех пар

(символ si состояния конечного автомата, помеченный символом X переход из состояния si),

где пара (si,X) считается покрытой тогда и только тогда, когда в тестовом наборе существует предложение языка, имеющее вывод     SαXβ такой, что префикс α отвечает состоянию si. Или, что то же самое, LR-анализатор, обрабатывая это предложение получит ситуацию, когда на вершине стека будет находиться символ si, а началом текущего входного потока будет последовательность токенов, отвечающая символу X.Аналогично возникают следующие критерии покрытия и для негативных тестовых наборов (эти критерии имеют параметр r – количество “правильных” токенов, предшествующих “неправильному” токену):  

(NLLR)   Пусть A – нетерминал. Последовательность токенов t1...tr назовем допустимой для A предпоследовательностью токенов, если существует сентенциальная форма αt1...trAβ, выводимая из стартового правила. Рассмотрим объединение множеств t1...tr по всем допустимым для A предпоследовательностям токенов длины r < R. Критерий состоит в том, что все пары (A,t'), где t' из рассмотренного объединения, должны быть покрыты. Здесь покрытие пары (A,t') означает, что среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая, что LL-анализатор, обрабатывая эту последовательность, получит ситуацию, когда на вершине стека будет находиться символ A, а текущим входным символом будет “некорректный” символ t'.

(NLRR)   Пусть si – символ состояния конечного автомата, определяющего активные префиксы. Последовательность токенов t1...tr назовем допустимой для si предпоследовательностью токенов, если существует выводимая из стартового правила последовательность токенов αt1...trβ такая, что ее префикс αt1...tr отвечает состоянию si. Рассмотрим объединение множеств t1...tr по всем допустимым для si предпоследовательностям токенов длины r < R. Критерий состоит в том, что все пары (si,t'), где t' из рассмотренного объединения, должны быть покрыты. Здесь покрытие пары (si,t') означает, что среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая, что LR-анализатор, обрабатывая эту последовательность получит ситуацию, когда на вершине стека будет находиться символ si, а текущим входным символом будет t'.

Для получения ситуации (A,t') в критерии (NLL) или ситуации (si,t') в критерии (NLR) требуется, чтобы парсер нормально проработал какое-то время, а затем встретил неверный символ. Для достижения этой цели необходимо, чтобы токены, идущие в последовательности до неверного токена t', образовывали префикс некоторого предложения языка, при разборе которого возникала бы требуемая ситуация в стеке. Поэтому в качестве негативного теста мы будем рассматривать измененное (с помощью вставки или замены токенов) предложение целевого языка так, чтобы в нем содержалась неправильная последовательность токенов t1...trt', где t'∈ t1...tr.2

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

Пусть грамматика G такова, что ее каноническая система множеств пунктов удовлетворяет следующему свойству: если Ii и Ij – два различных множества из канонической системы, то множества базисных пунктов из Ii и Ij не пересекаются. Заметим, что для такой грамматики покрытие всех пар (состояние конечного автомата, переход из этого состояния в другое) достигается при покрытии всех пунктов грамматики. Рассмотрим следующий критерий покрытия для наборов позитивных тестов:

(WPLR)  Покрытие всех пар (пункт π = B → α•Xβ грамматики G, допустимый первый токен t для символа X). Пара (π,t) считается покрытой тогда и только тогда, когда в тестовом наборе существует предложение языка, имеющее вывод SγBδγαXβδγαtμβδ.

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

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

(WNLRR) Пусть π = B → α•β – пункт грамматики G. Последовательность токенов t1...tr назовем предпоследовательностью токенов допустимой для π, если существует выводимая из стартового правила последовательность токенов μt1...tr•λ, имеющая вывод


               т.е. μt1...tr выводится из γα, а λ – из βδ. Рассмотрим объединение множеств t1...tr по всем допустимым для π предпоследовательностям токенов длины r < R. Критерий состоит в том, что все пары (π,t'), где t' из рассмотренного объединения, должны быть покрыты. Здесь покрытие пары (π,t') означает, что среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая, что некоторый ее префикс имеет вид μt1...trt', где t1...tr – некоторая допустимая для π предпоследовательность токенов такая, что t'∈ t1...tr.

Сноски

1 В общих словах мутационное тестирование состоит в следующем. Из тестируемого компонента получают множество его модификаций (мутантов), каждая из которых содержит ровно одну ошибку. Говорят, что мутант убит, если на некоторых входных данных его выход отличен от выхода исходной программы. Если имеется множество тестовых входных данных для программы, то с помощью мутационного анализа (mutation analysis) можно оценить качество этих тестов. Именно, если имеется множество мутантов, то критерий покрытия говорит, что все мутанты должны быть убиты. В случае синтаксического анализатора логично в качестве мутируемого материала рассматривать грамматику языка, т.к. ошибочный анализатор фактически распознает другой язык. В этом случае грамматика-мутант будет убита, если найдется последовательность токенов, принадлежащая языку, задаваемому этой грамматикой-мутантом и не принадлежащая исходному языку (в терминах анализаторов это как раз будет означать, что анализатор-мутант распознал данное предложение, а исходный анализатор – нет, т.е. анализатор-мутант оказался убитым).

2 Существует связь между предлагаемым подходом и методом мутационного тестирования. Именно, для любой последовательности токенов, являющейся негативным тестом в описанном выше смысле (т.е. предложением языка, “испорченным” с помощью вставки/замены “нехорошего” токена) можно построить грамматику-мутант такую, что данный негативный тест будет являться предложением языка, описываемого этой грамматикой-мутантом. Одним из принципов мутационного тестирования является так называемый эффект взаимосвязи (coupling effect): при обнаружении простых ошибок будут обнаруживаться и более сложные (см. [16]). Согласно этому эффекту взаимосвязи, мутации должны быть простыми. Заметим, что предлагаемый подход вполне согласуется с этим принципом.

Продолжение

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в 21 локации

От 104 рублей в месяц

Безлимитный трафик. Защита от ДДоС.

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...