Тестирование софта - статьи


         

Критерии полноты тестирования


Мы рассматриваем известные алгоритмы синтаксического анализа (LL-анализ и LR-анализ, построенные на основе стека - см. []) в качестве алгоритмов, моделирующих поведение парсера.

Критерий полноты набора позитивных тестов для тестирования LL-анализатора:

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

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

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

Критерий полноты набора позитивных тестов для тестирования LR-анализатора:

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

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

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

Критерий полноты набора негативных тестов для тестирования LL-анализатора:

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

          (нетерминал A; «некорректный» токен t'),

где пара (A, t') считается покрытой тогда и только тогда, когда среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая что LL-анализатор, обрабатывая эту последовательность, придет в ситуацию, когда после обработки как минимум R «правильных» токенов, на вершине стека будет находиться символ A, а текущим входным символом будет «некорректный» токен t'.

Критерий полноты набора негативных тестов для тестирования LR-анализатора:

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

     (символ s состояния конечного автомата; «некорректный» токен t'),

где пара (s, t') считается покрытой тогда и только тогда, когда среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая, что LR-анализатор, обрабатывая эту последовательность, придет в ситуацию, когда после обработки как минимум R «правильных» токенов, на вершине стека будет находиться символ s, а текущим входным символом будет «некорректный» токен t'.

Существует семейство алгоритмов генерации тестов, удовлетворяющих этим критериям. Их подробное описание можно найти в работе [].

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

Разработан инструмент SynTesK [], в котором реализованы алгоритмы, удовлетворяющие критериям PLL и NLL1, а также критерию NLR1 для некоторого специального вида грамматик [].

Инструмент SynTesK успешно применялся для тестирования компиляторов реальных языков программирования, в т.ч. C и Java []. Практические результаты этого применения показали эффективность реализованных в SynTesK алгоритмов.

Содержание  Назад  Вперед