Denial of service overview and related edits

This also moves some text from memory-exhaustion to overview,
and it removes the tor-spec/resource-exhaustion section as it's
redundant with the description of the same in dos-spec.

5 files changed, 92 insertions, 55 deletions

diff --git a/spec/SUMMARY.md b/spec/SUMMARY.md
index c425ee6..9cd0933 100644
--- a/spec/SUMMARY.md
+++ b/spec/SUMMARY.md
@@ -29,7 +29,6 @@
     - [Closing streams](./tor-spec/closing-streams.md)
     - [Remote hostname lookup](./tor-spec/remote-hostname-lookup.md)
   - [Flow control](./tor-spec/flow-control.md)
-  - [Handling resource exhaustion](./tor-spec/resource-exhaustion.md)
   - [Subprotocol versioning](./tor-spec/subprotocol-versioning.md)
   - [`Ed25519 certificates in Tor`](./cert-spec.md)
 - [`Tor directory protocol, version 3`](./dir-spec/index.md)
@@ -95,7 +94,9 @@
   - [Connection-level padding](./padding-spec/connection-level-padding.md)
   - [Circuit-level padding](./padding-spec/circuit-level-padding.md)
   - [Acknowledgments](./padding-spec/acknowledgments.md)
-- [Preventing Denial-Of-Service](./dos-spec.md)
+- [`Preventing Denial-Of-Service`](./dos-spec/index.md)
+  - [Overview](./dos-spec/overview.md)
+  - [Memory exhaustion](./dos-spec/memory-exhaustion.md)
 
 # Additional behaviors for clients
 
diff --git a/spec/dos-spec/index.md b/spec/dos-spec/index.md
new file mode 100644
index 0000000..1f88b09
--- /dev/null
+++ b/spec/dos-spec/index.md
@@ -0,0 +1,7 @@
+# Denial-of-service prevention mechanisms in Tor
+
+This document covers the strategy, motivation, and implementation for denial-of-service mitigation systems designed into Tor.
+
+The older `dos-spec` document is now the [Memory exhaustion](./dos-spec/memory-exhaustion.md) section here.
+
+An in-depth description of the proof of work mechanism for onion services, originally [proposal 327](../../proposals/327-pow-over-intro.txt), is now in the [Proof of Work for onion service introduction](../hspow-spec/index.md) spec.
\ No newline at end of file
diff --git a/spec/dos-spec/memory-exhaustion.md b/spec/dos-spec/memory-exhaustion.md
index d37649f..591d950 100644
--- a/spec/dos-spec/memory-exhaustion.md
+++ b/spec/dos-spec/memory-exhaustion.md
@@ -1,28 +1,10 @@
-# Denial-of-service prevention mechanisms in Tor
+# Memory exhaustion { #oom }
 
-This document is incomplete; it describes some mechanisms that Tor
-uses to avoid different kinds of denial-of-service attacks.
+Memory exhaustion is a broad issue with many underlying causes. The Tor protocol requires clients, onion services, relays, and authorities to store various kind of information in buffers and caches.  But an attacker can use these buffers and queues to exhaust the memory of the a targeted Tor process, and force the operating system to kill that process.
 
-## Handling low-memory conditions { #oom }
+With this in mind, any Tor implementation—especially one that runs as a relay or onion service—must take steps to prevent memory-based denial-of-service attacks.
 
-(See also `tor-spec.txt`, section 8.1.)
-
-The Tor protocol requires clients, onion services, relays, and
-authorities to store various kind of information in buffers and
-caches.  But an attacker can use these buffers and queues to queues
-to exhaust the memory of the a targeted Tor process, and force the
-operating system to kill that process.
-
-Worse still, the ability to kill targeted Tor instances can be used
-to facilitate traffic analysis. (For example, see
-[the "Sniper Attack" paper](https://www.freehaven.net/anonbib/#sniper14)
-by Jansen, Tschorsch, Johnson, and Scheuermann.
-
-With this in mind, any Tor implementation—especially one that
-runs as a relay or onion service—must take steps to prevent
-memory-based denial-of-service attacks.
-
-### Detecting low memory { #oom-detection }
+## Detecting low memory { #oom-detection }
 
 The easiest way to notice you're out of memory would, in theory, be
 getting an error when you try to allocate more.  Unfortunately, some
diff --git a/spec/dos-spec/overview.md b/spec/dos-spec/overview.md
new file mode 100644
index 0000000..d715b51
--- /dev/null
+++ b/spec/dos-spec/overview.md
@@ -0,0 +1,78 @@
+# Overview
+
+As a public and anonymous network, Tor is open to many types of denial-of-service attempts. It's necessary to constantly develop a variety of defenses that mitigate specific types of attacks.
+
+These mitigations are expected to improve network availability, but DoS mitigation is also important for limiting the avenues an attacker could use to perform active attacks on anonymity. For example, the ability to kill targeted Tor instances can be used to facilitate traffic analysis. See the ["Sniper Attack" paper](https://www.freehaven.net/anonbib/#sniper14) by Jansen, Tschorsch, Johnson, and Scheuermann.
+
+The attack and defense environment changes over time.
+Expect that this document is an attempt to describe the current state of things, but that it may not be complete.
+
+The defenses here are organized by the type of resource under contention. These can be physical resources (Memory, CPU, Bandwidth) or protocol resources (Connections, Circuits, Introductions).
+
+In practice there are always overlaps between these resource types.
+Connecting to an onion service, for example, puts some strain on every resource type here.
+
+## Physical resources
+
+### Memory {#memory}
+
+[Memory exhaustion](./memory-exhaustion.md) is both one of the most serious denial-of-service avenues and the subject of the most fully developed defense mechanisms so far. We track overall memory use and free the most disposable objects first when usage is over threshold.
+
+### CPU {#cpu}
+
+The available CPU time on a router can be exhausted, assuming the implementation is not capable of processing network input at line rate in all circumstances.
+This is especially problematic in the single-threaded C implementation.
+Certain expensive operations like circuit extension handshakes are deferred to a thread pool, but time on the main thread is still a precious resource.
+
+We currently don't directly monitor and respond to CPU usage.
+Instead C Tor relies on limits for protocol resources, like circuits extensions and onion service introductions, that are associated with this CPU load.
+
+### Bandwidth {#bandwidth}
+
+Relay operators can place hard limits on total bandwidth using the `Bandwidth` or `RelayBandwidth` options. These options can help relay operators avoid bandwidth peaks on their network, however they aren't designed as denial of service prevention mechanisms.
+
+Beyond just shaving off harmful bandwidth peaks it's important that normal service is not disrupted too much, and especially not disrupted in a targetable way.
+To approximate this goal we rely on [flow control](../tor-spec/flow-control.md) and fair dequeueing of relayed cells.
+
+## Protocol resources
+
+### Channels {#channels}
+
+All channels to some extent are a limited resource, but we focus specifically on preventing floods of incoming TLS connections.
+
+Excessive incoming TLS connections consume memory as well as limited network and operating system resources.
+Excessive incoming connections typically signal a low-effort denial of service attack.
+
+The C Tor implementation establishes limits on both the number of concurrent connections per IP address and the rate of new connections, using the `DoSConnection` family of configuration options and their corresponding consensus parameters.
+
+### Circuits {#circuits}
+
+Excessive circuit creation can impact the entire path of that circuit, so it's important to reject these attacks any time they can be identified. Ideally we reject them as early as possible, before they have fully built the circuit.
+
+Because of Tor's anonymity, most affected nodes experience the circuit flood as coming from every direction. The guard position, however, has a chance to notice specific peers that are creating too many circuits.
+
+The C Tor implementation limits the acceptable rate of circuit creation per client IP address using the `DoSCircuit` configuration options and their corresponding consensus parameters.
+
+### Onion service introductions {#hs-intro}
+
+Flooding an onion service with introduction attempts causes significant network load. In addition to the CPU, memory, and bandwidth load experienced by the introduction point and the service, all involved relays experience a circuit creation flood.
+
+We have two types of onion service DoS mitigations currently. Both are optional, enabled as needed by individual onion servce operators.
+
+#### Mitigation by rate limiting {#hs-intro-rate}
+
+Introduction attempts can be rate-limited by each introduction point, at the request of the service.
+
+This defense is configured by an operator using the `HiddenServiceEnableIntroDos` configuration options. Services use the [introduction DoS extension](../rend-spec/introduction-protocol.html#EST_INTRO_DOS_EXT) to communicate these settings to each introduction point.
+
+#### Mitigation using proof of work {#hs-intro-pow}
+
+A short non-interactive computational puzzle can be solved with each connection attempt. Requests provided by the client will be entered into a queue prioritized by their puzzle solution's effort score. Requests are processed by the service at a limited rate, which can be adjusted to a value within the server's capabilities.
+
+Based on the queue behavior, servers will continuously provide an updated effort suggestion.
+Queue backlogs cause the effort to rise, and an idle server will cause the effort to decay.
+If the queue is never overfull the effort decays to zero, asking clients not to include a proof-of-work solution at all.
+
+We may support multiple cryptographic algorithms for this puzzle in the future, but currently we support one type. It's called `v1` in our protocol, and it's based on the Equi-X algorithm developed for this purpose. See `327-pow-over-intro.txt` for more information.
+
+This defense is configured by an operator using the `HiddenServicePoW` configuration options. Additionally, it requires both the client and the onion service to be compiled with the `pow` module (`--enable-gpl` mode) available. Current versions of the Tor Browser do include `pow` support.
diff --git a/spec/tor-spec/resource-exhaustion.md b/spec/tor-spec/resource-exhaustion.md
deleted file mode 100644
index 4dddf9f..0000000
--- a/spec/tor-spec/resource-exhaustion.md
+++ /dev/null
@@ -1,31 +0,0 @@
-<a id="tor-spec.txt-8"></a>
-
-# Handling resource exhaustion
-
-<a id="tor-spec.txt-8.1"></a>
-
-## Memory exhaustion
-
-(See also ["Denial-of-service prevention mechanisms in Tor"](../dos-spec.md).)
-
-If RAM becomes low, an OR should begin destroying circuits until
-more memory is free again.  We recommend the following algorithm:
-
-- Set a threshold amount of RAM to recover at 10% of the total RAM.
-
-- Sort the circuits by their 'staleness', defined as the age of the
-  oldest data queued on the circuit.  This data can be:
-
-     * Bytes that are waiting to flush to or from a stream on that
-       circuit.
-
-     * Bytes that are waiting to flush from a connection created with
-       BEGIN_DIR.
-
-     * Cells that are waiting to flush or be processed.
-
-- While we have not yet recovered enough RAM:
-
-     * Free all memory held by the most stale circuit, and send DESTROY
-       cells in both directions on that circuit.  Count the amount of
-       memory we recovered towards the total.