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

The Math.random implementation in Hermes is collision prone for the App use case #1169

Closed
1 task
psaha-rbi opened this issue Oct 19, 2023 · 17 comments
Closed
1 task
Labels
community-support-needed Facebook can't provide direct support for this issue, it is up to the community enhancement New feature or request

Comments

@psaha-rbi
Copy link

psaha-rbi commented Oct 19, 2023

Bug Description

The implementation is

CallResult<HermesValue> mathRandom(void *, Runtime &runtime, NativeArgs) {
  RuntimeCommonStorage *storage = runtime.getCommonStorage();
  if (!storage->randomEngineSeeded_) {
    std::minstd_rand::result_type seed;
    seed = std::random_device()();
    storage->randomEngine_.seed(seed);
    storage->randomEngineSeeded_ = true;
  }
  std::uniform_real_distribution<> dist(0.0, 1.0);
  return HermesValue::encodeUntrustedNumberValue(dist(storage->randomEngine_));
}

As you can see, it uses std::random_device() as seed. It is an unsigned int and therefore there are only about 4B possible values. There is a 71% chance of a single collision if you generate 100k values using the Birthday problem formulation. So many different instances of this will go through the exact same sequence. While this is not used for security, this is also unusable for things like UUID v4 generation since there will be tons of collisions.

Please consider using a much larger seed space - ideally, 100+ bits. A simple way would be to concatenate multiple outputs from std::random_device().

  • I have run gradle clean and confirmed this bug does not occur with JSC

Hermes version: latest
React Native version (if any): all
OS version (if any): all
Platform (most likely one of arm64-v8a, armeabi-v7a, x86, x86_64): all

Steps To Reproduce

Theoretical but we have seen collisions matching the birthday problem formula out in the wild.

code example:

The Expected Behavior

Much harder to produce collisions.

@psaha-rbi psaha-rbi added the bug Something isn't working label Oct 19, 2023
@tmikov tmikov added enhancement New feature or request and removed bug Something isn't working labels Oct 19, 2023
@tmikov
Copy link
Contributor

tmikov commented Oct 19, 2023

Hi, I removed the "bug" label, since this not a bug - EcmaScript specifies it as implementation defined and puts no requirements for its "randomness".

Can you provide links to the relevant implementations in v8 or JSC? If we are to change this, we should probably match their behavior.

The best way to improve this would probably be to submit a PR.

@tmikov
Copy link
Contributor

tmikov commented Oct 19, 2023

Also, can you please clarify your 4B values comment. That is just the seed, which is used once. How does it affect the quality of the values that are generated after?

@psaha-rbi
Copy link
Author

@tmikov If two instances of the PRNG are seeded with the same value then they'll generate the same sequence of pseudo-random values. In this case, let's say you have 1M Hermes instances. In about 7 of them, the randomEngine_ will have the same seed and therefore end up generating the same sequence of "random" values. Now imagine an app that starts up and generates a sequence of UUID v4s. In 7 out of that million instances, you get the exact same sequence of uuid v4s.

Here's a good blog post that explains similar issues much better than I can

@psaha-rbi
Copy link
Author

psaha-rbi commented Oct 19, 2023

Hi, I removed the "bug" label, since this not a bug - EcmaScript specifies it as implementation defined and puts no requirements for its "randomness".

Can you provide links to the relevant implementations in v8 or JSC? If we are to change this, we should probably match their behavior.

The best way to improve this would probably be to submit a PR.

here's the v8 one
As you can see, it uses a 64 bit seed - so much less chance of a collision if the seeds are uniformly distributed.

[here's the JSC one] (https://github.com/WebKit/WebKit/blob/32f02266555bda2527e0a5fc1b9126bd33555a8e/Source/WTF/wtf/WeakRandom.h#L64) It seems to have 32 bit seed and therefore has the same problem as Hermes.

@johnculviner
Copy link

johnculviner commented Oct 20, 2023

I think it's important to note that this issue is prone to happening specifically because this issue is deemed out of scope. There isn't a built in cryptographically secure mechanism to PRNG which can cause collisions when using libraries that may fall-back to Math.random() like some versions of https://www.npmjs.com/package/uuid .

I think increasing the seed-space should be done at a minimum to reduce likelihood of collisions which we have personally observed using UUID with it's Math.random() fallback.

Ideally it'd be great to see crypto built in too since this is an enormous potential (as in a pure probability game!) foot-gun when using hermes but I understand your concerns on the other issue.

@tmikov
Copy link
Contributor

tmikov commented Oct 20, 2023

@johnculviner it is not really out of scope. See #1003 where we asked for a PR. It is just something that we don't feel competent to implement, especially since we won't use it.

@tmikov
Copy link
Contributor

tmikov commented Oct 20, 2023

@psaha-rbi Thanks for posting the v8 and JSC links. I see at least two complications:

  1. Where do we get a good 64-bit seed from in a portable way? If not, we would need multiple implementations, at least for Apple, Android, Linux, Windows. Seems like v8 is using a random generator for the seed (why?), but presumably that generator itself is seeded somewhere.
  2. minstd_rand apparently takes a 32-bit seed.

This does not appear to be a trivial fix.

@purujit
Copy link

purujit commented Oct 20, 2023

@psaha-rbi Thanks for posting the v8 and JSC links. I see at least two complications:

  1. Where do we get a good 64-bit seed from in a portable way? If not, we would need multiple implementations, at least for Apple, Android, Linux, Windows. Seems like v8 is using a random generator for the seed (why?), but presumably that generator itself is seeded somewhere.
  2. minstd_rand apparently takes a 32-bit seed.

This does not appear to be a trivial fix.

  1. You can use a similar technique as v8. On BSD (and Darwin) it uses the ARC4 algorithm to get a 64 bit seed. The ARC4 system itself (I think) tries to get entropy from the kernel and therefore, should be able to give a good random 64 bit seed. Or trivially, assuming std:: random_device() is a good implementation, you can just concat two 32 bit random numbers from it. At least in the LLVM implementation, it seems to do the right thing for std:: random_device (https://github.com/llvm/llvm-project/blob/f2517cbceec0bd9b049ba24f36cb3a2508c988fa/libcxx/src/random.cpp#L67)
  2. It looks like if you use 64 bit LCG (minstd_rand is the 32 bit version of this) you can use a 64 bit seed

@tmikov tmikov added the community-support-needed Facebook can't provide direct support for this issue, it is up to the community label Oct 20, 2023
@chakrihacker
Copy link

Can I give it a try??

@tmikov
Copy link
Contributor

tmikov commented Oct 21, 2023

@chakrihacker you don't need to ask for permission. Hermes is open source, anyone can submit a PR. We can't "assign tasks" to people 😀

@woshiccm
Copy link

woshiccm commented Oct 22, 2023

Hi @tmikov @psaha-rbi I have created a PR, please review it, thanks #1171

@tmikov
Copy link
Contributor

tmikov commented Oct 22, 2023

@psaha-rbi to confirm, assuming we had a random generator with a 64-bit seed, would constructing the seed by two calls to std::random_device()() eliminate the problem?

@tmikov
Copy link
Contributor

tmikov commented Oct 22, 2023

@woshiccm thanks for the PR! Can you please explain your solution in detail? How it addresses the problem - is using system time considered good enough? Also, what random generator algorithm are you using? Is it a standard one?

@purujit
Copy link

purujit commented Oct 22, 2023

I'm not a fan of the time based solution from @woshiccm since it depends on the clock resolution of the system. I think calling random_device() twice to construct a 64 bit seed and using a 64 bit LCG is a better solution like @tmikov proposed. (Responding from my personal account, I'm @psaha-rbi).

@sebholl
Copy link
Contributor

sebholl commented Oct 24, 2023

I put up an alternate PR here: #1175

@woshiccm
Copy link

woshiccm commented Oct 28, 2023

I'm not a fan of the time based solution from @woshiccm since it depends on the clock resolution of the system. I think calling random_device() twice to construct a 64 bit seed and using a 64 bit LCG is a better solution like @tmikov proposed. (Responding from my personal account, I'm @psaha-rbi).

OK, I have refer to v8's code to implement it, could you pls help review again @tmikov @purujit #1171

facebook-github-bot pushed a commit that referenced this issue Oct 31, 2023
Summary:
The `std::minstd_rand` implementation has its `seed()` value type defined as `result_type` which is aliased to `unsigned int`, a 32-bit value on supported platforms. Using 32-bit seeds and results can lead to real-world [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) collisions. As per Purujit's recommendation, we update the implementation of `Math.random()` to utilize a 64-bit LCG that can accept a 64-bit seed and also generate a 64-bit result.

There is a lot of [analysis](https://prng.di.unimi.it/) and [blog posts](https://v8.dev/blog/math-random) around the best way to implement random number generators. This PR attempts to deliver two improvements on the current implementation:

* Having 64-bit seeded values and result types instead of 32-bit.
* Ideally, being faster or at least the same speed.
* (optional) having better randomness properties.

Addressing #1169, we benchmark the `xoroshiro128+` (used by browsers); `randomDevice` (cryptographically secure); `mt19937_64` (complex but fast) and `lcg64` (simple & fast) unsigned 64-bit integer PRNGs against three different uniform random distribution implementations:

1. **`std::uniform_real_distribution()`**: standard library implementation, but slow as it requires multiple random numbers to be generated for a single [0, 1) value; plus it has known bugs where it can in fact return 1 because of rounding.
2. **Bit Twiddle Approach 1**: use the `(0x3FFL << 52 | uint64_t(x) >>> 12) - 1.0` from Java and Firefox that pairs a fixed exponent with 52 random mantissa bits to generate a double between [1, 2) and then subtracting 1.
3. **Bit Twiddle Approach 2**: use the `(uint64_t(x) >> 11) * 0x1.0p-53` approach which generates a double between [0, 1) directly with 53 bits worth of possible output (twice as many values as the 52 bits from Approach 1).

The bit twiddling approaches are described [here](https://prng.di.unimi.it/#:~:text=Generating%20uniform%20doubles%20in%20the%20unit%20interval).

Given the large number of platforms and architectures that Hermes is compiled to, we make copious use of `static_assert`s to make sure that we don't encounter unexpected rug-pulls or changing bit-widths when upgrading compilers; or adding new targets. These should of course be elided after compilation and so will not affect runtime performance.

### Alternatives Considered

- Instead of manually bit packing a 64-bit seed, an implementation leveraging C++11's `seed_seq` was explored that would ideally provide even more entropy, however the author of [this article](https://www.pcg-random.org/posts/cpp-seeding-surprises.html) asserts that 64 bits of seed seq data does not necessarily produce 64 bits of output. As such, we keep it simple with a single seed value so it is easier to reason with in the future.

Pull Request resolved: #1175

Test Plan:
We compile the following `benchmark.js` to byte-code using `../bin/hermes --emit-binary -fstatic-builtins -O ./benchmark.js -out ./benchmark.out.bin`:

```
const n_iterations = 10_000_000;
let sum = 0, min = 2, max = -2;
const rndFunction = Math.random;
for (const i = 0; i < n_iterations; i++) {
    const rnd = rndFunction();
    if (rnd < min)
        min = rnd;
    if (rnd > max)
        max = rnd;
    sum += rnd;
}
print(JSON.stringify({min, avg: sum / n_iterations, max}));
```

And then we execute this bytecode on each of the implementation's resulting `hvm` binary (I'm using `hyperfine`) on my local development machine (Apple MacBook Air M2 with ARM64):

| Command | Mean [s] | Min [s] | Max [s] | Relative |
|:---|---:|---:|---:|---:|
| `./hvm-main ./benchmark.out.bin` | 8.371 ± 0.065 | 8.310 | 8.508 | 1.05 ± 0.01 |
| `./hvm-xoroshiro128plus-twiddlebits ./benchmark.out.bin` | 8.075 ± 0.023 | 8.040 | 8.127 | 1.01 ± 0.00 |
| **`./hvm-xoroshiro128plus-twiddlebits2 ./benchmark.out.bin`** | 8.019 ± 0.033 | 7.975 | 8.068 | 1.00 ± 0.01 |
| `./hvm-lcg64-urd ./benchmark.out.bin` | 8.288 ± 0.041 | 8.232 | 8.369 | 1.04 ± 0.01 |
| `./hvm-lcg64-twiddlebits ./benchmark.out.bin` | 7.988 ± 0.030 | 7.949 | 8.039 | 1.00 |
| `./hvm-lcg64-twiddlebits2 ./benchmark.out.bin` | 8.010 ± 0.029 | 7.965 | 8.058 | 1.00 ± 0.01 |
| `./hvm-mt19937_64-urd ./benchmark.out.bin` | 8.109 ± 0.047 | 8.058 | 8.190 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-twiddlebits ./benchmark.out.bin` | 8.135 ± 0.055 | 8.063 | 8.262 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-twiddlebits2 ./benchmark.out.bin` | 8.143 ± 0.039 | 8.067 | 8.187 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-urd-hoisted ./benchmark.out.bin` | 8.028 ± 0.029 | 7.977 | 8.082 | 1.01 ± 0.01 |
| `./hvm-randomDevice-urd ./benchmark.out.bin` | 9.859 ± 0.036 | 9.800 | 9.918 | 1.23 ± 0.01 |
| `./hvm-randomDevice-twiddlebits ./benchmark.out.bin` | 9.514 ± 0.028 | 9.463 | 9.550 | 1.19 ± 0.01 |
| `./hvm-randomDevice-twiddlebits2 ./benchmark.out.bin` | 9.558 ± 0.033 | 9.498 | 9.610 | 1.20 ± 0.01 |

Although `xoroshiro128plus-twiddlebits2` appears optimal, neildhar preferred `mt19937_64-urd` as it's less invasive a change and has less complexity to maintain.

Reviewed By: avp

Differential Revision: D50792073

Pulled By: neildhar

fbshipit-source-id: 9a5a829dd32adf8986b912e4f424b48a6f937bd0
@tmikov
Copy link
Contributor

tmikov commented Oct 31, 2023

Fixed in 34f0b2b

@tmikov tmikov closed this as completed Oct 31, 2023
sebholl added a commit to sebholl/hermes that referenced this issue Oct 31, 2023
…k#1175)

Summary:
The `std::minstd_rand` implementation has its `seed()` value type defined as `result_type` which is aliased to `unsigned int`, a 32-bit value on supported platforms. Using 32-bit seeds and results can lead to real-world [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) collisions. As per Purujit's recommendation, we update the implementation of `Math.random()` to utilize a 64-bit LCG that can accept a 64-bit seed and also generate a 64-bit result.

There is a lot of [analysis](https://prng.di.unimi.it/) and [blog posts](https://v8.dev/blog/math-random) around the best way to implement random number generators. This PR attempts to deliver two improvements on the current implementation:

* Having 64-bit seeded values and result types instead of 32-bit.
* Ideally, being faster or at least the same speed.
* (optional) having better randomness properties.

Addressing facebook#1169, we benchmark the `xoroshiro128+` (used by browsers); `randomDevice` (cryptographically secure); `mt19937_64` (complex but fast) and `lcg64` (simple & fast) unsigned 64-bit integer PRNGs against three different uniform random distribution implementations:

1. **`std::uniform_real_distribution()`**: standard library implementation, but slow as it requires multiple random numbers to be generated for a single [0, 1) value; plus it has known bugs where it can in fact return 1 because of rounding.
2. **Bit Twiddle Approach 1**: use the `(0x3FFL << 52 | uint64_t(x) >>> 12) - 1.0` from Java and Firefox that pairs a fixed exponent with 52 random mantissa bits to generate a double between [1, 2) and then subtracting 1.
3. **Bit Twiddle Approach 2**: use the `(uint64_t(x) >> 11) * 0x1.0p-53` approach which generates a double between [0, 1) directly with 53 bits worth of possible output (twice as many values as the 52 bits from Approach 1).

The bit twiddling approaches are described [here](https://prng.di.unimi.it/#:~:text=Generating%20uniform%20doubles%20in%20the%20unit%20interval).

Given the large number of platforms and architectures that Hermes is compiled to, we make copious use of `static_assert`s to make sure that we don't encounter unexpected rug-pulls or changing bit-widths when upgrading compilers; or adding new targets. These should of course be elided after compilation and so will not affect runtime performance.

### Alternatives Considered

- Instead of manually bit packing a 64-bit seed, an implementation leveraging C++11's `seed_seq` was explored that would ideally provide even more entropy, however the author of [this article](https://www.pcg-random.org/posts/cpp-seeding-surprises.html) asserts that 64 bits of seed seq data does not necessarily produce 64 bits of output. As such, we keep it simple with a single seed value so it is easier to reason with in the future.

Pull Request resolved: facebook#1175

Test Plan:
We compile the following `benchmark.js` to byte-code using `../bin/hermes --emit-binary -fstatic-builtins -O ./benchmark.js -out ./benchmark.out.bin`:

```
const n_iterations = 10_000_000;
let sum = 0, min = 2, max = -2;
const rndFunction = Math.random;
for (const i = 0; i < n_iterations; i++) {
    const rnd = rndFunction();
    if (rnd < min)
        min = rnd;
    if (rnd > max)
        max = rnd;
    sum += rnd;
}
print(JSON.stringify({min, avg: sum / n_iterations, max}));
```

And then we execute this bytecode on each of the implementation's resulting `hvm` binary (I'm using `hyperfine`) on my local development machine (Apple MacBook Air M2 with ARM64):

| Command | Mean [s] | Min [s] | Max [s] | Relative |
|:---|---:|---:|---:|---:|
| `./hvm-main ./benchmark.out.bin` | 8.371 ± 0.065 | 8.310 | 8.508 | 1.05 ± 0.01 |
| `./hvm-xoroshiro128plus-twiddlebits ./benchmark.out.bin` | 8.075 ± 0.023 | 8.040 | 8.127 | 1.01 ± 0.00 |
| **`./hvm-xoroshiro128plus-twiddlebits2 ./benchmark.out.bin`** | 8.019 ± 0.033 | 7.975 | 8.068 | 1.00 ± 0.01 |
| `./hvm-lcg64-urd ./benchmark.out.bin` | 8.288 ± 0.041 | 8.232 | 8.369 | 1.04 ± 0.01 |
| `./hvm-lcg64-twiddlebits ./benchmark.out.bin` | 7.988 ± 0.030 | 7.949 | 8.039 | 1.00 |
| `./hvm-lcg64-twiddlebits2 ./benchmark.out.bin` | 8.010 ± 0.029 | 7.965 | 8.058 | 1.00 ± 0.01 |
| `./hvm-mt19937_64-urd ./benchmark.out.bin` | 8.109 ± 0.047 | 8.058 | 8.190 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-twiddlebits ./benchmark.out.bin` | 8.135 ± 0.055 | 8.063 | 8.262 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-twiddlebits2 ./benchmark.out.bin` | 8.143 ± 0.039 | 8.067 | 8.187 | 1.02 ± 0.01 |
| `./hvm-mt19937_64-urd-hoisted ./benchmark.out.bin` | 8.028 ± 0.029 | 7.977 | 8.082 | 1.01 ± 0.01 |
| `./hvm-randomDevice-urd ./benchmark.out.bin` | 9.859 ± 0.036 | 9.800 | 9.918 | 1.23 ± 0.01 |
| `./hvm-randomDevice-twiddlebits ./benchmark.out.bin` | 9.514 ± 0.028 | 9.463 | 9.550 | 1.19 ± 0.01 |
| `./hvm-randomDevice-twiddlebits2 ./benchmark.out.bin` | 9.558 ± 0.033 | 9.498 | 9.610 | 1.20 ± 0.01 |

Although `xoroshiro128plus-twiddlebits2` appears optimal, neildhar preferred `mt19937_64-urd` as it's less invasive a change and has less complexity to maintain.

Reviewed By: avp

Differential Revision: D50792073

Pulled By: neildhar

fbshipit-source-id: 9a5a829dd32adf8986b912e4f424b48a6f937bd0
facebook-github-bot pushed a commit that referenced this issue Nov 8, 2023
…1175)

Summary:
Original Author: [email protected]
Original Git: 34f0b2b
Original Reviewed By: avp
Original Revision: D50792073

The `std::minstd_rand` implementation has its `seed()` value type defined as `result_type` which is aliased to `unsigned int`, a 32-bit value on supported platforms. Using 32-bit seeds and results can lead to real-world [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) collisions. As per Purujit's recommendation, we update the implementation of `Math.random()` to utilize a 64-bit LCG that can accept a 64-bit seed and also generate a 64-bit result.

There is a lot of [analysis](https://prng.di.unimi.it/) and [blog posts](https://v8.dev/blog/math-random) around the best way to implement random number generators. This PR attempts to deliver two improvements on the current implementation:

* Having 64-bit seeded values and result types instead of 32-bit.
* Ideally, being faster or at least the same speed.
* (optional) having better randomness properties.

Addressing #1169, we benchmark the `xoroshiro128+` (used by browsers); `randomDevice` (cryptographically secure); `mt19937_64` (complex but fast) and `lcg64` (simple & fast) unsigned 64-bit integer PRNGs against three different uniform random distribution implementations:

1. **`std::uniform_real_distribution()`**: standard library implementation, but slow as it requires multiple random numbers to be generated for a single [0, 1) value; plus it has known bugs where it can in fact return 1 because of rounding.
2. **Bit Twiddle Approach 1**: use the `(0x3FFL << 52 | uint64_t(x) >>> 12) - 1.0` from Java and Firefox that pairs a fixed exponent with 52 random mantissa bits to generate a double between [1, 2) and then subtracting 1.
3. **Bit Twiddle Approach 2**: use the `(uint64_t(x) >> 11) * 0x1.0p-53` approach which generates a double between [0, 1) directly with 53 bits worth of possible output (twice as many values as the 52 bits from Approach 1).

The bit twiddling approaches are described [here](https://prng.di.unimi.it/#:~:text=Generating%20uniform%20doubles%20in%20the%20unit%20interval).

Given the large number of platforms and architectures that Hermes is compiled to, we make copious use of `static_assert`s to make sure that we don't encounter unexpected rug-pulls or changing bit-widths when upgrading compilers; or adding new targets. These should of course be elided after compilation and so will not affect runtime performance.

### Alternatives Considered

- Instead of manually bit packing a 64-bit seed, an implementation leveraging C++11's `seed_seq` was explored that would ideally provide even more entropy, however the author of [this article](https://www.pcg-random.org/posts/cpp-seeding-surprises.html) asserts that 64 bits of seed seq data does not necessarily produce 64 bits of output. As such, we keep it simple with a single seed value so it is easier to reason with in the future.

Pull Request resolved: #1175

Pulled By: neildhar

Reviewed By: neildhar

Differential Revision: D50992797

fbshipit-source-id: 0926d1dda08b217bdc46b0731a03b4cd3cb39812
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
community-support-needed Facebook can't provide direct support for this issue, it is up to the community enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants