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.

1 files changed, 256 insertions, 0 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
+}