tools: add a syz-diff tool

This is the prototype version of the patch series fuzzing functionality
based on the syzkaller fuzzing engine.

The tool takes two syzkaller configs -- one for the base kernel, one for
the patched kernel. Optionally the patch itself can be also provided.

syz-diff will consider a bug patched-only if:
1) It happened while fuzzing the patched kernel.
2) It was never observed on the base kernel.
3) The tool found a repro on the patched kernel.
4) The repro did not crash the base kernel.

1 files changed, 68 insertions, 0 deletions

diff --git a/pkg/fuzzer/queue/queue.go b/pkg/fuzzer/queue/queue.go
index 0a56c76d3..1d25cbc8a 100644
--- a/pkg/fuzzer/queue/queue.go
+++ b/pkg/fuzzer/queue/queue.go
@@ -8,6 +8,7 @@ import (
 	"context"
 	"encoding/gob"
 	"fmt"
+	"math/rand"
 	"sync"
 	"sync/atomic"
 
@@ -459,3 +460,70 @@ func (do *defaultOpts) Next() *Request {
 	req.ExecOpts.SandboxArg = do.opts.SandboxArg
 	return req
 }
+
+// RandomQueue holds up to |size| elements.
+// Next() evicts a random one.
+// On Submit(), if the queue is full, a random element is replaced.
+type RandomQueue struct {
+	mu      sync.Mutex
+	queue   []*Request
+	maxSize int
+	rnd     *rand.Rand
+}
+
+func NewRandomQueue(size int, rnd *rand.Rand) *RandomQueue {
+	return &RandomQueue{
+		maxSize: size,
+		rnd:     rnd,
+	}
+}
+
+func (rq *RandomQueue) Next() *Request {
+	rq.mu.Lock()
+	defer rq.mu.Unlock()
+	if len(rq.queue) == 0 {
+		return nil
+	}
+	pos := rq.rnd.Intn(len(rq.queue))
+	item := rq.queue[pos]
+
+	last := len(rq.queue) - 1
+	rq.queue[pos] = rq.queue[last]
+	rq.queue[last] = nil
+	rq.queue = rq.queue[0 : len(rq.queue)-1]
+	return item
+}
+
+func (rq *RandomQueue) Submit(req *Request) {
+	rq.mu.Lock()
+	defer rq.mu.Unlock()
+	if len(rq.queue) < rq.maxSize {
+		rq.queue = append(rq.queue, req)
+	} else {
+		pos := rq.rnd.Intn(rq.maxSize + 1)
+		if pos < len(rq.queue) {
+			rq.queue[pos].Done(&Result{Status: ExecFailure})
+			rq.queue[pos] = req
+		}
+	}
+}
+
+type tee struct {
+	queue Executor
+	src   Source
+}
+
+func Tee(src Source, queue Executor) Source {
+	return &tee{src: src, queue: queue}
+}
+
+func (t *tee) Next() *Request {
+	req := t.src.Next()
+	if req == nil {
+		return nil
+	}
+	t.queue.Submit(&Request{
+		Prog: req.Prog.Clone(),
+	})
+	return req
+}