Filename: 341-better-oos.md
Title: A better algorithm for out-of-sockets eviction
Author: Nick Mathewson
Created: 25 July 2022
Status: Open
Introduction
Our existing algorithm for handling an out-of-sockets condition needs
improvement. It only handles sockets used for OR connections, and
prioritizes those with more circuits. Because of these weaknesses, the
algorithm is trivial to circumvent, and it’s disabled by default with
DisableOOSCheck.
Here we propose a new algorithm for choosing which connections to close
when we’re out of sockets. In summary, the new algorithm works by
deciding which kinds of connections we have “too many” of, and then by
closing excess connections of each kind. The algorithm for selecting
connections of each kind is different.
Intuitions behind the algorithm below
We want to keep a healthy mix of connections running; favoring one kind
of connection over another gives the attacker a fine way to starve the
disfavored connections by making a bunch of the favored kind.
The correct mix of connections depends on the type of service we are
providing. Everywhere except authorities, for example, inbound
directory connections are perfectly fine to close, since nothing in our
protocol actually generates them.
In general, we would prefer to close DirPort connections, then Exit
connections, then OR connections.
The priority with which to close connections is different depending on
the connection type. “Age of connection” or “number of circuits” may be
a fine metric for how truly used an OR connection is, but for a DirPort
connection, high age is suspicious.
The algorithm
Define a “candidate” connection as one that has a socket, and is either
an exit stream, an inbound directory stream, or an OR connection.
(Note that OR connections can be from clients, relays, or bridges. Note
that ordinary relays should not get directory streams that use sockets,
since clients always use BEGIN_DIR to create tunneled directory
streams.)
In all of the following, treat subtraction as saturating at zero. In
other words, when you see “A - B” below, read it as “MAX(A-B, 0)”.
Phase 1: Deciding how many connections to close
When we are find that we are low on sockets, we pick a number of sockets
that we want to close according to our existing algorithm. (That is, we
try to close 1/4 of our maximum sockets if we have reached our upper
limit, or 1/10 of our maximum sockets if we have encountered a failure
from socket(2).) Call this N_CLOSE.
Then we decide which sockets to target based on this algorithm.
-
Consider the total number of sockets used for exit streams
(N_EXIT), the total number used for inbound directory streams
(N_DIR), and the total number used for OR connections (N_OR).
(In these calculations, we exclude connections that are already
marked to be closed.) Call the totalN_CONN = N_DIR + N_OR + N_EXIT. DefineN_RETAIN = N_CONN - N_CLOSE. -
Compute how many connections of each type are “in excess”. First,
calculate our target proportions:
- If we are an authority, let
T_DIR= 1. Otherwise setT_DIR = 0.1. - If we are an exit or we are running an onion service, let
T_EXIT = 2. Otherwise letT_EXIT = 0.1. - Let
T_OR= 1.
TODO: Should those numbers be consensus parameters?
These numbers define the relative proportions of connections that
we would be willing to retain retain in our final mix. Compute a
number of excess connections of each type by calculating.
T_TOTAL = T_OR + T_DIR + T_EXIT.
EXCESS_DIR = N_DIR - N_RETAIN * (T_DIR / T_TOTAL)
EXCESS_EXIT = N_EXIT - N_RETAIN * (T_EXIT / T_TOTAL)
EXCESS_OR = N_OR - N_RETAIN * (T_OR / T_TOTAL)
- Finally, divide N_CLOSE among the different types of excess
connections, assigning first to excess directory connections, then
excess exit connections, and finally to excess OR connections.
CLOSE_DIR = MIN(EXCESS_DIR, N_CLOSE)
N_CLOSE := N_CLOSE - CLOSE_DIR
CLOSE_EXIT = MIN(EXCESS_EXIT, N_CLOSE)
N_CLOSE := N_CLOSE - CLOSE_EXIT
CLOSE_OR = MIN(EXCESS_OR, N_CLOSE)
We will try to close CLOSE_DIR directory connections, CLOSE_EXIT
exit connections, and CLOSE_OR OR connections.
Phase 2: Closing directory connections
We want to close a certain number of directory connections. To select
our targets, we sort first by the number of directory connections from
a similar address (see “similar address” below) and then by their age,
preferring to close the oldest ones first.
This approach defeats “many requests from the same address” and “Open
a connection and hold it open, and do so from many addresses”. It
doesn’t do such a great job with defeating “open and close frequently
and do so on many addresses.”
Note that fallback directories do not typically use sockets for
handling directory connections: theirs are usually created with
BEGIN_DIR.
Phase 3: Closing exit connections.
We want to close a certain number of exit connections. To do this, we
pick an exit connection at random, then close its circuit along with
all the other exit connections on the same circuit. Then we repeat
until we have closed at least our target number of exit connections.
This approach probabilistically favors closing circuits with a large
number of sockets open, regardless of how long those sockets have been
open. This defeats the easiest way of opening a large number of exit
streams (“open them all on once circuit”) without making the
counter-approach (“open each exit stream on a its own circuit”) much
more attractive.
Phase 3: Closing OR connections.
We want to close a certain number of OR connections, to clients, bridges, or
relays.
To do this, we first close OR connections with zero circuits. Then we
close all OR connections but the most recent 2 from each “similar
address”. Then we close OR connections at random from among those not
to a recognized relay in the latest directory. Finally, we close OR
connections at random.
We used to unconditionally prefer to close connections with fewer
circuits. That’s trivial for an adversary to circumvent, though: they
can just open a bunch of circuits on their bogus OR connections, and
force us to preferentially close circuits from real clients, bridges,
and relays.
Note that some connections that seem like client connections (“not
from relays in the latest directory”) are actually those created by
bridges.
What is “A similar address”?
We define two connections as having a similar address if they are in the
same IPv4 /30, or if they are in the same IPv6 /90.
Acknowledgments
This proposal was inspired by a set of OOS improvements from starlight.