Skip to content

Research: PathGrind-style branch-flip input generation for executable ownership witnesses (bounded kill-first spike) #463

Open

Description

@PhysShell

Classification

P3 RESEARCH / test-only / reuse-first / kill-first. No production engine, solver, compiler/runtime or diagnostic change authorized.

Historical donor: codelion/pathgrind (GPL-3.0), fuzz/fuzz.py, settings.cfg, An Empirical Study of Path Feasibility Queries. PathGrind is an old 32-bit x86 Linux dynamic-symbolic/concolic fuzzer built on a Valgrind fork + STP + Python 2; latest master commit 2017-03-25. No port, installation or code copying.

Research question: new value beyond existing issues?

Could a tiny, independent, test-only branch-flip input generator take a validated ownership diagnostic and produce a concrete runnable input that exercises a selected conditional release/use path, with demonstrable added value over hand-written fixtures?

  • #431 owns targeted path-feasibility analysis / SAT-UNSAT-UNKNOWN (do not duplicate its oracle or build a global solver).
  • #270 owns WPF/GC retention witness tests (not a general input generator or concolic engine).
  • #405 owns semantic mutation fixtures; #424 owns stateful path pruning; #269 owns analysis trace/first divergence.
  • This issue is strictly candidate-input generation + concrete replay/measurement when an existing oracle has enough faithful predicates. If Research: COVA-inspired targeted path-condition oracle for ownership soundness (bounded spike) #431 already covers it, mark DUPLICATE/STOP rather than building a second system.

Concrete donor mechanics to audit

  1. Run one seed → collect conditions on executed path → negate a selected branch and solve only necessary earlier constraints → propose a new input → rerun → record observed path and outcome.
  2. Compare no pruning / duplicate-prefix elimination / independently justified constraint subsumption for unique reproduced paths per query and wall time, preserving negative controls.
  3. PathGrind's constraint_implies is a narrow handwritten syntactic heuristic, not generic proof of implication; the code also skips unsupported translation paths such as STPShiftError. Such omitted facts must not turn into safe or UNSAT conclusions. Audit historical branch semantics, symbolic input scope and solver assumptions before borrowing any algorithmic claim.
  4. Distinguish SAT under encoded conditions from actually replayed reachability, and a replayed path from proof that an ownership violation exists.

Proposed gates (nothing executes under this issue)

Gate 0: AS-IS / reuse first.

Gate 1: preregister a tiny oracle-based design.

  • 4–6 paired independently reviewed positive/negative C# fixtures: nested guard reaches resource release or use; impossible conjunction; predicate value changes between checks; at least one checked/overflow or alias/external-call boundary marked unsupported. Avoid path explosion.
  • Freeze source/fixture SHA, target predicate, initial input, expected behavior, resource identity, environmental dependencies and exact compiler/runtime semantics; include a null/unknown negative control.
  • Test-only candidate result schema: MODEL_SAT_UNREPLAYED, OBSERVED_REPRO, UNSAT_COMPLETE_MODEL, UNKNOWN_OR_INCOMPLETE, REPLAY_FAILED (plus trace/input/provenance/query cost). No status upgrades based on LLM conjecture.
  • Define independent replay and path condition matching; an unsatisfied runtime environment or unmodeled condition makes result UNKNOWN, not proof of safe ownership.

Gate 2: optional disposable experiment, separate GO required.

  • Only if Gate 0 found an uncovered seam: compare baseline hand-made cases vs minimal branch flip; report new adjudicated defects, distinct witnessed paths, missed genuine paths, input bytes, query count, CPU/memory/time.
  • Challenge every pruning rule with a mutation that breaks its implication assumptions. Fail closed on solver unknown/timeout, hidden branch facts, stale values or unsupported C# operations.
  • Hard budget, kill on no unique gain, poor reproducibility, or dependency on a broad new concolic stack.

Decision

Return GO-NARROW / PARK / KILL, an explicit overlap map to #431/#270, exact source links and at most a minimal reproducible fixture proposal. No project rewrites, installed Valgrind 3.x, STP tarball, production warning suppression, new CI gating, or automatic fixes.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions