state-space explosion

Concept

State-space explosion is illustrated in the cited microprocessor test-generation case study as the rapid growth of generated cases when case-splitting over instruction variants and test-sequence length. In that study, sequence tests were useful because they required less direct control over processor state, but they were more vulnerable to explosion than unit tests; the authors mitigated the problem with tactic-level heuristics and constraints expressed as test purposes.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 1 chunks

Wiki v1

WIKI

Overview

In the provided case study on model-based test-program generation for a microprocessor, state-space explosion appears as the rapid growth of generated cases when the test-generation process case-splits over many instruction variants across increasing sequence lengths. The assembly language in the study has 56 variants, and sequences of length 3 can lead to 56 + 56^2 + 56^3 = 178808 cases at one point in the process. [C1]

Where it arises

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

sequence testing part of → 90% 1e

Sequence testing is susceptible to state-space explosion.

LINKED ENTITIES

1 links

model-based testing context The evidence states that the approach was carried out in a generic model-based testing framework, within which state-space explosion had to be addressed.

CITATIONS

6 sources

6 citations — click to expand

[1] Case-splitting over 56 assembly-language variants causes rapid growth over sequence length, with length-3 sequences producing 56 + 56^2 + 56^3 = 178808 cases. Test Program Generation for a Microprocessor: A Case Study

[2] Unit tests impose stronger assumptions about access to registers and memory, while sequence tests make weaker assumptions but are more vulnerable to state-space explosion. Test Program Generation for a Microprocessor: A Case Study

[3] The study used tactic-level heuristic adaptations and test-purpose constraints to address state-space explosion; the example list_all is_logic ι reduces the sequence space to 7 + 7^2 + 7^3. Test Program Generation for a Microprocessor: A Case Study

[4] The reported load-and-store sequence scenario took 39 seconds for test partitioning and 42 seconds for test data selection, producing 1170 subgoals; other scenarios took between two and twenty seconds. Test Program Generation for a Microprocessor: A Case Study

[5] The executable model compiled in less than a second, and constraining each scenario to about 1000 test cases kept test compilation below 3 seconds. Test Program Generation for a Microprocessor: A Case Study

[6] The modeled machine used linear memory as a total, infinite function from natural numbers to memory cells, requiring memory comparisons to be weakened to finitized conformance relations. Test Program Generation for a Microprocessor: A Case Study