Opened 17 months ago
Last modified 4 months ago
#23523 assigned defect
Handle extreme values better in add_laplace_noise()
Reported by: | teor | Owned by: | |
---|---|---|---|
Priority: | Medium | Milestone: | Tor: unspecified |
Component: | Core Tor/Tor | Version: | Tor: 0.2.6.2-alpha |
Severity: | Normal | Keywords: | tor-relay, privcount, review-group-24, 034-triage-20180328, 034-removed-20180328 |
Cc: | catalyst | Actual Points: | |
Parent ID: | #25263 | Points: | 0.5 |
Reviewer: | catalyst | Sponsor: | SponsorQ |
Description
We think it's impossible to get values this large, but we should still check for them and handle them appropriately.
Child Tickets
Change History (19)
comment:1 Changed 17 months ago by
Milestone: | Tor: 0.3.2.x-final → Tor: 0.3.3.x-final |
---|---|
Status: | new → needs_review |
Version: | Tor: 0.2.2.14-alpha → Tor: 0.2.6.2-alpha |
comment:3 Changed 16 months ago by
Sponsor: | → SponsorQ |
---|
comment:4 Changed 16 months ago by
Status: | needs_review → needs_revision |
---|
The comment on get_max_safe_noise
seems to be unfinished; get_min_safe_noise
needs 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?
comment:5 Changed 16 months ago by
Status: | needs_revision → needs_review |
---|
Please 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.)
comment:7 Changed 16 months ago by
Cc: | catalyst added |
---|---|
Reviewer: | → catalyst |
comment:9 Changed 16 months ago by
Status: | assigned → needs_review |
---|
comment:10 follow-up: 11 Changed 16 months ago by
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 with DBL_MANT_DIG
less 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."
comment:11 Changed 16 months ago by
Status: | needs_review → needs_revision |
---|
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_DIG
less 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();
comment:12 Changed 16 months ago by
Also, a close reading of the proof in section 5.2 of the paper [0] shows that it only applies up to 246, not 253.
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 253.
(How do we report numbers greater than 246?
We increase the sensitivity of the signal.
Practically, this means we multiply the final noise by a scaling factor 2N, 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.)
[0]: https://pdfs.semanticscholar.org/2f2b/7a0d5000a31f7f0713a3d20919f9703c9876.pdf
comment:13 Changed 15 months ago by
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.
comment:14 Changed 13 months ago by
Milestone: | Tor: 0.3.3.x-final → Tor: 0.3.4.x-final |
---|
Moving most of my assigned tickets to 0.3.4
comment:15 Changed 12 months ago by
Parent ID: | #23061 → #25263 |
---|
comment:16 Changed 11 months ago by
Keywords: | 034-triage-20180328 added |
---|
comment:17 Changed 11 months ago by
Keywords: | 034-removed-20180328 added |
---|
Per our triage process, these tickets are pending removal from 0.3.4.
comment:18 Changed 10 months ago by
Milestone: | Tor: 0.3.4.x-final → Tor: unspecified |
---|
These needs_revision, tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if somebody does the necessary revision.
comment:19 Changed 4 months ago by
Owner: | teor deleted |
---|---|
Status: | needs_revision → assigned |
We should fix these issues by migrating these statistics to PrivCount in Tor.
See #25263 and its parents for details.
Please see my branch bug23523.