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

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!

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?

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.

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

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.