# Adversarial testing for analysis generalizability

Design document for a generic `malvin adversarial` command. The command hunts rules tuned to benchmark fixtures rather than structural witness-graph predicates. Normative background lives in a repo-specific **principles** document; known violations live in an **audit** document. This file is the malvin-side formal system; consumer repos (for example kiss calibration) instantiate it with domain-specific plugins and registries.

---

## Goal and constraint

Many static analyses map definitions and witnesses to per-unit outcomes (coverage credit, lint verdicts, dependency classifications) that should align with ground truth on representative repos. Scalar alignment metrics on benchmark suites belong in ops harnesses, not in unit adversarial tests.

**Adversarial goal:** Each obligation names a falsifiable invariant—locality, monotonicity, rename invariance of threshold index, channel separation—and fails when a rule encodes fixture identity. Tests assert **structural law** on witness-graph shape and outcome predicates via **metamorphic testing** (paired source/follow-up fixtures and metamorphic relations) and **property-based testing** (single-input algebraic laws), not scalar fit on a fixed benchmark tree.

**Hard constraint:** Production analysis stays deterministic. Unseeded randomness is allowed only in test generation (property fuzz, graft shell mutation), never in the analysis under test.

---

## What “non-generalizable” means

An analysis rule fails the quality bar when outcomes depend on:

| Failure mode | Example pattern | Greppable? |
|--------------|-----------------|------------|
| Benchmark dirname inventory | First-level path segments from a known benchmark tree | Sometimes |
| Generic filename inventory | Basenames keyed by name alone, not structural role | No |
| Benchmark crate / argv tables | Workspace crate literals or CLI subcommand blocklists | Sometimes |
| Non-local distant context | Outer directory vocabulary changes inner definition outcomes | No |
| Numeric staircase tuned to one repo | Thresholds fit to one tree topology | No |
| Algebraic violations | Order-dependent set walks, non-idempotent filters | No |
| Channel collapse | Many partition branches folded into one path-gate tree | No |

No single adversarial mechanism catches all of these. The portfolio below is intentional overlap, not duplication.

---

## Witness-graph adversary (abstract)

Static analysis operates over:

- **Definitions** \(D\): atomic units parsed from production sources.
- **Witnesses**: names referenced from test or consumer code—static mention, not runtime proof.
- **Propagation**: bounded import-graph or dependency channels (strict vs expanded witness lattices).
- **Partitions** \(P\): classes derived from topology and evidence channels, not dirname lists alone.
- **Outcome** \(c: D \to O\) under a shipped analysis bound (for example covered/uncovered, pass/fail).

An adversarial obligation is a predicate on \(c\) that must hold under transformations of the repo graph. In **metamorphic testing** terms (Chen, Cheung & Yiu 1998; Chen et al. 2018), each row below is a **metamorphic relation (MR)**: a source fixture \(x\), a follow-up fixture \(x'\) produced by a transform \(T\), and a relation \(R\) that must hold between outputs \(f(x)\) and \(f(x')\)—here \(f\) is the deterministic analysis under the shipped bound. This sidesteps a per-repo oracle (no ground-truth runtime comparison, no suite-wide scalar metric in unit tests) while still falsifying benchmark-tuned rules.

| Transform \(T\) | Metamorphic relation \(R\) (what it falsifies) |
|-----------------|------------------------------------------------|
| Global segment bijection \(\phi\) | \(c(x) = c(\phi(x))\) — path-string keys (rename invariance) |
| Graft shell family \(\{S_i\}\) at distance \(d\) | Inner outcome vector invariant across outer shells — non-local context sensitivity |
| Operator sequences \(\sigma \in \text{Ops}^*\) on expand/filter | Commutation / monotonicity / idempotence on witness sets — order dependence |
| Axis sweeps on \((n_{\text{defs}}, \text{depth}, \text{width})\) | Transition signatures match under \(\phi\) — numeric staircases tuned to one topology |
| Literal / gate-depth audits | Forbidden benchmark tokens must not be required for pass — inventory smuggled into source or tests |

**Synthetic path rule (normative):** Counterexamples use neutral trees (`acme/`, `vendor/`, `widget_tests/`). Benchmark first-level segments and workflow-specific names must not appear in committed unit adversarial fixtures.

---

## Smell-class registry (semantics)

Each smell row is an executable contract, not commentary:

| Field | Role |
|-------|------|
| `id` | Stable smell class (`dirname_inventory`, `channel_collapse`, …) |
| `principle` | Pointer into the principles document |
| `invariant` | One falsifiable sentence |
| `counterexample_shape` | Minimal neutral topology |
| `depends_on` | Ordering between smells |
| `target_modules` | Optional: modules or paths this smell guards (for incremental re-run) |

**Point predicate:** Under the shipped analysis bound, assert outcome on one definition in a minimal fixture—not a suite-wide scalar metric.

**Negation assertion (anti-MR):** A deliberately benchmark-shaped follow-up variant of the same topology (swap neutral segment → token from audit) must not be required for the predicate to pass. Violating this is a forbidden metamorphic follow-up: outcomes must stay stable when the transform is applied.

**Meta-completeness:** Every principle tag in adversarial test modules has a registry row; every row has a running obligation.

---

## Metamorphic testing vs property-based testing

Two oracle-free mechanisms appear in the portfolio; keep them distinct in test docs:

| Mechanism | Shape | Examples | Literature |
|-----------|-------|----------|------------|
| **Metamorphic testing** | Source + follow-up inputs; MR on paired outputs | Rename, graft, surface signatures, negation anti-MRs | Chen, Cheung & Yiu (1998); Segura et al. (2016) |
| **Property-based testing** | Single input; algebraic property on one output | Monotonicity, idempotence, order invariance | Claessen & Hughes (2000) |
| **Metamorphic differential testing** | Two implementations on related inputs; compare outputs | Full pipeline vs incremental op-sequence on frozen graph | Su et al. (2015) |

Single-input lattice laws are properties, not MRs. Paired-fixture rename/graft/surface obligations are MRs. A differential oracle compares two deterministic executions on the same frozen graph—a differential MR in the Su et al. sense.

---

## Invariant laws (algebra and surface)

From the formal model in the principles document:

| Law | Assertion |
|-----|-----------|
| Monotonicity | Adding a witness never decreases covered count (or never weakens a pass outcome) |
| Idempotence | Subtractive filter twice equals once |
| Tier interval | Strict outcome implies expanded outcome for every definition |
| Order invariance | Permuting expand ops (before final filter) yields same pre-filter witness set |
| Void fail-closed | Empty void attestation → void definitions stay uncovered |
| Fixpoint bound | Alternating expand/filter reaches fixed point within bounded steps |

**Outcome-surface topology:** Parameterize outcomes along axes (definition count, import depth, submodule width). Record **transition signatures**: `(axis, index, direction)` where outcomes flip. Under global segment bijection, crossing indices must match (catches path-string-tuned thresholds). At most one covered→uncovered transition per axis; no unattested plateaus on inflator/void partitions; isomorphic definitions in the same partition flip at the same index.

**Graft isolation:** Inner outcome vector for a fixed minimal inner graph must be identical when only distant outer shells change vocabulary—including shells that use benchmark-shaped dirname tokens at hop ≥ distance threshold.

**Channel coherence (optional):** Credited evidence channel must match partition class. Flag partition credited via the wrong channel alone.

**Path-gate depth:** Consecutive path or filename branches without an intervening graph-feature check must not exceed a documented budget.

---

## Tier stack (capability ordering)

```
Authorization:  unit obligations must not embed benchmark paths
Smell registry: executable rows + meta-completeness driver
Literal audit:  ban benchmark tokens in analysis source
Rename (MR):    global segment bijection invariance
Graft (MR):     non-local shell isolation
Algebra (PBT):  lattice laws on expand/filter operators
Surface (MR):   transition-signature coherence under rename
Guards:         path-gate depth, channel typing (cheap)
Ops:            ablation on benchmark suite (metric, not structure)
```

Cheap structural guards precede expensive fuzz. Rename (global bijection MR) and graft (outer-shell MR) are logically independent metamorphic tests: rename catches path-string keys; graft catches distant vocabulary. Composed transforms \(\phi \circ \text{graft}(S)\) may fail even when each MR passes alone (composition of metamorphic relations; see Segura et al. 2016 §4).

---

## Smell-class catalog (initial rows)

| id | Audit area | Invariant gist |
|----|------------|----------------|
| `dirname_inventory` | Path segments | Integration-cone credit must not veto on first-level segment names alone |
| `filename_inventory` | Basenames | Outcome must depend on structural role, not basename |
| `cli_argv_inventory` | CLI routing | Bulk exclusion must not key on workflow module names |
| `workspace_crate_inventory` | Workspace layout | Auxiliary crates by suffix pattern, not vendor crate literals |
| `repo_root_vocabulary` | Root allowlists | Partitions must not be global basename allowlists |
| `numeric_staircase` | Thresholds | Threshold placement must not encode one-repo scalar knobs |
| `channel_collapse` | Evidence channels | Partition outcome must not collapse evidence channels |
| `non_local_context` | Graft | Inner outcome invariant to distant dirname shells |

Consumer repos extend this catalog; the malvin command does not hard-code domain smells.

---

## Per-obligation documentation (field spec)

Every adversarial obligation must declare:

```
principle:      <section in principles document>
smell_registry: <id>
metamorphic:    <MR id or "none" for single-input PBT>
follow_up:      <transform T, or "n/a">
invariant:      <one falsifiable sentence — the MR R>
counterexample: <minimal shape, synthetic paths only>
```

Vague names like `analysis_works` are forbidden. The invariant states what breaks if someone adds a benchmark inventory.

---

## What stays outside unit adversarial tests

- Suite-wide **scalar alignment** regression (ops harness).
- Full-repo golden layouts from benchmark trees—migrate to synthetic equivalents over time.
- Parser edge cases unrelated to analysis generalizability.
- **Ablation matrix** (disable one hook at a time on benchmark targets): metric concentration detection, not structural law—lives in ops tooling, not fast unit gates.

---

## `malvin adversarial` command design

### Role

`malvin adversarial` is an oracle-free hunt engine over a witness graph. It takes:

1. A **smell registry** (`smell_registry.toml` or equivalent).
2. A **principles** pointer (markdown path).
3. A **token manifest** derived from audit findings (benchmark dirname segments, workflow basenames, crate literals).
4. A deterministic **analysis plugin** \(f\) (subprocess or library hook).

It does not replace `malvin constrain` or `malvin code`. It feeds them: on violation, emit a shrunk witness bundle; on clean run, gate loops may proceed.

### Proposed subcommands

| Subcommand | Purpose |
|------------|---------|
| `check-registry` | Schema validation, `depends_on` acyclicity, meta-completeness (every row compiles; every principle tag resolves). |
| `exec` | Compile each registry row into fixture + predicate; run tier stack as scheduled pipeline; report violations keyed by `smell_id`. |
| `compose` | Search composed transform chains up to a materialization budget; find shortest chain that falsifies any relation (rename ∘ graft ∘ permute, etc.). |
| `invert` | Negation-first hunt: generate forbidden follow-ups from token manifest; succeed when outcomes change under substitution (proves inventory dependence). |
| `diff-rows` | After a git diff, list registry rows whose `target_modules` changed—incremental re-run only. |

### CLI inputs and outputs

**Inputs:**

- `--registry <path>` — smell registry TOML.
- `--principles <path>` — normative constraints document.
- `--token-manifest <path>` — audit-derived forbidden tokens for literal audit and invert.
- `--bound <name>` — analysis bound (consumer-defined; e.g. shipped vs experimental).
- `--plugin <id|path>` — deterministic analysis hook.
- `--budget materializations=N` — cap temp-repo creations (compose, graft sweeps).
- `--target-smell <id>` — focus on one registry row.

**Outputs:**

- Non-zero exit on structural violation.
- Violation report: `smell_id`, transform chain, minimal counterexample topology.
- Shrunk bundles under `.malvin/adversarial/shrunk/<smell_id>/` (temp-repo topology + transform that broke relation \(R\)).
- No automatic commit of permanent test files—the human or a follow-up `malvin constrain` session decides.

### Tier stack inside the command

The tier stack is a **compile-time schedule** inside `exec`, not a folder layout in the consumer repo:

| Phase | Tier | Rationale |
|-------|------|-----------|
| 0 | Authorization + token manifest | Stop smuggling before more obligations |
| 1 | Registry + meta-completeness driver | Lock intent |
| 2 | Literal audit | Cheap; closes grep gaps from audit |
| 3 | New smell rows for highest-severity audit gaps | Point predicates + negation |
| 4 | Algebra PBT on frozen graphs | Order bugs without fixture explosion |
| 5 | Graft engine | Non-local failures |
| 6 | Surface topology prototype | Numeric hacks |
| 7 | Rename isomorphism | Complements graft |
| 8 | Random topology fuzz (optional) | After temp-repo harness exists |
| 9 | Path-gate / channel guards | Optional hardening |
| — | Ablation (ops) | Parallel; not in fast unit gate |

`compose` may invert cheap-before-expensive ordering when the goal is finding violations, not minimizing green-build wall-clock.

### Integration with malvin workflows

| Workflow | Integration |
|----------|-------------|
| `malvin constrain` | Gate may require `adversarial exec` or `compose --budget N` clean before `KPOP_SOLVED`. |
| `malvin code` | Optional pre-gate adversarial scan when plan touches analysis modules listed in registry `target_modules`. |
| `malvin tidy` | Surface adversarial failures alongside kiss and other repo gates. |
| `malvin invent` | Invented analysis ideas should name which smell rows they might violate; invert can falsify before code lands. |

### Artifact layout (malvin repo)

```
.malvin/
  adversarial/
    shrunk/           # violation bundles from exec / compose / invert
smell_registry.toml   # optional default; consumer repos may own their own
token_manifest.toml   # derived from audit; consumer-maintained
```

Consumer repos keep principles, audit findings, fixtures, and plugin implementations. Malvin owns the command, schedule, and shrunk-bundle format.

### Analysis plugin contract

A plugin implements deterministic \(f\) over a materialized repo graph:

```
Input:  temp directory tree + optional config (bound name, language flags)
Output: structured outcome map (definition id → outcome) + optional metadata
        (partition class, winning channel) for channel-coherence guards
```

Plugins must be deterministic: two runs on the same frozen fixture produce identical outputs. Non-deterministic agents are out of scope for \(f\); malvin agent sessions are tested separately if needed.

### Per-obligation header template (consumer test modules)

```text
/// principles: <principle section>
/// smell_registry: <id>
/// metamorphic: <MR id or "none">
/// follow_up: <transform T, or "n/a">
/// invariant: <one falsifiable sentence — the MR R>
/// counterexample: <minimal shape, synthetic paths only>
```

---

## References

### Metamorphic testing (foundations)

- Chen, T.Y., Cheung, S.C., and Yiu, S.M. (1998). *Metamorphic testing: A new approach for generating next test cases.* Technical Report HKUST-CS98-01, Hong Kong University of Science and Technology.
- Chen, T.Y., Kuo, F.-C., Liu, H., Poon, P.-L., Towey, D., Tse, T.H., and Zhou, Z.Q. (2018). *Metamorphic Testing: A Review of Challenges and Opportunities.* ACM Computing Surveys 51(1), Article 4.
- Segura, S., Fraser, G., Sánchez, A.B., and Ruiz-Cortés, A. (2016). *A Survey on Metamorphic Testing.* IEEE Transactions on Software Engineering 42(9):805–824.

### Property-based testing

- Claessen, K. and Hughes, J. (2000). *QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs.* Proc. ICFP 2000, pp. 268–279.

### Metamorphic / differential oracles

- Su, F.-H., Bell, J., Murphy, C., and Kaiser, G.E. (2015). *Dynamic Inference of Likely Metamorphic Properties to Support Differential Testing.* Proc. IEEE/ACM AST 2015, pp. 55–59.

### Input transforms and oracle-free settings

- Segura, S., Towey, D., Zhou, Z.Q., and Chen, T.Y. (2020). *Metamorphic Testing: Testing the Untestable.* IEEE Software 37(3):46–53.
- Zhou, Z.Q., Xiang, S., and Chen, T.Y. (2016). *Metamorphic Testing for Software Quality Assessment: A Study of Search Engines.* IEEE Transactions on Software Engineering 42(3):264–284.

### Lineage

- Kiss calibration instantiation: `kiss/adversarial.md` (domain-specific section (ii) and file paths).
- Malvin design logs: kiss repo `.malvin/logs/` (KPop violation hunt, doc split, metamorphic vocabulary, CLI generalization invent runs).
