GoSmith, a random Go program generator

[Dmitry Vyukov]

Hi,

In case you were not following
https://code.google.com/p/go/issues/detail?id=7985.
I've wrote a generator of random, but correct, Go programs and tested
various Go compilers on them.

In 10 days it has found 50+ bugs in all of
6g/8g/5g/race/gofmt/gccgo/llgo/runtime/spec:
http://gosmith.googlecode.com

I am wrapping up my work on it for now. Mostly because there are too
many known unfixed bugs, and significant portion of runs fail on known
bugs.

As far as I understand, the bugs won't be "invalidated" by Go 1.4
compiler overhaul, as it won't be a rewrite from scratch. On the
contrary, the ability to generate millions of test cases will be
especially important in front of significant compiler changes.

The tool still does not cover some significant parts of the language:
- interfaces, types satisfying interfaces and type assertions
- methods
- constants
and lots of minors things here and there.
The code will need some significant refactoring if/when the work is
resumed (I was figuring out how it must look like along the way).

If anybody wants to have some fun, hunt bugs and learn the spec along
the way, contributions are welcome!

[andrewc...@gmail.com]

This is cool work, did you also work on a reducer like C reduce (from the same people)?
http://embed.cs.utah.edu/creduce/

I'm sure you are aware of it considering you used CSmith. In case other people are unaware of the companion tool:
"C-Reduce is a tool that takes a large C or C++ program that has a property of interest (such as triggering a compiler bug) and automatically produces a much smaller C/C++ program that has the same property. It is intended for use by people who discover and report bugs in compilers and other tools that process C/C++ code."

A more generic version of a test case reduction tool: http://delta.tigris.org/.

[Dmitry Vyukov]

On Wed, May 28, 2014 at 4:33 AM, <andrewc...@gmail.com> wrote:
> This is cool work, did you also work on a reducer like C reduce (from the
> same people)?
> http://embed.cs.utah.edu/creduce/
>
> I'm sure you are aware of it considering you used CSmith. In case other
> people are unaware of the companion tool:
> "C-Reduce is a tool that takes a large C or C++ program that has a property
> of interest (such as triggering a compiler bug) and automatically produces a
> much smaller C/C++ program that has the same property. It is intended for
> use by people who discover and report bugs in compilers and other tools that
> process C/C++ code."
>
> A more generic version of a test case reduction tool:
> http://delta.tigris.org/.

I am aware of reducers, but I did not work on them.
Delta must be able to reduce Go programs on line basis.

[andrewc...@gmail.com]

Delta or singledelta works on line by line basis. Multidelta was an extension which flattens braced expressions such as if statements and functions onto single lines so that single line elimination has a chance to remove them. Singledelta will definitely work with go code.

single delta is good enough when combined with a human step between reductions where obvious reductions are applied. I'm going to play with this tool and see if I can come up with anything beneficial.

[Dmitry Vyukov]

You can use existing gosmith bugs without minimized examples as input
for minimization. Look for bugs with attachments (instead of small
embed reproducers).

[andrewc...@gmail.com]

Having played with the generator and looked though the code, I have a few comments.

CSmith takes a slightly different approach in that it generates random operations on global and local values and prints a hash of all the globals at the end of execution.
CSmiths approach makes it slightly easier to test differences between two compiler implementations or two compiler versions, your approach is currently more useful for finding compiler crashes rather than finding differences in compiler behaviour.

When the 1.4 compiler translation occurs adopting the csmith approach may allow some comparative testing.

Multiple goroutines do complicate this issue compared to csmith as execution is not deterministic like it is in csmith. Comparing output between compilers probably also requires disabling go routines and channels with a flag.

[Dmitry Vyukov]

On Wed, May 28, 2014 at 3:16 PM, <andrewc...@gmail.com> wrote:
> Having played with the generator and looked though the code, I have a few
> comments.
>
> CSmith takes a slightly different approach in that it generates random
> operations on global and local values and prints a hash of all the globals
> at the end of execution.

They do complex global analysis and sacrifice expressiveness to
achieve this goal.

> CSmiths approach makes it slightly easier to test differences between two
> compiler implementations or two compiler versions, your approach is
> currently more useful for finding compiler crashes rather than finding
> differences in compiler behaviour.

Right.

> When the 1.4 compiler translation occurs adopting the csmith approach may
> allow some comparative testing.
>
> Multiple goroutines do complicate this issue compared to csmith as execution
> is not deterministic like it is in csmith. Comparing output between
> compilers probably also requires disabling go routines and channels with a
> flag.

But goroutines and channels is one of the most interesting pieces of
Go wrt testing runtime behavior...

[andrewc...@gmail.com]

I agree with all your points.

CSmith is complex and replicating it's analysis totally would be a huge task for small gains compared to your approach which gives good results regardless.
I also agree Goroutines, scheduling and GC are extremely important features that CSmith doesn't need to care about at all. Most of the bugs in the Go are probably found in
code that is hard to test, which is probably going to be related to threading and GC edge cases and not in simple code generation.
Definitely don't take my comments before as criticism, because it's not.

I can imagine people researching ways to do deep random testing of multi threaded runtimes for years and years.