grammar-based fuzzing

[Ryan Kramer]

Does Racket have any grammar-based fuzzing utilities? I'm probably going to play around with this either way, but if there is an existing solution I'll quit after I've had my fun. If, however, people think Racket could use something like this I may attempt to make it into a usable package.

I'm thinking specifically about generating inputs for Quickcheck, but such a fuzzer might have other uses.

For example, given this grammar:

(struct tree (left right) #:transparent)

(define-grammar tree-grammar
  [Leaf (:choose-integer -9999 9999)]
  [Subtree #'(tree Node Node)]
  [Node #:max-nesting 10
        (:weighted-choice
         [1 Leaf]
         [5 Subtree])])

Then (tree-grammar 'Subtree) might generate #'(tree 1 (tree 2 3)) as one of many possibilities.

An important feature that I haven't seen yet is tracking/scoping identifiers. There are times when we want to generate any arbitrary identifier, and other times when we want to use an existing identifier that we know is in scope. For example, if we were fuzzing `let` we might have

(define-grammar let-grammar
  [Root #'(let ([LetId LetVal]
                ...)
            LetBody)]
  [LetId (:choose-identifier)]
  ; TODO ...
  )

And somehow we want to say that LetBody can and should use the enclosing LetIds, but I don't immediately see a great way to communicate that. It might be possible to have something like (:choose-bound LetId) which would generate a LetId that is known to be in scope.

[Jay McCarthy]

`redex-check` is what you want. If it isn't exactly what you need,
then `data/enumerate` will help you build what you need very easily.

--
Jay McCarthy
Associate Professor @ CS @ UMass Lowell
http://jeapostrophe.github.io
Vincit qui se vincit.

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/832ed76d-33f6-4f3f-b80f-da891613b6a3%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Eric Eide]

Ryan Kramer <default...@gmail.com> writes:

> Does Racket have any grammar-based fuzzing utilities?

You might be interested in Xsmith. Version 1.0 will be released imminently,
like within the next week. I'll send another email when it's released.

Stay tuned!

--
-------------------------------------------------------------------------------
Eric Eide <ee...@cs.utah.edu> . University of Utah School of Computing
http://www.cs.utah.edu/~eeide/ . +1 (801) 585-5512 voice, +1 (801) 581-5843 FAX

[Robby Findler]

In addition to the other suggestions, if you can express the thing you
want to generate as a contract, the contract library will generate
random instances of it. But it doesn't have the tuning of weights
you're looking for.

Robby

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/m1a7eucuqa.fsf%40gris.uconnect.utah.edu.

[zeRusski]

cool wasn't aware of Xsmith! Surprised to find RACR backing it - I looked at its source a while back for some attribute grammar magic - ended up not doing anything though - was it lack of docs - can't recall. IIRC it has some true scheme magic in there.

Academics often suck at marketing ;) For those who, like me, were interested but failed to navigate to relevant bits:

- Xsmith docs: https://docs.racket-lang.org/xsmith/index.html

- Xsmith src: https://gitlab.flux.utah.edu/xsmith/xsmith

- RACR docs: https://github.com/christoff-buerger/racr/blob/master/racr/documentation/contents.md

- RACR src: https://github.com/christoff-buerger/racr

On Thursday, 6 June 2019 21:41:21 UTC+1, Eric Eide wrote:

[Ryan Kramer]

Thanks everyone for the good suggestions. Xsmith looks particularly appealing, looking forward to 1.0!

[Eric Eide]

Eric Eide <ee...@cs.utah.edu> writes:

> You might be interested in Xsmith. Version 1.0 will be released imminently,
> like within the next week. I'll send another email when it's released.

To follow up in this thread, Xsmith version 1.0.0 is now available. You can
find it in the Racket package catalog:
https://pkgs.racket-lang.org/package/xsmith

(The online docs haven't updated yet. Soon, I expect.)

Happy fuzzing!

Eric.