syz-manager, pkg/cover: normalize module PCs between VM instances

Created a hash in syz-manager to map between each
instance address and a stored canonical address.

Translate PC coverage values when receiving inputs
from VMs and when sending inputs to each VM.

Signal conversion and coverage filtering will be
fixed in a future commit.

4 files changed, 282 insertions, 2 deletions

diff --git a/pkg/cover/canonicalizer.go b/pkg/cover/canonicalizer.go
new file mode 100644
index 000000000..011165c18
--- /dev/null
+++ b/pkg/cover/canonicalizer.go
@@ -0,0 +1,130 @@
+// Copyright 2023 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 cover
+
+import (
+	"sort"
+
+	"github.com/google/syzkaller/pkg/host"
+)
+
+type Canonicalizer struct {
+	// Map of modules stored as module name:kernel offset.
+	modules map[string]uint32
+
+	// Contains a sorted list of the canonical module addresses.
+	moduleKeys []uint32
+}
+
+type CanonicalizerInstance struct {
+	canonical Canonicalizer
+
+	// Contains a sorted list of the instance's module addresses.
+	moduleKeys []uint32
+
+	// Contains a map of the uint32 address to the necessary offset.
+	instToCanonicalMap map[uint32]*canonicalizerModule
+	canonicalToInstMap map[uint32]*canonicalizerModule
+}
+
+// Contains the offset and final address of each module.
+type canonicalizerModule struct {
+	offset  int
+	endAddr uint32
+}
+
+func NewCanonicalizer(modules []host.KernelModule) *Canonicalizer {
+	// Create a map of canonical module offsets by name.
+	canonicalModules := make(map[string]uint32)
+	for _, module := range modules {
+		canonicalModules[module.Name] = uint32(module.Addr)
+	}
+
+	// Store sorted canonical address keys.
+	canonicalModuleKeys := make([]uint32, len(modules))
+	setModuleKeys(canonicalModuleKeys, modules)
+	return &Canonicalizer{
+		modules:    canonicalModules,
+		moduleKeys: canonicalModuleKeys,
+	}
+}
+
+func (can *Canonicalizer) NewInstance(modules []host.KernelModule) *CanonicalizerInstance {
+	// Save sorted list of module offsets.
+	moduleKeys := make([]uint32, len(modules))
+	setModuleKeys(moduleKeys, modules)
+
+	// Create a hash between the "canonical" module addresses and each VM instance.
+	instToCanonicalMap := make(map[uint32]*canonicalizerModule)
+	canonicalToInstMap := make(map[uint32]*canonicalizerModule)
+	for _, module := range modules {
+		canonicalAddr := can.modules[module.Name]
+		instAddr := uint32(module.Addr)
+
+		canonicalModule := &canonicalizerModule{
+			offset:  int(instAddr) - int(canonicalAddr),
+			endAddr: uint32(module.Size) + canonicalAddr,
+		}
+		canonicalToInstMap[canonicalAddr] = canonicalModule
+
+		instModule := &canonicalizerModule{
+			offset:  int(canonicalAddr) - int(instAddr),
+			endAddr: uint32(module.Size) + instAddr,
+		}
+		instToCanonicalMap[instAddr] = instModule
+	}
+
+	return &CanonicalizerInstance{
+		canonical:          *can,
+		moduleKeys:         moduleKeys,
+		instToCanonicalMap: instToCanonicalMap,
+		canonicalToInstMap: canonicalToInstMap,
+	}
+}
+
+func (ci *CanonicalizerInstance) Canonicalize(cov []uint32) {
+	convertModulePCs(ci.moduleKeys, ci.instToCanonicalMap, cov)
+}
+
+func (ci *CanonicalizerInstance) Decanonicalize(cov []uint32) {
+	convertModulePCs(ci.canonical.moduleKeys, ci.canonicalToInstMap, cov)
+}
+
+// Store sorted list of addresses. Used to binary search when converting PCs.
+func setModuleKeys(moduleKeys []uint32, modules []host.KernelModule) {
+	for idx, module := range modules {
+		// Truncate PCs to uint32, assuming that they fit into 32 bits.
+		// True for x86_64 and arm64 without KASLR.
+		moduleKeys[idx] = uint32(module.Addr)
+	}
+
+	// Sort modules by address.
+	sort.Slice(moduleKeys, func(i, j int) bool { return moduleKeys[i] < moduleKeys[j] })
+}
+
+func convertModulePCs(moduleKeys []uint32, conversionHash map[uint32]*canonicalizerModule, cov []uint32) {
+	// Skip conversion if modules are not used.
+	if len(moduleKeys) == 0 {
+		return
+	}
+	for idx, pc := range cov {
+		// Determine which module each pc belongs to.
+		moduleIdx, _ := sort.Find(len(moduleKeys), func(i int) int {
+			if pc < moduleKeys[i] {
+				return -1
+			}
+			return +1
+		})
+		// Sort.Find returns the index above the correct module.
+		moduleIdx -= 1
+		// Check if address is above the first module address.
+		if moduleIdx >= 0 {
+			module := conversionHash[moduleKeys[moduleIdx]]
+			// If the address is within the found module add the offset.
+			if pc < module.endAddr {
+				cov[idx] = uint32(int(pc) + module.offset)
+			}
+		}
+	}
+}
diff --git a/pkg/cover/canonicalizer_test.go b/pkg/cover/canonicalizer_test.go
new file mode 100644
index 000000000..4d004aa32
--- /dev/null
+++ b/pkg/cover/canonicalizer_test.go
@@ -0,0 +1,144 @@
+// Copyright 2023 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.
+
+// Tests the translation of coverage pcs between fuzzer instances with differing module offsets.
+
+package cover_test
+
+import (
+	"fmt"
+	"strconv"
+	"testing"
+
+	"github.com/google/syzkaller/pkg/cover"
+	"github.com/google/syzkaller/pkg/host"
+)
+
+type RPCServer struct {
+	canonicalModules   *cover.Canonicalizer
+	modulesInitialized bool
+	fuzzers            map[string]*Fuzzer
+}
+
+type Fuzzer struct {
+	instModules *cover.CanonicalizerInstance
+}
+
+// Confirms there is no change to coverage if modules aren't instantiated.
+func TestNilModules(t *testing.T) {
+	serv := &RPCServer{
+		fuzzers: make(map[string]*Fuzzer),
+	}
+	serv.Connect("f1", nil)
+	serv.Connect("f2", nil)
+
+	testCov := []uint32{0x00010000, 0x00020000, 0x00030000, 0x00040000}
+	goalOut := []uint32{0x00010000, 0x00020000, 0x00030000, 0x00040000}
+
+	for name, fuzzer := range serv.fuzzers {
+		fuzzer.instModules.Canonicalize(testCov)
+		for idx, cov := range testCov {
+			if cov != goalOut[idx] {
+				failMsg := fmt.Errorf("fuzzer %v.\nExpected: 0x%x.\nReturned: 0x%x",
+					name, goalOut[idx], cov)
+				t.Fatalf("failed in canonicalization. %v", failMsg)
+			}
+		}
+
+		fuzzer.instModules.Decanonicalize(testCov)
+		for idx, cov := range testCov {
+			if cov != goalOut[idx] {
+				failMsg := fmt.Errorf("fuzzer %v.\nExpected: 0x%x.\nReturned: 0x%x",
+					name, goalOut[idx], cov)
+				t.Fatalf("failed in decanonicalization. %v", failMsg)
+			}
+		}
+	}
+}
+
+// Tests coverage conversion when modules are instantiated.
+func TestModules(t *testing.T) {
+	serv := &RPCServer{
+		fuzzers: make(map[string]*Fuzzer),
+	}
+
+	// Create modules at the specified address offsets.
+	var f1Modules, f2Modules []host.KernelModule
+	f1ModuleAddresses := []uint64{0x00015000, 0x00020000, 0x00030000, 0x00040000, 0x00045000}
+	f1ModuleSizes := []uint64{0x5000, 0x5000, 0x10000, 0x5000, 0x10000}
+
+	f2ModuleAddresses := []uint64{0x00015000, 0x00040000, 0x00045000, 0x00020000, 0x00030000}
+	f2ModuleSizes := []uint64{0x5000, 0x5000, 0x10000, 0x5000, 0x10000}
+	for idx, address := range f1ModuleAddresses {
+		f1Modules = append(f1Modules, host.KernelModule{
+			Name: strconv.FormatInt(int64(idx), 10),
+			Addr: address,
+			Size: f1ModuleSizes[idx],
+		})
+	}
+	for idx, address := range f2ModuleAddresses {
+		f2Modules = append(f2Modules, host.KernelModule{
+			Name: strconv.FormatInt(int64(idx), 10),
+			Addr: address,
+			Size: f2ModuleSizes[idx],
+		})
+	}
+
+	serv.Connect("f1", f1Modules)
+	serv.Connect("f2", f2Modules)
+
+	testCov := make(map[string][]uint32)
+	goalOutCanonical := make(map[string][]uint32)
+	goalOutDecanonical := make(map[string][]uint32)
+
+	// f1 is the "canonical" fuzzer as it is first one instantiated.
+	// This means that all coverage output should be the same as the inputs.
+	testCov["f1"] = []uint32{0x00010000, 0x00015000, 0x00020000, 0x00025000, 0x00030000,
+		0x00035000, 0x00040000, 0x00045000, 0x00050000, 0x00055000}
+	goalOutCanonical["f1"] = []uint32{0x00010000, 0x00015000, 0x00020000, 0x00025000, 0x00030000,
+		0x00035000, 0x00040000, 0x00045000, 0x00050000, 0x00055000}
+	goalOutDecanonical["f1"] = []uint32{0x00010000, 0x00015000, 0x00020000, 0x00025000, 0x00030000,
+		0x00035000, 0x00040000, 0x00045000, 0x00050000, 0x00055000}
+
+	// The modules addresss are inverted between: (2 and 4), (3 and 5),
+	// affecting the output canonical coverage values in these ranges.
+	testCov["f2"] = []uint32{0x00010000, 0x00015000, 0x00020000, 0x00025000, 0x00030000,
+		0x00035000, 0x00040000, 0x00045000, 0x00050000, 0x00055000}
+	goalOutCanonical["f2"] = []uint32{0x00010000, 0x00015000, 0x00040000, 0x00025000, 0x00045000,
+		0x0004a000, 0x00020000, 0x00030000, 0x0003b000, 0x00055000}
+	goalOutDecanonical["f2"] = []uint32{0x00010000, 0x00015000, 0x00020000, 0x00025000, 0x00030000,
+		0x00035000, 0x00040000, 0x00045000, 0x00050000, 0x00055000}
+
+	for name, fuzzer := range serv.fuzzers {
+		// Test address conversion from instance to canonical.
+		fuzzer.instModules.Canonicalize(testCov[name])
+		for idx, cov := range testCov[name] {
+			if cov != goalOutCanonical[name][idx] {
+				failMsg := fmt.Errorf("fuzzer %v.\nExpected: 0x%x.\nReturned: 0x%x",
+					name, goalOutCanonical[name][idx], cov)
+				t.Fatalf("failed in canonicalization. %v", failMsg)
+			}
+		}
+
+		// Test address conversion from canonical to instance.
+		fuzzer.instModules.Decanonicalize(testCov[name])
+		for idx, cov := range testCov[name] {
+			if cov != goalOutDecanonical[name][idx] {
+				failMsg := fmt.Errorf("fuzzer %v.\nExpected: 0x%x.\nReturned: 0x%x",
+					name, goalOutDecanonical[name][idx], cov)
+				t.Fatalf("failed in decanonicalization. %v", failMsg)
+			}
+		}
+	}
+}
+
+func (serv *RPCServer) Connect(name string, modules []host.KernelModule) {
+	if !serv.modulesInitialized {
+		serv.canonicalModules = cover.NewCanonicalizer(modules)
+		serv.modulesInitialized = true
+	}
+
+	serv.fuzzers[name] = &Fuzzer{
+		instModules: serv.canonicalModules.NewInstance(modules),
+	}
+}
diff --git a/pkg/host/machine_info.go b/pkg/host/machine_info.go
index 7078c3175..6dd2f0686 100644
--- a/pkg/host/machine_info.go
+++ b/pkg/host/machine_info.go
@@ -57,4 +57,5 @@ type machineInfoFunc struct {
 type KernelModule struct {
 	Name string
 	Addr uint64
+	Size uint64
 }
diff --git a/pkg/host/machine_info_linux.go b/pkg/host/machine_info_linux.go
index fc3664c42..702b55cb3 100644
--- a/pkg/host/machine_info_linux.go
+++ b/pkg/host/machine_info_linux.go
@@ -127,15 +127,20 @@ func readKVMInfo(buffer *bytes.Buffer) error {
 func getModulesInfo() ([]KernelModule, error) {
 	var modules []KernelModule
 	modulesText, _ := os.ReadFile("/proc/modules")
-	re := regexp.MustCompile(`(\w+) .*(0[x|X][a-fA-F0-9]+)[^\n]*`)
+	re := regexp.MustCompile(`(\w+) ([0-9]+) .*(0[x|X][a-fA-F0-9]+)[^\n]*`)
 	for _, m := range re.FindAllSubmatch(modulesText, -1) {
-		addr, err := strconv.ParseUint(string(m[2]), 0, 64)
+		addr, err := strconv.ParseUint(string(m[3]), 0, 64)
 		if err != nil {
 			return nil, fmt.Errorf("address parsing error in /proc/modules: %v", err)
 		}
+		size, err := strconv.ParseUint(string(m[2]), 0, 64)
+		if err != nil {
+			return nil, fmt.Errorf("module size parsing error in /proc/modules: %v", err)
+		}
 		modules = append(modules, KernelModule{
 			Name: string(m[1]),
 			Addr: addr,
+			Size: size,
 		})
 	}
 	return modules, nil