Unlimited test cases: The power of generative fuzzing

Anomalies in a test case

In Defensics, protocol messages are represented as a tree structure built from protocol-specific grammar and rules. This tree defines the relationships between different elements of the protocol, making it possible to generate and manipulate messages systematically. These messages, including those sent and the expected responses, form a test case.

A test case without anomalies is called a valid case, meaning it strictly follows the protocol specification. In contrast, an anomalous case is derived from a valid one but includes one or more intentional deviations. These anomalies are critical in fuzz testing because they help expose vulnerabilities, robustness issues, and edge cases that might not appear during normal operation.

Anomalies are created by altering the protocol tree through operations such as replacing, adding, removing, or duplicating branches, or even replacing the entire tree. Most commonly, an anomaly substitutes a single leaf (a value) with another. When anomalies occur in two independent locations within the tree, they form a combination anomaly, which extends the concept of a single anomaly by introducing multiple independent modifications within the same test case. This approach increases test coverage and helps find complex issues that may only arise when multiple deviations interact.

Since these modifications can be combined in countless ways, combination anomalies effectively create an infinite testing space, enabling the generation of an unlimited number of unique test cases. Defensics provides multiple approaches for producing these advanced cases.

• Pseudorandom combination cases: A very limited set generated in all suites, appearing in the root generation
• Traditional unlimited mode: Extended test cases available in most test suites, generating pseudorandom combination cases indefinitely
• Enhanced unlimited mode: Introduced in 2024, offering a more systematic and powerful way to create combination cases

This blog post focuses on the enhanced unlimited mode, which will gradually replace the traditional unlimited mode as test suites adopt the latest engine versions.

Combination anomalies

Combination anomalies are created by generating a new set of test cases from an existing one. The process for creating combination anomalies resembles the root generation process, which generates test cases from a valid case. The difference is that instead of using a valid case as the base, combination generations use an anomaly test case as the starting point. Each combination anomaly includes a generation path in its metadata, enabling easy reproduction of the anomaly.

Figure 1. Example of combination test case generation based on anomaly selection from the previous generation

Figure 1 illustrates the role of the suite model in creating combination anomalies. The root generation, which is a set of test cases based on the valid case(s), has anomalies for all the different fields. From any of these anomalies, we can generate a new set of test cases, creating a new generation based on the original anomaly. This iterative process can continue, producing further generations with additional anomalies. Each step adds complexity to the test cases and can expose previously unseen issues in the test target.

Exposing new vulnerabilities through combination anomalies

New vulnerabilities can appear when multiple anomalies occur together in combination cases. One real-world example with the HTTP client suite is CVE-2023-38545. This vulnerability involves a heap-based buffer overflow during the SOCKS5 proxy handshake. Reproducing this issue with the HTTP client test suite requires a combination anomaly rather than a single anomaly.

First, the status code must be changed to 301 instead of the default 200. Next, a location header must be introduced, as it is not present by default. Finally, the location header should have an overflow in the hostname, exceeding 255 bytes.

Figure 1. First anomaly changes the status code to 301 (Moved Permanently)

Figure 2. The second anomaly adds the location header and introduces an excessively long overflow in the hostname

The resulting combination anomaly test case (1426@202432), which includes two anomalies, should reproduce the issue. A single anomaly in the location header is insufficient because the system under test ignores the location header when the status code is 200.

When to run the unlimited mode

Defensics provides a fixed set of test cases that are ideal for regression testing after initial findings on a new test target have been addressed. In contrast, unlimited mode is not intended for regression testing because the astronomical number of possible cases makes it impractical. Its primary purpose is to expose new vulnerabilities after the fixed set of test cases has been executed against the test target.

Enhanced unlimited mode achieves this by continuously randomizing the selection of the next anomaly generation, ensuring that each test run is unique. Given sufficient runtime, overall coverage will eventually converge, increasing the likelihood of discovering issues that deterministic test sets might miss.

Figure 1. How the number of possible combinations grows

Figure 4 shows how quickly the number of anomalies grows. For example, if the root generation has 100,000 test cases, combinations with two anomalies would result in approximately 10 billion cases (100k × 100k). Adding a third anomaly increases this to 1 quadrillion cases (100k × 100k × 100k), which is already so many test cases that no one will be able to test those in any reasonable amount of time.

Running unlimited mode is like executing any other test plan. It might be a good idea to configure the test run stop criteria, for example, to limit the running time to 12 hours for overnight testing, and then during daytime the setup can be used for regression testing.