Page MenuHomePhabricator

[LibFuzzer] Avoid using std::random_swap() due to platform differences and implement our own version.
AbandonedPublic

Authored by delcypher on Jun 9 2016, 10:22 PM.

Details

Reviewers
kcc
aizatsky
Summary

[LibFuzzer] Avoid using std::random_swap() due to platform differences
and implement our own version.

It turns out that the behavior of std::random_swap is different between
libstdc++ and libcxx (even with the same random number source).
Therefore if we want consistent behavior between platforms we have to
use our own implementation.

This change (plus a change to the number of iterations of the Mutator in
the test required for the particular shuffle implementation used) fixes
the `FuzzerMutate.ShuffleBytes2` unit test on OSX.

I have verified that for the above unittest identical mutations are
now generated on both Linux and on OSX.

Diff Detail

Event Timeline

delcypher updated this revision to Diff 60310.Jun 9 2016, 10:22 PM
delcypher retitled this revision from to [LibFuzzer] Avoid using std::random_swap() due to platform differences and implement our own version..
delcypher updated this object.
delcypher added reviewers: kcc, aizatsky.
delcypher added subscribers: kcc, aizatsky, zaks.anna and 3 others.

@kcc: Sorry it took me quite a while to figure out exactly where divergence in mutation behavior was coming from but it does seem to be the use of std::random_shuffle() that is causing it which is rather sad. Here's a small test cases you can run to see the problem. You should fine that the printed result is different on Linux (with libstdc++) and OSX (with libcxx).

#include <algorithm>
#include <iostream>
#include <random>
#include <stdint.h>

void printArray(uint8_t* X, size_t length) {
  for (size_t index=0; index < length; ++index) {
    std::cout << "0x" << std::hex << static_cast<unsigned>(X[index]) << ",";
  }
  std::cout << std::endl;
}

class Random {
 public:
  Random(unsigned int seed) : R(seed) {}
  size_t Rand() { return R(); }
  size_t RandBool() { return Rand() % 2; }
  size_t operator()(size_t n) { return n ? Rand() % n : 0; }
  std::mt19937 &Get_mt19937() { return R; }
 private:
  std::mt19937 R;
};


int main() {
  Random R(0);
  uint8_t X[7] = { 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
  printArray(X, 7);
  // Shuffle
  std::random_shuffle(X + 2, X + 2 + 4, R);
  // With libstdc++ : 0x0,0x11,0x44,0x55,0x33,0x22,0x66,
  // With libcxx    : 0x0,0x11,0x22,0x33,0x55,0x44,0x66,
  printArray(X, 7);
  return 0;
}

I'm not entirely sure the implementation I've picked to replace random_shuffle is the best as it required more iterations in the unit test to hit all the mutations we want to see (previously 524288 now its 566171).

aizatsky requested changes to this revision.Jun 10 2016, 2:22 PM
aizatsky edited edge metadata.
aizatsky added inline comments.
lib/Fuzzer/FuzzerInternal.h
145

Specify algorithm reference.

152

Let's see that this is literally Fisher-Yates shuffle:

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Even (N-2) is important to have it produce uniform shuffles.

This revision now requires changes to proceed.Jun 10 2016, 2:22 PM
delcypher added inline comments.Jun 10 2016, 6:36 PM
lib/Fuzzer/FuzzerInternal.h
145

This algorithm is based on what is in libc++ but the loop iteration goes forwards rather than backwards.

152

Let's see that this is literally Fisher-Yates shuffle:
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I did not know this algorithm had a name. My version is basically the Durstenfeld implementation shuffling from lowest index to highest. This had made me realize there is a mistake in my implementation. My implementation loops one too many time as it will try to swap the last element with itself.

Even (N-2) is important to have it produce uniform shuffles.

I did not know that. I didn't see that explicitly stated in the wikipedia article. Is that a solution to the modulo bias problem it mentions?

kcc edited edge metadata.Jun 11 2016, 4:47 AM

What problem are you trying to fix and do you really need to fix it?

  • kcc (sent from phone)
kcc added a comment.Jun 13 2016, 7:27 AM

Can you just change the number of iterations to e.g. 1<<20 or 1<<21?

In D21218#455412, @kcc wrote:

What problem are you trying to fix and do you really need to fix it?

The problem I'm trying to fix is inconsistent mutation behavior between OSX and Linux. Having inconsistent behavior is undesirable because

  • It makes debugging issues on OSX harder because it prevents me from using how LibFuzzer behaves on Linux as my point of reference.
  • It makes tests flakey.
In D21218#456101, @kcc wrote:

Can you just change the number of iterations to e.g. 1<<20 or 1<<21?

That is the very first thing I tried and that does allow the test to pass on OSX but that's a terrible fix which just hides the underlying issue. I think it is very undesirable to have mutation behavior differ between platforms. The fact that the unit tests use a fix seed for the PRNG suggests to me that the author was trying to make the test behave consistently. Having tests behave consistently is a good thing and I don't understand why we would want only partially consistent behavior by not bothering to make random shuffle behave consistently.

I am more than happy to debate what the algorithm should be but I very strongly believe that LibFuzzer's reliance on std::random_shuffle needs to be removed.

kcc added a comment.Jun 13 2016, 4:06 PM
In D21218#455412, @kcc wrote:

What problem are you trying to fix and do you really need to fix it?

The problem I'm trying to fix is inconsistent mutation behavior between OSX and Linux. Having inconsistent behavior is undesirable because

  • It makes debugging issues on OSX harder because it prevents me from using how LibFuzzer behaves on Linux as my point of reference.
  • It makes tests flakey.

Tests that do random mutations will behave this way.
They are not flaky in usual meaning, i.e. running the same binary 10000000 times will give the same result.
But running on a different OS, or with a different STL may produce different result here and it should be fine.

In D21218#456978, @kcc wrote:
In D21218#455412, @kcc wrote:

What problem are you trying to fix and do you really need to fix it?

The problem I'm trying to fix is inconsistent mutation behavior between OSX and Linux. Having inconsistent behavior is undesirable because

  • It makes debugging issues on OSX harder because it prevents me from using how LibFuzzer behaves on Linux as my point of reference.
  • It makes tests flakey.

Tests that do random mutations will behave this way.
They are not flaky in usual meaning, i.e. running the same binary 10000000 times will give the same result.
But running on a different OS, or with a different STL may produce different result here and it should be fine.

I disagree with your choice here. I would prefer for consistent behavior where it is possible, however:

  • I have run out time to do any more major porting work for LibFuzzer.
  • LibFuzzer is your project so you have the final say here.

So would you accept a patch that just increases the number iterations we do of the mutator to fix the test? If yes do you want it to be the minimum number of iterations required or something more readable like (1 << 20)?

kcc added a comment.Jun 14 2016, 8:04 AM

Minimal power of two would be the best.