Random test generator for differential fuzzing

[adri326]

I've been inspired by the article on ZenBleed to do try out differential fuzzing, and from seeing instances of UB in scryer-prolog, I figured it would be a fun project to try to automatically find edge cases or UB through fuzzing.

Right now all I have is a random predicate generator, which produces simple (but nonsensical, since they're random) predicates:

% pred_0(
%     list(number)
%     number
%     number
% )
pred_0([A, 8], 14, A).

pred_0([14, 23, 10, 3], 21, 2).

pred_0([_A, 16 | _B], C, _D) :- C = 7.

pred_0([26 | _A], B, C) :- C = B.

% pred_1(
%     number
%     decreasing(list(number))
%     number
% )
pred_1(18, [19 | A], B) :- pred_1(B, A, _C).

pred_1(17, [A | B], 10) :- (
        pred_0([A | B], 26, 20),
        pred_1(11, B, A)
    ).

pred_1(_A, [], B) :- pred_0([B], _C, _D).

pred_1(25, [9 | _A], _B).

% pred_2(
%     number
%     number
%     list(number)
%     number
% )
pred_2(A, B, [14, B], 22) :- (
        pred_1(A, [], A),
        pred_0([2 | _E], _F, B),
        pred_0([21, _C, B], _D, A)
    ).

pred_2(A, _B, _C, 17) :- A = 26.

It works by randomly creating a new predicate, or a new case for an existing predicate, or by modifying the goals within a case.

One tricky area so far is termination; I'm enforcing a strictly decreasing term, but that of course limits the number of predicates that my code is able to generate. I hope to add more well orders for termination, so that I can cover more ground.

It's also quite easy to make predicates whose complexity blows up:

pred([]).
% Oops, O(2^n) complexity
pred([X | Rest]) :- pred(Rest), pred(Rest).

To solve that I made it so that the generator would let alone predicates which are complex enough, and would not add recursive calls to predicate cases that already have one.
It's, again, going to shrink the coverage that I can provide, but I need to be able to run the prolog code if I want to do some differential fuzzing :/

There's still a long way until this thing can produce prolog programs that properly stress the engine, but I'd love to hear your thoughts on this idea :)

[hurufu]

Nice, I also think that we should support something like https://hackage.haskell.org/package/QuickCheck in Scryer. The idea is to have a little bit more control over what kinds of predicates ought to be generated.

[triska]

Very interesting, thank you a lot for working on this!

Several of these test cases may be easier to describe in Prolog itself, is the Scryer library version usable for this? There are example usages of Scryer Prolog from within Rust programs in the repository: https://github.com/mthom/scryer-prolog/tree/master/src/machine/lib_machine

[adri326]

Yeah I think that would be the better way forward, it's becoming unwieldy to ensure that my rust code fulfills the requirements for termination, for instance. It would also be a shame not to use prolog to generate test cases for prolog :p