Opened 4 months ago

Closed 5 weeks ago

#28142 closed enhancement (fixed)

Merge original WTF-PAD branch

Reported by: asn Owned by: mikeperry
Priority: Medium Milestone: Tor: 0.4.0.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: wtf-pad, tor-relay, tor-cell, padding
Cc: nickm Actual Points:
Parent ID: #28631 Points:
Reviewer: asn Sponsor: Sponsor2

Description

This is a roadmap item for merging Mike's original WTF-PAD branch upstream. It's the first step to completing the WTF-PAD project.

Child Tickets

Attachments (3)

float-warn.patch (4.9 KB) - added by riastradh 3 months ago.
patch to commit a9f511ddd5bf5e57c159a21b3bbe0203412bc04a on asn-d6/adaptive_padding-prob-distr-tests to work around -Wfloat-equal, -Wfloat-conversion
patches.mbox (137.7 KB) - added by riastradh 3 months ago.
miscellaneous patches on top of de7b56e0d0ecf44f291c6159d2ff30defafea616
epsilon-note.patch (2.1 KB) - added by riastradh 3 months ago.
minor clarification of what epsilon means here and in general

Download all attachments as: .zip

Change History (40)

comment:1 Changed 4 months ago by asn

Status: newneeds_revision

Currently in needs_revision as Mike fixes the branch after the Mexico review.

comment:2 Changed 4 months ago by mikeperry

Status: needs_revisionneeds_review

https://github.com/torproject/tor/pull/439

I rebased everything onto 0.3.6 and organized the commits in a similar order to how we reviewed in Mexico. Strongly recommend reviewing it in commit order.

WARNING: The github PR UI is showing the commits in timestamp or some other random ordering. Reviewing in commit hash order is best. I have no idea how to change the github ordering. :/

Last edited 4 months ago by mikeperry (previous) (diff)

comment:3 Changed 4 months ago by dgoulet

Keywords: tor-relay tor-cell padding added
Owner: set to mikeperry
Reviewer: asn
Status: needs_reviewassigned
Type: defectenhancement

comment:4 Changed 4 months ago by asn

I started doing the review, and I put some general comments in github. I'm far from done.

I also started testing it with chutney and it seems to work pretty nicely. I have some local changes that add some extra logs, but I'm gonna push them after I do more testing.

Mike, you have any tips for more effective testing of this feature?

comment:5 Changed 4 months ago by asn

Status: assignedneeds_review

comment:6 Changed 4 months ago by mikeperry

Cc: nickm added

Ok, fresh squashed PR for nickm: https://github.com/torproject/tor/pull/461

Nickm -- the branch's commits are in recommended review order. Note that github reorders them by timestamp in its UI, which is not the right order to look at it. The right order is in the git hash-parent history.

Here's the latest proposal, updated to cover this branch. Section 3 and onward is the relevant bit. Section 2 is about netflow negotiation: https://github.com/asn-d6/torspec/blob/circuitpadding-proposal-updates/proposals/254-padding-negotiation.txt#L78

I would read that first, then the PR in commit order (starting with the header).

comment:7 Changed 4 months ago by asn

I have continued the review of this branch.
I think I have reviewed about 75% of the actual code.

The main parts I haven't reviewed are the various token removal logic functions which are quite complicated.

comment:8 Changed 3 months ago by nickm

Milestone: Tor: 0.3.6.x-finalTor: 0.4.0.x-final

Tor 0.3.6.x has been renamed to 0.4.0.x.

comment:9 Changed 3 months ago by asn

The last few days I've been focusing on using Riastradh's better probability distribution formulas as part of circuitpadding. Current work can be found in https://github.com/torproject/tor/pull/533.

Next steps in this area:

  • Fix the remaining compiler warnings.
  • Figure out if we want to keep the stochastic tests or not. Need to understand more about their failure rates, and also they are quite slow. Maybe I can put them into the slow test category which AFAIK is not run by the CI. We still get to run the numerical tests. Moved stochastic warnings to test-slow. I will open a ticket to figure out what to do about them.
  • Address various XXXs (e.g. geometric distr needs to conform to the API as well). Resolved a few of them, the rest we can open tickets for.
  • Do further documentation.
  • Ensure that the API consumer circpad_distribution_sample() works well in terms of using the prob distributions correctly. Added a basic test for uniform distribution circuit padding delay sampling.
  • Fix coding style of prob distr code because it's different from Tor's and make check-spaces is freaking out.
  • The new files were ported to Tor quite hastily. Ensure that they are proper wrt header file etc. Also fix the copyrights etc.

All remaining tasks above have been resolved. I pushed the code in `adaptive_padding-prob-distr-tests` and pending review from Riastradh. After review has been done, I will squash into something presentable along with the rest of the #28142 branch. I will also open some tickets for leftover optional work in this area.

Last edited 3 months ago by asn (previous) (diff)

Changed 3 months ago by riastradh

Attachment: float-warn.patch added

patch to commit a9f511ddd5bf5e57c159a21b3bbe0203412bc04a on asn-d6/adaptive_padding-prob-distr-tests to work around -Wfloat-equal, -Wfloat-conversion

comment:10 Changed 3 months ago by riastradh

I attached a patch to address all the -Wfloat-equal and -Wfloat-conversion warnings.

I didn't address -Wbad-function-casts; if you really want to appease the warning at the expense of code clarity, you can just replace each case of

integer-type y = (integer-type)floor(f(x));

by the clumsier

double yd = floor(f(x));
integer-type y = (integer-type)yd;
Last edited 3 months ago by riastradh (previous) (diff)

comment:11 Changed 3 months ago by riastradh

FYI: a part of this work, namely the uniform [0,1] sampler used throughout, is echoed in #23061. Just letting you know in case you want to avoid the duplication sooner rather than later.

Changed 3 months ago by riastradh

Attachment: patches.mbox added

miscellaneous patches on top of de7b56e0d0ecf44f291c6159d2ff30defafea616

comment:12 Changed 3 months ago by riastradh

I attached some patches to:

  • reindent the code according to my understanding of tor's indentation style, since it had been getting a little inconsistent;
  • address one of the questions in https://github.com/torproject/tor/pull/533, and re-enable some related tests that were mistakenly disabled;
  • use separate functions for floor and ceiling instead of one with a boolean parameter; and
  • convert assert to tor_assert.

With these patches, the only remaining complaints from make check are:

  • lines that are too long because they contain URLs that are too long; and
  • includes that are not allowed because of missing .may_include or something.

I'm not sure what the best way to address these is -- break the URLs, or add an override; update .may_include, or move files around -- so I'll leave that up to you folks to decide.

Changed 3 months ago by riastradh

Attachment: epsilon-note.patch added

minor clarification of what epsilon means here and in general

comment:13 Changed 3 months ago by asn

Parent ID: #28631

comment:14 Changed 3 months ago by asn

OK, the current state of things can be found here: https://github.com/torproject/tor/pull/547

It's basically the PR#461 branch, rebased to latest master, plus Riastradh's probability distribution work, plus the other tests I wrote.

Here are the remaining tasks that we should address to close this:

  • Go through the remaining GH review comments.
  • Disable the current machine so that we don't merge it as on-by-default.

After this we can give it back to Nick for another round of review.

Mike, when you come back can you start crunching through the list of unittests apart from the two I mentioned above? And also perhaps go through the GH PR#461 review for more unanswered points? And also check the pull request above to see the integration of Riastradh's work? Let's also meet in IRC at some point to coordinate further.

Last edited 3 months ago by asn (previous) (diff)

comment:15 Changed 3 months ago by mikeperry

Ok I looked at the branches a bit.. One issue is that there are a fair amount of fixups I still need to do for Nick's remaining comments on PR#461.. So I'm trying to decide how to do them. For sanity/cleanliness I think the answer is to squash everything down in PR#547 into a fresh PR, and do the fixups for Nick from PR#461 on top of that branch. There is the question of how to handle the new commits you're adding asn, to make those easy for Nick to review. Some of them look like they could be squashed back into circuitpadding.c. The test ones can probably remain their own commit.

Do you have any other preference for how to do this? Or want to reorg the branch how you prefer? Otherwise I will do that my tomorrow.

comment:16 in reply to:  15 Changed 3 months ago by asn

Replying to mikeperry:

Ok I looked at the branches a bit.. One issue is that there are a fair amount of fixups I still need to do for Nick's remaining comments on PR#461.. So I'm trying to decide how to do them. For sanity/cleanliness I think the answer is to squash everything down in PR#547 into a fresh PR, and do the fixups for Nick from PR#461 on top of that branch. There is the question of how to handle the new commits you're adding asn, to make those easy for Nick to review. Some of them look like they could be squashed back into circuitpadding.c. The test ones can probably remain their own commit.

Hey Mike, good to have you back, hope the off days were good.

I agree that the right thing to do is squash up PR#547 and start building from there.
Perhaps for the extra commits that I added we can leave them as is for the purposes of the next nickm review, and squash them into circuitpadding etc. after that review.

For now, I keep on working on testing the remaining remove token functions.

comment:17 Changed 3 months ago by mikeperry

Ok I squashed this as https://github.com/mikeperry-tor/tor/tree/adaptive_padding-rebased_0.3.6-pr547-squashed -- same as head 56376125a42de88bd57240551f7a76f5219fc455 from pr547.

Definitely easier to look at git logs for. Hopefully not too confusing for Nick. And hopefully we don't step on eachother. I have a looot of fixups for circuitpadding.c to do. If you end up modifying that file lmk.

I'm also in the process of making more typedefs and tighter precise int_t usage for the various integer types we use, for clarity and to reduce type confusion/sign errors/overflow risk. That may end up touching some tests. When I get there, I'll let you know. Probably Monday.

comment:18 Changed 3 months ago by asn

Hello, pushed three test commits in https://github.com/torproject/tor/pull/547.

The tests cover the remaining removal token functions that were not covered, and also give a bit more coverage to the global rate limiting test (based on coverage analysis).

comment:19 Changed 3 months ago by asn

Hey Mike, I saw your comment on the meeting pad yesterday. I see you have one or two fixups remaining. So let's do the following: Finish with your fixups, push your branch, (update the PR if needed), and we can switch: I will take your branch and start doing fixups based on PR#461, and you can start writing unittests and increasing coverage. Let me know when we can do the switch.

comment:20 Changed 3 months ago by mikeperry

Ok I did the fixup with the type clarifications. It's at https://github.com/mikeperry-tor/tor/tree/adaptive_padding-rebased_0.3.6-pr547-squashed still.

It looks like you've been force-pushing to that PR. The head I used (56376125a42de88bd57240551f7a76f5219fc455) is now gone. and I have conflicts from my fixup (its extensive due to type renaming -- which is why I wanted it done before we switched). It looks like 56376125a42de88bd57240551f7a76f5219fc455 is 4bf714c9355254e788db886b0fd7da8cedae0822.

Might not be able to fix the conflicts until tomorrow. In the future, try not to force push (tho that would not have helped the conflicts.. we just collided changesets).

comment:21 in reply to:  20 Changed 3 months ago by asn

Replying to mikeperry:

Ok I did the fixup with the type clarifications. It's at https://github.com/mikeperry-tor/tor/tree/adaptive_padding-rebased_0.3.6-pr547-squashed still.

It looks like you've been force-pushing to that PR. The head I used (56376125a42de88bd57240551f7a76f5219fc455) is now gone. and I have conflicts from my fixup (its extensive due to type renaming -- which is why I wanted it done before we switched). It looks like 56376125a42de88bd57240551f7a76f5219fc455 is 4bf714c9355254e788db886b0fd7da8cedae0822.

Might not be able to fix the conflicts until tomorrow. In the future, try not to force push (tho that would not have helped the conflicts.. we just collided changesets).

Oof sorry about this. I had to rebase to master because some of the probability distribution work was using stuff from master (#28193), but I shouldn't have force pushed into the useful PR. Please let me know if there is anything I can do to help you with declogging the conflict resolution.

FWIW, I started doing fixups from PR461. Some of them are quite heavy (e.g. https://github.com/torproject/tor/pull/461#discussion_r231893260) so I'm gonna wait until you address the conflicts and finish up the branch before doing those, to avoid more conflict hell. Then I will start applying the fixups, and you can start doing the tests, and after that I will take care of the conflict resolution between our two branches.

BTW, there are a few non-fixup related questions in PR461 that I would like help with. I will resolve the fixup stuff in PR461 soon, and only leave the questions hanging, so that you can roll through them.

cheers!

comment:22 Changed 2 months ago by mikeperry

OK! Phew. https://github.com/mikeperry-tor/tor/tree/adaptive_padding-rebased_0.3.6-pr547-squashed is now the same as https://github.com/torproject/tor/pull/547 (head 7b65aba210f62b3527782705ba867f6ce4a57088) with the type changes. Plus a couple tweaks. I think, anyway.

comment:23 in reply to:  22 Changed 2 months ago by asn

Replying to mikeperry:

OK! Phew. https://github.com/mikeperry-tor/tor/tree/adaptive_padding-rebased_0.3.6-pr547-squashed is now the same as https://github.com/torproject/tor/pull/547 (head 7b65aba210f62b3527782705ba867f6ce4a57088) with the type changes. Plus a couple tweaks. I think, anyway.

Great! Please see https://github.com/torproject/tor/pull/573 where I pushed fixups to all the open comments in GH PR#461, and opened tickets (children of #28637) for ones that were too messy to fix right now.

Mike can you please answer this question as well: https://github.com/torproject/tor/pull/461#discussion_r237104250
I think there might be some spec fixes that should be done based on the answer there, that I will do as soon as you answer.

I guess the rest of the work here is on tests.

UPDATE: There seem to be a broken unittest on clang on the branch you pushed (https://github.com/torproject/tor/pull/574), and also some more broken tests on the branch I pushed (https://github.com/torproject/tor/pull/573). I will look into these.

Last edited 2 months ago by asn (previous) (diff)

comment:24 Changed 2 months ago by mikeperry

Ok I fixed the errors in PR 574. They were due to return type mismatched, which caused clang to garble the return value of circpad_histogram_usec_to_bin(). This is now running as https://github.com/torproject/tor/pull/575

If you fix your unit tests, please rebase your stuff on top of PR575, or vice-versa?

As I said on IRC, note that https://github.com/torproject/tor/pull/461 still has some fixup comments from nickm that are currently hidden due to being "outdated" (I think we just changed code near them). They still need fixups tho. I also commented on a couple things in that PR.

After fixups, I think next steps for implementation is making a working machine. See my thoughts in https://trac.torproject.org/projects/tor/ticket/28634#comment:3. You can work on that if you like, after fixups. I can go back to working on tests, since you are tired of that.

comment:25 Changed 2 months ago by asn

OK I took Mike's unittest branch from PR#593 and on top of it I applied my fixups. I pushed two branches: an unsquashed one with all the fixups intact, and a squashed one which is completely squashed down to the base. The two branches should have a git-diff of zero.

I also replied to all the open review comments by Nick on PR#461 by pointing to the unsquashed branch. So after the fixups get validated, we can start working on top of the squashed branch which is cleaner.

If everyone likes the fixups and CI blesses the branches, then I think the next step is to disable/kill the current machine so that the branch can get merged and we can start working off master for good!

comment:26 Changed 8 weeks ago by asn

Hey Mike,

I reviewed your latest adaptive_padding-20181218-rebased and it looks great! On this note I took your branch and did the following changes:

  • Tested the unittests for memleaks with ASAN (all good).
  • Disabled the current machines

and also rebased it to latest master (so that CI runs) and made a PR out of it: https://github.com/torproject/tor/pull/622

Let me know what else there is to do. Otherwise, we should make a squashed version of this branch for the final review and merge by Nick. I can do the squash no problem.

comment:27 Changed 8 weeks ago by mikeperry

Ok I did a couple tweaks:

  • ensure that when negotiation fails, we dont try again
  • change the size of circpad_hist_token_t

I then pushed https://github.com/torproject/tor/pull/623.

I think this is ready for review, though could use a squash.

comment:28 Changed 7 weeks ago by asn

Status: needs_reviewmerge_ready

OK this is now in merge_ready!

Here are the updates:

The final (squashed) branch is in https://github.com/torproject/tor/pull/624.
The identical-but-unsquashed branch is in https://github.com/torproject/tor/pull/623 (as per mike's post above).
Nick's last review comments from PR#461 have been addressed and answered by referencing the commits in PR#623.

This branch is ready to be reviewed & merged. It does not actually enable any machines atm, but let's see if we can fit something in for 040 after we merge this.

comment:29 Changed 6 weeks ago by nickm

Status: merge_readyneeds_revision

Okay, I've been over pr 624. I think it's nearly ready; I just want to double-check a few things with you here. In many cases, just opening a followup ticket and attaching a link should be good enough, though we should talk about "necessary for 0.4.0" vs "can wait".

comment:30 in reply to:  29 Changed 6 weeks ago by asn

Status: needs_revisionneeds_review

Replying to nickm:

Okay, I've been over pr 624. I think it's nearly ready; I just want to double-check a few things with you here. In many cases, just opening a followup ticket and attaching a link should be good enough, though we should talk about "necessary for 0.4.0" vs "can wait".

Thanks for the review.

I went through all the new review comments and provided fixups to most of them.

There is only one comment I'm not sure what to do with, and that's the one about using non-coarse monotime in various places. Feedback would be appreciated: https://github.com/torproject/tor/pull/624#discussion_r246443113

Also, Mike what do you want to do with the TODO file?

Other than that, I think we are good to go here.

comment:31 Changed 6 weeks ago by asn

I pushed a few more commits to adaptive_padding-final that Riastradh authored to improve the prob distr codebase (it now does type checking on the distr macros) and fix a bug and some compilation issues.

I'm still unsure how to handle the monotime issue because I'm not sure what's acceptable in terms of timing accuracy and overhead. Mike has some questions on IRC for you Nick.

comment:32 Changed 6 weeks ago by nickm

Mike has some questions on IRC for you Nick.

I've added a FAQ to compat_time.h, answering those questions as best I can with the info I have.

I think it's okay to leave the time stuff unchanged _for now_, iff it won't be called by default. Otherwise, I think we should define an abstract type to represent "whatever time we're using" so we can switch it easily if we have to.

comment:33 Changed 6 weeks ago by mikeperry

Hrmm.. For monotime, I think my preference would be some kind of check that helps decide which of these time abstractions to use, for optimal accuracy and speed. I also think that its likely that the choices we make for client circuits will be different than for relays. I think clients can sacrifice more speed for accuracy, since their volumes of traffic will be lower.

As for the TODO, we should drop it and make sure it is captured in the tickets.

comment:34 Changed 5 weeks ago by nickm

For monotime, I think my preference would be some kind of check that helps decide which of these time abstractions to use, for optimal accuracy and speed.

I think that might be possible, but it's not going to happen between now and the freeze on the 15th.

Does the current monotime usage happen in the critical path for default tor configurations with this patch? If no, I think we don't have to block on a new monotoime approach. If yes, maybe we can make it conditional on wtf-pad being enabled.

comment:35 in reply to:  34 Changed 5 weeks ago by asn

Replying to nickm:

For monotime, I think my preference would be some kind of check that helps decide which of these time abstractions to use, for optimal accuracy and speed.

I think that might be possible, but it's not going to happen between now and the freeze on the 15th.

Does the current monotime usage happen in the critical path for default tor configurations with this patch? If no, I think we don't have to block on a new monotoime approach. If yes, maybe we can make it conditional on wtf-pad being enabled.

I think we are good here. Because there are currently no machines enabled for any tor configuration, there is no monotime usage happening because of circpadding at all. I verified that by adding log messages to monotime usage and making sure nothing happens from circuitpadding.

comment:36 Changed 5 weeks ago by asn

Status: needs_reviewmerge_ready

All github PR comments have been resolved so putting this back in MR.

comment:37 Changed 5 weeks ago by nickm

Resolution: fixed
Status: merge_readyclosed

Merged to master. Woo!

Note: See TracTickets for help on using tickets.