Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

internal/fuzz: regression finding interesting inputs in simple tests #48179

Closed
stevenjohnstone opened this issue Sep 3, 2021 · 5 comments
Closed
Labels
FrozenDueToAge fuzz Issues related to native fuzzing support NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@stevenjohnstone
Copy link
Contributor

What version of Go are you using (go version)?

$ go version
go version devel go1.17-e5247f7886a Thu Sep 2 21:43:52 2021 +0000 linux/amd64

Does this issue reproduce with the latest release?

n/a

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/stevie/.cache/go-build"
GOENV="/home/stevie/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/stevie/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/stevie/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/stevie/sdk/gotip"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/stevie/sdk/gotip/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="devel go1.17-e5247f7886a Thu Sep 2 21:43:52 2021 +0000"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/stevie/code/coverbug/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build2198212895=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Ran tests from https://github.com/stevenjohnstone/go-beta-fuzzer-vs-libfuzzer. Specifically, the test "FuzzLoop" which started to pass for the beta fuzzer after commit 7b6893d has stopped working with commit 5bc273a.

The fuzzer runs indefinitely (well, several hours so far) without finding a crasher. Notably the "interesting" column remains at zero for the duration of the run.

What did you expect to see?

Prior to 5bc273a, this test case would end with the fuzzer finding a crasher with the "interesting" count increasing through the run.

What did you see instead?

Now, no crasher is found and the "interesting" count remains zero.

@stevenjohnstone
Copy link
Contributor Author

stevenjohnstone commented Sep 3, 2021

I was a bit blocked on investigating this by coverage not working for fuzzing runs: #48178.

I suspected that the fuzzer was making progress but nothing was being labelled as interesting. To give an idea of the coverage, I used bpftrace to instrument the function under test where the function returns (with offsets to RET instructions from the function address). This confirmed that the fuzzer generated an input which reached this line which I think qualifies as finding new coverage.

In a checkout of https://github.com/stevenjohnstone/go-beta-fuzzer-vs-libfuzzer, I built a test executable fuzztests.test with

gotip test -c -fuzz=FuzzLoop -coverprofile=cover.out

I then used my own hacky tool to generate a skeleton bpftrace program which ended up like this

// exit from github.com/stevenjohnstone/fuzztests.loopmagic
uprobe:/home/stevie/code/go/fuzztests.test:"github.com/stevenjohnstone/fuzztests.loopmagic" + 169 {
          @exit[169] = count();
}

// exit from github.com/stevenjohnstone/fuzztests.loopmagic
uprobe:/home/stevie/code/go/fuzztests.test:"github.com/stevenjohnstone/fuzztests.loopmagic" + 352 {
          @exit[352] = count();
}

// exit from github.com/stevenjohnstone/fuzztests.loopmagic
uprobe:/home/stevie/code/go/fuzztests.test:"github.com/stevenjohnstone/fuzztests.loopmagic" + 377 {
          @exit[377] = count();
}

This counts the exit points for loopmagic with 169 meaning the input wasn't length 4, 352 meaning the input didn't match the magic value and 377 means a match. I've attached the objdump output which shows the RET instructions at the offsets I've used , for completeness.

go tool objdump -s 'fuzztests.loopmagic' fuzztests.test
TEXT github.com/stevenjohnstone/fuzztests.loopmagic(SB) /home/stevie/code/go/magic.go
  magic.go:9		0x57abc0		493b6610		CMPQ 0x10(R14), SP										
  magic.go:9		0x57abc4		0f867c010000		JBE 0x57ad46											
  magic.go:9		0x57abca		4883ec38		SUBQ $0x38, SP											
  magic.go:9		0x57abce		48896c2430		MOVQ BP, 0x30(SP)										
  magic.go:9		0x57abd3		488d6c2430		LEAQ 0x30(SP), BP										
  magic.go:10		0x57abd8		48895c2448		MOVQ BX, 0x48(SP)										
  magic.go:15		0x57abdd		4889442440		MOVQ AX, 0x40(SP)										
  magic.go:6		0x57abe2		0fb60db1041b00		MOVZX 0x1b04b1(IP), CX										
  magic.go:6		0x57abe9		ffc1			INCL CX												
  magic.go:6		0x57abeb		880da9041b00		MOVB CL, 0x1b04a9(IP)										
  magic.go:9		0x57abf1		c705e9f4150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+4(SB)	
  magic.go:10		0x57abfb		b804000000		MOVL $0x4, AX											
  magic.go:10		0x57ac00		e85be8fcff		CALL runtime.libfuzzerTraceConstCmp8(SB)							
  magic.go:10		0x57ac05		488b4c2448		MOVQ 0x48(SP), CX										
  magic.go:10		0x57ac0a		4883f904		CMPQ $0x4, CX											
  magic.go:10		0x57ac0e		7535			JNE 0x57ac45											
  magic.go:10		0x57ac10		0fb61585041b00		MOVZX 0x1b0485(IP), DX										
  magic.go:10		0x57ac17		ffc2			INCL DX												
  magic.go:10		0x57ac19		88157d041b00		MOVB DL, 0x1b047d(IP)										
  magic.go:14		0x57ac1f		c705bff4150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+8(SB)	
  magic.go:14		0x57ac29		488b1da8141700		MOVQ github.com/stevenjohnstone/fuzztests.leet+8(SB), BX					
  magic.go:14		0x57ac30		48895c2420		MOVQ BX, 0x20(SP)										
  magic.go:14		0x57ac35		488b1594141700		MOVQ github.com/stevenjohnstone/fuzztests.leet(SB), DX						
  magic.go:14		0x57ac3c		4889542428		MOVQ DX, 0x28(SP)										
  magic.go:14		0x57ac41		31c0			XORL AX, AX											
  magic.go:14		0x57ac43		eb42			JMP 0x57ac87											
  magic.go:10		0x57ac45		0fb60d4f041b00		MOVZX 0x1b044f(IP), CX										
  magic.go:10		0x57ac4c		ffc1			INCL CX												
  magic.go:10		0x57ac4e		880d47041b00		MOVB CL, 0x1b0447(IP)										
  magic.go:10		0x57ac54		c70592f4150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+16(SB)	
  magic.go:11		0x57ac5e		31c0			XORL AX, AX											
  magic.go:11		0x57ac60		488b6c2430		MOVQ 0x30(SP), BP										
  magic.go:11		0x57ac65		4883c438		ADDQ $0x38, SP											
  magic.go:11		0x57ac69		c3			RET												
  magic.go:15		0x57ac6a		0fb60d18041b00		MOVZX 0x1b0418(IP), CX										
  magic.go:15		0x57ac71		ffc1			INCL CX												
  magic.go:15		0x57ac73		880d10041b00		MOVB CL, 0x1b0410(IP)										
  magic.go:14		0x57ac79		488b4c2418		MOVQ 0x18(SP), CX										
  magic.go:14		0x57ac7e		488d4101		LEAQ 0x1(CX), AX										
  magic.go:14		0x57ac82		488b5c2420		MOVQ 0x20(SP), BX										
  magic.go:14		0x57ac87		4889442418		MOVQ AX, 0x18(SP)										
  magic.go:14		0x57ac8c		e84fe7fcff		CALL runtime.libfuzzerTraceCmp8(SB)								
  magic.go:14		0x57ac91		488b442418		MOVQ 0x18(SP), AX										
  magic.go:14		0x57ac96		488b4c2420		MOVQ 0x20(SP), CX										
  magic.go:14		0x57ac9b		0f1f440000		NOPL 0(AX)(AX*1)										
  magic.go:14		0x57aca0		4839c8			CMPQ CX, AX											
  magic.go:14		0x57aca3		7d7c			JGE 0x57ad21											
  magic.go:14		0x57aca5		488b542428		MOVQ 0x28(SP), DX										
  magic.go:14		0x57acaa		0fb61c02		MOVZX 0(DX)(AX*1), BX										
  magic.go:14		0x57acae		0fb635e8031b00		MOVZX 0x1b03e8(IP), SI										
  magic.go:14		0x57acb5		ffc6			INCL SI												
  magic.go:14		0x57acb7		408835df031b00		MOVB SI, 0x1b03df(IP)										
  magic.go:14		0x57acbe		c7052cf4150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+20(SB)	
  magic.go:15		0x57acc8		488b742448		MOVQ 0x48(SP), SI										
  magic.go:15		0x57accd		4839c6			CMPQ AX, SI											
  magic.go:15		0x57acd0		7668			JBE 0x57ad3a											
  magic.go:14		0x57acd2		885c2416		MOVB BL, 0x16(SP)										
  magic.go:15		0x57acd6		488b4c2440		MOVQ 0x40(SP), CX										
  magic.go:15		0x57acdb		0fb61401		MOVZX 0(CX)(AX*1), DX										
  magic.go:15		0x57acdf		88542417		MOVB DL, 0x17(SP)										
  magic.go:15		0x57ace3		89d0			MOVL DX, AX											
  magic.go:15		0x57ace5		e896e6fcff		CALL runtime.libfuzzerTraceCmp1(SB)								
  magic.go:15		0x57acea		0fb64c2417		MOVZX 0x17(SP), CX										
  magic.go:15		0x57acef		0fb6542416		MOVZX 0x16(SP), DX										
  magic.go:15		0x57acf4		38d1			CMPL DL, CL											
  magic.go:15		0x57acf6		0f846effffff		JE 0x57ac6a											
  magic.go:15		0x57acfc		0fb60d85031b00		MOVZX 0x1b0385(IP), CX										
  magic.go:15		0x57ad03		ffc1			INCL CX												
  magic.go:15		0x57ad05		880d7d031b00		MOVB CL, 0x1b037d(IP)										
  magic.go:15		0x57ad0b		c705e3f3150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+24(SB)	
  magic.go:16		0x57ad15		31c0			XORL AX, AX											
  magic.go:16		0x57ad17		488b6c2430		MOVQ 0x30(SP), BP										
  magic.go:16		0x57ad1c		4883c438		ADDQ $0x38, SP											
  magic.go:16		0x57ad20		c3			RET												
  magic.go:19		0x57ad21		c705c1f3150001000000	MOVL $0x1, github.com/stevenjohnstone/fuzztests.GoCover_0_646331393033323261336366+12(SB)	
  magic.go:19		0x57ad2b		b801000000		MOVL $0x1, AX											
  magic.go:19		0x57ad30		488b6c2430		MOVQ 0x30(SP), BP										
  magic.go:19		0x57ad35		4883c438		ADDQ $0x38, SP											
  magic.go:19		0x57ad39		c3			RET												
  magic.go:15		0x57ad3a		4889f1			MOVQ SI, CX											
  magic.go:15		0x57ad3d		0f1f00			NOPL 0(AX)											
  magic.go:15		0x57ad40		e89bc6eeff		CALL runtime.panicIndex(SB)									
  magic.go:15		0x57ad45		90			NOPL												
  magic.go:9		0x57ad46		4889442408		MOVQ AX, 0x8(SP)										
  magic.go:9		0x57ad4b		48895c2410		MOVQ BX, 0x10(SP)										
  magic.go:9		0x57ad50		48894c2418		MOVQ CX, 0x18(SP)										
  magic.go:9		0x57ad55		e826a2eeff		CALL runtime.morestack_noctxt.abi0(SB)								
  magic.go:9		0x57ad5a		488b442408		MOVQ 0x8(SP), AX										
  magic.go:9		0x57ad5f		488b5c2410		MOVQ 0x10(SP), BX										
  magic.go:9		0x57ad64		488b4c2418		MOVQ 0x18(SP), CX										
  magic.go:9		0x57ad69		e952feffff		JMP github.com/stevenjohnstone/fuzztests.loopmagic(SB)

After tracing the fuzzer for a few seconds, the output was

@exit[352]: 29909
@exit[169]: 46724610

but the fuzzer displays

fuzzing, elapsed: 3.0s, execs: 332330 (110742/sec), workers: 8, interesting: 0
fuzzing, elapsed: 6.0s, execs: 677478 (112897/sec), workers: 8, interesting: 0
fuzzing, elapsed: 9.0s, execs: 989988 (109980/sec), workers: 8, interesting: 0
fuzzing, elapsed: 12.0s, execs: 1301831 (108477/sec), workers: 8, interesting: 0
fuzzing, elapsed: 15.0s, execs: 1639608 (109299/sec), workers: 8, interesting: 0
fuzzing, elapsed: 18.0s, execs: 1993935 (110766/sec), workers: 8, interesting: 0
fuzzing, elapsed: 21.0s, execs: 2348378 (111821/sec), workers: 8, interesting: 0
fuzzing, elapsed: 24.0s, execs: 2706682 (112775/sec), workers: 8, interesting: 0

I think the bpftrace output indicates that new coverage has been found. I think those should turn up in the "interesting" count displayed when fuzzing?

@cherrymui cherrymui added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 3, 2021
@cherrymui cherrymui added this to the Backlog milestone Sep 3, 2021
@cherrymui
Copy link
Member

cc @golang/fuzzing

@stevenjohnstone
Copy link
Contributor Author

Here's a simpler setup which doesn't need "unsafe" support in bpftrace.

I built a test executable in a checkout of https://github.com/stevenjohnstone/go-beta-fuzzer-vs-libfuzzer

gotip test -c -fuzz=FuzzLoop

This is the function under test

var leet = []byte{1, 3, 3, 7}

func loopmagic(input []byte) bool {
	if len(input) != 4 {
		return false
	}

	for i, v := range leet {
		if input[i] != v {
			return false
		}
	}
	return true
}

When loopmagic returns true, the test will end with a fatal error with a crasher []byte{1, 3, 3, 7}.

I wrote a bpftrace script which captures the slice input to loopmagic and records guesses which are the correct length and
keeps a record of how many match 1, 2, 3 or 4 bytes of []byte{1, 3, 3, 7}:

$ cat depth.bt
uprobe:/home/stevie/code/go/fuzztests.test:"github.com/stevenjohnstone/fuzztests.loopmagic"  {
        // func loopmagic(data []byte) bool
        // calling convention has slice data pointer in ax, len in bx and cap in cx
        $data = reg("ax");
        $len = reg("bx");

        @len = hist($len); // histogram of the slice lengths the fuzzer is trying

        if ($len == 4) {
          $a = *(uint8 *)($data);
          $b = *(uint8 *)($data + 1);
          $c = *(uint8 *)($data + 2);
          $d = *(uint8 *)($data + 3);

          if ($a == 1) {
            @depth[1] = count();
            if ($b == 3) {
              @depth[2] = count();
              if ($c == 3) {
                @depth[3] = count();
                if ($d == 7) {
                  // if we got here the fuzzer should exit
                  @depth[4] = count();
                  exit();
                }
              }
            }
          }
        }
}

I ran this with

sudo bpftrace depth.bt

Then run the fuzzer with

./fuzztests.test -test.run=^$ -test.fuzz=FuzzLoop -test.fuzzcachedir=./cache

Fuzzer says there's no interesting input:

fuzzing, elapsed: 591.0s, execs: 68572276 (116027/sec), workers: 8, interesting: 0
fuzzing, elapsed: 594.0s, execs: 68907698 (116006/sec), workers: 8, interesting: 0
fuzzing, elapsed: 597.0s, execs: 69243662 (115986/sec), workers: 8, interesting: 0
fuzzing, elapsed: 600.0s, execs: 69580536 (115967/sec), workers: 8, interesting: 0
fuzzing, elapsed: 603.0s, execs: 69903837 (115927/sec), workers: 8, interesting: 0
fuzzing, elapsed: 606.0s, execs: 70240967 (115909/sec), workers: 8, interesting: 0
^Cfuzzing, elapsed: 608.5s, execs: 70533725 (115906/sec), workers: 8, interesting: 0
PASS

However, the bpftrace script output suggests that the fuzzer has guessed 6 slices of length 4 matching the first two bytes:

@depth[2]: 6
@depth[1]: 552
@len: 
[0]                10974 |                                                    |
[1]                51852 |                                                    |
[2, 4)            134611 |                                                    |
[4, 8)            170252 |                                                    |
[8, 16)           320473 |@                                                   |
[16, 32)          580568 |@                                                   |
[32, 64)         1110985 |@@@                                                 |
[64, 128)        2040969 |@@@@@@                                              |
[128, 256)       3535660 |@@@@@@@@@@@@                                        |
[256, 512)       5578225 |@@@@@@@@@@@@@@@@@@@                                 |
[512, 1K)        8327420 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@                        |
[1K, 2K)        12171563 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@           |
[2K, 4K)        15215898 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[4K, 8K)        15195794 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[8K, 16K)        5166501 |@@@@@@@@@@@@@@@@@                                   |
[16K, 32K)        424977 |@                                                   |
[32K, 64K)         13997 |                                                    |
[64K, 128K)          255 |                                                    |


Going twice around the loop in loopmagic should be an interesting input as it expands coverage? Even getting past

	if len(input) != 4 {
		return false
	}

(552 times) is interesting coverage?

@jayconrod jayconrod changed the title [dev.fuzz] regression in simple tests [dev.fuzz] internal/fuzz: regression finding interesting inputs in simple tests Sep 8, 2021
@jayconrod jayconrod added the fuzz Issues related to native fuzzing support label Sep 8, 2021
@rsc rsc changed the title [dev.fuzz] internal/fuzz: regression finding interesting inputs in simple tests internal/fuzz: regression finding interesting inputs in simple tests Sep 21, 2021
@stevenjohnstone
Copy link
Contributor Author

@rolandshoemaker the tests at https://github.com/stevenjohnstone/go-beta-fuzzer-vs-libfuzzer now complete in under a second when I use gotip from https://go-review.googlesource.com/c/go/+/364214/ (#49601) 👍

@gopherbot
Copy link

Change https://golang.org/cl/364214 mentions this issue: internal/fuzz: limit number of consecutive mutations

@dmitshur dmitshur added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Nov 18, 2021
@dmitshur dmitshur modified the milestones: Backlog, Go1.18 Nov 18, 2021
@golang golang locked and limited conversation to collaborators Nov 18, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge fuzz Issues related to native fuzzing support NeedsFix The path to resolution is known, but the work has not been done.
Projects
Status: No status
Development

No branches or pull requests

5 participants