path: root/src/core/or/circuitpadding.h

/*
 * Copyright (c) 2017-2020, 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 "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,
  /* This state has used up its cell count */
  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;
#define CIRCPAD_DELAY_UNITS_PER_SECOND  (1000*1000)

/**
 * 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?
 */
#define CIRCPAD_DELAY_INFINITE  (UINT32_MAX)

/**
 * This is the maximum delay that the circuit padding system can have, in
 * seconds.
 */
#define CIRCPAD_DELAY_MAX_SECS   \
    ((CIRCPAD_DELAY_INFINITE/CIRCPAD_DELAY_UNITS_PER_SECOND)+1)

/**
 * Macro to clarify when we're checking the infinity bin.
 *
 * Works with either circpad_state_t or circpad_machine_runtime_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;

  /**
   * This machine is ok to use if reduced padding is set in consensus
   * or torrc. This machine will still be applied even if reduced padding
   * is not set; this flag only acts to exclude machines that don't have
   * it set when reduced padding is requested. Therefore, reduced padding
   * machines should appear at the lowest priority in the padding machine
   * lists (aka first in the list), so that non-reduced padding machines
   * for the same purpose are given a chance to apply when reduced padding
   * is not requested. */
  unsigned reduced_padding_ok : 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.
 *
 * Each distribution takes up to two parameters which are described below. */
typedef enum {
  /* No probability distribution is used */
  CIRCPAD_DIST_NONE = 0,
  /* Uniform distribution: param1 is lower bound and param2 is upper bound */
  CIRCPAD_DIST_UNIFORM = 1,
  /* Logistic distribution: param1 is Mu, param2 is sigma. */
  CIRCPAD_DIST_LOGISTIC = 2,
  /* Log-logistic distribution: param1 is Alpha, param2 is 1.0/Beta */
  CIRCPAD_DIST_LOG_LOGISTIC = 3,
  /* Geometric distribution: param1 is 'p' (success probability) */
  CIRCPAD_DIST_GEOMETRIC = 4,
  /* Weibull distribution: param1 is k, param2 is Lambda */
  CIRCPAD_DIST_WEIBULL = 5,
  /* Generalized Pareto distribution: param1 is sigma, param2 is xi */
  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 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.
 */
#define CIRCPAD_MAX_HISTOGRAM_LEN (100)

/**
 * 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_runtime_t.
 *
 * This struct describes the histograms and/or probability distributions, as
 * well as 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.
   *
   * In particular, the following histogram:
   *
   * Tokens
   *         +
   *      10 |    +----+
   *       9 |    |    |           +---------+
   *       8 |    |    |           |         |
   *       7 |    |    |     +-----+         |
   *       6 +----+ Bin+-----+     |         +---------------+
   *       5 |    | #1 |     |     |         |               |
   *         | Bin|    | Bin | Bin |  Bin #4 |    Bin #5     |
   *         | #0 |    | #2  | #3  |         | (infinity bin)|
   *         |    |    |     |     |         |               |
   *         |    |    |     |     |         |               |
   *       0 +----+----+-----+-----+---------+---------------+
   *         0   100  200   350   500      1000             inf  microseconds
   *
   * would be specified the following way: