| 1 | package idear |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "net/http/httptest" |
| 6 | "sync" |
| 7 | "testing" |
| 8 | "time" |
| 9 | ) |
| 10 | |
| 11 | // The limiter's own tests live inside the package because the thing |
| 12 | // worth proving about it — that the table is BOUNDED — is not visible |
| 13 | // from outside: a caller can only observe 429s, and a limiter that |
| 14 | // leaked a bucket per client would answer exactly the same 429s while |
| 15 | // growing until the process died. |
| 16 | |
| 17 | func TestLimiterSpendsAndRefills(t *testing.T) { |
| 18 | now := time.Now() |
| 19 | l := newLimiter(RateLimit{Burst: 3, Every: time.Second}) |
| 20 | l.now = func() time.Time { return now } |
| 21 | |
| 22 | for i := range 3 { |
| 23 | if !l.allow("a") { |
| 24 | t.Fatalf("request %d of a burst of 3 was refused", i+1) |
| 25 | } |
| 26 | } |
| 27 | if l.allow("a") { |
| 28 | t.Fatal("the fourth request of a burst of 3 was allowed") |
| 29 | } |
| 30 | // Another client has their own budget: the limit is per client and |
| 31 | // not global, or one prober would lock out every invitee. |
| 32 | if !l.allow("b") { |
| 33 | t.Fatal("a second client was refused on their first request") |
| 34 | } |
| 35 | |
| 36 | // One token comes back per Every, and no more than Burst ever |
| 37 | // accumulates. |
| 38 | now = now.Add(time.Second) |
| 39 | if !l.allow("a") { |
| 40 | t.Fatal("no token came back after one refill interval") |
| 41 | } |
| 42 | if l.allow("a") { |
| 43 | t.Fatal("more than one token came back in one interval") |
| 44 | } |
| 45 | now = now.Add(time.Hour) |
| 46 | for i := range 3 { |
| 47 | if !l.allow("a") { |
| 48 | t.Fatalf("request %d after a long idle was refused", i+1) |
| 49 | } |
| 50 | } |
| 51 | if l.allow("a") { |
| 52 | t.Fatal("an idle client accumulated more than Burst tokens") |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | func TestLimiterTableIsBounded(t *testing.T) { |
| 57 | now := time.Now() |
| 58 | const max = 8 |
| 59 | l := newLimiter(RateLimit{Burst: 2, Every: time.Second, Max: max}) |
| 60 | l.now = func() time.Time { return now } |
| 61 | |
| 62 | // Far more clients than the table may hold, each spending their |
| 63 | // whole burst so none of them is sweepable. |
| 64 | for i := range max * 10 { |
| 65 | key := fmt.Sprintf("client-%d", i) |
| 66 | l.allow(key) |
| 67 | l.allow(key) |
| 68 | if got := l.size(); got > max { |
| 69 | t.Fatalf("the table holds %d buckets, above the bound of %d", got, max) |
| 70 | } |
| 71 | } |
| 72 | if got := l.size(); got != max { |
| 73 | t.Fatalf("the table holds %d buckets, want it filled to %d", got, max) |
| 74 | } |
| 75 | |
| 76 | // A full table FAILS CLOSED for an unseen client — see RateLimit.Max. |
| 77 | if l.allow("someone-new") { |
| 78 | t.Error("a full table admitted an unseen client; it must fail closed") |
| 79 | } |
| 80 | // And a client already in the table is unaffected by the crowd. |
| 81 | if l.allow("client-0") { |
| 82 | t.Error("client-0 had spent its burst and was allowed anyway") |
| 83 | } |
| 84 | |
| 85 | // Once the crowd's buckets refill they are swept, and the table |
| 86 | // takes new clients again — the bound is on live clients, not a |
| 87 | // permanent cap on how many the process may ever see. |
| 88 | now = now.Add(time.Hour) |
| 89 | if !l.allow("someone-new") { |
| 90 | t.Error("a swept table still refused a new client") |
| 91 | } |
| 92 | if got := l.size(); got > max { |
| 93 | t.Fatalf("the table holds %d buckets after a sweep", got) |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | func TestLimiterIsConcurrencySafe(t *testing.T) { |
| 98 | l := newLimiter(RateLimit{Burst: 1000, Every: time.Hour, Max: 16}) |
| 99 | var wg sync.WaitGroup |
| 100 | for i := range 8 { |
| 101 | wg.Add(1) |
| 102 | go func() { |
| 103 | defer wg.Done() |
| 104 | for j := range 50 { |
| 105 | l.allow(fmt.Sprintf("client-%d", (i+j)%16)) |
| 106 | } |
| 107 | }() |
| 108 | } |
| 109 | wg.Wait() |
| 110 | if got := l.size(); got > 16 { |
| 111 | t.Fatalf("the table holds %d buckets, above the bound of 16", got) |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | func TestClientIPKeysByNetworkNotAddress(t *testing.T) { |
| 116 | key := func(remote string) string { |
| 117 | r := httptest.NewRequest("GET", "/invitations/x", nil) |
| 118 | r.RemoteAddr = remote |
| 119 | return clientIP(r) |
| 120 | } |
| 121 | |
| 122 | // IPv4: the address, without the port. A browser making a second |
| 123 | // request from a new source port must share the first one's |
| 124 | // budget, or the limit is no limit at all. |
| 125 | if got := key("203.0.113.9:51234"); got != "203.0.113.9" { |
| 126 | t.Errorf("clientIP = %q, want the address without the port", got) |
| 127 | } |
| 128 | if got := key("203.0.113.9:51235"); got != "203.0.113.9" { |
| 129 | t.Errorf("clientIP = %q for a second port, want the same key", got) |
| 130 | } |
| 131 | // ...and a DIFFERENT IPv4 host is a different client. Folding v4 |
| 132 | // further would put a whole CGNAT behind one bucket. |
| 133 | if key("203.0.113.9:1") == key("203.0.113.10:1") { |
| 134 | t.Error("two IPv4 hosts share a key; the fold is too coarse") |
| 135 | } |
| 136 | |
| 137 | // IPv6: the /64, because every host is handed one and can rotate |
| 138 | // addresses inside it for free. Three addresses in one /64 are |
| 139 | // one client. |
| 140 | sixtyFour := key("[2001:db8:1:2::5]:443") |
| 141 | if sixtyFour != "2001:db8:1:2::/64" { |
| 142 | t.Errorf("clientIP = %q, want the /64 prefix", sixtyFour) |
| 143 | } |
| 144 | for _, other := range []string{"[2001:db8:1:2:ffff::9]:443", "[2001:db8:1:2:dead:beef:cafe:1]:80"} { |
| 145 | if got := key(other); got != sixtyFour { |
| 146 | t.Errorf("clientIP(%s) = %q, want the same /64 key %q", other, got, sixtyFour) |
| 147 | } |
| 148 | } |
| 149 | // A different /64 is a different client, so a shared limit does |
| 150 | // not fall out of the fold either. |
| 151 | if got := key("[2001:db8:1:3::5]:443"); got == sixtyFour { |
| 152 | t.Errorf("a neighbouring /64 shares the key %q", got) |
| 153 | } |
| 154 | // An IPv4-mapped address is unmapped first: one client must not |
| 155 | // hold two budgets by switching representation. |
| 156 | if got := key("[::ffff:203.0.113.9]:80"); got != "203.0.113.9" { |
| 157 | t.Errorf("clientIP = %q for an IPv4-mapped address, want %q", got, "203.0.113.9") |
| 158 | } |
| 159 | // The zone is the local interface, not the client. |
| 160 | if key("[fe80::1%eth0]:80") != key("[fe80::1%eth1]:80") { |
| 161 | t.Error("the interface zone splits one client's budget in two") |
| 162 | } |
| 163 | // An address with no port at all (a unix socket, a test) is used |
| 164 | // whole rather than dropped, so it still keys to something. |
| 165 | if got := key("@"); got != "@" { |
| 166 | t.Errorf("clientIP = %q, want the raw RemoteAddr when it has no port", got) |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | // TestClientIPIgnoresForwardingHeaders pins the claim clientIP's doc |
| 171 | // comment makes outright: a header idear cannot verify is a header an |
| 172 | // attacker can spoof to mint unlimited budgets, so idear never reads |
| 173 | // one. Without this test, teaching clientIP to prefer X-Forwarded-For |
| 174 | // left the whole suite green while handing every prober an unlimited |
| 175 | // supply of fresh buckets. |
| 176 | func TestClientIPIgnoresForwardingHeaders(t *testing.T) { |
| 177 | r := httptest.NewRequest("GET", "/invitations/x", nil) |
| 178 | r.RemoteAddr = "203.0.113.9:51234" |
| 179 | for _, header := range []string{"X-Forwarded-For", "X-Real-IP", "Forwarded", "CF-Connecting-IP", "True-Client-IP"} { |
| 180 | r.Header.Set(header, "1.2.3.4") |
| 181 | } |
| 182 | if got := clientIP(r); got != "203.0.113.9" { |
| 183 | t.Errorf("clientIP = %q with forwarding headers set, want the RemoteAddr host %q", got, "203.0.113.9") |
| 184 | } |
| 185 | } |
| 186 | |
| 187 | // TestIPv6RotationCannotLockOutOtherClients is the scenario the /64 |
| 188 | // fold exists for, run end to end against the limiter. |
| 189 | // |
| 190 | // One machine rotates source addresses inside its own /64 — free, on |
| 191 | // any IPv6 host — and spends far more than the table can hold. Keyed |
| 192 | // on the bare address that fills the table, and allow then fails |
| 193 | // closed for every UNSEEN client: invitees, and orphans, whose only |
| 194 | // healing path is POST /invitations/{token}. Failing closed is right; |
| 195 | // the key was the bug. |
| 196 | func TestIPv6RotationCannotLockOutOtherClients(t *testing.T) { |
| 197 | const max = 8 |
| 198 | l := newLimiter(RateLimit{Burst: 2, Every: time.Hour, Max: max}) |
| 199 | |
| 200 | key := func(remote string) string { |
| 201 | r := httptest.NewRequest("POST", "/invitations/x", nil) |
| 202 | r.RemoteAddr = remote |
| 203 | return clientIP(r) |
| 204 | } |
| 205 | |
| 206 | for i := range max * 20 { |
| 207 | l.allow(key(fmt.Sprintf("[2001:db8:1:2::%x]:443", i))) |
| 208 | } |
| 209 | if got := l.size(); got != 1 { |
| 210 | t.Fatalf("one attacker's /64 filled %d buckets, want 1", got) |
| 211 | } |
| 212 | // The attacker is throttled on the budget their whole /64 shares. |
| 213 | if l.allow(key("[2001:db8:1:2::ffff]:443")) { |
| 214 | t.Error("an address rotation inside one /64 bought a fresh burst") |
| 215 | } |
| 216 | // And everybody else is still served — including the orphan whose |
| 217 | // only way back into the instance is the route being defended. |
| 218 | for _, invitee := range []string{"198.51.100.7:1", "[2001:db8:9:9::1]:443", "[2001:db8:aa::5]:443"} { |
| 219 | if !l.allow(key(invitee)) { |
| 220 | t.Errorf("a real client (%s) was locked out by one machine's address rotation", invitee) |
| 221 | } |
| 222 | } |
| 223 | } |
| 224 | |
amadan