net/quic/crypto/strike_register_test.cc

   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 net {
  15
  16 namespace {
  17
  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(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
  44   SetNonce(nonce, 1000, kOrbit);
  45   EXPECT_EQ(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(NONCE_OK, set.Insert(nonce, 1000));
  64   EXPECT_EQ(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(NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
  81   SetNonce(nonce, 999, kOrbit);
  82   EXPECT_EQ(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(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(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(NONCE_OK, set.Insert(nonce, 1101));
 113   EXPECT_EQ(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(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(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(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(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(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(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(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(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 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 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, 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 NONCE_NOT_UNIQUE_FAILURE;
 240     }
 241
 242     nonces_.insert(nonce);
 243     return 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(NONCE_OK, nonce_error1);
 323     } else {
 324       EXPECT_EQ(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 }  // namespace
 407
 408 }  // namespace net