commit 45bc5a07434376c0d801a547b38893d85a515b49 Author: George Kadianakis <desnacked@riseup.net> Date: Thu Jan 15 14:36:24 2015 +0000 Restrict sample values of the Laplace distribution to int64_t. This helps avoid undefined behavior from casting big double values to int64_t. Fixes #14090. --- changes/bug14090 | 4 ++++ src/common/util.c | 20 +++++++++++++++----- src/common/util.h | 2 +- src/test/test_util.c | 10 +++++----- 4 files changed, 25 insertions(+), 11 deletions(-) diff --git a/changes/bug14090 b/changes/bug14090 new file mode 100644 index 0000000..d6a6df4 --- /dev/null +++ b/changes/bug14090 @@ -0,0 +1,4 @@ + o Minor bugfixes: + - Avoid undefined behavior when sampling huge values from the + Laplace distribution. This made unittests fail on Raspberry Pi. + Bug found by Device. Fixes bug 14090; bugfix on 0.2.6.2-alpha. diff --git a/src/common/util.c b/src/common/util.c index f7baab0..be866a5 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -527,15 +527,25 @@ round_int64_to_next_multiple_of(int64_t number, int64_t divisor) /** Transform a random value <b>p</b> from the uniform distribution in * [0.0, 1.0[ into a Laplace distributed value with location parameter - * <b>mu</b> and scale parameter <b>b</b> in [-Inf, Inf[. */ -double + * <b>mu</b> and scale parameter <b>b</b>. Truncate the final result + * to be an integer in [INT64_MIN, INT64_MAX]. */ +int64_t sample_laplace_distribution(double mu, double b, double p) { + double result; + tor_assert(p >= 0.0 && p < 1.0); /* This is the "inverse cumulative distribution function" from: * http://en.wikipedia.org/wiki/Laplace_distribution */ - return mu - b * (p > 0.5 ? 1.0 : -1.0) - * tor_mathlog(1.0 - 2.0 * fabs(p - 0.5)); + result = mu - b * (p > 0.5 ? 1.0 : -1.0) + * tor_mathlog(1.0 - 2.0 * fabs(p - 0.5)); + + if (result >= INT64_MAX) + return INT64_MAX; + else if (result <= INT64_MIN) + return INT64_MIN; + else + return (int64_t) result; } /** Add random noise between INT64_MIN and INT64_MAX coming from a @@ -546,10 +556,10 @@ int64_t add_laplace_noise(int64_t signal, double random, double delta_f, double epsilon) { - /* cast to int64_t intended */ int64_t noise = sample_laplace_distribution( 0.0, /* just add noise, no further signal */ delta_f / epsilon, random); + if (noise > 0 && INT64_MAX - noise < signal) return INT64_MAX; else if (noise < 0 && INT64_MIN - noise > signal) diff --git a/src/common/util.h b/src/common/util.h index 1b8fc74..89c1400 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -173,7 +173,7 @@ unsigned round_to_next_multiple_of(unsigned number, unsigned divisor); uint32_t round_uint32_to_next_multiple_of(uint32_t number, uint32_t divisor); uint64_t round_uint64_to_next_multiple_of(uint64_t number, uint64_t divisor); int64_t round_int64_to_next_multiple_of(int64_t number, int64_t divisor); -double sample_laplace_distribution(double mu, double b, double p); +int64_t sample_laplace_distribution(double mu, double b, double p); int64_t add_laplace_noise(int64_t signal, double random, double delta_f, double epsilon); int n_bits_set_u8(uint8_t v); diff --git a/src/test/test_util.c b/src/test/test_util.c index 15470e8..75727a4 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -4654,11 +4654,11 @@ test_util_laplace(void *arg) const double delta_f = 15.0, epsilon = 0.3; /* b = 15.0 / 0.3 = 50.0 */ (void)arg; - tt_assert(isinf(sample_laplace_distribution(mu, b, 0.0))); - test_feq(-69.88855213, sample_laplace_distribution(mu, b, 0.01)); - test_feq(24.0, sample_laplace_distribution(mu, b, 0.5)); - test_feq(24.48486498, sample_laplace_distribution(mu, b, 0.51)); - test_feq(117.88855213, sample_laplace_distribution(mu, b, 0.99)); + tt_int_op(INT64_MIN, ==, sample_laplace_distribution(mu, b, 0.0)); + tt_int_op(-69, ==, sample_laplace_distribution(mu, b, 0.01)); + tt_int_op(24, ==, sample_laplace_distribution(mu, b, 0.5)); + tt_int_op(24, ==, sample_laplace_distribution(mu, b, 0.51)); + tt_int_op(117, ==, sample_laplace_distribution(mu, b, 0.99)); /* >>> laplace.ppf([0.0, 0.1, 0.25, 0.5, 0.75, 0.9, 0.99], * ... loc = 0, scale = 50)