💻 computer science

Requirements Coverage-Guided Minimization for Natural Language Test Cases

This paper proposes RTM, a novel approach that utilizes natural language processing and a genetic algorithm to minimize redundant natural language test cases while preserving full requirement coverage and maximizing fault detection rates in critical systems.

Original authors: Rongqi Pan, Feifei Niu, Lionel C. Briand, Hanyang Hu

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rongqi Pan, Feifei Niu, Lionel C. Briand, Hanyang Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head chef of a massive, high-stakes restaurant. Your job is to ensure every single dish served is perfect, safe, and meets the exact specifications of the menu (the Requirements). To do this, you have a massive "Test Kitchen" where you taste-test every dish before it goes to the customer.

The Problem: The Overcrowded Kitchen

Over time, your menu has grown, and so has your list of taste-tests. You now have 736 different tests (like checking the temperature of a steak, tasting the sauce, checking the plating, etc.).

The problem? Your kitchen is redundant.

Test #45 checks if the steak is cooked to 140°F.
Test #46 checks if the steak is cooked to 140°F (but written slightly differently).
Test #47 checks the same thing again.

Running all 736 tests takes forever, costs a fortune in ingredients, and ties up your staff. You want to cut the list down to save time and money, but you can't just throw away random tests. If you do, you might miss a burnt steak (a Fault) or fail to prove you met the menu specs (Requirement Coverage).

The Solution: RTM (The Smart Sous-Chef)

The authors of this paper, Pan, Niu, Briand, and Hu, built a smart tool called RTM (Requirement-guided Test suite Minimization). Think of RTM as a super-smart Sous-Chef who helps you trim the fat from your test list without losing any flavor.

Here is how RTM works, broken down into simple steps:

1. Reading the Recipe Cards (Natural Language Processing)

Your test cases aren't written in computer code; they are written in English (e.g., "Set the valve to 5," "Check the pressure").

The Challenge: Computers don't naturally "read" like humans. They see "Set valve" and "Adjust valve" as totally different things.
The Fix: RTM uses Text Embedding. Imagine this as a translator that turns every sentence into a unique GPS coordinate in a giant 3D map.
- If two tests are very similar (like "Set valve to 5" and "Set valve to 5.1"), their GPS coordinates are right next to each other.
- If they are different, they are far apart.
- Analogy: It's like turning every recipe card into a color. Similar recipes are shades of blue; different ones are red or green.

2. Measuring the Distance (Similarity)

Once the tests are mapped out, RTM measures the "distance" between them.

If two tests are standing shoulder-to-shoulder on the map, they are redundant (doing the same job).
If they are on opposite sides of the map, they are diverse (checking different things).
RTM tries to find the perfect group of tests that are as far apart from each other as possible (maximizing diversity) while still covering every single requirement.

3. The Genetic Algorithm (The Evolutionary Chef)

How do you pick the best group from 736 options? You can't just guess. RTM uses a Genetic Algorithm (GA).

The Analogy: Imagine you are breeding the perfect team of dogs for a search-and-rescue mission.
1. Generation 1: You randomly pick a few teams of dogs.
2. Selection: You see which teams cover the most ground and find the most "lost hikers" (faults).
3. Breeding: You take the best teams and mix them up (crossover) to create new teams.
4. Mutation: You occasionally swap a dog for a different one to see if it helps.
5. Repeat: You do this hundreds of times until you find the ultimate team that is small, covers every area, and finds every lost hiker.

4. The Golden Rule: No Cutting Corners

In many industries (like cars, planes, or medical devices), you must prove you checked every single rule.

The Trap: Some old tools would cut the test list to save money but accidentally skip a critical rule.
RTM's Promise: RTM has a hard rule: "You cannot reduce the list unless 100% of the requirements are still covered." It ensures you never lose the safety net while shrinking the list.

What Did They Find?

The authors tested this on a real automotive company's data (736 tests, 54 requirements).

It Works Better: RTM found more "bugs" (faults) than any other method, even when they were forced to cut the test list down to 10% or 50% of its original size.
It's Fast: Even though it's smart, it doesn't take forever. It scales linearly. If you double the number of tests, the time it takes to sort them only doubles. It's like sorting a deck of cards: it gets slower as the deck gets bigger, but it's still manageable.
The "Redundancy" Secret: They discovered that if your test list is very redundant (lots of duplicate tests), RTM can cut it down massively without losing quality. But if your list is already very lean, you have to be more careful.

The Big Picture

Think of RTM as a smart filter.

Old way: "Let's just delete half the tests randomly and hope for the best." (Risky!)
RTM way: "Let's look at every test, see which ones are doing the same job, and keep the most unique ones that cover every single rule." (Safe and Efficient!)

For companies building safety-critical systems (like self-driving cars), this means they can test their software faster and cheaper, without ever compromising on safety or missing a critical bug. It's the difference between throwing away a whole toolbox because it's too heavy, versus carefully selecting the one perfect wrench that can fix everything.

1. Problem Definition

The paper addresses the challenge of Test Suite Minimization (TSM) in safety-critical systems, specifically within the automotive domain.

Context: As software systems evolve, test suites grow large and redundant. In critical systems (e.g., automotive), test cases are often specified in natural language (following structured templates) and traced to requirements before being implemented in code.
The Gap: Existing TSM techniques primarily rely on code coverage (e.g., statement/branch coverage) and do not effectively handle natural language test cases. Furthermore, most existing methods cannot simultaneously satisfy two conflicting industrial constraints:
1. Fixed Minimization Budget: Reducing the test suite to a specific size (e.g., 50% of the original).
2. Full Requirement Coverage: Ensuring 100% of system requirements are still covered by the reduced suite (a strict necessity for functional safety standards like ISO 26262).
Objective: To develop an approach that reduces test suite redundancy (improving Fault Detection Rate - FDR) while strictly maintaining full requirement coverage under a fixed budget.

2. Methodology: The RTM Approach

The authors propose RTM (Requirement coverage-guided Test suite Minimization), a novel approach combining Natural Language Processing (NLP) and Evolutionary Search.

A. Preprocessing and Representation

RTM converts natural language test steps into vector representations to compute similarity.

Preprocessing: Three methods were investigated:
1. $PM_1$ : Lowercasing, removing whitespace/line breaks.
2. $PM_2$ : $PM_1$ + punctuation removal, tokenization, and lemmatization.
3. $PM_3$ : Raw text (no preprocessing).
Embedding Techniques: Seven techniques were evaluated:
- Sentence-level: TF-IDF, Universal Sentence Encoder (USE), LongT5, Amazon Titan Text Embedding V2.
- Word-level: Word2Vec, GloVe, FastText.
Similarity Metrics:
- Word-level: Word Mover's Distance (WMD).
- Sentence-level: Cosine Similarity and Euclidean Distance.

B. Optimization via Genetic Algorithm (GA)

Since TSM is an NP-hard problem, RTM employs a Genetic Algorithm to search for the optimal subset of test cases.

Individual Representation: A binary vector where '1' indicates a selected test case.
Constraints (Hard):
1. Budget: The subset size must equal $\max(|R|, \lfloor M \cdot |T| \rfloor)$ , where $M$ is the budget and $|R|$ is the number of requirements.
2. Coverage: The union of requirements covered by the subset must equal the full set of requirements ( $R$ ).
Fitness Function: The goal is to minimize the sum of pairwise similarities between selected test cases. Lower similarity implies higher diversity, which correlates with higher fault detection.
- Formula: $Fitness(T') = \frac{1}{n} \sum_{i=1}^{n} (\max_{j \neq i} NormSim(t_i, t_j))^2$
Initialization Strategies: Three strategies were designed to generate valid initial populations that satisfy coverage and budget constraints:
1. Iterative Selection.
2. Initial Requirement + Random.
3. Proportional Selection.

3. Experimental Setup

Dataset: An industrial automotive dataset containing 736 system test cases covering 54 requirements. The test cases detect 220 unique faults.
Redundancy Analysis: The authors generated 10 diverse test suites for 15 different redundancy levels (ranging from 4.5 to 11.5) to study the impact of redundancy on TSM effectiveness.
Baselines:
- Random Minimization (RM): With and without requirement coverage constraints.
- FAST-R: A state-of-the-art similarity-based TSM approach (including fixed-budget and adequate versions).
Metrics: Fault Detection Rate (FDR), Requirement Coverage, and Runtime (Scalability).

4. Key Results

A. Optimal Configuration (RQ1)

Best Performance: The combination of TF-IDF (sentence-level) with Cosine Similarity, using Preprocessing Method 3 (Raw text) and Initialization Strategy 2, achieved the highest FDR (86.09%) at a 50% budget.
Insight: Surprisingly, the simple TF-IDF outperformed deep learning models (USE, LongT5, Titan). The authors attribute this to the highly structured, template-based nature of automotive test cases, where TF-IDF effectively captures unique variable names and parameter values, whereas semantic models tend to "smooth out" these critical lexical differences.

B. Comparison with Baselines (RQ2)

FDR Superiority: RTM consistently outperformed Random Minimization and all FAST-R variants across most minimization budgets (10%–90%).
Mid-Range Budgets: The performance gap was most significant at mid-range budgets (30%–60%). For example, at a 40% budget, RTM achieved 78.68% FDR, while FAST++ and RM-Req achieved ~56% and ~65% respectively.
Coverage Guarantee: Unlike FAST-R (which struggles to guarantee both fixed budget and full coverage simultaneously), RTM maintained 100% requirement coverage in all experiments.

C. Impact of Redundancy (RQ3)

Redundancy Effect: Higher test suite redundancy levels generally led to higher FDR for all techniques.
RTM Robustness: RTM consistently outperformed baselines across all redundancy levels.
Low Budget Risk: At low budgets combined with high redundancy, there remains a significant gap between the theoretical maximum FDR and the achieved FDR, suggesting room for future improvement in highly constrained scenarios.

D. Scalability (RQ4)

Linear Scaling: RTM's runtime scales linearly with the test suite size.
Efficiency: For the evaluated dataset (up to ~600 test cases), RTM completed minimization in 1.3s to 4.4s.
Practicality: While RTM is slower than Random Minimization, the absolute time difference for large-scale suites (e.g., 200k test cases) is estimated to be around 20 minutes. Given that TSM is typically a periodic activity (e.g., major releases), this overhead is considered acceptable given the significant gains in FDR.

5. Key Contributions

Novel Approach (RTM): A TSM technique specifically designed for natural language, requirement-based testing that enforces 100% requirement coverage under a fixed budget.
Comprehensive Evaluation: A rigorous study involving 7 embedding techniques, 3 distance metrics, 3 preprocessing methods, and 3 initialization strategies on a real-world industrial automotive dataset.
Redundancy Insights: New empirical evidence showing that test suite redundancy levels significantly impact TSM effectiveness and that RTM is robust across varying redundancy levels.
Open Source: The authors released a replication package including source code, data, and results to foster reproducibility.

6. Significance

This paper bridges a critical gap in software testing for safety-critical systems. It provides a practical solution for industries (like automotive) where:

Test cases are defined in natural language.
Full requirement coverage is non-negotiable for compliance.
Testing resources are limited.

By demonstrating that RTM can significantly reduce testing costs (by minimizing the suite size) without sacrificing fault detection capabilities or compliance, the work offers a scalable, reliable method for optimizing requirement-based test suites. The finding that simple statistical methods (TF-IDF) can outperform complex LLMs in this specific domain also provides valuable guidance for future research in NLP-based testing.