syz-verifier: use only system calls supported by all kernels and with no transitive dependencies when building the `prog.ChoiceTable` (#2653)

* pkg/rpctype: add types for CheckUnsupported RPC

* syz-runner: added functionality for detecting unsupported system calls

* syz-verifier: added UpdateUnsupported RPC method

This will receive the unsupported system calls from each  kernel,
compute the intersections of system calls that are enabled by all
kernels and  build the choice table only using those.

* syz-verifier, syz-runner: report only when specific calls are enabled

2 files changed, 295 insertions, 31 deletions

diff --git a/syz-verifier/main.go b/syz-verifier/main.go
index d82fe0a88..7a9bb0f2b 100755
--- a/syz-verifier/main.go
+++ b/syz-verifier/main.go
@@ -5,6 +5,7 @@ package main
 import (
 	"flag"
 	"fmt"
+	"io"
 	"log"
 	"math/rand"
 	"net"
@@ -40,26 +41,31 @@ type Verifier struct {
 	// - <workdir>/corpus.db: corpus with interesting programs
 	// - <workdir>/<OS-Arch>/instance-x: per VM instance temporary files
 	// grouped by OS/Arch
-	workdir     string
-	crashdir    string
-	resultsdir  string
-	target      *prog.Target
-	runnerBin   string
-	executorBin string
-	choiceTable *prog.ChoiceTable
-	rnd         *rand.Rand
-	progIdx     int
-	addr        string
+	workdir       string
+	crashdir      string
+	resultsdir    string
+	target        *prog.Target
+	runnerBin     string
+	executorBin   string
+	choiceTable   *prog.ChoiceTable
+	rnd           *rand.Rand
+	progIdx       int
+	addr          string
+	calls         map[*prog.Syscall]bool
+	reasons       map[*prog.Syscall]string
+	reportReasons bool
 }
 
 // RPCServer is a wrapper around the rpc.Server. It communicates with  Runners,
 // generates programs and sends complete Results for verification.
 type RPCServer struct {
-	vrf   *Verifier
-	port  int
-	mu    sync.Mutex
-	pools map[int]*poolInfo
-	progs map[int]*progInfo
+	vrf        *Verifier
+	port       int
+	mu         sync.Mutex
+	cond       *sync.Cond
+	pools      map[int]*poolInfo
+	progs      map[int]*progInfo
+	notChecked int
 }
 
 // poolInfo contains kernel-specific information for spawning virtual machines
@@ -74,8 +80,11 @@ type poolInfo struct {
 	//  There is one Runner executing per VM instance.
 	vmRunners map[int][]*progInfo
 	// progs stores the programs that haven't been sent to this kernel yet but
-	// have been sent to at least one kernel.
+	// have been sent to at least one other kernel.
 	progs []*progInfo
+	// checked is set to true when the set of system calls not supported on the
+	// kernel is known.
+	checked bool
 }
 
 type progInfo struct {
@@ -163,21 +172,24 @@ func main() {
 	}
 
 	calls := make(map[*prog.Syscall]bool)
+
 	for _, id := range cfg.Syscalls {
 		calls[target.Syscalls[id]] = true
 	}
 
 	vrf := &Verifier{
-		workdir:     workdir,
-		crashdir:    crashdir,
-		resultsdir:  resultsdir,
-		pools:       pools,
-		target:      target,
-		choiceTable: target.BuildChoiceTable(nil, calls),
-		rnd:         rand.New(rand.NewSource(time.Now().UnixNano() + 1e12)),
-		runnerBin:   runnerBin,
-		executorBin: execBin,
-		addr:        addr,
+		workdir:       workdir,
+		crashdir:      crashdir,
+		resultsdir:    resultsdir,
+		pools:         pools,
+		target:        target,
+		calls:         calls,
+		reasons:       make(map[*prog.Syscall]string),
+		rnd:           rand.New(rand.NewSource(time.Now().UnixNano() + 1e12)),
+		runnerBin:     runnerBin,
+		executorBin:   execBin,
+		addr:          addr,
+		reportReasons: len(cfg.EnabledSyscalls) != 0 || len(cfg.DisabledSyscalls) != 0,
 	}
 
 	srv, err := startRPCServer(vrf)
@@ -224,10 +236,12 @@ func main() {
 
 func startRPCServer(vrf *Verifier) (*RPCServer, error) {
 	srv := &RPCServer{
-		vrf:   vrf,
-		pools: vrf.pools,
-		progs: make(map[int]*progInfo),
+		vrf:        vrf,
+		pools:      vrf.pools,
+		progs:      make(map[int]*progInfo),
+		notChecked: len(vrf.pools),
 	}
+	srv.cond = sync.NewCond(&srv.mu)
 
 	s, err := rpctype.NewRPCServer(vrf.addr, "Verifier", srv)
 	if err != nil {
@@ -242,14 +256,78 @@ func startRPCServer(vrf *Verifier) (*RPCServer, error) {
 }
 
 // Connect notifies the RPCServer that a new Runner was started.
-func (srv *RPCServer) Connect(a *rpctype.RunnerConnectArgs, r *int) error {
+func (srv *RPCServer) Connect(a *rpctype.RunnerConnectArgs, r *rpctype.RunnerConnectRes) error {
 	srv.mu.Lock()
 	defer srv.mu.Unlock()
 	pool, vm := a.Pool, a.VM
 	srv.pools[pool].vmRunners[vm] = nil
+	r.CheckUnsupportedCalls = !srv.pools[pool].checked
 	return nil
 }
 
+// UpdateUnsupported communicates to the server the list of system calls not
+// supported by the kernel corresponding to this pool and updates the list of
+// enabled system calls. This function is called once for each kernel.
+// When all kernels have reported the list of unsupported system calls, the
+// choice table will be created using only the system calls supported by all
+// kernels.
+func (srv *RPCServer) UpdateUnsupported(a *rpctype.UpdateUnsupportedArgs, r *int) error {
+	srv.mu.Lock()
+	defer srv.mu.Unlock()
+	if srv.pools[a.Pool].checked {
+		return nil
+	}
+	srv.pools[a.Pool].checked = true
+	vrf := srv.vrf
+
+	for _, unsupported := range a.UnsupportedCalls {
+		if c := vrf.target.Syscalls[unsupported.ID]; vrf.calls[c] {
+			vrf.reasons[c] = unsupported.Reason
+		}
+	}
+
+	srv.notChecked--
+	if srv.notChecked == 0 {
+		vrf.finalizeCallSet(os.Stdout)
+		vrf.choiceTable = vrf.target.BuildChoiceTable(nil, vrf.calls)
+		srv.cond.Signal()
+	}
+	return nil
+}
+
+// finalizeCallSet removes the system calls that are not supported from the set
+// of enabled system calls and reports the reason to the io.Writer (either
+// because the call is not supported by one of the kernels or because the call
+// is missing some transitive dependencies). The resulting set of system calls
+// will be used to build the prog.ChoiceTable.
+func (vrf *Verifier) finalizeCallSet(w io.Writer) {
+	for c := range vrf.reasons {
+		delete(vrf.calls, c)
+	}
+
+	// Find and report to the user all the system calls that need to be
+	// disabled due to missing dependencies.
+	_, disabled := vrf.target.TransitivelyEnabledCalls(vrf.calls)
+	for c, reason := range disabled {
+		vrf.reasons[c] = reason
+		delete(vrf.calls, c)
+	}
+
+	if len(vrf.calls) == 0 {
+		log.Fatal("All enabled system calls are missing dependencies or not" +
+			" supported by some kernels, exiting syz-verifier.")
+	}
+
+	if !vrf.reportReasons {
+		return
+	}
+
+	fmt.Fprintln(w, "The following calls have been disabled:")
+	for c, reason := range vrf.reasons {
+		fmt.Fprintf(w, "\t%v: %v\n", c.Name, reason)
+	}
+}
+
 // NextExchange is called when a Runner requests a new program to execute and,
 // potentially, wants to send a new Result to the RPCServer.
 func (srv *RPCServer) NextExchange(a *rpctype.NextExchangeArgs, r *rpctype.NextExchangeRes) error {
@@ -284,6 +362,11 @@ func (srv *RPCServer) NextExchange(a *rpctype.NextExchangeArgs, r *rpctype.NextE
 		}
 	}
 
+	if srv.notChecked > 0 {
+		// Runner is blocked until the choice table is created.
+		srv.cond.Wait()
+	}
+
 	prog, pi := srv.newProgram(a.Pool, a.VM)
 	r.RPCProg = rpctype.RPCProg{Prog: prog, ProgIdx: pi}
 	return nil
diff --git a/syz-verifier/main_test.go b/syz-verifier/main_test.go
index ca2c86ebe..a7c9ebe03 100644
--- a/syz-verifier/main_test.go
+++ b/syz-verifier/main_test.go
@@ -3,9 +3,11 @@
 package main
 
 import (
+	"bytes"
 	"math/rand"
 	"os"
 	"path/filepath"
+	"strings"
 	"testing"
 	"time"
 
@@ -188,9 +190,13 @@ func TestConnect(t *testing.T) {
 		Pool: 1,
 		VM:   1,
 	}
-	if err := srv.Connect(a, nil); err != nil {
+	r := &rpctype.RunnerConnectRes{}
+	if err := srv.Connect(a, r); err != nil {
 		t.Fatalf("srv.Connect failed: %v", err)
 	}
+	if diff := cmp.Diff(&rpctype.RunnerConnectRes{CheckUnsupportedCalls: true}, r); diff != "" {
+		t.Errorf("Connect result mismatch (-want +got):\n%s", diff)
+	}
 	want, got := map[int][]*progInfo{
 		0: {{idx: 1, left: map[int]bool{1: true, 2: true}}},
 		1: nil,
@@ -200,6 +206,181 @@ func TestConnect(t *testing.T) {
 	}
 }
 
+func TestFinalizeCallSet(t *testing.T) {
+	target, err := prog.GetTarget("test", "64")
+	if err != nil {
+		t.Fatalf("failed to initialise test target: %v", err)
+	}
+
+	vrf := Verifier{
+		target: target,
+		reasons: map[*prog.Syscall]string{
+			target.SyscallMap["test$res0"]:  "foo",
+			target.SyscallMap["minimize$0"]: "bar",
+		},
+		calls: map[*prog.Syscall]bool{
+			target.SyscallMap["minimize$0"]: true,
+			target.SyscallMap["test$res0"]:  true,
+			target.SyscallMap["disabled1"]:  true,
+		},
+		reportReasons: true,
+	}
+
+	out := bytes.Buffer{}
+	vrf.finalizeCallSet(&out)
+	wantLines := []string{
+		"The following calls have been disabled:\n",
+		"\ttest$res0: foo\n",
+		"\tminimize$0: bar\n",
+	}
+	output := out.String()
+	for _, line := range wantLines {
+		if !strings.Contains(output, line) {
+			t.Errorf("finalizeCallSet: %q missing in reported output", line)
+		}
+	}
+
+	wantCalls, gotCalls := map[*prog.Syscall]bool{
+		target.SyscallMap["disabled1"]: true,
+	}, vrf.calls
+	if diff := cmp.Diff(wantCalls, gotCalls); diff != "" {
+		t.Errorf("srv.calls mismatch (-want +got):\n%s", diff)
+	}
+}
+
+func TestUpdateUnsupported(t *testing.T) {
+	target, err := prog.GetTarget("test", "64")
+	if err != nil {
+		t.Fatalf("failed to initialise test target: %v", err)
+	}
+
+	tests := []struct {
+		name           string
+		vrfPools       map[int]*poolInfo
+		wantPools      map[int]*poolInfo
+		wantCalls      map[*prog.Syscall]bool
+		wantNotChecked int
+		nilCT          bool
+	}{
+		{
+			name:           "choice table not generated",
+			vrfPools:       map[int]*poolInfo{0: {}, 1: {}},
+			wantPools:      map[int]*poolInfo{0: {checked: true}, 1: {}},
+			wantNotChecked: 1,
+			wantCalls: map[*prog.Syscall]bool{
+				target.SyscallMap["minimize$0"]:     true,
+				target.SyscallMap["breaks_returns"]: true,
+				target.SyscallMap["test$res0"]:      true,
+				target.SyscallMap["test$union0"]:    true,
+			},
+			nilCT: true,
+		},
+		{
+			name:           "choice table generated",
+			vrfPools:       map[int]*poolInfo{0: {}},
+			wantPools:      map[int]*poolInfo{0: {checked: true}},
+			wantNotChecked: 0,
+			wantCalls: map[*prog.Syscall]bool{
+				target.SyscallMap["minimize$0"]:     true,
+				target.SyscallMap["breaks_returns"]: true,
+			},
+			nilCT: false,
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			vrf := Verifier{
+				target:        target,
+				pools:         test.vrfPools,
+				reasons:       make(map[*prog.Syscall]string),
+				reportReasons: true,
+				calls: map[*prog.Syscall]bool{
+					target.SyscallMap["minimize$0"]:     true,
+					target.SyscallMap["breaks_returns"]: true,
+					target.SyscallMap["test$res0"]:      true,
+					target.SyscallMap["test$union0"]:    true,
+				},
+			}
+			srv, err := startRPCServer(&vrf)
+			if err != nil {
+				t.Fatalf("failed to initialise RPC server: %v", err)
+			}
+
+			a := &rpctype.UpdateUnsupportedArgs{
+				Pool: 0,
+				UnsupportedCalls: []rpctype.SyscallReason{
+					{ID: 137, Reason: "foo"},
+					{ID: 2, Reason: "bar"},
+					{ID: 151, Reason: "tar"},
+				}}
+			if err := srv.UpdateUnsupported(a, nil); err != nil {
+				t.Fatalf("srv.UpdateUnsupported failed: %v", err)
+			}
+
+			if diff := cmp.Diff(test.wantPools, srv.pools, cmp.AllowUnexported(poolInfo{})); diff != "" {
+				t.Errorf("srv.pools mismatch (-want +got):\n%s", diff)
+			}
+
+			wantReasons := map[*prog.Syscall]string{
+				target.SyscallMap["test$res0"]:   "foo",
+				target.SyscallMap["test$union0"]: "tar",
+			}
+			if diff := cmp.Diff(wantReasons, vrf.reasons); diff != "" {
+				t.Errorf("srv.reasons mismatch (-want +got):\n%s", diff)
+			}
+
+			if diff := cmp.Diff(test.wantCalls, vrf.calls); diff != "" {
+				t.Errorf("srv.calls mismatch (-want +got):\n%s", diff)
+			}
+
+			if want, got := test.wantNotChecked, srv.notChecked; want != got {
+				t.Errorf("srv.notChecked: got %d want %d", got, want)
+			}
+
+			if want, got := test.nilCT, vrf.choiceTable == nil; want != got {
+				t.Errorf("vrf.choiceTable == nil: want nil, got: %v", srv.vrf.choiceTable)
+			}
+		})
+	}
+}
+
+func TestUpdateUnsupportedNotCalledTwice(t *testing.T) {
+	vrf := Verifier{
+		pools: map[int]*poolInfo{
+			0: {vmRunners: map[int][]*progInfo{0: nil, 1: nil}, checked: false},
+			1: {vmRunners: map[int][]*progInfo{}, checked: false},
+		},
+	}
+	srv, err := startRPCServer(&vrf)
+	if err != nil {
+		t.Fatalf("failed to initialise RPC server: %v", err)
+	}
+	a := &rpctype.UpdateUnsupportedArgs{Pool: 0}
+
+	if err := srv.UpdateUnsupported(a, nil); err != nil {
+		t.Fatalf("srv.UpdateUnsupported failed: %v", err)
+	}
+	if want, got := 1, srv.notChecked; want != got {
+		t.Errorf("srv.notChecked: got %d want %d", got, want)
+	}
+
+	if err := srv.UpdateUnsupported(a, nil); err != nil {
+		t.Fatalf("srv.UpdateUnsupported failed: %v", err)
+	}
+	if want, got := 1, srv.notChecked; want != got {
+		t.Fatalf("srv.UpdateUnsupported called twice")
+	}
+
+	wantPools := map[int]*poolInfo{
+		0: {vmRunners: map[int][]*progInfo{0: nil, 1: nil}, checked: true},
+		1: {vmRunners: map[int][]*progInfo{}, checked: false},
+	}
+	if diff := cmp.Diff(wantPools, srv.pools, cmp.AllowUnexported(poolInfo{}, progInfo{})); diff != "" {
+		t.Errorf("srv.pools mismatch (-want +got):\n%s", diff)
+	}
+}
+
 func TestProcessResults(t *testing.T) {
 	tests := []struct {
 		name      string