[tor-commits] [tor/master] Restrict sample values of the Laplace distribution to int64_t.

[nickm@xxxxxxxxxxxxxx]

commit 45bc5a07434376c0d801a547b38893d85a515b49
Author: George Kadianakis <desnacked@xxxxxxxxxx>
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)



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits