Random Shrinking in state machine tests

[henriiik]

Hello!

I am using proptest_state_machine to write some tests. Whilst experimenting, i noticed that it appears that the input for shrinking the collection of transitions is the original collection of transitions, rather than the transitions that were able to be executed against the system under test.

here is a portion of the verbose log output:

proptest: Next test input: (initial_state, transitions) = (RefState { wallet_state: None }, [RegisterWallet, RegisterAlreadyRegisteredWallet, DeregisterWallet, RegisterDeregisteredWallet, DeregisterWallet, RegisterDeregisteredWallet, DeregisterWallet, RegisterDeregisteredWallet])

Running a test case with 8 transitions.

Applying transition 1/8: RegisterWallet

Applying transition 2/8: RegisterAlreadyRegisteredWallet
thread 'experiment::test_fn' panicked at libs/spbt/src/experiment.rs:178:17:
OMG2!
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
proptest: Test case failed: OMG2!
proptest: Next test input: (initial_state, transitions) = (RefState { wallet_state: None }, [RegisterWallet, RegisterAlreadyRegisteredWallet, DeregisterWallet, RegisterDeregisteredWallet, DeregisterWallet, RegisterDeregisteredWallet, DeregisterWallet])

Running a test case with 7 transitions.

Applying transition 1/7: RegisterWallet

Applying transition 2/7: RegisterAlreadyRegisteredWallet
thread 'experiment::test_fn' panicked at libs/spbt/src/experiment.rs:178:17:
OMG2!
proptest: Test case failed: OMG2!

As you can see after the abstract execution proptest generated a sequence of 8 transitions. When executing those transitions against the system under test it failed after the second transition. proptests current behavior appears to be attempting to shrink the original sequence of transitions from the abstract execution (8 transitions) rather than the transitions that were executed against system until it failed (2 transitions).

Is this behavior deliberate? Would it not be better to shrink based on the sequence of transitions that led to failure as this is more likely to lead to a minimally reproducible case?

Additionally it appears from my understanding of the code, that it only shrinks from the back until it removes the bad transition, and does not try to remove random transitions from before it.

proptest/proptest-state-machine/src/strategy.rs

Lines 295 to 322 in d6f95d4

	if let DeleteTransition(ix) = self.shrink {
	if self.included_transitions.count() == self.min_size {
	// Can't delete any more transitions, move on to shrinking them
	self.shrink = Transition(0);
	} else {
	// Delete the index from the included transitions
	self.included_transitions.clear(ix);
	self.last_shrink = Some(self.shrink);
	self.shrink = if ix == 0 {
	// Reached the beginning of the list, move on to shrinking
	Transition(0)
	} else {
	// Try to delete the previous transition next
	DeleteTransition(ix - 1)
	};
	// If this delete is not acceptable, undo it and try again
	if !self.check_acceptable(None) {
	self.included_transitions.set(ix);
	self.last_shrink = None;
	return self.try_simplify();
	}
	// If the delete was accepted, remove this index from shrinkable
	// transitions
	self.shrinkable_transitions.clear(ix);
	return true;
	}
	}

My (naive) expectation would be that given a sequence of transitions leading to a failure, the shrinking would start from the failing sequence and discard intermediary transitions in order to determine the minimal sequence of transitions needed to reproduce the failure.

I am willing to help contribute a fix :)

[tzemanovic]

Hi, what are you using for the number of transitions in the prop_state_machine! macro invocation? There's one thing that may be preventing shrinking of the number of the transitions; when you use a single value rather than a range, the minimum number of transition is set to this value, which prevents any DeleteTransition to be applicable (the condition if self.included_transitions.count() == self.min_size in fn try_simplify). I will open a PR to improve this so that the minimum doesn't prevent deletions, which is both unnecessary and unexpected.

If you use a range (e.g. ..20) for the number of transitions fn try_simplify first attempts to delete transitions from the back of the vec, as that cannot invalidate pre-conditions and once that's exhausted, it also tries to delete transitions anywhere else in the vec.

[tzemanovic]

@henriiik pls let me know if this has solved your issue. If not, we can reopen this

[henriiik]

@henriiik pls let me know if this has solved your issue. If not, we can reopen this

@tzemanovic This does not solve my issue.

My main problem is that the shrinking only shrinks one transition from the end for each iteration.

If the initial transition list contains 100 transitions and the test fails after 10 transitions, the next iteration of the test will be initiated with 99 transitions and still fail after 3. It will take 90 test iterations to reduce the test down to a state where it can start removing relevant transitions.

I use proptest to test networked services and every transition makes at least one network call and thus usually takes a minimum of 100ms but often longer. If the test failure is due to a timeout it's of course a lot worse.

Sorry for the slow reply, and thank you for the fix you did make! It was quite annoying to have to specify the minimum and sometimes get a very low transition counts in tests.

[tzemanovic]

Closed by #388