From 0ec6a4882eeb34338b916567f8e63fb71afc84fd Mon Sep 17 00:00:00 2001 From: Louis Dionne Date: Thu, 7 Nov 2019 12:06:14 +0000 Subject: [PATCH] [libc++] Fix potential OOB in poisson_distribution See details in the original Chromium bug report: https://bugs.chromium.org/p/chromium/issues/detail?id=994957 --- libcxx/include/random | 45 ++++++++------- .../rand.dist.bern.geo/eval.pass.cpp | 11 ++++ .../rand.dist.pois.poisson/eval.pass.cpp | 64 +++++++++++++++++++++- 3 files changed, 98 insertions(+), 22 deletions(-) diff --git a/libcxx/include/random b/libcxx/include/random index afa60b4..0cbc72d 100644 --- a/libcxx/include/random +++ b/libcxx/include/random @@ -4592,7 +4592,10 @@ public: template poisson_distribution<_IntType>::param_type::param_type(double __mean) - : __mean_(__mean) + // According to the standard `inf` is a valid input, but it causes the + // distribution to hang, so we replace it with the maximum representable + // mean. + : __mean_(isinf(__mean) ? numeric_limits::max() : __mean) { if (__mean_ < 10) { @@ -4610,7 +4613,7 @@ poisson_distribution<_IntType>::param_type::param_type(double __mean) { __s_ = _VSTD::sqrt(__mean_); __d_ = 6 * __mean_ * __mean_; - __l_ = static_cast(__mean_ - 1.1484); + __l_ = std::trunc(__mean_ - 1.1484); __omega_ = .3989423 / __s_; double __b1_ = .4166667E-1 / __mean_; double __b2_ = .3 * __b1_ * __b1_; @@ -4627,12 +4630,12 @@ template _IntType poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr) { - result_type __x; + double __tx; uniform_real_distribution __urd; if (__pr.__mean_ < 10) { - __x = 0; - for (double __p = __urd(__urng); __p > __pr.__l_; ++__x) + __tx = 0; + for (double __p = __urd(__urng); __p > __pr.__l_; ++__tx) __p *= __urd(__urng); } else @@ -4642,19 +4645,19 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr double __u; if (__g > 0) { - __x = static_cast(__g); - if (__x >= __pr.__l_) - return __x; - __difmuk = __pr.__mean_ - __x; + __tx = std::trunc(__g); + if (__tx >= __pr.__l_) + return std::__clamp_to_integral(__tx); + __difmuk = __pr.__mean_ - __tx; __u = __urd(__urng); if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk) - return __x; + return std::__clamp_to_integral(__tx); } exponential_distribution __edist; for (bool __using_exp_dist = false; true; __using_exp_dist = true) { double __e; - if (__using_exp_dist || __g < 0) + if (__using_exp_dist || __g <= 0) { double __t; do @@ -4664,31 +4667,31 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr __u += __u - 1; __t = 1.8 + (__u < 0 ? -__e : __e); } while (__t <= -.6744); - __x = __pr.__mean_ + __pr.__s_ * __t; - __difmuk = __pr.__mean_ - __x; + __tx = std::trunc(__pr.__mean_ + __pr.__s_ * __t); + __difmuk = __pr.__mean_ - __tx; __using_exp_dist = true; } double __px; double __py; - if (__x < 10) + if (__tx < 10 && __tx >= 0) { const double __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; __px = -__pr.__mean_; - __py = _VSTD::pow(__pr.__mean_, (double)__x) / __fac[__x]; + __py = _VSTD::pow(__pr.__mean_, (double)__tx) / __fac[static_cast(__tx)]; } else { - double __del = .8333333E-1 / __x; + double __del = .8333333E-1 / __tx; __del -= 4.8 * __del * __del * __del; - double __v = __difmuk / __x; + double __v = __difmuk / __tx; if (_VSTD::abs(__v) > 0.25) - __px = __x * _VSTD::log(1 + __v) - __difmuk - __del; + __px = __tx * _VSTD::log(1 + __v) - __difmuk - __del; else - __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) * + __px = __tx * __v * __v * (((((((.1250060 * __v + -.1384794) * __v + .1421878) * __v + -.1661269) * __v + .2000118) * __v + -.2500068) * __v + .3333333) * __v + -.5) - __del; - __py = .3989423 / _VSTD::sqrt(__x); + __py = .3989423 / _VSTD::sqrt(__tx); } double __r = (0.5 - __difmuk) / __pr.__s_; double __r2 = __r * __r; @@ -4708,7 +4711,7 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr } } } - return __x; + return std::__clamp_to_integral(__tx); } template diff --git a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp index bdeaa20..11eeb97 100644 --- a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp +++ b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp @@ -30,6 +30,16 @@ sqr(T x) return x * x; } +void test_small_inputs() { + std::mt19937 engine; + std::geometric_distribution distribution(5.45361e-311); + typedef std::geometric_distribution::result_type result_type; + for (int i = 0; i < 1000; ++i) { + volatile result_type res = distribution(engine); + ((void)res); + } +} + void test1() { @@ -296,6 +306,7 @@ int main(int, char**) test4(); test5(); test6(); + test_small_inputs(); return 0; } diff --git a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp index 4b07d23..00a70ac 100644 --- a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp +++ b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp @@ -30,6 +30,67 @@ sqr(T x) return x * x; } +void test_bad_ranges() { + // Test cases where the mean is around the largest representable integer for + // `result_type`. These cases don't generate valid poisson distributions, but + // at least they don't blow up. + std::mt19937 eng; + + { + std::poisson_distribution distribution(32710.9); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution(std::numeric_limits::max()); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution( + static_cast(std::numeric_limits::max()) + 10); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution( + static_cast(std::numeric_limits::max()) * 2); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + // We convert `INF` to `DBL_MAX` otherwise the distribution will hang. + std::poisson_distribution distribution(std::numeric_limits::infinity()); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution(0); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + // We convert `INF` to `DBL_MAX` otherwise the distribution will hang. + std::poisson_distribution distribution(-100); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } +} + int main(int, char**) { { @@ -150,5 +211,6 @@ int main(int, char**) assert(std::abs((kurtosis - x_kurtosis) / x_kurtosis) < 0.01); } - return 0; + test_bad_ranges(); + return 0; } -- 2.7.4