pkg/bisect: try to drop instrumentation

Refactor Minimize().

As a part of Minimize(), attempt to drop all unnecessary instrumentation
and test whether the kernel is still crashing.

This should reduce the number of irrelevant crashes during bisection and
thus increase bisection result quality.

4 files changed, 114 insertions, 27 deletions

diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go
index 815d6ba72..3d3de92b6 100644
--- a/pkg/bisect/bisect.go
+++ b/pkg/bisect/bisect.go
@@ -260,14 +260,14 @@ func (env *env) bisect() (*Result, error) {
 	}
 	env.reportTypes = testRes.types
 
-	if len(cfg.Kernel.BaselineConfig) != 0 {
-		testRes1, err := env.minimizeConfig()
-		if err != nil {
-			return nil, err
-		}
-		if testRes1 != nil {
-			testRes = testRes1
-		}
+	testRes1, err := env.minimizeConfig()
+	if err != nil {
+		return nil, fmt.Errorf("config minimization failed: %w", err)
+	}
+	if testRes1 != nil {
+		// If config minimization even partially succeeds, minimizeConfig()
+		// would return a non-nil value of a new report.
+		testRes = testRes1
 	}
 
 	bad, good, results1, fatalResult, err := env.commitRange()
@@ -372,11 +372,14 @@ func (env *env) minimizeConfig() (*testResult, error) {
 		if err != nil {
 			return 0, err
 		}
-		testResults[hash.Hash(test)] = testRes
+		if testRes.verdict == vcs.BisectBad {
+			// Only remember crashes.
+			testResults[hash.Hash(test)] = testRes
+		}
 		return testRes.verdict, err
 	}
 	minConfig, err := env.minimizer.Minimize(env.cfg.Manager.SysTarget, env.cfg.Kernel.Config,
-		env.cfg.Kernel.BaselineConfig, env.cfg.Trace, predMinimize)
+		env.cfg.Kernel.BaselineConfig, env.reportTypes, env.cfg.Trace, predMinimize)
 	if err != nil {
 		return nil, err
 	}
diff --git a/pkg/vcs/linux.go b/pkg/vcs/linux.go
index 07278e83f..c6effd58a 100644
--- a/pkg/vcs/linux.go
+++ b/pkg/vcs/linux.go
@@ -17,6 +17,7 @@ import (
 	"github.com/google/syzkaller/pkg/debugtracer"
 	"github.com/google/syzkaller/pkg/kconfig"
 	"github.com/google/syzkaller/pkg/osutil"
+	"github.com/google/syzkaller/pkg/report/crash"
 	"github.com/google/syzkaller/prog"
 	"github.com/google/syzkaller/sys/targets"
 )
@@ -304,7 +305,12 @@ func ParseMaintainersLinux(text []byte) Recipients {
 
 const configBisectTag = "# Minimized by syzkaller"
 
-func (ctx *linux) Minimize(target *targets.Target, original, baseline []byte,
+// Minimize() attempts to drop Linux kernel configs that are unnecessary(*) for bug reproduction.
+// 1. Remove sanitizers that are not needed to trigger the target class of bugs.
+// 2. Disable unrelated kernel subsystems. This is done by bisecting config changes between
+// `original` and `baseline`.
+// (*) After an unnecessary config is deleted, we still have pred() == BisectBad.
+func (ctx *linux) Minimize(target *targets.Target, original, baseline []byte, types []crash.Type,
 	dt debugtracer.DebugTracer, pred func(test []byte) (BisectResult, error)) ([]byte, error) {
 	if bytes.HasPrefix(original, []byte(configBisectTag)) {
 		dt.Log("# configuration already minimized\n")
@@ -314,27 +320,100 @@ func (ctx *linux) Minimize(target *targets.Target, original, baseline []byte,
 	if err != nil {
 		return nil, fmt.Errorf("failed to parse Kconfig: %v", err)
 	}
-	originalConfig, err := kconfig.ParseConfigData(original, "original")
+	config, err := kconfig.ParseConfigData(original, "original")
 	if err != nil {
 		return nil, err
 	}
-	baselineConfig, err := kconfig.ParseConfigData(baseline, "baseline")
+	minimizeCtx := &minimizeLinuxCtx{
+		kconf:  kconf,
+		config: config,
+		pred: func(cfg *kconfig.ConfigFile) (bool, error) {
+			res, err := pred(serialize(cfg))
+			return res == BisectBad, err
+		},
+		transform: func(cfg *kconfig.ConfigFile) {
+			setLinuxTagConfigs(cfg, nil)
+		},
+		DebugTracer: dt,
+	}
+	if len(types) > 0 {
+		// Technically, as almost all sanitizers are Yes/No config options, we could have
+		// achieved this minimization simply by disabling them all in the baseline config.
+		// However, we are now trying to make the most out of the few config minimization
+		// iterations we're ready to make do during the bisection process.
+		// Since it's possible to quite reliably determine the needed and unneeded sanitizers
+		// just by looking at crash reports, let's prefer a more complicated logic over worse
+		// bisection results.
+		// Once we start doing proper config minimizations for every reproducer, we can delete
+		// most of the related code.
+		err := minimizeCtx.dropInstrumentation(types)
+		if err != nil {
+			return nil, err
+		}
+	}
+	if len(baseline) > 0 {
+		baselineConfig, err := kconfig.ParseConfigData(baseline, "baseline")
+		if err != nil {
+			return nil, err
+		}
+		err = minimizeCtx.minimizeAgainst(baselineConfig)
+		if err != nil {
+			return nil, err
+		}
+	}
+	return minimizeCtx.getConfig(), nil
+}
+
+func serialize(cf *kconfig.ConfigFile) []byte {
+	return []byte(fmt.Sprintf("%v, rev: %v\n%s", configBisectTag, prog.GitRevision, cf.Serialize()))
+}
+
+type minimizeLinuxCtx struct {
+	kconf     *kconfig.KConfig
+	config    *kconfig.ConfigFile
+	pred      func(*kconfig.ConfigFile) (bool, error)
+	transform func(*kconfig.ConfigFile)
+	debugtracer.DebugTracer
+}
+
+func (ctx *minimizeLinuxCtx) minimizeAgainst(base *kconfig.ConfigFile) error {
+	base = base.Clone()
+	ctx.transform(base)
+	minConfig, err := ctx.kconf.Minimize(base, ctx.config, ctx.pred, ctx)
 	if err != nil {
-		return nil, err
+		return err
 	}
-	setLinuxTagConfigs(originalConfig, nil)
-	setLinuxTagConfigs(baselineConfig, nil)
-	kconfPred := func(candidate *kconfig.ConfigFile) (bool, error) {
-		res, err := pred(serialize(candidate))
-		return res == BisectBad, err
+	ctx.config = minConfig
+	return nil
+}
+
+func (ctx *minimizeLinuxCtx) dropInstrumentation(types []crash.Type) error {
+	ctx.Log("check whether we can drop unnecessary instrumentation")
+	oldTransform := ctx.transform
+	transform := func(c *kconfig.ConfigFile) {
+		oldTransform(c)
+		setLinuxSanitizerConfigs(c, types, ctx)
+	}
+	newConfig := ctx.config.Clone()
+	transform(newConfig)
+	if bytes.Equal(ctx.config.Serialize(), newConfig.Serialize()) {
+		ctx.Log("there was nothing we could disable; skip")
+		return nil
 	}
-	minConfig, err := kconf.Minimize(baselineConfig, originalConfig, kconfPred, dt)
+	ctx.SaveFile("no-instrumentation.config", newConfig.Serialize())
+	ok, err := ctx.pred(newConfig)
 	if err != nil {
-		return nil, err
+		return err
+	}
+	if ok {
+		ctx.Log("the bug reproduces without the instrumentation")
+		ctx.transform = transform
+		ctx.config = newConfig
 	}
-	return serialize(minConfig), nil
+	return nil
 }
 
-func serialize(cf *kconfig.ConfigFile) []byte {
-	return []byte(fmt.Sprintf("%v, rev: %v\n%s", configBisectTag, prog.GitRevision, cf.Serialize()))
+func (ctx *minimizeLinuxCtx) getConfig() []byte {
+	ctx.transform(ctx.config)
+	return serialize(ctx.config)
 }
diff --git a/pkg/vcs/testos.go b/pkg/vcs/testos.go
index fe7c3790f..cfc34cc23 100644
--- a/pkg/vcs/testos.go
+++ b/pkg/vcs/testos.go
@@ -7,6 +7,7 @@ import (
 	"fmt"
 
 	"github.com/google/syzkaller/pkg/debugtracer"
+	"github.com/google/syzkaller/pkg/report/crash"
 	"github.com/google/syzkaller/sys/targets"
 )
 
@@ -32,8 +33,11 @@ func (ctx *testos) EnvForCommit(
 	return &BisectEnv{KernelConfig: kernelConfig}, nil
 }
 
-func (ctx *testos) Minimize(target *targets.Target, original, baseline []byte,
+func (ctx *testos) Minimize(target *targets.Target, original, baseline []byte, types []crash.Type,
 	dt debugtracer.DebugTracer, pred func(test []byte) (BisectResult, error)) ([]byte, error) {
+	if len(baseline) == 0 {
+		return original, nil
+	}
 	if res, err := pred(baseline); err != nil {
 		return nil, err
 	} else if res == BisectBad {
diff --git a/pkg/vcs/vcs.go b/pkg/vcs/vcs.go
index 3e57a1695..9515692ea 100644
--- a/pkg/vcs/vcs.go
+++ b/pkg/vcs/vcs.go
@@ -16,6 +16,7 @@ import (
 	"github.com/google/syzkaller/dashboard/dashapi"
 	"github.com/google/syzkaller/pkg/debugtracer"
 	"github.com/google/syzkaller/pkg/osutil"
+	"github.com/google/syzkaller/pkg/report/crash"
 	"github.com/google/syzkaller/sys/targets"
 )
 
@@ -96,8 +97,8 @@ type Bisecter interface {
 }
 
 type ConfigMinimizer interface {
-	Minimize(target *targets.Target, original, baseline []byte, dt debugtracer.DebugTracer,
-		pred func(test []byte) (BisectResult, error)) ([]byte, error)
+	Minimize(target *targets.Target, original, baseline []byte, types []crash.Type,
+		dt debugtracer.DebugTracer, pred func(test []byte) (BisectResult, error)) ([]byte, error)
 }
 
 type Commit struct {