|
Tor
0.4.7.0-alpha-dev
|
Header file for circuitpadding.c. More...
Go to the source code of this file.
Data Structures | |
| struct | circpad_machine_conditions_t |
| struct | circpad_distribution_t |
| struct | circpad_state_t |
| struct | circpad_machine_runtime_t |
| struct | circpad_machine_spec_t |
Macros | |
| #define | CIRCPAD_NUM_EVENTS ((int)CIRCPAD_EVENT_LENGTH_COUNT+1) |
| #define | CIRCPAD_DELAY_UNITS_PER_SECOND (1000*1000) |
| #define | CIRCPAD_DELAY_INFINITE (UINT32_MAX) |
| #define | CIRCPAD_DELAY_MAX_SECS ((CIRCPAD_DELAY_INFINITE/CIRCPAD_DELAY_UNITS_PER_SECOND)+1) |
| #define | CIRCPAD_INFINITY_BIN(mi) ((mi)->histogram_len-1) |
| #define | CIRCPAD_STATE_ALL |
| #define | CIRCPAD_PURPOSE_ALL (0xFFFFFFFF) |
| #define | CIRCPAD_STATENUM_MAX (UINT16_MAX) |
| #define | CIRCPAD_MAX_HISTOGRAM_LEN (100) |
| #define | CIRCPAD_STATE_START 0 |
| #define | CIRCPAD_STATE_BURST 1 |
| #define | CIRCPAD_STATE_GAP 2 |
| #define | CIRCPAD_STATE_END CIRCPAD_STATENUM_MAX |
| #define | CIRCPAD_STATE_IGNORE (CIRCPAD_STATENUM_MAX-1) |
| #define | CIRCPAD_STATE_CANCEL (CIRCPAD_STATENUM_MAX-2) |
| #define | CIRCPAD_MAX_MACHINE_STATES (CIRCPAD_STATE_CANCEL-1) |
| #define | CIRCPAD_STATE_LENGTH_INFINITE UINT64_MAX |
| #define | CIRCPAD_MAX_MACHINES (2) |
| #define | CIRCPAD_GET_MACHINE(machineinfo) ((machineinfo)->on_circ->padding_machine[(machineinfo)->machine_index]) |
Typedefs | |
| typedef int | signed_error_t |
| typedef uint32_t | circpad_hist_token_t |
| typedef int8_t | circpad_hist_index_t |
| typedef uint64_t | circpad_time_t |
| typedef uint32_t | circpad_delay_t |
| typedef uint32_t | circpad_purpose_mask_t |
| typedef uint16_t | circpad_statenum_t |
| typedef uint8_t | circpad_machine_num_t |
Enumerations | |
| enum | circpad_event_t { CIRCPAD_EVENT_NONPADDING_RECV = 0 , CIRCPAD_EVENT_NONPADDING_SENT = 1 , CIRCPAD_EVENT_PADDING_SENT = 2 , CIRCPAD_EVENT_PADDING_RECV = 3 , CIRCPAD_EVENT_INFINITY = 4 , CIRCPAD_EVENT_BINS_EMPTY = 5 , CIRCPAD_EVENT_LENGTH_COUNT = 6 } |
| enum | circpad_decision_t { CIRCPAD_STATE_UNCHANGED = 0 , CIRCPAD_STATE_CHANGED = 1 } |
| enum | circpad_circuit_state_t { CIRCPAD_CIRC_BUILDING = 1<<0 , CIRCPAD_CIRC_OPENED = 1<<1 , CIRCPAD_CIRC_NO_STREAMS = 1<<2 , CIRCPAD_CIRC_STREAMS = 1<<3 , CIRCPAD_CIRC_HAS_RELAY_EARLY = 1<<4 , CIRCPAD_CIRC_HAS_NO_RELAY_EARLY = 1<<5 } |
| enum | circpad_removal_t { CIRCPAD_TOKEN_REMOVAL_NONE = 0 , CIRCPAD_TOKEN_REMOVAL_HIGHER = 1 , CIRCPAD_TOKEN_REMOVAL_LOWER = 2 , CIRCPAD_TOKEN_REMOVAL_CLOSEST = 3 , CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC = 4 , CIRCPAD_TOKEN_REMOVAL_EXACT = 5 } |
| enum | circpad_distribution_type_t { CIRCPAD_DIST_NONE = 0 , CIRCPAD_DIST_UNIFORM = 1 , CIRCPAD_DIST_LOGISTIC = 2 , CIRCPAD_DIST_LOG_LOGISTIC = 3 , CIRCPAD_DIST_GEOMETRIC = 4 , CIRCPAD_DIST_WEIBULL = 5 , CIRCPAD_DIST_PARETO = 6 } |
Header file for circuitpadding.c.
Definition in file circuitpadding.h.
| #define CIRCPAD_DELAY_INFINITE (UINT32_MAX) |
An infinite padding cell delay means don't schedule any padding – simply wait until a different event triggers a transition.
This means that the maximum delay we can schedule is UINT32_MAX-1 microseconds, or about 4300 seconds (1.25 hours). XXX: Is this enough if we want to simulate light, intermittent activity on an onion service?
Definition at line 87 of file circuitpadding.h.
| #define CIRCPAD_DELAY_MAX_SECS ((CIRCPAD_DELAY_INFINITE/CIRCPAD_DELAY_UNITS_PER_SECOND)+1) |
This is the maximum delay that the circuit padding system can have, in seconds.
Definition at line 93 of file circuitpadding.h.
| #define CIRCPAD_GET_MACHINE | ( | machineinfo | ) | ((machineinfo)->on_circ->padding_machine[(machineinfo)->machine_index]) |
Helper macro to get an actual state machine from a machineinfo
Definition at line 611 of file circuitpadding.h.
| #define CIRCPAD_INFINITY_BIN | ( | mi | ) | ((mi)->histogram_len-1) |
Macro to clarify when we're checking the infinity bin.
Works with either circpad_state_t or circpad_machine_runtime_t
Definition at line 101 of file circuitpadding.h.
| #define CIRCPAD_MAX_HISTOGRAM_LEN (100) |
A histogram can be used to sample padding delays given a machine state. This constant defines the maximum histogram width (i.e. the max number of bins).
The current limit is arbitrary and could be raised if there is a need, however too many bins will be hard to serialize in the future.
Memory concerns are not so great here since the corresponding histogram and histogram_edges arrays are global and not per-circuit.
If we ever upgrade this to a value that can't be represented by 8-bits we also need to upgrade circpad_hist_index_t.
Definition at line 281 of file circuitpadding.h.
| #define CIRCPAD_MAX_MACHINE_STATES (CIRCPAD_STATE_CANCEL-1) |
Since we have 3 pseudo-states, the max state array length is up to one less than cancel's statenum.
Definition at line 494 of file circuitpadding.h.
| #define CIRCPAD_MAX_MACHINES (2) |
Max number of padding machines on each circuit. If changed, also ensure the machine_index bitwith supports the new size.
Definition at line 602 of file circuitpadding.h.
| #define CIRCPAD_PURPOSE_ALL (0xFFFFFFFF) |
Bitmask that says "apply this machine to all purposes".
Definition at line 147 of file circuitpadding.h.
| #define CIRCPAD_STATE_ALL |
Bitmask that says "apply this machine to all states"
Definition at line 132 of file circuitpadding.h.
| #define CIRCPAD_STATE_BURST 1 |
The burst state for this machine.
In the original Adaptive Padding algorithm and in WTF-PAD (https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf and https://www.cs.kau.se/pulls/hot/thebasketcase-wtfpad/), the burst state serves to detect bursts in traffic. This is done by using longer delays in its histogram, which represent the expected delays between bursts of packets in the target stream. If this delay expires without a real packet being sent, the burst state sends a padding packet and then immediately transitions to the gap state, which is used to generate a synthetic padding packet train. In this implementation, this transition needs to be explicitly specified in the burst state's transition events.
Because of this flexibility, other padding mechanisms can transition between these two states arbitrarily, to encode other dynamics of target traffic.
Definition at line 448 of file circuitpadding.h.
| #define CIRCPAD_STATE_CANCEL (CIRCPAD_STATENUM_MAX-2) |
"Cancel" is a pseudo-state that means "cancel pending timers, but remain in your current state".
Cancel MUST NOT occupy a slot in the machine state array.
Definition at line 488 of file circuitpadding.h.
| #define CIRCPAD_STATE_END CIRCPAD_STATENUM_MAX |
End is a pseudo-state that causes the machine to go completely idle, and optionally get torn down (depending on the value of circpad_machine_spec_t.should_negotiate_end)
End MUST NOT occupy a slot in the machine state array.
Definition at line 472 of file circuitpadding.h.
| #define CIRCPAD_STATE_GAP 2 |
The gap state for this machine.
In the original Adaptive Padding algorithm and in WTF-PAD, the gap state serves to simulate an artificial packet train composed of padding packets. It does this by specifying much lower inter-packet delays than the burst state, and transitioning back to itself after padding is sent if these timers expire before real traffic is sent. If real traffic is sent, it transitions back to the burst state.
Again, in this implementation, these transitions must be specified explicitly, and other transitions are also permitted.
Definition at line 463 of file circuitpadding.h.
| #define CIRCPAD_STATE_IGNORE (CIRCPAD_STATENUM_MAX-1) |
"Ignore" is a pseudo-state that means "do not react to this event".
"Ignore" MUST NOT occupy a slot in the machine state array.
Definition at line 480 of file circuitpadding.h.
| #define CIRCPAD_STATE_START 0 |
The start state for this machine.
In the original WTF-PAD, this is only used for transition to/from the burst state. All other fields are not used. But to simplify the code we've made it a first-class state. This has no performance consequences, but may make naive serialization of the state machine large, if we're not careful about how we represent empty fields.
Definition at line 428 of file circuitpadding.h.
| typedef uint32_t circpad_delay_t |
The type for timer delays, in microseconds
Definition at line 75 of file circuitpadding.h.
| typedef int8_t circpad_hist_index_t |
The type for histogram indexes (needs to be negative for errors)
Definition at line 69 of file circuitpadding.h.
| typedef uint32_t circpad_hist_token_t |
The type for the things in histogram bins (aka tokens)
Definition at line 66 of file circuitpadding.h.
| typedef uint8_t circpad_machine_num_t |
This specifies a particular padding machine to use after negotiation.
The constants for machine_num_t are in trunnel. We want to be able to define extra numbers in the consensus/torrc, though.
Definition at line 620 of file circuitpadding.h.
| typedef uint32_t circpad_purpose_mask_t |
A compact circuit purpose bitfield mask that allows us to compactly specify which circuit purposes a machine should apply to.
The helper function circpad_circ_purpose_to_mask() converts circuit purposes into bit positions in this bitmask.
Definition at line 144 of file circuitpadding.h.
| typedef uint16_t circpad_statenum_t |
State number type. Represents current state of state machine.
Definition at line 265 of file circuitpadding.h.
| typedef uint64_t circpad_time_t |
The type for absolute time, from monotime_absolute_usec()
Definition at line 72 of file circuitpadding.h.
| typedef int signed_error_t |
Signed error return with the specific property that negative values mean error codes of various semantics, 0 means success, and positive values are unused.
XXX: Tor uses this concept a lot but just calls it int. Should we move this somewhere centralized? Where?
Definition at line 28 of file circuitpadding.h.
These constants form a bitfield that specifies when a state machine should be applied to a circuit.
If any of these elements is set, then the circuit will be tested against that specific condition. If an element is unset, then we don't test it. (E.g., if neither NO_STREAMS or STREAMS are set, then we will not care whether a circuit has streams attached when we apply a state machine.)
The helper function circpad_circuit_state() converts circuit state flags into this more compact representation.
Definition at line 115 of file circuitpadding.h.
| enum circpad_decision_t |
Boolean type that says if we decided to transition states or not
Definition at line 60 of file circuitpadding.h.
Distribution types supported by circpad_distribution_sample().
These can be used instead of histograms for the inter-packet timing distribution, or to specify a distribution on the number of cells that can be sent while in a specific state of the state machine.
Each distribution takes up to two parameters which are described below.
Definition at line 233 of file circuitpadding.h.
| enum circpad_event_t |
These constants specify the types of events that can cause transitions between state machine states.
Note that SENT and RECV are relative to this endpoint. For relays, SENT means packets destined towards the client and RECV means packets destined towards the relay. On the client, SENT means packets destined towards the relay, where as RECV means packets destined towards the client.
Definition at line 40 of file circuitpadding.h.
| enum circpad_removal_t |
Token removal strategy options.
The WTF-PAD histograms are meant to specify a target distribution to shape traffic towards. This is accomplished by removing tokens from the histogram when either padding or non-padding cells are sent.
When we see a non-padding cell at a particular time since the last cell, you remove a token from the corresponding delay bin. These flags specify which bin to choose if that bin is already empty.
Definition at line 205 of file circuitpadding.h.
| void circpad_cell_event_nonpadding_received | ( | circuit_t * | on_circ | ) |
A "non-padding" cell has been received by this endpoint. React according to any padding state machines on the circuit.
For origin circuits, this means we read a cell from the network. For middle relay circuits, this means we received a cell from the origin.
Definition at line 1903 of file circuitpadding.c.
Referenced by circpad_deliver_unrecognized_cell_events().
| void circpad_cell_event_nonpadding_sent | ( | circuit_t * | on_circ | ) |
Cell events are delivered by the above delivery functions
A "non-padding" cell has been sent from this endpoint. React according to any padding state machines on the circuit.
For origin circuits, this means we sent a cell into the network. For middle relay circuits, this means we sent a cell towards the origin.
Definition at line 1813 of file circuitpadding.c.
Referenced by circpad_deliver_unrecognized_cell_events().
| void circpad_cell_event_padding_received | ( | circuit_t * | on_circ | ) |
A padding cell has been received by this endpoint. React according to any padding state machines on the circuit.
For origin circuits, this means we read a cell from the network. For middle relay circuits, this means we received a cell from the origin.
Definition at line 1950 of file circuitpadding.c.
| void circpad_cell_event_padding_sent | ( | circuit_t * | on_circ | ) |
A padding cell has been sent from this endpoint. React according to any padding state machines on the circuit.
For origin circuits, this means we sent a cell into the network. For middle relay circuits, this means we sent a cell towards the origin.
Definition at line 1924 of file circuitpadding.c.
| int circpad_check_received_cell | ( | cell_t * | cell, |
| circuit_t * | circ, | ||
| crypt_path_t * | layer_hint, | ||
| const relay_header_t * | rh | ||
| ) |
Check if this cell or circuit are related to circuit padding and handle them if so. Return 0 if the cell was handled in this subsystem and does not need any other consideration, otherwise return 1.
Definition at line 1844 of file circuitpadding.c.
| circpad_purpose_mask_t circpad_circ_purpose_to_mask | ( | uint8_t | circ_purpose | ) |
Convert a normal circuit purpose into a bitmask that we can use for determining matching circuits.
Definition at line 2112 of file circuitpadding.c.
Referenced by circpad_machine_conditions_keep().
| void circpad_circuit_free_all_machineinfos | ( | circuit_t * | circ | ) |
Free all padding machines and mutable info associated with circuit
Definition at line 304 of file circuitpadding.c.
| void circpad_deliver_recognized_relay_cell_events | ( | circuit_t * | circ, |
| uint8_t | relay_command, | ||
| crypt_path_t * | layer_hint | ||
| ) |
Deliver circpad events for "recognized" relay cells.
Recognized cells are destined for this hop, either client or middle. Check if this is a padding cell or not, and send the appropriate received event.
Definition at line 2397 of file circuitpadding.c.
| void circpad_deliver_sent_relay_cell_events | ( | circuit_t * | circ, |
| uint8_t | relay_command | ||
| ) |
Deliver circpad events for relay cells sent from us.
If this is a padding cell, update our padding stats and deliver the event. Otherwise just deliver the event.
Definition at line 2434 of file circuitpadding.c.
| void circpad_deliver_unrecognized_cell_events | ( | circuit_t * | circ, |
| cell_direction_t | dir | ||
| ) |
The following are event call-in points that are of interest to the state machines. They are called during cell processing.
Deliver circpad events for an "unrecognized cell".
Unrecognized cells are sent to relays and are forwarded onto the next hop of their circuits. Unrecognized cells are by definition not padding. We need to tell relay-side state machines that a non-padding cell was sent or received, depending on the direction, so they can update their histograms and decide to pad or not.
Definition at line 2369 of file circuitpadding.c.
| void circpad_free_all | ( | void | ) |
Free all memory allocated by the circuitpadding subsystem.
Definition at line 3114 of file circuitpadding.c.
| signed_error_t circpad_handle_padding_negotiate | ( | circuit_t * | circ, |
| cell_t * | cell | ||
| ) |
Parse and react to a padding_negotiate cell.
This is called at the middle node upon receipt of the client's choice of state machine, so that it can use the requested state machine index, if it is available.
Returns -1 on error, 0 on success.
Definition at line 2967 of file circuitpadding.c.
| signed_error_t circpad_handle_padding_negotiated | ( | circuit_t * | circ, |
| cell_t * | cell, | ||
| crypt_path_t * | layer_hint | ||
| ) |
Parse and react to a padding_negotiated cell.
This is called at the origin upon receipt of the middle's response to our choice of state machine.
Returns -1 on error, 0 on success.
Definition at line 3044 of file circuitpadding.c.
| circpad_decision_t circpad_internal_event_bins_empty | ( | circpad_machine_runtime_t * | mi | ) |
All of the bins of our current state's histogram's are empty.
Check to see if this means transition to another state, and if not, refill the tokens.
Return 1 if we decide to transition, 0 otherwise.
Definition at line 1984 of file circuitpadding.c.
Referenced by check_machine_token_supply().
| circpad_decision_t circpad_internal_event_infinity | ( | circpad_machine_runtime_t * | mi | ) |
Internal events are events the machines send to themselves
An "infinite" delay has ben chosen from one of our histograms.
"Infinite" delays mean don't send padding – but they can also mean transition to another state depending on the state machine definitions. Check the rules and react accordingly.
Return 1 if we decide to transition, 0 otherwise.
Definition at line 1970 of file circuitpadding.c.
| circpad_decision_t circpad_internal_event_state_length_up | ( | circpad_machine_runtime_t * | mi | ) |
This state has used up its cell count. Emit the event and see if we transition.
Return 1 if we decide to transition, 0 otherwise.
Definition at line 2003 of file circuitpadding.c.
| void circpad_machine_event_circ_added_hop | ( | origin_circuit_t * | on_circ | ) |
Machine creation events are events that cause us to set up or tear down padding state machines.
Event that tells us we added a hop to an origin circuit.
This event is used to decide if we should create a padding machine on a circuit.
Definition at line 2246 of file circuitpadding.c.
| void circpad_machine_event_circ_built | ( | origin_circuit_t * | circ | ) |
Event that tells us that an origin circuit is now built.
Shut down any machines that only applied to un-built circuits. Activate any new ones.
Definition at line 2260 of file circuitpadding.c.
| void circpad_machine_event_circ_has_no_relay_early | ( | origin_circuit_t * | circ | ) |
Event that tells us that an origin circuit is out of RELAY_EARLY cells.
Shut down any machines that only applied to RELAY_EARLY circuits. Activate any new ones.
Definition at line 2287 of file circuitpadding.c.
| void circpad_machine_event_circ_has_no_streams | ( | origin_circuit_t * | circ | ) |
Streams detached event.
Called from circuit_detach_stream()
Shut down any machines that only applied to machines without streams. Activate any new ones.
Definition at line 2317 of file circuitpadding.c.
| void circpad_machine_event_circ_has_streams | ( | origin_circuit_t * | circ | ) |
Streams attached event.
Called from link_apconn_to_circ() and handle_hs_exit_conn()
Shut down any machines that only applied to machines without streams. Activate any new ones.
Definition at line 2302 of file circuitpadding.c.
| void circpad_machine_event_circ_purpose_changed | ( | origin_circuit_t * | circ | ) |
Circpad purpose changed event.
Shut down any machines that don't apply to our circ purpose. Activate any new ones that do.
Definition at line 2273 of file circuitpadding.c.
| circpad_decision_t circpad_machine_schedule_padding | ( | circpad_machine_runtime_t * | mi | ) |
Schedule the next padding time according to the machineinfo on a circuit.
The histograms represent inter-packet-delay. Whenever you get an packet event you should be scheduling your next timer (after cancelling any old ones and updating tokens accordingly).
Returns 1 if we decide to transition states (due to infinity bin), 0 otherwise.
Definition at line 1421 of file circuitpadding.c.
| char* circpad_machine_spec_to_string | ( | const circpad_machine_spec_t * | machine | ) |
Serializaton functions for writing to/from torrc and consensus
| circpad_decision_t circpad_machine_spec_transition | ( | circpad_machine_runtime_t * | mi, |
| circpad_event_t | event | ||
| ) |
Generic state transition function for padding state machines.
Given an event and our mutable machine info, decide if/how to transition to a different state, and perform actions accordingly.
Returns 1 if we transition states, 0 otherwise.
Definition at line 1606 of file circuitpadding.c.
Referenced by circpad_cell_event_nonpadding_received(), circpad_cell_event_padding_received(), circpad_internal_event_bins_empty(), circpad_internal_event_infinity(), and circpad_internal_event_state_length_up().
| void circpad_machine_states_init | ( | circpad_machine_spec_t * | machine, |
| circpad_statenum_t | num_states | ||
| ) |
Initialize the states array for a circpad machine.
Definition at line 2461 of file circuitpadding.c.
| void circpad_machines_free | ( | void | ) |
Free our padding machines
Definition at line 2800 of file circuitpadding.c.
| void circpad_machines_init | ( | void | ) |
Initialize all of our padding machines.
This is called at startup. It sets up some global machines, and then loads some from torrc, and from the tor consensus.
Definition at line 2773 of file circuitpadding.c.
| int circpad_marked_circuit_for_padding | ( | circuit_t * | circ, |
| int | reason | ||
| ) |
Return true if circpad has decided to hold the circuit open for additional padding. This function is used to take and retain ownership of certain types of circuits that have padding machines on them, that have been passed to circuit_mark_for_close().
circuit_mark_for_close() calls this function to ask circpad if any padding machines want to keep the circuit open longer to pad.
Any non-measurement circuit that was closed for a normal, non-error reason code may be held open for up to CIRCPAD_DELAY_INFINITE microseconds between network-driven cell events.
After CIRCPAD_DELAY_INFINITE microseconds of silence on a circuit, this function will no longer hold it open (it will return 0 regardless of what the machines ask for, and thus circuit_expire_old_circuits_clientside() will close the circuit after roughly 1.25hr of idle time, maximum, regardless of the padding machine state.
Definition at line 174 of file circuitpadding.c.
Referenced by circuit_mark_for_close_().
| signed_error_t circpad_negotiate_padding | ( | origin_circuit_t * | circ, |
| circpad_machine_num_t | machine, | ||
| uint8_t | target_hopnum, | ||
| uint8_t | command, | ||
| uint32_t | machine_ctr | ||
| ) |
Try to negotiate padding.
Returns -1 on error, 0 on success.
Definition at line 2874 of file circuitpadding.c.
Referenced by circpad_machine_spec_transitioned_to_end(), and circpad_shutdown_old_machines().
| void circpad_new_consensus_params | ( | const networkstatus_t * | ns | ) |
Cache our consensus parameters upon consensus update.
Definition at line 1318 of file circuitpadding.c.
| bool circpad_padding_is_from_expected_hop | ( | circuit_t * | circ, |
| crypt_path_t * | from_hop | ||
| ) |
Verify that padding is coming from the expected hop.
Returns true if from_hop matches the target hop from one of our padding machines.
Returns false if we're not an origin circuit, or if from_hop does not match one of the padding machines.
Definition at line 2333 of file circuitpadding.c.
| bool circpad_padding_negotiated | ( | circuit_t * | circ, |
| circpad_machine_num_t | machine, | ||
| uint8_t | command, | ||
| uint8_t | response, | ||
| uint32_t | machine_ctr | ||
| ) |
Try to negotiate padding.
Returns 1 if successful (or already set up), 0 otherwise.
Definition at line 2922 of file circuitpadding.c.
Referenced by circpad_machine_spec_transitioned_to_end().
| circpad_decision_t circpad_send_padding_cell_for_callback | ( | circpad_machine_runtime_t * | mi | ) |
Callback helper to send a padding cell.
This helper is called after our histogram-sampled delay period passes without another packet being sent first. If a packet is sent before this callback happens, it is canceled. So when we're called here, send padding right away.
If sending this padding cell forced us to transition states return CIRCPAD_STATE_CHANGED. Otherwise return CIRCPAD_STATE_UNCHANGED.
Definition at line 1224 of file circuitpadding.c.
1.9.1