Repository navigation
[TS PBT] Reuse bounded command models and state invariants in hybrid search #402
Description
Current state (2026-10-14)
Audited against usvm main at 19866c959d.
Stateless property definitions, joint input support and bounded scalar/array observations exist. No command-model sequence search/reduction implementation was identified.
Remaining acceptance boundary
Implement bounded command sequences with guards, model/state invariants, execution provenance and validity-preserving reduction. Reuse existing codecs/oracles/budgets; do not relabel repeated stateless samples as model-based stateful testing.
Original report and acceptance context, retained for traceability
Part of the full #345 delivery. Builds on #395, #353/#354, and #396/#398. Coordinate with #400 for dependent sequence generation without making the two implementations cyclic.
Delivery stage
This is a stage-two extension of #345. Complete and record the core assessment in #405 before accepting this extension's end-to-end integration and results. Literature, interface design and focused experiments may start earlier; the extension never blocks #355 or #405.
Reuse the completed core contracts. This issue owns any extension-specific changes to observation, binding, scheduling, replay, shrinking and feedback integration, with focused follow-up PRs; do not retroactively broaden #351/#352 or require already completed core issues to reopen. A negative or inconclusive pilot is recorded honestly and informs design; it does not silently cancel this full-roadmap obligation.
Publish a separately identifiable extension configuration and evaluate it against the same original oracle with the extension disabled. Its final held-out evaluation belongs to #357 and is reported separately from the development pilot.
Goal
Reuse PBT model-based command sequences, guards and postconditions to find stateful faults across a bounded sequence of operations.
Scope
- Support a bounded synchronous command model with an explicit initial model/SUT state, command identity/arguments, pure admissibility guard and concrete postcondition/invariant. The sequence is one property invocation.
- Reset model/SUT state between samples, replay and shrink attempts; preserve intended state and aliases between commands in the same sequence. This extends [TS PBT][P0] Align and simplify property execution semantics before integration #384 explicitly without introducing persistent cross-sample module state.
- Begin with a concrete collection/cache-like model and bounded command count. Use supported primitive/tuple arguments and explicit lowering/unrolling rather than requiring arbitrary object graphs or concurrency.
- Preserve the user's reference model and original command checks as the concrete oracle. Record per-step observations and hypothesis contexts keyed by command/state features.
- Let USVM select arguments and/or a bounded continuation of a concrete prefix. Reconstruct/reexecute the prefix faithfully; do not assert a sampled heap as a universally reachable symbolic state.
- Share the common total deadline and target/result/replay contracts. Track sequence bounds, unsupported commands, divergence and model errors separately.
- Minimize command sequences and arguments with backend support, preserving executable guards and the same failure. Deleting a setup command must not turn a failure into an invalid sequence.
- No async scheduling, distributed state, uncontrolled I/O or arbitrary environment snapshotting is required.
Definition of Done
- A real or representative stateful API has a confirmed sequence-dependent fault that is not exposed by isolated calls from the initial state.
- PBT state/command observations guide a bounded symbolic continuation, which reproduces through the full original command model.
- Cross-sample reset, within-sequence mutation, invalid guards, prefix replay and sequence shrinking have focused tests.
- The model, author effort, bounds and supported commands are published. [TS PBT] Evaluate causal contributions of property-aware feedback and bounded extensions #357 compares the same stateful oracle with and without feedback and with PBT-only generation.
Activity