[tor-dev] Proposal 341: A better algorithm for out-of-sockets eviction

[Nick Mathewson]

```
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.

1. 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 total `N_CONN = N_DIR + N_OR +
   N_EXIT`.  Define `N_RETAIN = N_CONN - N_CLOSE`.

2. 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 set `T_DIR = 0.1`.
    * If we are an exit or we are running an onion service, let `T_EXIT =
      2`. Otherwise let `T_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)
   ```

3. 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](https://gitlab.torproject.org/tpo/core/tor/-/issues/32794
)
from `starlight`.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20220725/7a129d50/attachment.htm>