From a632c00b0d023b8a40d09839fbb2662da1cb5d37 Mon Sep 17 00:00:00 2001 From: van Hauser Date: Fri, 12 Jun 2020 16:08:49 +0200 Subject: switch to faster and better hash + random --- src/afl-performance.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 135 insertions(+) create mode 100644 src/afl-performance.c (limited to 'src/afl-performance.c') diff --git a/src/afl-performance.c b/src/afl-performance.c new file mode 100644 index 00000000..a2eca8c9 --- /dev/null +++ b/src/afl-performance.c @@ -0,0 +1,135 @@ +/* Written in 2019 by David Blackman and Sebastiano Vigna (vigna@acm.org) + +To the extent possible under law, the author has dedicated all copyright +and related and neighboring rights to this software to the public domain +worldwide. This software is distributed without any warranty. + +See . + + This is xoshiro256++ 1.0, one of our all-purpose, rock-solid generators. + It has excellent (sub-ns) speed, a state (256 bits) that is large + enough for any parallel application, and it passes all tests we are + aware of. + + For generating just floating-point numbers, xoshiro256+ is even faster. + + The state must be seeded so that it is not everywhere zero. If you have + a 64-bit seed, we suggest to seed a splitmix64 generator and use its + output to fill s. */ + +#include +#include "afl-fuzz.h" +#include "types.h" +#include "xxh3.h" + +static inline uint64_t rotl(const uint64_t x, int k) { + + return (x << k) | (x >> (64 - k)); + +} + +uint64_t rand_next(afl_state_t *afl) { + + const uint64_t result = + rotl(afl->rand_seed[0] + afl->rand_seed[3], 23) + afl->rand_seed[0]; + + const uint64_t t = afl->rand_seed[1] << 17; + + afl->rand_seed[2] ^= afl->rand_seed[0]; + afl->rand_seed[3] ^= afl->rand_seed[1]; + afl->rand_seed[1] ^= afl->rand_seed[2]; + afl->rand_seed[0] ^= afl->rand_seed[3]; + + afl->rand_seed[2] ^= t; + + afl->rand_seed[3] = rotl(afl->rand_seed[3], 45); + + return result; + +} + +/* This is the jump function for the generator. It is equivalent + to 2^128 calls to rand_next(); it can be used to generate 2^128 + non-overlapping subsequences for parallel computations. */ + +void jump(afl_state_t *afl) { + + static const uint64_t JUMP[] = {0x180ec6d33cfd0aba, 0xd5a61266f0c9392c, + 0xa9582618e03fc9aa, 0x39abdc4529b1661c}; + + uint64_t s0 = 0; + uint64_t s1 = 0; + uint64_t s2 = 0; + uint64_t s3 = 0; + for (int i = 0; i < sizeof JUMP / sizeof *JUMP; i++) + for (int b = 0; b < 64; b++) { + + if (JUMP[i] & UINT64_C(1) << b) { + + s0 ^= afl->rand_seed[0]; + s1 ^= afl->rand_seed[1]; + s2 ^= afl->rand_seed[2]; + s3 ^= afl->rand_seed[3]; + + } + + rand_next(afl); + + } + + afl->rand_seed[0] = s0; + afl->rand_seed[1] = s1; + afl->rand_seed[2] = s2; + afl->rand_seed[3] = s3; + +} + +/* This is the long-jump function for the generator. It is equivalent to + 2^192 calls to rand_next(); it can be used to generate 2^64 starting points, + from each of which jump() will generate 2^64 non-overlapping + subsequences for parallel distributed computations. */ + +void long_jump(afl_state_t *afl) { + + static const uint64_t LONG_JUMP[] = {0x76e15d3efefdcbbf, 0xc5004e441c522fb3, + 0x77710069854ee241, 0x39109bb02acbe635}; + + uint64_t s0 = 0; + uint64_t s1 = 0; + uint64_t s2 = 0; + uint64_t s3 = 0; + for (int i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++) + for (int b = 0; b < 64; b++) { + + if (LONG_JUMP[i] & UINT64_C(1) << b) { + + s0 ^= afl->rand_seed[0]; + s1 ^= afl->rand_seed[1]; + s2 ^= afl->rand_seed[2]; + s3 ^= afl->rand_seed[3]; + + } + + rand_next(afl); + + } + + afl->rand_seed[0] = s0; + afl->rand_seed[1] = s1; + afl->rand_seed[2] = s2; + afl->rand_seed[3] = s3; + +} + +u32 hash32(const void *key, u32 len, u32 seed) { + + return XXH64(key, len, seed) % 0x100000000; + +} + +u64 hash64(const void *key, u32 len, u64 seed) { + + return XXH64(key, len, seed); + +} + -- cgit 1.4.1 From ce1af1bc9c0b58aea653abec8fb42f9714d4308f Mon Sep 17 00:00:00 2001 From: van Hauser Date: Fri, 12 Jun 2020 16:57:33 +0200 Subject: code-format killed the compilation --- include/xxhash.h | 8 ++++++-- src/afl-performance.c | 19 ++++++++++--------- 2 files changed, 16 insertions(+), 11 deletions(-) (limited to 'src/afl-performance.c') diff --git a/include/xxhash.h b/include/xxhash.h index 296fc856..826f39bd 100644 --- a/include/xxhash.h +++ b/include/xxhash.h @@ -1371,7 +1371,9 @@ static xxh_u32 XXH32_avalanche(xxh_u32 h32) { static xxh_u32 XXH32_finalize(xxh_u32 h32, const xxh_u8 *ptr, size_t len, XXH_alignment align) { -\ + + /* dummy comment */ + #define XXH_PROCESS1 \ do { \ \ @@ -1978,7 +1980,9 @@ static xxh_u64 XXH64_avalanche(xxh_u64 h64) { static xxh_u64 XXH64_finalize(xxh_u64 h64, const xxh_u8 *ptr, size_t len, XXH_alignment align) { -\ + + /* dummy comment */ + #define XXH_PROCESS1_64 \ do { \ \ diff --git a/src/afl-performance.c b/src/afl-performance.c index a2eca8c9..7a911ffd 100644 --- a/src/afl-performance.c +++ b/src/afl-performance.c @@ -56,13 +56,13 @@ void jump(afl_state_t *afl) { static const uint64_t JUMP[] = {0x180ec6d33cfd0aba, 0xd5a61266f0c9392c, 0xa9582618e03fc9aa, 0x39abdc4529b1661c}; - - uint64_t s0 = 0; - uint64_t s1 = 0; - uint64_t s2 = 0; - uint64_t s3 = 0; - for (int i = 0; i < sizeof JUMP / sizeof *JUMP; i++) - for (int b = 0; b < 64; b++) { + int i, b; + uint64_t s0 = 0; + uint64_t s1 = 0; + uint64_t s2 = 0; + uint64_t s3 = 0; + for (i = 0; i < sizeof JUMP / sizeof *JUMP; i++) + for (b = 0; b < 64; b++) { if (JUMP[i] & UINT64_C(1) << b) { @@ -94,12 +94,13 @@ void long_jump(afl_state_t *afl) { static const uint64_t LONG_JUMP[] = {0x76e15d3efefdcbbf, 0xc5004e441c522fb3, 0x77710069854ee241, 0x39109bb02acbe635}; + int i, b; uint64_t s0 = 0; uint64_t s1 = 0; uint64_t s2 = 0; uint64_t s3 = 0; - for (int i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++) - for (int b = 0; b < 64; b++) { + for (i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++) + for (b = 0; b < 64; b++) { if (LONG_JUMP[i] & UINT64_C(1) << b) { -- cgit 1.4.1 From 1542c7f49c00cd7d701869f951b9a2a126a7b960 Mon Sep 17 00:00:00 2001 From: van Hauser Date: Sat, 13 Jun 2020 10:58:30 +0200 Subject: fix typos --- docs/Changelog.md | 27 ++++++++++++++------------- include/hash.h | 2 +- src/afl-performance.c | 20 ++++++++++++++------ 3 files changed, 29 insertions(+), 20 deletions(-) (limited to 'src/afl-performance.c') diff --git a/docs/Changelog.md b/docs/Changelog.md index 751dd707..caf262fc 100644 --- a/docs/Changelog.md +++ b/docs/Changelog.md @@ -11,13 +11,13 @@ sending a mail to . ### Version ++2.65d (dev) - afl-fuzz: - - -S secondary nodes now only sync from the main node to increase performance, - the -M main node still syncs from everyone. Added checks that ensure - exactly one main node is present and warn otherwise - - If no main node is present at a sync one secondary node automatically becomes - a temporary main node until a real main nodes shows up - - switched murmur2 hashing and random() for xxh3 and xoshiro256**, giving up to 5.5% speed - increase + - -S secondary nodes now only sync from the main node to increase + performance, the -M main node still syncs from everyone. Added checks + that ensure exactly one main node is present and warn otherwise + - If no main node is present at a sync one secondary node automatically + becomes a temporary main node until a real main nodes shows up + - switched murmur2 hashing and random() for xxh3 and xoshiro256**, + resulting in an up to 5.5% speed increase - Resizing the window does not crash afl-fuzz anymore - fix/update to MOpt (thanks to arnow117) - added MOpt dictionary support from repo @@ -26,10 +26,10 @@ sending a mail to . better coverage. The original afl instrumentation can be set via AFL_LLVM_INSTRUMENT=AFL. This is automatically done when the WHITELIST feature is used. - - some targets want a ld variant for LD that is not gcc/clang but ld, added - afl-ld-lto to solve this - - lowered minimum required llvm version to 3.4 (except LLVMInsTrim, - which needs 3.8.0) + - some targets want a ld variant for LD that is not gcc/clang but ld, + added afl-ld-lto to solve this + - lowered minimum required llvm version to 3.4 (except LLVMInsTrim, which + needs 3.8.0) - WHITELIST feature now supports wildcards (thanks to sirmc) - small change to cmplog to make it work with current llvm 11-dev - added AFL_LLVM_LAF_ALL, sets all laf-intel settings @@ -41,6 +41,7 @@ sending a mail to . - enable snapshot lkm also for persistent mode - Unicornafl - Added powerPC support from unicorn/next + - rust bindings! - persistent mode shared memory testcase handover (instead of via files/stdin) - 10-100% performance increase - General support for 64 bit PowerPC, RiscV, Sparc etc. @@ -49,8 +50,8 @@ sending a mail to . the same second - added lots of dictionaries from oss-fuzz, go-fuzz and Jakub Wilk - added former post_library examples to examples/custom_mutators/ - - Dockerfile upgraded to Ubuntu 20.04 Focal and installing llvm 11 and gcc 10 - so afl-clang-lto can be build + - Dockerfile upgraded to Ubuntu 20.04 Focal and installing llvm 11 and + gcc 10 so afl-clang-lto can be build ### Version ++2.65c (release): diff --git a/include/hash.h b/include/hash.h index 09dabb59..6910e0e2 100644 --- a/include/hash.h +++ b/include/hash.h @@ -35,7 +35,7 @@ u64 hash64(const void *key, u32 len, u64 seed); #if 0 -The following code is disabled because xxh3 with a 32 bit resukt is 30% faster +The following code is disabled because xxh3 is 30% faster #ifdef __x86_64__ diff --git a/src/afl-performance.c b/src/afl-performance.c index 7a911ffd..28564eb8 100644 --- a/src/afl-performance.c +++ b/src/afl-performance.c @@ -1,10 +1,11 @@ -/* Written in 2019 by David Blackman and Sebastiano Vigna (vigna@acm.org) +/* + Written in 2019 by David Blackman and Sebastiano Vigna (vigna@acm.org) -To the extent possible under law, the author has dedicated all copyright -and related and neighboring rights to this software to the public domain -worldwide. This software is distributed without any warranty. + To the extent possible under law, the author has dedicated all copyright + and related and neighboring rights to this software to the public domain + worldwide. This software is distributed without any warranty. -See . + See . This is xoshiro256++ 1.0, one of our all-purpose, rock-solid generators. It has excellent (sub-ns) speed, a state (256 bits) that is large @@ -15,13 +16,17 @@ See . The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we suggest to seed a splitmix64 generator and use its - output to fill s. */ + output to fill s[]. +*/ #include #include "afl-fuzz.h" #include "types.h" #include "xxh3.h" +/* we use xoshiro256** instead of rand/random because it is 10x faster and has + better randomness properties. */ + static inline uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); @@ -122,6 +127,9 @@ void long_jump(afl_state_t *afl) { } +/* we switch from afl's murmur implementation to xxh3 as it is 30% faster - + and get 64 bit hashes instead of just 32 bit. Less collisions! :-) */ + u32 hash32(const void *key, u32 len, u32 seed) { return XXH64(key, len, seed) % 0x100000000; -- cgit 1.4.1 From 246444dd5765ee467b6fc090dc078cac3ce2074a Mon Sep 17 00:00:00 2001 From: Dominik Maier Date: Mon, 15 Jun 2020 21:40:30 +0200 Subject: tidied hash32, unicorn --- src/afl-performance.c | 6 +++--- unicorn_mode/UNICORNAFL_VERSION | 2 +- unicorn_mode/unicornafl | 2 +- 3 files changed, 5 insertions(+), 5 deletions(-) (limited to 'src/afl-performance.c') diff --git a/src/afl-performance.c b/src/afl-performance.c index 28564eb8..9c842312 100644 --- a/src/afl-performance.c +++ b/src/afl-performance.c @@ -130,13 +130,13 @@ void long_jump(afl_state_t *afl) { /* we switch from afl's murmur implementation to xxh3 as it is 30% faster - and get 64 bit hashes instead of just 32 bit. Less collisions! :-) */ -u32 hash32(const void *key, u32 len, u32 seed) { +u32 inline hash32(const void *key, u32 len, u32 seed) { - return XXH64(key, len, seed) % 0x100000000; + return XXH32(key, len, seed); } -u64 hash64(const void *key, u32 len, u64 seed) { +u64 inline hash64(const void *key, u32 len, u64 seed) { return XXH64(key, len, seed); diff --git a/unicorn_mode/UNICORNAFL_VERSION b/unicorn_mode/UNICORNAFL_VERSION index 589e3db2..c03c4529 100644 --- a/unicorn_mode/UNICORNAFL_VERSION +++ b/unicorn_mode/UNICORNAFL_VERSION @@ -1 +1 @@ -09e8e8ad +04765d30 diff --git a/unicorn_mode/unicornafl b/unicorn_mode/unicornafl index 09e8e8ad..04765d30 160000 --- a/unicorn_mode/unicornafl +++ b/unicorn_mode/unicornafl @@ -1 +1 @@ -Subproject commit 09e8e8adec97482d9937dd15f73f78611de19bc3 +Subproject commit 04765d30ac3c3d31d83520f35237a52d18002c83 -- cgit 1.4.1 From 6804065a8d4864755af866c5c800dde0b4445155 Mon Sep 17 00:00:00 2001 From: Dominik Maier Date: Mon, 15 Jun 2020 22:03:01 +0200 Subject: using XX64 for 32 bit hash --- src/afl-performance.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/afl-performance.c') diff --git a/src/afl-performance.c b/src/afl-performance.c index 9c842312..437df963 100644 --- a/src/afl-performance.c +++ b/src/afl-performance.c @@ -132,7 +132,7 @@ void long_jump(afl_state_t *afl) { u32 inline hash32(const void *key, u32 len, u32 seed) { - return XXH32(key, len, seed); + return (u32) XXH64(key, len, seed); } -- cgit 1.4.1 From 9c293b5b7b941d8046e77989f100d084a516d029 Mon Sep 17 00:00:00 2001 From: Dominik Maier Date: Mon, 15 Jun 2020 22:05:37 +0200 Subject: code format --- src/afl-performance.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/afl-performance.c') diff --git a/src/afl-performance.c b/src/afl-performance.c index 437df963..8efefcd8 100644 --- a/src/afl-performance.c +++ b/src/afl-performance.c @@ -132,7 +132,7 @@ void long_jump(afl_state_t *afl) { u32 inline hash32(const void *key, u32 len, u32 seed) { - return (u32) XXH64(key, len, seed); + return (u32)XXH64(key, len, seed); } -- cgit 1.4.1