[tor-bugs] #29527 [Core Tor/Tor]: Division by zero: undefined behaviour in circuitpadding/circuitpadding_sample_distribution test

[Tor Bug Tracker & Wiki]

#29527: Division by zero: undefined behaviour in
circuitpadding/circuitpadding_sample_distribution test
-------------------------------------------------+-------------------------
 Reporter:  teor                                 |          Owner:  (none)
     Type:  defect                               |         Status:  new
 Priority:  High                                 |      Milestone:  Tor:
                                                 |  0.4.0.x-final
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  regression, tor-ci, tor-test,        |  Actual Points:
  040-must                                       |
Parent ID:                                       |         Points:
 Reviewer:                                       |        Sponsor:
-------------------------------------------------+-------------------------

Comment (by riastradh):

 Floating-point division by zero isn't undefined behaviour -- it is
 precisely defined in IEEE 754 and has been consistently implemented in
 essentially all software and hardware for decades.  This looks like
 mostly, if not entirely, false positives from a buggy UB sanitizer that's
 confused about floating-point arithmetic.

 All of the cases in test_prob_distr.c appear to be working as intended.
 For example, test_prob_distr.c line 496 invokes `CHECK_RELERR(np,
 cdf_log_logistic(1/x, 1, 1))`.  The log-logistic distribution has the
 property that CDF(1/x) = 1 - CDF(x).  When x is arbitrarily close to 0, 1
 - CDF(x) should be extremely close to 1; when we round x to zero, CDF(x)
 should be 0, 1/x is rounded to infinity, and CDF(1/x) = 1 - CDF(x) should
 be 1, exactly as the test confirms.

 In prob_distr.c:

 - line 344, column 17 is inside logit.  logit(1) should be +inf (lim_{x
 --> 1^-^} logit(x) = +inf), and the +inf yielded by division by zero is
 correctly propagated by the expression log(p/(1 - p)).  The test suite
 specifically checks that logit(1) = +inf (test_prob_distr.c lines 323 and
 395).
 - line 427, column 26 is inside logithalf.  logithalf(1/2) = logit(1)
 should be +inf, and the +inf yielded by division by zero is correctly
 propagated by the expression log((0.5 + p0)/(0.5 - p0)).  The test suite
 specifically checks that logithalf(+/-1/2) = +/-inf (test_prob_distr.c
 lines 294, 323, and 397).
 - line 685, column 27 is inside isf_log_logistic.  The log logistic
 distribution has the property that CDF(1/x) = 1 - CDF(x), which means
 CDF^-1^(1 - p) = SF^-1^(p) = 1/x.  In test_prob_distr.c, line 450
 specifies a test where p = 0, np = 1 - p = 1, and line 553 confirms
 isf_log_logistic(p, 1, 1), which entails dividing by p, correctly gives
 1/x.
 - line 814, column 23 is in cdf_genpareto.  Here we are checking whether
 the approximation 1 - e^-x_0^ is safe for the specified value of xi, which
 we consider it to be if |xi| < 1e-17/x_0.  If x_0 is infinite, we consider
 it safe.  For any xi, as x_0 goes to zero, the CDF goes to zero too, which
 is exactly what the approximation computes, so this is correct.  The test
 case on line 718 of test_prob_distr.c specifies x_0 = 0.  (Side note: It
 appears I wrote no tests with a nonzero mean.  Should maybe add some.)
 - line 837, column 23 is in sf_genpareto, which has the same case analysis
 and test cases as the above instance.
 - line 1170, column 20 is in sample_log_logistic, evaluating the quotient
 in `(1 - p0)/p0`.  This is division by zero only if p0 = 0.  In that case,
 we return the correct answer is +inf, since as p0 -> 0, this function
 grows without bound.  In test_prob_distr.c, lines 565, 567, and 569
 specify tests with p0 = 0.  (However, in actual runs of the code with p0
 drawn using `random_uniform_01`, p0 = 0 should happen only with
 probability 2^-1075^, i.e. never.)
 - line 1311, column 17 is inside sample_geometric, evaluating the quotient
 in `-x/log1p(-p)`.  The divisor can be zero only if p = 0, which means
 we're trying to sample from a geometric distribution with zero success
 probability.  Of course, the only reasonable result is +inf.  **Is there
 anything _upstream_ of this logic that tries to construct a
 `CIRCPAD_DIST_GEOMETRIC` with zero success probability?**
 - line 1219, column 49 is inside sample_weibull, computing `1/k`.  This
 can happen only if k = 0, which is an edge case that's probably not very
 useful, but the expression does return +inf which is the correct limit as
 k --> 0.  **Is there anything upstream of this logic that tries to
 construct a `CIRCPAD_DIST_WEIBULL` with zero shape?**

 By the way, pretty much all non-arm hardware supports a kind of
 ‘sanitizer’ for floating-point invalid operations (which are not undefined
 behaviour, but are usually undesirable) with zero overhead if they don't
 happen, namely trapping the invalid-operation exception, which Unix will
 translate to SIGFPE.  (Most arm hardware supports the exception, but only
 via sticky bits you can explicitly test with `fetestexcept`, not via
 trapping.)

 I tried running the tests with tinytest.c modified to do
 `feenableexcept(FE_INVALID)` first thing in tinytest_main (needs `#define
 _GNU_SOURCE` and `#include <fenv.h>`).  This turned up only one invalid
 operation in the tests: the logsumexp in test_stochastic_geometric_impl
 slightly exceeds zero, so log1mexp performs an invalid operation (log of
 negative); it is safe to replace `log1mexp(logsumexp(...))` here by
 `log1mexp(fmin(0, logsumexp(...)))` to avoid this.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/29527#comment:7>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online