Opened 4 weeks ago

Last modified 4 days ago

#31788 new enhancement

Circuit padding trace simulator

Reported by: mikeperry Owned by:
Priority: Medium Milestone:
Component: Core Tor/Tor Version:
Severity: Normal Keywords: circpad-researchers-want, wtf-pad
Cc: pulls, asn, dgoulet, nickm Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description (last modified by mikeperry)

This is the parent ticket for the pieces of work required to make it possible to use circuitpadding.c in a trace simulator outside of Tor, so that defenses could be re-applied to crawl traces quickly without needing to re-crawl a set of sites.

An alternate way to do this, instead of extracting this code, is to make use of our unit testing framework and build the tracer as a unit test. We have mechanisms to mock the networking functions so that they output new traces, and then we can use the unit-test style to read in a trace file and output a new one, instead of performing a test.

Child Tickets

#31790enhancementnewAdd easy-to-parse event and packet tracing logs to circuit padding

Change History (3)

comment:1 Changed 4 weeks ago by mikeperry

Cc: pulls asn added
Description: modified (diff)

comment:2 Changed 3 weeks ago by mikeperry

Cc: dgoulet nickm added

I added nickm and dgoulet to Cc since they are most familiar with how circuitmux, etc looks on the wire, and how libevent callbacks in a mocked scenario may differ from reality, and to generally sanity check this.

Here are the specific details on the approach:

This simulator needs two components. First: instrumentation of Tor itself, so that researchers can produce reference trace sets from a crawl. Second: A unit-test driven defense simulator, which reads trace files, applies padding machines to them, and outputs new defense-applied trace files.

The undefended reference crawl traces must be collected at three locations: the client, the guard, and the middle node.

For the client and the middle node, the simplest place to collect these traces are in the circpad_cell_event_* callbacks, as well as the circpad_machine_event_* callbacks. Those callbacks can have added loglines/fprintfs that print out a timestamp, an event type, and a cell direction. Note also that the patches in #29494 will make these callback locations more closely reflect actual network wire write time. The middle-node callbacks should also check that this is a researcher machine that is meant to be recorded before emitting loglines, though.

For the guard node, we can allow our tracer clients to use a special magic third padding machine (if we bump CIRCPAD_MAX_MACHINES and increase the field width) just to hop 1. Then, to signal to the guard node which circuits to record, this machine can be negotiated with the guard, so it can mark circuits as belonging to the researcher, for safe collection, by way of adding a dummy padding machine. The same circpad_cell_event callbacks as were used for the client and middle can then be used for guard collection in that case, since a padding machine will be open there, only on the researcher's circuits (though the callbacks should check that this is a researcher machine that is meant to be recorded, just as in the middle node case).

Be warned though: this guard approach may get hairy because of the need to use index 3 on the client, but index 1 on the guard, as well as make sure the machine_index bitfield and CIRCPAD_MAX_MACHINES are bumped to 3 for the client.

The timing differences for cell transit time from middle to guard and client to guard should be used to compute some statistics for simulating this delay upon defense application, as the simulator will not have a guard node.

Alternatively, all of the classifier input could simply use client traces, with an appropriate model for guard latency built in. This will eliminate the need to pin the guard node in all crawls. However, without at least some live traces for reference, this model may miss out in varying congestion and queuing delays on the guard node from the live scenario.

For the simulator, our unit testing framework should be used to set up client and relay padding machines on mock circuits, with a mock circuitmux between them. Trace files can then be read, advance mocked monotime as per the timestamps in the trace (via timers_advance_and_run() function or similar code), and and call the appropriate circpad_cell_event_* and circpad_machine_event_* callbacks as per the trace file.

These callbacks themselves should then directly emit loglines/fprints as per their already instrumented code for the live trace collections. Remember to model guard latency and congestion into the client output, to create new guard traces for the classifier.

Example unit tests that already do this sort of thing are test_circuitpadding_rtt(), test_circuitpadding_negotiation(), and test_circuitpadding_circuitsetup_machine() (see #30578 for a fixup of this last test... it may be the most useful) in ./src/test/test_circuitpadding.c.

There is an extra wrinkle that after each event, the simulator must check if the next scheduled padding packet (if any, checked via circ->padding_info[N]->padding_scheduled_at_usec) would happen before or after the next timestamp in the trace. If it would happen before the next timestamp, we need to only advance monotime to that next padding callback, and not to the next timestamp in the trace, so that the callback can fire with an appropriately correct timestamp from monotime.

This simulator will also not measure the delays from libevent to the callbacks, because mocked monotime will prevent it from doing so. To capture this delay, calls to tor_gettimeofday() before advancing monotime, and then again in the callbacks can be used to try to measure this delta and move mocked monotime forward appropriately, but this may still be short of reality, since on relays especially, other libevent event callbacks will delay padding callbacks if they are made first.

Last edited 3 weeks ago by mikeperry (previous) (diff)

comment:3 Changed 4 days ago by pulls

Thank you for the detailed instructions Mike, very useful. I've started working on implementing a simulator, goal is to have something useful by the end of the month. Also thank you Nick for merging doc/HACKING/design, it helped me a lot.

The implementation now requires a client and relay trace (got a lazy python script to simulate a relay trace from a client trace as well). My biggest gripe right now is time. Every time a client/relay machine triggers padding, a corresponding event has to be added to the relay/client trace with an estimated time. This estimate will always be, well, wrong. I'm not sure it's possible to make this estimate in such a way that it'll fool time-based classifiers, even if we add in guard traces for better estimates and patches as you mention Mike.

Right now I think it might be best as a starting point to just try to use the simulator to find optimal machines against attacks like Deep Fingerprinting that ignores time. Once we have a better understanding of how feasible and costly that is we can look more closely at how time changes things.

Any thoughts on this? Have I missed some other reason than time estimates for including guard traces?

Also, if some other researcher working on this wants to collaborate please reach out.

Note: See TracTickets for help on using tickets.