diff options
Diffstat (limited to 'doc/HACKING')
| -rw-r--r-- | doc/HACKING/CircuitPaddingDevelopment.md | 1234 | ||||
| -rw-r--r-- | doc/HACKING/CircuitPaddingQuickStart.md | 266 | ||||
| -rw-r--r-- | doc/HACKING/CodeStructure.md | 129 | ||||
| -rw-r--r-- | doc/HACKING/CodingStandards.md | 283 | ||||
| -rw-r--r-- | doc/HACKING/CodingStandardsRust.md | 330 | ||||
| -rw-r--r-- | doc/HACKING/Fuzzing.md | 60 | ||||
| -rw-r--r-- | doc/HACKING/GettingStarted.md | 85 | ||||
| -rw-r--r-- | doc/HACKING/GettingStartedRust.md | 90 | ||||
| -rw-r--r-- | doc/HACKING/HelpfulTools.md | 224 | ||||
| -rw-r--r-- | doc/HACKING/HowToReview.md | 20 | ||||
| -rw-r--r-- | doc/HACKING/Maintaining.md | 113 | ||||
| -rw-r--r-- | doc/HACKING/Module.md | 49 | ||||
| -rw-r--r-- | doc/HACKING/README.1st.md | 47 | ||||
| -rw-r--r-- | doc/HACKING/ReleaseSeriesLifecycle.md | 113 | ||||
| -rw-r--r-- | doc/HACKING/ReleasingTor.md | 191 | ||||
| -rw-r--r-- | doc/HACKING/Tracing.md | 91 | ||||
| -rw-r--r-- | doc/HACKING/WritingTests.md | 205 | ||||
| -rw-r--r-- | doc/HACKING/android/Simpleperf.md | 9 | ||||
| -rw-r--r-- | doc/HACKING/tracing/EventsCircuit.md | 139 | ||||
| -rw-r--r-- | doc/HACKING/tracing/README.md | 163 |
20 files changed, 2927 insertions, 914 deletions
diff --git a/doc/HACKING/CircuitPaddingDevelopment.md b/doc/HACKING/CircuitPaddingDevelopment.md new file mode 100644 index 0000000000..95ffbae4dd --- /dev/null +++ b/doc/HACKING/CircuitPaddingDevelopment.md @@ -0,0 +1,1234 @@ +# Circuit Padding Developer Documentation + +This document is written for researchers who wish to prototype and evaluate circuit-level padding defenses in Tor. + +Written by Mike Perry and George Kadianakis. + +# Table of Contents + +- [0. Background](#0-background) +- [1. Introduction](#1-introduction) + - [1.1. System Overview](#11-system-overview) + - [1.2. Layering Model](#12-layering-model) + - [1.3. Computation Model](#13-computation-model) + - [1.4. Deployment Constraints](#14-other-deployment-constraints) +- [2. Creating New Padding Machines](#2-creating-new-padding-machines) + - [2.1. Registering a New Padding Machine](#21-registering-a-new-padding-machine) + - [2.2. Machine Activation and Shutdown](#22-machine-activation-and-shutdown) +- [3. Specifying Padding Machines](#3-specifying-padding-machines) + - [3.1. Padding Machine States](#31-padding-machine-states) + - [3.2. Padding Machine State Transitions](#32-padding-machine-state-transitions) + - [3.3. Specifying Per-State Padding](#33-specifying-per-state-padding) + - [3.4. Specifying Precise Cell Counts](#34-specifying-precise-cell-counts) + - [3.5. Specifying Overhead Limits](#35-specifying-overhead-limits) +- [4. Evaluating Padding Machines](#4-evaluating-padding-machines) + - [4.1. Pure Simulation](#41-pure-simulation) + - [4.2. Testing in Chutney](#42-testing-in-chutney) + - [4.3. Testing in Shadow](#43-testing-in-shadow) + - [4.4. Testing on the Live Network](#44-testing-on-the-live-network) +- [5. Example Padding Machines](#5-example-padding-machines) + - [5.1. Deployed Circuit Setup Machines](#51-deployed-circuit-setup-machines) + - [5.2. Adaptive Padding Early](#52-adaptive-padding-early) + - [5.3. Sketch of Tamaraw](#53-sketch-of-tamaraw) + - [5.4. Other Padding Machines](#54-other-padding-machines) +- [6. Framework Implementation Details](#6-framework-implementation-details) + - [6.1. Memory Allocation Conventions](#61-memory-allocation-conventions) + - [6.2. Machine Application Events](#62-machine-application-events) + - [6.3. Internal Machine Events](#63-internal-machine-events) +- [7. Future Features and Optimizations](#7-future-features-and-optimizations) + - [7.1. Load Balancing and Flow Control](#71-load-balancing-and-flow-control) + - [7.2. Timing and Queuing Optimizations](#72-timing-and-queuing-optimizations) + - [7.3. Better Machine Negotiation](#73-better-machine-negotiation) + - [7.4. Probabilistic State Transitions](#74-probabilistic-state-transitions) + - [7.5. More Complex Pattern Recognition](#75-more-complex-pattern-recognition) +- [8. Open Research Problems](#8-open-research-problems) + - [8.1. Onion Service Circuit Setup](#81-onion-service-circuit-setup) + - [8.2. Onion Service Fingerprinting](#82-onion-service-fingerprinting) + - [8.3. Open World Fingerprinting](#83-open-world-fingerprinting) + - [8.4. Protocol Usage Fingerprinting](#84-protocol-usage-fingerprinting) + - [8.5. Datagram Transport Side Channels](#85-datagram-transport-side-channels) +- [9. Must Read Papers](#9-must-read-papers) + + +## 0. Background + +Tor supports both connection-level and circuit-level padding, and both +systems are live on the network today. The connection-level padding behavior +is described in [section 2 of +padding-spec.txt](https://github.com/torproject/torspec/blob/master/padding-spec.txt#L47). The +circuit-level padding behavior is described in [section 3 of +padding-spec.txt](https://github.com/torproject/torspec/blob/master/padding-spec.txt#L282). + +These two systems are orthogonal and should not be confused. The +connection-level padding system is only active while the TLS connection is +otherwise idle. Moreover, it regards circuit-level padding as normal data +traffic, and hence while the circuit-level padding system is actively padding, +the connection-level padding system will not add any additional overhead. + +While the currently deployed circuit-level padding behavior is quite simple, +it is built on a flexible framework. This framework supports the description +of event-driven finite state machine by filling in fields of a simple C +structure, and is designed to support any delay-free statistically shaped +cover traffic on individual circuits, with cover traffic flowing to and from a +node of the implementor's choice (Guard, Middle, Exit, Rendezvous, etc). + +This class of system was first proposed in +[Timing analysis in low-latency mix networks: attacks and defenses](https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf) +by Shmatikov and Wang, and extended for the website traffic fingerprinting +domain by Juarez et al. in +[Toward an Efficient Website Fingerprinting Defense](http://arxiv.org/pdf/1512.00524). The +framework also supports fixed parameterized probability distributions, as +used in [APE](https://www.cs.kau.se/pulls/hot/thebasketcase-ape/) by Tobias +Pulls, and many other features. + +This document describes how to use Tor's circuit padding framework to +implement and deploy novel delay-free cover traffic defenses. + +## 1. Introduction + +The circuit padding framework is the official way to implement padding +defenses in Tor. It may be used in combination with application-layer +defenses, and/or obfuscation defenses, or on its own. + +Its current design should be enough to deploy most defenses without +modification, but you can extend it to [provide new +features](#7-future-features-and-optimizations) as well. + +### 1.1. System Overview + +Circuit-level padding can occur between Tor clients and relays at any hop of +one of the client's circuits. Both parties need to support the same padding +mechanisms for the system to work, and the client must enable it. + +We added a padding negotiation relay cell to the Tor protocol that clients use +to ask a relay to start padding, as well as a torrc directive for researchers +to pin their clients' relay selection to the subset of Tor nodes that +implement their custom defenses, to support ethical live network testing and +evaluation. + +Circuit-level padding is performed by 'padding machines'. A padding machine is +a finite state machine. Every state specifies a different form of +padding style, or stage of padding, in terms of inter-packet timings and total +packet counts. + +Padding state machines are specified by filling in fields of a C structure, +which specifies the transitions between padding states based on various events, +probability distributions of inter-packet delays, and the conditions under +which padding machines should be applied to circuits. + +This compact C structure representation is designed to function as a +microlanguage, which can be compiled down into a +bitstring that [can be tuned](#13-computation-model) using various +optimization methods (such as gradient descent, GAs, or GANs), either in +bitstring form or C struct form. + +The event driven, self-contained nature of this framework is also designed to +make [evaluation](#4-evaluating-padding-machines) both expedient and rigorously +reproducible. + +This document covers the engineering steps to write, test, and deploy a +padding machine, as well as how to extend the framework to support new machine +features. + +If you prefer to learn by example, you may want to skip to either the +[QuickStart Guide](CircuitPaddingQuickStart.md), and/or [Section +5](#5-example-padding-machines) for example machines to get you up and running +quickly. + +### 1.2. Layering Model + +The circuit padding framework is designed to provide one layer in a layered +system of interchangeable components. + +The circuit padding framework operates at the Tor circuit layer. It only deals +with the inter-cell timings and quantity of cells sent on a circuit. It can +insert cells on a circuit in arbitrary patterns, and in response to arbitrary +conditions, but it cannot delay cells. It also does not deal with packet +sizes, how cells are packed into TLS records, or ways that the Tor protocol +might be recognized on the wire. + +The problem of differentiating Tor traffic from non-Tor traffic based on +TCP/TLS packet sizes, initial handshake patterns, and DPI characteristics is the +domain of [pluggable +transports](https://gitlab.torproject.org/tpo/anti-censorship/team/-/wikis/AChildsGardenOfPluggableTransports), +which may optionally be used in conjunction with this framework (or without +it). + +This document focuses primarily on the circuit padding framework's cover +traffic features, and will only briefly touch on the potential obfuscation and +application layer coupling points of the framework. Explicit layer coupling +points can be created by adding either new [machine application +events](#62-machine-application-events) or new [internal machine +events](#63-internal-machine-events) to the circuit padding framework, so that +your padding machines can react to events from other layers. + +### 1.3. Computation Model + +The circuit padding framework is designed to support succinctly specified +defenses that can be tuned through [computer-assisted +optimization](#4-evaluating-padding-machines). + +We chose to generalize the original [Adaptive Padding 2-state +design](https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf) into an +event-driven state machine because state machines are the simplest form of +sequence recognition devices from [automata +theory](https://en.wikipedia.org/wiki/Finite-state_machine). + +Most importantly: this framing allows cover traffic defenses to be modeled as +an optimization problem search space, expressed as fields of a C structure +(which is simultaneously a compact opaque bitstring as well as a symbolic +vector in an abstract feature space). This kind of space is particularly well +suited to search by gradient descent, GAs, and GANs. + +When performing this optimization search, each padding machine should have a +fitness function, which will allow two padding machines to be compared for +relative effectiveness. Optimization searches work best if this fitness can be +represented as a single number, for example the total amount by which it +reduces the [Balanced +Accuracy](https://en.wikipedia.org/wiki/Precision_and_recall#Imbalanced_Data) +of an adversary's classifier, divided by an amount of traffic overhead. + +Before you begin the optimization phase for your defense, you should +also carefully consider the [features and +optimizations](#7-future-features-and-optimizations) that we suspect will be +useful, and also see if you can come up with any more. You should similarly be +sure to restrict your search space to avoid areas of the bitstring/feature +vector that you are sure you will not need. For example, some +[applications](#8-open-research-problems) may not need the histogram +accounting used by Adaptive Padding, but might need to add other forms of +[pattern recognition](#75-more-complex-pattern-recognition) to react to +sequences that resemble HTTP GET and HTTP POST. + +### 1.4. Other Deployment Constraints + +The framework has some limitations that are the result of deliberate +choices. We are unlikely to deploy defenses that ignore these limitations. + +In particular, we have deliberately not provided any mechanism to delay actual +user traffic, even though we are keenly aware that if we were to support +additional delay, defenses would be able to have [more success with less +bandwidth +overhead](https://freedom.cs.purdue.edu/anonymity/trilemma/index.html). + +In the website traffic fingerprinting domain, [provably optimal +defenses](https://www.cypherpunks.ca/~iang/pubs/webfingerprint-ccs14.pdf) +achieve their bandwidth overhead bounds by ensuring that a non-empty queue is +maintained, by rate limiting traffic below the actual throughput of a circuit. +For optimal results, this queue must avoid draining to empty, and yet it +must also be drained fast enough to avoid tremendous queue overhead in fast +Tor relays, which carry hundreds of thousands of circuits simultaneously. + +Unfortunately, Tor's end-to-end flow control is not congestion control. Its +window sizes are currently fixed. This means there is no signal when queuing +occurs, and thus no ability to limit queue size through pushback. This means +there is currently no way to do the fine-grained queue management necessary to +create such a queue and rate limit traffic effectively enough to keep this +queue from draining to empty, without also risking that aggregate queuing +would cause out-of-memory conditions on fast relays. + +It may be possible to create a congestion control algorithm that can support +such fine grained queue management, but this is a [deeply unsolved area of +research](https://lists.torproject.org/pipermail/tor-dev/2018-November/013562.html). + +Even beyond these major technical hurdles, additional latency is also +unappealing to the wider Internet community, for the simple reason that +bandwidth [continues to increase +exponentially](https://ipcarrier.blogspot.com/2014/02/bandwidth-growth-nearly-what-one-would.html) +where as the speed of light is fixed. Significant engineering effort has been +devoted to optimizations that reduce the effect of latency on Internet +protocols. To go against this trend would ensure our irrelevance to the wider +conversation about traffic analysis defenses for low latency Internet protocols. + +On the other hand, through [load +balancing](https://gitweb.torproject.org/torspec.git/tree/proposals/265-load-balancing-with-overhead.txt) +and [circuit multiplexing strategies](https://bugs.torproject.org/29494), we +believe it is possible to add significant bandwidth overhead in the form of +cover traffic, without significantly impacting end-user performance. + +For these reasons, we believe the trade-off should be in favor of adding more +cover traffic, rather than imposing queuing memory overhead and queuing delay. + +As a last resort for narrowly scoped application domains (such as +shaping Tor service-side onion service traffic to look like other websites or +different application-layer protocols), delay *may* be added at the +[application layer](https://petsymposium.org/2017/papers/issue2/paper54-2017-2-source.pdf). +Any additional cover traffic required by such defenses should still be +added at the circuit padding layer using this framework, to provide +engineering efficiency through loose layer coupling and component re-use, as +well as to provide additional gains against [low +resolution](https://github.com/torproject/torspec/blob/master/padding-spec.txt#L47) +end-to-end traffic correlation. + +Because such delay-based defenses will impact performance significantly more +than simply adding cover traffic, they must be optional, and negotiated by +only specific application layer endpoints that want them. This will have +consequences for anonymity sets and base rates, if such traffic shaping and +additional cover traffic is not very carefully constructed. + +In terms of acceptable overhead, because Tor onion services +[currently use](https://metrics.torproject.org/hidserv-rend-relayed-cells.html) +less than 1% of the +[total consumed bandwidth](https://metrics.torproject.org/bandwidth-flags.html) +of the Tor network, and because onion services exist to provide higher +security as compared to Tor Exit traffic, they are an attractive target for +higher-overhead defenses. We encourage researchers to target this use case +for defenses that require more overhead, and/or for the deployment of +optional negotiated application-layer delays on either the server or the +client side. + +## 2. Creating New Padding Machines + +This section explains how to use the existing mechanisms in Tor to define a +new circuit padding machine. We assume here that you know C, and are at +least somewhat familiar with Tor development. For more information on Tor +development in general, see the other files in doc/HACKING/ in a recent Tor +distribution. + +Again, if you prefer to learn by example, you may want to skip to either the +[QuickStart Guide](CircuitPaddingQuickStart.md), and/or [Section +5](#5-example-padding-machines) for example machines to get up and running +quickly. + +To create a new padding machine, you must: + + 1. Define your machine using the fields of a heap-allocated + `circpad_machine_spec_t` C structure. + + 2. Register this object in the global list of available padding machines, + using `circpad_register_padding_machine()`. + + 3. Ensure that your machine is properly negotiated under your desired + circuit conditions. + +### 2.1. Registering a New Padding Machine + +Again, a circuit padding machine is designed to be specified entirely as a [single +C structure](#13-computation-model). + +Your machine definitions should go into their own functions in +[circuitpadding_machines.c](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding_machines.c). For +details on all of the fields involved in specifying a padding machine, see +[Section 3](#3-specifying-padding-machines). + +You must register your machine in `circpad_machines_init()` in +[circuitpadding.c](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding.c). To +add a new padding machine specification, you must allocate a +`circpad_machine_spec_t` on the heap with `tor_malloc_zero()`, give it a +human readable name string, and a machine number equivalent to the number of +machines in the list, and register the structure using +`circpad_register_padding_machine()`. + +Each machine must have a client instance and a relay instance. Register your +client-side machine instance in the `origin_padding_machines` list, and your +relay side machine instance in the `relay_padding_machines` list. Once you +have registered your instance, you do not need to worry about deallocation; +this is handled for you automatically. + +Both machine lists use registration order to signal machine precedence for a +given `machine_idx` slot on a circuit. This means that machines that are +registered last are checked for activation *before* machines that are +registered first. (This reverse precedence ordering allows us to +deprecate older machines simply by adding new ones after them.) + +### 2.2. Machine Activation and Shutdown + +After a machine has been successfully registered with the framework, it will +be instantiated on any client-side circuits that support it. Only client-side +circuits may initiate padding machines, but either clients or relays may shut +down padding machines. + +#### 2.2.1. Machine Application Conditions + +The +[circpad_machine_conditions_t conditions field](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L641) +of your `circpad_machine_spec_t` machine definition instance controls the +conditions under which your machine will be attached and enabled on a Tor +circuit, and when it gets shut down. + +*All* of your explicitly specified conditions in +`circpad_machine_spec_t.conditions` *must* be met for the machine to be +applied to a circuit. If *any* condition ceases to be met, then the machine +is shut down. (This is checked on every event that arrives, even if the +condition is unrelated to the event.) +Another way to look at this is that +all specified conditions must evaluate to true for the entire duration that +your machine is running. If any are false, your machine does not run (or +stops running and shuts down). + +In particular, as part of the +[circpad_machine_conditions_t structure](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding.h#L149), +the circuit padding subsystem gives the developer the option to enable a +machine based on: + - The + [length](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L157) + on the circuit (via the `min_hops` field). + - The + [current state](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L174) + of the circuit, such as streams, relay_early, etc. (via the + `circpad_circuit_state_t state_mask` field). + - The + [purpose](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L178) + (i.e. type) of the circuit (via the `circpad_purpose_mask_t purpose_mask` + field). + +This condition mechanism is the preferred way to determine if a machine should +apply to a circuit. For information about potentially useful conditions that +we have considered but have not yet implemented, see [Section +7.3](#73-better-machine-negotiation). We will happily accept patches for those +conditions, or any for other additional conditions that are needed for your +use case. + +#### 2.2.2. Detecting and Negotiating Machine Support + +When a new machine specification is added to Tor (or removed from Tor), you +should bump the Padding subprotocol version in `src/core/or/protover.c` and +`src/rust/protover/protover.rs`, add a field to `protover_summary_flags_t` in +`or.h`, and set this field in `memoize_protover_summary()` in versions.c. This +new field must then be checked in `circpad_node_supports_padding()` in +`circuitpadding.c`. + +Note that this protocol version update and associated support check is not +necessary if your experiments will *only* be using your own relays that +support your own padding machines. This can be accomplished by using the +`MiddleNodes` directive; see [Section 4](#4-evaluating-padding-machines) for more information. + +If the protocol support check passes for the circuit, then the client sends a +`RELAY_COMMAND_PADDING_NEGOTIATE` cell towards the +`circpad_machine_spec_t.target_hop` relay, and immediately enables the +padding machine, and may begin sending padding. (The framework does not wait +for the `RELAY_COMMAND_PADDING_NEGOTIATED` response to begin padding, +so that we can +switch between machines rapidly.) + +#### 2.2.3. Machine Shutdown Mechanisms + +Padding machines can be shut down on a circuit in three main ways: + 1. During a `circpad_machine_event` callback, when + `circpad_machine_spec_t.conditions` no longer applies (client side) + 2. After a transition to the CIRCPAD_STATE_END, if + `circpad_machine_spec_t.should_negotiate_end` is set (client or relay + side) + 3. If there is a `RELAY_COMMAND_PADDING_NEGOTIATED` error response from the + relay during negotiation. + +Each of these cases causes the originating node to send a relay cell towards +the other side, indicating that shutdown has occurred. The client side sends +`RELAY_COMMAND_PADDING_NEGOTIATE`, and the relay side sends +`RELAY_COMMAND_PADDING_NEGOTIATED`. + +Because padding from malicious exit nodes can be used to construct active +timing-based side channels to malicious guard nodes, the client checks that +padding-related cells only come from relays with active padding machines. +For this reason, when a client decides to shut down a padding machine, +the framework frees the mutable `circuit_t.padding_info`, but leaves the +`circuit_t.padding_machine` pointer set until the +`RELAY_COMMAND_PADDING_NEGOTIATED` response comes back, to ensure that any +remaining in-flight padding packets are recognized a valid. Tor does +not yet close circuits due to violation of this property, but the +[vanguards addon component "bandguard"](https://github.com/mikeperry-tor/vanguards/blob/master/README_TECHNICAL.md#the-bandguards-subsystem) +does. + +As an optimization, a client may replace a machine with another, by +sending a `RELAY_COMMAND_PADDING_NEGOTIATE` cell to shut down a machine, and +immediately sending a `RELAY_COMMAND_PADDING_NEGOTIATE` to start a new machine +in the same index, without waiting for the response from the first negotiate +cell. + +Unfortunately, there is a known bug as a consequence of this optimization. If +your machine depends on repeated shutdown and restart of the same machine +number on the same circuit, please see [Bug +30922](https://bugs.torproject.org/30992). Depending on your use case, we may +need to fix that bug or help you find a workaround. See also [Section +6.1.3](#613-deallocation-and-shutdown) for some more technical details on this +mechanism. + + +## 3. Specifying Padding Machines + +By now, you should understand how to register, negotiate, and control the +lifetime of your padding machine, but you still don't know how to make it do +anything yet. This section should help you understand how to specify how your +machine reacts to events and adds padding to the wire. + +If you prefer to learn by example first instead, you may wish to skip to +[Section 5](#5-example-padding-machines). + + +A padding machine is specified by filling in an instance of +[circpad_machine_spec_t](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L605). Instances +of this structure specify the precise functionality of a machine: it's +what the circuit padding developer is called to write. These instances +are created only at startup, and are referenced via `const` pointers during +normal operation. + +In this section we will go through the most important elements of this +structure. + +### 3.1. Padding Machine States + +A padding machine is a finite state machine where each state +specifies a different style of padding. + +As an example of a simple padding machine, you could have a state machine +with the following states: `[START] -> [SETUP] -> [HTTP] -> [END]` where the +`[SETUP]` state pads in a way that obfuscates the ''circuit setup'' of Tor, +and the `[HTTP]` state pads in a way that emulates a simple HTTP session. Of +course, padding machines can be more complicated than that, with dozens of +states and non-trivial transitions. + +Padding developers encode the machine states in the +[circpad_machine_spec_t structure](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L655). Each +machine state is described by a +[circpad_state_t structure](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L273) +and each such structure specifies the style and amount of padding to be sent, +as well as the possible state transitions. + +The function `circpad_machine_states_init()` must be used for allocating and +initializing the `circpad_machine_spec_t.states` array before states and +state transitions can be defined, as some of the state object has non-zero +default values. + +### 3.2. Padding Machine State Transitions + +As described above, padding machines can have multiple states, to +support different forms of padding. Machines can transition between +states based on events that occur either on the circuit level or on +the machine level. + +State transitions are specified using the +[next_state field](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding.h#L381) +of the `circpad_state_t` structure. As a simple example, to transition +from state `A` to state `B` when event `E` occurs, you would use the +following code: `A.next_state[E] = B`. + +#### 3.2.1. State Transition Events + +Here we will go through +[the various events](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding.h#L30) +that can be used to transition between states: + +* Circuit-level events + * `CIRCPAD_EVENT_NONPADDING_RECV`: A non-padding cell is received + * `CIRCPAD_EVENT_NONPADDING_SENT`: A non-adding cell is sent + * `CIRCPAD_EVENT_PADDING_SENT`: A padding cell is sent + * `CIRCPAD_EVENT_PADDING_RECV`: A padding cell is received +* Machine-level events + * `CIRCPAD_EVENT_INFINITY`: Tried to schedule padding using the ''infinity bin''. + * `CIRCPAD_EVENT_BINS_EMPTY`: All histogram bins are empty (out of tokens) + * `CIRCPAD_EVENT_LENGTH_COUNT`: State has used all its padding capacity (see `length_dist` below) + +### 3.3. Specifying Per-State Padding + +Each state of a padding machine specifies either: + * A padding histogram describing inter-transmission delays between cells; +d OR + * A parameterized delay probability distribution for inter-transmission + delays between cells. + +Either mechanism specifies essentially the *minimum inter-transmission time* +distribution. If non-padding traffic does not get transmitted from this +endpoint before the delay value sampled from this distribution expires, a +padding packet is sent. + +The choice between histograms and probability distributions can be subtle. A +rule of thumb is that probability distributions are easy to specify and +consume very little memory, but might not be able to describe certain types +of complex padding logic. Histograms, in contrast, can support precise +packet-count oriented or multimodal delay schemes, and can use token removal +logic to reduce overhead and shape the total padding+non-padding inter-packet +delay distribution towards an overall target distribution. + +We suggest that you start with a probability distribution if possible, and +you move to a histogram-based approach only if a probability distribution +does not suit your needs. + +#### 3.3.1. Padding Probability Distributions + +The easiest, most compact way to schedule padding using a machine state is to +use a probability distribution that specifies the possible delays. That can +be done +[using the circpad_state_t fields](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L339) +`iat_dist`, `dist_max_sample_usec` and `dist_added_shift_usec`. + +The Tor circuit padding framework +[supports multiple types](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L214) +of probability distributions, and the developer should use the +[circpad_distribution_t structure](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L240) +to specify them as well as the required parameters. + +#### 3.3.2. Padding Histograms + +A more advanced way to schedule padding is to use a ''padding +histogram''. The main advantages of a histogram are that it allows you to +specify distributions that are not easily parameterized in closed form, or +require specific packet counts at particular time intervals. Histograms also +allow you to make use of an optional traffic minimization and shaping +optimization called *token removal*, which is central to the original +[Adaptive Padding](https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf) +concept. + +If a histogram is used by a state (as opposed to a fixed parameterized +distribution), then the developer must use the +[histogram-related fields](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L285) +of the `circpad_state_t` structure. + +The width of a histogram bin specifies the range of inter-packet delay times, +whereas its height specifies the amount of tokens in each bin. To sample a +padding delay from a histogram, we first randomly pick a bin (weighted by the +amount of tokens in each bin) and then sample a delay from within that bin by +picking a uniformly random delay using the width of the bin as the range. + +Each histogram also has an ''infinity bin'' as its final bin. If the +''infinity bin'' is chosen, +we don't schedule any padding (i.e., we schedule padding with +infinite delay). If the developer does not want infinite delay, they +should not give any tokens to the ''infinity bin''. + +If a token removal strategy is specified (via the +`circpad_state_t.token_removal` field), each time padding is sent using a +histogram, the padding machine will remove a token from the appropriate +histogram bin whenever this endpoint sends *either a padding packet or a +non-padding packet*. The different removal strategies govern what to do when +the bin corresponding to the current inter-packet delay is empty. + +Token removal is optional. It is useful if you want to do things like specify +a burst should be at least N packets long, and you only want to add padding +packets if there are not enough non-padding packets. The cost of doing token +removal is additional memory allocations for making per-circuit copies of +your histogram that can be modified. + +### 3.4. Specifying Precise Cell Counts + +Padding machines should be able to specify the exact amount of padding they +send. For histogram-based machines this can be done using a specific amount +of tokens, but another (and perhaps easier) way to do this, is to use the +[length_dist field](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.h#L362) +of the `circpad_state_t` structure. + +The `length_dist` field is basically a probability distribution similar to the +padding probability distributions, which applies to a specific machine state +and specifies the amount of padding we are willing to send during that state. +This value gets sampled when we transition to that state (TODO document this +in the code). + +### 3.5. Specifying Overhead Limits + +Separately from the length counts, it is possible to rate limit the overhead +percentage of padding at both the global level across all machines, and on a +per-machine basis. + +At the global level, the overhead percentage of all circuit padding machines +as compared to total traffic can be limited through the Tor consensus +parameter `circpad_global_max_padding_pct`. This overhead is defined as the +percentage of padding cells *sent* out of the sum of non padding and padding +cells *sent*, and is applied *only after* at least +`circpad_global_allowed_cells` padding cells are sent by that relay or client +(to allow for small bursts of pure padding on otherwise idle or freshly +restarted relays). When both of these limits are hit by a relay or client, no +further padding cells will be sent, until sufficient non-padding traffic is +sent to cause the percentage of padding traffic to fall back below the +threshold. + +Additionally, each individual padding machine can rate limit itself by +filling in the fields `circpad_machine_spec_t.max_padding_percent` and +`circpad_machine_spec_t.allowed_padding_count`, which behave identically to +the consensus parameters, but only apply to that specific machine. + +## 4. Evaluating Padding Machines + +One of the goals of the circuit padding framework is to provide improved +evaluation and scientific reproducibility for lower cost. This includes both +the [choice](#13-computation-model) of the compact C structure representation +(which has an easy-to-produce bitstring representation for optimization by +gradient descent, GAs, or GANs), as well as rapid prototyping and evaluation. + +So far, whenever evaluation cost has been a barrier, each research group has +developed their own ad-hoc packet-level simulators of various padding +mechanisms for evaluating website fingerprinting attacks and defenses. The +process typically involves doing a crawl of Alexa top sites over Tor, and +recording the Tor cell count and timing information for each page in the +trace. These traces are then fed to simulations of defenses, which output +modified trace files. + +Because no standardized simulation and evaluation mechanism exists, it is +often hard to tell if independent implementations of various attacks and +defenses are in fact true-to-form or even properly calibrated for direct +comparison, and discrepancies in results across the literature suggests +this is not always so. + +Our preferred outcome with this framework is that machines are tuned +and optimized on a tracing simulator, but that the final results come from +an actual live network test of the defense. The traces from this final crawl +should be preserved as artifacts to be run on the simulator and reproduced +on the live network by future papers, ideally in journal venues that have an +artifact preservation policy. + +### 4.1. Pure Simulation + +When doing initial tuning of padding machines, especially in adversarial +settings, variations of a padding machine defense may need to be applied to +network activity hundreds or even millions of times. The wall-clock time +required to do this kind of tuning using live testing or even Shadow network +emulation may often be prohibitive. + +To help address this, and to better standardize results, Tobias Pulls has +implemented a [circpad machine trace simulator](https://github.com/pylls/circpad-sim), +which uses Tor's unit test framework to simulate applying padding machines to +circuit packet traces via a combination of Tor patches and python scripts. This +simulator can be used to record traces from clients, Guards, Middles, Exits, +and any other hop in the path, only for circuits that are run by the +researcher. This makes it possible to safely record baseline traces and +ultimately even mount passive attacks on the live network, without impacting +or recording any normal user traffic. + +In this way, a live crawl of the Alexa top sites could be performed once, to +produce a standard "undefended" corpus. Padding machines can be then quickly +evaluated and tuned on these simulated traces in a standardized way, and then +the results can then be [reproduced on the live Tor +network](#44-Testing-on-the-Live-Network) with the machines running on your own relays. + +Please be mindful of the Limitations section of the simulator documentation, +however, to ensure that you are aware of the edge cases and timing +approximations that are introduced by this approach. + +### 4.2. Testing in Chutney + +The Tor Project provides a tool called +[Chutney](https://github.com/torproject/chutney/) which makes it very easy to +setup private Tor networks. While getting it work for the first time might +take you some time of doc reading, the final result is well worth it for the +following reasons: + +- You control all the relays and hence you have greater control and debugging + capabilities. +- You control all the relays and hence you can toggle padding support on/off + at will. +- You don't need to be cautious about overhead or damaging the real Tor + network during testing. +- You don't even need to be online; you can do all your testing offline over + localhost. + +A final word of warning here is that since Chutney runs over localhost, the +packet latencies and delays are completely different from the real Tor +network, so if your padding machines rely on real network timings you will +get different results on Chutney. You can work around this by using a +different set of delays if Chutney is used, or by moving your padding +machines to the real network when you want to do latency-related testing. + +### 4.3. Testing in Shadow + +[Shadow](https://shadow.github.io/) is an environment for running entire Tor +network simulations, similar to Chutney, but designed to be both more memory +efficient, as well as provide an accurate Tor network topology and latency +model. + +While Shadow is significantly more memory efficient than Chutney, and can make +use of extremely accurate Tor network capacity and latency models, it will not +be as fast or efficient as the [circpad trace simulator](https://github.com/pylls/circpad-sim), +if you need to do many many iterations of an experiment to tune your defense. + +### 4.4. Testing on the Live Network + +Live network testing is the gold standard for verifying that any attack or +defense is behaving as expected, to minimize the influence of simplifying +assumptions. + +However, it is not ethical, or necessarily possible, to run high-resolution +traffic analysis attacks on the entire Tor network. But it is both ethical +and possible to run small scale experiments that target only your own +clients, who will only use your own Tor relays that support your new padding +machines. + +We provide the `MiddleNodes` torrc directive to enable this, which will allow +you to specify the fingerprints and/or IP netmasks of relays to be used in +the second hop position. Options to restrict other hops also exist, if your +padding system is padding to a different hop. The `HSLayer2Nodes` option +overrides the `MiddleNodes` option for onion service circuits, if both are +set. (The +[vanguards addon](https://github.com/mikeperry-tor/vanguards/README_TECHNICAL.md) +will set `HSLayer2Nodes`.) + +When you run your own clients, and use MiddleNodes to restrict your clients +to use your relays, you can perform live network evaluations of a defense +applied to whatever traffic crawl or activity your clients do. + +## 5. Example Padding Machines + +### 5.1. Deployed Circuit Setup Machines + +Tor currently has two padding machines enabled by default, which aim to hide +certain features of the client-side onion service circuit setup protocol. For +more details on their precise goal and function, please see +[proposal 302](https://github.com/torproject/torspec/blob/master/proposals/302-padding-machines-for-onion-clients.txt) +. In this section we will go over the code of those machines to clarify some +of the engineering parts: + +#### 5.1.1. Overview + +The codebase of proposal 302 can be found in +[circuitpadding_machines.c](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding_machines.c) +and specifies four padding machines: + +- The [client-side introduction](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L60) circuit machine. +- The [relay-side introduction](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L146) circuit machine. +- The [client-side rendezvous](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L257) circuit machine +- The [relay-side rendezvous](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L374) circuit machine. + +Each of those machines has its own setup function, and +[they are all initialized](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding.c#L2718) +by the circuit padding framework. To understand more about them, please +carefully read the individual setup function for each machine which are +fairly well documented. Each function goes through the following steps: +- Machine initialization + - Give it a [name](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L70) + - Specify [which hop](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L73) the padding should go to + - Specify whether it should be [client-side](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L75) or relay-side. +- Specify for [which types of circuits](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L78) the machine should apply +- Specify whether the circuits should be [kept alive](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding_machines.c#L112) until the machine finishes padding. +- Sets [padding limits](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L116) to avoid too much overhead in case of bugs or errors. +- Setup [machine states](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L120) + - Specify [state transitions](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L123). +- Finally [register the machine](https://github.com/torproject/tor/blob/35e978da61efa04af9a5ab2399dff863bc6fb20a/src/core/or/circuitpadding_machines.c#L137) to the global machine list + +### 5.2. Adaptive Padding Early + +[Adaptive Padding Early](https://www.cs.kau.se/pulls/hot/thebasketcase-ape/) +is a variant of Adaptive Padding/WTF-PAD that does not use histograms or token +removal to shift padding distributions, but instead uses fixed parameterized +distributions to specify inter-packet timing thresholds for burst and gap +inter-packet delays. + +Tobias Pulls's [QuickStart Guide](CircuitPaddingQuickStart.md) describes how +to get this machine up and running, and has links to branches with a working +implementation. + +### 5.3. Sketch of Tamaraw + +The [Tamaraw defense +paper](https://www.cypherpunks.ca/~iang/pubs/webfingerprint-ccs14.pdf) is the +only defense to date that provides a proof of optimality for the finite-length +website traffic fingerprinting domain. These bounds assume that a defense is +able to perform a full, arbitrary transform of a trace that is under a fixed +number of packets in length. + +The key insight to understand Tamaraw's optimality is that it achieves one +such optimal transform by delaying traffic below a circuit's throughput. By +doing this, it creates a queue that is rarely empty, allowing it to produce +a provably optimal transform with minimal overhead. As [Section +1.4](#14-other-deployment-constraints) explains, this queue +cannot be maintained on the live Tor network without risk of out-of-memory +conditions at relays. + +However, if the queue is not maintained in the Tor network, but instead by the +application layer, it could be deployed by websites that opt in to using it. + +In this case, the application layer component would do *optional* constant +rate shaping, negotiated between a web browser and a website. The Circuit +Padding Framework can then easily fill in any missing gaps of cover traffic +packets, and also ensure that only a fixed length number of packets are sent +in total. + +However, for such a defense to be safe, additional care must be taken to +ensure that the resulting traffic pattern still has a large +anonymity/confusion set with other traces on the live network. + +Accomplishing this is an unsolved problem. + +### 5.4. Other Padding Machines + +Our partners in this project at RIT have produced a couple prototypes, based +on their published research designs +[REB and RBB](https://www.researchgate.net/publication/329743510_UNDERSTANDING_FEATURE_DISCOVERY_IN_WEBSITE_FINGERPRINTING_ATTACKS). + +As [their writeup +explains](https://github.com/notem/tor-rbp-padding-machine-doc), because RBB +uses delay, the circuit padding machine that they made is a no-delay version. + +They also ran into an issue with the 0-delay timing workaround for [bug +31653](https://bugs.torproject.org/31653). Keep an eye on that bug for updates +with improved workarounds/fixes. + +Their code is [available on github](https://github.com/notem/tor/tree/circuit_padding_rbp_machine). + + +## 6. Framework Implementation Details + +If you need to add additional events, conditions, or other features to the +circuit padding framework, then this section is for you. + +### 6.1. Memory Allocation Conventions + +If the existing circuit padding features are sufficient for your needs, then +you do not need to worry about memory management or pointer lifespans. The +circuit padding framework should take care of this for you automatically. + +However, if you need to add new padding machine features to support your +padding machines, then it will be helpful to understand how circuits +correspond to the global machine definitions, and how mutable padding machine +memory is managed. + +#### 6.1.1. Circuits and Padding Machines + +In Tor, the +[circuit_t structure](https://github.com/torproject/tor/blob/master/src/core/or/circuit_st.h) +is the superclass structure for circuit-related state that is used on both +clients and relays. On clients, the actual datatype of the object pointed to +by `circuit_t *` is the subclass structure +[origin_circuit_t](https://github.com/torproject/tor/blob/master/src/core/or/origin_circuit_st.h). The +macros `CIRCUIT_IS_ORIGIN()` and `TO_ORIGIN_CIRCUIT()` are used to determine +if a circuit is a client-side (origin) circuit and to cast the pointer safely +to `origin_circuit_t *`. + +Because circuit padding machines can be present at both clients and relays, +the circuit padding fields are stored in the `circuit_t *` superclass +structure. Notice that there are actually two sets of circuit padding fields: +a `const circpad_machine_spec_t *` array, and a `circpad_machine_runtime_t *` +array. Each of these arrays holds at most two elements, as there can be at +most two padding machines on each circuit. + +The `const circpad_machine_spec_t *` points to a globally allocated machine +specification. These machine specifications are +allocated and set up during Tor program startup, in `circpad_machines_init()` +in +[circuitpadding.c](https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding.c). Because +the machine specification object is shared by all circuits, it must not be +modified or freed until program exit (by `circpad_machines_free()`). The +`const` qualifier should enforce this at compile time. + +The `circpad_machine_runtime_t *` array member points to the mutable runtime +information for machine specification at that same array index. This runtime +structure keeps track of the current machine state, packet counts, and other +information that must be updated as the machine operates. When a padding +machine is successfully negotiated `circpad_setup_machine_on_circ()` allocates +the associated runtime information. + +#### 6.1.2. Histogram Management + +If a `circpad_state_t` of a machine specifies a `token_removal` strategy +other than `CIRCPAD_TOKEN_REMOVAL_NONE`, then every time +there is a state transition into this state, `circpad_machine_setup_tokens()` +will copy the read-only `circpad_state_t.histogram` array into a mutable +version at `circpad_machine_runtime_t.histogram`. This mutable copy is used +to decrement the histogram bin accounts as packets are sent, as per the +specified token removal strategy. + +When the state machine transitions out of this state, the mutable histogram copy is freed +by this same `circpad_machine_setup_tokens()` function. + +#### 6.1.3. Deallocation and Shutdown + +As an optimization, padding machines can be swapped in and out by the client +without waiting a full round trip for the relay machine to shut down. + +Internally, this is accomplished by immediately freeing the heap-allocated +`circuit_t.padding_info` field corresponding to that machine, but still preserving the +`circuit_t.padding_machine` pointer to the global padding machine +specification until the response comes back from the relay. Once the response +comes back, that `circuit_t.padding_machine` pointer is set to NULL, if the +response machine number matches the current machine present. + +Because of this partial shutdown condition, we have two macros for iterating +over machines. `FOR_EACH_ACTIVE_CIRCUIT_MACHINE_BEGIN()` is used to iterate +over machines that have both a `circuit_t.padding_info` slot and a +`circuit_t.padding_machine` slot occupied. `FOR_EACH_CIRCUIT_MACHINE_BEGIN()` +is used when we need to iterate over all machines that are either active or +are simply waiting for a response to a shutdown request. + +If the machine is replaced instead of just shut down, then the client frees +the `circuit_t.padding_info`, and then sets the `circuit_t.padding_machine` +and `circuit_t.padding_info` fields for this next machine immediately. This is +done in `circpad_add_matching_machines()`. In this case, since the new machine +should have a different machine number, the shut down response from the relay +is silently discarded, since it will not match the new machine number. + +If this sequence of machine teardown and spin-up happens rapidly enough for +the same machine number (as opposed to different machines), then a race +condition can happen. This is +[known bug #30992](https://bugs.torproject.org/30992). + +When the relay side decides to shut down a machine, it sends a +`RELAY_COMMAND_PADDING_NEGOTIATED` towards the client. If this cell matches the +current machine number on the client, that machine is torn down, by freeing +the `circuit_t.padding_info` slot and immediately setting +`circuit_t.padding_machine` slot to NULL. + +Additionally, if Tor decides to close a circuit forcibly due to error before +the padding machine is shut down, then `circuit_t.padding_info` is still +properly freed by the call to `circpad_circuit_free_all_machineinfos()` +in `circuit_free_()`. + +### 6.2. Machine Application Events + +The framework checks client-side origin circuits to see if padding machines +should be activated or terminated during specific event callbacks in +`circuitpadding.c`. We list these event callbacks here only for reference. You +should not modify any of these callbacks to get your machine to run; instead, +you should use the `circpad_machine_spec_t.conditions` field. + +However, you may add new event callbacks if you need other activation events, +for example to provide obfuscation-layer or application-layer signaling. Any +new event callbacks should behave exactly like the existing callbacks. + +During each of these event callbacks, the framework checks to see if any +current running padding machines have conditions that no longer apply as a +result of the event, and shuts those machines down. Then, it checks to see if +any new padding machines should be activated as a result of the event, based +on their circuit application conditions. **Remember: Machines are checked in +reverse order in the machine list. This means that later, more recently added +machines take precedence over older, earlier entries in each list.** + +Both of these checks are performed using the machine application conditions +that you specify in your machine's `circpad_machine_spec_t.conditions` field. + +The machine application event callbacks are prefixed by `circpad_machine_event_` by convention in circuitpadding.c. As of this writing, these callbacks are: + + - `circpad_machine_event_circ_added_hop()`: Called whenever a new hop is + added to a circuit. + - `circpad_machine_event_circ_built()`: Called when a circuit has completed + construction and is + opened. <!-- open != ready for traffic. Which do we mean? -nickm --> + - `circpad_machine_event_circ_purpose_changed()`: Called when a circuit + changes purpose. + - `circpad_machine_event_circ_has_no_relay_early()`: Called when a circuit + runs out of `RELAY_EARLY` cells. + - `circpad_machine_event_circ_has_streams()`: Called when a circuit gets a + stream attached. + - `circpad_machine_event_circ_has_no_streams()`: Called when the last + stream is detached from a circuit. + +### 6.3. Internal Machine Events + +To provide for some additional capabilities beyond simple finite state machine +behavior, the circuit padding machines also have internal events that they +emit to themselves when packet count length limits are hit, when the Infinity +bin is sampled, and when the histogram bins are emptied of all tokens. + +These events are implemented as `circpad_internal_event_*` functions in +`circuitpadding.c`, which are called from various areas that determine when +the events should occur. + +While the conditions that trigger these internal events to be called may be +complex, they are processed by the state machine definitions in a nearly +identical manner as the cell processing events, with the exception that they +are sent to the current machine only, rather than all machines on the circuit. + + +## 7. Future Features and Optimizations + +While implementing the circuit padding framework, our goal was to deploy a +system that obscured client-side onion service circuit setup and supported +deployment of WTF-PAD and/or APE. Along the way, we noticed several features +that might prove useful to others, but were not essential to implement +immediately. We do not have immediate plans to implement these ideas, but we +would gladly accept patches that do so. + +The following list gives an overview of these improvements, but as this +document ages, it may become stale. The canonical list of improvements that +researchers may find useful is labeled in our bugtracker with +[Padding Research](https://gitlab.torproject.org/tpo/core/tor/-/issues?scope=all&utf8=%E2%9C%93&state=opened&label_name[]=Padding%20Research), +and the list of improvements that are known to be necessary for some research +areas are labeled with +[Padding Research Requires](https://gitlab.torproject.org/tpo/core/tor/-/issues?scope=all&utf8=%E2%9C%93&state=opened&label_name[]=Padding%20Research%20Requires). + +Please consult those lists for the latest status of these issues. Note that +not all fixes will be backported to all Tor versions, so be mindful of which +Tor releases receive which fixes as you conduct your experiments. + +### 7.1. Load Balancing and Flow Control + +Fortunately, non-Exit bandwidth is already plentiful and exceeds the Exit +capacity, and we anticipate that if we inform our relay operator community of +the need for non-Exit bandwidth to satisfy padding overhead requirements, +they will be able to provide that with relative ease. + +Unfortunately, padding machines that have large quantities of overhead will +require changes to our load balancing system to account for this +overhead. The necessary changes are documented in +[Proposal 265](https://gitweb.torproject.org/torspec.git/tree/proposals/265-load-balancing-with-overhead.txt). + +Additionally, padding cells are not currently subjected to flow control. For +high amounts of padding, we may want to change this. See [ticket +31782](https://bugs.torproject.org/31782) for details. + +### 7.2. Timing and Queuing Optimizations + +The circuitpadding framework has some timing related issues that may impact +results. If high-resolution timestamps are fed to opaque deep learning +trainers, those training models may end up able to differentiate padding +traffic from non-padding traffic due to these timing bugs. + +The circuit padding cell event callbacks come from post-decryption points in +the cell processing codepath, and from the pre-queue points in the cell send +codepath. This means that our cell events will not reflect the actual time +when packets are read or sent on the wire. This is much worse in the send +direction, as the circuitmux queue, channel outbuf, and kernel TCP buffer will +impose significant additional delay between when we currently report that a +packet was sent, and when it actually hits the wire. + +[Ticket 29494](https://bugs.torproject.org/29494) has a more detailed +description of this problem, and an experimental branch that changes the cell +event callback locations to be from circuitmux post-queue, which with KIST, +should be an accurate reflection of when they are actually sent on the wire. + +If your padding machine and problem space depends on very accurate notions of +relay-side packet timing, please try that branch and let us know on the +ticket if you need any further assistance fixing it up. + +Additionally, with these changes, it will be possible to provide further +overhead reducing optimizations by letting machines specify flags to indicate +that padding should not be sent if there are any cells pending in the cell +queue, for doing things like extending cell bursts more accurately and with +less overhead. + +However, even if we solve the queuing issues, Tor's current timers are not as +precise as some padding designs may require. We will still have issues of +timing precision to solve. [Ticket 31653](https://bugs.torproject.org/31653) +describes an issue the circuit padding system has with sending 0-delay padding +cells, and [ticket 32670](https://bugs.torproject.org/32670) describes a +libevent timer accuracy issue, which causes callbacks to vary up to 10ms from +their scheduled time, even in absence of load. + +All of these issues strongly suggest that you either truncate the resolution +of any timers you feed to your classifier, or that you omit timestamps +entirely from the classification problem until these issues are addressed. + +### 7.3. Better Machine Negotiation + +Circuit padding is applied to circuits through machine conditions. + +The following machine conditions may be useful for some use cases, but have +not been implemented yet: + * [Exit Policy-based Stream Conditions](https://bugs.torproject.org/29083) + * [Probability to apply machine/Cointoss condition](https://bugs.torproject.org/30092) + * [Probability distributions for launching new padding circuit(s)](https://bugs.torproject.org/31783) + * [More flexible purpose handling](https://bugs.torproject.org/32040) + +Additionally, the following features may help to obscure that padding is being +negotiated, and/or streamline that negotiation process: + * [Always send negotiation cell on all circuits](https://bugs.torproject.org/30172) + * [Better shutdown handling](https://bugs.torproject.org/30992) + * [Preference-ordered negotiation menu](https://bugs.torproject.org/30348) + +### 7.4. Probabilistic State Transitions + +Right now, the state machine transitions are fully deterministic. However, +one could imagine a state machine that uses probabilistic transitions between +states to simulate a random walk or Hidden Markov Model traversal across +several pages. + +The simplest way to implement this is to make the `circpad_state_t.next_state` array +into an array of structs that have a next state field, and a probability to +transition to that state. + +If you need this feature, please see [ticket +31787](https://bugs.torproject.org/31787) for more details. + +### 7.5. More Complex Pattern Recognition + +State machines are extremely efficient sequence recognition devices. But they +are not great pattern recognition devices. This is one of the reasons why +[Adaptive Padding](https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf) +used state machines in combination with histograms, to model the target +distribution of interpacket delays for transmitted packets. + +However, there currently is no such optimization for reaction to patterns of +*received* traffic. There may also be cases where defenses must react to more +complex patterns of sent traffic than can be expressed by our current +histogram and length count events. + +For example: if you wish your machine to react to a certain count of incoming +cells in a row, right now you have to have a state for each cell, and use the +infinity bin to timeout of the sequence in each state. We could make this more +compact if each state had an arrival cell counter and inter-cell timeout. Or +we could make more complex mechanisms to recognize certain patterns of arrival +traffic in a state. + +The best way to build recognition primitives like this into the framework is +to add additional [Internal Machine Events](#63-internal-machine-events) for +the pattern in question. + +As another simple example, a useful additional event might be to transition +whenever any of your histogram bins are empty, rather than all of them. To do +this, you would add `CIRCPAD_EVENT_ANY_BIN_EMPTY` to the enum +`circpad_event_t` in `circuitpadding.h`. You would then create a function +`circuitpadding_internal_event_any_bin_empty()`, which would work just like +`circuitpadding_internal_event_bin_empty()`, and also be called from +`check_machine_token_supply()` in `circuitpadding.c` but with the check for +each bin being zero instead of the total. With this change, new machines could +react to this new event in the same way as any other. + +If you have any other ideas that may be useful, please comment on [ticket +32680](https://bugs.torproject.org/32680). + + +## 8. Open Research Problems + +### 8.1. Onion Service Circuit Setup + +Our circuit setup padding does not address timing-based features, only +packet counts. Deep learning can probably see this. + +However, before going too deep down the timing rabithole, we may need to make +[some improvements to Tor](#72-timing-and-queuing-optimizations). Please +comment on those tickets if you need this. + +### 8.2. Onion Service Fingerprinting + +We have done nothing to obscure the service side of onion service circuit +setup. Because service-side onion services will have the reverse traffic byte +counts as normal clients, they will likely need some kind of [hybrid +application layer traffic shaping](#53-sketch-of-tamaraw), in addition to +simple circuit setup obfuscation. + +Fingerprinting in +[combination](https://github.com/mikeperry-tor/vanguards/blob/master/README_SECURITY.md) +with +[vanguards](https://github.com/mikeperry-tor/vanguards/blob/master/README_TECHNICAL.md) +ia also an open issue. + +### 8.3. Open World Fingerprinting + +Similarly, Open World/clearweb website fingerprinting defenses remain +an unsolved problem from the practicality point of view. The original WTF-PAD +defense was never tuned, and it is showing accuracy issues against deep +learning attacks. + +### 8.4. Protocol Usage Fingerprinting + +Traffic Fingerprinting to determine the protocol in use by a client has not +been studied, either from the attack or defense point of view. + +### 8.5. Datagram Transport Side Channels + +Padding can reduce the accuracy of dropped-cell side channels in such +transports, but we don't know [how to measure +this](https://lists.torproject.org/pipermail/tor-dev/2018-November/013562.html). + +## 9. Must Read Papers + +These are by far the most important papers in the space, to date: + + - [Tamaraw](https://www.cypherpunks.ca/~iang/pubs/webfingerprint-ccs14.pdf) + - [Bayes, Not Naive](https://www.petsymposium.org/2017/papers/issue4/paper50-2017-4-source.pdf) + - [Anonymity Trilemma](https://eprint.iacr.org/2017/954.pdf) + - [WTF-PAD](http://arxiv.org/pdf/1512.00524) + +Except for WTF-PAD, these papers were selected because they point towards +optimality bounds that can be benchmarked against. + +We cite them even though we are skeptical that provably optimal defenses can +be constructed, at least not without trivial or impractical transforms (such as +those that can be created with unbounded queue capacity, or stored knowledge +of traces for every possible HTTP trace on the Internet). + +We also are not demanding an optimality or security proof for every defense. + +Instead, we cite the above as benchmarks. We believe the space, especially the +open-world case, to be more akin to an optimization problem, where a +WTF-PAD-like defense must be tuned through an optimizer to produce results +comparable to provably optimal but practically unrealizable defenses, through +rigorous adversarial evaluation. + +## A. Acknowledgments + +This research was supported in part by NSF grants CNS-1619454 and CNS-1526306. diff --git a/doc/HACKING/CircuitPaddingQuickStart.md b/doc/HACKING/CircuitPaddingQuickStart.md new file mode 100644 index 0000000000..25bf05048c --- /dev/null +++ b/doc/HACKING/CircuitPaddingQuickStart.md @@ -0,0 +1,266 @@ +# A Padding Machine from Scratch + +A quickstart guide by Tobias Pulls. + +This document describes the process of building a "padding machine" in tor's new +circuit padding framework from scratch. Notes were taken as part of porting +[Adaptive Padding Early +(APE)](https://www.cs.kau.se/pulls/hot/thebasketcase-ape/) from basket2 to the +circuit padding framework. The goal is just to document the process and provide +useful pointers along the way, not create a useful machine. + +The quick and dirty plan is to: +1. clone and compile tor +2. use newly built tor in TB and at small (non-exit) relay we run +3. add a bare-bones APE padding machine +4. run the machine, inspect logs for activity +5. port APE's state machine without thinking much about parameters + +## Clone and compile tor + +```console +$ git clone https://git.torproject.org/tor.git +$ cd tor +$ git checkout tor-0.4.1.5 +``` +Above we use the tag for tor-0.4.1.5 where the circuit padding framework was +released. Note that this version of the framework is missing many features and +fixes that have since been merged to origin/master. If you need the newest +framework features, you should use that master instead. + +```console +$ sh autogen.sh +$ ./configure +$ make +``` +When you run `./configure` you'll be told of missing dependencies and packages +to install on debian-based distributions. Important: if you plan to run `tor` on +a relay as part of the real Tor network and your server runs a distribution that +uses systemd, then I'd recommend that you `apt install dpkg dpkg-dev +libevent-dev libssl-dev asciidoc quilt dh-apparmor libseccomp-dev dh-systemd +libsystemd-dev pkg-config dh-autoreconf libfakeroot zlib1g zlib1g-dev automake +liblzma-dev libzstd-dev` and ensure that tor has systemd support enabled: +`./configure --enable-systemd`. Without this, on a recent Ubuntu, my tor service +was forcefully restarted (SIGINT interrupt) by systemd every five minutes. + +If you want to install on your localsystem, run `make install`. For our case we +just want the tor binary at `src/app/tor`. + +## Use tor in TB and at a relay + +Download and install a fresh Tor Browser (TB) from torproject.org. Make sure it +works. From the command line, relative to the folder created when you extracted +TB, run `./Browser/start-tor-browser --verbose` to get some basic log output. +Note the version of tor, in my case, `Tor 0.4.0.5 (git-bf071e34aa26e096)` as +part of TB 8.5.4. Shut down TB, copy the `tor` binary that you compiled earlier +and replace `Browser/TorBrowser/Tor/tor`. Start TB from the command line again, +you should see a different version, in my case `Tor 0.4.1.5 +(git-439ca48989ece545)`. + +The relay we run is also on linux, and `tor` is located at `/usr/bin/tor`. To +view relevant logs since last boot `sudo journalctl -b /usr/bin/tor`, where we +find `Tor 0.4.0.5 running on Linux`. Copy the locally compiled `tor` to the +relay at a temporary location and then make sure it's ownership and access +rights are identical to `/usr/bin/tor`. Next, shut down the running tor service +with `sudo service tor stop`, wait for it to stop (typically 30s), copy our +locally compiled tor to replace `/usr/bin/tor` then start the service again. +Checking the logs we see `or 0.4.1.5 (git-439ca48989ece545)`. + +Repeatedly shutting down a relay is detrimental to the network and should be +avoided. Sorry about that. + +We have one more step left before we move on the machine: configure TB to always +use our middle relay. Edit `Browser/TorBrowser/Data/Tor/torrc` and set +`MiddleNodes <fingerprint>`, where `<fingerprint>` is the fingerprint of the +relay. Start TB, visit a website, and manually confirm that the middle is used +by looking at the circuit display. + +## Add a bare-bones APE padding machine + +Now the fun part. We have several resources at our disposal (mind that links +might be broken in the future, just search for the headings): +- The official [Circuit Padding Developer + Documentation](https://storm.torproject.org/shared/ChieH_sLU93313A2gopZYT3x2waJ41hz5Hn2uG1Uuh7). +- Notes we made on the [implementation of the circuit padding + framework](https://github.com/pylls/padding-machines-for-tor/blob/master/notes/circuit-padding-framework.md). +- The implementation of the current circuit padding machines in tor: + [circuitpadding.c](https://gitweb.torproject.org/tor.git/tree/src/core/or/circuitpadding_machines.c) + and + [circuitpadding_machines.h](https://gitweb.torproject.org/tor.git/tree/src/core/or/circuitpadding_machines.h). + +Please consult the above links for details. Moving forward, the focus is to +describe what was done, not necessarily explaining all the details why. + +Since we plan to make changes to tor, create a new branch `git checkout -b +circuit-padding-ape-machine tor-0.4.1.5`. + +We start with declaring two functions, one for the machine at the client and one +at the relay, in `circuitpadding_machines.h`: + +```c +void circpad_machine_relay_wf_ape(smartlist_t *machines_sl); +void circpad_machine_client_wf_ape(smartlist_t *machines_sl); +``` + +The definitions go into `circuitpadding_machines.c`: + +```c +/**************** Adaptive Padding Early (APE) machine ****************/ + +/** + * Create a relay-side padding machine based on the APE design. + */ +void +circpad_machine_relay_wf_ape(smartlist_t *machines_sl) +{ + circpad_machine_spec_t *relay_machine + = tor_malloc_zero(sizeof(circpad_machine_spec_t)); + + relay_machine->name = "relay_wf_ape"; + relay_machine->is_origin_side = 0; // relay-side + + // Pad to/from the middle relay, only when the circuit has streams + relay_machine->target_hopnum = 2; + relay_machine->conditions.min_hops = 2; + relay_machine->conditions.state_mask = CIRCPAD_CIRC_STREAMS; + + // limits to help guard against excessive padding + relay_machine->allowed_padding_count = 1; + relay_machine->max_padding_percent = 1; + + // one state to start with: START (-> END, never takes a slot in states) + circpad_machine_states_init(relay_machine, 1); + relay_machine->states[CIRCPAD_STATE_START]. + next_state[CIRCPAD_EVENT_NONPADDING_SENT] = + CIRCPAD_STATE_END; + + // register the machine + relay_machine->machine_num = smartlist_len(machines_sl); + circpad_register_padding_machine(relay_machine, machines_sl); + + log_info(LD_CIRC, + "Registered relay WF APE padding machine (%u)", + relay_machine->machine_num); +} + +/** + * Create a client-side padding machine based on the APE design. + */ +void +circpad_machine_client_wf_ape(smartlist_t *machines_sl) +{ + circpad_machine_spec_t *client_machine + = tor_malloc_zero(sizeof(circpad_machine_spec_t)); + + client_machine->name = "client_wf_ape"; + client_machine->is_origin_side = 1; // client-side + + /** Pad to/from the middle relay, only when the circuit has streams, and only + * for general purpose circuits (typical for web browsing) + */ + client_machine->target_hopnum = 2; + client_machine->conditions.min_hops = 2; + client_machine->conditions.state_mask = CIRCPAD_CIRC_STREAMS; + client_machine->conditions.purpose_mask = + circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_GENERAL); + + // limits to help guard against excessive padding + client_machine->allowed_padding_count = 1; + client_machine->max_padding_percent = 1; + + // one state to start with: START (-> END, never takes a slot in states) + circpad_machine_states_init(client_machine, 1); + client_machine->states[CIRCPAD_STATE_START]. + next_state[CIRCPAD_EVENT_NONPADDING_SENT] = + CIRCPAD_STATE_END; + + client_machine->machine_num = smartlist_len(machines_sl); + circpad_register_padding_machine(client_machine, machines_sl); + log_info(LD_CIRC, + "Registered client WF APE padding machine (%u)", + client_machine->machine_num); +} +``` + +We also have to modify `circpad_machines_init()` in `circuitpadding.c` to +register our machines: + +```c +/* Register machines for the APE WF defense */ +circpad_machine_client_wf_ape(origin_padding_machines); +circpad_machine_relay_wf_ape(relay_padding_machines); +``` + +We run `make` to get a new `tor` binary and copy it to our local TB. + +## Run the machine + +To be able +to view circuit info events in the console as we launch TB, we add `Log +[circ]info notice stdout` to `torrc` of TB. + +Running TB to visit example.com we first find in the log: + +``` +Aug 30 18:36:43.000 [info] circpad_machine_client_hide_intro_circuits(): Registered client intro point hiding padding machine (0) +Aug 30 18:36:43.000 [info] circpad_machine_relay_hide_intro_circuits(): Registered relay intro circuit hiding padding machine (0) +Aug 30 18:36:43.000 [info] circpad_machine_client_hide_rend_circuits(): Registered client rendezvous circuit hiding padding machine (1) +Aug 30 18:36:43.000 [info] circpad_machine_relay_hide_rend_circuits(): Registered relay rendezvous circuit hiding padding machine (1) +Aug 30 18:36:43.000 [info] circpad_machine_client_wf_ape(): Registered client WF APE padding machine (2) +Aug 30 18:36:43.000 [info] circpad_machine_relay_wf_ape(): Registered relay WF APE padding machine (2) +``` + +All good, our machine is running. Looking further we find: + +``` +Aug 30 18:36:55.000 [info] circpad_setup_machine_on_circ(): Registering machine client_wf_ape to origin circ 2 (5) +Aug 30 18:36:55.000 [info] circpad_node_supports_padding(): Checking padding: supported +Aug 30 18:36:55.000 [info] circpad_negotiate_padding(): Negotiating padding on circuit 2 (5), command 2 +Aug 30 18:36:55.000 [info] circpad_machine_spec_transition(): Circuit 2 circpad machine 0 transitioning from 0 to 65535 +Aug 30 18:36:55.000 [info] circpad_machine_spec_transitioned_to_end(): Padding machine in end state on circuit 2 (5) +Aug 30 18:36:55.000 [info] circpad_circuit_machineinfo_free_idx(): Freeing padding info idx 0 on circuit 2 (5) +Aug 30 18:36:55.000 [info] circpad_handle_padding_negotiated(): Middle node did not accept our padding request on circuit 2 (5) +``` +We see that our middle support padding (since we upgraded to tor-0.4.1.5), that +we attempt to negotiate, our machine starts on the client, transitions to the +end state, and is freed. The last line shows that the middle doesn't have a +padding machine that can run. + +Next, we follow the same steps as earlier and replace the modified `tor` at our +middle relay. We don't update the logging there to avoid logging on the info +level on the live network. Looking at the client log again we see that +negotiation works as before except for the last line: it's missing, so the +machine is running at the middle as well. + +## Implementing the APE state machine + +Porting is fairly straightforward: define the states for all machines, add two +more machines (for the receive portion of WTFP-PAD, beyond AP), and pick +reasonable parameters for the distributions (I completely winged it now, as when +implementing APE). The [circuit-padding-ape-machine +branch](https://github.com/pylls/tor/tree/circuit-padding-ape-machine) contains +the commits for the full machines with plenty of comments. + +Some comments on the process: + +- `tor-0.4.1.5` did not support two machines on the same circuit, the following + fix had to be made: https://bugs.torproject.org/tpo/core/tor/31111 . + The good news is that everything else seems to work after the small change in + the fix. +- APE randomizes its distributions. Currently, this can only be done during + start of `tor`. This makes sense in the censorship circumvention setting + (`obfs4`), less so for WF defenses: further randomizing each circuit is likely + a PITA for attackers with few downsides. +- it was annoying to figure out that the lack of systemd support in my compiled + tor caused systemd to interrupt (SIGINT) my tor process at the middle relay + every five minutes. Updated build steps above to hopefully save others the + pain. +- there's for sure some bug on relays when sending padding cells too early (?). + It can happen with some probability with the APE implementation due to + `circpad_machine_relay_wf_ape_send()`. Will investigate next. +- Moving the registration of machines from the definition of the machines to + `circpad_machines_init()` makes sense, as suggested in the circuit padding doc + draft. + +Remember that APE is just a proof-of-concept and we make zero claims about its +ability to withstand WF attacks, in particular those based on deep learning. diff --git a/doc/HACKING/CodeStructure.md b/doc/HACKING/CodeStructure.md deleted file mode 100644 index 736d6cd484..0000000000 --- a/doc/HACKING/CodeStructure.md +++ /dev/null @@ -1,129 +0,0 @@ - -TODO: revise this to talk about how things are, rather than how things -have changed. - -TODO: Make this into good markdown. - - - -For quite a while now, the program "tor" has been built from source -code in just two directories: src/common and src/or. - -This has become more-or-less untenable, for a few reasons -- most -notably of which is that it has led our code to become more -spaghetti-ish than I can endorse with a clean conscience. - -So to fix that, we've gone and done a huge code movement in our git -master branch, which will land in a release once Tor 0.3.5.1-alpha is -out. - -Here's what we did: - - * src/common has been turned into a set of static libraries. These -all live in the "src/lib/*" directories. The dependencies between -these libraries should have no cycles. The libraries are: - - arch -- Headers to handle architectural differences - cc -- headers to handle differences among compilers - compress -- wraps zlib, zstd, lzma - container -- high-level container types - crypt_ops -- Cryptographic operations. Planning to split this into -a higher and lower level library - ctime -- Operations that need to run in constant-time. (Properly, -data-invariant time) - defs -- miscelaneous definitions needed throughout Tor. - encoding -- transforming one data type into another, and various -data types into strings. - err -- lowest-level error handling, in cases where we can't use -the logs because something that the logging system needs has broken. - evloop -- Generic event-loop handling logic - fdio -- Low-level IO wrapper functions for file descriptors. - fs -- Operations on the filesystem - intmath -- low-level integer math and misc bit-twiddling hacks - lock -- low-level locking code - log -- Tor's logging module. This library sits roughly halfway up -the library dependency diagram, since everything it depends on has to -be carefully crafted to *not* log. - malloc -- Low-level wrappers for the platform memory allocation functions. - math -- Higher-level mathematical functions, and floating-point math - memarea -- An arena allocator - meminfo -- Functions for querying the current process's memory -status and resources - net -- Networking compatibility and convenience code - osinfo -- Querying information about the operating system - process -- Launching and querying the status of other processes - sandbox -- Backend for the linux seccomp2 sandbox - smartlist_core -- The lowest-level of the smartlist_t data type. -Separated from the rest of the containers library because the logging -subsystem depends on it. - string -- Compatibility and convenience functions for manipulating -C strings. - term -- Terminal-related functions (currently limited to a getpass -function). - testsupport -- Macros for mocking, unit tests, etc. - thread -- Higher-level thread compatibility code - time -- Higher-level time management code, including format -conversions and monotonic time - tls -- Our wrapper around our TLS library - trace -- Formerly src/trace -- a generic event tracing API - wallclock -- Low-level time code, used by the log module. - - * To ensure that the dependency graph in src/common remains under -control, there is a tool that you can run called "make -check-includes". It verifies that each module in Tor only includes -the headers that it is permitted to include, using a per-directory -".may_include" file. - - * The src/or/or.h header has been split into numerous smaller -headers. Notably, many important structures are now declared in a -header called foo_st.h, where "foo" is the name of the structure. - - * The src/or directory, which had most of Tor's code, had been split -up into several directories. This is still a work in progress: This -code has not itself been refactored, and its dependency graph is still -a tangled web. I hope we'll be working on that over the coming -releases, but it will take a while to do. - - The new top-level source directories are: - - src/core -- Code necessary to actually perform or use onion routing. - src/feature -- Code used only by some onion routing -configurations, or only for a special purpose. - src/app -- Top-level code to run, invoke, and configure the -lower-level code - - The new second-level source directories are: - src/core/crypto -- High-level cryptographic protocols used in Tor - src/core/mainloop -- Tor's event loop, connection-handling, and -traffic-routing code. - src/core/or -- Parts related to handling onion routing itself - src/core/proto -- support for encoding and decoding different -wire protocols - - src/feature/api -- Support for making Tor embeddable - src/feature/client -- Functionality which only Tor clients need - src/feature/control -- Controller implementation - src/feature/dirauth -- Directory authority - src/feature/dircache -- Directory cache - src/feature/dirclient -- Directory client - src/feature/dircommon -- Shared code between the other directory modules - src/feature/hibernate -- Hibernating when Tor is out of bandwidth -or shutting down - src/feature/hs -- v3 onion service implementation - src/feature/hs_common -- shared code between both onion service -implementations - src/feature/nodelist -- storing and accessing the list of relays on -the network. - src/feature/relay -- code that only relay servers and exit servers need. - src/feature/rend -- v2 onion service implementation - src/feature/stats -- statistics and history - - src/app/config -- configuration and state for Tor - src/app/main -- Top-level functions to invoke the rest or Tor. - - * The "tor" executable is now built in src/app/tor rather than src/or/tor. - - * There are more static libraries than before that you need to build -into your application if you want to embed Tor. Rather than -maintaining this list yourself, I recommend that you run "make -show-libs" to have Tor emit a list of what you need to link. diff --git a/doc/HACKING/CodingStandards.md b/doc/HACKING/CodingStandards.md index 4f229348e4..cd3417d0b5 100644 --- a/doc/HACKING/CodingStandards.md +++ b/doc/HACKING/CodingStandards.md @@ -1,5 +1,4 @@ -Coding conventions for Tor -========================== +# Coding conventions for Tor tl;dr: @@ -10,8 +9,7 @@ tl;dr: - Run `make distcheck` if you have made changes to build system components - Add a file in `changes` for your branch. -Patch checklist ---------------- +## Patch checklist If possible, send your patch as one of these (in descending order of preference) @@ -34,7 +32,7 @@ Did you remember... If you are submitting a major patch or new feature, or want to in the future... - - Set up Chutney and Stem, see HACKING/WritingTests.md + - Set up Chutney and Stem, see `doc/HACKING/WritingTests.md` - Run `make test-full` to test against all unit and integration tests. If you have changed build system components: @@ -42,8 +40,7 @@ If you have changed build system components: - For example, if you have changed Makefiles, autoconf files, or anything else that affects the build system. -License issues -============== +## License issues Tor is distributed under the license terms in the LICENSE -- in brief, the "3-clause BSD license". If you send us code to @@ -57,10 +54,7 @@ Some compatible licenses include: - 2-clause BSD - CC0 Public Domain Dedication - - -How we use Git branches -======================= +## How we use Git branches Each main development series (like 0.2.1, 0.2.2, etc) has its main work applied to a single branch. At most one series can be the development series @@ -91,37 +85,80 @@ conflicts in the ChangeLog when it comes time to merge your branch into Tor. Best advice: don't try to keep an independent branch forked for more than 6 months and expect it to merge cleanly. Try to merge pieces early and often. - -How we log changes -================== +## How we log changes When you do a commit that needs a ChangeLog entry, add a new file to the `changes` toplevel subdirectory. It should have the format of a one-entry changelog section from the current ChangeLog file, as in -- Major bugfixes: + o Major bugfixes (security): - Fix a potential buffer overflow. Fixes bug 99999; bugfix on 0.3.1.4-beta. + o Minor features (performance): + - Make tor faster. Closes ticket 88888. To write a changes file, first categorize the change. Some common categories -are: Minor bugfixes, Major bugfixes, Minor features, Major features, Code -simplifications and refactoring. Then say what the change does. If -it's a bugfix, mention what bug it fixes and when the bug was -introduced. To find out which Git tag the change was introduced in, -you can use `git describe --contains <sha1 of commit>`. - -If at all possible, try to create this file in the same commit where you are -making the change. Please give it a distinctive name that no other branch will -use for the lifetime of your change. To verify the format of the changes file, -you can use `make check-changes`. This is run automatically as part of -`make check` -- if it fails, we must fix it before we release. These -checks are implemented in `scripts/maint/lintChanges.py`. +are: + o Minor bugfixes (subheading): + o Major bugfixes (subheading): + o Minor features (subheading): + o Major features (subheading): + o Code simplifications and refactoring: + o Testing: + o Documentation: + +The subheading is a particular area within Tor. See the ChangeLog for +examples. + +Then say what the change does. If it's a bugfix, mention what bug it fixes +and when the bug was introduced. To find out which Git tag the change was +introduced in, you can use `git describe --contains <sha1 of commit>`. +If you don't know the commit, you can search the git diffs (-S) for the first +instance of the feature (--reverse). + +For example, for #30224, we wanted to know when the bridge-distribution-request +feature was introduced into Tor: + +```console +$ git log -S bridge-distribution-request --reverse commit ebab521525 +Author: Roger Dingledine <arma@torproject.org> +Date: Sun Nov 13 02:39:16 2016 -0500 + + Add new BridgeDistribution config option + +$ git describe --contains ebab521525 +tor-0.3.2.3-alpha~15^2~4 +``` + +If you need to know all the Tor versions that contain a commit, use: + +```console +$ git tag --contains 9f2efd02a1 | sort -V +tor-0.2.5.16 +tor-0.2.8.17 +tor-0.2.9.14 +tor-0.2.9.15 +... +tor-0.3.0.13 +tor-0.3.1.9 +tor-0.3.1.10 +... +``` + +If a bug was introduced before the oldest currently supported release series +of Tor, and it's hard to track down where it was introduced, you may say +"bugfix on all supported versions of Tor." + +If at all possible, try to create the changes file in the same commit where +you are making the change. Please give it a distinctive name that no other +branch will use for the lifetime of your change. We usually use "ticketNNNNN" +or "bugNNNNN", where NNNNN is the ticket number. To verify the format of the +changes file, you can use `make check-changes`. This is run automatically as +part of `make check` -- if it fails, we must fix it as soon as possible, so +that our CI passes. These checks are implemented in +`scripts/maint/lintChanges.py`. Changes file style guide: - * Changes files begin with " o Header (subheading):". The header - should usually be "Minor/Major bugfixes/features". The subheading is a - particular area within Tor. See the ChangeLog for examples. - * Make everything terse. * Write from the user's point of view: describe the user-visible changes @@ -152,6 +189,14 @@ What needs a changes file? What does not need a changes file? * Bugfixes for code that hasn't shipped in any released version of Tor + * Any change to a file that is not distributed in the tarball. This + includes: + * Any change to our CI configuration that does not affect the distributed + source. + * Any change to developer-only tools, unless those tools are distributed + in the tarball. + * Non-functional code movement. + * Identifier re-namings, comment edits, spelling fixes, and so on. Why use changes files instead of Git commit messages? @@ -163,11 +208,11 @@ Why use changes files instead of entries in the ChangeLog? * Having every single commit touch the ChangeLog file tended to create zillions of merge conflicts. -Whitespace and C conformance ----------------------------- +## Whitespace and C conformance -Invoke `make check-spaces` from time to time, so it can tell you about -deviations from our C whitespace style. Generally, we use: +Tor's C code is written in accordance with the C99 standard. Invoke `make +check-spaces` from time to time, so it can tell you about deviations from our C +whitespace style. Generally, we use: - Unix-style line endings - K&R-style indentation @@ -183,6 +228,11 @@ deviations from our C whitespace style. Generally, we use: - No space between a function name and an opening paren. `puts(x)`, not `puts (x)`. - Function declarations at the start of the line. + - Use `void foo(void)` to declare a function with no arguments. Saying + `void foo()` is C++ syntax. + - Use `const` for new APIs. + - Variables should be initialized when declared, rather than declared at the + top of a scope. If you use an editor that has plugins for editorconfig.org, the file `.editorconfig` will help you to conform this coding style. @@ -192,30 +242,55 @@ you're using gcc, you should invoke the configure script with the option `--enable-fatal-warnings`. This will tell the compiler to make all warnings into errors. -Functions to use; functions not to use --------------------------------------- +## Functions to use; functions not to use We have some wrapper functions like `tor_malloc`, `tor_free`, `tor_strdup`, and `tor_gettimeofday;` use them instead of their generic equivalents. (They always succeed or exit.) +Specifically, Don't use `malloc`, `realloc`, `calloc`, `free`, or +`strdup`. Use `tor_malloc`, `tor_realloc`, `tor_calloc`, `tor_free`, or +`tor_strdup`. + +Don't use `tor_realloc(x, y\*z)`. Use `tor_reallocarray(x, y, z)` instead.; + You can get a full list of the compatibility functions that Tor provides by looking through `src/lib/*/*.h`. You can see the available containers in `src/lib/containers/*.h`. You should probably familiarize yourself with these modules before you write too much code, or else you'll wind up reinventing the wheel. -We don't use `strcat` or `strcpy` or `sprintf` of any of those notoriously broken -old C functions. Use `strlcat`, `strlcpy`, or `tor_snprintf/tor_asprintf` instead. +We don't use `strcat` or `strcpy` or `sprintf` of any of those notoriously +broken old C functions. We also avoid `strncat` and `strncpy`. Use +`strlcat`, `strlcpy`, or `tor_snprintf/tor_asprintf` instead. We don't call `memcmp()` directly. Use `fast_memeq()`, `fast_memneq()`, -`tor_memeq()`, or `tor_memneq()` for most purposes. +`tor_memeq()`, or `tor_memneq()` for most purposes. If you really need a +tristate return value, use `tor_memcmp()` or `fast_memcmp()`. + +Don't call `assert()` directly. For hard asserts, use `tor_assert()`. For +soft asserts, use `tor_assert_nonfatal()` or `BUG()`. If you need to print +debug information in assert error message, consider using `tor_assertf()` and +`tor_assertf_nonfatal()`. If you are writing code that is too low-level to +use the logging subsystem, use `raw_assert()`. -Also see a longer list of functions to avoid in: -https://people.torproject.org/~nickm/tor-auto/internal/this-not-that.html +Don't use `toupper()` and `tolower()` functions. Use `TOR_TOUPPER` and +`TOR_TOLOWER` macros instead. Similarly, use `TOR_ISALPHA`, `TOR_ISALNUM` et. +al. instead of `isalpha()`, `isalnum()`, etc. -What code can use what other code? ----------------------------------- +When allocating new string to be added to a smartlist, use +`smartlist_add_asprintf()` to do both at once. + +Avoid calling BSD socket functions directly. Use portable wrappers to work +with sockets and socket addresses. Also, sockets should be of type +`tor_socket_t`. + +Don't use any of these functions: they aren't portable. Use the +version prefixed with `tor_` instead: strtok_r, memmem, memstr, +asprintf, localtime_r, gmtime_r, inet_aton, inet_ntop, inet_pton, +getpass, ntohll, htonll. (This list is incomplete.) + +## What code can use what other code? We're trying to simplify Tor's structure over time. In the long run, we want Tor to be structured as a set of modules with *no circular dependencies*. @@ -232,8 +307,7 @@ included except those specifically permitted by the `.may_include` file. When editing one of these files, please make sure that you are not introducing any cycles into Tor's dependency graph. -Floating point math is hard ---------------------------- +## Floating point math is hard Floating point arithmetic as typically implemented by computers is very counterintuitive. Failure to adequately analyze floating point @@ -279,7 +353,7 @@ General advice: For additional useful advice (and a little bit of background), see [What Every Programmer Should Know About Floating-Point -Arithmetic](http://floating-point-gui.de/). +Arithmetic](https://floating-point-gui.de/). A list of notable (and surprising) facts about floating point arithmetic is at [Floating-point @@ -292,8 +366,7 @@ For more detailed (and math-intensive) background, see [What Every Computer Scientist Should Know About Floating-Point Arithmetic](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html). -Other C conventions -------------------- +## Other C conventions The `a ? b : c` trinary operator only goes inside other expressions; don't use it as a replacement for if. (You can ignore this inside macro @@ -302,8 +375,15 @@ definitions when necessary.) Assignment operators shouldn't nest inside other expressions. (You can ignore this inside macro definitions when necessary.) -Functions not to write ----------------------- +## Binary data and wire formats + +Use pointer to `char` when representing NUL-terminated string. To represent +arbitrary binary data, use pointer to `uint8_t`. (Many older Tor APIs ignore +this rule.) + +Refrain from attempting to encode integers by casting their pointers to byte +arrays. Use something like `set_uint32()`/`get_uint32()` instead and don't +forget about endianness. Try to never hand-write new code to parse or generate binary formats. Instead, use trunnel if at all possible. See @@ -314,9 +394,7 @@ for more information about trunnel. For information on adding new trunnel code to Tor, see src/trunnel/README - -Calling and naming conventions ------------------------------- +## Calling and naming conventions Whenever possible, functions should return -1 on error and 0 on success. @@ -339,17 +417,15 @@ probably time to create an enum. If you find that you are passing three or more flags to a function, it's probably time to create a flags argument that takes a bitfield. -What To Optimize ----------------- +## What To Optimize Don't optimize anything if it's not in the critical path. Right now, the critical path seems to be AES, logging, and the network itself. Feel free to do your own profiling to determine otherwise. -Log conventions ---------------- +## Log conventions -`https://www.torproject.org/docs/faq#LogLevel` +[FAQ - Log Levels](https://www.torproject.org/docs/faq#LogLevel) No error or warning messages should be expected during normal OR or OP operation. @@ -363,8 +439,7 @@ end-users that they aren't expected to understand the message (perhaps with a string like "internal error"). Option (A) is to be preferred to option (B). -Assertions In Tor ------------------ +## Assertions In Tor Assertions should be used for bug-detection only. Don't use assertions to detect bad user inputs, network errors, resource exhaustion, or similar @@ -380,11 +455,12 @@ use `tor_assert_nonfatal()` in place of `tor_assert()`. If you'd like to write a conditional that incorporates a nonfatal assertion, use the `BUG()` macro, as in: - if (BUG(ptr == NULL)) - return -1; +```c +if (BUG(ptr == NULL)) + return -1; +``` -Allocator conventions ---------------------- +## Allocator conventions By convention, any tor type with a name like `abc_t` should be allocated by a function named `abc_new()`. This function should never return @@ -394,60 +470,71 @@ Also, a type named `abc_t` should be freed by a function named `abc_free_()`. Don't call this `abc_free_()` function directly -- instead, wrap it in a macro called `abc_free()`, using the `FREE_AND_NULL` macro: - void abc_free_(abc_t *obj); - #define abc_free(obj) FREE_AND_NULL(abc_t, abc_free_, (obj)) +```c +void abc_free_(abc_t *obj); +#define abc_free(obj) FREE_AND_NULL(abc_t, abc_free_, (obj)) +``` This macro will free the underlying `abc_t` object, and will also set the object pointer to NULL. You should define all `abc_free_()` functions to accept NULL inputs: - void - abc_free_(abc_t *obj) - { - if (!obj) - return; - tor_free(obj->name); - thing_free(obj->thing); - tor_free(obj); - } +```c +void +abc_free_(abc_t *obj) +{ + if (!obj) + return; + tor_free(obj->name); + thing_free(obj->thing); + tor_free(obj); +} +``` If you need a free function that takes a `void *` argument (for example, to use it as a function callback), define it with a name like `abc_free_void()`: - static void - abc_free_void_(void *obj) - { - abc_free_(obj); - } +```c +static void +abc_free_void_(void *obj) +{ + abc_free_(obj); +} +``` +When deallocating, don't say e.g. `if (x) tor_free(x)`. The convention is to +have deallocators do nothing when NULL pointer is passed. -Doxygen comment conventions ---------------------------- +## Doxygen comment conventions Say what functions do as a series of one or more imperative sentences, as though you were telling somebody how to be the function. In other words, DO NOT say: - /** The strtol function parses a number. - * - * nptr -- the string to parse. It can include whitespace. - * endptr -- a string pointer to hold the first thing that is not part - * of the number, if present. - * base -- the numeric base. - * returns: the resulting number. - */ - long strtol(const char *nptr, char **nptr, int base); +```c +/** The strtol function parses a number. + * + * nptr -- the string to parse. It can include whitespace. + * endptr -- a string pointer to hold the first thing that is not part + * of the number, if present. + * base -- the numeric base. + * returns: the resulting number. + */ +long strtol(const char *nptr, char **nptr, int base); +``` Instead, please DO say: - /** Parse a number in radix <b>base</b> from the string <b>nptr</b>, - * and return the result. Skip all leading whitespace. If - * <b>endptr</b> is not NULL, set *<b>endptr</b> to the first character - * after the number parsed. - **/ - long strtol(const char *nptr, char **nptr, int base); +```c +/** Parse a number in radix <b>base</b> from the string <b>nptr</b>, + * and return the result. Skip all leading whitespace. If + * <b>endptr</b> is not NULL, set *<b>endptr</b> to the first character + * after the number parsed. + **/ +long strtol(const char *nptr, char **nptr, int base); +``` Doxygen comments are the contract in our abstraction-by-contract world: if the functions that call your function rely on it doing something, then your diff --git a/doc/HACKING/CodingStandardsRust.md b/doc/HACKING/CodingStandardsRust.md index fc562816db..c821465173 100644 --- a/doc/HACKING/CodingStandardsRust.md +++ b/doc/HACKING/CodingStandardsRust.md @@ -1,48 +1,51 @@ +# Rust Coding Standards - Rust Coding Standards -======================= - -You MUST follow the standards laid out in `.../doc/HACKING/CodingStandards.md`, +You MUST follow the standards laid out in `doc/HACKING/CodingStandards.md`, where applicable. - Module/Crate Declarations ---------------------------- +## Module/Crate Declarations Each Tor C module which is being rewritten MUST be in its own crate. -See the structure of `.../src/rust` for examples. +See the structure of `src/rust` for examples. In your crate, you MUST use `lib.rs` ONLY for pulling in external crates (e.g. `extern crate libc;`) and exporting public objects from other Rust modules (e.g. `pub use mymodule::foo;`). For example, if -you create a crate in `.../src/rust/yourcrate`, your Rust code should -live in `.../src/rust/yourcrate/yourcode.rs` and the public interface -to it should be exported in `.../src/rust/yourcrate/lib.rs`. +you create a crate in `src/rust/yourcrate`, your Rust code should +live in `src/rust/yourcrate/yourcode.rs` and the public interface +to it should be exported in `src/rust/yourcrate/lib.rs`. If your code is to be called from Tor C code, you MUST define a safe `ffi.rs`. See the "Safety" section further down for more details. For example, in a hypothetical `tor_addition` Rust module: -In `.../src/rust/tor_addition/addition.rs`: +In `src/rust/tor_addition/addition.rs`: - pub fn get_sum(a: i32, b: i32) -> i32 { - a + b - } +```rust +pub fn get_sum(a: i32, b: i32) -> i32 { + a + b +} +``` -In `.../src/rust/tor_addition/lib.rs`: +In `src/rust/tor_addition/lib.rs`: - pub use addition::*; +```rust +pub use addition::*; +``` -In `.../src/rust/tor_addition/ffi.rs`: +In `src/rust/tor_addition/ffi.rs`: - #[no_mangle] - pub extern "C" fn tor_get_sum(a: c_int, b: c_int) -> c_int { - get_sum(a, b) - } +```rust +#[no_mangle] +pub extern "C" fn tor_get_sum(a: c_int, b: c_int) -> c_int { + get_sum(a, b) +} +``` If your Rust code must call out to parts of Tor's C code, you must declare the functions you are calling in the `external` crate, located -at `.../src/rust/external`. +at `src/rust/external`. <!-- XXX get better examples of how to declare these externs, when/how they --> <!-- XXX are unsafe, what they are expected to do —isis --> @@ -54,8 +57,7 @@ If you have any external modules as dependencies (e.g. `extern crate libc;`), you MUST declare them in your crate's `lib.rs` and NOT in any other module. - Dependencies and versions ---------------------------- +## Dependencies and versions In general, we use modules from only the Rust standard library whenever possible. We will review including external crates on a @@ -81,8 +83,7 @@ Currently, Tor requires that you use the latest stable Rust version. At some point in the future, we will freeze on a given stable Rust version, to ensure backward compatibility with stable distributions that ship it. - Updating/Adding Dependencies ------------------------------- +## Updating/Adding Dependencies To add/remove/update dependencies, first add your dependencies, exactly specifying their versions, into the appropriate *crate-level* @@ -101,14 +102,13 @@ Next, run `/scripts/maint/updateRustDependencies.sh`. Then, go into `src/ext/rust` and commit the changes to the `tor-rust-dependencies` repo. - Documentation ---------------- +## Documentation You MUST include `#![deny(missing_docs)]` in your crate. For function/method comments, you SHOULD include a one-sentence, "first person" description of function behaviour (see requirements for documentation as -described in `.../src/HACKING/CodingStandards.md`), then an `# Inputs` section +described in `src/HACKING/CodingStandards.md`), then an `# Inputs` section for inputs or initialisation values, a `# Returns` section for return values/types, a `# Warning` section containing warnings for unsafe behaviours or panics that could happen. For publicly accessible @@ -118,14 +118,12 @@ types/constants/objects/functions/methods, you SHOULD also include an You MUST document your module with _module docstring_ comments, i.e. `//!` at the beginning of each line. - Style -------- +## Style You SHOULD consider breaking up large literal numbers with `_` when it makes it more human readable to do so, e.g. `let x: u64 = 100_000_000_000`. - Testing ---------- +## Testing All code MUST be unittested and integration tested. @@ -134,22 +132,23 @@ describing how the function/object is expected to be used. Integration tests SHOULD go into a `tests/` directory inside your crate. Unittests SHOULD go into their own module inside the module -they are testing, e.g. in `.../src/rust/tor_addition/addition.rs` you +they are testing, e.g. in `src/rust/tor_addition/addition.rs` you should put: - #[cfg(test)] - mod test { - use super::*; +```rust +#[cfg(test)] +mod test { + use super::*; - #[test] - fn addition_with_zero() { - let sum: i32 = get_sum(5i32, 0i32); - assert_eq!(sum, 5); - } +#[test] + fn addition_with_zero() { + let sum: i32 = get_sum(5i32, 0i32); + assert_eq!(sum, 5); } +} +``` - Benchmarking --------------- +## Benchmarking The external `test` crate can be used for most benchmarking. However, using this crate requires nightly Rust. Since we may want to switch to a more @@ -160,49 +159,52 @@ benchmarks in the following manner. If you wish to benchmark some of your Rust code, you MUST put the following in the `[features]` section of your crate's `Cargo.toml`: - [features] - bench = [] +```toml +[features] +bench = [] +``` Next, in your crate's `lib.rs` you MUST put: - #[cfg(all(test, feature = "bench"))] - extern crate test; +```rust +#[cfg(all(test, feature = "bench"))] +extern crate test; +``` This ensures that the external crate `test`, which contains utilities for basic benchmarks, is only used when running benchmarks via `cargo bench --features bench`. Finally, to write your benchmark code, in -`.../src/rust/tor_addition/addition.rs` you SHOULD put: +`src/rust/tor_addition/addition.rs` you SHOULD put: - #[cfg(all(test, features = "bench"))] - mod bench { - use test::Bencher; - use super::*; +```rust +#[cfg(all(test, features = "bench"))] +mod bench { + use test::Bencher; + use super::*; - #[bench] - fn addition_small_integers(b: &mut Bencher) { - b.iter(| | get_sum(5i32, 0i32)); - } +#[bench] + fn addition_small_integers(b: &mut Bencher) { + b.iter(| | get_sum(5i32, 0i32)); } +} +``` - Fuzzing ---------- +## Fuzzing If you wish to fuzz parts of your code, please see the -[`cargo fuzz`](https://github.com/rust-fuzz/cargo-fuzz) crate, which uses +[cargo fuzz](https://github.com/rust-fuzz/cargo-fuzz) crate, which uses [libfuzzer-sys](https://github.com/rust-fuzz/libfuzzer-sys). - Whitespace & Formatting -------------------------- +## Whitespace & Formatting You MUST run `rustfmt` (https://github.com/rust-lang-nursery/rustfmt) on your code before your code will be merged. You can install rustfmt by doing `cargo install rustfmt-nightly` and then run it with `cargo fmt`. - Safety --------- +## Safety You SHOULD read [the nomicon](https://doc.rust-lang.org/nomicon/) before writing Rust FFI code. It is *highly advised* that you read and write normal Rust code @@ -222,10 +224,10 @@ Here are some additional bits of advice and rules: > > * Data races > * Dereferencing a null/dangling raw pointer - > * Reads of [undef](http://llvm.org/docs/LangRef.html#undefined-values) + > * Reads of [undef](https://llvm.org/docs/LangRef.html#undefined-values) > (uninitialized) memory > * Breaking the - > [pointer aliasing rules](http://llvm.org/docs/LangRef.html#pointer-aliasing-rules) + > [pointer aliasing rules](https://llvm.org/docs/LangRef.html#pointer-aliasing-rules) > with raw pointers (a subset of the rules used by C) > * `&mut T` and `&T` follow LLVM’s scoped noalias model, except if the `&T` > contains an `UnsafeCell<U>`. Unsafe code must not violate these aliasing @@ -256,42 +258,50 @@ Here are some additional bits of advice and rules: or 2) should fail (i.e. in a unittest). You SHOULD NOT use `unwrap()` anywhere in which it is possible to handle the - potential error with either `expect()` or the eel operator, `?`. + potential error with the eel operator, `?` or another non panicking way. For example, consider a function which parses a string into an integer: - fn parse_port_number(config_string: &str) -> u16 { - u16::from_str_radix(config_string, 10).unwrap() - } + ```rust + fn parse_port_number(config_string: &str) -> u16 { + u16::from_str_radix(config_string, 10).unwrap() + } + ``` There are numerous ways this can fail, and the `unwrap()` will cause the - whole program to byte the dust! Instead, either you SHOULD use `expect()` + whole program to byte the dust! Instead, either you SHOULD use `ok()` (or another equivalent function which will return an `Option` or a `Result`) and change the return type to be compatible: - fn parse_port_number(config_string: &str) -> Option<u16> { - u16::from_str_radix(config_string, 10).expect("Couldn't parse port into a u16") - } + ```rust + fn parse_port_number(config_string: &str) -> Option<u16> { + u16::from_str_radix(config_string, 10).ok() + } + ``` or you SHOULD use `or()` (or another similar method): - fn parse_port_number(config_string: &str) -> Option<u16> { - u16::from_str_radix(config_string, 10).or(Err("Couldn't parse port into a u16") - } + ```rust + fn parse_port_number(config_string: &str) -> Option<u16> { + u16::from_str_radix(config_string, 10).or(Err("Couldn't parse port into a u16") + } + ``` Using methods like `or()` can be particularly handy when you must do something afterwards with the data, for example, if we wanted to guarantee that the port is high. Combining these methods with the eel operator (`?`) makes this even easier: - fn parse_port_number(config_string: &str) -> Result<u16, Err> { - let port = u16::from_str_radix(config_string, 10).or(Err("Couldn't parse port into a u16"))?; + ```rust + fn parse_port_number(config_string: &str) -> Result<u16, Err> { + let port = u16::from_str_radix(config_string, 10).or(Err("Couldn't parse port into a u16"))?; - if port > 1024 { - return Ok(port); - } else { - return Err("Low ports not allowed"); - } + if port > 1024 { + return Ok(port); + } else { + return Err("Low ports not allowed"); } + } + ``` 2. `unsafe` @@ -304,25 +314,29 @@ Here are some additional bits of advice and rules: When creating an FFI in Rust for C code to call, it is NOT REQUIRED to declare the entire function `unsafe`. For example, rather than doing: - #[no_mangle] - pub unsafe extern "C" fn increment_and_combine_numbers(mut numbers: [u8; 4]) -> u32 { - for number in &mut numbers { - *number += 1; - } - std::mem::transmute::<[u8; 4], u32>(numbers) + ```rust + #[no_mangle] + pub unsafe extern "C" fn increment_and_combine_numbers(mut numbers: [u8; 4]) -> u32 { + for number in &mut numbers { + *number += 1; } + std::mem::transmute::<[u8; 4], u32>(numbers) + } + ``` You SHOULD instead do: - #[no_mangle] - pub extern "C" fn increment_and_combine_numbers(mut numbers: [u8; 4]) -> u32 { - for index in 0..numbers.len() { - numbers[index] += 1; - } - unsafe { - std::mem::transmute::<[u8; 4], u32>(numbers) - } + ```rust + #[no_mangle] + pub extern "C" fn increment_and_combine_numbers(mut numbers: [u8; 4]) -> u32 { + for index in 0..numbers.len() { + numbers[index] += 1; } + unsafe { + std::mem::transmute::<[u8; 4], u32>(numbers) + } + } + ``` 3. Pass only C-compatible primitive types and bytes over the boundary @@ -397,45 +411,51 @@ Here are some additional bits of advice and rules: rather than using an untyped mapping between strings and integers like so: - use std::collections::HashMap; + ```rust + use std::collections::HashMap; - pub fn get_elements_with_over_9000_points(map: &HashMap<String, usize>) -> Vec<String> { - ... - } + pub fn get_elements_with_over_9000_points(map: &HashMap<String, usize>) -> Vec<String> { + ... + } + ``` It would be safer to define a new type, such that some other usage of `HashMap<String, usize>` cannot be confused for this type: - pub struct DragonBallZPowers(pub HashMap<String, usize>); + ```rust + pub struct DragonBallZPowers(pub HashMap<String, usize>); - impl DragonBallZPowers { - pub fn over_nine_thousand<'a>(&'a self) -> Vec<&'a String> { - let mut powerful_enough: Vec<&'a String> = Vec::with_capacity(5); + impl DragonBallZPowers { + pub fn over_nine_thousand<'a>(&'a self) -> Vec<&'a String> { + let mut powerful_enough: Vec<&'a String> = Vec::with_capacity(5); - for (character, power) in &self.0 { - if *power > 9000 { - powerful_enough.push(character); - } - } - powerful_enough - } - } + for (character, power) in &self.0 { + if *power > 9000 { + powerful_enough.push(character); + } + } + powerful_enough + } + } + ``` Note the following code, which uses Rust's type aliasing, is valid but it does NOT meet the desired type safety goals: - pub type Power = usize; + ```rust + pub type Power = usize; - pub fn over_nine_thousand(power: &Power) -> bool { - if *power > 9000 { - return true; - } - false + pub fn over_nine_thousand(power: &Power) -> bool { + if *power > 9000 { + return true; } + false + } - // We can still do the following: - let his_power: usize = 9001; - over_nine_thousand(&his_power); + // We can still do the following: + let his_power: usize = 9001; + over_nine_thousand(&his_power); + ``` 7. Unsafe mucking around with lifetimes @@ -443,15 +463,17 @@ Here are some additional bits of advice and rules: family of types, individual lifetimes can be treated as types. For example, one can arbitrarily extend and shorten lifetime using `std::mem::transmute`: - struct R<'a>(&'a i32); + ```rust + struct R<'a>(&'a i32); - unsafe fn extend_lifetime<'b>(r: R<'b>) -> R<'static> { - std::mem::transmute::<R<'b>, R<'static>>(r) - } + unsafe fn extend_lifetime<'b>(r: R<'b>) -> R<'static> { + std::mem::transmute::<R<'b>, R<'static>>(r) + } - unsafe fn shorten_invariant_lifetime<'b, 'c>(r: &'b mut R<'static>) -> &'b mut R<'c> { - std::mem::transmute::<&'b mut R<'static>, &'b mut R<'c>>(r) - } + unsafe fn shorten_invariant_lifetime<'b, 'c>(r: &'b mut R<'static>) -> &'b mut R<'c> { + std::mem::transmute::<&'b mut R<'static>, &'b mut R<'c>>(r) + } + ``` Calling `extend_lifetime()` would cause an `R` passed into it to live forever for the life of the program (the `'static` lifetime). Similarly, @@ -472,12 +494,14 @@ Here are some additional bits of advice and rules: For example, `std::mem::transmute` can be abused in ways where casting with `as` would be both simpler and safer: - // Don't do this - let ptr = &0; - let ptr_num_transmute = unsafe { std::mem::transmute::<&i32, usize>(ptr)}; + ```rust + // Don't do this + let ptr = &0; + let ptr_num_transmute = unsafe { std::mem::transmute::<&i32, usize>(ptr)}; - // Use an `as` cast instead - let ptr_num_cast = ptr as *const i32 as usize; + // Use an `as` cast instead + let ptr_num_cast = ptr as *const i32 as usize; + ``` In fact, using `std::mem::transmute` for *any* reason is a code smell and as such SHOULD be avoided. @@ -487,8 +511,10 @@ Here are some additional bits of advice and rules: This is generally fine to do, but it has some behaviours which you should be aware of. Casting down chops off the high bits, e.g.: - let x: u32 = 4294967295; - println!("{}", x as u16); // prints 65535 + ```rust + let x: u32 = 4294967295; + println!("{}", x as u16); // prints 65535 + ``` Some cases which you MUST NOT do include: @@ -499,24 +525,28 @@ Here are some additional bits of advice and rules: * Casting between integers and floats when the thing being cast cannot fit into the type it is being casted into, e.g.: - println!("{}", 42949.0f32 as u8); // prints 197 in debug mode and 0 in release - println!("{}", 1.04E+17 as u8); // prints 0 in both modes - println!("{}", (0.0/0.0) as i64); // prints whatever the heck LLVM wants + ```rust + println!("{}", 42949.0f32 as u8); // prints 197 in debug mode and 0 in release + println!("{}", 1.04E+17 as u8); // prints 0 in both modes + println!("{}", (0.0/0.0) as i64); // prints whatever the heck LLVM wants + ``` Because this behaviour is undefined, it can even produce segfaults in safe Rust code. For example, the following program built in release mode segfaults: - #[inline(never)] - pub fn trigger_ub(sl: &[u8; 666]) -> &[u8] { - // Note that the float is out of the range of `usize`, invoking UB when casting. - let idx = 1e99999f64 as usize; - &sl[idx..] // The bound check is elided due to `idx` being of an undefined value. - } - - fn main() { - println!("{}", trigger_ub(&[1; 666])[999999]); // ~ out of bound - } + ```rust + #[inline(never)] + pub fn trigger_ub(sl: &[u8; 666]) -> &[u8] { + // Note that the float is out of the range of `usize`, invoking UB when casting. + let idx = 1e99999f64 as usize; + &sl[idx..] // The bound check is elided due to `idx` being of an undefined value. + } + + fn main() { + println!("{}", trigger_ub(&[1; 666])[999999]); // ~ out of bound + } + ``` And in debug mode panics with: diff --git a/doc/HACKING/Fuzzing.md b/doc/HACKING/Fuzzing.md index 2039d6a4c0..1a9185aebf 100644 --- a/doc/HACKING/Fuzzing.md +++ b/doc/HACKING/Fuzzing.md @@ -1,18 +1,20 @@ -= Fuzzing Tor +# Fuzzing Tor -== The simple version (no fuzzing, only tests) +## The simple version (no fuzzing, only tests) Check out fuzzing-corpora, and set TOR_FUZZ_CORPORA to point to the place where you checked it out. To run the fuzzing test cases in a deterministic fashion, use: - make test-fuzz-corpora + +```console +$ make test-fuzz-corpora +``` This won't actually fuzz Tor! It will just run all the fuzz binaries on our existing set of testcases for the fuzzer. - -== Different kinds of fuzzing +## Different kinds of fuzzing Right now we support three different kinds of fuzzer. @@ -26,7 +28,7 @@ have a reasonably recent clang and libfuzzer installed. At that point, you just build with --enable-expensive-hardening and --enable-libfuzzer. That will produce a set of binaries in src/test/fuzz/lf-fuzz-* . These programs take as input a series of directories full of fuzzing examples. For more -information on libfuzzer, see http://llvm.org/docs/LibFuzzer.html +information on libfuzzer, see https://llvm.org/docs/LibFuzzer.html Third, there's Google's OSS-Fuzz infrastructure, which expects to get all of its. For more on this, see https://github.com/google/oss-fuzz and the @@ -37,7 +39,7 @@ In all cases, you'll need some starting examples to give the fuzzer when it starts out. There's a set in the "fuzzing-corpora" git repository. Try setting TOR_FUZZ_CORPORA to point to a checkout of that repository -== Writing Tor fuzzers +## Writing Tor fuzzers A tor fuzzing harness should have: * a fuzz_init() function to set up any necessary global state. @@ -51,8 +53,7 @@ But the fuzzing harness should crash if tor fails an assertion, triggers a bug, or accesses memory it shouldn't. This helps fuzzing frameworks detect "interesting" cases. - -== Guided Fuzzing with AFL +## Guided Fuzzing with AFL There is no HTTPS, hash, or signature for American Fuzzy Lop's source code, so its integrity can't be verified. That said, you really shouldn't fuzz on a @@ -60,11 +61,13 @@ machine you care about, anyway. To Build: Get AFL from http://lcamtuf.coredump.cx/afl/ and unpack it - cd afl - make - cd ../tor - PATH=$PATH:../afl/ CC="../afl/afl-gcc" ./configure --enable-expensive-hardening - AFL_HARDEN=1 make clean fuzzers + ```console + $ cd afl + $ make + $ cd ../tor + $ PATH=$PATH:../afl/ CC="../afl/afl-gcc" ./configure --enable-expensive-hardening + $ AFL_HARDEN=1 make clean fuzzers + ``` To Find The ASAN Memory Limit: (64-bit only) @@ -74,13 +77,15 @@ and then not actually use it. Read afl/docs/notes_for_asan.txt for more details. - Download recidivm from http://jwilk.net/software/recidivm + Download recidivm from https://jwilk.net/software/recidivm Download the signature Check the signature - tar xvzf recidivm*.tar.gz - cd recidivm* - make - /path/to/recidivm -v src/test/fuzz/fuzz-http + ```console + $ tar xvzf recidivm*.tar.gz + $ cd recidivm* + $ make + $ /path/to/recidivm -v src/test/fuzz/fuzz-http + ``` Use the final "ok" figure as the input to -m when calling afl-fuzz (Normally, recidivm would output a figure automatically, but in some cases, the fuzzing harness will hang when the memory limit is too small.) @@ -90,9 +95,11 @@ don't care about memory limits. To Run: - mkdir -p src/test/fuzz/fuzz_http_findings - ../afl/afl-fuzz -i ${TOR_FUZZ_CORPORA}/http -o src/test/fuzz/fuzz_http_findings -m <asan-memory-limit> -- src/test/fuzz/fuzz-http +```console +$ mkdir -p src/test/fuzz/fuzz_http_findings +$ ../afl/afl-fuzz -i ${TOR_FUZZ_CORPORA}/http -o src/test/fuzz/fuzz_http_findings -m <asan-memory-limit> -- src/test/fuzz/fuzz-http +``` AFL has a multi-core mode, check the documentation for details. You might find the included fuzz-multi.sh script useful for this. @@ -101,7 +108,7 @@ macOS (OS X) requires slightly more preparation, including: * using afl-clang (or afl-clang-fast from the llvm directory) * disabling external crash reporting (AFL will guide you through this step) -== Triaging Issues +## Triaging Issues Crashes are usually interesting, particularly if using AFL_HARDEN=1 and --enable-expensive-hardening. Sometimes crashes are due to bugs in the harness code. @@ -111,13 +118,16 @@ valid inputs may take a second or so, particularly with the fuzzer and sanitizers enabled. To see what fuzz-http is doing with a test case, call it like this: - src/test/fuzz/fuzz-http --debug < /path/to/test.case + +```console +$ src/test/fuzz/fuzz-http --debug < /path/to/test.case +``` (Logging is disabled while fuzzing to increase fuzzing speed.) -== Reporting Issues +## Reporting Issues Please report any issues discovered using the process in Tor's security issue policy: -https://trac.torproject.org/projects/tor/wiki/org/meetings/2016SummerDevMeeting/Notes/SecurityIssuePolicy +https://gitlab.torproject.org/tpo/core/team/-/wikis/NetworkTeam/SecurityPolicy diff --git a/doc/HACKING/GettingStarted.md b/doc/HACKING/GettingStarted.md index 0c42404634..6d61be9881 100644 --- a/doc/HACKING/GettingStarted.md +++ b/doc/HACKING/GettingStarted.md @@ -1,23 +1,19 @@ - -Getting started in Tor development -================================== +# Getting started in Tor development Congratulations! You've found this file, and you're reading it! This means that you might be interested in getting started in developing Tor. -(This guide is just about Tor itself--the small network program at the +(_This guide is just about Tor itself--the small network program at the heart of the Tor network--and not about all the other programs in the -whole Tor ecosystem.) - +whole Tor ecosystem._) If you are looking for a more bare-bones, less user-friendly information -dump of important information, you might like reading the "torguts" -documents linked to below. You should probably read it before you write +dump of important information, you might like reading the +[doxygen output](https://src-ref.docs.torproject.org/tor/index.html). +You probably should skim some of the topic headings there before you write your first patch. - -Required background -------------------- +## Required background First, I'm going to assume that you can build Tor from source, and that you know enough of the C language to read and write it. (See the README @@ -26,43 +22,43 @@ and any high-quality guide to C for information on programming.) I'm also going to assume that you know a little bit about how to use Git, or that you're able to follow one of the several excellent guides -at http://git-scm.org to learn. +at [git-scm](https://git-scm.org) to learn. -Most Tor developers develop using some Unix-based system, such as Linux, -BSD, or OSX. It's okay to develop on Windows if you want, but you're +Most Tor developers develop using some Unix-based system, such as GNU/Linux, +BSD, or macOS. It's okay to develop on Windows if you want, but you're going to have a more difficult time. - -Getting your first patch into Tor ---------------------------------- +## Getting your first patch into Tor Once you've reached this point, here's what you need to know. 1. Get the source. We keep our source under version control in Git. To get the latest - version, run + version, run: - git clone https://git.torproject.org/git/tor + ```console + $ git clone https://git.torproject.org/git/tor + ``` This will give you a checkout of the master branch. If you're going to fix a bug that appears in a stable version, check out the appropriate "maint" branch, as in: - git checkout maint-0.2.7 - - 2. Find your way around the source + ```console + $ git checkout maint-0.4.3 + ``` - Our overall code structure is explained in the "torguts" documents, - currently at + 2. Find your way around the source. - git clone https://git.torproject.org/user/nickm/torguts.git + Our overall code structure is explained in our + [source documentation](https://src-ref.docs.torproject.org/tor/index.html). Find a part of the code that looks interesting to you, and start looking around it to see how it fits together! We do some unusual things in our codebase. Our testing-related - practices and kludges are explained in doc/WritingTests.txt. + practices and kludges are explained in `doc/HACKING/WritingTests.md`. If you see something that doesn't make sense, we love to get questions! @@ -74,11 +70,12 @@ Once you've reached this point, here's what you need to know. Many people have gotten started by looking for an area where they personally felt Tor was underperforming, and investigating ways to - fix it. If you're looking for ideas, you can head to our bug - tracker at trac.torproject.org and look for tickets that have - received the "easy" tag: these are ones that developers think would - be pretty simple for a new person to work on. For a bigger - challenge, you might want to look for tickets with the "lorax" + fix it. If you're looking for ideas, you can head to + [gitlab](https://gitlab.torproject.org) our bug tracking tool and look for + tickets that have received the "First Contribution" label: these are ones + that developers + think would be pretty simple for a new person to work on. For a bigger + challenge, you might want to look for tickets with the "Project Ideas" keyword: these are tickets that the developers think might be a good idea to build, but which we have no time to work on any time soon. @@ -96,7 +93,7 @@ Once you've reached this point, here's what you need to know. 4. Meet the developers! - We discuss stuff on the tor-dev mailing list and on the #tor-dev + We discuss stuff on the tor-dev mailing list and on the `#tor-dev` IRC channel on OFTC. We're generally friendly and approachable, and we like to talk about how Tor fits together. If we have ideas about how something should be implemented, we'll be happy to share @@ -113,8 +110,8 @@ Once you've reached this point, here's what you need to know. protocols, there needs to be a written design proposal before it can be merged. (We use this process to manage changes in the protocols.) To write one, see the instructions at - https://gitweb.torproject.org/torspec.git/tree/proposals/001-process.txt - . If you'd like help writing a proposal, just ask! We're happy to + [the Tor proposal process](https://gitweb.torproject.org/torspec.git/plain/proposals/001-process.txt). + If you'd like help writing a proposal, just ask! We're happy to help out with good ideas. You might also like to look around the rest of that directory, to @@ -125,7 +122,7 @@ Once you've reached this point, here's what you need to know. As you write your code, you'll probably want it to fit in with the standards of the rest of the Tor codebase so it will be easy for us to review and merge. You can learn our coding standards in - doc/HACKING. + `doc/HACKING` directory. If your patch is large and/or is divided into multiple logical components, remember to divide it into a series of Git commits. A @@ -137,17 +134,17 @@ Once you've reached this point, here's what you need to know. ensure that it runs correctly. Also, all code should actually be _run_ by somebody, to make sure it works. - See doc/WritingTests.txt for more information on how we test things + See `doc/HACKING/WritingTests.md` for more information on how we test things in Tor. If you'd like any help writing tests, just ask! We're glad to help out. 8. Submitting your patch We review patches through tickets on our bugtracker at - trac.torproject.org. You can either upload your patches there, or + [gitlab](https://gitlab.torproject.org). You can either upload your patches there, or put them at a public git repository somewhere we can fetch them - (like github or bitbucket) and then paste a link on the appropriate - trac ticket. + (like gitlab, github or bitbucket) and then paste a link on the appropriate + ticket. Once your patches are available, write a short explanation of what you've done on trac, and then change the status of the ticket to @@ -163,17 +160,17 @@ Once you've reached this point, here's what you need to know. When your patch is reviewed, one of these things will happen: - * The reviewer will say "looks good to me" and your + * The reviewer will say "_looks good to me_" and your patch will get merged right into Tor. [Assuming we're not in the middle of a code-freeze window. If the codebase is frozen, your patch will go into the next release series.] - * OR the reviewer will say "looks good, just needs some small - changes!" And then the reviewer will make those changes, + * OR the reviewer will say "_looks good, just needs some small + changes!_" And then the reviewer will make those changes, and merge the modified patch into Tor. - * OR the reviewer will say "Here are some questions and - comments," followed by a bunch of stuff that the reviewer + * OR the reviewer will say "_Here are some questions and + comments,_" followed by a bunch of stuff that the reviewer thinks should change in your code, or questions that the reviewer has. diff --git a/doc/HACKING/GettingStartedRust.md b/doc/HACKING/GettingStartedRust.md index aa29c097da..beef825226 100644 --- a/doc/HACKING/GettingStartedRust.md +++ b/doc/HACKING/GettingStartedRust.md @@ -1,12 +1,9 @@ +# Hacking on Rust in Tor - Hacking on Rust in Tor -======================== - - Getting Started ------------------ +## Getting Started Please read or review our documentation on Rust coding standards -(`.../doc/HACKING/CodingStandardsRust.md`) before doing anything. +(`doc/HACKING/CodingStandardsRust.md`) before doing anything. Please also read [the Rust Code of Conduct](https://www.rust-lang.org/en-US/conduct.html). We @@ -23,8 +20,7 @@ Please be patient with the other people who are working on getting more Rust code into Tor, because they are graciously donating their free time to contribute to this effort. - Resources for learning Rust ------------------------------ +## Resources for learning Rust **Beginning resources** @@ -47,10 +43,9 @@ is [The Little Book of Rust Macros](https://danielkeep.github.io/tlborm/book/index.html). For learning more about FFI and Rust, see Jake Goulding's -[Rust FFI Omnibus](http://jakegoulding.com/rust-ffi-omnibus/). +[Rust FFI Omnibus](https://jakegoulding.com/rust-ffi-omnibus/). - Compiling Tor with Rust enabled ---------------------------------- +## Compiling Tor with Rust enabled You will need to run the `configure` script with the `--enable-rust` flag to explicitly build with Rust. Additionally, you will need to @@ -59,7 +54,9 @@ fetching dependencies from Cargo or specifying a local directory. **Fetch dependencies from Cargo** - ./configure --enable-rust --enable-cargo-online-mode +```console +$ ./configure --enable-rust --enable-cargo-online-mode +``` **Using a local dependency cache** @@ -71,25 +68,29 @@ We vendor our Rust dependencies in a separate repo using [cargo-vendor](https://github.com/alexcrichton/cargo-vendor). To use them, do: - git submodule init - git submodule update +```console +$ git submodule init +$ git submodule update +``` To specify the local directory containing the dependencies, (assuming you are in the top level of the repository) configure tor with: - TOR_RUST_DEPENDENCIES='path_to_dependencies_directory' ./configure --enable-rust +```console +$ TOR_RUST_DEPENDENCIES='path_to_dependencies_directory' ./configure --enable-rust +``` -(Note that TOR_RUST_DEPENDENCIES must be the full path to the directory; it +(Note that `TOR_RUST_DEPENDENCIES` must be the full path to the directory; it cannot be relative.) Assuming you used the above `git submodule` commands and you're in the topmost directory of the repository, this would be: - TOR_RUST_DEPENDENCIES=`pwd`/src/ext/rust/crates ./configure --enable-rust - +```console +$ TOR_RUST_DEPENDENCIES=`pwd`/src/ext/rust/crates ./configure --enable-rust +``` - Identifying which modules to rewrite -====================================== +## Identifying which modules to rewrite The places in the Tor codebase that are good candidates for porting to Rust are: @@ -109,20 +110,21 @@ areas of responsibility. A good first step is to build a module-level callgraph to understand how interconnected your target module is. - git clone https://git.torproject.org/user/nickm/calltool.git - cd tor - CFLAGS=0 ./configure - ../calltool/src/main.py module_callgraph +```console +$ git clone https://git.torproject.org/user/nickm/calltool.git +$ cd tor +$ CFLAGS=0 ./configure +$ ../calltool/src/main.py module_callgraph +``` The output will tell you each module name, along with a set of every module that the module calls. Modules which call fewer other modules are better targets. - Writing your Rust module -========================== +## Writing your Rust module Strive to change the C API as little as possible. -We are currently targetting Rust stable. (See CodingStandardsRust.md for more +We are currently targeting Rust stable. (See `CodingStandardsRust.md` for more details.) It is on our TODO list to try to cultivate good @@ -134,19 +136,17 @@ If parts of your Rust code needs to stay in sync with C code (such as handling enums across the FFI boundary), annonotate these places in a comment structured as follows: - /// C_RUST_COUPLED: <path_to_file> `<name_of_c_object>` + `/// C_RUST_COUPLED: <path_to_file> <name_of_c_object>` -Where <name_of_c_object> can be an enum, struct, constant, etc. Then, +Where `<name_of_c_object>` can be an enum, struct, constant, etc. Then, do the same in the C code, to note that rust will need to be changed when the C does. - - Adding your Rust module to Tor's build system ------------------------------------------------ +## Adding your Rust module to Tor's build system 0. Your translation of the C module should live in its own crate(s) - in the `.../tor/src/rust/` directory. -1. Add your crate to `.../tor/src/rust/Cargo.toml`, in the + in the `src/rust/` directory. +1. Add your crate to `src/rust/Cargo.toml`, in the `[workspace.members]` section. 2. Add your crate's files to src/rust/include.am @@ -156,28 +156,32 @@ dependency of other Rust modules): `src/rust/tor_util/Cargo.toml` and include it in `src/rust/tor_rust/lib.rs` - How to test your Rust code ----------------------------- +## How to test your Rust code Everything should be tested full stop. Even non-public functionality. -Be sure to edit `.../tor/src/test/test_rust.sh` to add the name of your +Be sure to edit `src/test/test_rust.sh` to add the name of your crate to the `crates` variable! This will ensure that `cargo test` is run on your crate. Configure Tor's build system to build with Rust enabled: - ./configure --enable-fatal-warnings --enable-rust --enable-cargo-online-mode +```console +$ ./configure --enable-fatal-warnings --enable-rust --enable-cargo-online-mode +``` Tor's test should be run by doing: - make check +```console +$ make check +``` Tor's integration tests should also pass: - make test-stem +```console +$ make test-stem +``` - Submitting a patch -===================== +## Submitting a patch -Please follow the instructions in `.../doc/HACKING/GettingStarted.md`. +Please follow the instructions in `doc/HACKING/GettingStarted.md`. diff --git a/doc/HACKING/HelpfulTools.md b/doc/HACKING/HelpfulTools.md index d499238526..0ce59576f0 100644 --- a/doc/HACKING/HelpfulTools.md +++ b/doc/HACKING/HelpfulTools.md @@ -1,11 +1,10 @@ -Useful tools -============ +# Useful tools These aren't strictly necessary for hacking on Tor, but they can help track down bugs. -Travis/Appveyor CI ------------------- +## Travis/Appveyor CI + It's CI. Looks like this: @@ -29,8 +28,7 @@ for your fork to build commits outside of PRs too: Builds should show up on the web at travis-ci.com and on IRC at #tor-ci on OFTC. If they don't, ask #tor-dev (also on OFTC). -Jenkins -------- +## Jenkins It's CI/builders. Looks like this: https://jenkins.torproject.org @@ -43,25 +41,24 @@ Builds Linux and Windows cross-compilation. Runs Linux tests. Builds should show up on the web at jenkins.torproject.org and on IRC at #tor-bots on OFTC. If they don't, ask #tor-dev (also on OFTC). -Valgrind --------- +## Valgrind - valgrind --leak-check=yes --error-limit=no --show-reachable=yes src/app/tor +```console +$ valgrind --leak-check=yes --error-limit=no --show-reachable=yes src/app/tor +``` (Note that if you get a zillion openssl warnings, you will also need to pass `--undef-value-errors=no` to valgrind, or rebuild your openssl with `-DPURIFY`.) -Coverity --------- +## Coverity Nick regularly runs the coverity static analyzer on the Tor codebase. The preprocessor define `__COVERITY__` is used to work around instances where coverity picks up behavior that we wish to permit. -clang Static Analyzer ---------------------- +## clang Static Analyzer The clang static analyzer can be run on the Tor codebase using Xcode (WIP) or a command-line build. @@ -69,8 +66,7 @@ or a command-line build. The preprocessor define `__clang_analyzer__` is used to work around instances where clang picks up behavior that we wish to permit. -clang Runtime Sanitizers ------------------------- +## clang Runtime Sanitizers To build the Tor codebase with the clang Address and Undefined Behavior sanitizers, see the file `contrib/clang/sanitize_blacklist.txt`. @@ -78,16 +74,17 @@ sanitizers, see the file `contrib/clang/sanitize_blacklist.txt`. Preprocessor workarounds for instances where clang picks up behavior that we wish to permit are also documented in the blacklist file. -Running lcov for unit test coverage ------------------------------------ +## Running lcov for unit test coverage Lcov is a utility that generates pretty HTML reports of test code coverage. To generate such a report: - ./configure --enable-coverage - make - make coverage-html - $BROWSER ./coverage_html/index.html +```console +$ ./configure --enable-coverage +$ make +$ make coverage-html +$ $BROWSER ./coverage_html/index.html +``` This will run the tor unit test suite `./src/test/test` and generate the HTML coverage code report under the directory `./coverage_html/`. To change the @@ -96,42 +93,52 @@ output directory, use `make coverage-html HTML_COVER_DIR=./funky_new_cov_dir`. Coverage diffs using lcov are not currently implemented, but are being investigated (as of July 2014). -Running the unit tests ----------------------- +## Running the unit tests To quickly run all the tests distributed with Tor: - make check +```console +$ make check +``` To run the fast unit tests only: - make test +```console +$ make test +``` To selectively run just some tests (the following can be combined arbitrarily): - ./src/test/test <name_of_test> [<name of test 2>] ... - ./src/test/test <prefix_of_name_of_test>.. [<prefix_of_name_of_test2>..] ... - ./src/test/test :<name_of_excluded_test> [:<name_of_excluded_test2]... +```console +$ ./src/test/test <name_of_test> [<name of test 2>] ... +$ ./src/test/test <prefix_of_name_of_test>.. [<prefix_of_name_of_test2>..] ... +$ ./src/test/test :<name_of_excluded_test> [:<name_of_excluded_test2]... +``` To run all tests, including those based on Stem or Chutney: - make test-full +```console +$ make test-full +``` To run all tests, including those based on Stem or Chutney that require a working connection to the internet: - make test-full-online +```console +$ make test-full-online +``` -Running gcov for unit test coverage ------------------------------------ +## Running gcov for unit test coverage - ./configure --enable-coverage - make - make check - # or--- make test-full ? make test-full-online? - mkdir coverage-output - ./scripts/test/coverage coverage-output +```console +$ ./configure --enable-coverage +$ make +$ make check +$ # or--- make test-full ? make test-full-online? +$ mkdir coverage-output +$ ./scripts/test/coverage coverage-output +``` (On OSX, you'll need to start with `--enable-coverage CC=clang`.) @@ -154,7 +161,9 @@ you can run `make reset-gcov` to clear the intermediary gcov output. If you have two different `coverage-output` directories, and you want to see a meaningful diff between them, you can run: - ./scripts/test/cov-diff coverage-output1 coverage-output2 | less +```console +$ ./scripts/test/cov-diff coverage-output1 coverage-output2 | less +``` In this diff, any lines that were visited at least once will have coverage "1", and line numbers are deleted. This lets you inspect what you (probably) really @@ -164,8 +173,7 @@ lines? If you run ./scripts/test/cov-exclude, it marks excluded unreached lines with 'x', and excluded reached lines with '!!!'. -Running integration tests -------------------------- +## Running integration tests We have the beginnings of a set of scripts to run integration tests using Chutney. To try them, set CHUTNEY_PATH to your chutney source directory, and @@ -174,14 +182,12 @@ run `make test-network`. We also have scripts to run integration tests using Stem. To try them, set `STEM_SOURCE_DIR` to your Stem source directory, and run `test-stem`. -Profiling Tor -------------- +## Profiling Tor Ongoing notes about Tor profiling can be found at https://pad.riseup.net/p/profiling-tor -Profiling Tor with oprofile ---------------------------- +## Profiling Tor with oprofile The oprofile tool runs (on Linux only!) to tell you what functions Tor is spending its CPU time in, so we can identify performance bottlenecks. @@ -206,8 +212,7 @@ Here are some basic instructions * `opreport -l that_dir/*` - Profit -Profiling Tor with perf ------------------------ +## Profiling Tor with perf This works with a running Tor, and requires root. @@ -236,8 +241,7 @@ This works with a running Tor, and requires root. report -g > <FILENAME>.out`. Then you can compress that and put it somewhere public. -Profiling Tor with gperftools aka Google-performance-tools ----------------------------------------------------------- +## Profiling Tor with gperftools aka Google-performance-tools This should work on nearly any unixy system. It doesn't seem to be compatible with RunAsDaemon though. @@ -251,23 +255,21 @@ Now you can run Tor with profiling enabled, and use the pprof utility to look at performance! See the gperftools manual for more info, but basically: 2. Run `env CPUPROFILE=/tmp/profile src/app/tor -f <path/torrc>`. The profile file - is not written to until Tor finishes execuction. + is not written to until Tor finishes execution. -3. Run `pprof src/app/tor /tm/profile` to start the REPL. +3. Run `pprof src/app/tor /tmp/profile` to start the REPL. -Generating and analyzing a callgraph ------------------------------------- +## Generating and analyzing a callgraph 0. Build Tor on linux or mac, ideally with -O0 or -fno-inline. -1. Clone 'https://gitweb.torproject.org/user/nickm/calltool.git/' . +1. Clone 'https://git.torproject.org/user/nickm/calltool.git/' . Follow the README in that repository. Note that currently the callgraph generator can't detect calls that pass through function pointers. -Getting emacs to edit Tor source properly ------------------------------------------ +## Getting emacs to edit Tor source properly Nick likes to put the following snippet in his .emacs file: @@ -315,59 +317,107 @@ If you use emacs for editing Tor and nothing else, you could always just say: There is probably a better way to do this. No, we are probably not going to clutter the files with emacs stuff. +## Building a tag file (code index) + +Many functions in tor use `MOCK_IMPL` wrappers for unit tests. Your +tag-building program must be told how to handle this syntax. + +If you're using emacs, you can generate an emacs-compatible tag file using +`make tags`. This will run your system's `etags`. Tor's build system assumes +that you're using the emacs-specific version of `etags` (bundled under the +`xemacs21-bin` package on Debian). This is incompatible with other versions of +`etags` such as the version provided by Exuberant Ctags. + +If you're using vim or emacs, you can also use Universal Ctags to build a tag +file using the syntax: + +```console +$ ctags -R -D 'MOCK_IMPL(r,h,a)=r h a' . +``` + +If you're using an older version of Universal Ctags, you can use the following +instead: -Doxygen -------- +```console +ctags -R --mline-regex-c='/MOCK_IMPL\([^,]+,\W*([a-zA-Z0-9_]+)\W*,/\1/f/{mgroup=1}' . +``` + +A vim-compatible tag file will be generated by default. If you use emacs, add +the `-e` flag to generate an emacs-compatible tag file. + +## Doxygen We use the 'doxygen' utility to generate documentation from our source code. Here's how to use it: 1. Begin every file that should be documented with - /** - * \file filename.c - * \brief Short description of the file. - */ +``` + /** + * \file filename.c + * \brief Short description of the file. + */ +``` - (Doxygen will recognize any comment beginning with /** as special.) + (Doxygen will recognize any comment beginning with /** as special.) 2. Before any function, structure, #define, or variable you want to document, add a comment of the form: - /** Describe the function's actions in imperative sentences. - * - * Use blank lines for paragraph breaks - * - and - * - hyphens - * - for - * - lists. - * - * Write <b>argument_names</b> in boldface. - * - * \code - * place_example_code(); - * between_code_and_endcode_commands(); - * \endcode - */ +``` +/** Describe the function's actions in imperative sentences. + * + * Use blank lines for paragraph breaks + * - and + * - hyphens + * - for + * - lists. + * + * Write <b>argument_names</b> in boldface. + * + * \code + * place_example_code(); + * between_code_and_endcode_commands(); + * \endcode + */ +``` 3. Make sure to escape the characters `<`, `>`, `\`, `%` and `#` as `\<`, `\>`, `\\`, `\%` and `\#`. 4. To document structure members, you can use two forms: - struct foo { - /** You can put the comment before an element; */ - int a; - int b; /**< Or use the less-than symbol to put the comment - * after the element. */ - }; +```c +struct foo { + /** You can put the comment before an element; */ + int a; + int b; /**< Or use the less-than symbol to put the comment + * after the element. */ +}; +``` 5. To generate documentation from the Tor source code, type: - $ doxygen -g +```console +$ doxygen -g +``` - to generate a file called `Doxyfile`. Edit that file and run - `doxygen` to generate the API documentation. + to generate a file called `Doxyfile`. Edit that file and run + `doxygen` to generate the API documentation. 6. See the Doxygen manual for more information; this summary just scratches the surface. + +## Style and best-practices checking + +We use scripts to check for various problems in the formatting and style +of our source code. The "check-spaces" test detects a bunch of violations +of our coding style on the local level. The "check-best-practices" test +looks for violations of some of our complexity guidelines. + +You can tell the tool about exceptions to the complexity guidelines via its +exceptions file (scripts/maint/practracker/exceptions.txt). But before you +do this, consider whether you shouldn't fix the underlying problem. Maybe +that file really _is_ too big. Maybe that function really _is_ doing too +much. (On the other hand, for stable release series, it is sometimes better +to leave things unrefactored.) diff --git a/doc/HACKING/HowToReview.md b/doc/HACKING/HowToReview.md index 2d1f3d1c9e..7815e76632 100644 --- a/doc/HACKING/HowToReview.md +++ b/doc/HACKING/HowToReview.md @@ -1,5 +1,4 @@ -How to review a patch -===================== +# How to review a patch Some folks have said that they'd like to review patches more often, but they don't know how. @@ -9,9 +8,7 @@ So, here are a bunch of things to check for when reviewing a patch! Note that if you can't do every one of these, that doesn't mean you can't do a good review! Just make it clear what you checked for and what you didn't. - -Top-level smell-checks ----------------------- +## Top-level smell-checks (Difficulty: easy) @@ -37,10 +34,9 @@ Top-level smell-checks - If this changes anything in the code, is there a "changes" file? -Let's look at the code! ------------------------ +## Let's look at the code! -- Does the code conform to CodingStandards.txt? +- Does the code conform to `CodingStandards.md`? - Does the code leak memory? @@ -60,18 +56,16 @@ Let's look at the code! - Is there duplicated code that could be turned into a function? -Let's look at the documentation! --------------------------------- +## Let's look at the documentation! -- Does the documentation confirm to CodingStandards.txt? +- Does the documentation conform to CodingStandards.txt? - Does it make sense? - Can you predict what the function will do from its documentation? -Let's think about security! ---------------------------- +## Let's think about security! - If there are any arrays, buffers, are you 100% sure that they cannot overflow? diff --git a/doc/HACKING/Maintaining.md b/doc/HACKING/Maintaining.md new file mode 100644 index 0000000000..4d5a7f6b76 --- /dev/null +++ b/doc/HACKING/Maintaining.md @@ -0,0 +1,113 @@ +# Maintaining Tor + +This document details the duties and processes on maintaining the Tor code +base. + +The first section describes who is the current Tor maintainer and what are the +responsibilities. Tor has one main single maintainer but does have many +committers and subsystem maintainers. + +The second third section describes how the **alpha and master** branches are +maintained and by whom. + +Finally, the last section describes how the **stable** branches are maintained +and by whom. + +This document does not cover how Tor is released, please see +[ReleasingTor.md](ReleasingTor.md) for that information. + +## Tor Maintainer + +The current maintainer is Nick Mathewson <nickm@torproject.org>. + +The maintainer takes final decisions in terms of engineering, architecture and +protocol design. Releasing Tor falls under their responsibility. + +## Alpha and Master Branches + +The Tor repository always has at all times a **master** branch which contains +the upstream ongoing development. + +It may also contain a branch for a released feature freezed version which is +called the **alpha** branch. The git tag and version number is always +postfixed with `-alpha[-dev]`. For example: `tor-0.3.5.0-alpha-dev` or +`tor-0.3.5.3-alpha`. + +Tor is separated into subsystems and some of those are maintained by other +developers than the main maintainer. Those people have commit access to the +code base but only commit (in most cases) into the subsystem they maintain. + +Upstream merges are restricted to the alpha and master branches. Subsystem +maintainers should never push a patch into a stable branch which is the +responsibility of the [stable branch maintainer](#stable-branches). + +### Who + +In alphabetical order, the following people have upstream commit access and +maintain the following subsystems: + +- David Goulet <dgoulet@torproject.org> + * Onion Service (including Shared Random). + ***keywords:*** *[tor-hs]* + * Channels, Circuitmux, Connection, Scheduler. + ***keywords:*** *[tor-chan, tor-cmux, tor-sched, tor-conn]* + * Cell Logic (Handling/Parsing). + ***keywords:*** *[tor-cell]* + * Threading backend. + ***keywords:*** *[tor-thread]* + +- George Kadianakis <asn@torproject.org> + * Onion Service (including Shared Random). + ***keywords:*** *[tor-hs]* + * Guard. + ***keywords:*** *[tor-guard]* + * Pluggable Transport (excluding Bridge networking). + ***keywords:*** *[tor-pt]* + +### Tasks + +These are the tasks of a subsystem maintainer: + +1. Regularly go over `merge_ready` tickets relevant to the related subsystem + and for the current alpha or development (master branch) Milestone. + +2. A subsystem maintainer is expected to contribute to any design changes + (including proposals) or large patch set about the subsystem. + +3. Leave their ego at the door. Mistakes will be made but they have to be + taking care of seriously. Learn and move on quickly. + +### Merging Policy + +These are few important items to follow when merging code upstream: + +1. To merge code upstream, the patch must have passed our CI (currently + github.com/torproject), have a corresponding ticket and reviewed by + **at least** one person that is not the original coder. + + Example A: If Alice writes a patch then Bob, a Tor network team member, + reviews it and flags it `merge_ready`. Then, the maintainer is required + to look at the patch and makes a decision. + + Example B: If the maintainer writes a patch then Bob, a Tor network + team member, reviews it and flags it `merge_ready`, then the maintainer + can merge the code upstream. + +2. Maintainer makes sure the commit message should describe what was fixed + and, if it applies, how was it fixed. It should also always refer to + the ticket number. + +3. Trivial patches such as comment change, documentation, syntax issues or + typos can be merged without a ticket or reviewers. + +4. Tor uses the "merge forward" method, that is, if a patch applies to the + alpha branch, it has to be merged there first and then merged forward + into master. + +5. Maintainer should always consult with the network team about any doubts, + mis-understandings or unknowns of a patch. Final word will always go to the + main Tor maintainer. + +## Stable Branches + +(Currently being drafted and reviewed by the network team.) diff --git a/doc/HACKING/Module.md b/doc/HACKING/Module.md index 9cf36090b4..b9d3a654eb 100644 --- a/doc/HACKING/Module.md +++ b/doc/HACKING/Module.md @@ -1,22 +1,33 @@ -# Modules in Tor # +# Modules in Tor This document describes the build system and coding standards when writing a module in Tor. -## What is a module? ## +## What is a module? In the context of the tor code base, a module is a subsystem that we can selectively enable or disable, at `configure` time. -Currently, there is only one module: +Currently, tor has these modules: + - Relay subsystem (relay) + - Directory cache system (dircache). - Directory Authority subsystem (dirauth) -It is located in its own directory in `src/feature/dirauth/`. To disable it, -one need to pass `--disable-module-dirauth` at configure time. All modules -are currently enabled by default. +The dirauth code is located in its own directory in `src/feature/dirauth/`. -## Build System ## +The relay code is located in a directory named `src/*/*relay`, which is +being progressively refactored and disabled. + +The dircache code is located in `src/*/*dircache`. Right now, it is +disabled if and only if the relay module is disabled. (We are treating +them as separate modules because they are logically independent, not +because you would actually want to run one without the other.) + +To disable a module, pass `--disable-module-{dirauth,relay}` at configure +time. All modules are currently enabled by default. + +## Build System The changes to the build system are pretty straightforward. @@ -24,7 +35,7 @@ The changes to the build system are pretty straightforward. contains a list (white-space separated) of the module in tor. Add yours to the list. -2. Use the `AC_ARG_ENABLE([module-dirauth]` template for your new module. We +2. Use the `AC_ARG_ENABLE([module-relay]` template for your new module. We use the "disable module" approach instead of enabling them one by one. So, by default, tor will build all the modules. @@ -32,7 +43,7 @@ The changes to the build system are pretty straightforward. the C code to conditionally compile things for your module. And the `BUILD_MODULE_<name>` is also defined for automake files (e.g: include.am). -3. In the `src/core/include.am` file, locate the `MODULE_DIRAUTH_SOURCES` +3. In the `src/core/include.am` file, locate the `MODULE_RELAY_SOURCES` value. You need to create your own `_SOURCES` variable for your module and then conditionally add the it to `LIBTOR_A_SOURCES` if you should build the module. @@ -40,18 +51,14 @@ The changes to the build system are pretty straightforward. It is then **very** important to add your SOURCES variable to `src_or_libtor_testing_a_SOURCES` so the tests can build it. -4. Do the same for header files, locate `ORHEADERS +=` which always add all - headers of all modules so the symbol can be found for the module entry - points. - Finally, your module will automatically be included in the -`TOR_MODULES_ALL_ENABLED` variable which is used to build the unit tests. They -always build everything in order to tests everything. +`TOR_MODULES_ALL_ENABLED` variable which is used to build the unit tests. +They always build everything in order to test everything. -## Coding ## +## Coding -As mentioned above, a module must be isolated in its own directory (name of -the module) in `src/feature/`. +As mentioned above, a module should be isolated in its own directories, +suffixed with the name of the module, in `src/*/`. There are couples of "rules" you want to follow: @@ -63,7 +70,7 @@ There are couples of "rules" you want to follow: base. Every entry point should have a second definition if the module is disabled. For instance: - ``` + ```c #ifdef HAVE_MODULE_DIRAUTH int sr_init(int save_to_disk); @@ -102,7 +109,9 @@ There are couples of "rules" you want to follow: * When you include headers from the module, **always** use the full module path in your statement. Example: - `#include "feature/dirauth/dirvote.h"` +```c +#include "feature/dirauth/dirvote.h"` +``` The main reason is that we do **not** add the module include path by default so it needs to be specified. But also, it helps our human brain understand diff --git a/doc/HACKING/README.1st.md b/doc/HACKING/README.1st.md index 8299fe634a..4bc3298c67 100644 --- a/doc/HACKING/README.1st.md +++ b/doc/HACKING/README.1st.md @@ -1,17 +1,18 @@ +# README.1st -In this directory ------------------ +## In this directory This directory has helpful information about what you need to know to hack on Tor! -First, read `GettingStarted.md` to learn how to get a start in Tor -development. +First, read `GettingStarted.md` and `GettingStartedRust.md` +to learn how to get a start in Tor development. -If you've decided to write a patch, `CodingStandards.txt` will give -you a bunch of information about how we structure our code. +If you've decided to write a patch, `CodingStandards.md` and +`CodingStandardsRust.md` will give you a bunch of information +about how we structure our code. -It's important to get code right! Reading `WritingTests.md` will +It's important to get the code right! Reading `WritingTests.md` will tell you how to write and run tests in the Tor codebase. There are a bunch of other programs we use to help maintain and @@ -21,42 +22,28 @@ with Tor. If it's your job to put out Tor releases, see `ReleasingTor.md` so that you don't miss any steps! - ------------------------ +## Additional Information For full information on how Tor is supposed to work, look at the files in -`https://gitweb.torproject.org/torspec.git/tree`. +[Tor specification](https://gitweb.torproject.org/torspec.git/tree). For an explanation of how to change Tor's design to work differently, look at -`https://gitweb.torproject.org/torspec.git/blob_plain/HEAD:/proposals/001-process.txt`. +[the Tor proposal process](https://gitweb.torproject.org/torspec.git/plain/proposals/001-process.txt). For the latest version of the code, get a copy of git, and - git clone https://git.torproject.org/git/tor +```console +$ git clone https://git.torproject.org/git/tor +``` + +## Stay in touch We talk about Tor on the `tor-talk` mailing list. Design proposals and discussion belong on the `tor-dev` mailing list. We hang around on -irc.oftc.net, with general discussion happening on #tor and development +irc.oftc.net, with general discussion happening on `#tor` and development happening on `#tor-dev`. The other files in this `HACKING` directory may also be useful as you get started working with Tor. Happy hacking! - - ------------------------ - -XXXXX also describe - -doc/HACKING/WritingTests.md - -torguts.git - -torspec.git - -The design paper - -freehaven.net/anonbib - -XXXX describe these and add links. diff --git a/doc/HACKING/ReleaseSeriesLifecycle.md b/doc/HACKING/ReleaseSeriesLifecycle.md new file mode 100644 index 0000000000..8536fbbd08 --- /dev/null +++ b/doc/HACKING/ReleaseSeriesLifecycle.md @@ -0,0 +1,113 @@ +# Release Series Lifecycle + + +## End Of Life On An Old Release Series + +Here are the steps that the maintainer should take when an old Tor release +series reaches End of Life. + +Note that they are _only_ for an entire series that has reached its planned +EOL: they do not apply to security-related deprecations of individual +patch versions. + + +### 1. Preliminaries + +1. A few months before End of Life: + Write a deprecation announcement. + Send the announcement out with every new release announcement. + +2. A month before End of Life: + Send the announcement to tor-announce, tor-talk, tor-relays, and the + packagers. + + +### 2. On The Day + +1. Open tickets to remove the release from: + - the jenkins builds + - tor's Travis CI cron jobs + - chutney's Travis CI tests + - sbws' Travis CI tests + - stem's Travis CI tests (but see + https://github.com/torproject/stem/issues/51) + - tor's scripts/git/gist-list-tor-branches.sh script + +2. Close the milestone in Trac. To do this, go to Trac, log in, + select "Admin" near the top of the screen, then select "Milestones" from + the menu on the left. Click on the milestone for this version, and + select the "Completed" checkbox. By convention, we select the date as + the End of Life date. + +3. Replace NNN-backport with NNN-unreached-backport in all open trac tickets. + +4. If there are any remaining tickets in the milestone: + - merge_ready tickets are for backports: + - if there are no supported releases for the backport, close the ticket + - if there is an earlier (LTS) release for the backport, move the ticket + to that release + - other tickets should be closed (if we won't fix them) or moved to a + supported release (if we will fix them) + +5. Mail the end of life announcement to tor-announce, the packagers list, + and tor-relays. The current list of packagers is in ReleasingTor.md. + +6. Ask at least two of weasel/arma/Sebastian to remove the old version + number from their approved versions list. + +7. Update the CoreTorReleases wiki page. + +8. Open a ticket (if there is not one already) for authorities to + start rejecting relays that are running that release series. + This ticket should be targeted for at least a month or two + after the series is officially EOL, unless there is an important + reason to un-list relays early. + +9. (LTS end-of-life only) Open a ticket (if appropriate) for updates to the + set of required and recommended subprotocol versions. (For the process + here, see proposal 303.) + +10. (LTS end-of-life only) Open a ticket to remove no-longer-needed + consensus methods. (For the process here, see proposal 290.) + +11. (All EOL) Open a ticket to grep for obsolete series names (e.g., "0.2.9" + and "029") in tor, chutney, sbws, fallback-scripts, and so on. These + should be updated or removed. + +12. Finally, make sure this document is up to date with our latest + process. + +## Starting A New Release Series + +Here are the steps that the maintainer should take to start new maint and +release branches for a stable release. + +Note that they are _only_ for an entire series, when it first becomes stable: +they do not apply to security-related patch release versions. + +(Ideally, do this immediately after a release.) + +1. Start a new maint-x.y.z branch based on master, and a new + release-x.y.z branch based on master. They should have the same + starting point. + + Push both of these branches to the master git repository. + +2. In master, change the version to "0.x.y.0-alpha-dev". Run the + update_versions.py script, and commit this version bump. + +3. Tag the version bump with "tor-0.x.y.0-alpha-dev". Push the tag + and master. + +4. Open tickets for connecting the new branches to various other + places. See section 2 above for a list of affected locations. + +5. Stop running practracker on maintenance and release branches: + * Remove "check-best-practices" from the check-local Makefile + target in the maint-x.y.z branch only. + * Delete the file scripts/maint/practracker/.enable_practracker_in_hooks + in the maint-x.y.z branch only. + * Merge to release-x.y.z, but do not forward-port to master. + +6. Finally, make sure this document is up to date with our latest + process. diff --git a/doc/HACKING/ReleasingTor.md b/doc/HACKING/ReleasingTor.md index 55a40fc89b..24b66a069a 100644 --- a/doc/HACKING/ReleasingTor.md +++ b/doc/HACKING/ReleasingTor.md @@ -1,53 +1,54 @@ - -Putting out a new release -------------------------- +# Putting out a new release Here are the steps that the maintainer should take when putting out a new Tor release: -=== 0. Preliminaries +## 0. Preliminaries 1. Get at least two of weasel/arma/Sebastian to put the new version number in their approved versions list. Give them a few days to do this if you can. -2. If this is going to be an important security release, give the packagers - some advance warning: See this list of packagers in IV.3 below. +2. If this is going to be an important security release, give these packagers + some advance warning: + + - {weasel,sysrqb,mikeperry} at torproject dot org + - {blueness} at gentoo dot org + - {paul} at invizbox dot io + - {vincent} at invizbox dot com + - {lfleischer} at archlinux dot org + - {Nathan} at freitas dot net + - {mike} at tig dot as + - {tails-rm} at boum dot org + - {simon} at sdeziel.info + - {yuri} at freebsd.org + - {mh+tor} at scrit.ch 3. Given the release date for Tor, ask the TB team about the likely release date of a TB that contains it. See note below in "commit, upload, announce". -=== I. Make sure it works - -1. Use it for a while, as a client, as a relay, as a hidden service, - and as a directory authority. See if it has any obvious bugs, and - resolve those. - - As applicable, merge the `maint-X` branch into the `release-X` branch. - But you've been doing that all along, right? - -2. Are all of the jenkins builders happy? See jenkins.torproject.org. +## I. Make sure it works - What about the bsd buildbots? - See http://buildbot.pixelminers.net/builders/ +1. Make sure that CI passes: have a look at Travis + (https://travis-ci.org/torproject/tor/branches), Appveyor + (https://ci.appveyor.com/project/torproject/tor/history), and + Jenkins (https://jenkins.torproject.org/view/tor/). + Make sure you're looking at the right branches. - What about Coverity Scan? + If there are any unexplained failures, try to fix them or figure them + out. - What about clang scan-build? +2. Verify that there are no big outstanding issues. You might find such + issues -- - Does 'make distcheck' complain? + * On Trac - How about 'make test-stem' and 'make test-network' and - `make test-network-full`? + * On coverity scan - - Are all those tests still happy with --enable-expensive-hardening ? - - Any memory leaks? - - -=== II. Write a changelog + * On OSS-Fuzz +## II. Write a changelog 1a. (Alpha release variant) @@ -55,11 +56,15 @@ new Tor release: of them and reordering to focus on what users and funders would find interesting and understandable. - To do this, first run `./scripts/maint/lintChanges.py changes/*` and - fix as many warnings as you can. Then run `./scripts/maint/sortChanges.py - changes/* > changelog.in` to combine headings and sort the entries. - After that, it's time to hand-edit and fix the issues that lintChanges - can't find: + To do this, run `./scripts/maint/sortChanges.py changes/* > changelog.in` + to combine headings and sort the entries. Copy the changelog.in file into + the ChangeLog. Run `format_changelog.py --inplace` (see below) to clean up + the line breaks. + + Remove the `changes/*` files that you just merged into the ChangeLog. + + After that, it's time to hand-edit and fix the issues that + lintChanges can't find: 1. Within each section, sort by "version it's a bugfix on", else by numerical ticket order. @@ -68,8 +73,6 @@ new Tor release: Make stuff very terse - Make sure each section name ends with a colon - Describe the user-visible problem right away Mention relevant config options by name. If they're rare or unusual, @@ -79,7 +82,9 @@ new Tor release: Present and imperative tense: not past. - 'Relays', not 'servers' or 'nodes' or 'Tor relays'. + "Relays", not "servers" or "nodes" or "Tor relays". + + "Onion services", not "hidden services". "Stop FOOing", not "Fix a bug where we would FOO". @@ -100,12 +105,14 @@ new Tor release: For stable releases that backport things from later, we try to compose their releases, we try to make sure that we keep the changelog entries - identical to their original versions, with a 'backport from 0.x.y.z' + identical to their original versions, with a "backport from 0.x.y.z" note added to each section. So in this case, once you have the items from the changes files copied together, don't use them to build a new changelog: instead, look up the corrected versions that were merged into ChangeLog in the master branch, and use those. + Add "backport from X.Y.Z" in the section header for these entries. + 2. Compose a short release blurb to highlight the user-facing changes. Insert said release blurb into the ChangeLog stanza. If it's a stable release, add it to the ReleaseNotes file too. If we're adding @@ -127,96 +134,100 @@ new Tor release: to start sorting and condensing entries. (Generally, we don't edit the text of existing entries, though.) - -=== III. Making the source release. +## III. Making the source release. 1. In `maint-0.?.x`, bump the version number in `configure.ac` and run - `perl scripts/maint/updateVersions.pl` to update version numbers in other + `make update-versions` to update version numbers in other places, and commit. Then merge `maint-0.?.x` into `release-0.?.x`. - (NOTE: To bump the version number, edit `configure.ac`, and then run - either `make`, or `perl scripts/maint/updateVersions.pl`, depending on - your version.) - When you merge the maint branch forward to the next maint branch, or into - master, merge it with "-s ours" to avoid a needless version bump. + master, merge it with "-s ours" to avoid conflict with the version + bump. 2. Make distcheck, put the tarball up in somewhere (how about your - homedir on your homedir on people.torproject.org?) , and tell `#tor` - about it. Wait a while to see if anybody has problems building it. - (Though jenkins is usually pretty good about catching these things.) + homedir on people.torproject.org?) , and tell `#tor-dev` + about it. -=== IV. Commit, upload, announce + If you want, wait until at least one person has built it + successfully. (We used to say "wait for others to test it", but our + CI has successfully caught these kinds of errors for the last several + years.) + +3. Make sure that the new version is recommended in the latest consensus. + (Otherwise, users will get confused when it complains to them + about its status.) + + If it is not, you'll need to poke Roger, Weasel, and Sebastian again: see + item 0.1 at the start of this document. + +## IV. Commit, upload, announce 1. Sign the tarball, then sign and push the git tag: - gpg -ba <the_tarball> - git tag -u <keyid> tor-0.3.x.y-status - git push origin tag tor-0.3.x.y-status +```console +$ gpg -ba <the_tarball> +$ git tag -s tor-0.4.x.y-<status> +$ git push origin tag tor-0.4.x.y-<status> +``` - (You must do this before you update the website: it relies on finding - the version by tag.) + (You must do this before you update the website: the website scripts + rely on finding the version by tag.) + + (If your default PGP key is not the one you want to sign with, then say + "-u <keyid>" instead of "-s".) 2. scp the tarball and its sig to the dist website, i.e. - `/srv/dist-master.torproject.org/htdocs/` on dist-master. When you want - it to go live, you run "static-update-component dist.torproject.org" - on dist-master. + `/srv/dist-master.torproject.org/htdocs/` on dist-master. Run + "static-update-component dist.torproject.org" on dist-master. - In the webwml.git repository, `include/versions.wmi` and `Makefile` - to note the new version. + In the project/web/tpo.git repository, update `databags/versions.ini` + to note the new version. Push these changes to master. (NOTE: Due to #17805, there can only be one stable version listed at once. Nonetheless, do not call your version "alpha" if it is stable, or people will get confused.) -3. Email the packagers (cc'ing tor-team) that a new tarball is up. - The current list of packagers is: + (NOTE: It will take a while for the website update scripts to update + the website.) - - {weasel,gk,mikeperry} at torproject dot org - - {blueness} at gentoo dot org - - {paul} at invizbox dot io - - {vincent} at invizbox dot com - - {lfleischer} at archlinux dot org - - {Nathan} at freitas dot net - - {mike} at tig dot as - - {tails-rm} at boum dot org - - {simon} at sdeziel.info - - {yuri} at freebsd.org - - {mh+tor} at scrit.ch +3. Email the tor-packagers@lists.torproject.org mailing list to tell them + about the new release. Also, email tor-packagers@lists.torproject.org. -4. Add the version number to Trac. To do this, go to Trac, log in, - select "Admin" near the top of the screen, then select "Versions" from - the menu on the left. At the right, there will be an "Add version" - box. By convention, we enter the version in the form "Tor: - 0.2.2.23-alpha" (or whatever the version is), and we select the date as - the date in the ChangeLog. + Mention where to download the tarball (https://dist.torproject.org). + + Include a link to the changelog. -5. Double-check: did the version get recommended in the consensus yet? Is - the website updated? If not, don't announce until they have the - up-to-date versions, or people will get confused. +4. Wait for the download page to be updated. (If you don't do this before you + announce, people will be confused.) -6. Mail the release blurb and ChangeLog to tor-talk (development release) or +5. Mail the release blurb and ChangeLog to tor-talk (development release) or tor-announce (stable). Post the changelog on the blog as well. You can generate a - blog-formatted version of the changelog with the -B option to - format-changelog. + blog-formatted version of the changelog with + `./scripts/maint/format_changelog.py -B` When you post, include an estimate of when the next TorBrowser releases will come out that include this Tor release. This will usually track https://wiki.mozilla.org/RapidRelease/Calendar , but it can vary. + For templates to use when announcing, see: + https://gitlab.torproject.org/tpo/core/team/-/wikis/NetworkTeam/AnnouncementTemplates -=== V. Aftermath and cleanup +## V. Aftermath and cleanup 1. If it's a stable release, bump the version number in the - `maint-x.y.z` branch to "newversion-dev", and do a `merge -s ours` - merge to avoid taking that change into master. + `maint-x.y.z` branch to "newversion-dev", and do a `merge -s ours` + merge to avoid taking that change into master. -2. Forward-port the ChangeLog (and ReleaseNotes if appropriate). +2. If there is a new `maint-x.y.z` branch, create a Travis CI cron job that + builds the release every week. (It's ok to skip the weekly build if the + branch was updated in the last 24 hours.) -3. Keep an eye on the blog post, to moderate comments and answer questions. +3. Forward-port the ChangeLog (and ReleaseNotes if appropriate) to the + master branch. +4. Keep an eye on the blog post, to moderate comments and answer questions. diff --git a/doc/HACKING/Tracing.md b/doc/HACKING/Tracing.md deleted file mode 100644 index 24fa761310..0000000000 --- a/doc/HACKING/Tracing.md +++ /dev/null @@ -1,91 +0,0 @@ -# Tracing # - -This document describes how the event tracing subsystem works in tor so -developers can add events to the code base but also hook them to an event -tracing framework. - -## Basics ### - -Event tracing is separated in two concepts, trace events and a tracer. The -tracing subsystem can be found in `src/trace`. The `events.h` header file is -the main file that maps the different tracers to trace events. - -### Events ### - -A trace event is basically a function from which we can pass any data that -we want to collect. In addition, we specify a context for the event such as -a subsystem and an event name. - -A trace event in tor has the following standard format: - - tor_trace(subsystem, event\_name, args...) - -The `subsystem` parameter is the name of the subsytem the trace event is in. -For example that could be "scheduler" or "vote" or "hs". The idea is to add -some context to the event so when we collect them we know where it's coming -from. The `event_name` is the name of the event which helps a lot with -adding some semantic to the event. Finally, `args` is any number of -arguments we want to collect. - -Here is an example of a possible tracepoint in main(): - - tor_trace(main, init_phase, argc) - -The above is a tracepoint in the `main` subsystem with `init_phase` as the -event name and the `int argc` is passed to the event as well. - -How `argc` is collected or used has nothing to do with the instrumentation -(adding trace events to the code). It is the work of the tracer so this is why -the trace events and collection framework (tracer) are decoupled. You _can_ -have trace events without a tracer. - -### Tracer ### - -In `src/trace/events.h`, we map the `tor_trace()` function to the right -tracer. A tracer support is only enabled at compile time. For instance, the -file `src/trace/debug.h` contains the mapping of the generic tracing function -`tor_trace()` to the `log_debug()` function. More specialized function can be -mapped depending on the tracepoint. - -## Build System ## - -This section describes how it is integrated into the build system of tor. - -By default, every tracing events are disabled in tor that is `tor_trace()` -is a NOP. - -To enable a tracer, there is a configure option on the form of: - - --enable-tracing-<tracer> - -We have an option that will send every trace events to a `log_debug()` (as -mentionned above) which will print you the subsystem and name of the event but -not the arguments for technical reasons. This is useful if you want to quickly -see if your trace event is being hit or well written. To do so, use this -configure option: - - --enable-tracing-debug - -## Instrument Tor ## - -This is pretty easy. Let's say you want to add a trace event in -`src/feature/rend/rendcache.c`, you only have to add this include statement: - - #include "trace/events.h" - -Once done, you can add as many as you want `tor_trace()` that you need. -Please use the right subsystem (here it would be `hs`) and a unique name that -tells what the event is for. For example: - - tor_trace(hs, store_desc_as_client, desc, desc_id); - -If you look in `src/trace/events.h`, you'll see that if tracing is enabled it -will be mapped to a function called: - - tor_trace_hs_store_desc_as_client(desc, desc_id) - -And the point of all this is for that function to be defined in a new file -that you might want to add named `src/trace/hs.{c|h}` which would defined how -to collect the data for the `tor_trace_hs_store_desc_as_client()` function -like for instance sending it to a `log_debug()` or do more complex operations -or use a userspace tracer like LTTng (https://lttng.org). diff --git a/doc/HACKING/WritingTests.md b/doc/HACKING/WritingTests.md index 05de8e0be8..e1497a77c2 100644 --- a/doc/HACKING/WritingTests.md +++ b/doc/HACKING/WritingTests.md @@ -1,6 +1,4 @@ - -Writing tests for Tor: an incomplete guide -========================================== +# Writing tests for Tor: an incomplete guide Tor uses a variety of testing frameworks and methodologies to try to keep from introducing bugs. The major ones are: @@ -19,8 +17,7 @@ keep from introducing bugs. The major ones are: 5. The Shadow network simulator. -How to run these tests ----------------------- +## How to run these tests ### The easy version @@ -64,7 +61,7 @@ The former are those that should finish in a few seconds; the latter tend to take more time, and may include CPU-intensive operations, deliberate delays, and stuff like that. -### Finding test coverage +## Finding test coverage Test coverage is a measurement of which lines your tests actually visit. @@ -110,9 +107,11 @@ covered or uncovered. To count new or modified uncovered lines in D2, you can run: - ./scripts/test/cov-diff ${D1} ${D2}" | grep '^+ *\#' | wc -l +```console +$ ./scripts/test/cov-diff ${D1} ${D2}" | grep '^+ *\#' | wc -l +``` -### Marking lines as unreachable by tests +## Marking lines as unreachable by tests You can mark a specific line as unreachable by using the special string LCOV_EXCL_LINE. You can mark a range of lines as unreachable @@ -126,9 +125,7 @@ unreached lines with 'x', and excluded reached lines with '!!!'. Note: you should never do this unless the line is meant to 100% unreachable by actual code. - -What kinds of test should I write? ----------------------------------- +## What kinds of test should I write? Integration testing and unit testing are complementary: it's probably a good idea to make sure that your code is hit by both if you can. @@ -143,8 +140,7 @@ If your code adds new externally visible functionality to Tor, it would be great to have a test for that functionality. That's where integration tests more usually come in. -Unit and regression tests: Does this function do what it's supposed to? ------------------------------------------------------------------------ +## Unit and regression tests: Does this function do what it's supposed to? Most of Tor's unit tests are made using the "tinytest" testing framework. You can see a guide to using it in the tinytest manual at @@ -165,32 +161,34 @@ If you have created a new test file, you will need to: I use the term "unit test" and "regression tests" very sloppily here. -### A simple example +## A simple example Here's an example of a test function for a simple function in util.c: - static void - test_util_writepid(void *arg) - { - (void) arg; +```c +static void +test_util_writepid(void *arg) +{ + (void) arg; - char *contents = NULL; - const char *fname = get_fname("tmp_pid"); - unsigned long pid; - char c; + char *contents = NULL; + const char *fname = get_fname("tmp_pid"); + unsigned long pid; + char c; - write_pidfile(fname); + write_pidfile(fname); - contents = read_file_to_str(fname, 0, NULL); - tt_assert(contents); + contents = read_file_to_str(fname, 0, NULL); + tt_assert(contents); - int n = sscanf(contents, "%lu\n%c", &pid, &c); - tt_int_op(n, OP_EQ, 1); - tt_int_op(pid, OP_EQ, getpid()); + int n = sscanf(contents, "%lu\n%c", &pid, &c); + tt_int_op(n, OP_EQ, 1); + tt_int_op(pid, OP_EQ, getpid()); - done: - tor_free(contents); - } +done: + tor_free(contents); +} +``` This should look pretty familiar to you if you've read the tinytest manual. One thing to note here is that we use the testing-specific @@ -207,7 +205,7 @@ Finally, remember that by convention, all `*_free()` functions that Tor defines are defined to accept NULL harmlessly. Thus, you don't need to say `if (contents)` in the cleanup block. -### Exposing static functions for testing +## Exposing static functions for testing Sometimes you need to test a function, but you don't want to expose it outside its usual module. @@ -220,15 +218,17 @@ macro-protected declaration of the function in the module's header. For example, `crypto_curve25519.h` contains: - #ifdef CRYPTO_CURVE25519_PRIVATE - STATIC int curve25519_impl(uint8_t *output, const uint8_t *secret, - const uint8_t *basepoint); - #endif +```c +#ifdef CRYPTO_CURVE25519_PRIVATE +STATIC int curve25519_impl(uint8_t *output, const uint8_t *secret, + const uint8_t *basepoint); +#endif +``` The `crypto_curve25519.c` file and the `test_crypto.c` file both define `CRYPTO_CURVE25519_PRIVATE`, so they can see this declaration. -### STOP! Does this test really test? +## STOP! Does this test really test? When writing tests, it's not enough to just generate coverage on all the lines of the code that you're testing: It's important to make sure that @@ -237,28 +237,29 @@ the test _really tests_ the code. For example, here is a _bad_ test for the unlink() function (which is supposed to remove a file). - static void - test_unlink_badly(void *arg) - { - (void) arg; - int r; - - const char *fname = get_fname("tmpfile"); +```c +static void +test_unlink_badly(void *arg) +{ + (void) arg; + int r; - /* If the file isn't there, unlink returns -1 and sets ENOENT */ - r = unlink(fname); - tt_int_op(n, OP_EQ, -1); - tt_int_op(errno, OP_EQ, ENOENT); + const char *fname = get_fname("tmpfile"); - /* If the file DOES exist, unlink returns 0. */ - write_str_to_file(fname, "hello world", 0); - r = unlink(fnme); - tt_int_op(r, OP_EQ, 0); + /* If the file isn't there, unlink returns -1 and sets ENOENT */ + r = unlink(fname); + tt_int_op(n, OP_EQ, -1); + tt_int_op(errno, OP_EQ, ENOENT); - done: - tor_free(contents); - } + /* If the file DOES exist, unlink returns 0. */ + write_str_to_file(fname, "hello world", 0); + r = unlink(fnme); + tt_int_op(r, OP_EQ, 0); +done: + tor_free(contents); +} +``` This test might get very high coverage on unlink(). So why is it a bad test? Because it doesn't check that unlink() *actually removes the @@ -269,8 +270,7 @@ it's supposed to do, and fail otherwise. Try to design your tests so that they check for the code's intended and documented functionality as much as possible. - -### Mock functions for testing in isolation +## Mock functions for testing in isolation Often we want to test that a function works right, but the function to be tested depends on other functions whose behavior is hard to observe, @@ -280,20 +280,25 @@ To write tests for this case, you can replace the underlying functions with testing stubs while your unit test is running. You need to declare the underlying function as 'mockable', as follows: - MOCK_DECL(returntype, functionname, (argument list)); +```c +MOCK_DECL(returntype, functionname, (argument list)); +``` and then later implement it as: - MOCK_IMPL(returntype, functionname, (argument list)) - { - /* implementation here */ - } +```c +MOCK_IMPL(returntype, functionname, (argument list)) +{ + /* implementation here */ +} +``` For example, if you had a 'connect to remote server' function, you could declare it as: - - MOCK_DECL(int, connect_to_remote, (const char *name, status_t *status)); +```c +MOCK_DECL(int, connect_to_remote, (const char *name, status_t *status)); +``` When you declare a function this way, it will be declared as normal in regular builds, but when the module is built for testing, it is declared @@ -302,16 +307,20 @@ as a function pointer initialized to the actual implementation. In your tests, if you want to override the function with a temporary replacement, you say: - MOCK(functionname, replacement_function_name); +```c +MOCK(functionname, replacement_function_name); +``` And later, you can restore the original function with: - UNMOCK(functionname); +```c +UNMOCK(functionname); +``` For more information, see the definitions of this mocking logic in `testsupport.h`. -### Okay but what should my tests actually do? +## Okay but what should my tests actually do? We talk above about "test coverage" -- making sure that your tests visit every line of code, or every branch of code. But visiting the code isn't @@ -331,11 +340,13 @@ cases and failure csaes. For example, consider testing this function: - /** Remove all elements E from sl such that E==element. Preserve - * the order of any elements before E, but elements after E can be - * rearranged. - */ - void smartlist_remove(smartlist_t *sl, const void *element); +```c +/** Remove all elements E from sl such that E==element. Preserve + * the order of any elements before E, but elements after E can be + * rearranged. + */ +void smartlist_remove(smartlist_t *sl, const void *element); +``` In order to test it well, you should write tests for at least all of the following cases. (These would be black-box tests, since we're only looking @@ -362,19 +373,21 @@ When you consider edge cases, you might try: Now let's look at the implementation: - void - smartlist_remove(smartlist_t *sl, const void *element) - { - int i; - if (element == NULL) +```c +void +smartlist_remove(smartlist_t *sl, const void *element) +{ + int i; + if (element == NULL) return; - for (i=0; i < sl->num_used; i++) + for (i=0; i < sl->num_used; i++) if (sl->list[i] == element) { - sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ - i--; /* so we process the new i'th element */ - sl->list[sl->num_used] = NULL; + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl->list[sl->num_used] = NULL; } - } +} +``` Based on the implementation, we now see three more edge cases to test: @@ -382,8 +395,7 @@ Based on the implementation, we now see three more edge cases to test: * Removing an element from the end of the list * Removing an element from a position other than the end of the list. - -### What should my tests NOT do? +## What should my tests NOT do? Tests shouldn't require a network connection. @@ -401,8 +413,7 @@ When possible, tests should not be over-fit to the implementation. That is, the test should verify that the documented behavior is implemented, but should not break if other permissible behavior is later implemented. - -### Advanced techniques: Namespaces +## Advanced techniques: Namespaces Sometimes, when you're doing a lot of mocking at once, it's convenient to isolate your identifiers within a single namespace. If this were C++, we'd @@ -414,9 +425,7 @@ them, you define `NS_MODULE` to a prefix to be used for your identifiers, and then use other macros in place of identifier names. See `src/test/test.h` for more documentation. - -Integration tests: Calling Tor from the outside ------------------------------------------------ +## Integration tests: Calling Tor from the outside Some tests need to invoke Tor from the outside, and shouldn't run from the same process as the Tor test program. Reasons for doing this might include: @@ -436,8 +445,7 @@ wrapped, add a new shell script to `TESTS`, and the new program to makefile (eg `${PYTHON}` for a python interpreter), then make sure that the makefile exports them. -Writing integration tests with Stem ------------------------------------ +## Writing integration tests with Stem The 'stem' library includes extensive tests for the Tor controller protocol. You can run stem tests from tor with `make test-stem`, or see @@ -483,8 +491,7 @@ you notice any strange behaviour that seems totally unreasonable. Check out the `test_exit_policy()` function in abovementioned file to see the final implementation for this test. -System testing with Chutney ---------------------------- +## System testing with Chutney The 'chutney' program configures and launches a set of Tor relays, authorities, and clients on your local host. It has a `test network` @@ -497,3 +504,15 @@ targets in `Makefile.am`. (Adding new kinds of program to chutney will still require hacking the code.) + +## Other integration tests + +It's fine to write tests that use a POSIX shell to invoke Tor or test other +aspects of the system. When you do this, have a look at our existing tests +of this kind in `src/test/` to make sure that you haven't forgotten anything +important. For example: it can be tricky to make sure you're invoking Tor at +the right path in various build scenarios. + +We use a POSIX shell whenever possible here, and we use the shellcheck tool +to make sure that our scripts portable. We should only require bash for +scripts that are developer-only. diff --git a/doc/HACKING/android/Simpleperf.md b/doc/HACKING/android/Simpleperf.md index 25f39a3d23..ed640f912e 100644 --- a/doc/HACKING/android/Simpleperf.md +++ b/doc/HACKING/android/Simpleperf.md @@ -29,7 +29,9 @@ the Android Software Development Kit (SDK) and Native Development Kit 3. Install the Android Package you generated in step 1: +```bash $ adb install /path/to/your/app-fullperm-debug.apk +``` 4. Check on your device that the newly installed Orbot actually works and behaves in the way you expect it to. @@ -76,10 +78,12 @@ was spend on the call. To access binaries, `torrc` files, and other useful information on the device do the following: +```console $ adb shell (device):/ $ run-as org.torproject.android (device):/data/data/org.torproject.android $ ls app_bin app_data cache databases files lib shared_prefs +``` Descriptors, control authentication cookie, state, and other files can be found in the `app_data` directory. The `torrc` can be found in the `app_bin/` @@ -88,11 +92,14 @@ was spend on the call. - You can enable logging in Tor via the syslog (or android) log mechanism with: +```console $ adb shell (device):/ $ run-as org.torproject.android (device):/data/data/org.torproject.android $ echo -e "\nLog info syslog" >> app_bin/torrc +``` Start Tor the normal way via Orbot and collect the logs from your computer using +```console $ adb logcat - +``` diff --git a/doc/HACKING/tracing/EventsCircuit.md b/doc/HACKING/tracing/EventsCircuit.md new file mode 100644 index 0000000000..42abdda856 --- /dev/null +++ b/doc/HACKING/tracing/EventsCircuit.md @@ -0,0 +1,139 @@ +# Circuit Subsystem Trace Events + +The circuit subsystem emits a series of tracing events related to a circuit +object life cycle and its state change. + +This document describes each event as in what data they record and what they +represent. + +## Background + +There are two types of circuits: origin and OR (onion router). Both of them +are derived from a base object called a general circuit. + +- Origin circuits are the ones initiated by tor itself so client or onion + service circuits for instance. + +- OR circuits are the ones going through us that we have not initiated and + thus only seen by relays. + +Many operations are done on the base (general) circuit, and some are specific +to an origin or OR. The following section describes each of them by circuit +type. + +## Trace Events + +For the LTTng tracer, the subsystem name of these events is: `tor_circuit`. + +Also, unless specified otherwise, every event emits a common set of parameters +thus they should always be expected in the following order: + +- `circ_id`: For an origin circuit, this is the global circuit identifier used + in a cell. For an OR circuit, the value is 0. + +- `purpose`: Purpose of the circuit as in what it is used for. Note that this + can change during the lifetime of a circuit. See `CIRCUIT_PURPOSE_*` in + `core/or/circuitlist.h` for an exhaustive list of the possible values. + +- `state`: State of a circuit. This changes during the lifetime of a circuit. + See `CIRCUIT_STATE_*` in `core/or/circuitlist.h` for an exhaustive list of + the possible values. + +Now, the tracing events. + +### General Circuit (`circuit_t`) + +The following events are triggered for the base circuit object and thus apply +to all types of circuits. + + * `free`: A circuit object is freed that is memory is released and not + usable anymore. After this event, no more events will be emitted for the + specific circuit object. + + * `mark_for_close`: A circuit object is marked for close that is scheduled + to be closed in a later mainloop periodic event. + + Extra parameters: + + - `end_reason`: Reason why the circuit is closed. Tor often changes that + reason to something generic sometimes in order to avoid leaking internal + reasons to the end point. Thus, this value can be different from + orig_close_reason. + + - `orig_close_reason`: Original reason why the circuit is closed. That + value never changes and contains the internal reason why we close it. It + is **never** this reason that is sent back on the circuit. + + * `change_purpose`: Purpose change. + + Extra parameters: + + (`purpose` parameter is not present) + + - `old_purpose`: Previous purpose that is no longer. + + - `new_purpose`: New purpose assigned to the circuit. + + * `change_state`: State change. + + Extra parameters: + + (`state` parameter is not present) + + - `old_state`: Previous state that is no longer. + + - `new_state`: New state assigned to the circuit. + +### Origin Circuit (`origin_circuit_t`) + +The following events are triggered only for origin circuits. + + * `new_origin`: New origin circuit has been created meaning it has been + newly allocated, initialized and added to the global list. + + * `establish`: Circuit is being established. This is the initial first step + where the path was selected and a connection to the first hop has been + launched. + + * `cannibalized`: Circuit has been cannibalized. This happens when we have + an already opened unused circuit (preemptive circuits) and it was picked. + + * `first_onion_skin`: First onion skin was sent that is the handshake with + the first hop. + + Extra parameters: + + - `fingerprint`: Identity digest (RSA) of the first hop. + + * `intermediate_onion_skin`: An intermediate onion skin was sent which can + be why any hops after the first one. There is thus `N - 1` of these events + where `N` is the total number of hops in the path. + + Extra parameters: + + - `fingerprint`: Identity digest (RSA) of the next hop. + + * `opened`: Circuit just became opened which means that all hops down the + path have negotiated the handshake between them and us and the circuit is + now ready to send cells. + + * `timeout`: Circuit has timed out that is we waited too long for the + circuit to be built. + + * `idle_timeout`: Circuit has timed out due to idleness. This is controlled + by the MaxCircuitDirtiness parameter which is 10 min by default. + +For the common use case of a 3-hop circuit, the following events should be +seen in this order: + + `new_origin` -> `establish` -> `first_onion_skin` -> + `intermediate_onion_skin` -> `intermediate_onion_skin` -> `opened` + +### OR Circuit (`or_circuit_t`) + +The following events are triggered only for OR circuits. For each of them, the +`circ_id` parameter is not present since it would always be 0. The `purpose` +and `state` remain. + + * `new_or`: New OR circuit has been created meaning it has been newly + allocated, initialized and added to the global list. diff --git a/doc/HACKING/tracing/README.md b/doc/HACKING/tracing/README.md new file mode 100644 index 0000000000..f34709bf3a --- /dev/null +++ b/doc/HACKING/tracing/README.md @@ -0,0 +1,163 @@ +# Tracing + +This document describes how the event tracing subsystem works in tor so +developers can add events to the code base but also hook them to an event +tracing framework (i.e. tracer). + +## WARNING ## + +Tracing the tor daemon **always** generates sensitive data if used in +production (on the public network). + +It **is** ethical for researchers to use tracing for their own tor client (for +example: building paths, timings, or performance). + +It is **NOT** ethical to archive, publish or keep data containing other users' +activity such as relay data or anything that handles users' traffic. This +of course includes any logs below notice level. + +Publishing analysis of tracing data containing user traffic is **NOT** safe +either. + +In other words, tracing data that contains other users's activity is **NOT** +safe to publish in any form. + +## Basics ### + +Tracing is separated in two different concepts. The tracing API and the +tracing probes. + +The API is in `src/lib/trace/` which defines how to call tracepoints in the +tor code. Every C files should include `src/lib/trace/events.h` if they want +to call a tracepoint. + +The probes are what actually record the tracepoint data. Because they often +need to access specific subsystem objects, the probes are within each +subsystem. They are defined in the `trace-probes-<subsystem>.c` files. + +### Events + +A trace event is basically a function from which we can pass any data that we +want to collect. In addition, we specify a context for the event such as the +subsystem and an event name. + +A trace event in tor has the following standard format: + +```c +tor_trace(subsystem, event_name, args...); +``` + +The `subsystem` parameter is the name of the subsystem the trace event is in. +For example that could be "scheduler" or "vote" or "hs". The idea is to add +some context to the event so when we collect them we know where it's coming +from. + +The `event_name` is the name of the event which adds better semantic to the +event. + +The `args` can be any number of arguments we want to collect. + +Here is an example of a possible tracepoint in main(): + +```c +tor_trace(main, init_phase, argc); +``` + +The above is a tracepoint in the `main` subsystem with `init_phase` as the +event name and the `int argc` is passed to the event as one argument. + +How `argc` is collected or used has nothing to do with the instrumentation +(adding trace events to the code). It is the work of the tracer so this is why +the trace events and collection framework (tracer) are decoupled. You _can_ +have trace events without a tracer. + +### Instrumentation ### + +In `src/lib/trace/events.h`, we map the high level `tor_trace()` macro to one +or many enabled instrumentation. + +Currently, we have 3 types of possible instrumentation: + +1. Debug + + This will map every tracepoint to `log_debug()`. However, none of the + arguments will be passed on because we don't know their type nor the string + format of the debug log. The output is standardized like this: + +``` +[debug] __FUNC__: Tracepoint <event_name> from subsystem <subsystem> hit. +``` + +2. USDT + + User Statically-Defined Tracing (USDT) is a kind of probe which can be + handled by a variety of tracers such as SystemTap, DTrace, perf, eBPF and + ftrace. + + For each tracer, one will need to define the ABI in order for the tracer to + be able to extract the data from the tracepoint objects. For instance, the + tracer needs to know how to print the circuit state of a `circuit_t` + object. + +3. LTTng-UST + + LTTng Userspace is a tracer that has it own type of instrumentation. The + probe definitions are created within the C code and is strongly typed. + + For more information, see https://lttng.org/docs. + +## Build System + +This section describes how the instrumentation is integrated into the build +system of tor. + +By default, every tracing events are disabled in tor that is `tor_trace()` is +a NOP thus has no execution cost time. + +To enable a specific instrumentation, there are configure options: + +1. Debug: `--enable-tracing-instrumentation-debug` + +2. USDT: `--enable-tracing-instrumentation-usdt` + +3. LTTng: `--enable-tracing-instrumentation-lttng` + +They can all be used together or independently. If one of them is set, +`HAVE_TRACING` define is set. And for each instrumentation, a +`USE_TRACING_INSTRUMENTATION_<type>` is set. + +## Adding a Tracepoint ## + +This is pretty easy. Let's say you want to add a trace event in +`src/feature/rend/rendcache.c`, you first need to include this file: + +```c +#include "lib/trace/events.h" +``` + +Then, the `tor_trace()` macro can be used with the specific format detailed +before in a previous section. As an example: + +```c +tor_trace(hs, store_desc_as_client, desc, desc_id); +``` + +For `Debug` instrumentation, you have nothing else to do. + +For `USDT`, instrumentation, you will need to define the probes in a way the +specific tracer can understand. For instance, SystemTap requires you to define +a `tapset` for each tracepoints. + +For `LTTng`, you will need to define the probes in the +`trace-probes-<subsystem>.{c|h}` file. See the `trace-probes-circuit.{c|h}` +file as an example and https://lttng.org/docs/v2.11/#doc-instrumenting. + +## Performance ## + +A word about performance when a tracepoint is enabled. One of the goal of a +tracepoint (USDT, LTTng-UST, ...) is that they can be enabled or disabled. By +default, they are disabled which means the tracer will not record the data but +it has to do a check thus the cost is basically the one of a `branch`. + +If enabled, then the performance depends on the tracer. In the case of +LTTng-UST, the event costs around 110nsec. |