Одним из недостатков анализа граничных значений и эквивалентного разбиения является то, что они не исследуют комбинаций входных условий. Например, пусть программа MTEST из предыдущего раздела не выполняется, если произведение числа вопросов и числа студентов превышает некоторый предел (например, объем памяти). Такая ошибка не обязательно будет обнаружена тестированием граничных значений.
Тестирование комбинаций входных условий — непростая задача, поскольку даже при построенном эквивалентном разбиении входных условий число комбинаций обычно астрономически велико. Если нет систематического способа выбора подмножества входных условий, то, как правило, выбирается произвольное подмножество, приводящее к неэффективному тесту.
Метод функциональных диаграмм или диаграмм причинно-следственных связей помогает систематически выбирать тесты с высокой результативностью. Он дает полезный побочный эффект, так как позволяет обнаруживать неполноту и неоднозначность исходных спецификаций.
Функциональная диаграмма представляет собой формальный язык, на который транслируется спецификация, написанная на естественном языке. Диаграмме можно сопоставить цифровую логическую цепь (комбинаторную логическую сеть), но для ее описания используется более простая нотация (форма записи), чем обычная форма записи, принятая в электронике. Для уяснения метода функциональных диаграмм вовсе не обязательно знание электроники, но желательно понимание булевской логики (т.е. логических операторов и, или и не). Построение тестов этим методом осуществляется в несколько этапов.
1. Спецификация разбивается на «рабочие» участки. Это связано с тем, что функциональные диаграммы становятся слишком громоздкими при применении данного метода к большим спецификациям. Например, когда тестируется система разделения времени, рабочим участком может быть спецификация отдельной команды. При тестировании компилятора в качестве рабочего участка можно рассматривать каждый отдельный оператор языка программирования.
2. В спецификации определяются причины и следствия. Причина есть отдельное входное условие или класс эквивалентности входных условий. Следствие есть выходное условие или преобразование системы (остаточное действие, которое входное условие оказывает на состояние программы или системы). Например, если сообщение программе приводит к обновлению основного файла, то изменение в нем и является преобразованием системы; подтверждающее сообщение было бы выходным условием. Причины и следствие определяются путем последовательного (слово за словом) чтения спецификации. При этом выделяются слова или фразы, которые описывают причины и следствия. Каждым причине и следствию приписывается отдельный номер.
3. Анализируется семантическое содержание спецификации, которая преобразуется в булевский граф, связывающий причины и следствия. Это и есть функциональная диаграмма.
4. Диаграмма снабжается примечаниями, задающими ограничения и описывающими комбинации причин и (или) следствий, которые являются невозможными из-за синтаксических или внешних ограничений.
5. Путем методического прослеживания состояний условий диаграммы она преобразуется в таблицу решений с ограниченными входами. Каждый столбец таблицы решений соответствует тесту.
6. Столбцы таблицы решений преобразуются в тесты.
Базовые символы для записи функциональных диаграмм показаны на рис. 6.9.
Рис. 6.9 — Базовые логические отношения функциональных диаграмм
Каждый узел диаграммы может находиться в двух состояниях — 0 или 1; 0 означает состояние «отсутствует», а 1 — «присутствует». Функция тождество устанавливает, что если значение a есть 1, то и значение b есть 1; в противном случае значение b есть 0. Функция не устанавливает, что если a есть 1, то b есть 0; в противном случае b есть 1. Функция или устанавливает, что если a, или b, или c есть 1, то d есть 1; в противном случае d есть 0. Функция и устанавливает, что если d и b есть 1, то и c есть 1; в противном случае c есть 0. Последние две функции разрешают иметь любое число входов.
Для иллюстрации изложенного рассмотрим диаграмму, отображающую спецификацию:
Символ в колонке 1 должен быть буквой «А» или «В», а в колонке 2 — цифрой. В этом случае файл обновляется. Если первый символ неправильный, то выдается сообщение Х12, а если второй символ неправильный — сообщение X13.
Причинами являются: 1 — символ «А» в колонке 1; 2 — символ «В» в колонке 1; 3 — цифра в колонке 2, а следствиями — 70 — файл обновляется; 71 — выдается сообщение Х12; 72 — выдается сообщение X13.
Функциональная диаграмма показана на рис. 6.10. Отметим, что здесь создан промежуточный узел 11.
Рис. 6.10 — Пример функциональной диаграммы
На рис. 6.11 показана эквивалентная логическая схема.
Рис. 6.11 — Логическая схема, эквивалентная диаграмме на рис. 6.10
Хотя диаграмма отображает спецификацию, она содержат невозможную комбинацию причин — причины 1 и 2 не могут быть установлены в 1 одновременно. В большинстве программ определенные комбинации причин невозможны из-за синтаксических или внешних ограничений (например, символ не может принимать значения «А» и «В» одновременно).
Рис. 6.12 — Символы ограничений
В этом случае используются дополнительные логические ограничения, изображенные на рис. 6.12. Ограничение E устанавливает, что E должно быть истинным, если хотя бы одна из причин — a или b — принимает значение 1 (a и b не могут принимать значение 1 одновременно). Ограничение I устанавливает, что, по крайней мере, одна из величин a, b или c всегда должна быть равной 1 (a, b и c не могут принимать значение 0 одновременно). Ограничение O устанавливает, что одна и только одна из величин a или b должна быть равна 1. Ограничение R устанавливает, что если a принимает значение 1, то и b должно быть равно 1 (т.е. невозможно, чтобы a было равно 1, а b — 0).
Рис. 6.13 — Символ для скрытого ограничения
Часто возникает необходимость в ограничениях для следствий. Ограничение M на рис. 6.13 устанавливает, что если следствие a имеет значение 1, то следствие b должно иметь значение 0.
Как видно из рассмотренного выше примера, физически невозможно, чтобы причины 1 и 2 присутствовали одновременно, но возможно, чтобы присутствовала одна из них. Следовательно, они связаны ограничением E (рис. 6.14.).
Рис. 6.14 — Пример функциональной диаграммы с ограничением «исключает»
Проиллюстрируем использование функциональных диаграмм для получения тестов. С этой целью воспользуемся спецификацией на команду отладки в интерактивной системе.
Команда DISPLAY используется для того, чтобы отобразить на экране распределение памяти. Синтаксис команды показан на рис. 6.15. Скобки представляют альтернативные необязательные операнды. Прописные буквы обозначают ключевые слова операндов, а буквы с предшествующими точками — значения операндов (т.е. действительные значения операндов, которые должны быть подставлены). Подчеркнутые операнды соответствуют стандартным значениям (т.е. если операнд опущен, то принимается стандартное значение).
Рис. 6.15 — Синтаксис команды DISPLAY
Первый операнд (адрес 1) определяет адрес первого байта области памяти, содержимое которой должно быть отображено на экран. Длина адреса задается 1—6 шестнадцатеричными цифрами (0—9, А—F). Если первый операнд не определен, то предполагается, что адрес равен 0. Адрес должен принимать значение из действительной области памяти машины.
Второй операнд определяет объем памяти, который должен быть отображен. Если адрес 2 определен, то он, в свою очередь, определяет адрес последнего байта области памяти, которую необходимо отобразить на экран. Длина этого адреса задается также 1—6 шестнадцатеричными цифрами. Он должен быть больше или равен начальному адресу (адрес 1). Аналогично, адрес 2 обязан принимать значения из действительной области памяти машины. Если в качестве второго операнда определено END, то память отображается до последнего действительного адреса машины. Если же в качестве операнда определен счетчик байтов, то он, в свою очередь, определяет число байтов памяти, которые нужно отобразить (начиная с байта с адресом адрес 1). Операнд счетчик байтов является шестнадцатеричным целым числом (длиной от одной до шести цифр). Сумма значений операндов счетчик байтов и адрес 1 не должна превышать действительного размера памяти плюс единица, а счетчик байтов должен, по крайней мере, иметь значение 1. Состояние памяти отображается на экран терминала в виде одной или нескольких строк следующего формата:
хххххх = слово 1 слово 2 слово 3 слово 4,
где хххххх есть шестнадцатеричный адрес слова 1.
Всегда отображается полное число слов (четырехбайтовых последовательностей, где адрес первого байта в слове кратен четырем), независимо от значения операнда адрес 1 или отображаемого объема памяти. Все выходные строки всегда содержат четыре слова (16 байт). Первый байт отображаемой области памяти находится в пределах первого слова.
Могут иметь место следующие сообщения об ошибках:
M1 – НЕПРАВИЛЬНЫЙ СИНТАКСИС КОМАНДЫ
M2 – ЗАПРАШИВАЕТСЯ АДРЕС, БОЛЬШИЙ ДОПУСТИМОГО
MЗ – ЗАПРАШИВАЕТСЯ ОБЛАСТЬ ПАМЯТИ С НУЛЕВЫМ ИЛИ
ОТРИЦАТЕЛЬНЫМ АДРЕСОМ
Примеры команды DISPLAY:
DISPLAY
отображает первые четыре слова в памяти (стандартное значение начального адреса 0, а стандартное значение счетчика байтов 1).
DISPLAY 77F
отображает слово, содержащее байт с адресом 77F, и три последующих слова.
DISPLAY 77F – 407A
отображает слова, содержащие байты с адресами от 77F до 407А.
DISPLAY 77F.6
отображает слова, содержащие шесть байт, начиная с адреса 77F.
DISPLAY 50FF – END
отображает слова, содержащие байты с адреса 50FF до конца памяти.
Первый шаг заключается в тщательном анализе спецификации с тем, чтобы идентифицировать причины и следствия. Причинами являются:
1. Наличие первого операнда.
2. Операнд адрес 1 содержит только шестнадцатеричные цифры.
3. Операнд адрес 1 содержит от одного до шести символов.
4. Операнд адрес 1 находится в пределах действительной области памяти.
5. Второй операнд есть END.
6. Второй операнд есть адрес 2.
7. Второй операнд есть счетчик байтов.
8. Второй операнд отсутствует.
9. Операнд адрес 2 содержит только шестнадцатеричные цифры.
10. Операнд адрес 2 содержит от одного до шести символов.
11. Операнд адрес 2 находится в пределах действительной области памяти.
12. Операнд адрес 2 больше или равен операнду адрес 1.
13. Операнд счетчик байтов содержит только шестнадцатеричные цифры.
14. Операнд счетчик байтов содержит от одного до шести символов.
15. Счетчик байтов + адрес 1 £ размер памяти + 1.
16. Счетчик байтов ³ 1.
17. Запрашиваемая область памяти настолько велика, что требуется много строк на экране.
18. Начало области не выровнено на границу слова.
Каждой причине соответствует произвольный единственный номер. Заметим, что для описания второго операнда необходимы четыре причины (5—8), так как второй операнд может принимать значения 1) END, 2) адрес 2, 3) счетчик байтов, 4) может отсутствовать и 5) неопределенное значение, т.е. ни одно из указанных выше.
Следствия:
91. На экран отображается сообщение M1.
92. На экран отображается сообщение M2.
93. На экран отображается сообщение M3.
94. Память отображается на одной строке.
95. Для отображения состояния памяти требуется много строк.
96. Первый байт отображаемой области памяти выровнен на границу слова.
97. Первый байт отображаемой области памяти не выровнен на границу слова.
Второй шаг — разработка функциональной диаграммы.
Узлы причин перечислены по вертикали у левого края страницы; узлы следствий собраны по вертикали у ее правого края. Тщательно анализируется семантическое содержание спецификации с тем, чтобы связать причины и следствия (т.е. показать, при каких условиях имеет место следствие).
На рис. 6.16 приведена начальная версия диаграммы. Промежуточный узел 32 представляет синтаксически правильный первый операнд, узел 35 — синтаксически правильный второй операнд, а узел 36 — синтаксически правильную команду. Если значение узла 36 есть 1, то следствие 91 (сообщение об ошибке) отсутствует. Если значение узла 36 есть 0, то следствие 91 имеет место.
На рис. 6.17 изображена полная функциональная диаграмма. Если диаграмму на рис. 6.17 непосредственно использовать для построения тестов, то создание многих из них на самом деле окажется невозможным. Это объясняется тем, что определенные комбинации причин не могут иметь место из-за синтаксических ограничений.
Рис. 6.16 — Начальная версия функциональной диаграммы команды DISPLAY
Например, причины 2 и 3 не могут присутствовать без причины 1. Причина 4 не может присутствовать, если нет причин 2 и 3. На рис. 6.18 показана окончательная диаграмма со всеми дополнительными ограничениям. Заметим, что может присутствовать только одна из причин 5, 6, 7 или 8. Другие ограничения причин являются условиями типа «требует». Причина 17 (много строк на экране) и причина 8 (второй операнд отсутствует) связаны отношением не; причина 17 может присутствовать только в отсутствии причины 8.
Рис. 6.17 — Полная функциональная диаграмма без ограничений
Рис. 6.18 — Окончательная функциональная диаграмма команды DISPLAY
Третьим шагом является генерация таблицы решений с ограниченными входами. В таблице решений причины есть условия, а следствия есть действия. Процедура генерации заключается в следующем:
1. Выбрать некоторое следствие, которое должно быть в состоянии 1.
2. Найти все комбинации причин (с учетом ограничений), которые установят это следствие в 1, прокладывая из этого следствия обратную трассу через диаграмму.
3. Построить столбец в таблице решений для каждой комбинации причин.
4. Для каждой комбинации причин определить состояния всех других следствий и поместить их в соответствующий столбец таблицы решений.
При выполнении этого шага необходимо руководствоваться тремя положениями:
1. Если обратная трасса прокладывается через узел или, выход которого должен принимать значение 1, то одновременно не следует устанавливать в 1 более одного входа в этот узел. Такое ограничение на установку входных значений называется чувствительностью пути. Цель данного правила — избежать пропуска отдельных ошибок из-за того, что одна причина маскируется другой.
2. Если обратная трасса прокладывается через узел и, выход которого должен принимать значение 0, то все комбинации входов, приводящие выход в 0, должны быть перечислены. Однако когда исследуется ситуация, где один вход есть 0, а один или более других входов есть 1, не обязательно перечислять все условия, при которых остальные входы могут быть 1.
3. Если обратная трасса прокладывается через узел и, выход которого должен принимать значение 0, то необходимо указать лишь одно условие, согласно которому все входы являются нулями. Когда узел и находится в середине графа и его входы исходят из других промежуточных узлов, может существовать чрезвычайно большое число ситуаций, при которых все его входы принимают значения 0.
Эти положения кратко поясняются рис. 6.19.
Рис. 6.19 — Положения, используемые при прокладке обратной трассы через диаграмму
Рис. 6.20 приведен в качестве примера функциональной диаграммы. Пусть требуется так задать входные условия, чтобы установить выходное состояние в 0. Согласно положению 3 следует рассматривать только один случай, когда узлы 5 и 6 — нули. По положению 2, для состояния, при котором узел 5 принимает значение 1, а узел 6 — значение 0, следует рассматривать только один случай, когда узел 5 принимает значение 1 (не перечисляя другие возможные случаи, когда узел 5 может принимать значение 1).
Аналогично для состояния, при котором узел 5 принимает значение 0, а узел 6 — значение 1, следует рассматривать только один случай, когда узел 6 принимает значение 1 (хотя в данном случае он является единственным). В соответствии с положением 1, если узел 5 должен быть установлен в состояние 1, то не рекомендуется устанавливать узлы 1 и 2 в состояние 1 одновременно. Таким образом, возможны пять состояний узлов 1—4, например значения
0 0 0 0 (5 = 0, 6 = 0),
1 0 0 0 (5 = 1, 6 = 0),
1 0 0 1 (5 = 1, 6 = 0),
1 0 1 0 (5 = 1, 6 = 0),
0 0 1 1 (5 = 0, 6 = 1),
а не 13, которые приводят к выходному состоянию 0.
Рис. 6.20 — Пример функциональной диаграммы для иллюстрации обратной трассировки
На первый взгляд, эти положения могут показаться необъективными, но они преследуют важную цель: уменьшить комбинаторику диаграммы. Их применение позволяет избежать ситуаций, которые приводят к получению малорезультативных тестов. Если не исключать малорезультативные тесты, то общее число тестов, порождаемых по большой функциональной диаграмме, получается астрономическим. Если же и без них число тестов все еще оказывается большим, то выбирается некоторое подмножество тестов, при этом не гарантируется, что малорезультативные тесты будут исключены. Поэтому самое лучшее — исключить их в процессе анализа диаграммы.
Рис. 6.21 — Первая половина результирующей таблицы решений
Рис. 6.22 — Вторая половина результирующей таблицы решений
Преобразуем функциональную диаграмму, изображенную на рис. 6.18, в таблицу решений. Выберем первым следствием 91. Следствие 91 имеет место, если узел 36 принимает значение 0. Значение узла 36 есть 0, значение узлов 32 и 35 есть 0,0, 0,1 или 1,0, и применимы положения 2 и 3. Хотя подобное преобразование — трудоемкий процесс, но можно проложить обратную трассу от следствий к причинам, учесть при этом ограничения причин и найти комбинации последних, которые приводят к следствию 91.
Результирующая таблица решений, при условии, что имеет место следствие 91, показана на рис. 6.21 (столбцы 1—11). Столбцы (тесты) 1—3 представляют условия, где узел 32 есть 0, а узел 35 есть 1. Столбцы 4—10 представляют условия, где узел 32 есть 1, а узел 35 есть 0. С помощью положения 3 определена только одна ситуация (колонка 11) из 21-ой возможной, когда узлы 32 и 35 есть 0. Пробелы представляют «безразличные» ситуации (т.е. состояние причины несущественно) или указывают на то, что состояние причины очевидно вследствие состояний других зависимых причин (например, для столбца 1 известно, что причины 5, 7 и 8 должны принимать значения 0, так как они связаны ограничением «одно и только одно» с причиной 6).
Столбцы 12—15 представляют ситуации, при которых имеет место следствие 92, а столбцы 16 и 17 — ситуации, при которых имеет место следствие 93. На рис. 6.22 показана остальная часть таблицы решений.
Последний шаг заключается в том, чтобы преобразовать таблицу решений в 38 тестов. Набор из 38-и тестов представлен ниже.
Числа возле каждого теста обозначают следствия, которые, как ожидается, должны здесь иметь место. Предположим, что последний используемый адрес памяти машины есть 7FFF.
1.
DISPLAY 24AF74 — 123
(91)
2.
DISPLAY 2ZX4 — 3000
(91)
3.
DISPLAY HHHHHHHH — 200
(91)
4.
DISPLAY 200 200
(91)
5.
DISPLAY 0 — 22222222
(91)
6.
DISPLAY 1 — 2X
(91)
7.
DISPLAY 2 — ABCDEFGHI
(91)
8.
DISPLAY 3.11111111
(91)
9.
DISPLAY 44.$42
(91)
10.
DISPLAY 100.$$$$$$$
(91)
11.
DISPLAY 10000000 — M
(91)
12.
DISPLAY FF — 8000
(92)
13.
DISPLAY FFF.7001
(92)
14.
DISPLAY 8000 — END
(92)
15.
DISPLAY 8000 — 8001
(92)
16.
DISPLAY AA-A0
(93)
17.
DISPLAY 7000.0
(93)
18.
DISPLAY 7FF9 — END
(94,97)
19.
DISPLAY 1
(94,97)
20.
DISPLAY 21 — 29
(94,97)
21.
DISPLAY 4021.A
(94,97)
22.
DISPLAY — END
(94,96)
23.
DISPLAY
(94,96)
24.
DISPLAY — F
(94,96)
25.
DISPLAY .E
(94,96)
26.
DISPLAY 7FF8 — END
(94,96)
27.
DISPLAY 6000
(94,96)
28.
DISPLAY A0 — A4
(94,96)
29.
DISPLAY 20.8
(94,96)
30.
DISPLAY 7001 — END
(95,97)
31.
DISPLAY 5 — 15
(95,97)
32.
DISPLAY 4FF.100
(95,97)
33.
DISPLAY — END
(95,96)
34.
DISPLAY —20
(95,96)
35.
DISPLAY .11
(95,96)
36.
DISPLAY 7000 — END
(95,96)
37.
DISPLAY 4 —14
(95,96)
38.
DISPLAY 500.11
(95,96)
Заметим, что в этом случае двум и более различным тестам соответствует один и тот же набор причин, следует стараться выбирать различные значения причин с тем, чтобы хотя бы незначительно улучшить результативность тестов. Заметим также, что из-за ограниченного размера памяти тест 22 является нереализуемым (при его использовании будет получено следствие 95 вместо 94, как отмечено в тесте 33). Следовательно, реализуемы только 37 тестов.
Замечания.
Применение функциональных диаграмм — систематический метод генерации тестов, представляющих комбинации условий. Альтернативой является специальный выбор комбинаций, но при этом существует вероятность пропуска многих «интересных» тестов, определенных с помощью функциональной диаграммы.
При использовании функциональных диаграмм требуется трансляция спецификации в булевскую логическую сеть. Следовательно, этот метод открывает перспективы ее применения и дополнительные возможности спецификаций. Действительно, разработка функциональных диаграмм есть хороший способ обнаружения неполноты и неоднозначности в исходных спецификациях. Например, можно заметить, что предложенный процесс обнаруживает неполноту в спецификации команды DISPLAY. Спецификация устанавливает, что все выходные строки содержат четыре слова. Это справедливо не во всех случаях; так, для тестов 18 и 26 это неверно, поскольку для них начальный адрес отображаемой памяти отличается от конечного адреса памяти машины менее чем на 16 байт.
Метод функциональных диаграмм позволяет построить набор полезных тестов, однако его применение обычно не обеспечивает построение всех полезных тестов, которые могут быть определены. Так, в нашем примере мы ничего не сказали о проверке идентичности отображаемых на экран терминала значений данных данным в памяти и об установлении случая, когда программа может отображать на экран любое возможное значение, хранящееся в ячейке памяти. Кроме того, функциональная диаграмма неадекватно исследует граничные условия. Конечно, в процессе работы функциональными диаграммами можно попробовать покрыть граничные условия. Например, вместо определения единственной причины
адрес 2 ³ адрес 1
можно определить две причины:
адрес 2 > адрес 1
адрес 2 = адрес 1
Однако при этом граф существенно усложняется, и число тестов становится чрезвычайно большим. Поэтому лучше отделить анализ граничных значений от метода функциональных диаграмм. Например, для спецификации команды DISPLAY могут быть определены следующие граничные условия:
1. Адрес 1 длиной в одну цифру.
2. Адрес 1 длиной в шесть цифр.
3. Адрес 1 длиной в семь цифр.
4. Адрес 1 = 0.
5. Адрес 1 = 7FFF.
6. Адрес 1 = 8000.
7. Адрес 2 длиной в одну цифру.
8. Адрес 2 длиной в шесть цифр.
9. Адрес 2 длиной в семь цифр.
10. Адрес 2 = 0.
11. Адрес 2 = 7FFF.
12. Адрес 2 = 8000.
13. Адрес 2 = адрес 1.
14. Адрес 2 = адрес 1.
15. Адрес 2 = адрес 1 – 1.
16. Счетчик байтов длиной в одну цифру.
17. Счетчик байтов длиной в шесть цифр.
18. Счетчик байтов длиной в семь цифр.
19. Счетчик байтов = 1.
20. Адрес 1 + счетчик байтов = 8000.
21. Адрес 1 + счетчик байтов = 8001.
22. Отображение шестнадцати байт (одна строка).
23. Отображение семнадцати байт (две строки).
Это вовсе не означает, что следует писать 60 (37 + 23) тестов. Поскольку функциональная диаграмма дает только направление в выборе определенных значений операндов, граничные условия могут входить в полученные из нее тесты. В нашем примере, переписывая некоторые из первоначальных 37 тестов, можно покрыть все 23 граничных условия без дополнительных тестов. Таким образом, мы получаем небольшой, но убедительный набор тестов, удовлетворяющий поставленным целям.
Заметим, что метод функциональных диаграмм согласуется с некоторыми принципами тестирования, изложенными в п. 6.2. Его неотъемлемой частью является определение ожидаемого выхода каждого теста (все столбцы в таблице решений обозначают ожидаемые следствия). Заметим также, что данный метод помогает выявить ошибочные побочные следствия. Например, столбец (тест) 1 устанавливает, что должно присутствовать следствие 91 и что следствия 92–97 должны отсутствовать.
Наиболее трудным при реализации метода является преобразование диаграммы в таблицу решений. Это преобразование представляет собой алгоритмический процесс. Следовательно, его можно автоматизировать посредством написания соответствующей программы. Фирма IBM имеет ряд таких программ, но не поставляет их.