Большинство программ и алгоритмов можно представить в виде графа, состоящего из набора вершин (N) и ребер (Е). Покрытие графов в тестировании полезно тем, что можно проектировать тесты, используя разные критерии покрытия, и выявить ошибки. Что касается тестирования черного ящика, то покрытие графов здесь тоже может иметь большое значение, если приходится работать с состояниями и переходами, графами состояний сущности и т.д. Если граф достаточно сложен, разные критерии покрытия позволят оценить достаточность тестового набора.

Определения

Графы

Формальное определение графа приведено ниже.

• Граф, G, состоит из множества одной и более (1..*) вершин, N, и множества нуля и более (0..*) ребер, Е.
• Должно быть задано начальное множество вершин, N₀, и конечное множество вершин, N_f. Оба эти множества должны быть непустыми. Если граф состоит из одной вершины, она должна быть в обоих множествах, значит, будет выполняться N₀ = N_f. Начальные вершины обозначаются входящими стрелками (см. ниже зеленые вершины). Конечные вершины обозначаются жирной окружностью. Ниже цвета используются просто для иллюстрации: зеленые — начальные, красные — конечные, синие — обычные.
• Ребро е может объединять две вершины, n_p и n_s, где p — источник, а s — приемник. Это представляется как (n_p, n_s). Также ребро может начинаться из одной вершины и заканчиваться в ней же: (n, n).
• Вершина формально обозначается n в нижнем регистре с числовым индексом для обозначения ее номера. Для краткости и легкости понимания будет использоваться упрощенный ситнаксис, где вершина просто обозначается номером (если возникнет какая-то неопределенность, используем формальную нотацию). Просто имейте в виду, что в тестах могут потребоваться «длинные» обозначения.

Пути в графе

Граф ниже — для иллюстрации приводимых определений.

• Путь — последовательность связанных вершин в графе G. Путь р из вершины 1 к 3, 6 и 4 можно записать так: p = [n₁, n₃, n₆, n₄] (формально). Я буду записывать это так: [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

В следующей и последней части: основные пути и покрытия, с ними связанные.