[Simplicity] Fuzz testing vectors

[Russell O'Connor]

On Mon, Nov 11, 2019 at 10:29 PM Gregory Maxwell <gmaxwell at gmail.com> wrote:

> The result is a collection of 7371 inputs extracted from a few billion
> attempts that collectively hit the as broad a coverage footprint as I
> observed in this test run:
>
> https://people.xiph.org/~greg/simplicityC_tests.tar.xz (78kb, expands to
> 7.3mb)
>
> The files are named based on the result of the execution, e.g.
> successes vs various failures and roughly where they failed.
>
> Collections like this are useful for comparing other implementations,
> quickly testing new changes, or as a starting point for new
> coverage-directed fuzzing runs.
>

Thanks for this Greg.  I think this will be very valuable.


> While setting up testing I found that the non-elements harness (e.g.
> test.c:test_program) segfaults when elements operations are used and
> no transaction context is provided, which is kind of surprising. I
> would have expected that either a null tx pointer should always fail
> (api misuse) or the elements operations should become cleanly
> unavailable.  This might just be me misunderstanding the intended
> interface.  But I would have guessed that there would be different
> entry points with different required arguments for different kinds of
> contexts, and use of the wrong opcodes for your context would just
> make execution fail like an executed assertLR node.
>

The 'test_program' function from 'test.c', and indeed everything from
'test.c' isn't part of the API.
As you noted already, the API for the Elements application of Simplicity is
currently found in 'C/include/simplicity/elements.h' with
'elements_simplicity_execSimplicity'
as the primary function.
As one would expect, if you try to pass NULL for the transaction argument
to 'elements_simplicity_execSimplicity' the function will immediately
return false (API misuse).

The C library is designed with having application modularity in mind, so
that we can easily build other Simplicity applications, e.g. a Bitcoin
application of Simplicity supporting Bitcoin-style transactions.  However,
at the moment there is only one backend implemented, and there isn't really
yet support for multiple backends in the Make system.

For all backends, having the transaction context is essentially a
requirement, and 'test_program' passing a 'NULL' context is arguably an
abuse that only works for programs that do not use any primitives, which is
the case for all calls to 'test_program' in 'test.c'.  (The 'test_program'
function was developed before the Elements primitives were implemented.)

That said, your comment gave me the idea that I could make a "empty"
Simplicity application that has no primitives.  This would only really be
useful for development and testing, but it would be useful.
With such a backend, attempting to use any primitive would fail cleanly at
parsing time.


> I also found two distinct assertion failures which probably trace back
> to a single faulty elements operation. See issues #21 and #22.
>

Thanks for the report. A PR to fix the issue is under review at <
https://github.com/ElementsProject/simplicity/pull/23>.


> I was surprised by the rather large percentage of inputs that made it
> through type inference. I have no idea how efficient the serialization
> will be for actual programs people want to use, but it's at least
> efficient for something. :)
>
> All in all I was pretty impressed by how robust the implementation
> appears to be even at this early stage of development.
>
> I don't, however, think this fuzzing effort is particularly good at
> this point. I'm aware of the following shortcomings of my efforts:
>
> * The implementation really needs a static runtime bound for this
> testing. With that, I could set it reasonably low, testing would run
> much faster, and any test case which still took a long time would be
> worth investigating.
>

I was holding off on this, because there are many DoS vectors that need to
be addressed before the Simplicity library is suitable for production use.
However, thinking about the issue more, I realise that most of the DoS
vectors are related to third-party malleability, and only a few are direct
DoS vectors.
It sounds like it would be useful for me to prioritize getting those
primary DoS vectors addressed first, and then once those are addressed,
move on to third-party malleability issues.


> * The success/failure state of each of the vectors in the collection
> should be at least checked against another implementation, which I
> didn't do. (but someone could do for me, e.g. with the haskell
> tools?).
>

Yes, I will look into evaluating these vectors with the Haskell
implementation, and maybe also the Coq implementation for those test
vectors that represent well-typed Simplicity programs.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/simplicity/attachments/20191116/1c5e57bd/attachment.htm>