Generation and shrinking design

This document explains how apiprobe turns an OpenAPI document into requests, how it builds deliberately invalid requests, and how it shrinks a failing request into a minimal reproducer.

1. From spec to schema graph

spec.load_spec parses YAML or JSON (JSON is valid YAML, so one parser handles both) and hands the document to Resolver, which inlines every $ref:

Recursive schemas are the tricky part. The resolver memoises every (document, pointer) it resolves and registers an empty dict in the memo before resolving the target's children. When the walk reaches the same reference again it receives that dict, so the result is a genuinely cyclic Python object graph:

Node:
  type: object
  properties:
    children: {type: array, items: {$ref: "#/components/schemas/Node"}}

resolves to a dict node where node["properties"]["children"]["items"] is node. The validator walks the data rather than the schema, so it terminates naturally. The generator bounds recursion with a depth budget (below). A reference chain with no content at all (A -> B -> A) is rejected with a SpecError.

2. Positive generation

generator.Generator is driven by a random.Random seeded with "{seed}:{METHOD path}". Every operation gets its own stream, so results do not depend on thread scheduling when you use --workers.

Each operation receives this plan (with --max-examples N):

# mode purpose
1 example use example/examples from the spec when they validate
2 min smallest lengths, counts and numbers; optional fields omitted
3 max largest lengths, counts and numbers; all optional fields present
4..N random random values inside the constraints

Keyword handling:

Every generated value is re-checked with the built-in validator and regenerated (up to 30 times) if it fails, so generation is correct by construction or rejected, never silently wrong. The test-suite checks this against the jsonschema library over hundreds of random schemas.

Regex generation

regexgen parses the pattern with Python's own regex parser (re._parser) and walks the parse tree: literals, ., character classes and ranges, \d \w \s and their negations, repetition (unbounded repeats capped at +8), groups, alternation, back-references and anchors. Because OpenAPI patterns use search semantics, the emitted core is enough; the result is confirmed with re.search. Example:

^[A-Z]{2}-\d{3}$   ->  "QX-481"
^(foo|bar)+baz?$   ->  "barfoofoobaz"

Lookarounds and other exotic constructs raise UnsupportedPattern; the case is skipped and listed under "notes" in the output rather than crashing the run.

3. Negative generation (exactly one violation)

negative.mutation_sites(schema) enumerates every constraint that can be broken, with its location:

NewPet = {type: object, required: [name, age], additionalProperties: false,
          properties: {name: {minLength: 1, maxLength: 40}, age: {minimum: 0, maximum: 50}, tag: {enum: [...]}}}

/: violates type          /: violates required ('name')   /: violates additionalProperties
/name: violates type      /name: violates minLength (1)   /name: violates maxLength (40)
/age: violates type       /age: violates minimum (0)      /age: violates maximum (50)
/tag: violates enum       /: violates required ('age')

negative_value then (1) generates a valid value, (2) makes sure the containers along the path exist, (3) swaps the target node for candidate violations (-1 for minimum: 0, a 41-char string for maxLength: 40, "dog-not-allowed" for an enum...) and (4) keeps the candidate only if the validator reports exactly one error. Step 4 is what guarantees "exactly one constraint": if age = -1 also broke multipleOf, it would be discarded and the next candidate tried.

At request level, cases.negative_targets adds parameter mutations and "omit a required parameter / required body". Parameter type mutations are only produced for numeric or boolean parameters, because on the wire every parameter is a string and "abc" is a perfectly valid string. The runner walks the list of targets round-robin so every single violation is tried at least once before any repeats.

4. Shrinking

When a check fails for the first time, shrink.shrink greedily minimises the request while it still fails the same way (same check, operation, status and normalised message):

  1. drop optional query/header/cookie parameters,
  2. simplify the body: remove object keys, empty/halve/trim arrays, empty/halve strings and delete single characters, move numbers to 0, halve them, or step them by one toward zero,
  3. simplify parameter values the same way.

Candidates are ordered most-aggressive-first and the first one that still fails is accepted; the loop restarts from the new case until nothing helps or the request budget (80) is spent.

A guard keeps the reproducer meaningful: candidates of a positive case must remain schema-valid (otherwise we would be shrinking a crash into a 400), and candidates of a negative case must remain invalid (otherwise "invalid request accepted" would shrink into a valid request that is legitimately accepted).

Worked example

Suppose the first random request that crashes the example server is

{"name": "f4é漢Hk 2", "age": 37, "tag": "cat"}

Shrinking then proceeds like this (illustrative trace):

step candidate outcome
1 drop name invalid (required) - skipped without sending
2 drop age invalid (required) - skipped
3 drop tag still 500 - accepted
4 name = "" invalid (minLength 1) - skipped
5 name = "f4é漢" (first half) still 500 - accepted
6 name = "f4é" ... "é" still 500 - accepted
7 age = 0 still 500 - accepted

Result: curl -X POST .../pets -H 'Content-Type: application/json' --data-binary '{"name": "é", "age": 0}'.

Shrinking talks to the live API, so side effects matter: each accepted candidate may create a resource. apiprobe therefore stores the response of the winning candidate instead of replaying it, since a replay could now hit "duplicate name" and fail differently.

5. Stateful sequences

stateful.infer_links collects explicit OpenAPI links (operationId or operationRef, with $response.body#/pointer and $response.header.X expressions), then adds heuristic links: a POST on a collection P links to every operation on P/{param}, binding param to the first of param, id, <stem>_id, <stem>Id that exists in the 2xx response schema, or to the last segment of a documented Location header.

For each collection the runner executes up to 10 sequences:

POST /pets            -> 201 {"id": 51, ...}
GET  /pets/51         -> must be 2xx   (else stateful:created_resource_not_retrievable)
PUT  /pets/51         -> must not 404  (else stateful:updated_resource_not_found)
DELETE /pets/51       -> 2xx
GET  /pets/51         -> must be 404/410 (else stateful:deleted_resource_still_available)

Every step also runs the normal response checks, which is how the missing created_at on freshly created pets is caught. The failure stores each step with its link bindings so apiprobe replay can re-run the sequence against a new resource id.