This source file includes following definitions.
- VerboseOut
- AddActor
- RunSimulation
- mock_request_
- SetDowntime
- AdvanceTime
- PerformAction
- HandleRequest
- num_overloaded_ticks
- max_experienced_queries_per_tick
- mock_request
- VisualizeASCII
- mock_backoff_entry_
- GetBackoffEntry
- GetBackoffEntry
- ImplGetTimeNow
- SetFakeNow
- fake_now
- num_blocked_
- AddSuccess
- AddFailure
- AddBlocked
- num_attempts
- num_successful
- num_failed
- num_blocked
- GetBlockedRatio
- GetSuccessRatio
- PrintResults
- results_
- AdvanceTime
- PerformAction
- SetStartupJitter
- SetRequestJitter
- last_downtime_duration
- SimulateAttack
- TEST
- SimulateDowntime
- TEST
#include <cmath>
#include <limits>
#include <vector>
#include "base/environment.h"
#include "base/memory/scoped_vector.h"
#include "base/rand_util.h"
#include "base/time/time.h"
#include "net/base/request_priority.h"
#include "net/url_request/url_request_test_util.h"
#include "net/url_request/url_request_throttler_manager.h"
#include "net/url_request/url_request_throttler_test_support.h"
#include "testing/gtest/include/gtest/gtest.h"
using base::TimeDelta;
using base::TimeTicks;
namespace net {
namespace {
const char kShowSimulationVariableName[] = "SHOW_SIMULATION_RESULTS";
void VerboseOut(const char* format, ...) {
static bool have_checked_environment = false;
static bool should_print = false;
if (!have_checked_environment) {
have_checked_environment = true;
scoped_ptr<base::Environment> env(base::Environment::Create());
if (env->HasVar(kShowSimulationVariableName))
should_print = true;
}
if (should_print) {
va_list arglist;
va_start(arglist, format);
vprintf(format, arglist);
va_end(arglist);
}
}
class DiscreteTimeSimulation {
public:
class Actor {
public:
virtual ~Actor() {}
virtual void AdvanceTime(const TimeTicks& absolute_time) = 0;
virtual void PerformAction() = 0;
};
DiscreteTimeSimulation() {}
void AddActor(Actor* actor) {
actors_.push_back(actor);
}
void RunSimulation(const TimeDelta& maximum_simulated_duration,
const TimeDelta& time_between_ticks) {
TimeTicks start_time = TimeTicks();
TimeTicks now = start_time;
while ((now - start_time) <= maximum_simulated_duration) {
for (std::vector<Actor*>::iterator it = actors_.begin();
it != actors_.end();
++it) {
(*it)->AdvanceTime(now);
}
for (std::vector<Actor*>::iterator it = actors_.begin();
it != actors_.end();
++it) {
(*it)->PerformAction();
}
now += time_between_ticks;
}
}
private:
std::vector<Actor*> actors_;
DISALLOW_COPY_AND_ASSIGN(DiscreteTimeSimulation);
};
class Server : public DiscreteTimeSimulation::Actor {
public:
Server(int max_queries_per_tick, double request_drop_ratio)
: max_queries_per_tick_(max_queries_per_tick),
request_drop_ratio_(request_drop_ratio),
num_overloaded_ticks_remaining_(0),
num_current_tick_queries_(0),
num_overloaded_ticks_(0),
max_experienced_queries_per_tick_(0),
mock_request_(GURL(), DEFAULT_PRIORITY, NULL, &context_) {}
void SetDowntime(const TimeTicks& start_time, const TimeDelta& duration) {
start_downtime_ = start_time;
end_downtime_ = start_time + duration;
}
virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE {
now_ = absolute_time;
}
virtual void PerformAction() OVERRIDE {
if (num_current_tick_queries_ > max_experienced_queries_per_tick_)
max_experienced_queries_per_tick_ = num_current_tick_queries_;
if (num_current_tick_queries_ > max_queries_per_tick_) {
num_overloaded_ticks_remaining_ = 5;
++num_overloaded_ticks_;
} else if (num_overloaded_ticks_remaining_ > 0) {
--num_overloaded_ticks_remaining_;
}
requests_per_tick_.push_back(num_current_tick_queries_);
num_current_tick_queries_ = 0;
}
int HandleRequest() {
++num_current_tick_queries_;
if (!start_downtime_.is_null() &&
start_downtime_ < now_ && now_ < end_downtime_) {
return 503;
}
if ((num_overloaded_ticks_remaining_ > 0 ||
num_current_tick_queries_ > max_queries_per_tick_) &&
base::RandDouble() < request_drop_ratio_) {
return 503;
}
return 200;
}
int num_overloaded_ticks() const {
return num_overloaded_ticks_;
}
int max_experienced_queries_per_tick() const {
return max_experienced_queries_per_tick_;
}
const URLRequest& mock_request() const {
return mock_request_;
}
std::string VisualizeASCII(int terminal_width) {
terminal_width -= 1;
VerboseOut("Overloaded for %d of %d ticks.\n",
num_overloaded_ticks_, requests_per_tick_.size());
VerboseOut("Got maximum of %d requests in a tick.\n\n",
max_experienced_queries_per_tick_);
VerboseOut("Traffic graph:\n\n");
int num_ticks = requests_per_tick_.size();
double ticks_per_column_exact =
static_cast<double>(num_ticks) / static_cast<double>(terminal_width);
int ticks_per_column = std::ceil(ticks_per_column_exact);
DCHECK_GE(ticks_per_column * terminal_width, num_ticks);
int num_columns = num_ticks / ticks_per_column;
if (num_ticks % ticks_per_column)
++num_columns;
DCHECK_LE(num_columns, terminal_width);
scoped_ptr<int[]> columns(new int[num_columns]);
for (int tx = 0; tx < num_ticks; ++tx) {
int cx = tx / ticks_per_column;
if (tx % ticks_per_column == 0)
columns[cx] = 0;
columns[cx] += requests_per_tick_[tx];
}
int max_value = 0;
for (int cx = 0; cx < num_columns; ++cx)
max_value = std::max(max_value, columns[cx]);
const int kNumRows = 50;
double row_divisor_exact = max_value / static_cast<double>(kNumRows);
int row_divisor = std::ceil(row_divisor_exact);
DCHECK_GE(row_divisor * kNumRows, max_value);
int overload_value = max_queries_per_tick_ * ticks_per_column;
int num_printed_columns = num_columns;
if (num_ticks % ticks_per_column)
--num_printed_columns;
std::string output;
for (int rx = 0; rx < kNumRows; ++rx) {
int range_min = (kNumRows - rx) * row_divisor;
int range_max = range_min + row_divisor;
if (range_min == 0)
range_min = -1;
output.append("|");
for (int cx = 0; cx < num_printed_columns; ++cx) {
char block = ' ';
if (range_min < overload_value && overload_value <= range_max)
block = '-';
if (range_min < columns[cx] && columns[cx] <= range_max)
block = '#';
output.append(1, block);
}
output.append("\n");
}
output.append("|");
output.append(num_printed_columns, '=');
return output;
}
private:
TimeTicks now_;
TimeTicks start_downtime_;
TimeTicks end_downtime_;
const int max_queries_per_tick_;
const double request_drop_ratio_;
int num_overloaded_ticks_remaining_;
int num_current_tick_queries_;
int num_overloaded_ticks_;
int max_experienced_queries_per_tick_;
std::vector<int> requests_per_tick_;
TestURLRequestContext context_;
TestURLRequest mock_request_;
DISALLOW_COPY_AND_ASSIGN(Server);
};
class MockURLRequestThrottlerEntry : public URLRequestThrottlerEntry {
public:
explicit MockURLRequestThrottlerEntry(URLRequestThrottlerManager* manager)
: URLRequestThrottlerEntry(manager, std::string()),
mock_backoff_entry_(&backoff_policy_) {}
virtual const BackoffEntry* GetBackoffEntry() const OVERRIDE {
return &mock_backoff_entry_;
}
virtual BackoffEntry* GetBackoffEntry() OVERRIDE {
return &mock_backoff_entry_;
}
virtual TimeTicks ImplGetTimeNow() const OVERRIDE {
return fake_now_;
}
void SetFakeNow(const TimeTicks& fake_time) {
fake_now_ = fake_time;
mock_backoff_entry_.set_fake_now(fake_time);
}
TimeTicks fake_now() const {
return fake_now_;
}
protected:
virtual ~MockURLRequestThrottlerEntry() {}
private:
TimeTicks fake_now_;
MockBackoffEntry mock_backoff_entry_;
};
class RequesterResults {
public:
RequesterResults()
: num_attempts_(0), num_successful_(0), num_failed_(0), num_blocked_(0) {
}
void AddSuccess() {
++num_attempts_;
++num_successful_;
}
void AddFailure() {
++num_attempts_;
++num_failed_;
}
void AddBlocked() {
++num_attempts_;
++num_blocked_;
}
int num_attempts() const { return num_attempts_; }
int num_successful() const { return num_successful_; }
int num_failed() const { return num_failed_; }
int num_blocked() const { return num_blocked_; }
double GetBlockedRatio() {
DCHECK(num_attempts_);
return static_cast<double>(num_blocked_) /
static_cast<double>(num_attempts_);
}
double GetSuccessRatio() {
DCHECK(num_attempts_);
return static_cast<double>(num_successful_) /
static_cast<double>(num_attempts_);
}
void PrintResults(const char* class_description) {
if (num_attempts_ == 0) {
VerboseOut("No data for %s\n", class_description);
return;
}
VerboseOut("Requester results for %s\n", class_description);
VerboseOut(" %d attempts\n", num_attempts_);
VerboseOut(" %d successes\n", num_successful_);
VerboseOut(" %d 5xx responses\n", num_failed_);
VerboseOut(" %d requests blocked\n", num_blocked_);
VerboseOut(" %.2f success ratio\n", GetSuccessRatio());
VerboseOut(" %.2f blocked ratio\n", GetBlockedRatio());
VerboseOut("\n");
}
private:
int num_attempts_;
int num_successful_;
int num_failed_;
int num_blocked_;
};
class Requester : public DiscreteTimeSimulation::Actor {
public:
Requester(MockURLRequestThrottlerEntry* throttler_entry,
const TimeDelta& time_between_requests,
Server* server,
RequesterResults* results)
: throttler_entry_(throttler_entry),
time_between_requests_(time_between_requests),
last_attempt_was_failure_(false),
server_(server),
results_(results) {
DCHECK(server_);
}
virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE {
if (time_of_last_success_.is_null())
time_of_last_success_ = absolute_time;
throttler_entry_->SetFakeNow(absolute_time);
}
virtual void PerformAction() OVERRIDE {
TimeDelta effective_delay = time_between_requests_;
TimeDelta current_jitter = TimeDelta::FromMilliseconds(
request_jitter_.InMilliseconds() * base::RandDouble());
if (base::RandInt(0, 1)) {
effective_delay -= current_jitter;
} else {
effective_delay += current_jitter;
}
if (throttler_entry_->fake_now() - time_of_last_attempt_ >
effective_delay) {
if (!throttler_entry_->ShouldRejectRequest(server_->mock_request())) {
int status_code = server_->HandleRequest();
MockURLRequestThrottlerHeaderAdapter response_headers(status_code);
throttler_entry_->UpdateWithResponse(std::string(), &response_headers);
if (status_code == 200) {
if (results_)
results_->AddSuccess();
if (last_attempt_was_failure_) {
last_downtime_duration_ =
throttler_entry_->fake_now() - time_of_last_success_;
}
time_of_last_success_ = throttler_entry_->fake_now();
last_attempt_was_failure_ = false;
} else {
if (results_)
results_->AddFailure();
last_attempt_was_failure_ = true;
}
} else {
if (results_)
results_->AddBlocked();
last_attempt_was_failure_ = true;
}
time_of_last_attempt_ = throttler_entry_->fake_now();
}
}
void SetStartupJitter(const TimeDelta& max_delay) {
int delay_ms = base::RandInt(0, max_delay.InMilliseconds());
time_of_last_attempt_ = TimeTicks() +
TimeDelta::FromMilliseconds(delay_ms) - time_between_requests_;
}
void SetRequestJitter(const TimeDelta& request_jitter) {
request_jitter_ = request_jitter;
}
TimeDelta last_downtime_duration() const { return last_downtime_duration_; }
private:
scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry_;
const TimeDelta time_between_requests_;
TimeDelta request_jitter_;
TimeTicks time_of_last_attempt_;
TimeTicks time_of_last_success_;
bool last_attempt_was_failure_;
TimeDelta last_downtime_duration_;
Server* const server_;
RequesterResults* const results_;
DISALLOW_COPY_AND_ASSIGN(Requester);
};
void SimulateAttack(Server* server,
RequesterResults* attacker_results,
RequesterResults* client_results,
bool enable_throttling) {
const size_t kNumAttackers = 50;
const size_t kNumClients = 50;
DiscreteTimeSimulation simulation;
URLRequestThrottlerManager manager;
ScopedVector<Requester> requesters;
for (size_t i = 0; i < kNumAttackers; ++i) {
scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
new MockURLRequestThrottlerEntry(&manager));
if (!enable_throttling)
throttler_entry->DisableBackoffThrottling();
Requester* attacker = new Requester(throttler_entry.get(),
TimeDelta::FromMilliseconds(1),
server,
attacker_results);
attacker->SetStartupJitter(TimeDelta::FromSeconds(120));
requesters.push_back(attacker);
simulation.AddActor(attacker);
}
for (size_t i = 0; i < kNumClients; ++i) {
scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
new MockURLRequestThrottlerEntry(&manager));
if (!enable_throttling)
throttler_entry->DisableBackoffThrottling();
Requester* client = new Requester(throttler_entry.get(),
TimeDelta::FromMinutes(2),
server,
client_results);
client->SetStartupJitter(TimeDelta::FromSeconds(120));
client->SetRequestJitter(TimeDelta::FromMinutes(1));
requesters.push_back(client);
simulation.AddActor(client);
}
simulation.AddActor(server);
simulation.RunSimulation(TimeDelta::FromMinutes(6),
TimeDelta::FromSeconds(1));
}
TEST(URLRequestThrottlerSimulation, HelpsInAttack) {
Server unprotected_server(30, 1.0);
RequesterResults unprotected_attacker_results;
RequesterResults unprotected_client_results;
Server protected_server(30, 1.0);
RequesterResults protected_attacker_results;
RequesterResults protected_client_results;
SimulateAttack(&unprotected_server,
&unprotected_attacker_results,
&unprotected_client_results,
false);
SimulateAttack(&protected_server,
&protected_attacker_results,
&protected_client_results,
true);
EXPECT_GT(unprotected_server.num_overloaded_ticks(),
protected_server.num_overloaded_ticks());
EXPECT_GT(unprotected_server.max_experienced_queries_per_tick(),
protected_server.max_experienced_queries_per_tick());
EXPECT_LT(protected_client_results.GetBlockedRatio(),
protected_attacker_results.GetBlockedRatio());
EXPECT_GT(protected_client_results.GetSuccessRatio(),
unprotected_client_results.GetSuccessRatio());
VerboseOut("\nUnprotected server's results:\n\n");
VerboseOut(unprotected_server.VisualizeASCII(132).c_str());
VerboseOut("\n\n");
VerboseOut("Protected server's results:\n\n");
VerboseOut(protected_server.VisualizeASCII(132).c_str());
VerboseOut("\n\n");
unprotected_attacker_results.PrintResults(
"attackers attacking unprotected server.");
unprotected_client_results.PrintResults(
"normal clients making requests to unprotected server.");
protected_attacker_results.PrintResults(
"attackers attacking protected server.");
protected_client_results.PrintResults(
"normal clients making requests to protected server.");
}
double SimulateDowntime(const TimeDelta& duration,
const TimeDelta& average_client_interval,
bool enable_throttling) {
TimeDelta time_between_ticks = duration / 200;
TimeTicks start_downtime = TimeTicks() + (duration / 2);
Server server(std::numeric_limits<int>::max(), 1.0);
server.SetDowntime(start_downtime, duration);
URLRequestThrottlerManager manager;
scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
new MockURLRequestThrottlerEntry(&manager));
if (!enable_throttling)
throttler_entry->DisableBackoffThrottling();
Requester requester(
throttler_entry.get(), average_client_interval, &server, NULL);
requester.SetStartupJitter(duration / 3);
requester.SetRequestJitter(average_client_interval);
DiscreteTimeSimulation simulation;
simulation.AddActor(&requester);
simulation.AddActor(&server);
simulation.RunSimulation(duration * 2, time_between_ticks);
return static_cast<double>(
requester.last_downtime_duration().InMilliseconds()) /
static_cast<double>(duration.InMilliseconds());
}
TEST(URLRequestThrottlerSimulation, PerceivedDowntimeRatio) {
struct Stats {
double expected_min_increase;
double expected_max_increase;
size_t num_runs;
double total_ratio_unprotected;
double total_ratio_protected;
bool DidConverge(double* increase_ratio_out) {
double unprotected_ratio = total_ratio_unprotected / num_runs;
double protected_ratio = total_ratio_protected / num_runs;
double increase_ratio = protected_ratio / unprotected_ratio;
if (increase_ratio_out)
*increase_ratio_out = increase_ratio;
return expected_min_increase <= increase_ratio &&
increase_ratio <= expected_max_increase;
}
void ReportTrialResult(double increase_ratio) {
VerboseOut(
" Perceived downtime with throttling is %.4f times without.\n",
increase_ratio);
VerboseOut(" Test result after %d trials.\n", num_runs);
}
};
Stats global_stats = { 1.08, 1.15 };
struct Trial {
TimeDelta duration;
TimeDelta average_client_interval;
Stats stats;
void PrintTrialDescription() {
double duration_minutes =
static_cast<double>(duration.InSeconds()) / 60.0;
double interval_minutes =
static_cast<double>(average_client_interval.InSeconds()) / 60.0;
VerboseOut("Trial with %.2f min downtime, avg. interval %.2f min.\n",
duration_minutes, interval_minutes);
}
};
Trial trials[] = {
{ TimeDelta::FromSeconds(10), TimeDelta::FromSeconds(3) },
{ TimeDelta::FromSeconds(30), TimeDelta::FromSeconds(7) },
{ TimeDelta::FromMinutes(5), TimeDelta::FromSeconds(30) },
{ TimeDelta::FromMinutes(10), TimeDelta::FromSeconds(20) },
{ TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(15) },
{ TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(50) },
{ TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(2) },
{ TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(5) },
{ TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(7) },
{ TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(2) },
{ TimeDelta::FromMinutes(40), TimeDelta::FromSeconds(15) },
{ TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(7) },
{ TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(2) },
{ TimeDelta::FromMinutes(60), TimeDelta::FromSeconds(15) },
{ TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(20) },
{ TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(3) },
{ TimeDelta::FromMinutes(80), TimeDelta::FromSeconds(15) },
{ TimeDelta::FromMinutes(45), TimeDelta::FromMilliseconds(500) },
};
while (global_stats.num_runs < 100000) {
for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) {
++global_stats.num_runs;
++trials[i].stats.num_runs;
double ratio_unprotected = SimulateDowntime(
trials[i].duration, trials[i].average_client_interval, false);
double ratio_protected = SimulateDowntime(
trials[i].duration, trials[i].average_client_interval, true);
global_stats.total_ratio_unprotected += ratio_unprotected;
global_stats.total_ratio_protected += ratio_protected;
trials[i].stats.total_ratio_unprotected += ratio_unprotected;
trials[i].stats.total_ratio_protected += ratio_protected;
}
double increase_ratio;
if (global_stats.DidConverge(&increase_ratio))
break;
if (global_stats.num_runs > 200) {
VerboseOut("Test has not yet converged on expected interval.\n");
global_stats.ReportTrialResult(increase_ratio);
}
}
double average_increase_ratio;
EXPECT_TRUE(global_stats.DidConverge(&average_increase_ratio));
double max_increase_ratio = 0.0;
for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) {
double increase_ratio;
trials[i].stats.DidConverge(&increase_ratio);
max_increase_ratio = std::max(max_increase_ratio, increase_ratio);
trials[i].PrintTrialDescription();
trials[i].stats.ReportTrialResult(increase_ratio);
}
VerboseOut("Average increase ratio was %.4f\n", average_increase_ratio);
VerboseOut("Maximum increase ratio was %.4f\n", max_increase_ratio);
}
}
}