Protover.rs could use a better algorithm

This probably doesn't matter in practice, but: it would be cool if protover.rs used a smarter representation for sets of protocol versions than HashSet.  Maybe a BTreeSet of (low,high) tuples?

changed milestone to %Tor: 0.3.3.x-final in legacy/trac

added 033-included-20180326 in Legacy / Trac 033-must in Legacy / Trac 033-triage-20180326 in Legacy / Trac actualpoints::5 in Legacy / Trac component::core tor/tor in Legacy / Trac milestone::Tor: 0.3.3.x-final in Legacy / Trac owner::isis in Legacy / Trac points::1 in Legacy / Trac priority::very high in Legacy / Trac protover in Legacy / Trac resolution::fixed in Legacy / Trac reviewer::nickm in Legacy / Trac rust in Legacy / Trac security in Legacy / Trac severity::normal in Legacy / Trac sponsor::M-can in Legacy / Trac status::closed in Legacy / Trac type::defect in Legacy / Trac version::tor 0.3.3.1-alpha in Legacy / Trac labels

It does matter in practice - using hashsets to list every supported protocol is a DoS risk: https://trac.torproject.org/projects/tor/ticket/25252#comment:1

Trac:
Points: N/A to 1
Milestone: Tor: unspecified to Tor: 0.3.3.x-final
Keywords: rust deleted, rust 033-must protover added

Trac:
Priority: Medium to High

An ordered vec of ranges would also be fine.

There are better voting algorithms we could use too, so that we could remove the 65536-version limit. I'm attaching a prototype of one such algorithm in Python.

Trac:
Milestone: Tor: 0.3.3.x-final to Tor: 0.3.4.x-final

Trac:
protocol-vote.py

O(n*m) algorithm to compute consensus of n votes containing m protocol ranges each

Assigning some 033-must tickets to myself.

Trac:
Status: new to accepted
Owner: N/A to isis

(FWIW, I think it would be okay to defer this to 0.3.4 if it isn't fast. We can just say "don't use Rust on dirauths yet", right?)

Replying to nickm:

(FWIW, I think it would be okay to defer this to 0.3.4 if it isn't fast. We can just say "don't use Rust on dirauths yet", right?)

I think it really does matter to get it in, even if we advise dirauths against using Rust, due to the potential for DoS that teor mentioned. Wouldn't the attack vector look something like this?:

1. A bad relay with alternate/modified tor implementation says Link 1-65536,LinkAuth 1-65536,Relay 1-65536,HSIntro 1-65536,HSRend 1-65536,HSDir 1-65536,DirCache 1-65536,Desc 1-65536,Microdesc 1-65536,Cons 1-65536.

2. The dirauths parse that in C and allow it.

3. A Rust relay/client gets this consensus and suddenly it's got a HashSet with 10 keys, each one with 65536 32-bit integers in it, so that's 2560.8594 kilobytes allocated per relay that does this. (according to this this tiny rust program)

4. Bad relay operator spins up ~400 relays and suddenly every Rust-enabled relay/client in the network is using over 1 GB of memory.

Trac:
main.rs

Replying to nickm:

(FWIW, I think it would be okay to defer this to 0.3.4 if it isn't fast. We can just say "don't use Rust on dirauths yet", right?)

Although, also yes, we should advise authorities not to use Rust until legacy/trac#24265 (moved) is finished, otherwise we risk splitting the vote.

Okay, I have an WIP (done actually, but I need to split it nicely into commits) implementation in my bug24031 branch.

Warning that I uh… also went a bit nuts on refactoring to have actual types for different things, moving functions into them as methods, and making them more rusty e.g. implementing proper traits like impl std::str::FromStr for ProtoEntry instead of having stuff like SupportedProtocols::from_proto_entries_string. The types are much nicer however, they really helped me reason about the code, and also I found several differences in behaviour to the C (which were due to us not having as much type safety as we could, e.g. if something doesn't parse correctly into a type, we want to make sure we're treating it the same way as when C can't parse it into a proto_entry_t or whatever, instead of just saying "this is a String" and "this is a HashMap").

Caveat emptor that even though I found some differences in return codes/parsing/etc to the C, I'm still not fully convinced there aren't more, and we should definitely do legacy/trac#24265 (moved) soon.

Trac:
Status: accepted to needs_revision

I've cleaned up (mostly! sorry sorry!) my code into more understandable commits in my bug24031_r4 branch.

The changes to the unittests might be a little hard to follow, that commit is not quite pleasant (although the integration test changes in that same commit should be simple to follow to see where/when behaviour has changed, so I'd argue that the internal unittests changing precariously isn't as much of an issue?). If test changes (or any changes) are difficult for the reviewer to understand, please feel free to ask questions, or make me split that commit up better.

The other thing is that one test I've added intentionally fails: protover_all_supported_should_include_version_we_actually_do_support. The behavioural difference is this: if we take a protover string "Link=3-999" and ask if it is supported, when "Link=1-5" is supported:

• the C version returns "Link=3-999" (which is, IMHO, wrong, since we do support 3, 4, and 5).
• the Rust version returns "Link=6-999", which I believe to be the correct implementation of the spec?

Upping the priority because potential DoS.

Upping the actual points to 5, although only ~3 were spent on this ticket, and another 2 finding/fixing related bugs elsewhere.

Marking as SponsorM-can, although that may be wrong; feel free to correct.

Changing the version to reflect inclusion in 0.3.3, along with the appropriate keywords.

Trac:
Sponsor: N/A to SponsorM-can
Priority: High to Very High
Actualpoints: N/A to 5
Milestone: Tor: 0.3.4.x-final to Tor: 0.3.3.x-final
Status: needs_revision to needs_review
Keywords: rust 033-must protover deleted, rust 033-must protover security added
Version: N/A to Tor: 0.3.3.1-alpha

Trac:
Cc: chelseakomlo to chelseakomlo, teor

Assign Reviewer to nickm for the 26/03/18 week.

Trac:
Reviewer: N/A to nickm

Second batch of triage for 0.3.3: tickets that we didn't cover the first time.

Trac:
Keywords: rust 033-must protover security deleted, 033-must, 033-triage-20180326, rust, security, protover added

Marking 033-must tickets as included. Round 2.

Trac:
Keywords: N/A deleted, 033-included-20180326 added

Hi Isis,

This looks great! Thanks for doing this and making these improvements, it is much cleaner!

There are a few things I noticed when looking at this, they are mostly nits. I'll do a deeper look by the end of this week, but this is looking significantly better.

1. If possible, it would be ideal to keep all FFI/C related code in ffi.rs. This way we can keep Rust/C code cleanly separated and if Rust needs to use these functions in the future, we don't need to do any refactoring or translation (for example, compute_for_old_tor and get_supported_protocols). It looks like in at least once place we get a string as a cstring in Rust (in supported for ProtoEntry) and then translate into a string- we should just keep this all as strings in Rust and then only translate in ffi.rs when we actually want to send something to C.
2. I really like how you broke out errors into their own file. Is this something we should add to our guide to writing Rust in Tor?
3. Is generating ToString implementations at runtime a common Rust practice? If not, document impl_to_string_for_proto_entry
4. supported for ProtoEntry maybe should return an actual error instead of an empty string