Skip to content

Software Quality

Input

The input is the data the code under test runs on.

Methods are not distinguished by the input's surface. Arguments, file contents, packets, the clock's readings, even the scheduler's interleaving choices are all just bits the program reads (a deterministic-simulation harness turns scheduler interleavings into seed-driven bits). Two orthogonal things distinguish methods instead:

  • Source — where the input comes from: pinned by the author (fixed), produced from a bit source under some steering signal (generative), or taken from the running system (live).
  • Shape — whether those bits are used raw or decoded through a schema into a well-formed, structured value.
  • Fixed
  • Generative
    • random
    • feedback
    • solver
    • exhaustive
  • Live

Source — where do the bits come from?

  • Fixed. Pinned at authoring time; no RNG — the value is the input. Example tests, snapshot / approval, acceptance / BDD.
  • Generative. Produced from a bit source. Random sampling is blind; the other three are steered, each using a signal to pick the next input:
    • Random. Blind sampling. Dumb fuzzing; property-based testing's default seed stream.
    • Feedback — a runtime signal used to steer. Usually code coverage (AFL++, libFuzzer; targeted property-based testing via Hypothesis target()), or a fitness function a metaheuristic optimizes, as in search-based testing.
    • Solver — constraint-solving derives bits that reach a path. Symbolic / concolic execution (KLEE, SAGE).
    • Exhaustive / systematic — enumeration deliberately covers the (bounded) space. Combinatorial (pairwise), boundary / equivalence partitioning, bounded model checking.
  • Live. The bits come from the running system, not the harness — real production traffic, neither pinned nor synthesized. Parallel run multicasts it to two implementations; production monitoring observes it as it arrives.

Shape — a decoder layered on top

A schema is a function bits→well-formed value\text{bits} \to \text{well-formed value}: it decodes the bit source, random or steered, into a structured input. A generator is this — Gen a≈Seed→a\mathsf{Gen}\ a \approx \mathsf{Seed} \to a, a bit source plus a decoder. Shape is orthogonal to the source:

unshaped (raw bits) shaped (schema decoder)
random dumb fuzzing (radamsa) property-based testing (QuickCheck, Hypothesis)
steered coverage fuzzing on bytes (AFL) structure-aware fuzzing (libFuzzer + arbitrary); targeted PBT

Structure-aware fuzzing takes the coverage-guided byte stream and runs it through a PBT-style generator to get a valid structured input — same shape layer, RNG swapped for a steered source.

Shape isn't strictly all-or-nothing: a generator constructs valid values, but the same effect comes from reject / assume — filtering the raw stream rather than building from it, at worse efficiency. Shrinking is a separate post-find concern, not part of the input axis.

Mapping to the established vocabulary

The standard survey of automated test-case generation (Anand et al. 2013)1 enumerates five methodologies, which map onto the source-and-shape tree:

  • Random testing (and adaptive random testing) ≈ generative random.
  • Search-based testing ≈ generative feedback — coverage-guided fuzzing is search over the input space.
  • Symbolic / concolic execution ≈ generative solver.
  • Combinatorial testing ≈ generative exhaustive.
  • Model-based testing (Utting et al. 2012)2 ≈ the shape layer: a schema or state-machine model that decodes bits into valid, structured inputs.

Referenced by

References

  1. Anand, Saswat, Edmund K. Burke, Tsong Yueh Chen, et al. 2013. "An Orchestrated Survey of Methodologies for Automated Software Test Case Generation." Journal of Systems and Software 86 (8): 1978–2001. https://doi.org/10.1016/j.jss.2013.02.061. ↩

  2. Utting, Mark, Alexander Pretschner, and Bruno Legeard. 2012. "A Taxonomy of Model-Based Testing Approaches." Software Testing, Verification and Reliability 22 (5): 297–312. https://doi.org/10.1002/stvr.456. ↩