[go] cmd/compile: support libFuzzer value profiling mode for integer compares

Gerrit Bot (Gerrit)

unread,

Feb 22, 2022, 12:33:54 PM2/22/22

to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com

Gerrit Bot has uploaded this change for review.

cmd/compile: support libFuzzer value profiling mode for integer compares

libFuzzer provides a special mode known as “value profiling” in which it
tracks the bit-wise progress made by the fuzzer in satisfying tracked
comparisons. Furthermore, libFuzzer uses the value of the return address
in its hooks to distinguish the progress for different comparisons.

The original implementation of the interception for integer comparisons
in Go simply called the libFuzzer hooks from a function written in Go
assembly. The libFuzzer hooks thus always see the same return address
(i.e., the address of the call instruction in the assembly snippet) and
thus can’t distinguish individual comparisons anymore. This drastically
reduces the usefulness of value profiling.

This is fixed by using an assembly trampoline that injects synthetic but
valid return addresses on the stack before calling the libFuzzer hook,
otherwise preserving the calling convention of the respective platform
(for starters, x86_64 Windows or Unix). These fake PCs are generated
deterministically based on the location of the compare instruction in
the IR representation.

Change-Id: Iea68057c83aea7f9dc226fba7128708e8637d07a
GitHub-Last-Rev: 7863abdfa3ce04ca8cfef8bed8f97c39d9dcdeb1
GitHub-Pull-Request: golang/go#51321
---
M src/cmd/compile/internal/typecheck/builtin.go
M src/cmd/compile/internal/typecheck/builtin/runtime.go
M src/cmd/compile/internal/walk/compare.go
M src/internal/fuzz/trace.go
M src/runtime/libfuzzer.go
M src/runtime/libfuzzer_amd64.s
6 files changed, 169 insertions(+), 42 deletions(-)

diff --git a/src/cmd/compile/internal/typecheck/builtin.go b/src/cmd/compile/internal/typecheck/builtin.go
index 67597ce..08f8e39 100644
--- a/src/cmd/compile/internal/typecheck/builtin.go
+++ b/src/cmd/compile/internal/typecheck/builtin.go
@@ -372,9 +372,9 @@
 	typs[142] = newSig(params(typs[7], typs[1], typs[5]), nil)
 	typs[143] = types.NewSlice(typs[7])
 	typs[144] = newSig(params(typs[7], typs[143]), nil)
-	typs[145] = newSig(params(typs[66], typs[66]), nil)
-	typs[146] = newSig(params(typs[60], typs[60]), nil)
-	typs[147] = newSig(params(typs[62], typs[62]), nil)
-	typs[148] = newSig(params(typs[24], typs[24]), nil)
+	typs[145] = newSig(params(typs[66], typs[66], typs[15]), nil)
+	typs[146] = newSig(params(typs[60], typs[60], typs[15]), nil)
+	typs[147] = newSig(params(typs[62], typs[62], typs[15]), nil)
+	typs[148] = newSig(params(typs[24], typs[24], typs[15]), nil)
 	return typs[:]
 }
diff --git a/src/cmd/compile/internal/typecheck/builtin/runtime.go b/src/cmd/compile/internal/typecheck/builtin/runtime.go
index 04ae4f2..fe861c5 100644
--- a/src/cmd/compile/internal/typecheck/builtin/runtime.go
+++ b/src/cmd/compile/internal/typecheck/builtin/runtime.go
@@ -257,14 +257,14 @@
 func checkptrAlignment(unsafe.Pointer, *byte, uintptr)
 func checkptrArithmetic(unsafe.Pointer, []unsafe.Pointer)
 
-func libfuzzerTraceCmp1(uint8, uint8)
-func libfuzzerTraceCmp2(uint16, uint16)
-func libfuzzerTraceCmp4(uint32, uint32)
-func libfuzzerTraceCmp8(uint64, uint64)
-func libfuzzerTraceConstCmp1(uint8, uint8)
-func libfuzzerTraceConstCmp2(uint16, uint16)
-func libfuzzerTraceConstCmp4(uint32, uint32)
-func libfuzzerTraceConstCmp8(uint64, uint64)
+func libfuzzerTraceCmp1(uint8, uint8, int)
+func libfuzzerTraceCmp2(uint16, uint16, int)
+func libfuzzerTraceCmp4(uint32, uint32, int)
+func libfuzzerTraceCmp8(uint64, uint64, int)
+func libfuzzerTraceConstCmp1(uint8, uint8, int)
+func libfuzzerTraceConstCmp2(uint16, uint16, int)
+func libfuzzerTraceConstCmp4(uint32, uint32, int)
+func libfuzzerTraceConstCmp8(uint64, uint64, int)
 
 // architecture variants
 var x86HasPOPCNT bool
diff --git a/src/cmd/compile/internal/walk/compare.go b/src/cmd/compile/internal/walk/compare.go
index 625e216..2ecbf06 100644
--- a/src/cmd/compile/internal/walk/compare.go
+++ b/src/cmd/compile/internal/walk/compare.go
@@ -5,7 +5,11 @@
 package walk
 
 import (
+	"encoding/binary"
+	"fmt"
 	"go/constant"
+	"hash/fnv"
+	"io"
 
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/ir"
@@ -15,6 +19,22 @@
 	"cmd/compile/internal/types"
 )
 
+func fakePC(n ir.Node) ir.Node {
+	// In order to get deterministic IDs, we include the package path, file index, line number, column number
+	// in the calculation of the fakePC for the IR node.
+	hash := fnv.New32()
+	// We ignore the errors here because the `io.Writer` in the `hash.Hash` interface never returns an error.
+	_, _ = io.WriteString(hash, base.Ctxt.Pkgpath)
+	_ = binary.Write(hash, binary.LittleEndian, n.Pos().FileIndex())
+	_ = binary.Write(hash, binary.LittleEndian, int64(n.Pos().Line()))
+	_ = binary.Write(hash, binary.LittleEndian, int64(n.Pos().Col()))
+	// We also include the string representation of the node to distinguish autogenerated expression since
+	// those get the same `src.XPos`
+	_, _ = io.WriteString(hash, fmt.Sprintf("%v", n))
+
+	return ir.NewInt(int64(hash.Sum32()))
+}
+
 // The result of walkCompare MUST be assigned back to n, e.g.
 // 	n.Left = walkCompare(n.Left, init)
 func walkCompare(n *ir.BinaryExpr, init *ir.Nodes) ir.Node {
@@ -131,7 +151,7 @@
 			default:
 				base.Fatalf("unexpected integer size %d for %v", t.Size(), t)
 			}
-			init.Append(mkcall(fn, nil, init, tracecmpArg(l, paramType, init), tracecmpArg(r, paramType, init)))
+			init.Append(mkcall(fn, nil, init, tracecmpArg(l, paramType, init), tracecmpArg(r, paramType, init), fakePC(n)))
 		}
 		return n
 	case types.TARRAY:
diff --git a/src/internal/fuzz/trace.go b/src/internal/fuzz/trace.go
index cab0838..8384b23 100644
--- a/src/internal/fuzz/trace.go
+++ b/src/internal/fuzz/trace.go
@@ -18,12 +18,12 @@
 //go:linkname libfuzzerTraceConstCmp4 runtime.libfuzzerTraceConstCmp4
 //go:linkname libfuzzerTraceConstCmp8 runtime.libfuzzerTraceConstCmp8
 
-func libfuzzerTraceCmp1(arg0, arg1 uint8)  {}
-func libfuzzerTraceCmp2(arg0, arg1 uint16) {}
-func libfuzzerTraceCmp4(arg0, arg1 uint32) {}
-func libfuzzerTraceCmp8(arg0, arg1 uint64) {}
+func libfuzzerTraceCmp1(arg0, arg1 uint8, fakePC int)  {}
+func libfuzzerTraceCmp2(arg0, arg1 uint16, fakePC int) {}
+func libfuzzerTraceCmp4(arg0, arg1 uint32, fakePC int) {}
+func libfuzzerTraceCmp8(arg0, arg1 uint64, fakePC int) {}
 
-func libfuzzerTraceConstCmp1(arg0, arg1 uint8)  {}
-func libfuzzerTraceConstCmp2(arg0, arg1 uint16) {}
-func libfuzzerTraceConstCmp4(arg0, arg1 uint32) {}
-func libfuzzerTraceConstCmp8(arg0, arg1 uint64) {}
+func libfuzzerTraceConstCmp1(arg0, arg1 uint8, fakePC int)  {}
+func libfuzzerTraceConstCmp2(arg0, arg1 uint16, fakePC int) {}
+func libfuzzerTraceConstCmp4(arg0, arg1 uint32, fakePC int) {}
+func libfuzzerTraceConstCmp8(arg0, arg1 uint64, fakePC int) {}
diff --git a/src/runtime/libfuzzer.go b/src/runtime/libfuzzer.go
index e7b3cdc..0ea3632 100644
--- a/src/runtime/libfuzzer.go
+++ b/src/runtime/libfuzzer.go
@@ -8,38 +8,49 @@
 
 import _ "unsafe" // for go:linkname
 
-func libfuzzerCall(fn *byte, arg0, arg1 uintptr)
+// Keep in sync with the definition of ret_sled in src/runtime/libfuzzer_amd64.s
+const retSledSize = 512
 
-func libfuzzerTraceCmp1(arg0, arg1 uint8) {
-	libfuzzerCall(&__sanitizer_cov_trace_cmp1, uintptr(arg0), uintptr(arg1))
+func libfuzzerCallTraceIntCmp(fn *byte, arg0, arg1, fakePC uintptr)
+
+func libfuzzerTraceCmp1(arg0, arg1 uint8, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_cmp1, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceCmp2(arg0, arg1 uint16) {
-	libfuzzerCall(&__sanitizer_cov_trace_cmp2, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceCmp2(arg0, arg1 uint16, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_cmp2, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceCmp4(arg0, arg1 uint32) {
-	libfuzzerCall(&__sanitizer_cov_trace_cmp4, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceCmp4(arg0, arg1 uint32, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_cmp4, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceCmp8(arg0, arg1 uint64) {
-	libfuzzerCall(&__sanitizer_cov_trace_cmp8, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceCmp8(arg0, arg1 uint64, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_cmp8, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceConstCmp1(arg0, arg1 uint8) {
-	libfuzzerCall(&__sanitizer_cov_trace_const_cmp1, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceConstCmp1(arg0, arg1 uint8, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_const_cmp1, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceConstCmp2(arg0, arg1 uint16) {
-	libfuzzerCall(&__sanitizer_cov_trace_const_cmp2, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceConstCmp2(arg0, arg1 uint16, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_const_cmp2, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceConstCmp4(arg0, arg1 uint32) {
-	libfuzzerCall(&__sanitizer_cov_trace_const_cmp4, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceConstCmp4(arg0, arg1 uint32, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_const_cmp4, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
-func libfuzzerTraceConstCmp8(arg0, arg1 uint64) {
-	libfuzzerCall(&__sanitizer_cov_trace_const_cmp8, uintptr(arg0), uintptr(arg1))
+func libfuzzerTraceConstCmp8(arg0, arg1 uint64, fakePC int) {
+	fakePC = fakePC % retSledSize
+	libfuzzerCallTraceIntCmp(&__sanitizer_cov_trace_const_cmp8, uintptr(arg0), uintptr(arg1), uintptr(fakePC))
 }
 
 //go:linkname __sanitizer_cov_trace_cmp1 __sanitizer_cov_trace_cmp1
diff --git a/src/runtime/libfuzzer_amd64.s b/src/runtime/libfuzzer_amd64.s
index 253fe15..1f21774 100644
--- a/src/runtime/libfuzzer_amd64.s
+++ b/src/runtime/libfuzzer_amd64.s
@@ -13,17 +13,47 @@
 #ifdef GOOS_windows
 #define RARG0 CX
 #define RARG1 DX
+#define RARG0 R8
+#define RARG1 R9
 #else
 #define RARG0 DI
 #define RARG1 SI
+#define RARG2 DX
+#define RARG3 CX
 #endif
 
-// void runtime·libfuzzerCall(fn, arg0, arg1 uintptr)
-// Calls C function fn from libFuzzer and passes 2 arguments to it.
-TEXT	runtime·libfuzzerCall(SB), NOSPLIT, $0-24
+// void runtime·libfuzzerCallTraceIntCmp(fn, arg0, arg1, fakePC uintptr)
+// Calls C function fn from libFuzzer and passes 2 arguments to it after
+// manipulating the return address so that libfuzzer's interger compare hooks
+// work
+// libFuzzer's compare hooks obtain the caller's address from the compiler
+// builtin __builtin_return_adress. Since we invoke the hooks always
+// from the same native function, this builtin would always return the same
+// value. Internally, the libFuzzer hooks call through to the always inlined
+// HandleCmp and thus can't be mimicked without patching libFuzzer.
+//
+// We solve this problem via an inline assembly trampoline construction that
+// translates a runtime argument `fake_pc` in the range [0, 512) into a call to
+// a hook with a fake return address whose lower 9 bits are `fake_pc` up to a
+// constant shift. This is achieved by pushing a return address pointing into
+// 512 ret instructions at offset `fake_pc` onto the stack and then jumping
+// directly to the address of the hook.
+//
+// Note: We only set the lowest 9 bits of the return address since only these
+// bits are used by the libFuzzer value profiling mode for integer compares, see
+// https://github.com/llvm/llvm-project/blob/704d92607d26e696daba596b72cb70effe79a872/compiler-rt/lib/fuzzer/FuzzerTracePC.cpp#L390
+// as well as
+// https://github.com/llvm/llvm-project/blob/704d92607d26e696daba596b72cb70effe79a872/compiler-rt/lib/fuzzer/FuzzerValueBitMap.h#L34
+// ValueProfileMap.AddValue() truncates its argument to 16 bits and shifts the
+// PC to the left by log_2(128)=7, which means that only the lowest 16 - 7 bits
+// of the return address matter. String compare hooks use the lowest 12 bits,
+// but take the return address as an argument and thus don't require the
+// indirection through a trampoline.
+TEXT	runtime·libfuzzerCallTraceIntCmp(SB), NOSPLIT, $0-32
 	MOVQ	fn+0(FP), AX
 	MOVQ	arg0+8(FP), RARG0
 	MOVQ	arg1+16(FP), RARG1
+	MOVQ	fakePC+24(FP), RARG2
 
 	get_tls(R12)
 	MOVQ	g(R12), R14
@@ -37,6 +67,42 @@
 	MOVQ	(g_sched+gobuf_sp)(R10), SP
 call:
 	ANDQ	$~15, SP	// alignment for gcc ABI
-	CALL	AX
+	// Load the address of the end of the function and push it into the stack.
+	// This address will be jumped to after executing the return instruction
+	// from the return sled. There we reset the stack pointer and return.
+	MOVQ    $end_of_function(SB), BX
+	PUSHQ   BX
+	// Load the starting address of the return sled into BX.
+	MOVQ    $ret_sled(SB), BX
+	// Load the address of the i'th return instruction fron the return sled.
+	// The index is given in the fakePC argument.
+	ADDQ    RARG2, BX
+	PUSHQ   BX
+	// Call the original function with the fakePC return address on the stack.
+	// Function arguments arg0 and arg1 are passed unchanged in the registers
+	// RDI and RSI as specified by the x64 calling convention.
+	JMP     AX
+// This code will not be executed and is only there to statisfy assembler
+// check of a balanced stack.
+not_reachable:
+	POPQ    BX
+	POPQ    BX
+	RET
+
+TEXT end_of_function(SB), NOSPLIT, $0-0
 	MOVQ	R12, SP
 	RET
+
+#define REPEAT_8(a) a \
+  a \
+  a \
+  a \
+  a \
+  a \
+  a \
+  a
+
+#define REPEAT_512(a) REPEAT_8(REPEAT_8(REPEAT_8(a)))
+
+TEXT ret_sled(SB), NOSPLIT, $0-0
+	REPEAT_512(RET)

To view, visit change 387336. To unsubscribe, or for help writing mail filters, visit settings.

Keith Randall (Gerrit)

unread,

Mar 1, 2022, 6:50:49 PM3/1/22

to Gerrit Bot, goph...@pubsubhelper.golang.org, Robert Griesemer, Katie Hockman, Roland Shoemaker, Austin Clements, Keith Randall, Michael Knyszek, Michael Pratt, Ian Lance Taylor, Dmitry Vyukov, Martin Möhrmann, Josh Bleecher Snyder, Matthew Dempsky, Gopher Robot, golang-co...@googlegroups.com

Attention is currently required from: Austin Clements, Michael Knyszek, Michael Pratt, Robert Griesemer, Katie Hockman, Roland Shoemaker.

[go] cmd/compile: support libFuzzer value profiling mode for integer compares

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Gerrit Bot (Gerrit)

Khaled Yakdan (Gerrit)

Keith Randall (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Khaled Yakdan (Gerrit)

Keith Randall (Gerrit)

Ian Lance Taylor (Gerrit)

Gerrit Bot (Gerrit)

Cherry Mui (Gerrit)

Khaled Yakdan (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Keith Randall (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Keith Randall (Gerrit)

Ian Lance Taylor (Gerrit)

Gerrit Bot (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Cherry Mui (Gerrit)

Cherry Mui (Gerrit)

Gerrit Bot (Gerrit)

Khaled Yakdan (Gerrit)

Cherry Mui (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Keith Randall (Gerrit)

Michael Knyszek (Gerrit)

Gerrit Bot (Gerrit)

Gerrit Bot (Gerrit)

Keith Randall (Gerrit)

Keith Randall (Gerrit)

Khaled Yakdan (Gerrit)

Gerrit Bot (Gerrit)

Gerrit Bot (Gerrit)

Khaled Yakdan (Gerrit)

Keith Randall (Gerrit)

Keith Randall (Gerrit)

Cherry Mui (Gerrit)

Khaled Yakdan (Gerrit)

Cherry Mui (Gerrit)

Khaled Yakdan (Gerrit)

Austin Clements (Gerrit)

Khaled Yakdan (Gerrit)