Improving the state of go-fuzz
By Christian Presa Schnell
During my winternship, I used the findings from recent Go audits to make several improvements to go-fuzz, a coverage-based fuzzer for projects written in Go. I focused on three enhancements to improve the effectiveness of Go fuzzing campaigns and provide a better experience for users. I contributed to fixing type alias issues, integrating dictionary support, and developing new mutation strategies.
What is go-fuzz?
go-fuzz finds software bugs by providing random input to a program and monitoring it for errors. It consists of two main components: go-fuzz and go-fuzz-build. The go-fuzz-build component is responsible for the source code instrumentation. And once the source code of the target program is instrumented, the code is compiled and the binary is then used by go-fuzz for the fuzzing campaign.
A user first instruments the source code to the tool, allowing for information, such as the coverage at runtime, to be extracted. Then, go-fuzz executes the program with a given set of inputs that are mutated with each interaction as it tries to increase coverage and trigger unexpected behaviors that lead to crashes. The harness, also provided by the user, is the fuzzing entry point and calls the function to be fuzzed. It returns a value to go-fuzz indicating whether the input should be dropped or promoted within the input corpus.
go-fuzz has been very successful in discovering new bugs, and the tool has helped find more than 200 bugs that are highlighted on GitHub and many more during Trail of Bits audits.
Instrumentation with type aliases
My first task was to investigate the root cause of a bug that crashed go-fuzz and propose a fix for it. In particular, the crash error we obtained was undefined: fs in fs.FileMode. A more detailed description of the bug can be found in issue dvyukov/go-fuzz#325.
This bug occurs only with Go version 1.16 and higher and when interacting with the file system via the os package rather than with fs. As many projects interact with the file system, this issue is of great importance, and therefore, the improvements I proposed are essential to increasing go-fuzz’s usability.
Even though there’s a workaround for this bug, it is still necessary to modify the code by adding statements using the fs package. This is not an ideal solution, since it requires one to manually modify the code, which may influence the fuzzing harness.
Another way of solving the problem is to simply use Go version 1.15. However, this is also problematic, since it is not always possible to run the project that we want to fuzz with a lower version of Go. Therefore, we wanted to find a thorough solution that would not require these constraints.
The error didn’t point to the root cause of the crash, so we needed to perform a detailed analysis.
Bug reproduction
I developed a minimal program that crashes go-fuzz-build based on the GitHub issue. The function that caused the bug, which is called HomeDir below, gets the stats for a file and checks whether the permission for the file and the current user is writable.
package homedir
import (
"os"
"fmt"
)
func HomeDir() {
p := "text.txt"
info, _ := os.Stat(p)
if info.Mode().Perm()&(1<<(uint(7))) & 1 != 0 {
fmt.Println("test")
}
}
To successfully instrument the program with go-fuzz-build, we needed to provide a fuzzing harness. Since we simply wanted to instrument the program, the harness did not require the HomeDir function to be invoked. So I implemented the harness in another file but in the same package as the HomeDir function so that the function could be instrumented without being called, allowing us to investigate the issue.
package homedir
func Fuzz(data []byte) int {
return 1
}
After looking at this code, the cause of the go-fuzz-build crash seemed even more confusing. The crash was related to the fs package, but the fs package was not used in the program:
failed to execute go build: exit status 2 homedir.go:13: undefined: fs in fs.FileMode
Bug triage
Interestingly, this bug was not introduced by a particular commit to go-fuzz, but it appeared when go-fuzz was used with a Go version of 1.16 and higher, which means that some change from Go version 1.15 to 1.16 had to be the reason for this issue.
Since the crash occurred when compiling the instrumented source code, figuring out where go-fuzz-build crashed was easy. The instrumentation was somehow faulty and produced non-valid code.
//line homedir.go:1
package homedir
//line homedir.go:1
import (
//line homedir.go:1
_go_fuzz_dep_ "go-fuzz-dep"
//line homedir.go:1
)
import (
"os"
"fmt"
)
//line homedir.go:8
func HomeDir() {
//line homedir.go:8
_go_fuzz_dep_.CoverTab[20570]++
p := "text.txt"
info, _ := os.Stat(p)
//line homedir.go:13
if func() _go_fuzz_dep_.Bool {
//line homedir.go:13
__gofuzz_v1 := fs.FileMode(info.Mode().Perm() & (1 << 7))
//line homedir.go:13
_go_fuzz_dep_.Sonar(__gofuzz_v1, 0, 725889)
//line homedir.go:13
return __gofuzz_v1 != 0
//line homedir.go:14
}() == true {
//line homedir.go:14
_go_fuzz_dep_.CoverTab[5104]++
fmt.Println("test")
} else {
//line homedir.go:14
_go_fuzz_dep_.CoverTab[24525]++
//line homedir.go:14
}
//line homedir.go:14
}
//line homedir.go:15
var _ = _go_fuzz_dep_.CoverTab
Root cause analysis
The expression in line 13 of the original program, (info.Mode().Perm() & (1 << 7)), is explicitly converted to the fs.FileMode type. This type conversion is one of the modifications performed by the instrumentation. The type conversion is correct by itself, since the info.Mode().Perm() has the type fs.FileMode. The real problem is that while the fs package is used, there lacks an import for it. Therefore, the compiler cannot resolve the type conversion, and the compilation fails.
However, this does not answer the question of why go-fuzz-build crashes in Go version 1.16 and up and not in lower versions. We found the answer to this question by looking at the differences between 1.15 and 1.16: the FileMode type in the os package changed from type FileMode uint32 in Go 1.15 to type FileMode = fs.FileMode in Go 1.16.
Essentially, the FileMode type changed from a type definition with the underlying uint32 type to a type alias with a type target defined in the fs package. A type alias does not create a new type. Instead, it just defines a new name for the original type. For this reason, the typechecker used by go-fuzz-build identifies fs.FileMode as the type that should be used for the type conversion instead of the type alias defined in the os package. This should not be an issue if the type alias and the original type are in the same package, but if there are multiple packages, the corresponding import statements should be added to the instrumented code.
Proposed fix
Ideally, a fix for this issue should be future-proof. While it is possible to hard-code the case of the fs.FileMode, this is not sufficient since other type aliases might be introduced in future versions of Go or in external packages used by the fuzzed code, so more fixes would be required. My proposed fix addresses this problem.
The fix I proposed consists of the following steps. First, analyze the typechecker output for every instrumented file for types that are defined in non-imported packages. If such a type exists, an import statement will be added with the corresponding package. However, there might be cases in which such a type exists but the instrumentation does not use it to perform a type conversion. That would render the import statement that was added to an unused import, and consequently, the compiler would refuse to compile the code. Therefore, it is essential to remove the unused added imports. For that purpose, goimports, a program that optimizes imports, will be executed before compilation. Then, the compilation succeeds.
Because the initializer is imported by the package in which the alias is defined, the package is guaranteed to execute only once. Therefore, we don’t have to worry about the import statement changing the semantics of the source code.
Dictionary support
The mutation engines of general-purpose fuzzers are designed to be very effective when mutating binary data formats, such as images or compressed data. However, general-purpose fuzzers don't perform very well when mutating inputs for syntax-aware programs, as they will accept only inputs that are valid for the underlying grammar. Common examples for such targets are programs that parse human-readable data formats like languages (SQL) or text-based protocols (HTTP, FTP).
Most of the time, in order to achieve good results with such human-readable targets, you have to build a custom mutation engine that adheres to the syntax, which is complex and time-consuming.
Another approach is to use fuzzing dictionaries. Fuzzing dictionaries are a collection of interesting keywords that are relevant for the required syntax. This approach allows a general-purpose mutation engine to insert keywords into the input at random positions. This gives the fuzzer more valid inputs than it would get with mutations on the bytes.
Up to this point, go-fuzz’s mutation engine generated a list of keywords using a technique called “token capture” and inserted these keywords into the mutated inputs. This technique extracts interesting strings directly from the instrumented code by looking for hard-coded values. The reasoning behind this approach is that if the input requires a certain syntax, there would be hard-coded statements within the program that check the validity of the input. While token capturing is correct, it has an important drawback: not only are the relevant keywords extracted, but so are keywords that are irrelevant to the input, such as log message strings. This is problematic, since adding noise to the string list reduces the fuzzer’s overall effectiveness.
A different approach is to let the user provide dictionaries containing interesting keywords relevant for the specific syntax used by the targeted program. I proposed a modification that allows one to pass a -dict parameter to go-fuzz and to provide a dictionary file containing the keywords (in the AFL/libFuzzer format) and a level parameter to provide more fine-grained control over the tokens in the dictionary file.
The following example illustrates the syntax of a token dictionary for SQL:
false] function_abs=" abs(1)" function_avg=" avg(1)" function_changes=" changes()" function_char=" char(1)" function_coalesce=" coalesce(1,1)" function_count=" count(1)" function_date=" date(1,1,1)" (...) keyword_ADD="ADD" keyword_AFTER="AFTER" keyword_ALL="ALL" keyword_ALTER="ALTER" keyword_ANALYZE="ANALYZE" keyword_AND="AND" (...)
By adopting the same syntax for the dictionaries used by AFL and libFuzzer, we can reuse preexisting dictionaries containing important keywords for specific fuzzing targets without having to redefine the keywords in a new format.
New mutation strategies
A fuzzer’s effectiveness depends on the quality of its mutation algorithms and whether they lead to more diverse inputs and increased code coverage. To this effect, I developed three new mutation strategies for go-fuzz.
Insert repeated bytes
This strategy mutates the fuzzer’s previous input by inserting a random byte that is repeated a random number of times. This is a variation of the insert random bytes strategy from libFuzzer that increases the likelihood of a situation in which certain bytes are repeated.
Shuffle bytes
Another mutation strategy inspired by libFuzzer, shuffle bytes selects a random subpart of the input with a random length and shuffles it using the Fisher-Yates shuffling algorithm.
Little endian base 128
Last but not least, I improved the InsertLiteral mutation strategy by implementing the little endian base 128 (LEB128) encoding. Similar to the process of inserting string literals discussed in the section on dictionaries above, with this improved strategy, the mutation engine scans the source code for hard-coded integer values and inserts them into the input to mutate it.
Inserting strings into the input is straightforward, as strings have a direct byte representation. This is not the case for integer values, since there are multiple formats to store the values in bytes depending on the length of the integer (8, 16, 32, and 64 bits) and on the endianness on which the integer is stored, either little endian or big endian. For this reason, the mutation engine needs to be able to insert the integer literals in different formats, since they might be used by the fuzzed program.
LEB128 is a variable-length encoding algorithm that is able to store integers by using very few bytes. In particular, LEB128 can store small integer values without leading zero bytes as well as arbitrarily big integers. Additionally, there are two different variants of the LEB128 encoding that have to be implemented separately: unsigned LEB128 and signed LEB128.
Because of its efficiency, this encoding is very popular and is used in many projects, like LLVM, DWARF, and Android DEX. Therefore, go-fuzz’s support of it is very useful.
The future of go-fuzz
The recent release of Go version 1.18 introduced first-party support for fuzzing. Hence, go-fuzz has reached the end of its life and future improvements will most likely be limited to bug fixes. Nonetheless, enhancing go-fuzz is still useful, as it is a well-known solution with an ecosystem of helpful tools, like trailofbits/go-fuzz-utils, and it may still be used in older projects.
I hope that the proposed improvements will be adopted upstream into go-fuzz so that everyone can benefit from them to discover and fix new bugs. Even though Go’s new built-in fuzzer will gain popularity due to its ease of use, we hope that Go developers will continue to draw inspiration from go-fuzz, which has been a huge success so far. It will certainly be interesting to see what the future holds for the fuzzing of Go projects.
I am very grateful for the opportunity to have worked as an intern at Trail of Bits and on the go-fuzz project—it was a great learning experience. I would like to thank my mentors, Dominik Czarnota and Rory Mackie, for their guidance and support.
*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored by Trail of Bits. Read the original post at: https://blog.trailofbits.com/2022/04/26/improving-the-state-of-go-fuzz/
