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 {
  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