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