From 4e1c0dbaeab92f02cef51524975f6cc447667b80 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Thu, 10 May 2018 07:20:48 +0200 Subject: pkg/bisect: add bisection logic Add first version of bisection package (supports both bug and fix bisection). And tools/syz-bisect wrapper for testing. Update #501 --- pkg/bisect/bisect.go | 306 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 306 insertions(+) create mode 100644 pkg/bisect/bisect.go (limited to 'pkg/bisect') diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go new file mode 100644 index 000000000..b26631de4 --- /dev/null +++ b/pkg/bisect/bisect.go @@ -0,0 +1,306 @@ +// Copyright 2018 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 bisect + +import ( + "fmt" + "io" + "path/filepath" + "time" + + "github.com/google/syzkaller/pkg/git" + "github.com/google/syzkaller/pkg/instance" + "github.com/google/syzkaller/pkg/kernel" + "github.com/google/syzkaller/pkg/osutil" + "github.com/google/syzkaller/syz-manager/mgrconfig" +) + +type Config struct { + Trace io.Writer + Fix bool + BinDir string + DebugDir string + Kernel KernelConfig + Syzkaller SyzkallerConfig + Repro ReproConfig + Manager mgrconfig.Config +} + +type KernelConfig struct { + Repo string + Branch string + Commit string + Cmdline string + Sysctl string + Config []byte + Userspace string +} + +type SyzkallerConfig struct { + Repo string + Commit string + Descriptions string +} + +type ReproConfig struct { + Opts []byte + Syz []byte + C []byte +} + +type env struct { + cfg *Config + head *git.Commit + inst *instance.Env + numTests int + buildTime time.Duration + testTime time.Duration +} + +type buildEnv struct { + compiler string +} + +func Run(cfg *Config) (*git.Commit, error) { + env := &env{ + cfg: cfg, + } + if cfg.Fix { + env.log("searching for fixing commit since %v", cfg.Kernel.Commit) + } else { + env.log("searching for guilty commit starting from %v", cfg.Kernel.Commit) + } + start := time.Now() + res, err := env.bisect() + env.log("revisions tested: %v, total time: %v (build: %v, test: %v)", + env.numTests, time.Since(start), env.buildTime, env.testTime) + if err != nil { + env.log("error: %v", err) + return nil, err + } + if res == nil { + env.log("the crash is still unfixed") + return nil, nil + } + what := "bad" + if cfg.Fix { + what = "good" + } + env.log("first %v commit: %v %v", what, res.Hash, res.Title) + return res, nil +} + +func (env *env) bisect() (*git.Commit, error) { + cfg := env.cfg + var err error + if env.inst, err = instance.NewEnv(&cfg.Manager); err != nil { + return nil, err + } + if env.head, err = git.Poll(cfg.Manager.KernelSrc, cfg.Kernel.Repo, cfg.Kernel.Branch); err != nil { + return nil, err + } + if err := kernel.Clean(cfg.Manager.KernelSrc); err != nil { + return nil, fmt.Errorf("kernel clean failed: %v", err) + } + env.log("building syzkaller on %v", cfg.Syzkaller.Commit) + if err := env.inst.BuildSyzkaller(cfg.Syzkaller.Repo, cfg.Syzkaller.Commit); err != nil { + return nil, err + } + if _, err := git.SwitchCommit(cfg.Manager.KernelSrc, cfg.Kernel.Commit); err != nil { + return nil, err + } + if res, err := env.test(); err != nil { + return nil, err + } else if res != git.BisectBad { + return nil, fmt.Errorf("the crash wasn't reproduced on the original commit") + } + res, bad, good, err := env.commitRange() + if err != nil { + return nil, err + } + if res != nil { + return res, nil // happens on the oldest release + } + if good == "" { + return nil, nil // still not fixed + } + return git.Bisect(cfg.Manager.KernelSrc, bad, good, cfg.Trace, func() (git.BisectResult, error) { + res, err := env.test() + if cfg.Fix { + if res == git.BisectBad { + res = git.BisectGood + } else if res == git.BisectGood { + res = git.BisectBad + } + } + return res, err + }) +} + +func (env *env) commitRange() (*git.Commit, string, string, error) { + if env.cfg.Fix { + return env.commitRangeForFix() + } + return env.commitRangeForBug() +} + +func (env *env) commitRangeForFix() (*git.Commit, string, string, error) { + env.log("testing current HEAD %v", env.head.Hash) + if _, err := git.SwitchCommit(env.cfg.Manager.KernelSrc, env.head.Hash); err != nil { + return nil, "", "", err + } + res, err := env.test() + if err != nil { + return nil, "", "", err + } + if res != git.BisectGood { + return nil, "", "", nil + } + return nil, env.head.Hash, env.cfg.Kernel.Commit, nil +} + +func (env *env) commitRangeForBug() (*git.Commit, string, string, error) { + cfg := env.cfg + tags, err := git.PreviousReleaseTags(cfg.Manager.KernelSrc, cfg.Kernel.Commit) + if err != nil { + return nil, "", "", err + } + if len(tags) == 0 { + return nil, "", "", fmt.Errorf("no release tags before this commit") + } + lastBad := cfg.Kernel.Commit + for i, tag := range tags { + env.log("testing release %v", tag) + commit, err := git.SwitchCommit(cfg.Manager.KernelSrc, tag) + if err != nil { + return nil, "", "", err + } + res, err := env.test() + if err != nil { + return nil, "", "", err + } + if res == git.BisectGood { + return nil, lastBad, tag, nil + } + if res == git.BisectBad { + lastBad = tag + } + if i == len(tags)-1 { + return commit, "", "", nil + } + } + panic("unreachable") +} + +func (env *env) test() (git.BisectResult, error) { + cfg := env.cfg + env.numTests++ + current, err := git.HeadCommit(cfg.Manager.KernelSrc) + if err != nil { + return 0, err + } + be, err := env.buildEnvForCommit(current.Hash) + if err != nil { + return 0, err + } + compilerID, err := kernel.CompilerIdentity(be.compiler) + if err != nil { + return 0, err + } + env.log("testing commit %v with %v", current.Hash, compilerID) + buildStart := time.Now() + if err := kernel.Clean(cfg.Manager.KernelSrc); err != nil { + return 0, fmt.Errorf("kernel clean failed: %v", err) + } + err = env.inst.BuildKernel(be.compiler, cfg.Kernel.Userspace, + cfg.Kernel.Cmdline, cfg.Kernel.Sysctl, cfg.Kernel.Config) + env.buildTime += time.Since(buildStart) + if err != nil { + env.log("kernel build failed: %v", err) + return git.BisectSkip, nil + } + testStart := time.Now() + results, err := env.inst.Test(5, cfg.Repro.Syz, cfg.Repro.Opts, cfg.Repro.C) + env.testTime += time.Since(testStart) + if err != nil { + env.log("failed: %v", err) + return git.BisectSkip, nil + } + var bad, good int + for i, res := range results { + if res == nil { + good++ + env.log("try #%v: OK", i) + continue + } + switch err := res.(type) { + case *instance.TestError: + what := "basic kernel testing" + if err.Boot { + what = "boot" + } + env.log("try #%v: %v failed: %v", i, what, err) + output := err.Output + if err.Report != nil { + output = err.Report.Output + } + env.saveDebugFile(current.Hash, i, output) + case *instance.CrashError: + bad++ + env.log("try #%v: kernel crashed: %v", i, err) + output := err.Report.Report + if len(output) == 0 { + output = err.Report.Output + } + env.saveDebugFile(current.Hash, i, output) + default: + env.log("try #%v: failed: %v", i, err) + } + } + res := git.BisectSkip + if bad != 0 { + res = git.BisectBad + } else if good != 0 { + res = git.BisectGood + } + return res, nil +} + +// Note: linux-specific. +func (env *env) buildEnvForCommit(commit string) (*buildEnv, error) { + cfg := env.cfg + tags, err := git.PreviousReleaseTags(cfg.Manager.KernelSrc, commit) + if err != nil { + return nil, err + } + be := &buildEnv{ + compiler: filepath.Join(cfg.BinDir, "gcc-"+linuxCompilerVersion(tags), "bin", "gcc"), + } + return be, nil +} + +func linuxCompilerVersion(tags []string) string { + for _, tag := range tags { + switch tag { + case "v4.12": + return "8.1.0" + case "v4.11": + return "7.3.0" + case "v3.19": + return "5.5.0" + } + } + return "4.9.4" +} + +func (env *env) saveDebugFile(hash string, idx int, data []byte) { + if env.cfg.DebugDir == "" || len(data) == 0 { + return + } + osutil.WriteFile(filepath.Join(env.cfg.DebugDir, fmt.Sprintf("%v.%v", hash, idx)), data) +} + +func (env *env) log(msg string, args ...interface{}) { + fmt.Fprintf(env.cfg.Trace, msg+"\n", args...) +} -- cgit mrf-deployment