Opened 19 months ago

Last modified 7 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 19 months ago by teor

Milestone: Tor: 0.3.2.x-finalTor: 0.3.3.x-final
Status: newneeds_review
Version: Tor: 0.2.2.14-alphaTor: 0.2.6.2-alpha

Please see my branch bug23523.

comment:2 Changed 18 months ago by nickm

Keywords: review-group-24 added

review-group-24 is now open.

comment:3 Changed 18 months ago by nickm

Sponsor: SponsorQ

comment:4 Changed 18 months ago by nickm

Status: needs_reviewneeds_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 18 months ago by teor

Status: needs_revisionneeds_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:6 Changed 18 months ago by teor

(I also added a changes file to the branch)

comment:7 Changed 18 months ago by catalyst

Cc: catalyst added
Reviewer: catalyst

comment:8 Changed 18 months ago by nickm

Owner: set to teor
Status: needs_reviewassigned

setting owner

comment:9 Changed 18 months ago by nickm

Status: assignedneeds_review

comment:10 Changed 18 months ago by 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 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 in reply to:  10 Changed 18 months ago by teor

Status: needs_reviewneeds_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 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."

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 18 months ago by teor

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 17 months ago by teor

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 15 months ago by teor

Milestone: Tor: 0.3.3.x-finalTor: 0.3.4.x-final

Moving most of my assigned tickets to 0.3.4

comment:15 Changed 14 months ago by teor

Parent ID: #23061#25263

comment:16 Changed 13 months ago by nickm

Keywords: 034-triage-20180328 added

comment:17 Changed 13 months ago by nickm

Keywords: 034-removed-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

comment:18 Changed 13 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: 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 7 months ago by teor

Owner: teor deleted
Status: needs_revisionassigned

We should fix these issues by migrating these statistics to PrivCount in Tor.
See #25263 and its parents for details.

Note: See TracTickets for help on using tickets.