net/quic/crypto/strike_register_test.cc - chromium/src.git - Git at Google

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "net/quic/crypto/strike_register.h"

 #include <set>
 #include <string>

 #include "base/basictypes.h"
 #include "base/rand_util.h"
 #include "testing/gtest/include/gtest/gtest.h"

 namespace {

 using net::InsertStatus;
 using net::StrikeRegister;
 using std::make_pair;
 using std::min;
 using std::pair;
 using std::set;
 using std::string;

 const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };

 // StrikeRegisterTests don't look at the random bytes so this function can
 // simply set the random bytes to 0.
 void SetNonce(uint8 nonce[32], unsigned time, const uint8 orbit[8]) {
   nonce[0] = time >> 24;
   nonce[1] = time >> 16;
   nonce[2] = time >> 8;
   nonce[3] = time;
   memcpy(nonce + 4, orbit, 8);
   memset(nonce + 12, 0, 20);
 }

 TEST(StrikeRegisterTest, SimpleHorizon) {
   // The set must reject values created on or before its own creation time.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 999, kOrbit);
   EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
   SetNonce(nonce, 1000, kOrbit);
   EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));

   EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */));
   EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */));
   EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */));
   EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */));
   EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */));
   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
 }

 TEST(StrikeRegisterTest, NoStartupMode) {
   // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
   // is specified.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
   uint8 nonce[32];
   SetNonce(nonce, 1000, kOrbit);
   EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1000));
   EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1000));

   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */));
   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */));
   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */));
   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */));
   EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
 }

 TEST(StrikeRegisterTest, WindowFuture) {
   // The set must reject values outside the window.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
   EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
   SetNonce(nonce, 999, kOrbit);
   EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
 }

 TEST(StrikeRegisterTest, BadOrbit) {
   // The set must reject values with the wrong orbit
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 };
   SetNonce(nonce, 1101, kBadOrbit);
   EXPECT_EQ(net::NONCE_INVALID_ORBIT_FAILURE, set.Insert(nonce, 1100));
 }

 TEST(StrikeRegisterTest, OneValue) {
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
   EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
 }

 TEST(StrikeRegisterTest, RejectDuplicate) {
   // The set must reject values with the wrong orbit
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
   EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
   EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1101));
 }

 TEST(StrikeRegisterTest, HorizonUpdating) {
   StrikeRegister::StartupType startup_types[] = {
     StrikeRegister::DENY_REQUESTS_AT_STARTUP,
     StrikeRegister::NO_STARTUP_PERIOD_NEEDED
   };

   for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) {
     StrikeRegister set(5 /* max size */, 500 /* current time */,
                        100 /* window secs */, kOrbit,
                        startup_types[type_idx]);
     uint8 nonce[6][32];
     for (unsigned i = 0; i < 5; i++) {
       SetNonce(nonce[i], 1101 + i, kOrbit);
       nonce[i][31] = i;
       EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[i], 1100));
     }

     // Valid window is still equal to |window_secs + 1|.
     EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100));

     // This should push the oldest value out and force the horizon to
     // be updated.
     SetNonce(nonce[5], 1110, kOrbit);
     EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
     // Effective horizon is computed based on the timestamp of the
     // value that was pushed out.
     EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110));

     SetNonce(nonce[5], 1111, kOrbit);
     EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
     EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110));

     // This should be behind the horizon now:
     SetNonce(nonce[5], 1101, kOrbit);
     nonce[5][31] = 10;
     EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));

     // Insert beyond the valid range.
     SetNonce(nonce[5], 1117, kOrbit);
     nonce[5][31] = 2;
     EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));

     // Insert at the upper valid range.
     SetNonce(nonce[5], 1116, kOrbit);
     nonce[5][31] = 1;
     EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));

     // This should be beyond the upper valid range now:
     SetNonce(nonce[5], 1116, kOrbit);
     nonce[5][31] = 2;
     EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
   }
 }

 TEST(StrikeRegisterTest, InsertMany) {
   StrikeRegister set(5000 /* max size */, 1000 /* current time */,
                      500 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);

   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
   for (unsigned i = 0; i < 100000; i++) {
     SetNonce(nonce, 1101 + i/500, kOrbit);
     memcpy(nonce + 12, &i, sizeof(i));
     EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
   }
 }


 // For the following test we create a slow, but simple, version of a
 // StrikeRegister. The behaviour of this object is much easier to understand
 // than the fully fledged version. We then create a test to show, empirically,
 // that the two objects have identical behaviour.

 // A SlowStrikeRegister has the same public interface as a StrikeRegister, but
 // is much slower. Hopefully it is also more obviously correct and we can
 // empirically test that their behaviours are identical.
 class SlowStrikeRegister {
  public:
   SlowStrikeRegister(unsigned max_entries, uint32 current_time,
                      uint32 window_secs, const uint8 orbit[8])
       : max_entries_(max_entries),
         window_secs_(window_secs),
         creation_time_(current_time),
         horizon_(ExternalTimeToInternal(current_time + window_secs) + 1) {
     memcpy(orbit_, orbit, sizeof(orbit_));
   }

   InsertStatus Insert(const uint8 nonce_bytes[32],
                       const uint32 nonce_time_external,
                       const uint32 current_time_external) {
     if (nonces_.size() == max_entries_) {
       DropOldestEntry();
     }

     const uint32 current_time = ExternalTimeToInternal(current_time_external);

     // Check to see if the orbit is correct.
     if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) {
       return net::NONCE_INVALID_ORBIT_FAILURE;
     }
     const uint32 nonce_time =
         ExternalTimeToInternal(TimeFromBytes(nonce_bytes));
     EXPECT_EQ(ExternalTimeToInternal(nonce_time_external), nonce_time);
     // We have dropped one or more nonces with a time value of |horizon_ - 1|,
     // so we have to reject anything with a timestamp less than or
     // equal to that.
     if (nonce_time < horizon_) {
       return net::NONCE_INVALID_TIME_FAILURE;
     }

     // Check that the timestamp is in the current window.
     if ((current_time > window_secs_ &&
          nonce_time < (current_time - window_secs_)) ||
         nonce_time > (current_time + window_secs_)) {
       return net::NONCE_INVALID_TIME_FAILURE;
     }

     pair<uint32, string> nonce = make_pair(
         nonce_time,
         string(reinterpret_cast<const char*>(nonce_bytes), 32));

     set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce);
     if (it != nonces_.end()) {
       return net::NONCE_NOT_UNIQUE_FAILURE;
     }

     nonces_.insert(nonce);
     return net::NONCE_OK;
   }

   uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const {
     const uint32 current_time = ExternalTimeToInternal(current_time_external);
     if (horizon_ > current_time) {
       return 0;
     }
     return 1 + min(current_time - horizon_, window_secs_);
   }

  private:
   // TimeFromBytes returns a big-endian uint32 from |d|.
   static uint32 TimeFromBytes(const uint8 d[4]) {
     return static_cast<uint32>(d[0]) << 24 |
            static_cast<uint32>(d[1]) << 16 |
            static_cast<uint32>(d[2]) << 8 |
            static_cast<uint32>(d[3]);
   }

   uint32 ExternalTimeToInternal(uint32 external_time) const {
     static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
     uint32 internal_epoch = 0;
     if (creation_time_ > kCreationTimeFromInternalEpoch) {
       internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch;
     }

     return external_time - internal_epoch;
   }

   void DropOldestEntry() {
     set<pair<uint32, string> >::iterator oldest = nonces_.begin();
     horizon_ = oldest->first + 1;
     nonces_.erase(oldest);
   }

   const unsigned max_entries_;
   const unsigned window_secs_;
   const uint32 creation_time_;
   uint8 orbit_[8];
   uint32 horizon_;

   set<pair<uint32, string> > nonces_;
 };

 class StrikeRegisterStressTest : public ::testing::Test {
 };

 TEST_F(StrikeRegisterStressTest, InOrderInsertion) {
   // Fixed seed gives reproducibility for this test.
   srand(42);

   unsigned max_entries = 64;
   uint32 current_time = 10000, window = 200;
   scoped_ptr<StrikeRegister> s1(
       new StrikeRegister(max_entries, current_time, window, kOrbit,
                          StrikeRegister::DENY_REQUESTS_AT_STARTUP));
   scoped_ptr<SlowStrikeRegister> s2(
       new SlowStrikeRegister(max_entries, current_time, window, kOrbit));

   uint64 i;
   const uint64 kMaxIterations = 10000;
   for (i = 0; i < kMaxIterations; i++) {
     const uint32 time = current_time + i;

     uint8 nonce[32];
     SetNonce(nonce, time, kOrbit);

     // There are 2048 possible nonce values:
     const uint32 v = rand() % 2048;
     nonce[30] = v >> 8;
     nonce[31] = v;

     const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
     const InsertStatus nonce_error1 = s1->Insert(nonce, time);
     EXPECT_EQ(nonce_error1, nonce_error2);

     // Inserts succeed after the startup period.
     if (time > current_time + window) {
       EXPECT_EQ(net::NONCE_OK, nonce_error1);
     } else {
       EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, nonce_error1);
     }
     EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
               s2->GetCurrentValidWindowSecs(time));

     if (i % 10 == 0) {
       s1->Validate();
     }

     if (HasFailure()) {
       break;
     }
   }

   if (i != kMaxIterations) {
     FAIL() << "Failed after " << i << " iterations";
   }
 }

 TEST_F(StrikeRegisterStressTest, Stress) {
   // Fixed seed gives reproducibility for this test.
   srand(42);
   unsigned max_entries = 64;
   uint32 current_time = 10000, window = 200;
   scoped_ptr<StrikeRegister> s1(
       new StrikeRegister(max_entries, current_time, window, kOrbit,
                          StrikeRegister::DENY_REQUESTS_AT_STARTUP));
   scoped_ptr<SlowStrikeRegister> s2(
       new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
   uint64 i;

   // When making changes it's worth removing the limit on this test and running
   // it for a while. For the initial development an opt binary was left running
   // for 10 minutes.
   const uint64 kMaxIterations = 10000;
   for (i = 0; i < kMaxIterations; i++) {
     if (rand() % 1000 == 0) {
       // 0.1% chance of resetting the sets.
       max_entries = rand() % 300 + 2;
       current_time = rand() % 10000;
       window = rand() % 500;
       s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit,
                                   StrikeRegister::DENY_REQUESTS_AT_STARTUP));
       s2.reset(
           new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
     }

     int32 time_delta = rand() % (window * 4);
     time_delta -= window * 2;
     const uint32 time = current_time + time_delta;
     if (time_delta < 0 && time > current_time) {
       continue;  // overflow
     }

     uint8 nonce[32];
     SetNonce(nonce, time, kOrbit);

     // There are 2048 possible nonce values:
     const uint32 v = rand() % 2048;
     nonce[30] = v >> 8;
     nonce[31] = v;

     const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
     const InsertStatus nonce_error1 = s1->Insert(nonce, time);
     EXPECT_EQ(nonce_error1, nonce_error2);
     EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
               s2->GetCurrentValidWindowSecs(time));

     if (i % 10 == 0) {
       s1->Validate();
     }

     if (HasFailure()) {
       break;
     }
   }

   if (i != kMaxIterations) {
     FAIL() << "Failed after " << i << " iterations";
   }
 }

 }  // anonymous namespace
	// Copyright (c) 2013 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "net/quic/crypto/strike_register.h"

	#include <set>
	#include <string>

	#include "base/basictypes.h"
	#include "base/rand_util.h"
	#include "testing/gtest/include/gtest/gtest.h"

	namespace {

	using net::InsertStatus;
	using net::StrikeRegister;
	using std::make_pair;
	using std::min;
	using std::pair;
	using std::set;
	using std::string;

	const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };

	// StrikeRegisterTests don't look at the random bytes so this function can
	// simply set the random bytes to 0.
	void SetNonce(uint8 nonce[32], unsigned time, const uint8 orbit[8]) {
	nonce[0] = time >> 24;
	nonce[1] = time >> 16;
	nonce[2] = time >> 8;
	nonce[3] = time;
	memcpy(nonce + 4, orbit, 8);
	memset(nonce + 12, 0, 20);
	}

	TEST(StrikeRegisterTest, SimpleHorizon) {
	// The set must reject values created on or before its own creation time.
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);
	uint8 nonce[32];
	SetNonce(nonce, 999, kOrbit);
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
	SetNonce(nonce, 1000, kOrbit);
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));

	EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */));
	EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */));
	EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */));
	EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */));
	EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */));
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
	}

	TEST(StrikeRegisterTest, NoStartupMode) {
	// Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
	// is specified.
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
	uint8 nonce[32];
	SetNonce(nonce, 1000, kOrbit);
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1000));
	EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1000));

	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */));
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */));
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */));
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */));
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
	}

	TEST(StrikeRegisterTest, WindowFuture) {
	// The set must reject values outside the window.
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);
	uint8 nonce[32];
	SetNonce(nonce, 1101, kOrbit);
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
	SetNonce(nonce, 999, kOrbit);
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
	}

	TEST(StrikeRegisterTest, BadOrbit) {
	// The set must reject values with the wrong orbit
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);
	uint8 nonce[32];
	static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 };
	SetNonce(nonce, 1101, kBadOrbit);
	EXPECT_EQ(net::NONCE_INVALID_ORBIT_FAILURE, set.Insert(nonce, 1100));
	}

	TEST(StrikeRegisterTest, OneValue) {
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);
	uint8 nonce[32];
	SetNonce(nonce, 1101, kOrbit);
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
	}

	TEST(StrikeRegisterTest, RejectDuplicate) {
	// The set must reject values with the wrong orbit
	StrikeRegister set(10 /* max size /, 1000 / current time */,
	100 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);
	uint8 nonce[32];
	SetNonce(nonce, 1101, kOrbit);
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
	EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1101));
	}

	TEST(StrikeRegisterTest, HorizonUpdating) {
	StrikeRegister::StartupType startup_types[] = {
	StrikeRegister::DENY_REQUESTS_AT_STARTUP,
	StrikeRegister::NO_STARTUP_PERIOD_NEEDED
	};

	for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) {
	StrikeRegister set(5 /* max size /, 500 / current time */,
	100 /* window secs */, kOrbit,
	startup_types[type_idx]);
	uint8 nonce[6][32];
	for (unsigned i = 0; i < 5; i++) {
	SetNonce(nonce[i], 1101 + i, kOrbit);
	nonce[i][31] = i;
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[i], 1100));
	}

	// Valid window is still equal to \|window_secs + 1\|.
	EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100));

	// This should push the oldest value out and force the horizon to
	// be updated.
	SetNonce(nonce[5], 1110, kOrbit);
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
	// Effective horizon is computed based on the timestamp of the
	// value that was pushed out.
	EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110));

	SetNonce(nonce[5], 1111, kOrbit);
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
	EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110));

	// This should be behind the horizon now:
	SetNonce(nonce[5], 1101, kOrbit);
	nonce[5][31] = 10;
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));

	// Insert beyond the valid range.
	SetNonce(nonce[5], 1117, kOrbit);
	nonce[5][31] = 2;
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));

	// Insert at the upper valid range.
	SetNonce(nonce[5], 1116, kOrbit);
	nonce[5][31] = 1;
	EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));

	// This should be beyond the upper valid range now:
	SetNonce(nonce[5], 1116, kOrbit);
	nonce[5][31] = 2;
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
	}
	}

	TEST(StrikeRegisterTest, InsertMany) {
	StrikeRegister set(5000 /* max size /, 1000 / current time */,
	500 /* window secs */, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP);

	uint8 nonce[32];
	SetNonce(nonce, 1101, kOrbit);
	for (unsigned i = 0; i < 100000; i++) {
	SetNonce(nonce, 1101 + i/500, kOrbit);
	memcpy(nonce + 12, &i, sizeof(i));
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
	}
	}


	// For the following test we create a slow, but simple, version of a
	// StrikeRegister. The behaviour of this object is much easier to understand
	// than the fully fledged version. We then create a test to show, empirically,
	// that the two objects have identical behaviour.

	// A SlowStrikeRegister has the same public interface as a StrikeRegister, but
	// is much slower. Hopefully it is also more obviously correct and we can
	// empirically test that their behaviours are identical.
	class SlowStrikeRegister {
	public:
	SlowStrikeRegister(unsigned max_entries, uint32 current_time,
	uint32 window_secs, const uint8 orbit[8])
	: max_entries_(max_entries),
	window_secs_(window_secs),
	creation_time_(current_time),
	horizon_(ExternalTimeToInternal(current_time + window_secs) + 1) {
	memcpy(orbit_, orbit, sizeof(orbit_));
	}

	InsertStatus Insert(const uint8 nonce_bytes[32],
	const uint32 nonce_time_external,
	const uint32 current_time_external) {
	if (nonces_.size() == max_entries_) {
	DropOldestEntry();
	}

	const uint32 current_time = ExternalTimeToInternal(current_time_external);

	// Check to see if the orbit is correct.
	if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) {
	return net::NONCE_INVALID_ORBIT_FAILURE;
	}
	const uint32 nonce_time =
	ExternalTimeToInternal(TimeFromBytes(nonce_bytes));
	EXPECT_EQ(ExternalTimeToInternal(nonce_time_external), nonce_time);
	// We have dropped one or more nonces with a time value of \|horizon_ - 1\|,
	// so we have to reject anything with a timestamp less than or
	// equal to that.
	if (nonce_time < horizon_) {
	return net::NONCE_INVALID_TIME_FAILURE;
	}

	// Check that the timestamp is in the current window.
	if ((current_time > window_secs_ &&
	nonce_time < (current_time - window_secs_)) \|\|
	nonce_time > (current_time + window_secs_)) {
	return net::NONCE_INVALID_TIME_FAILURE;
	}

	pair<uint32, string> nonce = make_pair(
	nonce_time,
	string(reinterpret_cast<const char*>(nonce_bytes), 32));

	set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce);
	if (it != nonces_.end()) {
	return net::NONCE_NOT_UNIQUE_FAILURE;
	}

	nonces_.insert(nonce);
	return net::NONCE_OK;
	}

	uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const {
	const uint32 current_time = ExternalTimeToInternal(current_time_external);
	if (horizon_ > current_time) {
	return 0;
	}
	return 1 + min(current_time - horizon_, window_secs_);
	}

	private:
	// TimeFromBytes returns a big-endian uint32 from \|d\|.
	static uint32 TimeFromBytes(const uint8 d[4]) {
	return static_cast<uint32>(d[0]) << 24 \|
	static_cast<uint32>(d[1]) << 16 \|
	static_cast<uint32>(d[2]) << 8 \|
	static_cast<uint32>(d[3]);
	}

	uint32 ExternalTimeToInternal(uint32 external_time) const {
	static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
	uint32 internal_epoch = 0;
	if (creation_time_ > kCreationTimeFromInternalEpoch) {
	internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch;
	}

	return external_time - internal_epoch;
	}

	void DropOldestEntry() {
	set<pair<uint32, string> >::iterator oldest = nonces_.begin();
	horizon_ = oldest->first + 1;
	nonces_.erase(oldest);
	}

	const unsigned max_entries_;
	const unsigned window_secs_;
	const uint32 creation_time_;
	uint8 orbit_[8];
	uint32 horizon_;

	set<pair<uint32, string> > nonces_;
	};

	class StrikeRegisterStressTest : public ::testing::Test {
	};

	TEST_F(StrikeRegisterStressTest, InOrderInsertion) {
	// Fixed seed gives reproducibility for this test.
	srand(42);

	unsigned max_entries = 64;
	uint32 current_time = 10000, window = 200;
	scoped_ptr<StrikeRegister> s1(
	new StrikeRegister(max_entries, current_time, window, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP));
	scoped_ptr<SlowStrikeRegister> s2(
	new SlowStrikeRegister(max_entries, current_time, window, kOrbit));

	uint64 i;
	const uint64 kMaxIterations = 10000;
	for (i = 0; i < kMaxIterations; i++) {
	const uint32 time = current_time + i;

	uint8 nonce[32];
	SetNonce(nonce, time, kOrbit);

	// There are 2048 possible nonce values:
	const uint32 v = rand() % 2048;
	nonce[30] = v >> 8;
	nonce[31] = v;

	const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
	const InsertStatus nonce_error1 = s1->Insert(nonce, time);
	EXPECT_EQ(nonce_error1, nonce_error2);

	// Inserts succeed after the startup period.
	if (time > current_time + window) {
	EXPECT_EQ(net::NONCE_OK, nonce_error1);
	} else {
	EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, nonce_error1);
	}
	EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
	s2->GetCurrentValidWindowSecs(time));

	if (i % 10 == 0) {
	s1->Validate();
	}

	if (HasFailure()) {
	break;
	}
	}

	if (i != kMaxIterations) {
	FAIL() << "Failed after " << i << " iterations";
	}
	}

	TEST_F(StrikeRegisterStressTest, Stress) {
	// Fixed seed gives reproducibility for this test.
	srand(42);
	unsigned max_entries = 64;
	uint32 current_time = 10000, window = 200;
	scoped_ptr<StrikeRegister> s1(
	new StrikeRegister(max_entries, current_time, window, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP));
	scoped_ptr<SlowStrikeRegister> s2(
	new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
	uint64 i;

	// When making changes it's worth removing the limit on this test and running
	// it for a while. For the initial development an opt binary was left running
	// for 10 minutes.
	const uint64 kMaxIterations = 10000;
	for (i = 0; i < kMaxIterations; i++) {
	if (rand() % 1000 == 0) {
	// 0.1% chance of resetting the sets.
	max_entries = rand() % 300 + 2;
	current_time = rand() % 10000;
	window = rand() % 500;
	s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit,
	StrikeRegister::DENY_REQUESTS_AT_STARTUP));
	s2.reset(
	new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
	}

	int32 time_delta = rand() % (window * 4);
	time_delta -= window * 2;
	const uint32 time = current_time + time_delta;
	if (time_delta < 0 && time > current_time) {
	continue; // overflow
	}

	uint8 nonce[32];
	SetNonce(nonce, time, kOrbit);

	// There are 2048 possible nonce values:
	const uint32 v = rand() % 2048;
	nonce[30] = v >> 8;
	nonce[31] = v;

	const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
	const InsertStatus nonce_error1 = s1->Insert(nonce, time);
	EXPECT_EQ(nonce_error1, nonce_error2);
	EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
	s2->GetCurrentValidWindowSecs(time));

	if (i % 10 == 0) {
	s1->Validate();
	}

	if (HasFailure()) {
	break;
	}
	}

	if (i != kMaxIterations) {
	FAIL() << "Failed after " << i << " iterations";
	}
	}

	} // anonymous namespace