4 ms·

Can you give some more details about that? What kind of invariants do you test, and how?

• pfdietz 5y ago
  I have applied it to testing Common Lisp implementations, but there has been much work on applying it to other languages (most famously C and Javascript.) I applied the following techniques: (1) Generate random valid well defined programs and see (a) if they crash the compiler, (b) cause different CL implementations to produce different outputs, (c) when modified (by addition of randomly generated optimization directives or valid type declarations) they still produce the same output. This is differential testing, which was used by McKeeman at DEC in the 1990s to test C compilers, and later improved (again, on C compilers) by Yang, Chan, Eide, and Regehr at U. of Utah (csmith, creduce). Since a running lisp image can generate and compile functions internally (this IS lisp, after all), the testing loop can be very fast. Since 2003 I have run this on and off for many billions of iterations on desktop and laptop machines on various CL implementations, now mainly on SBCL. Most of the test input reduction is handled automatically, which is a big help. (2) Generate random possibly invalid code by mutating or recombining snippets drawn from a large corpus of code, to see if it crashes the compiler (in CL implementations where the compiler is promised to never respond to bad code by signaling an error.) This was also the approach jsfunfuzz took on Javascript. (3) Extensive fuzzing of calls to standard functions in CL, using random generation of input values and random generation of valid type declarations, with the invariant being that the same values should be computed (and the compiler not fail.) This is a specialization of (1), but was sufficiently different that the bugs it found were not the same. Examples of tests produced by (1) and (3) over an early period when this was being developed. Each caused a failure in some CL implementation: https://github.com/pfdietz/ansi-test/blob/master/misc/misc.lsp https://github.com/pfdietz/ansi-test/blob/master/misc/misc.l... This was one of my favorite bugs found: https://bugs.launchpad.net/sbcl/+bug/1730699 https://bugs.launchpad.net/sbcl/+bug/1730699 The experience with this sort of testing of compilers (in any language) is that if the compiler (free or commercial) has never been subjected to it, it will immediately find bugs in the compiler.
  • DylanSp 5y ago
    Out of curiosity, how do you go about generating "random valid well defined programs"? I thought about doing something like this for testing my own toy language, but wasn't sure how to go about generating random test cases.
    • pfdietz 5y ago
      Basically by a top down approach. For example, to generate a random integer valued form, pick one of N fixed rules and invoke it. A rule for a form of size S might be "generate some value k in [1,S-1] and then partitions S-1 into k integers, generate an integer valued form for each, then produce the form that is their sum." At the leaf nodes, generate constants or variables. Keep track of the variables that are in scope as you do this (and their types.) This is a pretty standard approach used in compiler testing. In languages like C you have problems ensuring the program doesn't cause undefined behavior, but Common Lisp is much nicer in that respect -- for example, evaluation order of arguments to functions is defined, and you don't have to worry about integer operations overflowing. All this has made me appreciate language specifications that really nail down what programs are supposed to do. The forms generated are constrained if one wants them to be easily reducible while preserving validity. Hypothesis has a nice solution to that problem, which I didn't use, as this was done a decade and a half earlier.
      • DylanSp 5y ago
        Interesting, I'll have to take a stab at trying something like that. Thanks for the reply!