1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // The tests in this file attempt to verify the following through simulation:
6 // a) That a server experiencing overload will actually benefit from the
7 // anti-DDoS throttling logic, i.e. that its traffic spike will subside
8 // and be distributed over a longer period of time;
9 // b) That "well-behaved" clients of a server under DDoS attack actually
10 // benefit from the anti-DDoS throttling logic; and
11 // c) That the approximate increase in "perceived downtime" introduced by
12 // anti-DDoS throttling for various different actual downtimes is what
13 // we expect it to be.
14
15 #include <cmath>
16 #include <limits>
17 #include <memory>
18 #include <vector>
19
20 #include "base/environment.h"
21 #include "base/rand_util.h"
22 #include "base/stl_util.h"
23 #include "base/test/task_environment.h"
24 #include "base/time/time.h"
25 #include "net/base/request_priority.h"
26 #include "net/traffic_annotation/network_traffic_annotation_test_helper.h"
27 #include "net/url_request/url_request.h"
28 #include "net/url_request/url_request_context.h"
29 #include "net/url_request/url_request_test_util.h"
30 #include "net/url_request/url_request_throttler_manager.h"
31 #include "net/url_request/url_request_throttler_test_support.h"
32 #include "testing/gtest/include/gtest/gtest.h"
33
34 using base::TimeDelta;
35 using base::TimeTicks;
36
37 namespace net {
38 namespace {
39
40 // Set this variable in your environment if you want to see verbose results
41 // of the simulation tests.
42 const char kShowSimulationVariableName[] = "SHOW_SIMULATION_RESULTS";
43
44 // Prints output only if a given environment variable is set. We use this
45 // to not print any output for human evaluation when the test is run without
46 // supervision.
VerboseOut(const char * format,...)47 void VerboseOut(const char* format, ...) {
48 static bool have_checked_environment = false;
49 static bool should_print = false;
50 if (!have_checked_environment) {
51 have_checked_environment = true;
52 std::unique_ptr<base::Environment> env(base::Environment::Create());
53 if (env->HasVar(kShowSimulationVariableName))
54 should_print = true;
55 }
56
57 if (should_print) {
58 va_list arglist;
59 va_start(arglist, format);
60 vprintf(format, arglist);
61 va_end(arglist);
62 }
63 }
64
65 // A simple two-phase discrete time simulation. Actors are added in the order
66 // they should take action at every tick of the clock. Ticks of the clock
67 // are two-phase:
68 // - Phase 1 advances every actor's time to a new absolute time.
69 // - Phase 2 asks each actor to perform their action.
70 class DiscreteTimeSimulation {
71 public:
72 class Actor {
73 public:
74 virtual ~Actor() = default;
75 virtual void AdvanceTime(const TimeTicks& absolute_time) = 0;
76 virtual void PerformAction() = 0;
77 };
78
79 DiscreteTimeSimulation() = default;
80
81 // Adds an |actor| to the simulation. The client of the simulation maintains
82 // ownership of |actor| and must ensure its lifetime exceeds that of the
83 // simulation. Actors should be added in the order you wish for them to
84 // act at each tick of the simulation.
AddActor(Actor * actor)85 void AddActor(Actor* actor) {
86 actors_.push_back(actor);
87 }
88
89 // Runs the simulation for, pretending |time_between_ticks| passes from one
90 // tick to the next. The start time will be the current real time. The
91 // simulation will stop when the simulated duration is equal to or greater
92 // than |maximum_simulated_duration|.
RunSimulation(const TimeDelta & maximum_simulated_duration,const TimeDelta & time_between_ticks)93 void RunSimulation(const TimeDelta& maximum_simulated_duration,
94 const TimeDelta& time_between_ticks) {
95 TimeTicks start_time = TimeTicks();
96 TimeTicks now = start_time;
97 while ((now - start_time) <= maximum_simulated_duration) {
98 for (auto it = actors_.begin(); it != actors_.end(); ++it) {
99 (*it)->AdvanceTime(now);
100 }
101
102 for (auto it = actors_.begin(); it != actors_.end(); ++it) {
103 (*it)->PerformAction();
104 }
105
106 now += time_between_ticks;
107 }
108 }
109
110 private:
111 std::vector<Actor*> actors_;
112
113 DISALLOW_COPY_AND_ASSIGN(DiscreteTimeSimulation);
114 };
115
116 // Represents a web server in a simulation of a server under attack by
117 // a lot of clients. Must be added to the simulation's list of actors
118 // after all |Requester| objects.
119 class Server : public DiscreteTimeSimulation::Actor {
120 public:
Server(int max_queries_per_tick,double request_drop_ratio)121 Server(int max_queries_per_tick, double request_drop_ratio)
122 : max_queries_per_tick_(max_queries_per_tick),
123 request_drop_ratio_(request_drop_ratio),
124 num_overloaded_ticks_remaining_(0),
125 num_current_tick_queries_(0),
126 num_overloaded_ticks_(0),
127 max_experienced_queries_per_tick_(0),
128 mock_request_(context_.CreateRequest(GURL(),
129 DEFAULT_PRIORITY,
130 nullptr,
131 TRAFFIC_ANNOTATION_FOR_TESTS)) {}
132
SetDowntime(const TimeTicks & start_time,const TimeDelta & duration)133 void SetDowntime(const TimeTicks& start_time, const TimeDelta& duration) {
134 start_downtime_ = start_time;
135 end_downtime_ = start_time + duration;
136 }
137
AdvanceTime(const TimeTicks & absolute_time)138 void AdvanceTime(const TimeTicks& absolute_time) override {
139 now_ = absolute_time;
140 }
141
PerformAction()142 void PerformAction() override {
143 // We are inserted at the end of the actor's list, so all Requester
144 // instances have already done their bit.
145 if (num_current_tick_queries_ > max_experienced_queries_per_tick_)
146 max_experienced_queries_per_tick_ = num_current_tick_queries_;
147
148 if (num_current_tick_queries_ > max_queries_per_tick_) {
149 // We pretend the server fails for the next several ticks after it
150 // gets overloaded.
151 num_overloaded_ticks_remaining_ = 5;
152 ++num_overloaded_ticks_;
153 } else if (num_overloaded_ticks_remaining_ > 0) {
154 --num_overloaded_ticks_remaining_;
155 }
156
157 requests_per_tick_.push_back(num_current_tick_queries_);
158 num_current_tick_queries_ = 0;
159 }
160
161 // This is called by Requester. It returns the response code from
162 // the server.
HandleRequest()163 int HandleRequest() {
164 ++num_current_tick_queries_;
165 if (!start_downtime_.is_null() &&
166 start_downtime_ < now_ && now_ < end_downtime_) {
167 // For the simulation measuring the increase in perceived
168 // downtime, it might be interesting to count separately the
169 // queries seen by the server (assuming a front-end reverse proxy
170 // is what actually serves up the 503s in this case) so that we could
171 // visualize the traffic spike seen by the server when it comes up,
172 // which would in many situations be ameliorated by the anti-DDoS
173 // throttling.
174 return 503;
175 }
176
177 if ((num_overloaded_ticks_remaining_ > 0 ||
178 num_current_tick_queries_ > max_queries_per_tick_) &&
179 base::RandDouble() < request_drop_ratio_) {
180 return 503;
181 }
182
183 return 200;
184 }
185
num_overloaded_ticks() const186 int num_overloaded_ticks() const {
187 return num_overloaded_ticks_;
188 }
189
max_experienced_queries_per_tick() const190 int max_experienced_queries_per_tick() const {
191 return max_experienced_queries_per_tick_;
192 }
193
mock_request() const194 const URLRequest& mock_request() const {
195 return *mock_request_.get();
196 }
197
VisualizeASCII(int terminal_width)198 std::string VisualizeASCII(int terminal_width) {
199 // Account for | characters we place at left of graph.
200 terminal_width -= 1;
201
202 VerboseOut("Overloaded for %d of %d ticks.\n",
203 num_overloaded_ticks_, requests_per_tick_.size());
204 VerboseOut("Got maximum of %d requests in a tick.\n\n",
205 max_experienced_queries_per_tick_);
206
207 VerboseOut("Traffic graph:\n\n");
208
209 // Printing the graph like this is a bit overkill, but was very useful
210 // while developing the various simulations to see if they were testing
211 // the corner cases we want to simulate.
212
213 // Find the smallest number of whole ticks we need to group into a
214 // column that will let all ticks fit into the column width we have.
215 int num_ticks = requests_per_tick_.size();
216 double ticks_per_column_exact =
217 static_cast<double>(num_ticks) / static_cast<double>(terminal_width);
218 int ticks_per_column = std::ceil(ticks_per_column_exact);
219 DCHECK_GE(ticks_per_column * terminal_width, num_ticks);
220
221 // Sum up the column values.
222 int num_columns = num_ticks / ticks_per_column;
223 if (num_ticks % ticks_per_column)
224 ++num_columns;
225 DCHECK_LE(num_columns, terminal_width);
226 std::unique_ptr<int[]> columns(new int[num_columns]);
227 for (int tx = 0; tx < num_ticks; ++tx) {
228 int cx = tx / ticks_per_column;
229 if (tx % ticks_per_column == 0)
230 columns[cx] = 0;
231 columns[cx] += requests_per_tick_[tx];
232 }
233
234 // Find the lowest integer divisor that will let the column values
235 // be represented in a graph of maximum height 50.
236 int max_value = 0;
237 for (int cx = 0; cx < num_columns; ++cx)
238 max_value = std::max(max_value, columns[cx]);
239 const int kNumRows = 50;
240 double row_divisor_exact = max_value / static_cast<double>(kNumRows);
241 int row_divisor = std::ceil(row_divisor_exact);
242 DCHECK_GE(row_divisor * kNumRows, max_value);
243
244 // To show the overload line, we calculate the appropriate value.
245 int overload_value = max_queries_per_tick_ * ticks_per_column;
246
247 // When num_ticks is not a whole multiple of ticks_per_column, the last
248 // column includes fewer ticks than the others. In this case, don't
249 // print it so that we don't show an inconsistent value.
250 int num_printed_columns = num_columns;
251 if (num_ticks % ticks_per_column)
252 --num_printed_columns;
253
254 // This is a top-to-bottom traversal of rows, left-to-right per row.
255 std::string output;
256 for (int rx = 0; rx < kNumRows; ++rx) {
257 int range_min = (kNumRows - rx) * row_divisor;
258 int range_max = range_min + row_divisor;
259 if (range_min == 0)
260 range_min = -1; // Make 0 values fit in the bottom range.
261 output.append("|");
262 for (int cx = 0; cx < num_printed_columns; ++cx) {
263 char block = ' ';
264 // Show the overload line.
265 if (range_min < overload_value && overload_value <= range_max)
266 block = '-';
267
268 // Preferentially, show the graph line.
269 if (range_min < columns[cx] && columns[cx] <= range_max)
270 block = '#';
271
272 output.append(1, block);
273 }
274 output.append("\n");
275 }
276 output.append("|");
277 output.append(num_printed_columns, '=');
278
279 return output;
280 }
281
context() const282 const URLRequestContext& context() const { return context_; }
283
284 private:
285 TimeTicks now_;
286 TimeTicks start_downtime_; // Can be 0 to say "no downtime".
287 TimeTicks end_downtime_;
288 const int max_queries_per_tick_;
289 const double request_drop_ratio_; // Ratio of requests to 503 when failing.
290 int num_overloaded_ticks_remaining_;
291 int num_current_tick_queries_;
292 int num_overloaded_ticks_;
293 int max_experienced_queries_per_tick_;
294 std::vector<int> requests_per_tick_;
295
296 TestURLRequestContext context_;
297 std::unique_ptr<URLRequest> mock_request_;
298
299 DISALLOW_COPY_AND_ASSIGN(Server);
300 };
301
302 // Mock throttler entry used by Requester class.
303 class MockURLRequestThrottlerEntry : public URLRequestThrottlerEntry {
304 public:
MockURLRequestThrottlerEntry(URLRequestThrottlerManager * manager)305 explicit MockURLRequestThrottlerEntry(URLRequestThrottlerManager* manager)
306 : URLRequestThrottlerEntry(manager, std::string()),
307 backoff_entry_(&backoff_policy_, &fake_clock_) {}
308
GetBackoffEntry() const309 const BackoffEntry* GetBackoffEntry() const override {
310 return &backoff_entry_;
311 }
312
GetBackoffEntry()313 BackoffEntry* GetBackoffEntry() override { return &backoff_entry_; }
314
ImplGetTimeNow() const315 TimeTicks ImplGetTimeNow() const override { return fake_clock_.NowTicks(); }
316
SetFakeNow(const TimeTicks & fake_time)317 void SetFakeNow(const TimeTicks& fake_time) {
318 fake_clock_.set_now(fake_time);
319 }
320
321 protected:
322 ~MockURLRequestThrottlerEntry() override = default;
323
324 private:
325 mutable TestTickClock fake_clock_;
326 BackoffEntry backoff_entry_;
327 };
328
329 // Registry of results for a class of |Requester| objects (e.g. attackers vs.
330 // regular clients).
331 class RequesterResults {
332 public:
RequesterResults()333 RequesterResults()
334 : num_attempts_(0), num_successful_(0), num_failed_(0), num_blocked_(0) {
335 }
336
AddSuccess()337 void AddSuccess() {
338 ++num_attempts_;
339 ++num_successful_;
340 }
341
AddFailure()342 void AddFailure() {
343 ++num_attempts_;
344 ++num_failed_;
345 }
346
AddBlocked()347 void AddBlocked() {
348 ++num_attempts_;
349 ++num_blocked_;
350 }
351
num_attempts() const352 int num_attempts() const { return num_attempts_; }
num_successful() const353 int num_successful() const { return num_successful_; }
num_failed() const354 int num_failed() const { return num_failed_; }
num_blocked() const355 int num_blocked() const { return num_blocked_; }
356
GetBlockedRatio()357 double GetBlockedRatio() {
358 DCHECK(num_attempts_);
359 return static_cast<double>(num_blocked_) /
360 static_cast<double>(num_attempts_);
361 }
362
GetSuccessRatio()363 double GetSuccessRatio() {
364 DCHECK(num_attempts_);
365 return static_cast<double>(num_successful_) /
366 static_cast<double>(num_attempts_);
367 }
368
PrintResults(const char * class_description)369 void PrintResults(const char* class_description) {
370 if (num_attempts_ == 0) {
371 VerboseOut("No data for %s\n", class_description);
372 return;
373 }
374
375 VerboseOut("Requester results for %s\n", class_description);
376 VerboseOut(" %d attempts\n", num_attempts_);
377 VerboseOut(" %d successes\n", num_successful_);
378 VerboseOut(" %d 5xx responses\n", num_failed_);
379 VerboseOut(" %d requests blocked\n", num_blocked_);
380 VerboseOut(" %.2f success ratio\n", GetSuccessRatio());
381 VerboseOut(" %.2f blocked ratio\n", GetBlockedRatio());
382 VerboseOut("\n");
383 }
384
385 private:
386 int num_attempts_;
387 int num_successful_;
388 int num_failed_;
389 int num_blocked_;
390 };
391
392 // Represents an Requester in a simulated DDoS situation, that periodically
393 // requests a specific resource.
394 class Requester : public DiscreteTimeSimulation::Actor {
395 public:
Requester(MockURLRequestThrottlerEntry * throttler_entry,const TimeDelta & time_between_requests,Server * server,RequesterResults * results)396 Requester(MockURLRequestThrottlerEntry* throttler_entry,
397 const TimeDelta& time_between_requests,
398 Server* server,
399 RequesterResults* results)
400 : throttler_entry_(throttler_entry),
401 time_between_requests_(time_between_requests),
402 last_attempt_was_failure_(false),
403 server_(server),
404 results_(results) {
405 DCHECK(server_);
406 }
407
AdvanceTime(const TimeTicks & absolute_time)408 void AdvanceTime(const TimeTicks& absolute_time) override {
409 if (time_of_last_success_.is_null())
410 time_of_last_success_ = absolute_time;
411
412 throttler_entry_->SetFakeNow(absolute_time);
413 }
414
PerformAction()415 void PerformAction() override {
416 const TimeDelta current_jitter = request_jitter_ * base::RandDouble();
417 const TimeDelta effective_delay =
418 time_between_requests_ +
419 (base::RandInt(0, 1) ? -current_jitter : current_jitter);
420
421 if (throttler_entry_->ImplGetTimeNow() - time_of_last_attempt_ >
422 effective_delay) {
423 if (!throttler_entry_->ShouldRejectRequest(server_->mock_request())) {
424 int status_code = server_->HandleRequest();
425 throttler_entry_->UpdateWithResponse(status_code);
426
427 if (status_code == 200) {
428 if (results_)
429 results_->AddSuccess();
430
431 if (last_attempt_was_failure_) {
432 last_downtime_duration_ =
433 throttler_entry_->ImplGetTimeNow() - time_of_last_success_;
434 }
435
436 time_of_last_success_ = throttler_entry_->ImplGetTimeNow();
437 } else if (results_) {
438 results_->AddFailure();
439 }
440 last_attempt_was_failure_ = status_code != 200;
441 } else {
442 if (results_)
443 results_->AddBlocked();
444 last_attempt_was_failure_ = true;
445 }
446
447 time_of_last_attempt_ = throttler_entry_->ImplGetTimeNow();
448 }
449 }
450
451 // Adds a delay until the first request, equal to a uniformly distributed
452 // value between now and now + max_delay.
SetStartupJitter(const TimeDelta & max_delay)453 void SetStartupJitter(const TimeDelta& max_delay) {
454 int delay_ms = base::RandInt(0, max_delay.InMilliseconds());
455 time_of_last_attempt_ = TimeTicks() +
456 TimeDelta::FromMilliseconds(delay_ms) - time_between_requests_;
457 }
458
SetRequestJitter(const TimeDelta & request_jitter)459 void SetRequestJitter(const TimeDelta& request_jitter) {
460 request_jitter_ = request_jitter;
461 }
462
last_downtime_duration() const463 TimeDelta last_downtime_duration() const { return last_downtime_duration_; }
464
465 private:
466 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry_;
467 const TimeDelta time_between_requests_;
468 TimeDelta request_jitter_;
469 TimeTicks time_of_last_attempt_;
470 TimeTicks time_of_last_success_;
471 bool last_attempt_was_failure_;
472 TimeDelta last_downtime_duration_;
473 Server* const server_;
474 RequesterResults* const results_; // May be NULL.
475
476 DISALLOW_COPY_AND_ASSIGN(Requester);
477 };
478
SimulateAttack(Server * server,RequesterResults * attacker_results,RequesterResults * client_results,bool enable_throttling)479 void SimulateAttack(Server* server,
480 RequesterResults* attacker_results,
481 RequesterResults* client_results,
482 bool enable_throttling) {
483 const size_t kNumAttackers = 50;
484 const size_t kNumClients = 50;
485 DiscreteTimeSimulation simulation;
486 URLRequestThrottlerManager manager;
487 std::vector<std::unique_ptr<Requester>> requesters;
488 for (size_t i = 0; i < kNumAttackers; ++i) {
489 // Use a tiny time_between_requests so the attackers will ping the
490 // server at every tick of the simulation.
491 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
492 new MockURLRequestThrottlerEntry(&manager));
493 if (!enable_throttling)
494 throttler_entry->DisableBackoffThrottling();
495
496 std::unique_ptr<Requester> attacker(
497 new Requester(throttler_entry.get(), TimeDelta::FromMilliseconds(1),
498 server, attacker_results));
499 attacker->SetStartupJitter(TimeDelta::FromSeconds(120));
500 simulation.AddActor(attacker.get());
501 requesters.push_back(std::move(attacker));
502 }
503 for (size_t i = 0; i < kNumClients; ++i) {
504 // Normal clients only make requests every 2 minutes, plus/minus 1 minute.
505 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
506 new MockURLRequestThrottlerEntry(&manager));
507 if (!enable_throttling)
508 throttler_entry->DisableBackoffThrottling();
509
510 std::unique_ptr<Requester> client(new Requester(throttler_entry.get(),
511 TimeDelta::FromMinutes(2),
512 server, client_results));
513 client->SetStartupJitter(TimeDelta::FromSeconds(120));
514 client->SetRequestJitter(TimeDelta::FromMinutes(1));
515 simulation.AddActor(client.get());
516 requesters.push_back(std::move(client));
517 }
518 simulation.AddActor(server);
519
520 simulation.RunSimulation(TimeDelta::FromMinutes(6),
521 TimeDelta::FromSeconds(1));
522 }
523
TEST(URLRequestThrottlerSimulation,HelpsInAttack)524 TEST(URLRequestThrottlerSimulation, HelpsInAttack) {
525 base::test::TaskEnvironment task_environment;
526
527 Server unprotected_server(30, 1.0);
528 RequesterResults unprotected_attacker_results;
529 RequesterResults unprotected_client_results;
530 Server protected_server(30, 1.0);
531 RequesterResults protected_attacker_results;
532 RequesterResults protected_client_results;
533 SimulateAttack(&unprotected_server,
534 &unprotected_attacker_results,
535 &unprotected_client_results,
536 false);
537 SimulateAttack(&protected_server,
538 &protected_attacker_results,
539 &protected_client_results,
540 true);
541
542 // These assert that the DDoS protection actually benefits the
543 // server. Manual inspection of the traffic graphs will show this
544 // even more clearly.
545 EXPECT_GT(unprotected_server.num_overloaded_ticks(),
546 protected_server.num_overloaded_ticks());
547 EXPECT_GT(unprotected_server.max_experienced_queries_per_tick(),
548 protected_server.max_experienced_queries_per_tick());
549
550 // These assert that the DDoS protection actually benefits non-malicious
551 // (and non-degenerate/accidentally DDoSing) users.
552 EXPECT_LT(protected_client_results.GetBlockedRatio(),
553 protected_attacker_results.GetBlockedRatio());
554 EXPECT_GT(protected_client_results.GetSuccessRatio(),
555 unprotected_client_results.GetSuccessRatio());
556
557 // The rest is just for optional manual evaluation of the results;
558 // in particular the traffic pattern is interesting.
559
560 VerboseOut("\nUnprotected server's results:\n\n");
561 VerboseOut(unprotected_server.VisualizeASCII(132).c_str());
562 VerboseOut("\n\n");
563 VerboseOut("Protected server's results:\n\n");
564 VerboseOut(protected_server.VisualizeASCII(132).c_str());
565 VerboseOut("\n\n");
566
567 unprotected_attacker_results.PrintResults(
568 "attackers attacking unprotected server.");
569 unprotected_client_results.PrintResults(
570 "normal clients making requests to unprotected server.");
571 protected_attacker_results.PrintResults(
572 "attackers attacking protected server.");
573 protected_client_results.PrintResults(
574 "normal clients making requests to protected server.");
575 }
576
577 // Returns the downtime perceived by the client, as a ratio of the
578 // actual downtime.
SimulateDowntime(const TimeDelta & duration,const TimeDelta & average_client_interval,bool enable_throttling)579 double SimulateDowntime(const TimeDelta& duration,
580 const TimeDelta& average_client_interval,
581 bool enable_throttling) {
582 TimeDelta time_between_ticks = duration / 200;
583 TimeTicks start_downtime = TimeTicks() + (duration / 2);
584
585 // A server that never rejects requests, but will go down for maintenance.
586 Server server(std::numeric_limits<int>::max(), 1.0);
587 server.SetDowntime(start_downtime, duration);
588
589 URLRequestThrottlerManager manager;
590 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
591 new MockURLRequestThrottlerEntry(&manager));
592 if (!enable_throttling)
593 throttler_entry->DisableBackoffThrottling();
594
595 Requester requester(throttler_entry.get(), average_client_interval, &server,
596 nullptr);
597 requester.SetStartupJitter(duration / 3);
598 requester.SetRequestJitter(average_client_interval);
599
600 DiscreteTimeSimulation simulation;
601 simulation.AddActor(&requester);
602 simulation.AddActor(&server);
603
604 simulation.RunSimulation(duration * 2, time_between_ticks);
605
606 return static_cast<double>(
607 requester.last_downtime_duration().InMilliseconds()) /
608 static_cast<double>(duration.InMilliseconds());
609 }
610
TEST(URLRequestThrottlerSimulation,PerceivedDowntimeRatio)611 TEST(URLRequestThrottlerSimulation, PerceivedDowntimeRatio) {
612 base::test::TaskEnvironment task_environment;
613
614 struct Stats {
615 // Expected interval that we expect the ratio of downtime when anti-DDoS
616 // is enabled and downtime when anti-DDoS is not enabled to fall within.
617 //
618 // The expected interval depends on two things: The exponential back-off
619 // policy encoded in URLRequestThrottlerEntry, and the test or set of
620 // tests that the Stats object is tracking (e.g. a test where the client
621 // retries very rapidly on a very long downtime will tend to increase the
622 // number).
623 //
624 // To determine an appropriate new interval when parameters have changed,
625 // run the test a few times (you may have to Ctrl-C out of it after a few
626 // seconds) and choose an interval that the test converges quickly and
627 // reliably to. Then set the new interval, and run the test e.g. 20 times
628 // in succession to make sure it never takes an obscenely long time to
629 // converge to this interval.
630 double expected_min_increase;
631 double expected_max_increase;
632
633 size_t num_runs;
634 double total_ratio_unprotected;
635 double total_ratio_protected;
636
637 bool DidConverge(double* increase_ratio_out) {
638 double unprotected_ratio = total_ratio_unprotected / num_runs;
639 double protected_ratio = total_ratio_protected / num_runs;
640 double increase_ratio = protected_ratio / unprotected_ratio;
641 if (increase_ratio_out)
642 *increase_ratio_out = increase_ratio;
643 return expected_min_increase <= increase_ratio &&
644 increase_ratio <= expected_max_increase;
645 }
646
647 void ReportTrialResult(double increase_ratio) {
648 VerboseOut(
649 " Perceived downtime with throttling is %.4f times without.\n",
650 increase_ratio);
651 VerboseOut(" Test result after %d trials.\n", num_runs);
652 }
653 };
654
655 Stats global_stats = { 1.08, 1.15 };
656
657 struct Trial {
658 TimeDelta duration;
659 TimeDelta average_client_interval;
660 Stats stats;
661
662 void PrintTrialDescription() {
663 const double duration_minutes =
664 duration / base::TimeDelta::FromMinutes(1);
665 const double interval_minutes =
666 average_client_interval / base::TimeDelta::FromMinutes(1);
667 VerboseOut("Trial with %.2f min downtime, avg. interval %.2f min.\n",
668 duration_minutes, interval_minutes);
669 }
670 };
671
672 // We don't set or check expected ratio intervals on individual
673 // experiments as this might make the test too fragile, but we
674 // print them out at the end for manual evaluation (we want to be
675 // able to make claims about the expected ratios depending on the
676 // type of behavior of the client and the downtime, e.g. the difference
677 // in behavior between a client making requests every few minutes vs.
678 // one that makes a request every 15 seconds).
679 Trial trials[] = {
680 { TimeDelta::FromSeconds(10), TimeDelta::FromSeconds(3) },
681 { TimeDelta::FromSeconds(30), TimeDelta::FromSeconds(7) },
682 { TimeDelta::FromMinutes(5), TimeDelta::FromSeconds(30) },
683 { TimeDelta::FromMinutes(10), TimeDelta::FromSeconds(20) },
684 { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(15) },
685 { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(50) },
686 { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(2) },
687 { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(5) },
688 { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(7) },
689 { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(2) },
690 { TimeDelta::FromMinutes(40), TimeDelta::FromSeconds(15) },
691 { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(7) },
692 { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(2) },
693 { TimeDelta::FromMinutes(60), TimeDelta::FromSeconds(15) },
694 { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(20) },
695 { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(3) },
696 { TimeDelta::FromMinutes(80), TimeDelta::FromSeconds(15) },
697
698 // Most brutal?
699 { TimeDelta::FromMinutes(45), TimeDelta::FromMilliseconds(500) },
700 };
701
702 // If things don't converge by the time we've done 100K trials, then
703 // clearly one or more of the expected intervals are wrong.
704 while (global_stats.num_runs < 100000) {
705 for (size_t i = 0; i < base::size(trials); ++i) {
706 ++global_stats.num_runs;
707 ++trials[i].stats.num_runs;
708 double ratio_unprotected = SimulateDowntime(
709 trials[i].duration, trials[i].average_client_interval, false);
710 double ratio_protected = SimulateDowntime(
711 trials[i].duration, trials[i].average_client_interval, true);
712 global_stats.total_ratio_unprotected += ratio_unprotected;
713 global_stats.total_ratio_protected += ratio_protected;
714 trials[i].stats.total_ratio_unprotected += ratio_unprotected;
715 trials[i].stats.total_ratio_protected += ratio_protected;
716 }
717
718 double increase_ratio;
719 if (global_stats.DidConverge(&increase_ratio))
720 break;
721
722 if (global_stats.num_runs > 200) {
723 VerboseOut("Test has not yet converged on expected interval.\n");
724 global_stats.ReportTrialResult(increase_ratio);
725 }
726 }
727
728 double average_increase_ratio;
729 EXPECT_TRUE(global_stats.DidConverge(&average_increase_ratio));
730
731 // Print individual trial results for optional manual evaluation.
732 double max_increase_ratio = 0.0;
733 for (size_t i = 0; i < base::size(trials); ++i) {
734 double increase_ratio;
735 trials[i].stats.DidConverge(&increase_ratio);
736 max_increase_ratio = std::max(max_increase_ratio, increase_ratio);
737 trials[i].PrintTrialDescription();
738 trials[i].stats.ReportTrialResult(increase_ratio);
739 }
740
741 VerboseOut("Average increase ratio was %.4f\n", average_increase_ratio);
742 VerboseOut("Maximum increase ratio was %.4f\n", max_increase_ratio);
743 }
744
745 } // namespace
746 } // namespace net
747