url_request_throttler_simulation_unittest.cc 26 KB

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