[Перевод] Покрытие графов в тестировании ПО, часть 1
Большинство программ и алгоритмов можно представить в виде графа, состоящего из набора вершин (N) и ребер (Е). Покрытие графов в тестировании полезно тем, что можно проектировать тесты, используя разные критерии покрытия, и выявить ошибки. Что касается тестирования черного ящика, то покрытие графов здесь тоже может иметь большое значение, если приходится работать с состояниями и переходами, графами состояний сущности и т.д. Если граф достаточно сложен, разные критерии покрытия позволят оценить достаточность тестового набора.
Определения
Графы
Формальное определение графа приведено ниже.
- Граф, G, состоит из множества одной и более (1…*) вершин, N, и множества нуля и более (0…*) ребер, Е.
- Должно быть задано начальное множество вершин, N0, и конечное множество вершин, Nf. Оба эти множества должны быть непустыми. Если граф состоит из одной вершины, она должна быть в обоих множествах, значит, будет выполняться N0 = Nf. Начальные вершины обозначаются входящими стрелками (см. ниже зеленые вершины). Конечные вершины обозначаются жирной окружностью. Ниже цвета используются просто для иллюстрации: зеленые — начальные, красные — конечные, синие — обычные.
- Ребро е может объединять две вершины, np и ns, где p — источник, а s — приемник. Это представляется как (np, ns). Также ребро может начинаться из одной вершины и заканчиваться в ней же: (n, n).
- Вершина формально обозначается n в нижнем регистре с числовым индексом для обозначения ее номера. Для краткости и легкости понимания будет использоваться упрощенный ситнаксис, где вершина просто обозначается номером (если возникнет какая-то неопределенность, используем формальную нотацию). Просто имейте в виду, что в тестах могут потребоваться «длинные» обозначения.
Пути в графе
Граф ниже — для иллюстрации приводимых определений.
- Путь — последовательность связанных вершин в графе G. Путь р из вершины 1 к 3, 6 и 4 можно записать так: p = [n1, n3, n6, n4] (формально). Я буду записывать это так: [1, 3, 6, 4]. Соседние пары вершин в этом пути представляют собой ребра. Например, множество ребер в этом пути — {(1, 3), (3, 6), (6, 4)}. Обратите внимание, это набор пар, и я использовал неформальный способ записи (также стоит уделять внимание правильной расстановке скобочек).
- Длина пути — число ребер в пути. Одна вершина имеет путь длины 0 (нетрудно понять, поскольку вообще говоря, у нее 0 ребер). Длина пути р — 3.
- Отрезок пути — подмножество вершин в пути р. [1, 3] — отрезок пути [1, 3, 6, 4]. Не стоит путать это с ребром (1, 3).
- Предел досягаемости (n) можно определить как подграф (вершины и ребра), который может быть достигнут из вершины n. Предел досягаемости (2) — множество, содержащее вершины 2, 4 и 5. Обратите внимание, Предел досягаемости () может принимать в качестве параметра наборы вершин и ребер. Результирующий граф — просто объединение всех отдельных пределов досягаемости. Например, Предел досягаемости ({6,2}) — то же, что и объединение множеств Предел досягаемости (6) и Предел досягаемости (2). Чтобы получить этот результат, перечислите все вершины, досягаемые из вершины 6, и все вершины, досягаемые из вершины 2, объедините списки и удалите дубликаты. Используя граф выше, результат такой: {6, 4, 2, 5}. Предел досягаемости ({3, 2}) достигает все вершины и ребра в графе G. Можно указать, что Предел досягаемости ({2, 3}) = G.
- Тестовый путь начинается в начальной вершине и заканчивается в конечной. Путь [1, 3, 4] — корректный тестовый путь, а [1, 3, 6] — нет. Понимаете почему?
- SESE (single-entry, single-exit) графы — графы с одним входом и одним выходом, т.е. те у которых ровно одна начальная и одна конечная вершина.
Покрытие вершин (ПВ)
Самые простые критерии покрытия — покрытие вершин и покрытие ребер. Покрытие вершин предполагает, что ваши тесты покрывают все достижимые вершины в графе. Требования для тестового покрытия вершин в графе — множество вершин (N) графа.
Для этого графа требования и удовлетворяющий их тестовый путь приведены ниже.
требования = {1, 2, 3}
путь (T) = {[1, 2, 3]}
Покрытие ребер (ПР)
Цель покрытия ребер — пройти по всем ребрам в графе. Ребро можно выразить как путь длины 1. Требования содержат все достижимые пути длиной до 1 (и включительно). Формулировка «до 1» позволяет учесть графы, состоящие из одной вершины и не имеющие ребер.
требования = {(1, 2), (1, 3), (2, 3)}
путь (T) = {[1, 2, 3], [1, 3]}
Покрытия вершин и ребер чаще всего одинаковы. Исключение составляют особые случаи, включающие условные конструкции (if-else). (Таковым является и граф из трех вершин в примере выше: сравните требуемые тестовые пути и увидите почему.)
Попарное покрытие ребер (ППР)
Требования включают каждый достижимый путь длины до 2 включительно.
Фактически, найдите все пути, включающие три вершины и два ребра и создайте набор тест-кейсов, покрывающих эти пути. Пути длины 1 будут автоматически покрываться, поскольку будут включены в один из этих тестовых путей. Если есть путь длины 1, не являющийся отрезком уже перечисленных путей, нужно включить его в список.
В графе выше есть пять разных пар ребер. Попарное покрытие ребер предполагает, что каждая из этих пар покрывается минимум одним тестовым путем.
требования = {[1, 3, 5], [1, 2, 3], [1, 2, 4], [2, 3, 5], [2, 4, 5]}
путь (T) = {[1, 3, 5], [1, 2, 3, 5], [1, 2, 4, 5]}
Полное покрытие путей (ППП)
Требования включают все пути в G. Это невозможно, если в графе есть цикл. В качестве компромисса используется покрытие установленных путей.
Покрытие заданных путей (ПЗП)
В ПЗП требования представляют собой множество из S тестовых путей, где S — множество путей, выбранных тестировщиком. Это позволяет избежать проблемы с необходимостью покрыть бесконечно много путей в ППП, если граф содержит цикл. В ПЗП тестировщик просто исключает цикл из S, и требования ПЗП можно будет удовлетворить.
S = {[1, 2, 3], [1, 3], [1, 4, 3]} (Все пути в G, кроме содержащих циклы)
требования = {[1, 2, 3], [1, 3], [1, 4, 3]}
путь (T) = {[1, 2, 3], [1, 3], [1, 4, 3]}
ППП нецелесообразно. ПЗП — слабый компромисс, чтобы фактически удовлетворить ППП без добавления бесконечного набора требований для графов с циклами. Однако, покрытие заданных путей также неидеально. Тестировщик может пропустить важные пути при составлении множества S, что приводит к субъективному и неустойчивому к ошибкам ПЗП.
Попытки решить эту проблему предпринимаются уже долго. Начиная с однократного прохождения цикла (1970-е), прохождения каждого цикла ровно один раз (1980-е) до менее формального описания — прохождения каждого цикла 0, 1 или более раз (1990-е), тестировщики ПО пришли к идее использования основных путей, чтобы ограничить общее количество путей в графе.
Записка на полях: цикломатическая сложность графа определяет количество тестов, необходимых, чтобы все строки в программе выполнились как минимум один раз. Цикломатическую сложность можно рассчитать, прибавив 2 к разности между количеством ребер и вершин в графе.
ЦС = #ребер — #вершин + 2
В следующей и последней части: основные пути и покрытия, с ними связанные.
