pkg/bisect: Implement config bisection

Implement Linux kernel configuration bisection. Use bisected minimalistic
configuration in commit bisection. Utilizes config_bisect.pl script from Linux
kernel tree in bisection.

Modify syz-bisect to read in kernel.baseline_config. This is used as a "good"
configuration when bisection is run.

6 files changed, 454 insertions, 1 deletions

diff --git a/pkg/vcs/linux.go b/pkg/vcs/linux.go
index 9fc96fef4..81026f805 100644
--- a/pkg/vcs/linux.go
+++ b/pkg/vcs/linux.go
@@ -5,8 +5,12 @@ package vcs
 
 import (
 	"bytes"
+	"fmt"
 	"io"
+	"io/ioutil"
 	"net/mail"
+	"os"
+	"os/exec"
 	"path/filepath"
 	"sort"
 	"strconv"
@@ -15,6 +19,7 @@ import (
 
 	"github.com/google/syzkaller/pkg/email"
 	"github.com/google/syzkaller/pkg/osutil"
+	"github.com/google/syzkaller/prog"
 )
 
 type linux struct {
@@ -22,6 +27,7 @@ type linux struct {
 }
 
 var _ Bisecter = new(linux)
+var _ ConfigMinimizer = new(linux)
 
 func newLinux(dir string) *linux {
 	ignoreCC := map[string]bool{
@@ -240,3 +246,253 @@ func (ctx *linux) getMaintainers(hash string, blame bool) []string {
 	}
 	return list
 }
+
+var configBisectTag string = "# Minimized by syzkaller"
+
+func (ctx *linux) Minimize(original, baseline []byte, trace io.Writer,
+	pred func(test []byte) (BisectResult, error)) ([]byte, error) {
+	if strings.HasPrefix(string(original), configBisectTag) {
+		fmt.Fprintf(trace, "# configuration already minimized\n")
+		return original, nil
+	}
+	bisectDir := "config_bisect"
+
+	suffix := ""
+	i := 0
+	for {
+		bisectDir = "config_bisect" + suffix
+		if !osutil.IsExist(bisectDir) {
+			fmt.Fprintf(trace, "# using %v as config bisect directory\n", bisectDir)
+			break
+		}
+		suffix = strconv.Itoa(i)
+		i++
+	}
+	kernelConfig := filepath.Join(bisectDir, "kernel.config")
+	kernelBaselineConfig := filepath.Join(bisectDir, "kernel.baseline_config")
+
+	err := os.MkdirAll(bisectDir, 0755)
+	if err != nil {
+		return nil, fmt.Errorf("failed to create dir for config bisect: %v", err)
+	}
+
+	err = ctx.prepareConfigBisectEnv(kernelConfig, kernelBaselineConfig, original, baseline)
+	if err != nil {
+		return nil, err
+	}
+
+	cmd := exec.Command(ctx.git.dir+"/tools/testing/ktest/config-bisect.pl",
+		"-l", ctx.git.dir, "-r", "-b", ctx.git.dir, kernelBaselineConfig, kernelConfig)
+
+	configBisectName := filepath.Join(bisectDir, "config_bisect.log")
+	configBisectLog, err := os.Create(configBisectName)
+	if err != nil {
+		return nil, fmt.Errorf("failed to create bisect log file: %v", err)
+	}
+	defer configBisectLog.Close()
+	cmd.Stdout = configBisectLog
+	cmd.Stderr = configBisectLog
+
+	fmt.Fprintf(trace, "# start config bisection\n")
+	if err := cmd.Run(); err != nil {
+		return nil, fmt.Errorf("config bisect failed: %v", err)
+	}
+
+	verdict := ""
+	var configOptions []string
+	for {
+		config, err := ioutil.ReadFile(filepath.Join(ctx.git.dir,
+			".config"))
+		if err != nil {
+			return nil, fmt.Errorf("failed to read .config: %v", err)
+		}
+
+		testRes, err := pred(config)
+		if err != nil {
+			break
+		} else if testRes == BisectBad {
+			verdict = "bad"
+		} else if testRes == BisectGood {
+			verdict = "good"
+		} else {
+			return nil, fmt.Errorf("unable to test, stopping config bisection: %v", err)
+		}
+
+		cmd = exec.Command(ctx.git.dir+"/tools/testing/ktest/config-bisect.pl",
+			"-l", ctx.git.dir, "-b", ctx.git.dir,
+			kernelBaselineConfig, kernelConfig, verdict)
+
+		cmd.Stdout = configBisectLog
+		cmd.Stderr = configBisectLog
+
+		if err := cmd.Run(); err != nil {
+			if fmt.Sprint(err) != "exit status 2" {
+				return nil, fmt.Errorf("config bisect failed: %v", err)
+			}
+
+			fmt.Fprintf(trace, "# config_bisect.pl finished or failed: %v\n", err)
+			logForParsing, err := ioutil.ReadFile(configBisectName)
+			if err != nil {
+				return nil, fmt.Errorf("failed to read config_bisect.pl log: %v", err)
+			}
+			configOptions = append(configOptions, ctx.parseConfigBisectLog(trace, logForParsing)...)
+
+			break
+		}
+	}
+
+	if err != nil || len(configOptions) == 0 {
+		return nil, fmt.Errorf("configuration bisection failed: %v", err)
+	}
+
+	// Parse minimalistic configuration to generate the crash
+	minimizedConfig, err := ctx.generateMinConfig(configOptions, bisectDir,
+		kernelBaselineConfig)
+	if err != nil {
+		return nil, fmt.Errorf("generating minimized config failed (%v)", err)
+	}
+
+	// Check that crash is really reproduced with generated config
+	testRes, err := pred(minimizedConfig)
+	if err != nil {
+		return nil, fmt.Errorf("testing generated minimized config failed (%v)", err)
+	}
+	if testRes == BisectGood {
+		fmt.Fprintf(trace, "# testing with generated minimized config doesn't reproduce the crash\n")
+		return original, nil
+	}
+	return minimizedConfig, nil
+}
+
+func (ctx *linux) prepareConfigBisectEnv(kernelConfig, kernelBaselineConfig string, original, baseline []byte) error {
+	current, err := ctx.HeadCommit()
+	if err != nil {
+		return err
+	}
+
+	// Call EnvForCommit if some options needs to be adjusted
+	bisectEnv, err := ctx.EnvForCommit("", current.Hash, original)
+	if err != nil {
+		return fmt.Errorf("failed create commit environment: %v", err)
+	}
+	if err := osutil.WriteFile(kernelConfig, bisectEnv.KernelConfig); err != nil {
+		return fmt.Errorf("failed to write config file: %v", err)
+	}
+
+	// Call EnvForCommit again if some options needs to be adjusted in baseline
+	bisectEnv, err = ctx.EnvForCommit("", current.Hash, baseline)
+	if err != nil {
+		return fmt.Errorf("failed create commit environment: %v", err)
+	}
+	if err := osutil.WriteFile(kernelBaselineConfig, bisectEnv.KernelConfig); err != nil {
+		return fmt.Errorf("failed to write minimum config file: %v", err)
+	}
+	return nil
+}
+
+//       Takes in config_bisect.pl output:
+//       Hmm, can't make any more changes without making good == bad?
+//       Difference between good (+) and bad (-)
+//        +DRIVER1=n
+//        +DRIVER2=n
+//        -DRIVER3=n
+//        -DRIVER4=n
+//        DRIVER5 n -> y
+//        DRIVER6 y -> n
+//       See good and bad configs for details:
+//       good: /mnt/work/linux/good_config.tmp
+//       bad:  /mnt/work/linux/bad_config.tmp
+func (ctx *linux) parseConfigBisectLog(trace io.Writer, bisectLog []byte) []string {
+	var configOptions []string
+	start := false
+	for _, line := range strings.Split(string(bisectLog), "\n") {
+		if strings.Contains(line, "See good and bad configs for details:") {
+			break
+		}
+		if start {
+			selection := ""
+			option := ""
+			configOptioon := ""
+			if strings.HasPrefix(line, "+") {
+				// This is option only in good config. Drop it as it's dependent
+				// on some option which is disabled in bad config.
+				continue
+			}
+			if strings.HasPrefix(line, "-") {
+				// -CONFIG_DRIVER_1=n
+				// Remove preceding -1 and split to option and selection
+				fields := strings.Split(strings.TrimPrefix(line, "-"), "=")
+				option = fields[0]
+				selection = fields[len(fields)-1]
+			} else {
+				// DRIVER_OPTION1 n -> y
+				fields := strings.Split(strings.TrimPrefix(line, " "), " ")
+				option = fields[0]
+				selection = fields[len(fields)-1]
+			}
+
+			if selection == "n" {
+				configOptioon = "# CONFIG_" + option + " is not set"
+			} else {
+				configOptioon = "CONFIG_" + option + "=" + selection
+			}
+
+			configOptions = append(configOptions, configOptioon)
+		}
+		if strings.Contains(line, "Difference between good (+) and bad (-)") {
+			start = true
+		}
+	}
+
+	fmt.Fprintf(trace, "# found config option changes %v\n", configOptions)
+	return configOptions
+}
+
+func (ctx *linux) generateMinConfig(configOptions []string, outdir string, baseline string) ([]byte, error) {
+	kernelAdditionsConfig := filepath.Join(outdir, "kernel.additions_config")
+	configMergeOutput := filepath.Join(outdir, ".config")
+	kernelMinConfig := filepath.Join(outdir, filepath.Base(baseline)+"_modified")
+
+	additionsFile, err := os.OpenFile(kernelAdditionsConfig, os.O_CREATE|os.O_WRONLY, 0644)
+	if err != nil {
+		return nil, fmt.Errorf("failed to create config additions file: %v", err)
+	}
+	defer additionsFile.Close()
+
+	for _, line := range configOptions {
+		if _, err := additionsFile.WriteString(line + "\n"); err != nil {
+			return nil, fmt.Errorf("failed to write config additions file: %v", err)
+		}
+	}
+
+	cmd := exec.Command(ctx.git.dir+"/scripts/kconfig/merge_config.sh", "-m",
+		"-O", outdir, baseline, kernelAdditionsConfig)
+
+	configMergeLog, err := os.Create(filepath.Join(outdir, "config_merge.log"))
+	if err != nil {
+		return nil, fmt.Errorf("failed to create merge log file: %v", err)
+	}
+	defer configMergeLog.Close()
+	cmd.Stdout = configMergeLog
+	cmd.Stderr = configMergeLog
+
+	if err := cmd.Run(); err != nil {
+		return nil, fmt.Errorf("config merge failed: %v", err)
+	}
+
+	minConfig, err := ioutil.ReadFile(configMergeOutput)
+	if err != nil {
+		return nil, fmt.Errorf("failed to read merged configuration: %v", err)
+	}
+
+	minConfigWithTag := []byte(configBisectTag)
+	minConfigWithTag = append(minConfigWithTag, []byte(", rev: ")...)
+	minConfigWithTag = append(minConfigWithTag, []byte(prog.GitRevision)...)
+	minConfigWithTag = append(minConfigWithTag, []byte("\n")...)
+	minConfigWithTag = append(minConfigWithTag, minConfig...)
+
+	if err := osutil.WriteFile(kernelMinConfig, minConfigWithTag); err != nil {
+		return nil, fmt.Errorf("failed to write tagged minimum config file: %v", err)
+	}
+	return minConfigWithTag, nil
+}
diff --git a/pkg/vcs/linux_test.go b/pkg/vcs/linux_test.go
new file mode 100644
index 000000000..ce61a9f4b
--- /dev/null
+++ b/pkg/vcs/linux_test.go
@@ -0,0 +1,114 @@
+// Copyright 2019 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package vcs
+
+import (
+	"bytes"
+	"io/ioutil"
+	"os"
+	"strings"
+	"testing"
+
+	"github.com/google/syzkaller/pkg/osutil"
+)
+
+type MinimizationTest struct {
+	config         string
+	baselineConfig string
+	// Output contains expected config option
+	expectedConfig string
+	// Minimization is expected to pass or fail
+	passing bool
+}
+
+func createTestLinuxRepo(t *testing.T) string {
+	baseDir, err := ioutil.TempDir("", "syz-config-bisect-test")
+	if err != nil {
+		t.Fatal(err)
+	}
+	repo := CreateTestRepo(t, baseDir, "")
+	repo.CommitChange("commit")
+	repo.SetTag("v4.1")
+	err = os.MkdirAll(baseDir+"/tools/testing/ktest", 0755)
+	if err != nil {
+		t.Fatal(err)
+	}
+	err = os.MkdirAll(baseDir+"/scripts/kconfig", 0755)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// Copy stubbed scripts used by config bisect
+	err = osutil.CopyFile("testdata/linux/config-bisect.pl",
+		baseDir+"/tools/testing/ktest/config-bisect.pl")
+	if err != nil {
+		t.Fatal(err)
+	}
+	err = osutil.CopyFile("testdata/linux/merge_config.sh",
+		baseDir+"/scripts/kconfig/merge_config.sh")
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	return baseDir
+}
+
+func TestMinimizationResults(t *testing.T) {
+	tests := []MinimizationTest{
+		{
+			config:         "CONFIG_ORIGINAL=y",
+			baselineConfig: "CONFIG_FAILING=y",
+			expectedConfig: "CONFIG_ORIGINAL=y",
+			passing:        false,
+		},
+		{
+			config:         "CONFIG_ORIGINAL=y",
+			baselineConfig: "CONFIG_REPRODUCES_CRASH=y",
+			expectedConfig: "CONFIG_REPRODUCES_CRASH=y",
+			passing:        true,
+		},
+		{
+			config:         "CONFIG_ORIGINAL=y",
+			baselineConfig: "CONFIG_NOT_REPRODUCE_CRASH=y",
+			expectedConfig: "CONFIG_ORIGINAL=y",
+			passing:        true,
+		},
+		{
+			config:         configBisectTag,
+			baselineConfig: "CONFIG_NOT_REPRODUCE_CRASH=y",
+			expectedConfig: configBisectTag,
+			passing:        true,
+		},
+	}
+
+	trace := new(bytes.Buffer)
+	baseDir := createTestLinuxRepo(t)
+	repo, err := NewRepo("linux", "64", baseDir)
+	if err != nil {
+		t.Fatalf("Unable to create repository")
+	}
+	pred := func(test []byte) (BisectResult, error) {
+		if strings.Contains(string(test), "CONFIG_REPRODUCES_CRASH=y") {
+			return BisectBad, nil
+		}
+		return BisectGood, nil
+	}
+
+	minimizer, ok := repo.(ConfigMinimizer)
+	if !ok {
+		t.Fatalf("Config minimization is not implemented")
+	}
+	for _, test := range tests {
+		outConfig, err := minimizer.Minimize([]byte(test.config),
+			[]byte(test.baselineConfig), trace, pred)
+		if test.passing && err != nil {
+			t.Fatalf("Failed to run Minimize")
+		} else if test.passing && !strings.Contains(string(outConfig),
+			test.expectedConfig) {
+			t.Fatalf("Output is not expected %v vs. %v", string(outConfig),
+				test.expectedConfig)
+		}
+	}
+	t.Log(trace.String())
+}
diff --git a/pkg/vcs/testdata/linux/config-bisect.pl b/pkg/vcs/testdata/linux/config-bisect.pl
new file mode 100755
index 000000000..5cecb8b6d
--- /dev/null
+++ b/pkg/vcs/testdata/linux/config-bisect.pl
@@ -0,0 +1,53 @@
+#!/bin/bash
+# Copyright 2020 syzkaller project authors. All rights reserved.
+# Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+# config-bisect.pl -l ctx.git.dir -r -b ctx.git.dir kernelBaselineConfig kernelConfig
+
+if [ "$3" == "-r" ]
+then
+    baseline=`cat $6`
+    outdir=$5
+    echo $baseline > $outdir/.config
+    exit 0
+fi
+
+# config-bisect.pl -l ctx.git.dir -b ctx.git.dir kernelBaselineConfig kernelConfig verdict
+baseline=`cat $5`
+
+# Test baseline file contains string CONFIG_FAILING -> fail
+if [ "$baseline" == "CONFIG_FAILING=y" ]
+then
+    exit 1
+fi
+
+# Generate end results which "reproduces" the crash
+if [ $baseline == "CONFIG_REPRODUCES_CRASH=y" ]
+then
+    echo "%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%"
+    echo "Hmm, can't make any more changes without making good == bad?"
+    echo "Difference between good (+) and bad (-)"
+    echo "REPRODUCES_CRASH n -> y"
+    echo "-DISABLED_OPTION=n"
+    echo "+ONLY_IN_ORIGINAL_OPTION=y"
+    echo "See good and bad configs for details:"
+    echo "good: /mnt/work/config_bisect_evaluation/out/config_bisect/kernel.baseline_config.tmp"
+    echo "bad:  /mnt/work/config_bisect_evaluation/out/config_bisect/kernel.config.tmp"
+    echo "%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%"
+    exit 2
+fi
+
+# Generate end result which doesn't "reproduce" the crash
+if [ $baseline == "CONFIG_NOT_REPRODUCE_CRASH=y" ]
+then
+    echo "%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%"
+    echo "Hmm, can't make any more changes without making good == bad?"
+    echo "Difference between good (+) and bad (-)"
+    echo "NOT_REPRODUCE_CRASH n -> y"
+    echo "See good and bad configs for details:"
+    echo "good: /mnt/work/config_bisect_evaluation/out/config_bisect/kernel.baseline_config.tmp"
+    echo "bad:  /mnt/work/config_bisect_evaluation/out/config_bisect/kernel.config.tmp"
+    echo "%%%%%%%% FAILED TO FIND SINGLE BAD CONFIG %%%%%%%%"
+    exit 2
+fi
+
+
diff --git a/pkg/vcs/testdata/linux/merge_config.sh b/pkg/vcs/testdata/linux/merge_config.sh
new file mode 100755
index 000000000..1ab10d379
--- /dev/null
+++ b/pkg/vcs/testdata/linux/merge_config.sh
@@ -0,0 +1,11 @@
+#!/bin/bash
+# Copyright 2020 syzkaller project authors. All rights reserved.
+# Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+# merge_config.sh -m -O outdir baseline kernelAdditionsConfig
+OUTDIR=$3
+
+echo `cat $4` > $OUTDIR/.config
+echo `cat $5` >> $OUTDIR/.config
+
+exit 0
diff --git a/pkg/vcs/testos.go b/pkg/vcs/testos.go
index 611937da7..c8746a684 100644
--- a/pkg/vcs/testos.go
+++ b/pkg/vcs/testos.go
@@ -3,10 +3,17 @@
 
 package vcs
 
+import (
+	"fmt"
+	"io"
+)
+
 type testos struct {
 	*git
 }
 
+var _ ConfigMinimizer = new(testos)
+
 func newTestos(dir string) *testos {
 	return &testos{
 		git: newGit(dir, nil),
@@ -18,5 +25,13 @@ func (ctx *testos) PreviousReleaseTags(commit string) ([]string, error) {
 }
 
 func (ctx *testos) EnvForCommit(binDir, commit string, kernelConfig []byte) (*BisectEnv, error) {
-	return &BisectEnv{}, nil
+	return &BisectEnv{KernelConfig: kernelConfig}, nil
+}
+
+func (ctx *testos) Minimize(original, baseline []byte, trace io.Writer,
+	pred func(test []byte) (BisectResult, error)) ([]byte, error) {
+	if string(baseline) == "minimize-fails" {
+		return nil, fmt.Errorf("minimization failure")
+	}
+	return original, nil
 }
diff --git a/pkg/vcs/vcs.go b/pkg/vcs/vcs.go
index 45751f598..9944baf88 100644
--- a/pkg/vcs/vcs.go
+++ b/pkg/vcs/vcs.go
@@ -69,6 +69,10 @@ type Bisecter interface {
 	EnvForCommit(binDir, commit string, kernelConfig []byte) (*BisectEnv, error)
 }
 
+type ConfigMinimizer interface {
+	Minimize(original, baseline []byte, trace io.Writer, pred func(test []byte) (BisectResult, error)) ([]byte, error)
+}
+
 type Commit struct {
 	Hash       string
 	Title      string