Причинно-следственный граф¶

Причинно-следственный граф (англ. cause-effect graph) — это формальная модель, используемая в теории тестирования программного обеспечения и системного анализа для описания логических связей между входными условиями (причинами) и ожидаемыми результатами (следствиями). Представляет собой ориентированный граф, вершины которого соответствуют причинам и следствиям, а дуги — логическим операциям (конъюнкция, дизъюнкция, отрицание), связывающим их. Применяется для генерации тестовых наборов, обеспечивающих максимальное покрытие логических комбинаций.

¶История

Метод причинно-следственных графов был предложен в 1970-х годах американским инженером и математиком Гленфордом Майерсом (Glenford J. Myers) в контексте разработки системного тестирования. Майерс, работавший в IBM, впервые описал технику в книге «The Art of Software Testing» (1979). Изначально метод предназначался для тестирования программ управления телефонными станциями, где требовалось проверить множество комбинаций входных сигналов. Впоследствии техника была адаптирована для общего тестирования программного обеспечения, а также для анализа бизнес-правил и систем управления базами данных.

В 1980-х годах метод получил развитие в работах Бориса Бейзера (Boris Beizer), который формализовал алгоритмы построения графов и преобразования их в таблицы решений. С распространением методологий структурного тестирования (например, MC/DC — Modified Condition/Decision Coverage) причинно-следственные графы стали использоваться в авиационной и медицинской промышленности, где требуется высокая надёжность систем.

¶Основные понятия

¶Причины и следствия

Причина (cause) — входное условие или событие, которое может принимать значение «истина» или «ложь». Примеры: «нажата кнопка А», «значение поля больше 0», «файл существует».
Следствие (effect) — выходное условие или результат, который должен наблюдаться при определённых комбинациях причин. Примеры: «загорается индикатор», «выводится сообщение об ошибке», «запись сохраняется в базу».

¶Логические связи

Причинно-следственный граф использует три базовых логических оператора:

Конъюнкция (AND) — следствие истинно, если истинны все связанные причины. Обозначается символом ∧.
Дизъюнкция (OR) — следствие истинно, если истинна хотя бы одна из причин. Обозначается символом ∨.
Отрицание (NOT) — инвертирует значение причины. Обозначается символом ¬.

Дополнительно могут применяться операторы исключающего ИЛИ (XOR) и импликации (если-то), но они сводятся к комбинациям базовых.

¶Ограничения (constraints)

Для реалистичного моделирования в граф вводятся ограничения, накладываемые на причины:

E (exclusive) — не более одной причины может быть истинной.
I (inclusive) — хотя бы одна причина должна быть истинной.
O (one and only one) — ровно одна причина истинна.
R (requires) — если причина A истинна, то причина B также должна быть истинна.
M (mask) — если причина A истинна, то причина B должна быть ложной.

¶Построение графа

Процесс построения причинно-следственного графа включает следующие этапы:

Анализ спецификации — выявление всех входных условий (причин) и ожидаемых результатов (следствий) из требований к системе.
Идентификация логических связей — определение, какие комбинации причин приводят к каждому следствию.
Построение графа — создание ориентированного графа, где вершины-причины располагаются слева, вершины-следствия — справа, а между ними размещаются промежуточные узлы с логическими операторами.
Наложение ограничений — добавление ограничений на причины (например, «две кнопки не могут быть нажаты одновременно»).
Преобразование в таблицу решений — граф переводится в таблицу, где строки соответствуют комбинациям причин, а столбцы — следствиям.

¶Применение

¶Тестирование программного обеспечения

Основная область применения — генерация тестовых наборов для функционального тестирования. Метод позволяет:

Обеспечить покрытие всех возможных комбинаций причин, включая граничные случаи.
Выявить логические ошибки в спецификациях (например, противоречия или неполноту).
Сократить количество тестов по сравнению с полным перебором (экспоненциальный рост комбинаций).

¶Анализ бизнес-правил

В системах управления бизнес-процессами (BPM) и базах данных причинно-следственные графы используются для формализации правил принятия решений. Например, в страховых компаниях графы помогают определить, при каких условиях клиент получает скидку.

¶Системы реального времени

В авионике, медицинских приборах и промышленных контроллерах графы применяются для верификации логики управления, где ошибка может привести к катастрофическим последствиям.

¶Преимущества и недостатки

¶Преимущества

Наглядность: граф позволяет визуально представить сложные логические зависимости.
Систематичность: метод гарантирует, что все комбинации причин будут рассмотрены.
Автоматизация: существуют инструменты (например, Cause-Effect Graph Tool), которые автоматически генерируют тесты из графа.

¶Недостатки

Трудоёмкость: построение графа для систем с большим числом причин (более 10–15) становится сложным.
Ограниченность: метод плохо подходит для систем с непрерывными входными данными (например, аналоговые сигналы).
Зависимость от спецификации: если требования неполны или противоречивы, граф может быть некорректным.

¶Пример

Рассмотрим простую систему: автоматический дверной замок. Причины:

A: «Введён правильный код».
B: «Нажата кнопка открытия».
C: «Дверь не заблокирована изнутри».

Следствие:

D: «Дверь открывается».

Логическая связь: D = A ∧ B ∧ C (все три причины должны быть истинны). Ограничение: если A ложно, то B игнорируется (R-ограничение: A требует B? нет, здесь это не требуется). Граф будет содержать три вершины-причины, одну вершину-следствие и один узел AND.

¶Инструменты

Для автоматизации работы с причинно-следственными графами существуют:

Cause-Effect Graph Tool (CEG) — бесплатное ПО для построения и анализа графов.
GraphWalker — инструмент для генерации тестов на основе графов.
Selenium IDE — дополнения, позволяющие импортировать графы для веб-тестирования.

¶Критика

Некоторые специалисты отмечают, что метод причинно-следственных графов устарел в эпоху agile-разработки, где требования часто меняются. Вместо него чаще применяются техники попарного тестирования (pairwise testing) и комбинаторные методы. Однако в проектах с жёсткими требованиями к безопасности (например, в авиации) графы остаются востребованными.

¶Источники

Myers, G. J. (1979). The Art of Software Testing. John Wiley & Sons.
Beizer, B. (1990). Software Testing Techniques (2nd ed.). Van Nostrand Reinhold.
Pressman, R. S. (2014). Software Engineering: A Practitioner’s Approach (8th ed.). McGraw-Hill.
IEEE Standard 1012-2016 — Standard for System and Software Verification and Validation.