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 "testing/gtest/include/gtest/gtest.h"
  12
  13 namespace {
  14
  15 using net::StrikeRegister;
  16 using std::set;
  17 using std::string;
  18
  19 const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  20
  21 // StrikeRegisterTests don't look at the random bytes so this function can
  22 // simply set the random bytes to 0.
  23 void SetNonce(uint8 nonce[32], unsigned time, const uint8 orbit[8]) {
  24   nonce[0] = time >> 24;
  25   nonce[1] = time >> 16;
  26   nonce[2] = time >> 8;
  27   nonce[3] = time;
  28   memcpy(nonce + 4, orbit, 8);
  29   memset(nonce + 12, 0, 20);
  30 }
  31
  32 TEST(StrikeRegisterTest, SimpleHorizon) {
  33   // The set must reject values created on or before its own creation time.
  34   StrikeRegister set(10 /* max size */, 1000 /* current time */,
  35                      100 /* window secs */, kOrbit,
  36                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
  37   uint8 nonce[32];
  38   SetNonce(nonce, 999, kOrbit);
  39   ASSERT_FALSE(set.Insert(nonce, 1000));
  40   SetNonce(nonce, 1000, kOrbit);
  41   ASSERT_FALSE(set.Insert(nonce, 1000));
  42 }
  43
  44 TEST(StrikeRegisterTest, NoStartupMode) {
  45   // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
  46   // is specified.
  47   StrikeRegister set(10 /* max size */, 0 /* current time */,
  48                      100 /* window secs */, kOrbit,
  49                      StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
  50   uint8 nonce[32];
  51   SetNonce(nonce, 0, kOrbit);
  52   ASSERT_TRUE(set.Insert(nonce, 0));
  53   ASSERT_FALSE(set.Insert(nonce, 0));
  54 }
  55
  56 TEST(StrikeRegisterTest, WindowFuture) {
  57   // The set must reject values outside the window.
  58   StrikeRegister set(10 /* max size */, 1000 /* current time */,
  59                      100 /* window secs */, kOrbit,
  60                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
  61   uint8 nonce[32];
  62   SetNonce(nonce, 1101, kOrbit);
  63   ASSERT_FALSE(set.Insert(nonce, 1000));
  64   SetNonce(nonce, 999, kOrbit);
  65   ASSERT_FALSE(set.Insert(nonce, 1100));
  66 }
  67
  68 TEST(StrikeRegisterTest, BadOrbit) {
  69   // The set must reject values with the wrong orbit
  70   StrikeRegister set(10 /* max size */, 1000 /* current time */,
  71                      100 /* window secs */, kOrbit,
  72                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
  73   uint8 nonce[32];
  74   static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 };
  75   SetNonce(nonce, 1101, kBadOrbit);
  76   ASSERT_FALSE(set.Insert(nonce, 1100));
  77 }
  78
  79 TEST(StrikeRegisterTest, OneValue) {
  80   StrikeRegister set(10 /* max size */, 1000 /* current time */,
  81                      100 /* window secs */, kOrbit,
  82                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
  83   uint8 nonce[32];
  84   SetNonce(nonce, 1101, kOrbit);
  85   ASSERT_TRUE(set.Insert(nonce, 1100));
  86 }
  87
  88 TEST(StrikeRegisterTest, RejectDuplicate) {
  89   // The set must reject values with the wrong orbit
  90   StrikeRegister set(10 /* max size */, 1000 /* current time */,
  91                      100 /* window secs */, kOrbit,
  92                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
  93   uint8 nonce[32];
  94   SetNonce(nonce, 1101, kOrbit);
  95   ASSERT_TRUE(set.Insert(nonce, 1100));
  96   ASSERT_FALSE(set.Insert(nonce, 1100));
  97 }
  98
  99 TEST(StrikeRegisterTest, HorizonUpdating) {
 100   StrikeRegister set(5 /* max size */, 1000 /* current time */,
 101                      100 /* window secs */, kOrbit,
 102                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
 103   uint8 nonce[6][32];
 104   for (unsigned i = 0; i < 5; i++) {
 105     SetNonce(nonce[i], 1101, kOrbit);
 106     nonce[i][31] = i;
 107     ASSERT_TRUE(set.Insert(nonce[i], 1100));
 108   }
 109
 110   // This should push the oldest value out and force the horizon to be updated.
 111   SetNonce(nonce[5], 1102, kOrbit);
 112   ASSERT_TRUE(set.Insert(nonce[5], 1100));
 113
 114   // This should be behind the horizon now:
 115   SetNonce(nonce[5], 1101, kOrbit);
 116   nonce[5][31] = 10;
 117   ASSERT_FALSE(set.Insert(nonce[5], 1100));
 118 }
 119
 120 TEST(StrikeRegisterTest, InsertMany) {
 121   StrikeRegister set(5000 /* max size */, 1000 /* current time */,
 122                      500 /* window secs */, kOrbit,
 123                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
 124
 125   uint8 nonce[32];
 126   SetNonce(nonce, 1101, kOrbit);
 127   for (unsigned i = 0; i < 100000; i++) {
 128     SetNonce(nonce, 1101 + i/500, kOrbit);
 129     memcpy(nonce + 12, &i, sizeof(i));
 130     set.Insert(nonce, 1100);
 131   }
 132 }
 133
 134
 135 // For the following test we create a slow, but simple, version of a
 136 // StrikeRegister. The behaviour of this object is much easier to understand
 137 // than the fully fledged version. We then create a test to show, empirically,
 138 // that the two objects have identical behaviour.
 139
 140 // A SlowStrikeRegister has the same public interface as a StrikeRegister, but
 141 // is much slower. Hopefully it is also more obviously correct and we can
 142 // empirically test that their behaviours are identical.
 143 class SlowStrikeRegister {
 144  public:
 145   SlowStrikeRegister(unsigned max_entries, uint32 current_time,
 146                      uint32 window_secs, const uint8 orbit[8])
 147       : max_entries_(max_entries),
 148         window_secs_(window_secs),
 149         creation_time_(current_time),
 150         horizon_(ExternalTimeToInternal(current_time + window_secs)) {
 151     memcpy(orbit_, orbit, sizeof(orbit_));
 152   }
 153
 154   bool Insert(const uint8 nonce_bytes[32], const uint32 current_time_external) {
 155     const uint32 current_time = ExternalTimeToInternal(current_time_external);
 156
 157     // Check to see if the orbit is correct.
 158     if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) {
 159       return false;
 160     }
 161     const uint32 nonce_time =
 162         ExternalTimeToInternal(TimeFromBytes(nonce_bytes));
 163     // We have dropped one or more nonces with a time value of |horizon_|, so
 164     // we have to reject anything with a timestamp less than or equal to that.
 165     if (nonce_time <= horizon_) {
 166       return false;
 167     }
 168
 169     // Check that the timestamp is in the current window.
 170     if ((current_time > window_secs_ &&
 171          nonce_time < (current_time - window_secs_)) ||
 172         nonce_time > (current_time + window_secs_)) {
 173       return false;
 174     }
 175
 176     string nonce;
 177     nonce.reserve(32);
 178     nonce +=
 179         string(reinterpret_cast<const char*>(&nonce_time), sizeof(nonce_time));
 180     nonce +=
 181         string(reinterpret_cast<const char*>(nonce_bytes) + sizeof(nonce_time),
 182                32 - sizeof(nonce_time));
 183
 184     set<string>::const_iterator it = nonces_.find(nonce);
 185     if (it != nonces_.end()) {
 186       return false;
 187     }
 188
 189     if (nonces_.size() == max_entries_) {
 190       DropOldestEntry();
 191     }
 192
 193     nonces_.insert(nonce);
 194     return true;
 195   }
 196
 197  private:
 198   // TimeFromBytes returns a big-endian uint32 from |d|.
 199   static uint32 TimeFromBytes(const uint8 d[4]) {
 200     return static_cast<uint32>(d[0]) << 24 |
 201            static_cast<uint32>(d[1]) << 16 |
 202            static_cast<uint32>(d[2]) << 8 |
 203            static_cast<uint32>(d[3]);
 204   }
 205
 206   uint32 ExternalTimeToInternal(uint32 external_time) {
 207     static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
 208     uint32 internal_epoch = 0;
 209     if (creation_time_ > kCreationTimeFromInternalEpoch) {
 210       internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch;
 211     }
 212
 213     return external_time - internal_epoch;
 214   }
 215
 216   void DropOldestEntry() {
 217     set<string>::iterator oldest = nonces_.begin(), it;
 218     uint32 oldest_time =
 219         TimeFromBytes(reinterpret_cast<const uint8*>(oldest->data()));
 220
 221     for (it = oldest; it != nonces_.end(); it++) {
 222       uint32 t = TimeFromBytes(reinterpret_cast<const uint8*>(it->data()));
 223       if (t < oldest_time ||
 224           (t == oldest_time && memcmp(it->data(), oldest->data(), 32) < 0)) {
 225         oldest_time = t;
 226         oldest = it;
 227       }
 228     }
 229
 230     nonces_.erase(oldest);
 231     horizon_ = oldest_time;
 232   }
 233
 234   const unsigned max_entries_;
 235   const unsigned window_secs_;
 236   const uint32 creation_time_;
 237   uint8 orbit_[8];
 238   uint32 horizon_;
 239
 240   set<string> nonces_;
 241 };
 242
 243 TEST(StrikeRegisterStressTest, Stress) {
 244   // Fixed seed gives reproducibility for this test.
 245   srand(42);
 246   unsigned max_entries = 64;
 247   uint32 current_time = 10000, window = 200;
 248   scoped_ptr<StrikeRegister> s1(
 249       new StrikeRegister(max_entries, current_time, window, kOrbit,
 250                          StrikeRegister::DENY_REQUESTS_AT_STARTUP));
 251   scoped_ptr<SlowStrikeRegister> s2(
 252       new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
 253   uint64 i;
 254
 255   // When making changes it's worth removing the limit on this test and running
 256   // it for a while. For the initial development an opt binary was left running
 257   // for 10 minutes.
 258   const uint64 kMaxIterations = 10000;
 259   for (i = 0; i < kMaxIterations; i++) {
 260     if (rand() % 1000 == 0) {
 261       // 0.1% chance of resetting the sets.
 262       max_entries = rand() % 300 + 2;
 263       current_time = rand() % 10000;
 264       window = rand() % 500;
 265       s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit,
 266                                   StrikeRegister::DENY_REQUESTS_AT_STARTUP));
 267       s2.reset(
 268           new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
 269     }
 270
 271     int32 time_delta = rand() % (window * 4);
 272     time_delta -= window * 2;
 273     const uint32 time = current_time + time_delta;
 274     if (time_delta < 0 && time > current_time) {
 275       continue;  // overflow
 276     }
 277
 278     uint8 nonce[32];
 279     SetNonce(nonce, time, kOrbit);
 280
 281     // There are 2048 possible nonce values:
 282     const uint32 v = rand() % 2048;
 283     nonce[30] = v >> 8;
 284     nonce[31] = v;
 285
 286     const bool r2 = s2->Insert(nonce, time);
 287     const bool r1 = s1->Insert(nonce, time);
 288
 289     if (r1 != r2) {
 290       break;
 291     }
 292
 293     if (i % 10 == 0) {
 294       s1->Validate();
 295     }
 296   }
 297
 298   if (i != kMaxIterations) {
 299     FAIL() << "Failed after " << i << " iterations";
 300   }
 301 }
 302
 303 }  // anonymous namespace