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::make_pair; 19 using std::min; 20 using std::pair; 21 using std::set; 22 using std::string; 23 24 const uint8 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 nonce[32], unsigned time, const uint8 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 nonce[32]; 43 SetNonce(nonce, 999, kOrbit); 44 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000)); 45 SetNonce(nonce, 1000, kOrbit); 46 EXPECT_EQ(net::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 nonce[32]; 63 SetNonce(nonce, 1000, kOrbit); 64 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1000)); 65 EXPECT_EQ(net::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 nonce[32]; 80 SetNonce(nonce, 1101, kOrbit); 81 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000)); 82 SetNonce(nonce, 999, kOrbit); 83 EXPECT_EQ(net::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 nonce[32]; 92 static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 }; 93 SetNonce(nonce, 1101, kBadOrbit); 94 EXPECT_EQ(net::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 nonce[32]; 102 SetNonce(nonce, 1101, kOrbit); 103 EXPECT_EQ(net::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 nonce[32]; 112 SetNonce(nonce, 1101, kOrbit); 113 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101)); 114 EXPECT_EQ(net::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 123 for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) { 124 StrikeRegister set(5 /* max size */, 500 /* current time */, 125 100 /* window secs */, kOrbit, 126 startup_types[type_idx]); 127 uint8 nonce[6][32]; 128 for (unsigned i = 0; i < 5; i++) { 129 SetNonce(nonce[i], 1101 + i, kOrbit); 130 nonce[i][31] = i; 131 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[i], 1100)); 132 } 133 134 // Valid window is still equal to |window_secs + 1|. 135 EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100)); 136 137 // This should push the oldest value out and force the horizon to 138 // be updated. 139 SetNonce(nonce[5], 1110, kOrbit); 140 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110)); 141 // Effective horizon is computed based on the timestamp of the 142 // value that was pushed out. 143 EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110)); 144 145 SetNonce(nonce[5], 1111, kOrbit); 146 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110)); 147 EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110)); 148 149 // This should be behind the horizon now: 150 SetNonce(nonce[5], 1101, kOrbit); 151 nonce[5][31] = 10; 152 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); 153 154 // Insert beyond the valid range. 155 SetNonce(nonce[5], 1117, kOrbit); 156 nonce[5][31] = 2; 157 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); 158 159 // Insert at the upper valid range. 160 SetNonce(nonce[5], 1116, kOrbit); 161 nonce[5][31] = 1; 162 EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110)); 163 164 // This should be beyond the upper valid range now: 165 SetNonce(nonce[5], 1116, kOrbit); 166 nonce[5][31] = 2; 167 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110)); 168 } 169 } 170 171 TEST(StrikeRegisterTest, InsertMany) { 172 StrikeRegister set(5000 /* max size */, 1000 /* current time */, 173 500 /* window secs */, kOrbit, 174 StrikeRegister::DENY_REQUESTS_AT_STARTUP); 175 176 uint8 nonce[32]; 177 SetNonce(nonce, 1101, kOrbit); 178 for (unsigned i = 0; i < 100000; i++) { 179 SetNonce(nonce, 1101 + i/500, kOrbit); 180 memcpy(nonce + 12, &i, sizeof(i)); 181 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100)); 182 } 183 } 184 185 186 // For the following test we create a slow, but simple, version of a 187 // StrikeRegister. The behaviour of this object is much easier to understand 188 // than the fully fledged version. We then create a test to show, empirically, 189 // that the two objects have identical behaviour. 190 191 // A SlowStrikeRegister has the same public interface as a StrikeRegister, but 192 // is much slower. Hopefully it is also more obviously correct and we can 193 // empirically test that their behaviours are identical. 194 class SlowStrikeRegister { 195 public: 196 SlowStrikeRegister(unsigned max_entries, uint32 current_time, 197 uint32 window_secs, const uint8 orbit[8]) 198 : max_entries_(max_entries), 199 window_secs_(window_secs), 200 creation_time_(current_time), 201 horizon_(ExternalTimeToInternal(current_time + window_secs) + 1) { 202 memcpy(orbit_, orbit, sizeof(orbit_)); 203 } 204 205 InsertStatus Insert(const uint8 nonce_bytes[32], 206 const uint32 nonce_time_external, 207 const uint32 current_time_external) { 208 if (nonces_.size() == max_entries_) { 209 DropOldestEntry(); 210 } 211 212 const uint32 current_time = ExternalTimeToInternal(current_time_external); 213 214 // Check to see if the orbit is correct. 215 if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) { 216 return net::NONCE_INVALID_ORBIT_FAILURE; 217 } 218 const uint32 nonce_time = 219 ExternalTimeToInternal(TimeFromBytes(nonce_bytes)); 220 EXPECT_EQ(ExternalTimeToInternal(nonce_time_external), nonce_time); 221 // We have dropped one or more nonces with a time value of |horizon_ - 1|, 222 // so we have to reject anything with a timestamp less than or 223 // equal to that. 224 if (nonce_time < horizon_) { 225 return net::NONCE_INVALID_TIME_FAILURE; 226 } 227 228 // Check that the timestamp is in the current window. 229 if ((current_time > window_secs_ && 230 nonce_time < (current_time - window_secs_)) || 231 nonce_time > (current_time + window_secs_)) { 232 return net::NONCE_INVALID_TIME_FAILURE; 233 } 234 235 pair<uint32, string> nonce = make_pair( 236 nonce_time, 237 string(reinterpret_cast<const char*>(nonce_bytes), 32)); 238 239 set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce); 240 if (it != nonces_.end()) { 241 return net::NONCE_NOT_UNIQUE_FAILURE; 242 } 243 244 nonces_.insert(nonce); 245 return net::NONCE_OK; 246 } 247 248 uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const { 249 const uint32 current_time = ExternalTimeToInternal(current_time_external); 250 if (horizon_ > current_time) { 251 return 0; 252 } 253 return 1 + min(current_time - horizon_, window_secs_); 254 } 255 256 private: 257 // TimeFromBytes returns a big-endian uint32 from |d|. 258 static uint32 TimeFromBytes(const uint8 d[4]) { 259 return static_cast<uint32>(d[0]) << 24 | 260 static_cast<uint32>(d[1]) << 16 | 261 static_cast<uint32>(d[2]) << 8 | 262 static_cast<uint32>(d[3]); 263 } 264 265 uint32 ExternalTimeToInternal(uint32 external_time) const { 266 static const uint32 kCreationTimeFromInternalEpoch = 63115200.0; 267 uint32 internal_epoch = 0; 268 if (creation_time_ > kCreationTimeFromInternalEpoch) { 269 internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch; 270 } 271 272 return external_time - internal_epoch; 273 } 274 275 void DropOldestEntry() { 276 set<pair<uint32, string> >::iterator oldest = nonces_.begin(); 277 horizon_ = oldest->first + 1; 278 nonces_.erase(oldest); 279 } 280 281 const unsigned max_entries_; 282 const unsigned window_secs_; 283 const uint32 creation_time_; 284 uint8 orbit_[8]; 285 uint32 horizon_; 286 287 set<pair<uint32, string> > nonces_; 288 }; 289 290 class StrikeRegisterStressTest : public ::testing::Test { 291 }; 292 293 TEST_F(StrikeRegisterStressTest, InOrderInsertion) { 294 // Fixed seed gives reproducibility for this test. 295 srand(42); 296 297 unsigned max_entries = 64; 298 uint32 current_time = 10000, window = 200; 299 scoped_ptr<StrikeRegister> s1( 300 new StrikeRegister(max_entries, current_time, window, kOrbit, 301 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); 302 scoped_ptr<SlowStrikeRegister> s2( 303 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); 304 305 uint64 i; 306 const uint64 kMaxIterations = 10000; 307 for (i = 0; i < kMaxIterations; i++) { 308 const uint32 time = current_time + i; 309 310 uint8 nonce[32]; 311 SetNonce(nonce, time, kOrbit); 312 313 // There are 2048 possible nonce values: 314 const uint32 v = rand() % 2048; 315 nonce[30] = v >> 8; 316 nonce[31] = v; 317 318 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time); 319 const InsertStatus nonce_error1 = s1->Insert(nonce, time); 320 EXPECT_EQ(nonce_error1, nonce_error2); 321 322 // Inserts succeed after the startup period. 323 if (time > current_time + window) { 324 EXPECT_EQ(net::NONCE_OK, nonce_error1); 325 } else { 326 EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, nonce_error1); 327 } 328 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time), 329 s2->GetCurrentValidWindowSecs(time)); 330 331 if (i % 10 == 0) { 332 s1->Validate(); 333 } 334 335 if (HasFailure()) { 336 break; 337 } 338 } 339 340 if (i != kMaxIterations) { 341 FAIL() << "Failed after " << i << " iterations"; 342 } 343 } 344 345 TEST_F(StrikeRegisterStressTest, Stress) { 346 // Fixed seed gives reproducibility for this test. 347 srand(42); 348 unsigned max_entries = 64; 349 uint32 current_time = 10000, window = 200; 350 scoped_ptr<StrikeRegister> s1( 351 new StrikeRegister(max_entries, current_time, window, kOrbit, 352 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); 353 scoped_ptr<SlowStrikeRegister> s2( 354 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); 355 uint64 i; 356 357 // When making changes it's worth removing the limit on this test and running 358 // it for a while. For the initial development an opt binary was left running 359 // for 10 minutes. 360 const uint64 kMaxIterations = 10000; 361 for (i = 0; i < kMaxIterations; i++) { 362 if (rand() % 1000 == 0) { 363 // 0.1% chance of resetting the sets. 364 max_entries = rand() % 300 + 2; 365 current_time = rand() % 10000; 366 window = rand() % 500; 367 s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit, 368 StrikeRegister::DENY_REQUESTS_AT_STARTUP)); 369 s2.reset( 370 new SlowStrikeRegister(max_entries, current_time, window, kOrbit)); 371 } 372 373 int32 time_delta = rand() % (window * 4); 374 time_delta -= window * 2; 375 const uint32 time = current_time + time_delta; 376 if (time_delta < 0 && time > current_time) { 377 continue; // overflow 378 } 379 380 uint8 nonce[32]; 381 SetNonce(nonce, time, kOrbit); 382 383 // There are 2048 possible nonce values: 384 const uint32 v = rand() % 2048; 385 nonce[30] = v >> 8; 386 nonce[31] = v; 387 388 const InsertStatus nonce_error2 = s2->Insert(nonce, time, time); 389 const InsertStatus nonce_error1 = s1->Insert(nonce, time); 390 EXPECT_EQ(nonce_error1, nonce_error2); 391 EXPECT_EQ(s1->GetCurrentValidWindowSecs(time), 392 s2->GetCurrentValidWindowSecs(time)); 393 394 if (i % 10 == 0) { 395 s1->Validate(); 396 } 397 398 if (HasFailure()) { 399 break; 400 } 401 } 402 403 if (i != kMaxIterations) { 404 FAIL() << "Failed after " << i << " iterations"; 405 } 406 } 407 408 } // anonymous namespace 409
