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