pkg/cover: ensure that all PCs returned by kcov have matching callbacks

In the case some modules' addresses are off, certain kernel addresses
returned by kcov may not have corresponding coverage callbacks in the
.ko files. Keep an additional map in the backend to verify those
addresses and report an error if that is the case.

Because GCC < 14 may tail-call coverage callbacks, the described check
is not performed for binaries which mention GCC in their .comment
section.

Also adjust text expectations in pkg/cover/report_test.go, so that
non-GCC targets check for PCs matching the callbacks.

See https://github.com/google/syzkaller/issues/4447 for more details.

6 files changed, 158 insertions, 11 deletions

diff --git a/pkg/cover/backend/backend.go b/pkg/cover/backend/backend.go
index 4bffcd65a..8a7f3b879 100644
--- a/pkg/cover/backend/backend.go
+++ b/pkg/cover/backend/backend.go
@@ -11,11 +11,12 @@ import (
 )
 
 type Impl struct {
-	Units     []*CompileUnit
-	Symbols   []*Symbol
-	Frames    []Frame
-	Symbolize func(pcs map[*Module][]uint64) ([]Frame, error)
-	RestorePC func(pc uint32) uint64
+	Units       []*CompileUnit
+	Symbols     []*Symbol
+	Frames      []Frame
+	Symbolize   func(pcs map[*Module][]uint64) ([]Frame, error)
+	RestorePC   func(pc uint32) uint64
+	CoverPoints map[uint64]bool
 }
 
 type Module struct {
diff --git a/pkg/cover/backend/dwarf.go b/pkg/cover/backend/dwarf.go
index 2e4096074..5902d6079 100644
--- a/pkg/cover/backend/dwarf.go
+++ b/pkg/cover/backend/dwarf.go
@@ -12,6 +12,7 @@ import (
 	"fmt"
 	"io"
 	"path/filepath"
+	"regexp"
 	"runtime"
 	"sort"
 	"strconv"
@@ -35,6 +36,7 @@ type dwarfParams struct {
 	readModuleCoverPoints func(*targets.Target, *Module, *symbolInfo) ([2][]uint64, error)
 	readTextRanges        func(*Module) ([]pcRange, []*CompileUnit, error)
 	getModuleOffset       func(string) uint64
+	getCompilerVersion    func(string) string
 }
 
 type Arch struct {
@@ -124,6 +126,28 @@ func processModule(params *dwarfParams, module *Module, info *symbolInfo,
 	return result, nil
 }
 
+// Regexps to parse compiler version string in IsKcovBrokenInCompiler.
+// Some targets (e.g. NetBSD) use g++ instead of gcc.
+var gccRE = regexp.MustCompile(`gcc|GCC|g\+\+`)
+var gccVersionRE = regexp.MustCompile(`(gcc|GCC|g\+\+).* ([0-9]{1,2})\.[0-9]+\.[0-9]+`)
+
+// GCC < 14 incorrectly tail-calls kcov callbacks, which does not let syzkaller
+// verify that collected coverage points have matching callbacks.
+// See https://github.com/google/syzkaller/issues/4447 for more information.
+func IsKcovBrokenInCompiler(versionStr string) bool {
+	if !gccRE.MatchString(versionStr) {
+		return false
+	}
+	groups := gccVersionRE.FindStringSubmatch(versionStr)
+	if len(groups) > 0 {
+		version, err := strconv.Atoi(groups[2])
+		if err == nil {
+			return version < 14
+		}
+	}
+	return true
+}
+
 func makeDWARFUnsafe(params *dwarfParams) (*Impl, error) {
 	target := params.target
 	objDir := params.objDir
@@ -141,6 +165,7 @@ func makeDWARFUnsafe(params *dwarfParams) (*Impl, error) {
 	var allRanges []pcRange
 	var allUnits []*CompileUnit
 	var pcBase uint64
+	var verifyCoverPoints = true
 	for _, module := range modules {
 		errc := make(chan error, 1)
 		go func() {
@@ -174,6 +199,9 @@ func makeDWARFUnsafe(params *dwarfParams) (*Impl, error) {
 		}
 		allRanges = append(allRanges, ranges...)
 		allUnits = append(allUnits, units...)
+		if IsKcovBrokenInCompiler(params.getCompilerVersion(module.Path)) {
+			verifyCoverPoints = false
+		}
 	}
 
 	sort.Slice(allSymbols, func(i, j int) bool {
@@ -207,13 +235,22 @@ func makeDWARFUnsafe(params *dwarfParams) (*Impl, error) {
 		// On FreeBSD .text address in ELF is 0, but .text is actually mapped at 0xffffffff.
 		pcBase = ^uint64(0)
 	}
+	var allCoverPointsMap = make(map[uint64]bool)
+	if verifyCoverPoints {
+		for i := 0; i < 2; i++ {
+			for _, pc := range allCoverPoints[i] {
+				allCoverPointsMap[pc] = true
+			}
+		}
+	}
 	impl := &Impl{
 		Units:   allUnits,
 		Symbols: allSymbols,
 		Symbolize: func(pcs map[*Module][]uint64) ([]Frame, error) {
 			return symbolize(target, objDir, srcDir, buildDir, pcs)
 		},
-		RestorePC: makeRestorePC(params, pcBase),
+		RestorePC:   makeRestorePC(params, pcBase),
+		CoverPoints: allCoverPointsMap,
 	}
 	return impl, nil
 }
diff --git a/pkg/cover/backend/dwarf_test.go b/pkg/cover/backend/dwarf_test.go
new file mode 100644
index 000000000..b82bea7db
--- /dev/null
+++ b/pkg/cover/backend/dwarf_test.go
@@ -0,0 +1,40 @@
+// Copyright 2024 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 backend
+
+import (
+	"testing"
+)
+
+// kcov is known to be broken in GCC versions < 14.
+// If the version cannot be parsed, assume it is broken.
+func TestIsKcovBrokenInCompiler(t *testing.T) {
+	inputDataTrue := []string{
+		"gcc (Debian 12.2.0-14) 12.2.0",
+		"gcc (Debian 13.2.0-5) 13.2.0",
+		"arm-unknown-linux-gnueabihf-g++ (GCC) 13.2.0",
+		"aarch64-unknown-linux-gnu-g++ (GCC) 11.1.0",
+		"g++ (Compiler-Explorer-Build-gcc-d3f1cf4e50356e44f745c5bc67ffd529cc4e2358-binutils-2.36.1) 12.0.0 20210426 (experimental)", // nolint:lll
+		"g++ (Compiler-Explorer-Build-gcc--binutils-2.40) 13.2.0",
+		"gcc (Compiler-Explorer-Build) 9.2.0",
+		"GCC something something",
+	}
+	inputDataFalse := []string{
+		"Debian clang version 16.0.6 (16)",
+		"arm-unknown-linux-gnueabihf-g++ (GCC) 14.0.1 20240124 (experimental)",
+		"g++ (Compiler-Explorer-Build-gcc-2a9637b229f64775d82fb5917f83f71e8ad1911d-binutils-2.40) 14.0.1 20240125 (experimental)", // nolint:lll
+	}
+	for _, ver := range inputDataTrue {
+		result := IsKcovBrokenInCompiler(ver)
+		if !result {
+			t.Fatalf("IsKcovBrokenInCompiler(`%s`) unexpectedly returned %v\n", ver, result)
+		}
+	}
+	for _, ver := range inputDataFalse {
+		result := IsKcovBrokenInCompiler(ver)
+		if result {
+			t.Fatalf("IsKcovBrokenInCompiler(`%s`) unexpectedly returned %v\n", ver, result)
+		}
+	}
+}
diff --git a/pkg/cover/backend/elf.go b/pkg/cover/backend/elf.go
index 5398d64bb..08d8890ce 100644
--- a/pkg/cover/backend/elf.go
+++ b/pkg/cover/backend/elf.go
@@ -29,6 +29,7 @@ func makeELF(target *targets.Target, objDir, srcDir, buildDir string,
 		readModuleCoverPoints: elfReadModuleCoverPoints,
 		readTextRanges:        elfReadTextRanges,
 		getModuleOffset:       elfGetModuleOffset,
+		getCompilerVersion:    elfGetCompilerVersion,
 	})
 }
 
@@ -211,6 +212,23 @@ func elfGetModuleOffset(path string) uint64 {
 	return 0
 }
 
+func elfGetCompilerVersion(path string) string {
+	file, err := elf.Open(path)
+	if err != nil {
+		return ""
+	}
+	defer file.Close()
+	sec := file.Section(".comment")
+	if sec == nil {
+		return ""
+	}
+	data, err := sec.Data()
+	if err != nil {
+		return ""
+	}
+	return string(data[:])
+}
+
 func alignUp(addr, align uint64) uint64 {
 	if align == 0 {
 		return addr
diff --git a/pkg/cover/report.go b/pkg/cover/report.go
index 2d1b8bd2e..a886eb014 100644
--- a/pkg/cover/report.go
+++ b/pkg/cover/report.go
@@ -88,12 +88,17 @@ func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error
 		}
 	}
 	progPCs := make(map[uint64]map[int]bool)
+	unmatchedProgPCs := make(map[uint64]bool)
+	verifyCoverPoints := (len(rg.CoverPoints) > 0)
 	for i, prog := range progs {
 		for _, pc := range prog.PCs {
 			if progPCs[pc] == nil {
 				progPCs[pc] = make(map[int]bool)
 			}
 			progPCs[pc][i] = true
+			if verifyCoverPoints && !rg.CoverPoints[pc] {
+				unmatchedProgPCs[pc] = true
+			}
 		}
 	}
 	matchedPC := false
@@ -123,6 +128,13 @@ func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error
 	if !matchedPC {
 		return nil, fmt.Errorf("coverage doesn't match any coverage callbacks")
 	}
+	// If the backend provided coverage callback locations for the binaries, use them to
+	// verify data returned by kcov.
+	if verifyCoverPoints && (len(unmatchedProgPCs) > 0) {
+		return nil, fmt.Errorf("%d out of %d PCs returned by kcov do not have matching "+
+			"coverage callbacks. Check the discoverModules() code",
+			len(unmatchedProgPCs), len(progPCs))
+	}
 	for _, unit := range rg.Units {
 		f := files[unit.Name]
 		for _, pc := range unit.PCs {
diff --git a/pkg/cover/report_test.go b/pkg/cover/report_test.go
index 64baf3ee2..c6c9d28f1 100644
--- a/pkg/cover/report_test.go
+++ b/pkg/cover/report_test.go
@@ -11,6 +11,7 @@ package cover
 import (
 	"bytes"
 	"encoding/csv"
+	"fmt"
 	"os"
 	"path/filepath"
 	"reflect"
@@ -36,8 +37,15 @@ type Test struct {
 	Progs     []Prog
 	DebugInfo bool
 	AddCover  bool
-	Result    string
-	Supports  func(target *targets.Target) bool
+	AddBadPc  bool
+	// Set by the testing environment depending on the target compiler.
+	// See https://github.com/google/syzkaller/issues/4447.
+	KcovIsBroken bool
+	// Set to true if the test should be skipped under broken kcov.
+	SkipIfKcovIsBroken bool
+	// Inexact coverage generated by AddCover=true may override empty Result.
+	Result   string
+	Supports func(target *targets.Target) bool
 }
 
 func TestReportGenerator(t *testing.T) {
@@ -74,6 +82,15 @@ func TestReportGenerator(t *testing.T) {
 			DebugInfo: true,
 		},
 		{
+			Name:               "mismatch-pcs",
+			AddCover:           true,
+			AddBadPc:           true,
+			CFlags:             []string{"-fsanitize-coverage=trace-pc"},
+			DebugInfo:          true,
+			SkipIfKcovIsBroken: true,
+			Result:             `.* do not have matching coverage callbacks`,
+		},
+		{
 			Name:      "good-pie",
 			AddCover:  true,
 			CFlags:    []string{"-fsanitize-coverage=trace-pc", "-fpie"},
@@ -116,12 +133,17 @@ func TestReportGenerator(t *testing.T) {
 				if target.BrokenCompiler != "" {
 					t.Skip("skipping the test due to broken cross-compiler:\n" + target.BrokenCompiler)
 				}
+				kcovIsBroken := targetKcovIsBroken(t, target)
 				for _, test := range tests {
 					test := test
+					test.KcovIsBroken = kcovIsBroken
 					t.Run(test.Name, func(t *testing.T) {
 						if test.Supports != nil && !test.Supports(target) {
 							t.Skip("unsupported target")
 						}
+						if test.SkipIfKcovIsBroken && test.KcovIsBroken {
+							t.Skip("coverage testing requested, but kcov is broken")
+						}
 						t.Parallel()
 						testReportGenerator(t, target, test)
 					})
@@ -132,7 +154,7 @@ func TestReportGenerator(t *testing.T) {
 }
 
 func testReportGenerator(t *testing.T, target *targets.Target, test Test) {
-	rep, csv, err := generateReport(t, target, test)
+	rep, csv, err := generateReport(t, target, &test)
 	if err != nil {
 		if test.Result == "" {
 			t.Fatalf("expected no error, but got:\n%v", err)
@@ -177,7 +199,7 @@ void* aslr_base() { return NULL; }
 void __sanitizer_cov_trace_pc() { printf("%llu", (long long)(__builtin_return_address(0) - aslr_base())); }
 `
 
-func buildTestBinary(t *testing.T, target *targets.Target, test Test, dir string) string {
+func buildTestBinary(t *testing.T, target *targets.Target, test *Test, dir string) string {
 	kcovSrc := filepath.Join(dir, "kcov.c")
 	kcovObj := filepath.Join(dir, "kcov.o")
 	if err := osutil.WriteFile(kcovSrc, []byte(kcovCode)); err != nil {
@@ -257,7 +279,15 @@ func buildTestBinary(t *testing.T, target *targets.Target, test Test, dir string
 	return bin
 }
 
-func generateReport(t *testing.T, target *targets.Target, test Test) ([]byte, []byte, error) {
+// Work around https://github.com/google/syzkaller/issues/4447. Do not use for anything else.
+func targetKcovIsBroken(t *testing.T, target *targets.Target) bool {
+	if out, err := osutil.RunCmd(time.Hour, "", target.CCompiler, "--version"); err == nil {
+		return backend.IsKcovBrokenInCompiler(string(out))
+	}
+	return true
+}
+
+func generateReport(t *testing.T, target *targets.Target, test *Test) ([]byte, []byte, error) {
 	dir := t.TempDir()
 	bin := buildTestBinary(t, target, test, dir)
 	cfg := &mgrconfig.Config{
@@ -292,6 +322,7 @@ func generateReport(t *testing.T, target *targets.Target, test Test) ([]byte, []
 	}
 	if test.AddCover {
 		var pcs []uint64
+		Inexact := false
 		// Sanitizers crash when installing signal handlers with static libc.
 		const sanitizerOptions = "handle_segv=0:handle_sigbus=0:handle_sigfpe=0"
 		cmd := osutil.Command(bin)
@@ -322,6 +353,14 @@ func generateReport(t *testing.T, target *targets.Target, test Test) ([]byte, []
 				pcs = append(pcs, main.Addr+uint64(off))
 			}
 			t.Logf("using inexact coverage range 0x%x-0x%x", main.Addr, main.Addr+uint64(main.Size))
+			Inexact = true
+		}
+		if Inexact && test.Result == "" && !test.KcovIsBroken {
+			test.Result = fmt.Sprintf("%d out of %d PCs returned by kcov do not have matching coverage callbacks",
+				len(pcs)-1, len(pcs))
+		}
+		if test.AddBadPc {
+			pcs = append(pcs, 0xdeadbeef)
 		}
 		progs = append(progs, Prog{Data: "main", PCs: pcs})
 	}