Remove PathBias use of timestamp_dirty and record usage accounting

Instead of using timestamp_dirty as a signal for "circuit use" in the pathbias code, we should create a dedicated path_state_t state (PATH_STATE_USE_ATTEMPTED).

It's also debatable as to if we should remove the additional timestamp_dirty markings I added in #7157 (moved). The most controversial addition was marking freshly cannibalized circuits as dirty. While this seems to make sense to me (do we really want to use cannibalized circuits for any random stream?), it may have subtle impacts on the proper use of GENERAL purpose circuits that get cannibalized during predictive circuit building or other cases involving hidden services.

changed milestone to %Tor: 0.2.4.x-final

added MikePerry201301 actualpoints::15 component::core tor/tor milestone::Tor: 0.2.4.x-final parent::7755 priority::medium resolution::implemented status::closed type::enhancement labels

Trac:
Parent: N/A to #7755 (moved)

When I do this, I think I should also record circuit usage attempt counts in the state file. This means adding another field to the EntryGuardPathBias state file line to say how many circuit usage attempts there were for each guard..

Further down the line, depending on what sort of results we see in the field, we then can set thresholds on these values.

The reason to do this is because the adversary might get a bonus by allowing circuits to build that go unused while only failing the usage attempts. Since I suspect most normal clients build way more circuits than they actually try to use, this difference might be substantial.

Trac:
Summary: Remove PathBias use of timestamp_dirty to Remove PathBias use of timestamp_dirty and record usage accounting

Trac:
Keywords: MikePerry201212 deleted, MikePerry201301 added

How much of this ticket is "fix path selection (or stream allocation) behavior", and how much is "make our path bias detection stuff cleaner"?

Assuming PathBiasDisableRate (if I have my names correct, #7982 (moved)) is disabled in 0.2.4, it seems like the latter isn't as critical as the former, yes? (Since Nick is getting stressed about fitting everything in)

arma: mikeperry/bug7802 contains both.

I refactored the stream accounting stuff to record separate stream usage statistics; improved the path state machine and added some safeguards to state transitions and record keeping; eliminated reliance on timestamp_dirty; and fixed a couple of edge cases I found during testing that also apply to the previous code.

I've again put the branch through several thousand hidden service client and server streams, wget fetches, DNS resolves, and unreachable host connect attempts during the course of this development, and am still stress testing it now.

Trac:
Actualpoints: N/A to 12
Status: new to needs_review

If you've pulled this branch already, I may have committed the mortal sin of rebasing it since your pull. I accidentally pushed a commit that should have been an auto-squash, which I corrected by rebasing. I won't do that again.

The commit hash you're looking for is b810d322bfc55d202dbbd2e8ebe4529cf0778c8b, but I may toss some more autosquash commits on top of that if I notice any more issues.

Trac:
Actualpoints: 12 to 15

Is there any subset of these that could be done for a minimal version? This is a 1300 line diff and a 1700 line patch series. It's a lot of changed code.

If not, what is the most rigorous, specific explanation of what this code is supposed to do?

Replying to nickm:

Is there any subset of these that could be done for a minimal version? This is a 1300 line diff and a 1700 line patch series. It's a lot of changed code.

Most of the changes are refactoring that should both improve readability and future-proof the state machine against bitrot.

If not, what is the most rigorous, specific explanation of what this code is supposed to do?

The only substantial functional change is to provide separate tunable limits for the acceptable rate of circuit use failure before we emit log messages. A circuit use failure is defined as a built circuit for which any streams detach and that we are also unable to probe successfully.

The separate use failure accounting is actually limited to changes to just a couple of functions: pathbias_check_use_rate(), and writing two counter variables to the state file as EntryGuardPathUseBias.

All of the other circuit use state transitions and probing code were already there. I just cleaned things up to remove dependence upon timestamp_dirty and improve/guard the state machine transitions, and refactor some common code into helper functions.

#7804 (moved) is my ticket to document all of the path bias stuff in path-spec.txt.

Just when you're not looking, git can rear up and bite you.

This branch got merged, squash! commits and all, when andrea was trying to merge the #8024 (moved) fix alone. So we had to decide whether to revert or whether to call it "good enough for now".

We just did a little^W pretty thorough emergency post-merge review, and stuff looks basically okay. Closing this and #8024 (moved); Andrea is opening a new ticket with the issues we found during review.

Trac:
Resolution: N/A to implemented
Status: needs_review to closed

Replying to nickm:

Andrea is opening a new ticket with the issues we found during review.

For the record, this was #8081 (moved).

closed

added 120h of time spent

mentioned in issue #8024 (moved)

moved to tpo/core/tor#7802 (closed)