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.

8 files changed, 596 insertions, 23 deletions

diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go
index fb11e5753..ff464f814 100644
--- a/pkg/bisect/bisect.go
+++ b/pkg/bisect/bisect.go
@@ -29,12 +29,18 @@ type Config struct {
 }
 
 type KernelConfig struct {
-	Repo           string
-	Branch         string
-	Commit         string
-	Cmdline        string
-	Sysctl         string
-	Config         []byte
+	Repo    string
+	Branch  string
+	Commit  string
+	Cmdline string
+	Sysctl  string
+	Config  []byte
+	// Baseline configuration is used in commit bisection. If the crash doesn't reproduce
+	// with baseline configuratopm config bisection is run. When triggering configuration
+	// option is found provided baseline configuration is modified according the bisection
+	// results. This new configuration is tested once more with current head. If crash
+	// reproduces with the generated configuration original configuation is replaced with
+	//this minimized one
 	BaselineConfig []byte
 	Userspace      string
 }
@@ -55,6 +61,7 @@ type env struct {
 	cfg       *Config
 	repo      vcs.Repo
 	bisecter  vcs.Bisecter
+	minimizer vcs.ConfigMinimizer
 	commit    *vcs.Commit
 	head      *vcs.Commit
 	inst      instance.Env
@@ -80,10 +87,12 @@ const NumTests = 10 // number of tests we do per commit
 //    - no commits in Commits
 //    - the crash report on the oldest release/HEAD;
 //    - Commit points to the oldest/latest commit where crash happens.
+//  - Config contains kernel config used for bisection
 type Result struct {
 	Commits    []*vcs.Commit
 	Report     *report.Report
 	Commit     *vcs.Commit
+	Config     *[]byte
 	NoopChange bool
 	IsRelease  bool
 }
@@ -103,6 +112,10 @@ func Run(cfg *Config) (*Result, error) {
 	if !ok {
 		return nil, fmt.Errorf("bisection is not implemented for %v", cfg.Manager.TargetOS)
 	}
+
+	// Minimizer may or may not be supported
+	minimizer, _ := repo.(vcs.ConfigMinimizer)
+
 	inst, err := instance.NewEnv(&cfg.Manager)
 	if err != nil {
 		return nil, err
@@ -110,15 +123,17 @@ func Run(cfg *Config) (*Result, error) {
 	if _, err = repo.CheckoutBranch(cfg.Kernel.Repo, cfg.Kernel.Branch); err != nil {
 		return nil, err
 	}
-	return runImpl(cfg, repo, bisecter, inst)
+	return runImpl(cfg, repo, bisecter, minimizer, inst)
 }
 
-func runImpl(cfg *Config, repo vcs.Repo, bisecter vcs.Bisecter, inst instance.Env) (*Result, error) {
+func runImpl(cfg *Config, repo vcs.Repo, bisecter vcs.Bisecter, minimizer vcs.ConfigMinimizer,
+	inst instance.Env) (*Result, error) {
 	env := &env{
-		cfg:      cfg,
-		repo:     repo,
-		bisecter: bisecter,
-		inst:     inst,
+		cfg:       cfg,
+		repo:      repo,
+		bisecter:  bisecter,
+		minimizer: minimizer,
+		inst:      inst,
 	}
 	head, err := repo.HeadCommit()
 	if err != nil {
@@ -183,6 +198,7 @@ func (env *env) bisect() (*Result, error) {
 	if err != nil {
 		return nil, err
 	}
+
 	env.commit = com
 	testRes, err := env.test()
 	if err != nil {
@@ -190,12 +206,18 @@ func (env *env) bisect() (*Result, error) {
 	} else if testRes.verdict != vcs.BisectBad {
 		return nil, fmt.Errorf("the crash wasn't reproduced on the original commit")
 	}
+
+	if cfg.Kernel.BaselineConfig != nil {
+		env.minimizeConfig()
+	}
+
 	bad, good, rep1, results1, err := env.commitRange()
 	if err != nil {
 		return nil, err
 	}
 	if rep1 != nil {
-		return &Result{Report: rep1, Commit: bad}, nil // still not fixed/happens on the oldest release
+		return &Result{Report: rep1, Commit: bad, Config: &cfg.Kernel.Config},
+			nil // still not fixed/happens on the oldest release
 	}
 	results := map[string]*testResult{cfg.Kernel.Commit: testRes}
 	for _, res := range results1 {
@@ -222,6 +244,7 @@ func (env *env) bisect() (*Result, error) {
 	}
 	res := &Result{
 		Commits: commits,
+		Config:  &cfg.Kernel.Config,
 	}
 	if len(commits) == 1 {
 		com := commits[0]
@@ -244,6 +267,39 @@ func (env *env) bisect() (*Result, error) {
 	return res, nil
 }
 
+func (env *env) minimizeConfig() {
+	cfg := env.cfg
+	// Check if crash reproduces with baseline config
+	originalConfig := cfg.Kernel.Config
+	cfg.Kernel.Config = cfg.Kernel.BaselineConfig
+	testRes, err := env.test()
+	cfg.Kernel.Config = originalConfig
+	if err != nil {
+		env.log("testing baseline config failed")
+	} else if testRes.verdict == vcs.BisectBad {
+		env.log("crash reproduces with baseline config")
+		cfg.Kernel.Config = cfg.Kernel.BaselineConfig
+	} else if testRes.verdict == vcs.BisectGood && env.minimizer != nil {
+		predMinimize := func(test []byte) (vcs.BisectResult, error) {
+			cfg.Kernel.Config = test
+			testRes, err := env.test()
+			if err != nil {
+				return 0, err
+			}
+			return testRes.verdict, err
+		}
+		// Find minimal configuration based on baseline to reproduce the crash
+		cfg.Kernel.Config, err = env.minimizer.Minimize(cfg.Kernel.Config,
+			cfg.Kernel.BaselineConfig, cfg.Trace, predMinimize)
+		if err != nil {
+			env.log("Minimizing config failed, using original config")
+			cfg.Kernel.Config = originalConfig
+		}
+	} else {
+		env.log("unable to test using baseline config, keep original config")
+	}
+}
+
 func (env *env) detectNoopChange(results map[string]*testResult, com *vcs.Commit) (bool, error) {
 	testRes := results[com.Hash]
 	if testRes.kernelSign == "" || len(com.Parents) != 1 {
@@ -341,6 +397,7 @@ func (env *env) build() (*vcs.Commit, string, error) {
 	if err != nil {
 		return nil, "", err
 	}
+
 	bisectEnv, err := env.bisecter.EnvForCommit(env.cfg.BinDir, current.Hash, env.cfg.Kernel.Config)
 	if err != nil {
 		return nil, "", err
diff --git a/pkg/bisect/bisect_test.go b/pkg/bisect/bisect_test.go
index 2bad2192b..29acffd14 100644
--- a/pkg/bisect/bisect_test.go
+++ b/pkg/bisect/bisect_test.go
@@ -20,9 +20,11 @@ import (
 // testEnv will implement instance.BuilderTester. This allows us to
 // set bisect.env.inst to a testEnv object.
 type testEnv struct {
-	t    *testing.T
-	r    vcs.Repo
-	test BisectionTest
+	t *testing.T
+	r vcs.Repo
+	// Kernel config used in "build"
+	config string
+	test   BisectionTest
 }
 
 func (env *testEnv) BuildSyzkaller(repo, commit string) error {
@@ -36,17 +38,25 @@ func (env *testEnv) BuildKernel(compilerBin, userspaceDir, cmdlineFile, sysctlFi
 	if commit >= env.test.sameBinaryStart && commit <= env.test.sameBinaryEnd {
 		kernelSign = "same-sign"
 	}
+	env.config = string(kernelConfig)
+	if env.config == "baseline-fails" {
+		return "", kernelSign, fmt.Errorf("Failure")
+	}
 	return "", kernelSign, nil
 }
 
 func (env *testEnv) Test(numVMs int, reproSyz, reproOpts, reproC []byte) ([]error, error) {
 	commit := env.headCommit()
-	if commit >= env.test.brokenStart && commit <= env.test.brokenEnd {
+	if commit >= env.test.brokenStart && commit <= env.test.brokenEnd ||
+		env.config == "baseline-skip" {
 		return nil, fmt.Errorf("broken build")
 	}
-	if !env.test.fix && commit >= env.test.culprit || env.test.fix && commit < env.test.culprit {
+	if (env.config == "baseline-repro" || env.config == "original config") &&
+		(!env.test.fix && commit >= env.test.culprit || env.test.fix &&
+			commit < env.test.culprit) {
 		return crashErrors(numVMs, "crash occurs"), nil
 	}
+
 	return make([]error, numVMs), nil
 }
 
@@ -114,8 +124,10 @@ func runBisection(t *testing.T, baseDir string, test BisectionTest) (*Result, er
 			KernelSrc:    baseDir,
 		},
 		Kernel: KernelConfig{
-			Repo:   baseDir,
-			Commit: sc.Hash,
+			Repo:           baseDir,
+			Commit:         sc.Hash,
+			Config:         []byte("original config"),
+			BaselineConfig: []byte(test.baselineConfig),
 		},
 	}
 	inst := &testEnv{
@@ -123,7 +135,7 @@ func runBisection(t *testing.T, baseDir string, test BisectionTest) (*Result, er
 		r:    r,
 		test: test,
 	}
-	res, err := runImpl(cfg, r, r.(vcs.Bisecter), inst)
+	res, err := runImpl(cfg, r, r.(vcs.Bisecter), r.(vcs.ConfigMinimizer), inst)
 	t.Log(trace.String())
 	return res, err
 }
@@ -146,7 +158,8 @@ type BisectionTest struct {
 	commitLen    int
 	oldestLatest int
 	// input and output
-	culprit int
+	culprit        int
+	baselineConfig string
 }
 
 var bisectionTests = []BisectionTest{
@@ -158,6 +171,56 @@ var bisectionTests = []BisectionTest{
 		expectRep:   true,
 		culprit:     602,
 	},
+	// Test bisection returns correct cause with different baseline/config
+	// combinations
+	{
+		name:           "cause-finds-cause-baseline-repro",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "baseline-repro",
+	},
+	{
+		name:           "cause-finds-cause-baseline-does-not-repro",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "baseline-not-reproducing",
+	},
+	{
+		name:           "cause-finds-cause-baseline-fails",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "baseline-fails",
+	},
+	{
+		name:           "cause-finds-cause-baseline-skip",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "baseline-skip",
+	},
+	{
+		name:           "cause-finds-cause-minimize_succeeds",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "minimize-succeeds",
+	},
+	{
+		name:           "cause-finds-cause-minimize_fails",
+		startCommit:    905,
+		commitLen:      1,
+		expectRep:      true,
+		culprit:        602,
+		baselineConfig: "minimize-fails",
+	},
 	// Tests that cause bisection returns error when crash does not reproduce
 	// on the original commit.
 	{
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