Lecture07 (Лекции в ПДФ)

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

Реализациянеизвестна, известно только, что это конечный автомат, удовлетворяющий ряду условий.Задача состоит в построении как можно более компактного набора тестов — входныхпоследовательностей (и соответствующих им в спецификации выходных), — позволяющихотличить реализацию от спецификации всякий раз, когда они не эквивалентны.Соответственно, если поведение реализации на этом наборе тестов не будет отличаться отповедения спецификации, можно быть уверенным, что они эквивалентны.На спецификацию и реализацию накладываются дополнительные ограничения.Спецификация•детерминирована;•минимальна;•полностью определена;сильно связна или имеет действие reset(R), достоверно приводящее из любогосостояния в начальное.От реализации требуется•детерминизм;•полная определенность;•сильная связность или наличие reset;•согласованность стимулов и реакций со спецификацией — входной и выходнойалфавиты реализации те же;•согласованность начального состояния — в начале работы реализация находится вначальном состоянии;•ограниченность — число состояний в реализации не превосходит некоторого числаN.•Методы, использующие resetМетоды построения тестов, рассматриваемые ниже, условно можно разделить наодношаговые или однофазные и многошаговые.

В первых все тесты строятся по одной и тойже общей процедуре, а вторые используют несколько разных процедур или шагов.Одношаговые методыПервый метод построения тестов для автоматов без специальных действий set или statusбыл разработан в 1973 Василевским [3]. Его более понятное изложение на английском языкеприведено в статье Chow [4], поэтому большинство англоязычных авторов дают ссылки наэту статью. В статье Chow этот метод назван W-методом в честь Василевского.Без действия status проверить, что некоторый переход в реализации ведет в состояние,эквивалентное конечному состоянию соответствующего перехода в спецификации,становится не так просто.

W-метод использует для этого диагностическое множество W,которое имеется для каждого минимального детерминированного полностью определенногоавтомата (см. Лекцию 6).Как и в ранее описанных методах, необходимо для каждого перехода, однозначноопределяемого своими начальным состоянием и стимулом, выполнить его, проверитькорректность реакции, а затем проверить корректность его конечного состояния.Чтобы выполнить все переходы, используется reset и покрывающее множество.Покрывающее множество (или базис достижимости) C для конечного автомата — этоминимальное такое множество входных последовательностей, что вместе с каждойпоследовательностью оно содержит все ее начала и позволят из начального состоянияпопасть в любое состояние автомата.

То есть, #C = #S & ∀αa ∈ C α ∈ C & ∀s ∈ S ∃α ∈ C s =δ(s0, α). (Здесь # обозначает число элементов в множестве).a/xa/xb/x0a/x10b/y2b/xb/yb/ya/ya/x1b/ya/y2Для автомата, изображенного слева, покрывающим множеством является {ε, b, bb}.Если число состояний в реализации не превосходит числа состояний в спецификации, т.е.N = n, W-метод действует так.•В каждом тесте первым действием является reset, затем идет какая-нибудь изпоследовательностей из покрывающего множества (так мы оказываемся впроизвольном состоянии), затем идет любой стимул (так выполняется произвольныйпереход), затем выполняется одна из последовательностей диагностическогомножества W. Чтобы проверить все переходы, нужно после каждого из нихвыполнить все последовательности из W.Другими словами этот метод можно записать так: строятся все входныепоследовательности из конкатенации множеств CIW, перед каждой из нихвставляется R и все полученные последовательности конкатенируются.Построим набор тестов для изображенного выше слева автомата с помощью W-метода.В рассматриваемом автомате C = {ε, b, bb}, I = {a, b}, W = {a, b}.

Значит, IW = {aa, ab, ba,bb}, и поэтому {R}CIW = RaaRabRbaRbbRbaaRbabRbbaRbbbRbbaaRbbabRbbbaRbbbb.Корректная последовательность реакций:xx.xy.yy.yy.yyy.yyy.yyx.yyx.yyxx.yyxx.yyxx.yyxy.Если с помощью этого теста проверять реализацию, изображенную выше справа, будетполучен следующий результат — xx.xx.yy.yy.yyy.yyy.yyx.yyx.yyxx.yyxx.yyxx.yyxy.Полученная ошибка выделена красным цветом.Для произвольного N >= n W-метод строит набор тестов {R}CIN–n+1W.

То есть,вместо однократных стимулов при построении всех возможных переходовиспользуются все возможные последовательности стимулов длины N–n+1.W-метод может быть применен для произвольной детерминированной полностьюопределенной спецификации, однако он дает достаточно большой набор тестов. Для•сокращения размеров тестов можно использовать другие способы идентификации состояний(см. Лекцию 6), например, UIO-последовательности и различающие последовательности.D-метод применяется для спецификаций, имеющих различающую последовательность d.Он полностью аналогичен W-методу, только вместо диагностического множества Wиспользуется различающая последовательность d.D-метод строит набор тестов {R}CIN–n+1d.Для уже рассматриваемой ранее спецификации существует различающаяпоследовательность d = ab. Поэтому построенный с помощью D-метода тест для N = nвыглядит так: RaabRbabRbaabRbbabRbbaabRbbbab/xxy.yyy.yyyy.yyxx.yyxxx.yyxxy.

Дляприведенной выше ошибочной реализации результат его выполнения выглядит так:xxx.yyy.yyyy.yyxx.yyxxx.yyxxx.В D-методе наряду со статической может также использоваться адаптивная различающаяпоследовательность.UIO-метод использует после каждого перехода вместо диагностического множестваUIO-последовательность конечного состояния этого перехода. Однако, UIO-метод негарантирует обнаружения всех ошибок — UIO-последовательности изменяются из-заошибок, и поэтому может существовать ошибочная реализация, в которой для ошибочногоконечного состояния одного из переходов UIO-последовательность дает корректныерезультаты.•Многошаговые методыДругим методом, позволяющим сократить размер тестов, является частичный W-методили Wp-метод. Он, в отличие от ранее представленных методов, выполняется в несколькошагов и использует идентифицирующие множества.Идентифицирующее множество (identification set) Ws для состояния s — такоемножество входных последовательностей, что для любого другого состояния автомата однаиз этих последовательностей дает результат, отличающийся от результата ее применения в s.То есть, ∀s1 ∈ S s1 ≠ s ⇒ ∃α ∈ Ws λ(s, α) ≠ λ(s1, α).В качестве идентифицирующего множества состояния всегда можно выбрать некотороеподмножество диагностического множества автомата.Шаги Wp-метода для N = n следующие.Сначала выполняются тесты {R}CW.

Их успешное выполнение гарантирует, что всесостояния реализации подобны состояниям спецификации, т.е. выдают те жерезультаты на все последовательности из W.•Каждый переход, не проверенный на предыдущем шаге, т.е. не покрытый привыполнении множества С, выполняется и проверяется с помощьюидентифицирующего множества своего конечного состояния.Построим набор тестов по Wp-методу для той же спецификации, изображенной выше.C = {ε, b, bb}, I = {a, b}, W = {a, b}, W0 = {ab}, W1 = {b}, W2 = {a}.

Здесь в качестве W0взято не подмножество W, а множество из одной последовательности, что позволяет немногосократить тест.•Первый шаг дает тест RaRbRbaRbbRbbaRbbb/x.y.yy.yy.yyx.yyx.На втором шаге требуется проверить только переходы по стимулу a и переход по стимулуb в состоянии 1. Получаем RaabRbaaRbbabRbbbab/xxy.yyy.yyxx.yyxxy.Полный тест выглядит следующим образом:RaRbRbaRbbRbbaRbbbRaabRbaaRbbabRbbbab/x.y.yy.yy.yyx.yyx.xxy.yyy.yyxx.yyxxy.Результат его выполнения для приведенной выше ошибочной реализации:x.y.yy.yy.yyx.yyx.xxx.yyy.yyxx.yyxxx.Если у каждого состояния автомата есть UIO-последовательность, можно использоватьUIOv-метод, гарантирующий, в отличие от UIO-метода, обнаружение всех ошибок.UIOv-метод получается из Wp-метода заменой W на множество, содержащее UIOпоследовательности всех состояний, а Ws — на UIO-последовательность состояния s.В нашем примере полный тест по UIOv-методу выглядит так:RaRbRabRbaRbbRbabRbbaRbbbRbbabRaabRbaaRbbabRbbbab/x.y.xy.yy.yy.yyy.yyx.yyx.yyxx.xxy.yyy.yyxx.yyxxy.Сложность тестов в общем случае и их минимизацияНесмотря на то, что D-метод и Wp-метод обычно строят тесты, меньшие по размерам,чем W-метод, их сложность в общем случае описывается иначе.В общем случае размер и сложность вычисления тестов по W-методу или Wp-методуодинакова и равна по порядку O(pN-n+1n3) (O(pn3) для N = n).

Эта оценка не может бытьулучшена — существуют спецификации, которые нельзя отличить от всех ошибочныхреализаций с N состояниями с помощью набора тестов, имеющего размер меньше, чемO(pN-n+1n3).Поскольку длина различающей последовательности может быть экспоненциальной отчисла состояний, сложность D-метода в общем случае тоже экспоненциальная.Для каждого конкретного случая можно, однако, сокращать размер тестов, построенныхэтими методами. Основное правило, которое используется при сокращении — если началоодно из элементарных тестов (последовательностей, заключенных между двумя reset’-ами)совпадает с другим элементарным тестом, то второй элементарный тест можно выбросить.Ясно, что в этом случае ошибка, обнаруживаемая выбрасываемым тестом всегдаобнаруживается более длинным тестом.Рассмотрим все полученные для нашего примера тесты.•W-метод.RaaRabRbaRbbRbaaRbabRbbaRbbbRbbaaRbbabRbbbaRbbbb.Сокращение даетRaaRabRbaaRbabRbbaaRbbabRbbbaRbbbb.•D-метод.RaabRbabRbaabRbbabRbbaabRbbbab.Сократить нельзя.•Wp-метод.RaRbRbaRbbRbbaRbbbRaabRbaaRbbabRbbbab.Сокращение даетRaabRbaaRbbabRbbbab.•UIOv-метод.RaRbRabRbaRbbRbabRbbaRbbbRbbabRaabRbaaRbbabRbbbab.Сокращение даетRbabRaabRbaaRbbabRbbbab.Таким образом, в этом примере эквивалентность любой реализации с не более чем 3-мясостояниями может быть проверена с помощью тестаRaabRbaaRbbabRbbbab/xxy.yyy.yyxx.yyxxy.Методы, не использующие resetПри отсутствии надежно работающей операции reset тестирование автоматов становитсянесколько сложнее.