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 <vector> 18 19 #include "base/environment.h" 20 #include "base/memory/scoped_ptr.h" 21 #include "base/memory/scoped_vector.h" 22 #include "base/rand_util.h" 23 #include "base/time/time.h" 24 #include "net/base/request_priority.h" 25 #include "net/url_request/url_request.h" 26 #include "net/url_request/url_request_context.h" 27 #include "net/url_request/url_request_test_util.h" 28 #include "net/url_request/url_request_throttler_manager.h" 29 #include "net/url_request/url_request_throttler_test_support.h" 30 #include "testing/gtest/include/gtest/gtest.h" 31 32 using base::TimeDelta; 33 using base::TimeTicks; 34 35 namespace net { 36 namespace { 37 38 // Set this variable in your environment if you want to see verbose results 39 // of the simulation tests. 40 const char kShowSimulationVariableName[] = "SHOW_SIMULATION_RESULTS"; 41 42 // Prints output only if a given environment variable is set. We use this 43 // to not print any output for human evaluation when the test is run without 44 // supervision. 45 void VerboseOut(const char* format, ...) { 46 static bool have_checked_environment = false; 47 static bool should_print = false; 48 if (!have_checked_environment) { 49 have_checked_environment = true; 50 scoped_ptr<base::Environment> env(base::Environment::Create()); 51 if (env->HasVar(kShowSimulationVariableName)) 52 should_print = true; 53 } 54 55 if (should_print) { 56 va_list arglist; 57 va_start(arglist, format); 58 vprintf(format, arglist); 59 va_end(arglist); 60 } 61 } 62 63 // A simple two-phase discrete time simulation. Actors are added in the order 64 // they should take action at every tick of the clock. Ticks of the clock 65 // are two-phase: 66 // - Phase 1 advances every actor's time to a new absolute time. 67 // - Phase 2 asks each actor to perform their action. 68 class DiscreteTimeSimulation { 69 public: 70 class Actor { 71 public: 72 virtual ~Actor() {} 73 virtual void AdvanceTime(const TimeTicks& absolute_time) = 0; 74 virtual void PerformAction() = 0; 75 }; 76 77 DiscreteTimeSimulation() {} 78 79 // Adds an |actor| to the simulation. The client of the simulation maintains 80 // ownership of |actor| and must ensure its lifetime exceeds that of the 81 // simulation. Actors should be added in the order you wish for them to 82 // act at each tick of the simulation. 83 void AddActor(Actor* actor) { 84 actors_.push_back(actor); 85 } 86 87 // Runs the simulation for, pretending |time_between_ticks| passes from one 88 // tick to the next. The start time will be the current real time. The 89 // simulation will stop when the simulated duration is equal to or greater 90 // than |maximum_simulated_duration|. 91 void RunSimulation(const TimeDelta& maximum_simulated_duration, 92 const TimeDelta& time_between_ticks) { 93 TimeTicks start_time = TimeTicks(); 94 TimeTicks now = start_time; 95 while ((now - start_time) <= maximum_simulated_duration) { 96 for (std::vector<Actor*>::iterator it = actors_.begin(); 97 it != actors_.end(); 98 ++it) { 99 (*it)->AdvanceTime(now); 100 } 101 102 for (std::vector<Actor*>::iterator it = actors_.begin(); 103 it != actors_.end(); 104 ++it) { 105 (*it)->PerformAction(); 106 } 107 108 now += time_between_ticks; 109 } 110 } 111 112 private: 113 std::vector<Actor*> actors_; 114 115 DISALLOW_COPY_AND_ASSIGN(DiscreteTimeSimulation); 116 }; 117 118 // Represents a web server in a simulation of a server under attack by 119 // a lot of clients. Must be added to the simulation's list of actors 120 // after all |Requester| objects. 121 class Server : public DiscreteTimeSimulation::Actor { 122 public: 123 Server(int max_queries_per_tick, double request_drop_ratio) 124 : max_queries_per_tick_(max_queries_per_tick), 125 request_drop_ratio_(request_drop_ratio), 126 num_overloaded_ticks_remaining_(0), 127 num_current_tick_queries_(0), 128 num_overloaded_ticks_(0), 129 max_experienced_queries_per_tick_(0), 130 mock_request_(context_.CreateRequest( 131 GURL(), DEFAULT_PRIORITY, NULL, NULL)) {} 132 133 void SetDowntime(const TimeTicks& start_time, const TimeDelta& duration) { 134 start_downtime_ = start_time; 135 end_downtime_ = start_time + duration; 136 } 137 138 virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE { 139 now_ = absolute_time; 140 } 141 142 virtual 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. 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 186 int num_overloaded_ticks() const { 187 return num_overloaded_ticks_; 188 } 189 190 int max_experienced_queries_per_tick() const { 191 return max_experienced_queries_per_tick_; 192 } 193 194 const URLRequest& mock_request() const { 195 return *mock_request_.get(); 196 } 197 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 scoped_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 282 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 scoped_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: 305 explicit MockURLRequestThrottlerEntry(URLRequestThrottlerManager* manager) 306 : URLRequestThrottlerEntry(manager, std::string()), 307 mock_backoff_entry_(&backoff_policy_) {} 308 309 virtual const BackoffEntry* GetBackoffEntry() const OVERRIDE { 310 return &mock_backoff_entry_; 311 } 312 313 virtual BackoffEntry* GetBackoffEntry() OVERRIDE { 314 return &mock_backoff_entry_; 315 } 316 317 virtual TimeTicks ImplGetTimeNow() const OVERRIDE { 318 return fake_now_; 319 } 320 321 void SetFakeNow(const TimeTicks& fake_time) { 322 fake_now_ = fake_time; 323 mock_backoff_entry_.set_fake_now(fake_time); 324 } 325 326 TimeTicks fake_now() const { 327 return fake_now_; 328 } 329 330 protected: 331 virtual ~MockURLRequestThrottlerEntry() {} 332 333 private: 334 TimeTicks fake_now_; 335 MockBackoffEntry mock_backoff_entry_; 336 }; 337 338 // Registry of results for a class of |Requester| objects (e.g. attackers vs. 339 // regular clients). 340 class RequesterResults { 341 public: 342 RequesterResults() 343 : num_attempts_(0), num_successful_(0), num_failed_(0), num_blocked_(0) { 344 } 345 346 void AddSuccess() { 347 ++num_attempts_; 348 ++num_successful_; 349 } 350 351 void AddFailure() { 352 ++num_attempts_; 353 ++num_failed_; 354 } 355 356 void AddBlocked() { 357 ++num_attempts_; 358 ++num_blocked_; 359 } 360 361 int num_attempts() const { return num_attempts_; } 362 int num_successful() const { return num_successful_; } 363 int num_failed() const { return num_failed_; } 364 int num_blocked() const { return num_blocked_; } 365 366 double GetBlockedRatio() { 367 DCHECK(num_attempts_); 368 return static_cast<double>(num_blocked_) / 369 static_cast<double>(num_attempts_); 370 } 371 372 double GetSuccessRatio() { 373 DCHECK(num_attempts_); 374 return static_cast<double>(num_successful_) / 375 static_cast<double>(num_attempts_); 376 } 377 378 void PrintResults(const char* class_description) { 379 if (num_attempts_ == 0) { 380 VerboseOut("No data for %s\n", class_description); 381 return; 382 } 383 384 VerboseOut("Requester results for %s\n", class_description); 385 VerboseOut(" %d attempts\n", num_attempts_); 386 VerboseOut(" %d successes\n", num_successful_); 387 VerboseOut(" %d 5xx responses\n", num_failed_); 388 VerboseOut(" %d requests blocked\n", num_blocked_); 389 VerboseOut(" %.2f success ratio\n", GetSuccessRatio()); 390 VerboseOut(" %.2f blocked ratio\n", GetBlockedRatio()); 391 VerboseOut("\n"); 392 } 393 394 private: 395 int num_attempts_; 396 int num_successful_; 397 int num_failed_; 398 int num_blocked_; 399 }; 400 401 // Represents an Requester in a simulated DDoS situation, that periodically 402 // requests a specific resource. 403 class Requester : public DiscreteTimeSimulation::Actor { 404 public: 405 Requester(MockURLRequestThrottlerEntry* throttler_entry, 406 const TimeDelta& time_between_requests, 407 Server* server, 408 RequesterResults* results) 409 : throttler_entry_(throttler_entry), 410 time_between_requests_(time_between_requests), 411 last_attempt_was_failure_(false), 412 server_(server), 413 results_(results) { 414 DCHECK(server_); 415 } 416 417 virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE { 418 if (time_of_last_success_.is_null()) 419 time_of_last_success_ = absolute_time; 420 421 throttler_entry_->SetFakeNow(absolute_time); 422 } 423 424 virtual void PerformAction() OVERRIDE { 425 TimeDelta effective_delay = time_between_requests_; 426 TimeDelta current_jitter = TimeDelta::FromMilliseconds( 427 request_jitter_.InMilliseconds() * base::RandDouble()); 428 if (base::RandInt(0, 1)) { 429 effective_delay -= current_jitter; 430 } else { 431 effective_delay += current_jitter; 432 } 433 434 if (throttler_entry_->fake_now() - time_of_last_attempt_ > 435 effective_delay) { 436 if (!throttler_entry_->ShouldRejectRequest( 437 server_->mock_request(), 438 server_->context().network_delegate())) { 439 int status_code = server_->HandleRequest(); 440 MockURLRequestThrottlerHeaderAdapter response_headers(status_code); 441 throttler_entry_->UpdateWithResponse(std::string(), &response_headers); 442 443 if (status_code == 200) { 444 if (results_) 445 results_->AddSuccess(); 446 447 if (last_attempt_was_failure_) { 448 last_downtime_duration_ = 449 throttler_entry_->fake_now() - time_of_last_success_; 450 } 451 452 time_of_last_success_ = throttler_entry_->fake_now(); 453 last_attempt_was_failure_ = false; 454 } else { 455 if (results_) 456 results_->AddFailure(); 457 last_attempt_was_failure_ = true; 458 } 459 } else { 460 if (results_) 461 results_->AddBlocked(); 462 last_attempt_was_failure_ = true; 463 } 464 465 time_of_last_attempt_ = throttler_entry_->fake_now(); 466 } 467 } 468 469 // Adds a delay until the first request, equal to a uniformly distributed 470 // value between now and now + max_delay. 471 void SetStartupJitter(const TimeDelta& max_delay) { 472 int delay_ms = base::RandInt(0, max_delay.InMilliseconds()); 473 time_of_last_attempt_ = TimeTicks() + 474 TimeDelta::FromMilliseconds(delay_ms) - time_between_requests_; 475 } 476 477 void SetRequestJitter(const TimeDelta& request_jitter) { 478 request_jitter_ = request_jitter; 479 } 480 481 TimeDelta last_downtime_duration() const { return last_downtime_duration_; } 482 483 private: 484 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry_; 485 const TimeDelta time_between_requests_; 486 TimeDelta request_jitter_; 487 TimeTicks time_of_last_attempt_; 488 TimeTicks time_of_last_success_; 489 bool last_attempt_was_failure_; 490 TimeDelta last_downtime_duration_; 491 Server* const server_; 492 RequesterResults* const results_; // May be NULL. 493 494 DISALLOW_COPY_AND_ASSIGN(Requester); 495 }; 496 497 void SimulateAttack(Server* server, 498 RequesterResults* attacker_results, 499 RequesterResults* client_results, 500 bool enable_throttling) { 501 const size_t kNumAttackers = 50; 502 const size_t kNumClients = 50; 503 DiscreteTimeSimulation simulation; 504 URLRequestThrottlerManager manager; 505 ScopedVector<Requester> requesters; 506 for (size_t i = 0; i < kNumAttackers; ++i) { 507 // Use a tiny time_between_requests so the attackers will ping the 508 // server at every tick of the simulation. 509 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry( 510 new MockURLRequestThrottlerEntry(&manager)); 511 if (!enable_throttling) 512 throttler_entry->DisableBackoffThrottling(); 513 514 Requester* attacker = new Requester(throttler_entry.get(), 515 TimeDelta::FromMilliseconds(1), 516 server, 517 attacker_results); 518 attacker->SetStartupJitter(TimeDelta::FromSeconds(120)); 519 requesters.push_back(attacker); 520 simulation.AddActor(attacker); 521 } 522 for (size_t i = 0; i < kNumClients; ++i) { 523 // Normal clients only make requests every 2 minutes, plus/minus 1 minute. 524 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry( 525 new MockURLRequestThrottlerEntry(&manager)); 526 if (!enable_throttling) 527 throttler_entry->DisableBackoffThrottling(); 528 529 Requester* client = new Requester(throttler_entry.get(), 530 TimeDelta::FromMinutes(2), 531 server, 532 client_results); 533 client->SetStartupJitter(TimeDelta::FromSeconds(120)); 534 client->SetRequestJitter(TimeDelta::FromMinutes(1)); 535 requesters.push_back(client); 536 simulation.AddActor(client); 537 } 538 simulation.AddActor(server); 539 540 simulation.RunSimulation(TimeDelta::FromMinutes(6), 541 TimeDelta::FromSeconds(1)); 542 } 543 544 TEST(URLRequestThrottlerSimulation, HelpsInAttack) { 545 Server unprotected_server(30, 1.0); 546 RequesterResults unprotected_attacker_results; 547 RequesterResults unprotected_client_results; 548 Server protected_server(30, 1.0); 549 RequesterResults protected_attacker_results; 550 RequesterResults protected_client_results; 551 SimulateAttack(&unprotected_server, 552 &unprotected_attacker_results, 553 &unprotected_client_results, 554 false); 555 SimulateAttack(&protected_server, 556 &protected_attacker_results, 557 &protected_client_results, 558 true); 559 560 // These assert that the DDoS protection actually benefits the 561 // server. Manual inspection of the traffic graphs will show this 562 // even more clearly. 563 EXPECT_GT(unprotected_server.num_overloaded_ticks(), 564 protected_server.num_overloaded_ticks()); 565 EXPECT_GT(unprotected_server.max_experienced_queries_per_tick(), 566 protected_server.max_experienced_queries_per_tick()); 567 568 // These assert that the DDoS protection actually benefits non-malicious 569 // (and non-degenerate/accidentally DDoSing) users. 570 EXPECT_LT(protected_client_results.GetBlockedRatio(), 571 protected_attacker_results.GetBlockedRatio()); 572 EXPECT_GT(protected_client_results.GetSuccessRatio(), 573 unprotected_client_results.GetSuccessRatio()); 574 575 // The rest is just for optional manual evaluation of the results; 576 // in particular the traffic pattern is interesting. 577 578 VerboseOut("\nUnprotected server's results:\n\n"); 579 VerboseOut(unprotected_server.VisualizeASCII(132).c_str()); 580 VerboseOut("\n\n"); 581 VerboseOut("Protected server's results:\n\n"); 582 VerboseOut(protected_server.VisualizeASCII(132).c_str()); 583 VerboseOut("\n\n"); 584 585 unprotected_attacker_results.PrintResults( 586 "attackers attacking unprotected server."); 587 unprotected_client_results.PrintResults( 588 "normal clients making requests to unprotected server."); 589 protected_attacker_results.PrintResults( 590 "attackers attacking protected server."); 591 protected_client_results.PrintResults( 592 "normal clients making requests to protected server."); 593 } 594 595 // Returns the downtime perceived by the client, as a ratio of the 596 // actual downtime. 597 double SimulateDowntime(const TimeDelta& duration, 598 const TimeDelta& average_client_interval, 599 bool enable_throttling) { 600 TimeDelta time_between_ticks = duration / 200; 601 TimeTicks start_downtime = TimeTicks() + (duration / 2); 602 603 // A server that never rejects requests, but will go down for maintenance. 604 Server server(std::numeric_limits<int>::max(), 1.0); 605 server.SetDowntime(start_downtime, duration); 606 607 URLRequestThrottlerManager manager; 608 scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry( 609 new MockURLRequestThrottlerEntry(&manager)); 610 if (!enable_throttling) 611 throttler_entry->DisableBackoffThrottling(); 612 613 Requester requester( 614 throttler_entry.get(), average_client_interval, &server, NULL); 615 requester.SetStartupJitter(duration / 3); 616 requester.SetRequestJitter(average_client_interval); 617 618 DiscreteTimeSimulation simulation; 619 simulation.AddActor(&requester); 620 simulation.AddActor(&server); 621 622 simulation.RunSimulation(duration * 2, time_between_ticks); 623 624 return static_cast<double>( 625 requester.last_downtime_duration().InMilliseconds()) / 626 static_cast<double>(duration.InMilliseconds()); 627 } 628 629 TEST(URLRequestThrottlerSimulation, PerceivedDowntimeRatio) { 630 struct Stats { 631 // Expected interval that we expect the ratio of downtime when anti-DDoS 632 // is enabled and downtime when anti-DDoS is not enabled to fall within. 633 // 634 // The expected interval depends on two things: The exponential back-off 635 // policy encoded in URLRequestThrottlerEntry, and the test or set of 636 // tests that the Stats object is tracking (e.g. a test where the client 637 // retries very rapidly on a very long downtime will tend to increase the 638 // number). 639 // 640 // To determine an appropriate new interval when parameters have changed, 641 // run the test a few times (you may have to Ctrl-C out of it after a few 642 // seconds) and choose an interval that the test converges quickly and 643 // reliably to. Then set the new interval, and run the test e.g. 20 times 644 // in succession to make sure it never takes an obscenely long time to 645 // converge to this interval. 646 double expected_min_increase; 647 double expected_max_increase; 648 649 size_t num_runs; 650 double total_ratio_unprotected; 651 double total_ratio_protected; 652 653 bool DidConverge(double* increase_ratio_out) { 654 double unprotected_ratio = total_ratio_unprotected / num_runs; 655 double protected_ratio = total_ratio_protected / num_runs; 656 double increase_ratio = protected_ratio / unprotected_ratio; 657 if (increase_ratio_out) 658 *increase_ratio_out = increase_ratio; 659 return expected_min_increase <= increase_ratio && 660 increase_ratio <= expected_max_increase; 661 } 662 663 void ReportTrialResult(double increase_ratio) { 664 VerboseOut( 665 " Perceived downtime with throttling is %.4f times without.\n", 666 increase_ratio); 667 VerboseOut(" Test result after %d trials.\n", num_runs); 668 } 669 }; 670 671 Stats global_stats = { 1.08, 1.15 }; 672 673 struct Trial { 674 TimeDelta duration; 675 TimeDelta average_client_interval; 676 Stats stats; 677 678 void PrintTrialDescription() { 679 double duration_minutes = 680 static_cast<double>(duration.InSeconds()) / 60.0; 681 double interval_minutes = 682 static_cast<double>(average_client_interval.InSeconds()) / 60.0; 683 VerboseOut("Trial with %.2f min downtime, avg. interval %.2f min.\n", 684 duration_minutes, interval_minutes); 685 } 686 }; 687 688 // We don't set or check expected ratio intervals on individual 689 // experiments as this might make the test too fragile, but we 690 // print them out at the end for manual evaluation (we want to be 691 // able to make claims about the expected ratios depending on the 692 // type of behavior of the client and the downtime, e.g. the difference 693 // in behavior between a client making requests every few minutes vs. 694 // one that makes a request every 15 seconds). 695 Trial trials[] = { 696 { TimeDelta::FromSeconds(10), TimeDelta::FromSeconds(3) }, 697 { TimeDelta::FromSeconds(30), TimeDelta::FromSeconds(7) }, 698 { TimeDelta::FromMinutes(5), TimeDelta::FromSeconds(30) }, 699 { TimeDelta::FromMinutes(10), TimeDelta::FromSeconds(20) }, 700 { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(15) }, 701 { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(50) }, 702 { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(2) }, 703 { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(5) }, 704 { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(7) }, 705 { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(2) }, 706 { TimeDelta::FromMinutes(40), TimeDelta::FromSeconds(15) }, 707 { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(7) }, 708 { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(2) }, 709 { TimeDelta::FromMinutes(60), TimeDelta::FromSeconds(15) }, 710 { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(20) }, 711 { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(3) }, 712 { TimeDelta::FromMinutes(80), TimeDelta::FromSeconds(15) }, 713 714 // Most brutal? 715 { TimeDelta::FromMinutes(45), TimeDelta::FromMilliseconds(500) }, 716 }; 717 718 // If things don't converge by the time we've done 100K trials, then 719 // clearly one or more of the expected intervals are wrong. 720 while (global_stats.num_runs < 100000) { 721 for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) { 722 ++global_stats.num_runs; 723 ++trials[i].stats.num_runs; 724 double ratio_unprotected = SimulateDowntime( 725 trials[i].duration, trials[i].average_client_interval, false); 726 double ratio_protected = SimulateDowntime( 727 trials[i].duration, trials[i].average_client_interval, true); 728 global_stats.total_ratio_unprotected += ratio_unprotected; 729 global_stats.total_ratio_protected += ratio_protected; 730 trials[i].stats.total_ratio_unprotected += ratio_unprotected; 731 trials[i].stats.total_ratio_protected += ratio_protected; 732 } 733 734 double increase_ratio; 735 if (global_stats.DidConverge(&increase_ratio)) 736 break; 737 738 if (global_stats.num_runs > 200) { 739 VerboseOut("Test has not yet converged on expected interval.\n"); 740 global_stats.ReportTrialResult(increase_ratio); 741 } 742 } 743 744 double average_increase_ratio; 745 EXPECT_TRUE(global_stats.DidConverge(&average_increase_ratio)); 746 747 // Print individual trial results for optional manual evaluation. 748 double max_increase_ratio = 0.0; 749 for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) { 750 double increase_ratio; 751 trials[i].stats.DidConverge(&increase_ratio); 752 max_increase_ratio = std::max(max_increase_ratio, increase_ratio); 753 trials[i].PrintTrialDescription(); 754 trials[i].stats.ReportTrialResult(increase_ratio); 755 } 756 757 VerboseOut("Average increase ratio was %.4f\n", average_increase_ratio); 758 VerboseOut("Maximum increase ratio was %.4f\n", max_increase_ratio); 759 } 760 761 } // namespace 762 } // namespace net 763