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