Лекции. Тестирование ПО (all in one) (1186159), страница 28
Текст из файла (страница 28)
Лекцию 6).Как и в ранее описанных методах, необходимо для каждого перехода, однозначноопределяемого своими начальным состоянием и стимулом, выполнить его, проверитькорректность реакции, а затем проверить корректность его конечного состояния.Чтобы выполнить все переходы, используется reset и покрывающее множество.Покрывающее множество (или базис достижимости) C для конечного автомата — этоминимальное такое множество входных последовательностей, что вместе с каждойпоследовательностью оно содержит все ее начала и позволят из начального состоянияпопасть в любое состояние автомата. То есть, #C = #S & ∀αa ∈ C α ∈ C & ∀s ∈ S ∃α ∈ C s =δ(s0, α).
(Здесь # обозначает число элементов в множестве).a/xa/xb/x0a/x10b/xb/y1b/yb/ya/ya/xb/y2a/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 = W, W1 = {b}, W2 = {a}.•Первый шаг дает тест RaRbRbaRbbRbbaRbbb/x.y.yy.yy.yyx.yyx.На втором шаге требуется проверить только переходы по стимулу a и переход по стимулуb в состоянии 1. Получаем RaaRabRbaaRbbabRbbbaRbbbb/xx.xy.yyy.yyxx.yyxx.yyxy.Полный тест выглядит следующим образом: RaRbRbaRbbRbbaRbbbRaaRabRbaaRbbabRbbbaRbbbb/x.y.yy.yy.yyx.yyx.xx.xy.yyy.yyxx.yyxx.yyxy.Результат его выполнения для приведенной выше ошибочной реализации:x.y.yy.yy.yyx.yyx.xx.xx.yyy.yyxx.yyxx.yyxy.В том случае, когда N > n, в Wp-методе добавляются дополнительные шаги, а именно.На (i+1)-ом шаге для 2<= i < N-n+2 для каждой цепочки переходов длины i, которая небыла проверена на одном из предудущих шагов (поскольку начало некоторых цепочеклежит на C), надо пройти по последовательности из C в начало этой цепочки,выполнить эту цепочку, а потом проверить ее конечное состояние при помощи егоидентифицирующего множества.Если у каждого состояния автомата есть 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 тестирование автоматов становитсянесколько сложнее.
Существуют методы, позволяющие построить тесты для произвольнойдетерминированной полностью определенной сильно связной спецификации, но размерполучаемых тестов может быть достаточно велик. Такие методы используют установочныепоследовательности (homing sequences).Рассмотрим здесь только один метод, работающий без reset, и предполагающий? Чтоспецификация обладает различающей последовательностью d.Поскольку спецификационный автомат сильно связен, для каждой пары его состояний s1и s2 существует переводящая последовательность стимулов t(s1, s2), выполнение которой в s1переводит автомат в состояние s2.Обозначим для каждого i >= 0 через si’ итоговое состоянием после выполнения d в si.Тогда тест d t(s0’, s1) d t(s1’,s2) d … d t(sn–2’,sn–1) d проверяет, что в реализации для каждогосостояния спецификации есть подобное, в котором d дает ту же последовательность реакций.Чтобы после этого проверить, что некоторый переход работает правильно, нужно перейтив начало перехода si, выполнить его и выполнить d.
Ошибки в реализации могут привести нев начало этого перехода, в другое место. Однако, мы уже знаем, что последовательностьdt(si–1’, si), будучи применена в состоянии si–1, во-первых, проверит, что это действительнотакое состояние с помощью d, а во-вторых, приведет после этого в si уже провереннымспособом. Поэтому, попав в некоторое состояние s, для еще не проверенного перехода si –a->s’ выполним t(s, si–1) d t(si–1’, si) a d.Получаемая таким образом последовательность обеспечит проверку всех переходов.Построим такой тест для нашего примера спецификации.a/xa/xb/x0a/x10b/xb/y1b/yb/ya/ya/xb/y2a/y2Имеем d = ab, s0’ = s2, s1’ = s0, s2’ = s1. Если мы будем обходить состояния в порядке s0-s2s1, то переводящие последовательности пусты.
Поэтому первый этап дает abababab, и в егоконце мы оказываемся в состоянии s2.Далее будем проверять переходы в следующем порядке: 1-a->1, 2-a->2, 0-a->0, 1-b->0, 0b->2, 2-b->1. В этом случае промежуточные переводящие последовательности пусты, заисключением двух последних случаев, поэтому на втором этапе получаем такую входнуюпоследовательность: abaab.abaab.abaab.abbab.babbab.babbab.Итоговый тест:abababab.abaab.abaab.abaab.abbab.babbab.babbab/xyyyxxxy.yyxxx.xyyyy.xxxxy.yyxxy.yxxyyy.xxyyxx.Результат, возвращаемый ошибочной реализацией: xxxxxxxx…, после этого тестированиеможно не продолжать.В этом примере многие ошибки могут быть найдены уже на первом этапе, поскольку вполученную на нем последовательность входят все переходы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
