How to write fuzzers for encoding/decoding (potentially recursively nested) datatypes?

Learn
1

Hello everyone!

As you might know from the other topics I have recently been posting, I am building a library to interact with the Ethereum Blockchain. Requests/responses to code that lives in Ethereum are done using a special encoded format, known as the ‘Ethereum ABI Encoding’.
It is quite some work to make sure that this encoding/decoding happens properly (But Elm’s strong typing definitely helps to ensure that the implementation is reasonably likely to be correct and at least not break at runtime :heart: )

In any case, this means I am creating my own Encoders and Decoders, which in functionality are very similar to the built-in JSON ones.

Now I want to create some fuzz tests that test the encoding/decoding process. To be exact:

  1. Create an arbitrary data structure made out of Eth ABI types.
  2. Use the matching encoder for that datastructure to encode it to a Hexstring.
  3. Use the matching decoder for that datastructure to (if all goes well) decode it back to the data structure.

To be more exact:

  1. Creating arbitrary datastructures is done using functions of type a -> Result String b, since there is not for every type a 1:1 mapping between Elm’s built-in types and Ethereum’s types.
  2. The encoder function needs to be picked based on what datastructure we chose in the previous step. These are functions of type b -> Encoder (and there is an encode function that turns an Encoder into a Hexstring)
  3. The decoder function needs to be picked based on what datastructure we chose in the first step. These are of the opaque type Decoder t (they have to keep track of some internal offsets etc. when chaining multiple decoders), but they can be used together with decodeString which has the type Decoder b -> Hexstring -> Result String b to regain the b we put in.

So, seems fine: We can just write the Fuzzer function to create a triple with the type: Fuzzer (Result String b, b -> Hexstring, Hexstring -> b), and for this (x, y, z) call Expect.equals (x |> Result.andThen (y >> z))?

But this is where I am stuck:

  • How can such a triple be used as input for Fuzz.oneOf? Each of the triples would have a different b in there, so how can I combine them in one list?
  • How can I combine these fuzzers such that I can create a recursive data structure fuzzer? (It is possible to create/represent arrays (of arrays of arrays …) with different dimensions and types in the Ethereum ABI, and I’d like to be able to fuzz-test not only bool, int256 and uint256, but also int256[8], uint[8][2] and bool[3][][42][][].

Your help is greatly appreciated!

2

It is not entirely clear to me what Encoder is but what I’d suggest is just to create one Fuzzer (Result String b) per b and have different fuzz tests for each.

So, seems fine: We can just write the Fuzzer function to create a triple with the type: Fuzzer (Result String b, b → Hexstring, Hexstring → b)

If you have one test per b, it simplifies this, since if I understand correctly, you don’t have to pair it with the correct b -> Hexstring and Hexstring ->. You just have to call the correct one in the tests.

How can I combine these fuzzers such that I can create a recursive data structure fuzzer?

What is your elm type representation of those arrays?

3

Just a general remark: make sure you bound the recursion of the fuzzer to a fixed depth. It will blow the stack if you don’t.

Also I think a concrete code example would help.

4

Currently List Int256, List Bool, List String, etc. for the input types themselves.

The dynamic_array encoder accepts any list, whereas the fixed-size array encoder will (should; I need to fix it) reject any List of the wrong length (and thus return a Result)

And the decoding dynamic_array and array will take an element decoder of type Decoder a and the encoded value and turn this back into Result String List a.

:+1:

The current Fuzzing code lives here: Tests.EthABI.Fuzz, where you can see the implementation of what I described in the first post. The actual test that uses this fuzzer currently lives here