Skip to content
Snippets Groups Projects
New look
  • View options
  • View options

    • Activity

    • All activity
    • Comments only
    • History only
    • Newest first
    • Oldest first
    • teor changed milestone to %Tor: 0.4.0.x-final
    • teor added 040-backport 040-must asn-merge component::core tor/tor milestone::Tor: 0.4.0.x-final nickm-merge owner::teor priority::high regression resolution::fixed reviewer::nickm severity::normal sponsor::2-can status::closed teor-merge tor-ci tor-test type::defect was-merged-to-041-after-29298 labels
    • T
      teor @teor

      I opened #29528 (moved) to fix the general case: we should fail on sanitizer errors.

      Trac:
      Keywords: N/A deleted, tor-test added

    • T
      teor @teor

      There are actually more of these than I thought:

      prob_distr/logit_logistics: [forking] ../src/lib/math/prob_distr.c:427:26: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:427:26 in 
../src/lib/math/prob_distr.c:344:17: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:344:17 in 
OK
prob_distr/log_logistic: [forking] ../src/test/test_prob_distr.c:496:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:496:5 in 
../src/test/test_prob_distr.c:496:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:496:5 in 
../src/test/test_prob_distr.c:497:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:497:5 in 
../src/test/test_prob_distr.c:497:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:497:5 in 
../src/test/test_prob_distr.c:498:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:498:5 in 
../src/test/test_prob_distr.c:498:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:498:5 in 
../src/test/test_prob_distr.c:499:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:499:5 in 
../src/test/test_prob_distr.c:499:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:499:5 in 
../src/test/test_prob_distr.c:500:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:500:5 in 
../src/test/test_prob_distr.c:500:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:500:5 in 
../src/test/test_prob_distr.c:501:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:501:5 in 
../src/test/test_prob_distr.c:501:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:501:5 in 
../src/test/test_prob_distr.c:508:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:508:5 in 
../src/test/test_prob_distr.c:508:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:508:5 in 
../src/test/test_prob_distr.c:509:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:509:5 in 
../src/test/test_prob_distr.c:509:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:509:5 in 
../src/test/test_prob_distr.c:510:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:510:5 in 
../src/test/test_prob_distr.c:510:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:510:5 in 
../src/test/test_prob_distr.c:511:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:511:5 in 
../src/test/test_prob_distr.c:511:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:511:5 in 
../src/test/test_prob_distr.c:512:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:512:5 in 
../src/test/test_prob_distr.c:512:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:512:5 in 
../src/test/test_prob_distr.c:513:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:513:5 in 
../src/test/test_prob_distr.c:513:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:513:5 in 
../src/test/test_prob_distr.c:553:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:553:5 in 
../src/lib/math/prob_distr.c:685:27: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:685:27 in 
../src/test/test_prob_distr.c:553:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:553:5 in 
../src/test/test_prob_distr.c:554:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:554:5 in 
../src/test/test_prob_distr.c:554:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:554:5 in 
../src/test/test_prob_distr.c:555:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:555:5 in 
../src/test/test_prob_distr.c:555:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:555:5 in 
../src/test/test_prob_distr.c:556:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:556:5 in 
../src/test/test_prob_distr.c:556:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:556:5 in 
../src/test/test_prob_distr.c:557:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:557:5 in 
../src/test/test_prob_distr.c:557:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:557:5 in 
../src/test/test_prob_distr.c:558:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:558:5 in 
../src/test/test_prob_distr.c:558:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:558:5 in 
../src/test/test_prob_distr.c:559:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:559:5 in 
../src/test/test_prob_distr.c:559:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:559:5 in 
../src/test/test_prob_distr.c:560:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:560:5 in 
../src/test/test_prob_distr.c:560:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:560:5 in 
../src/test/test_prob_distr.c:561:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:561:5 in 
../src/test/test_prob_distr.c:561:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:561:5 in 
../src/test/test_prob_distr.c:568:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:568:5 in 
../src/lib/math/prob_distr.c:1170:20: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:1170:20 in 
../src/test/test_prob_distr.c:568:5: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/test/test_prob_distr.c:568:5 in 
OK
prob_distr/weibull: [forking] OK
prob_distr/genpareto: [forking] ../src/lib/math/prob_distr.c:814:23: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:814:23 in 
../src/lib/math/prob_distr.c:837:23: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/lib/math/prob_distr.c:837:23 in 
OK
    • George Kadianakis
      George Kadianakis @asn

      Trac:
      Cc: mikeperry, asn to mikeperry, asn, riastradh

    • Nick Mathewson
      Nick Mathewson @nickm

      Trac:
      Priority: Medium to High

    • Nick Mathewson
      Nick Mathewson @nickm

      For me this happens on linux too, with clang and --enable-fragile-hardening

    • Nick Mathewson
      Nick Mathewson @nickm

      Marking tickets as 040-must based on triage with dgoulet.

      Trac:
      Keywords: N/A deleted, 040-must added

    • R
      riastradh @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.

      (The issue in test_stochastic_geometric_impl does not invalidate any of the test results: the NaN it produced without exceptions trapped was never used again in the subsequent computation, because it should have been an effectively zero probability (less than e^-100^ = 2^-144^ or something) and the corresponding count is always zero in tests as it should be, so psi_test ignores the probability. If the count were ever nonzero, indicating a broken geometric sampler, psi would be computed as a NaN and the psi test would fail. So floating-point arithmetic once again does the right thing in the end, though it still would probably be better to use log1mexp(fmin(0, logsumexp(...))).)

    • R
      riastradh @riastradh

      test_circuitpadding.c, helper_circpad_circ_distribution_machine_setup has the following comment:

      /** Helper function: Initializes a padding machine where every state uses the
 *  uniform probability distribution.  */

      However, it proceeds to set up several other distributions with nonsensical and/or ignored parameters:

        zero_st->iat_dist.type = CIRCPAD_DIST_UNIFORM;
  zero_st->iat_dist.param1 = min;
  zero_st->iat_dist.param2 = max;
...
  first_st->iat_dist.type = CIRCPAD_DIST_LOGISTIC;
  first_st->iat_dist.param1 = min;
  first_st->iat_dist.param2 = max;
...
  second_st->iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;
  second_st->iat_dist.param1 = min;
  second_st->iat_dist.param2 = max;
...
  third_st->iat_dist.type = CIRCPAD_DIST_GEOMETRIC;
  third_st->iat_dist.param1 = min;
  third_st->iat_dist.param2 = max;
...
  fourth_st->iat_dist.type = CIRCPAD_DIST_WEIBULL;
  fourth_st->iat_dist.param1 = min;
  fourth_st->iat_dist.param2 = max;
...
  fifth_st->iat_dist.type = CIRCPAD_DIST_PARETO;
  fifth_st->iat_dist.param1 = min;
  fifth_st->iat_dist.param2 = max;

      Is this intended? (Here min=0 and max=10 in the solitary call site, which might explain the geometric and Weibull distributions with zero parameters.)

    • T
      teor @teor

      Replying to riastradh:

      ...

      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.

      (The issue in test_stochastic_geometric_impl does not invalidate any of the test results: the NaN it produced without exceptions trapped was never used again in the subsequent computation, because it should have been an effectively zero probability (less than e^-100^ = 2^-144^ or something) and the corresponding count is always zero in tests as it should be, so psi_test ignores the probability. If the count were ever nonzero, indicating a broken geometric sampler, psi would be computed as a NaN and the psi test would fail. So floating-point arithmetic once again does the right thing in the end, though it still would probably be better to use log1mexp(fmin(0, logsumexp(...))).)

      Ok, let's fix these issues in this ticket? #29528 (moved) deals with the general case.

    • T
      teor @teor

      From https://trac.torproject.org/projects/tor/ticket/29528#comment:3

      There is an open Clang bug for this: https://bugs.llvm.org/show_bug.cgi?id=19535

      Possible workaround: use -fno-sanitize=float-divide-by-zero in addition to -fsanitize=undefined.

      Let's also implement this workaround for the warnings that are obviously not bugs.

    • George Kadianakis
      George Kadianakis @asn

      Thanks for the great analysis in this ticket. Based on the comments here it was quite easy to to write a patch.

      You can see it in https://github.com/torproject/tor/pull/722 Please note that only the last two commits are about this ticket, the others are there because I based the branch on #29298 (moved) to avoid some conflicts in the future.

      The first commit (a64ccf151f) fixes the probability distribution parameters that Riastradh mentioned with bold in comment:7. The second commit (f708055e9f) silences float-divide-by-zero as suggested by #29528 (moved).

      Trac:
      Status: new to needs_review

    • George Kadianakis
      George Kadianakis @asn

      Trac:
      Reviewer: N/A to mikeperry

    • R
      riastradh @riastradh

      Replying to asn:

      The first commit (a64ccf151f) fixes the probability distribution parameters that Riastradh mentioned with bold in comment:7. The second commit (f708055e9f) silences float-divide-by-zero as suggested by #29528 (moved).

      Cool. One suggestion for a change and one comment:

      • It might be helpful if you put a comment on each line describing what the name and purpose of the parameter is, like /* k, shape parameter */, because I can never remember which one goes first and which one goes last.

      • This is the kind of code where the struct weibull dist = { WEIBULL(dist), .k = ..., .lambda = ... } can be much more legible than struct circpad_distribution dist = { .type = CIRCPAD_DIST_WEIBULL, .param1 = ..., .param2 = ... }. (Obviously changing the code to work like that here is more involved than would be warranted, even if you wanted it, for this particular issue, of course.)

    • George Kadianakis
      George Kadianakis @asn

      Replying to riastradh:

      Replying to asn:

      The first commit (a64ccf151f) fixes the probability distribution parameters that Riastradh mentioned with bold in comment:7. The second commit (f708055e9f) silences float-divide-by-zero as suggested by #29528 (moved).

      Cool. One suggestion for a change and one comment:

      • It might be helpful if you put a comment on each line describing what the name and purpose of the parameter is, like /* k, shape parameter */, because I can never remember which one goes first and which one goes last.

      Agreed! I pushed a fixup that tries to do this: https://github.com/torproject/tor/pull/722/commits/5b616a4831979bf25ad3429b0673c00f2757dd25

      • This is the kind of code where the struct weibull dist = { WEIBULL(dist), .k = ..., .lambda = ... } can be much more legible than struct circpad_distribution dist = { .type = CIRCPAD_DIST_WEIBULL, .param1 = ..., .param2 = ... }. (Obviously changing the code to work like that here is more involved than would be warranted, even if you wanted it, for this particular issue, of course.)

      Agreed. Let's not try to do this in this bugfix ticket but we can probably do it in 041 as part of #28636 (moved): https://trac.torproject.org/projects/tor/ticket/28636#comment:13

    • Mike Perry
      Mike Perry @mikeperry

      Little nervous about disabling divide by zero sanitation across all of Tor for this code, but it's not actually undefined behavior, so it's probably ok.

      Thought I should still just flag that for Nick in case he wants to hack autoconf to apply -fno-sanitize=float-divide-by-zero to just this c file somehow.

      Trac:
      Status: needs_review to merge_ready

    • Nick Mathewson
      Nick Mathewson @nickm

      I'm fine with -fno-sanitize=float-divide-by-zero globally. Should I wait until #29298 (moved) is merged to merge this branch?

    • George Kadianakis
      George Kadianakis @asn

      Replying to nickm:

      I'm fine with -fno-sanitize=float-divide-by-zero globally. Should I wait until #29298 (moved) is merged to merge this branch?

      That'd be cool and make things easier if possible.

      Otherwise, let me know and I can make a branch based on master (but then I would need to make a different branch for #29298 (moved)).

    • T
      teor @teor

      Trac:
      Sponsor: N/A to Sponsor2-can

    Loading Loading Loading Loading Loading Loading Loading Loading Loading Loading