Handle extreme values better in add_laplace_noise()
We think it's impossible to get values this large, but we should still check for them and handle them appropriately.
Activity
changed milestone to %Tor: unspecified
The comment on
get_max_safe_noiseseems to be unfinished;get_min_safe_noiseneeds documentation.Otherwise, looks okay to me, but you know the math here better than I do. Is there a math reviewer you'd recommend for the math changes, or shall we just merge it in once those comments are ready?
Trac:
Status: needs_review to needs_revisionPlease see the fixups in my bug23523 branch, they:
- re-format a comment for style and line length, and remove a unicode character
- expand the comments on the new functions, use the correct integer type, and handle unusually large mantissa lengths
- add a missing semicolon
I would recommend catalyst as a reviewer, they are good with fiddly math. Or maybe isis? (I am looking forward to a future where we can write code like this in a language that does its own integer checks, and has built-in saturating arithmetic functions.)
Trac:
Status: needs_revision to needs_reviewI'm still looking over this. One thing that sticks out is that the comment in
get_min_safe_noise()is inaccurate and caused me to misinterpret what it's actually doing on platforms withDBL_MANT_DIGless than 64. It might be more correct to say "This is always safe, because floating point numbers are sign-magnitude and the negation of an exact number is also exact."Replying to catalyst:
I'm still looking over this. One thing that sticks out is that the comment in
get_min_safe_noise()is inaccurate and caused me to misinterpret what it's actually doing on platforms withDBL_MANT_DIGless than 64. It might be more correct to say "This is always safe, because floating point numbers are sign-magnitude and the negation of an exact number is also exact."All the types here are int64_t.
But I agree the comment is confusing, particularly after I added a case that actually returns +/-INT64_MAX.
Let's change it to:
tor_assert(get_max_safe_noise() >= 0); /* This is safe as long as get_max_safe_noise() is in 0..INT64_MAX, because -INT64_MAX..0 are representable as an int64_t. */ return -get_max_safe_noise();Trac:
Status: needs_review to needs_revisionAlso, a close reading of the proof in section 5.2 of the paper 0 shows that it only applies up to 2^46^, not 2^53^. So we need to define a constant and use that instead. And I think we should error out on platforms that don't have mantissas of 2^53^.
(How do we report numbers greater than 2^46^? We increase the sensitivity of the signal. Practically, this means we multiply the final noise by a scaling factor 2^N^, clear the N lowest bits of the signal, and add them together. We have to clear the signal bits, otherwise signals of 0 are biased, because they only occur half as often. This is what we tried to do by rounding the hidden service counts to the nearest figure, but it's not implemented correctly.)
We should revise or close these tickets based on Appendix C in the latest privcount-shamir spec:
https://github.com/teor2345/privcount_shamir/blob/noise-limits/doc/xxx-privcount-with-shamir.txt
The good news is that we probably don't need to care about extreme values or binning, because properly implemented noise has known limits, and doesn't need binning.
Trac:
Parent: #23061 (moved) to #25263 (moved)We should fix these issues by migrating these statistics to PrivCount in Tor. See #25263 (moved) and its parents for details.
Trac:
Status: needs_revision to assigned
Owner: teor to N/Amoved to tpo/core/tor#23523 (closed)