incremental fuzzing of the admissible input space: a test framework

[0xekez]

in Zargham and Shorish's Generalized Dynamical Systems, systems are modeled as having a set of admissible inputs at any step in their evolution. given the ability to determine all of the admissible input for a system at a given step, and information about the state transition process of the system, one can then extrapolate what the possible next states of the system are by simulating all admissible inputs.

what i propose here is that for smart contracts, this admissible input space may be considered to be the interface that they implement. for example, for a DAO DAO voting module, a trait to describe its interface might look like:

pub trait VotingModule {
  fn voting_power_at_height(address, height) -> Result<Uint128, Error>
  fn total_power_at_height(height) -> Result<Uint128, Error>
}

in this example, the admissible input space is all configurations of a voting module wherein this interface is satisfied.

given an implementation of this interface for each voting module, one might write a simple test:

#[test]
fn test_revoting() {
  let me = ProposalSinglle::new();
  let dao = DAO::with_proposal_module(me);
  let voting_power = dao.total_power_at_height(42);
  // ...
}

the moment that we construct DAO::with_propose_module, the testing framework knows that the tester does not care about the specifics of any module other than the proposal module: me. the critical observation is that the configuration of the voting module used can be completely randomized.

constraining the DAO based on the interfaces that it must implement, and then randomizing the actual configuration within those constraints lets us gradually fuzz the admissible input space of the DAO as this test gets run.

to integrate this in the type system, we extend the voting module interface with an additional method that gives a randomly configured version of the voting module:

pub trait VotingModule {
  fn randomize(seed) -> Box<dyn VotingModule>
}

the test framework then first selects a random voting module to use with the test, and then creates a randomly configured version of the module to be used in the test. a random seed makes this process reproducible.

beyond DAO DAO

what is described here is not voting module, nor is it DAO DAO specific. the general formalism here is:

create an interface I which implements a module interface and provides a method randomize which when called produces a randomized instantiation of that interface.

this is applicable to any smart contract system with well-defined interfaces.

[blue-note]

this admissible input space may be considered to be the interface that they implement.

can you explain how this maps to the idea of a system moving through a set of states?

[0xekez]

imagine that we're writing a test using this framework that tests that votes can not be cast twice, by default, with a proposal module. it might look something like:

let dao = DAO::unconstrained();
let id = dao.proposal_module.propose(vec![])?;
dao.proposal_module.vote(id, sender)?;
dao.proposal_module.vote(id, sender).unwrap_err();

every time we're calling a method on the proposal_module we're slightly constraining the set of admissible inputs, but saying nothing about the underlying configuration. the test framework, as time passes and new random iterations are tried, may run this test with multisig voting, a proposal with multiple proposals already, ranked choice voting, etc.

[0xekez]

system moving through a set of states

i'd say that we indicate the state changes in our calls to the interfaces. i'd say we're making high-level statements about what state change should occur. does that sound reasonable to you?

i know this is a little un-mathy. my thought is that as-of-yet i have no clue how to model DAO's with GDS, but i think we can approximate math that explores the input space with fuzzing.

[0xstepit]

The idea is very interesting. I'm curious on that:

in this example, the admissible input space is all configurations of a voting module wherein this interface is satisfied.

Why did you say that the input space is given by "configurations of a voting module"? At a first read of the paper you cited I would imagine that:

• interfaces: define the state transition logic.
• input space: given by all combinations of the admissible input to the interface methods implementation.

Have you thought about how to implement an equilibrium state for a test?

[0xekez]

i think this is a lovely distillation. let me attempt to describe this in your words. consider the following hypothetical test which tests that a proposal passes when the majority vote yes:

let dao = DAO::with_voting_powers(vec![("blue", 6), ("violet", 4)]);
let id = dao.proposal_module.propose(vec![]);
dao.proposal_module.vote(id, "blue");
assert!(dao.proposal_module.passed(id));

interfaces: define the state transition logic

here our proposal module interface (assuming it contains a propose, vote, and passed method) define the set of possible state transitions.

input space: given by all combinations of the admissible input to the interface methods implementation

the business of the DAO type is to do this permutation and fuzzing of admissible inputs. another way of describing the test above is: a test that given a proposal module the majority pass. "given a proposal module" means that the DAO type knows that it may permute all other configuration options of the test. it may, for example:

1. run this test with a multiple choice proposal module who has six pending proposals.
2. run this test with a DAO with NFT voting and revoting enabled.
3. run this test with a DAO with a parent DAO and many pending unstaking claims.
4. etc..

in short: the DAO's instantiation has constrained the admissible input space to the set of DAO configurations where blue and violet have a particular ratio of tokens. otherwise, the testing framework may try anything and fuzz any other configuration.

does that help clear things up? if not, i'd be very interested in more of your thoughts.

[0xekez]

Have you thought about how to implement an equilibrium state for a test?

my idea here is to cheat a little and move the business of detecting out-of-equilibrium states to the author of the test. in the example from my previous comment, i'd say an equilibrium state is any state that does not cause the assert! statement to fail.

[0xstepit]

"given a proposal module" means that the DAO type knows that it may permute all other configuration options of the test

Thanks for the example, now it is more clear. Correct me if I'm wrong, your idea is to make (a kind of) input matrix that span (more or less) all the input space of the test case?

It would be very nice to be able to produce little state transition test that can be mixed together to produce a more complex state transition logic in a fuzzy way.

The problem I see here is that is very hard to make a fuzzy logic and at the same time impose all the correct assert.

If you are already working on it, it would be amazing to look at a concrete example 😊