| OLD | NEW |
|---|
| (Empty) |
| 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. | |
| 4 | |
| 5 #include "net/quic/crypto/strike_register.h" | |
| 6 | |
| 7 #include <set> | |
| 8 #include <string> | |
| 9 | |
| 10 #include "base/basictypes.h" | |
| 11 #include "base/rand_util.h" | |
| 12 #include "testing/gtest/include/gtest/gtest.h" | |
| 13 | |
| 14 namespace { | |
| 15 | |
| 16 using net::InsertStatus; | |
| 17 using net::StrikeRegister; | |
| 18 using std::min; | |
| 19 using std::pair; | |
| 20 using std::set; | |
| 21 using std::string; | |
| 22 | |
| 23 const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; | |
| 24 | |
| 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); | |
| 34 } | |
| 35 | |
| 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)); | |
| 46 | |
| 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 */)); | |
| 53 } | |
| 54 | |
| 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)); | |
| 65 | |
| 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 */)); | |
| 71 } | |
| 72 | |
| 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)); | |
| 83 } | |
| 84 | |
| 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)); | |
| 94 } | |
| 95 | |
| 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)); | |
| 103 } | |
| 104 | |
| 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)); | |
| 114 } | |
| 115 | |
| 116 TEST(StrikeRegisterTest, HorizonUpdating) { | |
| 117 StrikeRegister::StartupType startup_types[] = { | |
| 118 StrikeRegister::DENY_REQUESTS_AT_STARTUP, | |
| 119 StrikeRegister::NO_STARTUP_PERIOD_NEEDED | |
| 120 }; | |
| 121 | |
| 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)); | |
| 131 } | |
| 132 | |
| 133 // Valid window is still equal to |window_secs + 1|. | |
| 134 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100)); | |
| 135 | |
| 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)); | |
| 143 | |
| 144 SetNonce(nonce[5], 1111, kOrbit); | |
| 145 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110)); | |
| 146 EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110)); | |
| 147 | |
| 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)); | |
| 152 | |
| 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)); | |
| 157 | |
| 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)); | |
| 162 | |
| 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)); | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 TEST(StrikeRegisterTest, InsertMany) { | |
| 171 StrikeRegister set(5000 /* max size */, 1000 /* current time */, | |
| 172 500 /* window secs */, kOrbit, | |
| 173 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 174 | |
| 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)); | |
| 181 } | |
| 182 } | |
| 183 | |
| 184 | |
| 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. | |
| 189 | |
| 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_)); | |
| 202 } | |
| 203 | |
| 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(); | |
| 209 } | |
| 210 | |
| 211 const uint32 current_time = ExternalTimeToInternal(current_time_external); | |
| 212 | |
| 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; | |
| 216 } | |
| 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; | |
| 225 } | |
| 226 | |
| 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; | |
| 232 } | |
| 233 | |
| 234 pair<uint32, string> nonce = std::make_pair( | |
| 235 nonce_time, string(reinterpret_cast<const char*>(nonce_bytes), 32)); | |
| 236 | |
| 237 set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce); | |
| 238 if (it != nonces_.end()) { | |
| 239 return net::NONCE_NOT_UNIQUE_FAILURE; | |
| 240 } | |
| 241 | |
| 242 nonces_.insert(nonce); | |
| 243 return net::NONCE_OK; | |
| 244 } | |
| 245 | |
| 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; | |
| 250 } | |
| 251 return 1 + min(current_time - horizon_, window_secs_); | |
| 252 } | |
| 253 | |
| 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]); | |
| 261 } | |
| 262 | |
| 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; | |
| 268 } | |
| 269 | |
| 270 return external_time - internal_epoch; | |
| 271 } | |
| 272 | |
| 273 void DropOldestEntry() { | |
| 274 set<pair<uint32, string> >::iterator oldest = nonces_.begin(); | |
| 275 horizon_ = oldest->first + 1; | |
| 276 nonces_.erase(oldest); | |
| 277 } | |
| 278 | |
| 279 const unsigned max_entries_; | |
| 280 const unsigned window_secs_; | |
| 281 const uint32 creation_time_; | |
| 282 uint8 orbit_[8]; | |
| 283 uint32 horizon_; | |
| 284 | |
| 285 set<pair<uint32, string> > nonces_; | |
| 286 }; | |
| 287 | |
| 288 class StrikeRegisterStressTest : public ::testing::Test { | |
| 289 }; | |
| 290 | |
| 291 TEST_F(StrikeRegisterStressTest, InOrderInsertion) { | |
| 292 // Fixed seed gives reproducibility for this test. | |
| 293 srand(42); | |
| 294 | |
| 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)); | |
| 302 | |
| 303 uint64 i; | |
| 304 const uint64 kMaxIterations = 10000; | |
| 305 for (i = 0; i < kMaxIterations; i++) { | |
| 306 const uint32 time = current_time + i; | |
| 307 | |
| 308 uint8 nonce[32]; | |
| 309 SetNonce(nonce, time, kOrbit); | |
| 310 | |
| 311 // There are 2048 possible nonce values: | |
| 312 const uint32 v = rand() % 2048; | |
| 313 nonce[30] = v >> 8; | |
| 314 nonce[31] = v; | |
| 315 | |
| 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); | |
| 319 | |
| 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); | |
| 325 } | |
| 326 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time), | |
| 327 s2->GetCurrentValidWindowSecs(time)); | |
| 328 | |
| 329 if (i % 10 == 0) { | |
| 330 s1->Validate(); | |
| 331 } | |
| 332 | |
| 333 if (HasFailure()) { | |
| 334 break; | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 if (i != kMaxIterations) { | |
| 339 FAIL() << "Failed after " << i << " iterations"; | |
| 340 } | |
| 341 } | |
| 342 | |
| 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; | |
| 354 | |
| 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)); | |
| 369 } | |
| 370 | |
| 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 | |
| 376 } | |
| 377 | |
| 378 uint8 nonce[32]; | |
| 379 SetNonce(nonce, time, kOrbit); | |
| 380 | |
| 381 // There are 2048 possible nonce values: | |
| 382 const uint32 v = rand() % 2048; | |
| 383 nonce[30] = v >> 8; | |
| 384 nonce[31] = v; | |
| 385 | |
| 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)); | |
| 391 | |
| 392 if (i % 10 == 0) { | |
| 393 s1->Validate(); | |
| 394 } | |
| 395 | |
| 396 if (HasFailure()) { | |
| 397 break; | |
| 398 } | |
| 399 } | |
| 400 | |
| 401 if (i != kMaxIterations) { | |
| 402 FAIL() << "Failed after " << i << " iterations"; | |
| 403 } | |
| 404 } | |
| 405 | |
| 406 } // anonymous namespace | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master