We started redesigning GpuMemoryBuffer interface to handle multiple buffers [0].
[chromium-blink-merge.git] / net / quic / crypto / strike_register_test.cc
blob73a6b2faa138ab56cf1db4cb8daead1e374a6cea
1 // Copyright (c) 2013 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.
5 #include "net/quic/crypto/strike_register.h"
7 #include <set>
8 #include <string>
10 #include "base/basictypes.h"
11 #include "base/rand_util.h"
12 #include "testing/gtest/include/gtest/gtest.h"
14 namespace {
16 using net::InsertStatus;
17 using net::StrikeRegister;
18 using std::min;
19 using std::pair;
20 using std::set;
21 using std::string;
23 const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
25 // StrikeRegisterTests don't look at the random bytes so this function can
26 // simply set the random bytes to 0.
27 void SetNonce(uint8 nonce[32], unsigned time, const uint8 orbit[8]) {
28 nonce[0] = time >> 24;
29 nonce[1] = time >> 16;
30 nonce[2] = time >> 8;
31 nonce[3] = time;
32 memcpy(nonce + 4, orbit, 8);
33 memset(nonce + 12, 0, 20);
36 TEST(StrikeRegisterTest, SimpleHorizon) {
37 // The set must reject values created on or before its own creation time.
38 StrikeRegister set(10 /* max size */, 1000 /* current time */,
39 100 /* window secs */, kOrbit,
40 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
41 uint8 nonce[32];
42 SetNonce(nonce, 999, kOrbit);
43 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
44 SetNonce(nonce, 1000, kOrbit);
45 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
47 EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */));
48 EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */));
49 EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */));
50 EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */));
51 EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */));
52 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
55 TEST(StrikeRegisterTest, NoStartupMode) {
56 // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
57 // is specified.
58 StrikeRegister set(10 /* max size */, 1000 /* current time */,
59 100 /* window secs */, kOrbit,
60 StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
61 uint8 nonce[32];
62 SetNonce(nonce, 1000, kOrbit);
63 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1000));
64 EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1000));
66 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */));
67 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */));
68 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */));
69 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */));
70 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
73 TEST(StrikeRegisterTest, WindowFuture) {
74 // The set must reject values outside the window.
75 StrikeRegister set(10 /* max size */, 1000 /* current time */,
76 100 /* window secs */, kOrbit,
77 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
78 uint8 nonce[32];
79 SetNonce(nonce, 1101, kOrbit);
80 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
81 SetNonce(nonce, 999, kOrbit);
82 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
85 TEST(StrikeRegisterTest, BadOrbit) {
86 // The set must reject values with the wrong orbit
87 StrikeRegister set(10 /* max size */, 1000 /* current time */,
88 100 /* window secs */, kOrbit,
89 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
90 uint8 nonce[32];
91 static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 };
92 SetNonce(nonce, 1101, kBadOrbit);
93 EXPECT_EQ(net::NONCE_INVALID_ORBIT_FAILURE, set.Insert(nonce, 1100));
96 TEST(StrikeRegisterTest, OneValue) {
97 StrikeRegister set(10 /* max size */, 1000 /* current time */,
98 100 /* window secs */, kOrbit,
99 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
100 uint8 nonce[32];
101 SetNonce(nonce, 1101, kOrbit);
102 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
105 TEST(StrikeRegisterTest, RejectDuplicate) {
106 // The set must reject values with the wrong orbit
107 StrikeRegister set(10 /* max size */, 1000 /* current time */,
108 100 /* window secs */, kOrbit,
109 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
110 uint8 nonce[32];
111 SetNonce(nonce, 1101, kOrbit);
112 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
113 EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1101));
116 TEST(StrikeRegisterTest, HorizonUpdating) {
117 StrikeRegister::StartupType startup_types[] = {
118 StrikeRegister::DENY_REQUESTS_AT_STARTUP,
119 StrikeRegister::NO_STARTUP_PERIOD_NEEDED
122 for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) {
123 StrikeRegister set(5 /* max size */, 500 /* current time */,
124 100 /* window secs */, kOrbit,
125 startup_types[type_idx]);
126 uint8 nonce[6][32];
127 for (unsigned i = 0; i < 5; i++) {
128 SetNonce(nonce[i], 1101 + i, kOrbit);
129 nonce[i][31] = i;
130 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[i], 1100));
133 // Valid window is still equal to |window_secs + 1|.
134 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100));
136 // This should push the oldest value out and force the horizon to
137 // be updated.
138 SetNonce(nonce[5], 1110, kOrbit);
139 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
140 // Effective horizon is computed based on the timestamp of the
141 // value that was pushed out.
142 EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110));
144 SetNonce(nonce[5], 1111, kOrbit);
145 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
146 EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110));
148 // This should be behind the horizon now:
149 SetNonce(nonce[5], 1101, kOrbit);
150 nonce[5][31] = 10;
151 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
153 // Insert beyond the valid range.
154 SetNonce(nonce[5], 1117, kOrbit);
155 nonce[5][31] = 2;
156 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
158 // Insert at the upper valid range.
159 SetNonce(nonce[5], 1116, kOrbit);
160 nonce[5][31] = 1;
161 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
163 // This should be beyond the upper valid range now:
164 SetNonce(nonce[5], 1116, kOrbit);
165 nonce[5][31] = 2;
166 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
170 TEST(StrikeRegisterTest, InsertMany) {
171 StrikeRegister set(5000 /* max size */, 1000 /* current time */,
172 500 /* window secs */, kOrbit,
173 StrikeRegister::DENY_REQUESTS_AT_STARTUP);
175 uint8 nonce[32];
176 SetNonce(nonce, 1101, kOrbit);
177 for (unsigned i = 0; i < 100000; i++) {
178 SetNonce(nonce, 1101 + i/500, kOrbit);
179 memcpy(nonce + 12, &i, sizeof(i));
180 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
185 // For the following test we create a slow, but simple, version of a
186 // StrikeRegister. The behaviour of this object is much easier to understand
187 // than the fully fledged version. We then create a test to show, empirically,
188 // that the two objects have identical behaviour.
190 // A SlowStrikeRegister has the same public interface as a StrikeRegister, but
191 // is much slower. Hopefully it is also more obviously correct and we can
192 // empirically test that their behaviours are identical.
193 class SlowStrikeRegister {
194 public:
195 SlowStrikeRegister(unsigned max_entries, uint32 current_time,
196 uint32 window_secs, const uint8 orbit[8])
197 : max_entries_(max_entries),
198 window_secs_(window_secs),
199 creation_time_(current_time),
200 horizon_(ExternalTimeToInternal(current_time + window_secs) + 1) {
201 memcpy(orbit_, orbit, sizeof(orbit_));
204 InsertStatus Insert(const uint8 nonce_bytes[32],
205 const uint32 nonce_time_external,
206 const uint32 current_time_external) {
207 if (nonces_.size() == max_entries_) {
208 DropOldestEntry();
211 const uint32 current_time = ExternalTimeToInternal(current_time_external);
213 // Check to see if the orbit is correct.
214 if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) {
215 return net::NONCE_INVALID_ORBIT_FAILURE;
217 const uint32 nonce_time =
218 ExternalTimeToInternal(TimeFromBytes(nonce_bytes));
219 EXPECT_EQ(ExternalTimeToInternal(nonce_time_external), nonce_time);
220 // We have dropped one or more nonces with a time value of |horizon_ - 1|,
221 // so we have to reject anything with a timestamp less than or
222 // equal to that.
223 if (nonce_time < horizon_) {
224 return net::NONCE_INVALID_TIME_FAILURE;
227 // Check that the timestamp is in the current window.
228 if ((current_time > window_secs_ &&
229 nonce_time < (current_time - window_secs_)) ||
230 nonce_time > (current_time + window_secs_)) {
231 return net::NONCE_INVALID_TIME_FAILURE;
234 pair<uint32, string> nonce = std::make_pair(
235 nonce_time, string(reinterpret_cast<const char*>(nonce_bytes), 32));
237 set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce);
238 if (it != nonces_.end()) {
239 return net::NONCE_NOT_UNIQUE_FAILURE;
242 nonces_.insert(nonce);
243 return net::NONCE_OK;
246 uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const {
247 const uint32 current_time = ExternalTimeToInternal(current_time_external);
248 if (horizon_ > current_time) {
249 return 0;
251 return 1 + min(current_time - horizon_, window_secs_);
254 private:
255 // TimeFromBytes returns a big-endian uint32 from |d|.
256 static uint32 TimeFromBytes(const uint8 d[4]) {
257 return static_cast<uint32>(d[0]) << 24 |
258 static_cast<uint32>(d[1]) << 16 |
259 static_cast<uint32>(d[2]) << 8 |
260 static_cast<uint32>(d[3]);
263 uint32 ExternalTimeToInternal(uint32 external_time) const {
264 static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
265 uint32 internal_epoch = 0;
266 if (creation_time_ > kCreationTimeFromInternalEpoch) {
267 internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch;
270 return external_time - internal_epoch;
273 void DropOldestEntry() {
274 set<pair<uint32, string> >::iterator oldest = nonces_.begin();
275 horizon_ = oldest->first + 1;
276 nonces_.erase(oldest);
279 const unsigned max_entries_;
280 const unsigned window_secs_;
281 const uint32 creation_time_;
282 uint8 orbit_[8];
283 uint32 horizon_;
285 set<pair<uint32, string> > nonces_;
288 class StrikeRegisterStressTest : public ::testing::Test {
291 TEST_F(StrikeRegisterStressTest, InOrderInsertion) {
292 // Fixed seed gives reproducibility for this test.
293 srand(42);
295 unsigned max_entries = 64;
296 uint32 current_time = 10000, window = 200;
297 scoped_ptr<StrikeRegister> s1(
298 new StrikeRegister(max_entries, current_time, window, kOrbit,
299 StrikeRegister::DENY_REQUESTS_AT_STARTUP));
300 scoped_ptr<SlowStrikeRegister> s2(
301 new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
303 uint64 i;
304 const uint64 kMaxIterations = 10000;
305 for (i = 0; i < kMaxIterations; i++) {
306 const uint32 time = current_time + i;
308 uint8 nonce[32];
309 SetNonce(nonce, time, kOrbit);
311 // There are 2048 possible nonce values:
312 const uint32 v = rand() % 2048;
313 nonce[30] = v >> 8;
314 nonce[31] = v;
316 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
317 const InsertStatus nonce_error1 = s1->Insert(nonce, time);
318 EXPECT_EQ(nonce_error1, nonce_error2);
320 // Inserts succeed after the startup period.
321 if (time > current_time + window) {
322 EXPECT_EQ(net::NONCE_OK, nonce_error1);
323 } else {
324 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, nonce_error1);
326 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
327 s2->GetCurrentValidWindowSecs(time));
329 if (i % 10 == 0) {
330 s1->Validate();
333 if (HasFailure()) {
334 break;
338 if (i != kMaxIterations) {
339 FAIL() << "Failed after " << i << " iterations";
343 TEST_F(StrikeRegisterStressTest, Stress) {
344 // Fixed seed gives reproducibility for this test.
345 srand(42);
346 unsigned max_entries = 64;
347 uint32 current_time = 10000, window = 200;
348 scoped_ptr<StrikeRegister> s1(
349 new StrikeRegister(max_entries, current_time, window, kOrbit,
350 StrikeRegister::DENY_REQUESTS_AT_STARTUP));
351 scoped_ptr<SlowStrikeRegister> s2(
352 new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
353 uint64 i;
355 // When making changes it's worth removing the limit on this test and running
356 // it for a while. For the initial development an opt binary was left running
357 // for 10 minutes.
358 const uint64 kMaxIterations = 10000;
359 for (i = 0; i < kMaxIterations; i++) {
360 if (rand() % 1000 == 0) {
361 // 0.1% chance of resetting the sets.
362 max_entries = rand() % 300 + 2;
363 current_time = rand() % 10000;
364 window = rand() % 500;
365 s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit,
366 StrikeRegister::DENY_REQUESTS_AT_STARTUP));
367 s2.reset(
368 new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
371 int32 time_delta = rand() % (window * 4);
372 time_delta -= window * 2;
373 const uint32 time = current_time + time_delta;
374 if (time_delta < 0 && time > current_time) {
375 continue; // overflow
378 uint8 nonce[32];
379 SetNonce(nonce, time, kOrbit);
381 // There are 2048 possible nonce values:
382 const uint32 v = rand() % 2048;
383 nonce[30] = v >> 8;
384 nonce[31] = v;
386 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
387 const InsertStatus nonce_error1 = s1->Insert(nonce, time);
388 EXPECT_EQ(nonce_error1, nonce_error2);
389 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
390 s2->GetCurrentValidWindowSecs(time));
392 if (i % 10 == 0) {
393 s1->Validate();
396 if (HasFailure()) {
397 break;
401 if (i != kMaxIterations) {
402 FAIL() << "Failed after " << i << " iterations";
406 } // anonymous namespace