| 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 <cstdint> | |
| 8 #include <memory> | |
| 9 #include <set> | |
| 10 #include <string> | |
| 11 | |
| 12 #include "base/rand_util.h" | |
| 13 #include "testing/gtest/include/gtest/gtest.h" | |
| 14 | |
| 15 namespace net { | |
| 16 | |
| 17 namespace { | |
| 18 | |
| 19 using std::min; | |
| 20 using std::pair; | |
| 21 using std::set; | |
| 22 using std::string; | |
| 23 | |
| 24 const uint8_t kOrbit[8] = {1, 2, 3, 4, 5, 6, 7, 8}; | |
| 25 | |
| 26 // StrikeRegisterTests don't look at the random bytes so this function can | |
| 27 // simply set the random bytes to 0. | |
| 28 void SetNonce(uint8_t nonce[32], unsigned time, const uint8_t orbit[8]) { | |
| 29 nonce[0] = time >> 24; | |
| 30 nonce[1] = time >> 16; | |
| 31 nonce[2] = time >> 8; | |
| 32 nonce[3] = time; | |
| 33 memcpy(nonce + 4, orbit, 8); | |
| 34 memset(nonce + 12, 0, 20); | |
| 35 } | |
| 36 | |
| 37 TEST(StrikeRegisterTest, SimpleHorizon) { | |
| 38 // The set must reject values created on or before its own creation time. | |
| 39 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 40 100 /* window secs */, kOrbit, | |
| 41 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 42 uint8_t nonce[32]; | |
| 43 SetNonce(nonce, 999, kOrbit); | |
| 44 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000)); | |
| 45 SetNonce(nonce, 1000, kOrbit); | |
| 46 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000)); | |
| 47 | |
| 48 EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */)); | |
| 49 EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */)); | |
| 50 EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */)); | |
| 51 EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */)); | |
| 52 EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */)); | |
| 53 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */)); | |
| 54 } | |
| 55 | |
| 56 TEST(StrikeRegisterTest, NoStartupMode) { | |
| 57 // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED | |
| 58 // is specified. | |
| 59 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 60 100 /* window secs */, kOrbit, | |
| 61 StrikeRegister::NO_STARTUP_PERIOD_NEEDED); | |
| 62 uint8_t nonce[32]; | |
| 63 SetNonce(nonce, 1000, kOrbit); | |
| 64 EXPECT_EQ(NONCE_OK, set.Insert(nonce, 1000)); | |
| 65 EXPECT_EQ(NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1000)); | |
| 66 | |
| 67 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */)); | |
| 68 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */)); | |
| 69 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */)); | |
| 70 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */)); | |
| 71 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */)); | |
| 72 } | |
| 73 | |
| 74 TEST(StrikeRegisterTest, WindowFuture) { | |
| 75 // The set must reject values outside the window. | |
| 76 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 77 100 /* window secs */, kOrbit, | |
| 78 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 79 uint8_t nonce[32]; | |
| 80 SetNonce(nonce, 1101, kOrbit); | |
| 81 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000)); | |
| 82 SetNonce(nonce, 999, kOrbit); | |
| 83 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100)); | |
| 84 } | |
| 85 | |
| 86 TEST(StrikeRegisterTest, BadOrbit) { | |
| 87 // The set must reject values with the wrong orbit | |
| 88 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 89 100 /* window secs */, kOrbit, | |
| 90 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 91 uint8_t nonce[32]; | |
| 92 static const uint8_t kBadOrbit[8] = {0, 0, 0, 0, 1, 1, 1, 1}; | |
| 93 SetNonce(nonce, 1101, kBadOrbit); | |
| 94 EXPECT_EQ(NONCE_INVALID_ORBIT_FAILURE, set.Insert(nonce, 1100)); | |
| 95 } | |
| 96 | |
| 97 TEST(StrikeRegisterTest, OneValue) { | |
| 98 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 99 100 /* window secs */, kOrbit, | |
| 100 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 101 uint8_t nonce[32]; | |
| 102 SetNonce(nonce, 1101, kOrbit); | |
| 103 EXPECT_EQ(NONCE_OK, set.Insert(nonce, 1101)); | |
| 104 } | |
| 105 | |
| 106 TEST(StrikeRegisterTest, RejectDuplicate) { | |
| 107 // The set must reject values with the wrong orbit | |
| 108 StrikeRegister set(10 /* max size */, 1000 /* current time */, | |
| 109 100 /* window secs */, kOrbit, | |
| 110 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 111 uint8_t nonce[32]; | |
| 112 SetNonce(nonce, 1101, kOrbit); | |
| 113 EXPECT_EQ(NONCE_OK, set.Insert(nonce, 1101)); | |
| 114 EXPECT_EQ(NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1101)); | |
| 115 } | |
| 116 | |
| 117 TEST(StrikeRegisterTest, HorizonUpdating) { | |
| 118 StrikeRegister::StartupType startup_types[] = { | |
| 119 StrikeRegister::DENY_REQUESTS_AT_STARTUP, | |
| 120 StrikeRegister::NO_STARTUP_PERIOD_NEEDED}; | |
| 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, startup_types[type_idx]); | |
| 125 uint8_t nonce[6][32]; | |
| 126 for (unsigned i = 0; i < 5; i++) { | |
| 127 SetNonce(nonce[i], 1101 + i, kOrbit); | |
| 128 nonce[i][31] = i; | |
| 129 EXPECT_EQ(NONCE_OK, set.Insert(nonce[i], 1100)); | |
| 130 } | |
| 131 | |
| 132 // Valid window is still equal to |window_secs + 1|. | |
| 133 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100)); | |
| 134 | |
| 135 // This should push the oldest value out and force the horizon to | |
| 136 // be updated. | |
| 137 SetNonce(nonce[5], 1110, kOrbit); | |
| 138 EXPECT_EQ(NONCE_OK, set.Insert(nonce[5], 1110)); | |
| 139 // Effective horizon is computed based on the timestamp of the | |
| 140 // value that was pushed out. | |
| 141 EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110)); | |
| 142 | |
| 143 SetNonce(nonce[5], 1111, kOrbit); | |
| 144 EXPECT_EQ(NONCE_OK, set.Insert(nonce[5], 1110)); | |
| 145 EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110)); | |
| 146 | |
| 147 // This should be behind the horizon now: | |
| 148 SetNonce(nonce[5], 1101, kOrbit); | |
| 149 nonce[5][31] = 10; | |
| 150 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); | |
| 151 | |
| 152 // Insert beyond the valid range. | |
| 153 SetNonce(nonce[5], 1117, kOrbit); | |
| 154 nonce[5][31] = 2; | |
| 155 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); | |
| 156 | |
| 157 // Insert at the upper valid range. | |
| 158 SetNonce(nonce[5], 1116, kOrbit); | |
| 159 nonce[5][31] = 1; | |
| 160 EXPECT_EQ(NONCE_OK, set.Insert(nonce[5], 1110)); | |
| 161 | |
| 162 // This should be beyond the upper valid range now: | |
| 163 SetNonce(nonce[5], 1116, kOrbit); | |
| 164 nonce[5][31] = 2; | |
| 165 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); | |
| 166 } | |
| 167 } | |
| 168 | |
| 169 TEST(StrikeRegisterTest, InsertMany) { | |
| 170 StrikeRegister set(5000 /* max size */, 1000 /* current time */, | |
| 171 500 /* window secs */, kOrbit, | |
| 172 StrikeRegister::DENY_REQUESTS_AT_STARTUP); | |
| 173 | |
| 174 uint8_t nonce[32]; | |
| 175 SetNonce(nonce, 1101, kOrbit); | |
| 176 for (unsigned i = 0; i < 100000; i++) { | |
| 177 SetNonce(nonce, 1101 + i / 500, kOrbit); | |
| 178 memcpy(nonce + 12, &i, sizeof(i)); | |
| 179 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100)); | |
| 180 } | |
| 181 } | |
| 182 | |
| 183 // For the following test we create a slow, but simple, version of a | |
| 184 // StrikeRegister. The behaviour of this object is much easier to understand | |
| 185 // than the fully fledged version. We then create a test to show, empirically, | |
| 186 // that the two objects have identical behaviour. | |
| 187 | |
| 188 // A SlowStrikeRegister has the same public interface as a StrikeRegister, but | |
| 189 // is much slower. Hopefully it is also more obviously correct and we can | |
| 190 // empirically test that their behaviours are identical. | |
| 191 class SlowStrikeRegister { | |
| 192 public: | |
| 193 SlowStrikeRegister(unsigned max_entries, | |
| 194 uint32_t current_time, | |
| 195 uint32_t window_secs, | |
| 196 const uint8_t 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_t nonce_bytes[32], | |
| 205 const uint32_t nonce_time_external, | |
| 206 const uint32_t current_time_external) { | |
| 207 if (nonces_.size() == max_entries_) { | |
| 208 DropOldestEntry(); | |
| 209 } | |
| 210 | |
| 211 const uint32_t 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 NONCE_INVALID_ORBIT_FAILURE; | |
| 216 } | |
| 217 const uint32_t 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 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 NONCE_INVALID_TIME_FAILURE; | |
| 232 } | |
| 233 | |
| 234 pair<uint32_t, string> nonce = std::make_pair( | |
| 235 nonce_time, string(reinterpret_cast<const char*>(nonce_bytes), 32)); | |
| 236 | |
| 237 set<pair<uint32_t, string>>::const_iterator it = nonces_.find(nonce); | |
| 238 if (it != nonces_.end()) { | |
| 239 return NONCE_NOT_UNIQUE_FAILURE; | |
| 240 } | |
| 241 | |
| 242 nonces_.insert(nonce); | |
| 243 return NONCE_OK; | |
| 244 } | |
| 245 | |
| 246 uint32_t GetCurrentValidWindowSecs( | |
| 247 const uint32_t current_time_external) const { | |
| 248 const uint32_t current_time = ExternalTimeToInternal(current_time_external); | |
| 249 if (horizon_ > current_time) { | |
| 250 return 0; | |
| 251 } | |
| 252 return 1 + min(current_time - horizon_, window_secs_); | |
| 253 } | |
| 254 | |
| 255 private: | |
| 256 // TimeFromBytes returns a big-endian uint32_t from |d|. | |
| 257 static uint32_t TimeFromBytes(const uint8_t d[4]) { | |
| 258 return static_cast<uint32_t>(d[0]) << 24 | | |
| 259 static_cast<uint32_t>(d[1]) << 16 | | |
| 260 static_cast<uint32_t>(d[2]) << 8 | static_cast<uint32_t>(d[3]); | |
| 261 } | |
| 262 | |
| 263 uint32_t ExternalTimeToInternal(uint32_t external_time) const { | |
| 264 static const uint32_t kCreationTimeFromInternalEpoch = 63115200.0; | |
| 265 uint32_t 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_t, 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_t creation_time_; | |
| 282 uint8_t orbit_[8]; | |
| 283 uint32_t horizon_; | |
| 284 | |
| 285 set<pair<uint32_t, string>> nonces_; | |
| 286 }; | |
| 287 | |
| 288 class StrikeRegisterStressTest : public ::testing::Test {}; | |
| 289 | |
| 290 TEST_F(StrikeRegisterStressTest, InOrderInsertion) { | |
| 291 // Fixed seed gives reproducibility for this test. | |
| 292 srand(42); | |
| 293 | |
| 294 unsigned max_entries = 64; | |
| 295 uint32_t current_time = 10000, window = 200; | |
| 296 std::unique_ptr<StrikeRegister> s1( | |
| 297 new StrikeRegister(max_entries, current_time, window, kOrbit, | |
| 298 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); | |
| 299 std::unique_ptr<SlowStrikeRegister> s2( | |
| 300 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); | |
| 301 | |
| 302 uint64_t i; | |
| 303 const uint64_t kMaxIterations = 10000; | |
| 304 for (i = 0; i < kMaxIterations; i++) { | |
| 305 const uint32_t time = current_time + i; | |
| 306 | |
| 307 uint8_t nonce[32]; | |
| 308 SetNonce(nonce, time, kOrbit); | |
| 309 | |
| 310 // There are 2048 possible nonce values: | |
| 311 const uint32_t v = rand() % 2048; | |
| 312 nonce[30] = v >> 8; | |
| 313 nonce[31] = v; | |
| 314 | |
| 315 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time); | |
| 316 const InsertStatus nonce_error1 = s1->Insert(nonce, time); | |
| 317 EXPECT_EQ(nonce_error1, nonce_error2); | |
| 318 | |
| 319 // Inserts succeed after the startup period. | |
| 320 if (time > current_time + window) { | |
| 321 EXPECT_EQ(NONCE_OK, nonce_error1); | |
| 322 } else { | |
| 323 EXPECT_EQ(NONCE_INVALID_TIME_FAILURE, nonce_error1); | |
| 324 } | |
| 325 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time), | |
| 326 s2->GetCurrentValidWindowSecs(time)); | |
| 327 | |
| 328 if (i % 10 == 0) { | |
| 329 s1->Validate(); | |
| 330 } | |
| 331 | |
| 332 if (HasFailure()) { | |
| 333 break; | |
| 334 } | |
| 335 } | |
| 336 | |
| 337 if (i != kMaxIterations) { | |
| 338 FAIL() << "Failed after " << i << " iterations"; | |
| 339 } | |
| 340 } | |
| 341 | |
| 342 TEST_F(StrikeRegisterStressTest, Stress) { | |
| 343 // Fixed seed gives reproducibility for this test. | |
| 344 srand(42); | |
| 345 unsigned max_entries = 64; | |
| 346 uint32_t current_time = 10000, window = 200; | |
| 347 std::unique_ptr<StrikeRegister> s1( | |
| 348 new StrikeRegister(max_entries, current_time, window, kOrbit, | |
| 349 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); | |
| 350 std::unique_ptr<SlowStrikeRegister> s2( | |
| 351 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); | |
| 352 uint64_t i; | |
| 353 | |
| 354 // When making changes it's worth removing the limit on this test and running | |
| 355 // it for a while. For the initial development an opt binary was left running | |
| 356 // for 10 minutes. | |
| 357 const uint64_t kMaxIterations = 10000; | |
| 358 for (i = 0; i < kMaxIterations; i++) { | |
| 359 if (rand() % 1000 == 0) { | |
| 360 // 0.1% chance of resetting the sets. | |
| 361 max_entries = rand() % 300 + 2; | |
| 362 current_time = rand() % 10000; | |
| 363 window = rand() % 500; | |
| 364 s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit, | |
| 365 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); | |
| 366 s2.reset( | |
| 367 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); | |
| 368 } | |
| 369 | |
| 370 int32_t time_delta = rand() % (window * 4); | |
| 371 time_delta -= window * 2; | |
| 372 const uint32_t time = current_time + time_delta; | |
| 373 if (time_delta < 0 && time > current_time) { | |
| 374 continue; // overflow | |
| 375 } | |
| 376 | |
| 377 uint8_t nonce[32]; | |
| 378 SetNonce(nonce, time, kOrbit); | |
| 379 | |
| 380 // There are 2048 possible nonce values: | |
| 381 const uint32_t v = rand() % 2048; | |
| 382 nonce[30] = v >> 8; | |
| 383 nonce[31] = v; | |
| 384 | |
| 385 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time); | |
| 386 const InsertStatus nonce_error1 = s1->Insert(nonce, time); | |
| 387 EXPECT_EQ(nonce_error1, nonce_error2); | |
| 388 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time), | |
| 389 s2->GetCurrentValidWindowSecs(time)); | |
| 390 | |
| 391 if (i % 10 == 0) { | |
| 392 s1->Validate(); | |
| 393 } | |
| 394 | |
| 395 if (HasFailure()) { | |
| 396 break; | |
| 397 } | |
| 398 } | |
| 399 | |
| 400 if (i != kMaxIterations) { | |
| 401 FAIL() << "Failed after " << i << " iterations"; | |
| 402 } | |
| 403 } | |
| 404 | |
| 405 } // namespace | |
| 406 | |
| 407 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2193073003:
Move shared files in net/quic/ into net/quic/core/ (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master