From c778c7f49050c40ff7c5e409d9b2c667483b3fc9 Mon Sep 17 00:00:00 2001 From: Liz Prucka Date: Tue, 4 Apr 2023 17:40:44 -0500 Subject: 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. --- pkg/cover/canonicalizer.go | 130 ++++++++++++++++++++++++++++++++++++ pkg/cover/canonicalizer_test.go | 144 ++++++++++++++++++++++++++++++++++++++++ pkg/host/machine_info.go | 1 + pkg/host/machine_info_linux.go | 9 ++- 4 files changed, 282 insertions(+), 2 deletions(-) create mode 100644 pkg/cover/canonicalizer.go create mode 100644 pkg/cover/canonicalizer_test.go (limited to 'pkg') 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 -- cgit mrf-deployment