LLMCFG-TGen: автоматическая генерация тест-кейсов через граф потоков

ШАГ 1 (в чате): Use case → LLM (Prompt #1 + Algorithm) → CFG в JSON
  ↓ Валидация: проверка связности графа, повторная генерация при ошибках

ШАГ 2 (требует код): DFS-обход графа → извлечение всех путей от корня до выхода
  ↓ Программа перебирает node IDs, заменяет на текстовые описания шагов

ШАГ 3 (в чате): Каждый путь → LLM (Prompt #2) → детальный тест-кейс
  ↓ Формат: заголовок, предусловия, шаги + ожидаемые результаты

⚠️ Шаг 2 требует программирование — обход графа и извлечение путей делает код, не LLM вручную.

Задача: У тебя есть описание процесса "Бронирование переговорки в офисе" для корпоративного портала. Нужны тест-кейсы для проверки всех сценариев — когда переговорка свободна, когда занята, когда отменяют бронь, когда меняют время.

Промпт (Шаг 1 — генерация CFG):

Ты — эксперт по software engineering. Твоя задача: преобразовать описание функциональности в граф потоков управления (CFG) в формате JSON.

**Правила построения CFG:**
1. Каждый шаг из основного потока и альтернативных потоков становится узлом графа
2. Узлы соединяются рёбрами по порядку выполнения
3. Условные ветвления создают два ребра из одного узла (true/false)
4. Альтернативные потоки явно связываются с основным потоком
5. Не должно быть изолированных узлов

**Алгоритм:**
- Объедини все шаги в последовательность
- Создай узлы S1, S2, ... для каждого шага
- Первый узел = корень графа
- Для каждого шага: если следующий содержит условие → создай два ребра (true → S_i+1, false → S_i+2), иначе → одно ребро к следующему
- Для альтернативных потоков: добавь рёбра от точки ветвления в основном потоке

**Формат JSON:**
{
  "nodes": [{"id": "S1", "Statement": "текст шага"}, ...],
  "edges": [{"from": "S1", "to": "S2", "condition": "условие", "weight": 1}, ...]
}

**Описание функциональности:**
{вставь сюда своё описание процесса бронирования}

Результат:

Модель выдаст JSON-граф со всеми узлами (шаги процесса) и рёбрами (переходы между шагами). Условные ветвления будут размечены полями "condition". Например, узел "Проверка доступности" будет иметь два исходящих ребра: "свободна" → запись брони, "занята" → вывод ошибки.

⚠️ Дальше нужен код: чтобы извлечь все пути из графа и сгенерировать тест-кейсы для каждого пути — требуется программа для обхода графа (DFS).

LLM плохо держит в "голове" сложную логику с множеством условий и ветвлений. При генерации тестов напрямую из текста она упускает редкие сценарии или генерирует дубли. Чем длиннее описание, тем больше пропусков.

LLM хорошо работает с явными алгоритмами и структурированным выводом. Когда в промпте есть пошаговая инструкция ("если условие → два ребра, иначе → одно"), модель следует формальной логике вместо интерпретации смысла. JSON-формат убирает двусмысленность — есть чёткая схема, что и где должно быть.

Метод разделяет задачу на три этапа: (1) извлечение структуры из текста (делает LLM по алгоритму), (2) перебор всех комбинаций (делает программа — гарантия полноты), (3) генерация текста тестов для конкретного пути (делает LLM — простая задача без ветвлений). Каждый этап использует сильную сторону исполнителя.

Рычаги управления:

• Алгоритм в промпте → убери для простых задач, где структура очевидна (экономия токенов)
• Валидация графа → отключи проверку изолированных узлов, если уверен в качестве входных данных
• JSON-схема → замени на другой формат (YAML, XML) под свои инструменты парсинга
• Условия на рёбрах → добавь поле "priority" для управления порядком выполнения тестов

Prompt #1: Генерация CFG

Ты — эксперт по software engineering. Преобразуй описание функциональности в граф потоков управления (CFG) в формате JSON.

**Правила:**
1. Каждый шаг становится узлом с уникальным ID и текстовым описанием
2. Узлы соединяются рёбрами по порядку выполнения
3. Условные ветвления → два ребра из одного узла (true branch / false branch)
4. Альтернативные и исключительные потоки связываются с основным потоком
5. Не должно быть изолированных узлов (каждый узел участвует хотя бы в одном ребре)

**Алгоритм построения:**
- Шаг 1: Объедини основной поток, альтернативные потоки и исключения в единую последовательность узлов S1, S2, ..., Sn
- Шаг 2: Первый узел S1 = корень графа
- Шаг 3: Добавь ребро S1 → S2 с весом 1
- Шаг 4: Для каждого узла Si:
  - Если Si+1 содержит условие: создай два ребра (Si → Si+1 для true, Si → Si+2 для false), вес = вес предыдущего ребра + 1
  - Иначе: создай одно ребро Si → Si+1, вес = вес предыдущего ребра + 1

**Формат вывода (JSON):**
{
  "nodes": [
    {"id": "S1", "Statement": "описание шага 1"},
    {"id": "S2", "Statement": "описание шага 2"}
  ],
  "edges": [
    {"from": "S1", "to": "S2", "weight": 1},
    {"from": "S2", "to": "S3", "condition": "если условие выполнено", "weight": 2}
  ]
}

**Описание функциональности:**
{текст_описания_процесса}

Плейсхолдеры: - {текст_описания_процесса} — текстовое описание функциональности системы (use case, user story, сценарий работы)

🚀 Быстрый старт — вставь в чат:

Вот шаблон для построения графа потоков из текста. Адаптируй под мою задачу: [опиши свою задачу — например, "создать CFG для процесса возврата товара в интернет-магазине"]. 
Задавай вопросы, чтобы заполнить поля.

[вставить шаблон выше]

LLM спросит какие шаги входят в процесс, есть ли условные ветвления, какие альтернативные сценарии — потому что для построения графа нужно знать все возможные пути выполнения. Она возьмёт паттерн алгоритма и адаптирует под твой контекст.

⚠️ Важно: Prompt #2 (генерация тест-кейсов из путей) в исследовании детально не раскрыт. После извлечения путей нужен будет свой промпт в стиле "преобразуй этот путь в тест-кейс с заголовком, предусловиями, шагами и ожиданиями".

⚠️ Требует программирование для полного workflow: Извлечение всех путей из графа делается через алгоритм обхода в глубину (DFS) — нужен код на Python или другом языке. Вручную в чате перебрать все комбинации путей в сложном графе (10+ узлов, условные ветвления) практически невозможно.

⚠️ Узкая специализация: Метод заточен под генерацию тест-кейсов из use-case описаний. Если ты не занимаешься тестированием софта или не работаешь с формальными описаниями процессов — применимость ограничена.

⚠️ Валидация графа требует логики: LLM иногда генерирует невалидные графы (изолированные узлы, нарушенные связи). В исследовании это решается автоматической проверкой и повторной генерацией — без кода придётся проверять структуру вручную.

⚠️ Неполный шаблон: Prompt #2 для финальной генерации тест-кейсов в статье не детализирован — придётся создавать самостоятельно.

Команда взяла 42 use-case описания из четырёх разных доменов (библиотечные системы, банкинг, e-commerce, здравоохранение) и проверила: может ли GPT-4o построить корректный граф потоков, и насколько качественные тесты получаются из этих графов.

Сравнивали с двумя baseline-подходами: (1) прямая генерация тестов через LLM без промежуточного графа и (2) ручное построение графов экспертами с последующей генерацией тестов. Измеряли полноту покрытия (все ли пути учтены), избыточность (есть ли дубли тестов) и точность (соответствие тестов описанию).

Результаты показали: - LLM генерирует корректные CFG в ~90% случаев с первой попытки. В остальных — срабатывает валидация и повторная генерация. - Метод с графом даёт 100% покрытие путей (все возможные сценарии превращаются в тесты), тогда как прямая генерация LLM упускает 20-30% редких ветвлений. - Редукция дублей: прямая генерация даёт ~15% избыточных тестов, метод с графом — почти 0%, потому что пути уникальны по построению.

Почему так получилось: Граф — это "каркас логики", где все условия уже размечены. LLM не нужно держать в контексте сразу весь флоу с ветвлениями — она работает отдельно с каждым путём. Прямая генерация пытается охватить всё сразу, путается и генерирует или неполно, или с дублями.

Практики оценили: Пригласили 5 тестировщиков с опытом 3-8 лет, дали им сгенерированные тесты вслепую (не сказали откуда). Оценивали логичность, полноту, читаемость. LLMCFG-TGen получил средний балл 4.2 из 5 — тесты "готовы к использованию с минимальной правкой". Ручные тесты — 4.5 из 5, прямая LLM-генерация — 3.1 из 5 (много пропусков и непоследовательности).

Неожиданный инсайт: Явный алгоритм в промпте оказался критичным. Эксперимент без алгоритма (только инструкции "построй граф") давал корректный CFG лишь в 60% случаев. Формализация через псевдокод повысила надёжность на +30% без fine-tuning.

Если описание функциональности короткое (5-7 шагов) и без вложенных условий, можно убрать блок "Алгоритм построения" из промпта. Оставить только правила и формат JSON.

Пример упрощённого промпта:

Преобразуй описание функциональности в CFG (граф потоков) в JSON.
Правила: каждый шаг = узел, связи = рёбра, условия → два ребра из узла.
Формат: {"nodes": [...], "edges": [...]}

Описание: {короткое_описание}

Для сложных многоветвенных процессов оставляй полный алгоритм — он страхует от пропусков.

Идея "дай LLM алгоритм + JSON-схему" работает не только для графов. Можно применить к любой задаче, где нужно извлечь структуру из текста:

Пример: Извлечение ментальной модели из интервью с пользователем

Ты — исследователь UX. Преобразуй транскрипт интервью в граф ментальной модели пользователя.

**Алгоритм:**
1. Найди все действия пользователя (глаголы) → узлы типа "action"
2. Найди все убеждения и предположения ("я думаю", "обычно", "всегда") → узлы типа "belief"
3. Найди причинно-следственные связи ("потому что", "поэтому") → рёбра типа "causation"
4. Найди временные связи ("сначала", "потом") → рёбра типа "sequence"

**Формат JSON:**
{
  "nodes": [{"id": "N1", "type": "action"/"belief", "text": "..."}],
  "edges": [{"from": "N1", "to": "N2", "type": "causation"/"sequence"}]
}

**Транскрипт:**
{текст_интервью}

Алгоритм делает извлечение надёжнее — LLM следует явным правилам вместо интерпретации "как понял".

LLMCFG-TGen: Using LLM-Generated Control Flow Graphs to Automatically Create Test Cases from Use Cases

Zhenzhen Yang, Chenhui Cui, Tao Li, Rubing Huang (Macau University of Science and Technology), Nan Niu (University of North Florida), Dave Towey (University of Nottingham Ningbo China), Shikai Guo (Dalian Maritime University)