Opened 7 months ago

Last modified 3 weeks ago

#32088 needs_revision enhancement

Proposal 310 - choose guards in sampled order

Reported by: Jaym Owned by:
Priority: High Milestone: Tor: 0.4.4.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-spec prop271 prop310
Cc: Actual Points:
Parent ID: Points:
Reviewer: nickm, asn Sponsor:

Child Tickets

Attachments (1)

0001-Makes-selection-of-filtered-guards-and-primary-guard.patch (7.0 KB) - added by nickm 7 months ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 7 months ago by arma

Component: Core TorCore Tor/Tor
Type: defectenhancement

comment:2 Changed 7 months ago by nickm

Milestone: Tor: 0.4.3.x-final
Status: newneeds_review

comment:3 Changed 7 months ago by dgoulet

Keywords: tor-spec prop271 added
Reviewer: nickm

comment:4 Changed 7 months ago by nickm

Priority: MediumHigh
Status: needs_reviewneeds_revision

Here are some initial comments based on reading the patch and the email, based on the assumption that the email is right, and that the patch does what the email says it should do.

Should next_sampled_idx persist across runs or be recalculated when we load guards? Right now it seems to start at 0 every time Tor starts. Maybe we should also re-calculate the sampled_idx values to be a dense array when we save/load the state, so that we aren't leaking more information than we intend to.

The patch will also need:

  • a short proposal. It can mostly be based on Florentin's email.
  • a patch to guard-spec.txt.
  • tests for the changed behavior.
  • a "changes" file (see doc/HACKING/)
  • editing so that "make check-spaces" passes.
  • Updates to the documentation and names of all the functions whose behavior has changed. (For example, sample_reachable_filtered_entry_guards` no longer does that the function's name implies or the documentation says.)

How much of that do the original authors want to do, and how much should we pick up?

comment:5 Changed 7 months ago by Jaym

woups, yes currently it would start at 0 every time, which is bad. Recalculation based on the last sampled_idx from the state file + 1 should be good.

I would recommend the short proposal to include the required change over the confirmed list (i.e., this list needs sorting by sampled_idx instead of confirmed_idx). So this patch would need to handle that as well.

I am happy to help on writing a small proposal from my email, and I can pick up whatever is left from your bullet list starting from January (I am bit busy for these next two months :/).

Could the proposal includes a kind of "further work" suggestion? Describing the issue that Roger wrote in the email thread.

comment:6 Changed 7 months ago by nickm

Could the proposal includes a kind of "further work" suggestion? Describing the issue that Roger wrote in the email thread.

Yes, that's fine.

comment:8 Changed 6 months ago by nickm

Status: needs_revisionneeds_review

comment:9 Changed 6 months ago by nickm

Resolution: implemented
Status: needs_reviewclosed

This is now added as proposal 310.

comment:11 Changed 3 months ago by teor

Keywords: prop308 added
Milestone: Tor: 0.4.3.x-finalTor: 0.4.4.x-final
Priority: HighMedium
Resolution: implemented
Status: closedreopened
Summary: Proposal 271 - straightforward improvementsProposal 308 - choose guards in sampled order

I did a small review on this code.

I've looked at entry_guard_parse_from_state(), and I can't work out where we create a dense set of indexes on load. (But I can see where we do it on save.)

Creating a dense set of indexes on load is important, because qsort() is not stable. Therefore, the first time a legacy state is loaded, the guards will be sorted in arbitrary order. And the order may change, every time the sort is performed.

I also wonder if we need to sort the guard list every time we select a guard. Instead, can we keep the list sorted when we add or delete guards?
Appending guards to the end of the list is just smartlist_add(). We have the smartlist_del_keeporder() to remove guards from the list.

comment:12 Changed 3 months ago by teor

Status: reopenedneeds_revision

comment:13 in reply to:  11 Changed 3 months ago by Jaym

Replying to teor:

I did a small review on this code.

I've looked at entry_guard_parse_from_state(), and I can't work out where we create a dense set of indexes on load. (But I can see where we do it on save.)

Creating a dense set of indexes on load is important, because qsort() is not stable. Therefore, the first time a legacy state is loaded, the guards will be sorted in arbitrary order. And the order may change, every time the sort is performed.

I also wonder if we need to sort the guard list every time we select a guard. Instead, can we keep the list sorted when we add or delete guards?
Appending guards to the end of the list is just smartlist_add(). We have the smartlist_del_keeporder() to remove guards from the list.

Yes, so, indeed I forgot to account for existing clients that would load states without any sampled_idx the first time they would use that patch. I need to workout a "fake" sampling order for those clients, or qsort() would not be stable as you mention (I guess taking the confirmed_idx ordering would be a good enough heuristic).

I am going to look closer to your recommendation on ordering. Thanks for your thoughtful review!

comment:14 Changed 3 months ago by Jaym

Hello,

The pull request has been updated.

On loading, Tor sets the sampled_idx to the confirmed_idx. That should keep older clients to behave the same (and not reordering primary guards). On the next state save, the sampled_idx should be made dense.

Also, the patch applies now ordering when it seems necessary (a couple of redundant orderings have been removed).

Also, I was concerned by the fact that Tor assumes integrity of the state when loading it. If some application has write access to this file, making the client rotate guards until a chosen one is found shouldn't be too much of a hard task. Is that kind of threat relevant?

comment:15 Changed 7 weeks ago by gk

Status: needs_revisionneeds_review
Summary: Proposal 308 - choose guards in sampled orderProposal 310 - choose guards in sampled order

comment:16 Changed 7 weeks ago by gk

Keywords: prop310 added; prop308 removed

comment:17 in reply to:  14 Changed 7 weeks ago by teor

Replying to Jaym:

The pull request has been updated.

On loading, Tor sets the sampled_idx to the confirmed_idx. That should keep older clients to behave the same (and not reordering primary guards). On the next state save, the sampled_idx should be made dense.

Also, the patch applies now ordering when it seems necessary (a couple of redundant orderings have been removed).

Thanks!

Also, I was concerned by the fact that Tor assumes integrity of the state when loading it. If some application has write access to this file, making the client rotate guards until a chosen one is found shouldn't be too much of a hard task. Is that kind of threat relevant?

An attacker who can modify files on the local system could do many worse things. So those attacks are not really part of tor's threat model. To defend against those kinds of attacks, people should use an amnesiac system like TAILS.

File corruption is a risk, though. And tor could detect file corruption earlier with checksums. But that's a different ticket :-)

comment:18 Changed 7 weeks ago by nickm

Priority: MediumHigh
Status: needs_reviewneeds_revision

Hi! Initial notes here. Sorry for the delay in the review.

First thing is, continuous integration isn't passing. It looks like there might be a memory leak in the unit tests? You can test that yourself by building with --enable-fragile-hardening and running the tests.

Also there seems to be a practracker failure:

problem file-size /src/feature/client/entrynodes.h 652

You can suppress this warning by editing the scripts/maint/practracker/exceptions.txt file and increasing the number on that line.

The code itself looks well-written and straightforward. I have some suggestions for perhaps making it more robust; I have left them on the github request.

comment:19 Changed 6 weeks ago by Jaym

Status: needs_revisionneeds_review

comment:20 Changed 5 weeks ago by nickm

Status: needs_reviewneeds_revision

Sorry for the delay: the last week or so has been hugely busy.

The changes look good, but CI still isn't passing. It looks like these tests are failing on appveyor:

entrynodes/confirming_guards: [forking] Skipping 1 testcases.
  FAIL ../src/test/test_entrynodes.c:1513: assert(g1->confirmed_idx OP_EQ 0): 2 vs 0
  [confirming_guards FAILED]
entrynodes/confirming_guards_reasonably_future: [forking] Skipping 1 testcases.
  FAIL ../src/test/test_entrynodes.c:1513: assert(g1->confirmed_idx OP_EQ 0): 2 vs 0
  [confirming_guards_reasonably_future FAILED]
entrynodes/confirming_guards_reasonably_past: [forking] Skipping 1 testcases.
  FAIL ../src/test/test_entrynodes.c:1513: assert(g1->confirmed_idx OP_EQ 0): 2 vs 0
  [confirming_guards_reasonably_past FAILED]

I'm also seeing more practracker issues on Travis:

problem function-size /src/feature/client/entrynodes.c:entry_guard_parse_from_state() 272

For this one we should probably look for some code we can extract into a new function, to simplify this function.

comment:21 Changed 5 weeks ago by Jaym

Hello Nick,

Thanks for the review!

Things have been fixed and github looks happy now.

Summary: The problem was apparently due to a qsort() behavior difference between my setup and appveyor running on windows (I wasn't experiencing the failure). Yet, the test was doing something weird; i.e., setting confirmed_idx of different guards to the same value, which is not something that seems ok to test. It means unstable behaviors with sorted lists, and we don't like unstable behaviors :)

I've slightly modified the original test since now the confirmed_guards are sorted by sampled_idx, and it makes sure that the confirmed guards are sorted as expected, with valid confirmed_idx (i.e., not the same).

comment:22 Changed 5 weeks ago by nickm

Status: needs_revisionneeds_review

comment:23 Changed 4 weeks ago by asn

Reviewer: nickmnickm, asn
Status: needs_reviewneeds_revision

Hello, thanks for all the work here! I actually missed the proposal and the ticket so this caught me by surprise today. This seems really well thought all-in-all and a solid patch, and the test adjustments look good to.

I added a few comments to the PR. It's mainly documentation requests to polish some parts that I didn't comprehend.

Also, can the next revision come with a new PR, which contains the changes in the top commits? This can be done with a rebase. Isolating the changes of this PR was not easy for me because the relevant commits were scattered around the log.

Thanks a lot!

comment:24 Changed 4 weeks ago by Jaym

Thanks! rebased on https://github.com/torproject/tor/pull/1873

+ tried to improve based on asn's comments

comment:25 Changed 4 weeks ago by Jaym

Status: needs_revisionneeds_review

comment:26 Changed 3 weeks ago by asn

Hey thanks for the super fast revisions here! I left a comment on the new PR.

Furthermore, I'd be more confidence if we had some more testing here. The test coverage of the branch in terms of LoC is great, but I would also like a test that tests the entire logic of this new feature. In particular, given that the changes are far from trivial, and change various behaviors in the code, I would like a test that tests most of that. In particular, I would be looking for something like: Load some guards to the sampled set (without using a state file), make sure that the sampled set has the sampled idxs correctly set, then create the confirmed set and make sure that's well ordered too, then make the primary guards list and make sure that's well ordered, finally ask for a guard and make sure that's what you would expect. Feel free to reuse code from other unittests of course...

So, before this branch gets merged we would need to do the following two things:

  • Get that unittest in.
  • Answer the comment on the new PR.
  • Get the torspec patch for guard-spec.txt merged.
  • Squash the PR into more organized commits. Ideally this PR would be squashed down to max 3-4 logical commits. Something like the following commit structure would work, but feel free to improvise:
    • Commit 1: Use helper functions parse_from_state_set_vals/parse_from_state_handle_time
    • Commit 2: Implement prop310"
    • Commit 3: Fix existing unittests
    • Commit 4: Add unittests

Thanks a lot for your work! :)

comment:27 Changed 3 weeks ago by asn

Status: needs_reviewneeds_revision
Note: See TracTickets for help on using tickets.