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