/* * Copyright (c) 2017-2019, The Tor Project, Inc. */ /* See LICENSE for licensing information */ /** * \file circuitpadding.h * \brief Header file for circuitpadding.c. **/ #ifndef TOR_CIRCUITPADDING_H #define TOR_CIRCUITPADDING_H #include "src/trunnel/circpad_negotiation.h" #include "lib/evloop/timers.h" struct circuit_t; struct origin_circuit_t; struct cell_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? */ typedef int signed_error_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. */ typedef enum { /* A non-padding cell was received. */ CIRCPAD_EVENT_NONPADDING_RECV = 0, /* A non-padding cell was sent. */ CIRCPAD_EVENT_NONPADDING_SENT = 1, /* A padding cell (RELAY_COMMAND_DROP) was sent. */ CIRCPAD_EVENT_PADDING_SENT = 2, /* A padding cell was received. */ CIRCPAD_EVENT_PADDING_RECV = 3, /* We tried to schedule padding but we ended up picking the infinity bin * which means that padding was delayed infinitely */ CIRCPAD_EVENT_INFINITY = 4, /* All histogram bins are empty (we are out of tokens) */ CIRCPAD_EVENT_BINS_EMPTY = 5, /* just a counter of the events above */ CIRCPAD_EVENT_LENGTH_COUNT = 6 } circpad_event_t; #define CIRCPAD_NUM_EVENTS ((int)CIRCPAD_EVENT_LENGTH_COUNT+1) /** Boolean type that says if we decided to transition states or not */ typedef enum { CIRCPAD_STATE_UNCHANGED = 0, CIRCPAD_STATE_CHANGED = 1 } circpad_decision_t; /** The type for the things in histogram bins (aka tokens) */ typedef uint32_t circpad_hist_token_t; /** The type for histogram indexes (needs to be negative for errors) */ typedef int8_t circpad_hist_index_t; /** The type for absolute time, from monotime_absolute_usec() */ typedef uint64_t circpad_time_t; /** The type for timer delays, in microseconds */ typedef uint32_t circpad_delay_t; /** * 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 scedule 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? */ #define CIRCPAD_DELAY_INFINITE (UINT32_MAX) /** * Macro to clarify when we're checking the infinity bin. * * Works with either circpad_state_t or circpad_machine_state_t */ #define CIRCPAD_INFINITY_BIN(mi) ((mi)->histogram_len-1) /** * 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. */ typedef enum { /* Only apply machine if the circuit is still building */ CIRCPAD_CIRC_BUILDING = 1<<0, /* Only apply machine if the circuit is open */ CIRCPAD_CIRC_OPENED = 1<<1, /* Only apply machine if the circuit has no attached streams */ CIRCPAD_CIRC_NO_STREAMS = 1<<2, /* Only apply machine if the circuit has attached streams */ CIRCPAD_CIRC_STREAMS = 1<<3, /* Only apply machine if the circuit still allows RELAY_EARLY cells */ CIRCPAD_CIRC_HAS_RELAY_EARLY = 1<<4, /* Only apply machine if the circuit has depleted its RELAY_EARLY cells * allowance. */ CIRCPAD_CIRC_HAS_NO_RELAY_EARLY = 1<<5 } circpad_circuit_state_t; /** Bitmask that says "apply this machine to all states" */ #define CIRCPAD_STATE_ALL \ (CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED| \ CIRCPAD_CIRC_STREAMS|CIRCPAD_CIRC_NO_STREAMS| \ CIRCPAD_CIRC_HAS_RELAY_EARLY|CIRCPAD_CIRC_HAS_NO_RELAY_EARLY) /** * 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. */ typedef uint32_t circpad_purpose_mask_t; /** Bitmask that says "apply this machine to all purposes". */ #define CIRCPAD_PURPOSE_ALL (0xFFFFFFFF) /** * This type specifies all of the conditions that must be met before * a client decides to initiate padding on a circuit. * * A circuit must satisfy every sub-field in this type in order * to be considered to match the conditions. */ typedef struct circpad_machine_conditions_t { /** Only apply the machine *if* the circuit has at least this many hops */ unsigned min_hops : 3; /** Only apply the machine *if* vanguards are enabled */ unsigned requires_vanguards : 1; /** Only apply the machine *if* the circuit's state matches any of * the bits set in this bitmask. */ circpad_circuit_state_t state_mask; /** Only apply a machine *if* the circuit's purpose matches one * of the bits set in this bitmask */ circpad_purpose_mask_t purpose_mask; } circpad_machine_conditions_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. */ typedef enum { /** Don't remove any tokens */ CIRCPAD_TOKEN_REMOVAL_NONE = 0, /** * Remove from the first non-zero higher bin index when current is zero. * This is the recommended strategy from the Adaptive Padding paper. */ CIRCPAD_TOKEN_REMOVAL_HIGHER = 1, /** Remove from the first non-zero lower bin index when current is empty. */ CIRCPAD_TOKEN_REMOVAL_LOWER = 2, /** Remove from the closest non-zero bin index when current is empty. */ CIRCPAD_TOKEN_REMOVAL_CLOSEST = 3, /** Remove from the closest bin by time value (since bins are * exponentially spaced). */ CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC = 4, /** Only remove from the exact bin corresponding to this delay. If * the bin is 0, simply do nothing. Don't pick another bin. */ CIRCPAD_TOKEN_REMOVAL_EXACT = 5 } circpad_removal_t; /** * 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. */ typedef enum { 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 } circpad_distribution_type_t; /** * Distribution information. * * This type specifies a specific distribution above, as well as * up to two parameters for that distribution. The specific * per-distribution meaning of these parameters is specified * in circpad_distribution_sample(). */ typedef struct circpad_distribution_t { circpad_distribution_type_t type; double param1; double param2; } circpad_distribution_t; /** State number type. Represents current state of state machine. */ typedef uint16_t circpad_statenum_t; #define CIRCPAD_STATENUM_MAX (UINT16_MAX) /** A histogram is used to sample padding delays given a machine state. This * constant defines the maximum histogram width (i.e. the max number of bins) * * Each histogram bin is twice as large as the previous. Two exceptions: The * first bin has zero width (which means that minimum delay is applied to the * next padding cell), and the last bin (infinity bin) has infinite width * (which means that the next padding cell will be delayed infinitely). */ #define CIRCPAD_MAX_HISTOGRAM_LEN (sizeof(circpad_delay_t)*8 + 1) /** * A state of a padding state machine. The information here are immutable and * represent the initial form of the state; it does not get updated as things * happen. The mutable information that gets updated in runtime are carried in * a circpad_machine_state_t. * * This struct describes the histograms and parameters of a single * state in the adaptive padding machine. Instances of this struct * exist in global circpad machine definitions that come from torrc * or the consensus. */ typedef struct circpad_state_t { /** If a histogram is used for this state, this specifies the number of bins * of this histogram. Histograms must have at least 2 bins. * * If a delay probability distribution is used for this state, this is set * to 0. */ circpad_hist_index_t histogram_len; /** The histogram itself: an array of uint16s of tokens, whose * widths are exponentially spaced, in microseconds */ circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]; /** Total number of tokens in this histogram. This is a constant and is *not* * decremented every time we spend a token. It's used for initializing and * refilling the histogram. */ uint32_t histogram_total_tokens; /** Minimum padding delay of this state in microseconds. * * If histograms are used, this is the left (and right) bound of the first * bin (since it has zero width). * * If a delay probability distribution is used, this represents the minimum * delay we can sample from the distribution. */ circpad_delay_t start_usec; /** If histograms are used, this is the width of the whole histogram in * microseconds, and it's used to calculate individual bin width. * * If a delay probability distribution is used, this is used as the max * delay we can sample from the distribution. */ circpad_delay_t range_usec; /** * Represents a delay probability distribution (aka IAT distribution). It's a * parametrized way of encoding inter-packet delay information in * microseconds. It can be used instead of histograms. * * If it is used, token_removal below must be set to * CIRCPAD_TOKEN_REMOVAL_NONE. * * Start_usec, range_sec, and rtt_estimates are still applied to the * results of sampling from this distribution (range_sec is used as a max). */ circpad_distribution_t iat_dist; /** * The length dist is a parameterized way of encoding how long this * state machine runs in terms of sent padding cells or all * sent cells. Values are sampled from this distribution, clamped * to max_len, and then start_len is added to that value. * * It may be specified instead of or in addition to * the infinity bins and bins empty conditions. */ circpad_distribution_t length_dist; /** A minimum length value, added to the output of length_dist */ uint16_t start_length; /** A cap on the length value that can be sampled from the length_dist */ uint64_t max_length; /** Should we decrement length when we see a nonpadding packet? * XXX: Are there any machines that actually want to set this to 0? There may * not be. OTOH, it's only a bit.. */ unsigned length_includes_nonpadding : 1; /** * This is an array that specifies the next state to transition to upon * receipt an event matching the indicated array index. * * This aborts our scheduled packet and switches to the state * corresponding to the index of the array. Tokens are filled upon * this transition. * * States are allowed to transition to themselves, which means re-schedule * a new padding timer. They are also allowed to temporarily "transition" * to the "IGNORE" and "CANCEL" pseudo-states. See #defines below * for details on state behavior and meaning. */ circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS]; /** * If true, estimate the RTT from this relay to the exit/website and add that * to start_usec for use as the histogram bin 0 start delay. * * Right now this is only supported for relay-side state machines. */ unsigned use_rtt_estimate : 1; /** This specifies the token removal strategy to use upon padding and * non-padding activity. */ circpad_removal_t token_removal; } circpad_state_t; /** * 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. */ #define CIRCPAD_STATE_START 0 /** * 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. */ #define CIRCPAD_STATE_BURST 1 /** * 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. */ #define CIRCPAD_STATE_GAP 2 /** * 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. */ #define CIRCPAD_STATE_END CIRCPAD_STATENUM_MAX /** * "Ignore" is a pseudo-state that means "do not react to this * event". * * "Ignore" MUST NOT occupy a slot in the machine state array. */ #define CIRCPAD_STATE_IGNORE (CIRCPAD_STATENUM_MAX-1) /** * "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. */ #define CIRCPAD_STATE_CANCEL (CIRCPAD_STATENUM_MAX-2) /** * Since we have 3 pseudo-states, the max state array length is * up to one less than cancel's statenum. */ #define CIRCPAD_MAX_MACHINE_STATES (CIRCPAD_STATE_CANCEL-1) /** * Mutable padding machine info. * * This structure contains mutable information about a padding * machine. The mutable information must be kept separate because * it exists per-circuit, where as the machines themselves are global. * This separation is done to conserve space in the circuit structure. * * This is the per-circuit state that changes regarding the global state * machine. Some parts of it are optional (ie NULL). * * XXX: Play with layout to minimize space on x64 Linux (most common relay). */ typedef struct circpad_machine_state_t { /** The callback pointer for the padding callbacks. * * These timers stick around the machineinfo until the machineinfo's circuit * is closed, at which point the timer is cancelled. For this reason it's * safe to assume that the machineinfo exists if this timer gets * triggered. */ tor_timer_t *padding_timer; /** The circuit for this machine */ struct circuit_t *on_circ; /** A mutable copy of the histogram for the current state. * NULL if remove_tokens is false for that state */ circpad_hist_token_t *histogram; /** Length of the above histogram. * XXX: This field *could* be removed at the expense of added * complexity+overhead for reaching back into the immutable machine * state every time we need to inspect the histogram. It's only a byte, * though, so it seemed worth it. */ circpad_hist_index_t histogram_len; /** Remove token from this index upon sending padding */ circpad_hist_index_t chosen_bin; /** Stop padding/transition if this many cells sent */ uint64_t state_length; #define CIRCPAD_STATE_LENGTH_INFINITE UINT64_MAX /** A scaled count of padding packets sent, used to limit padding overhead. * When this reaches UINT16_MAX, we cut it and nonpadding_sent in half. */ uint16_t padding_sent; /** A scaled count of non-padding packets sent, used to limit padding * overhead. When this reaches UINT16_MAX, we cut it and padding_sent in * half. */ uint16_t nonpadding_sent; /** * EWMA estimate of the RTT of the circuit from this hop * to the exit end, in microseconds. */ circpad_delay_t rtt_estimate_usec; /** * The last time we got an event relevant to estimating * the RTT. Monotonic time in microseconds since system * start. */ circpad_time_t last_received_time_usec; /** * The time at which we scheduled a non-padding packet, * or selected an infinite delay. * * Monotonic time in microseconds since system start. * This is 0 if we haven't chosen a padding delay. */ circpad_time_t padding_scheduled_at_usec; /** What state is this machine in? */ circpad_statenum_t current_state; /** * True if we have scheduled a timer for padding. * * This is 1 if a timer is pending. It is 0 if * no timer is scheduled. (It can be 0 even when * padding_was_scheduled_at_usec is non-zero). */ unsigned is_padding_timer_scheduled : 1; /** * If this is true, we have seen full duplex behavior. * Stop updating the RTT. */ unsigned stop_rtt_update : 1; /** Max number of padding machines on each circuit. If changed, * also ensure the machine_index bitwith supports the new size. */ #define CIRCPAD_MAX_MACHINES (2) /** Which padding machine index was this for. * (make sure changes to the bitwidth can support the * CIRCPAD_MAX_MACHINES define). */ unsigned machine_index : 1; } circpad_machine_state_t; /** Helper macro to get an actual state machine from a machineinfo */ #define CIRCPAD_GET_MACHINE(machineinfo) \ ((machineinfo)->on_circ->padding_machine[(machineinfo)->machine_index]) /** * 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. */ typedef uint8_t circpad_machine_num_t; /** Global state machine structure from the consensus */ typedef struct circpad_machine_spec_t { /** Global machine number */ circpad_machine_num_t machine_num; /** Which machine index slot should this machine go into in * the array on the circuit_t */ unsigned machine_index : 1; /** Send a padding negotiate to shut down machine at end state? */ unsigned should_negotiate_end : 1; // These next three fields are origin machine-only... /** Origin side or relay side */ unsigned is_origin_side : 1; /** Which hop in the circuit should we send padding to/from? * 1-indexed (ie: hop #1 is guard, #2 middle, #3 exit). */ unsigned target_hopnum : 3; /** This machine only kills fascists if the following conditions are met. */ circpad_machine_conditions_t conditions; /** How many padding cells can be sent before we apply overhead limits? * XXX: Note that we can only allow up to 64k of padding cells on an * otherwise quiet circuit. Is this enough? It's 33MB. */ uint16_t allowed_padding_count; /** Padding percent cap: Stop padding if we exceed this percent overhead. * 0 means no limit. Overhead is defined as percent of total traffic, so * that we can use 0..100 here. This is the same definition as used in * Prop#265. */ uint8_t max_padding_percent; /** State array: indexed by circpad_statenum_t */ circpad_state_t *states; /** * Number of states this machine has (ie: length of the states array). * XXX: This field is not needed other than for safety. */ circpad_statenum_t num_states; } circpad_machine_spec_t; void circpad_new_consensus_params(const networkstatus_t *ns); /** * The following are event call-in points that are of interest to * the state machines. They are called during cell processing. */ void circpad_deliver_unrecognized_cell_events(struct circuit_t *circ, cell_direction_t dir); void circpad_deliver_sent_relay_cell_events(struct circuit_t *circ, uint8_t relay_command); void circpad_deliver_recognized_relay_cell_events(struct circuit_t *circ, uint8_t relay_command, crypt_path_t *layer_hint); /** Cell events are delivered by the above delivery functions */ void circpad_cell_event_nonpadding_sent(struct circuit_t *on_circ); void circpad_cell_event_nonpadding_received(struct circuit_t *on_circ); void circpad_cell_event_padding_sent(struct circuit_t *on_circ); void circpad_cell_event_padding_received(struct circuit_t *on_circ); /** Internal events are events the machines send to themselves */ circpad_decision_t circpad_internal_event_infinity(circpad_machine_state_t *mi); circpad_decision_t circpad_internal_event_bins_empty(circpad_machine_state_t *); circpad_decision_t circpad_internal_event_state_length_up( circpad_machine_state_t *); /** Machine creation events are events that cause us to set up or * tear down padding state machines. */ void circpad_machine_event_circ_added_hop(struct origin_circuit_t *on_circ); void circpad_machine_event_circ_built(struct origin_circuit_t *circ); void circpad_machine_event_circ_purpose_changed(struct origin_circuit_t *circ); void circpad_machine_event_circ_has_streams(struct origin_circuit_t *circ); void circpad_machine_event_circ_has_no_streams(struct origin_circuit_t *circ); void circpad_machine_event_circ_has_no_relay_early(struct origin_circuit_t *circ); void circpad_machines_init(void); void circpad_machines_free(void); void circpad_machine_states_init(circpad_machine_spec_t *machine, circpad_statenum_t num_states); void circpad_circuit_free_all_machineinfos(struct circuit_t *circ); bool circpad_padding_is_from_expected_hop(struct circuit_t *circ, crypt_path_t *from_hop); /** Serializaton functions for writing to/from torrc and consensus */ char *circpad_machine_spec_to_string(const circpad_machine_spec_t *machine); const circpad_machine_spec_t *circpad_string_to_machine(const char *str); /* Padding negotiation between client and middle */ signed_error_t circpad_handle_padding_negotiate(struct circuit_t *circ, struct cell_t *cell); signed_error_t circpad_handle_padding_negotiated(struct circuit_t *circ, struct cell_t *cell, crypt_path_t *layer_hint); signed_error_t circpad_negotiate_padding(struct origin_circuit_t *circ, circpad_machine_num_t machine, uint8_t target_hopnum, uint8_t command); bool circpad_padding_negotiated(struct circuit_t *circ, circpad_machine_num_t machine, uint8_t command, uint8_t response); MOCK_DECL(circpad_decision_t, circpad_machine_schedule_padding,(circpad_machine_state_t *)); MOCK_DECL(circpad_decision_t, circpad_machine_spec_transition, (circpad_machine_state_t *mi, circpad_event_t event)); circpad_decision_t circpad_send_padding_cell_for_callback( circpad_machine_state_t *mi); #ifdef CIRCUITPADDING_PRIVATE STATIC circpad_delay_t circpad_machine_sample_delay(circpad_machine_state_t *mi); STATIC bool circpad_machine_reached_padding_limit(circpad_machine_state_t *mi); STATIC circpad_decision_t circpad_machine_remove_token(circpad_machine_state_t *mi); STATIC circpad_delay_t circpad_histogram_bin_to_usec(const circpad_machine_state_t *mi, circpad_hist_index_t bin); STATIC const circpad_state_t * circpad_machine_current_state(const circpad_machine_state_t *mi); STATIC circpad_hist_index_t circpad_histogram_usec_to_bin( const circpad_machine_state_t *mi, circpad_delay_t us); STATIC circpad_machine_state_t *circpad_circuit_machineinfo_new( struct circuit_t *on_circ, int machine_index); STATIC void circpad_machine_remove_higher_token(circpad_machine_state_t *mi, circpad_delay_t target_bin_us); STATIC void circpad_machine_remove_lower_token(circpad_machine_state_t *mi, circpad_delay_t target_bin_us); STATIC void circpad_machine_remove_closest_token(circpad_machine_state_t *mi, circpad_delay_t target_bin_us, bool use_usec); STATIC void circpad_machine_setup_tokens(circpad_machine_state_t *mi); MOCK_DECL(STATIC signed_error_t, circpad_send_command_to_hop,(struct origin_circuit_t *circ, uint8_t hopnum, uint8_t relay_command, const uint8_t *payload, ssize_t payload_len)); #ifdef TOR_UNIT_TESTS extern smartlist_t *origin_padding_machines; extern smartlist_t *relay_padding_machines; #endif #endif #endif