diff options
Diffstat (limited to 'chromium/net/quic/crypto/strike_register_test.cc')
-rw-r--r-- | chromium/net/quic/crypto/strike_register_test.cc | 303 |
1 files changed, 303 insertions, 0 deletions
diff --git a/chromium/net/quic/crypto/strike_register_test.cc b/chromium/net/quic/crypto/strike_register_test.cc new file mode 100644 index 00000000000..ddfa96535de --- /dev/null +++ b/chromium/net/quic/crypto/strike_register_test.cc @@ -0,0 +1,303 @@ +// 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 "testing/gtest/include/gtest/gtest.h" + +namespace { + +using net::StrikeRegister; +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); + ASSERT_FALSE(set.Insert(nonce, 1000)); + SetNonce(nonce, 1000, kOrbit); + ASSERT_FALSE(set.Insert(nonce, 1000)); +} + +TEST(StrikeRegisterTest, NoStartupMode) { + // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED + // is specified. + StrikeRegister set(10 /* max size */, 0 /* current time */, + 100 /* window secs */, kOrbit, + StrikeRegister::NO_STARTUP_PERIOD_NEEDED); + uint8 nonce[32]; + SetNonce(nonce, 0, kOrbit); + ASSERT_TRUE(set.Insert(nonce, 0)); + ASSERT_FALSE(set.Insert(nonce, 0)); +} + +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); + ASSERT_FALSE(set.Insert(nonce, 1000)); + SetNonce(nonce, 999, kOrbit); + ASSERT_FALSE(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); + ASSERT_FALSE(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); + ASSERT_TRUE(set.Insert(nonce, 1100)); +} + +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); + ASSERT_TRUE(set.Insert(nonce, 1100)); + ASSERT_FALSE(set.Insert(nonce, 1100)); +} + +TEST(StrikeRegisterTest, HorizonUpdating) { + StrikeRegister set(5 /* max size */, 1000 /* current time */, + 100 /* window secs */, kOrbit, + StrikeRegister::DENY_REQUESTS_AT_STARTUP); + uint8 nonce[6][32]; + for (unsigned i = 0; i < 5; i++) { + SetNonce(nonce[i], 1101, kOrbit); + nonce[i][31] = i; + ASSERT_TRUE(set.Insert(nonce[i], 1100)); + } + + // This should push the oldest value out and force the horizon to be updated. + SetNonce(nonce[5], 1102, kOrbit); + ASSERT_TRUE(set.Insert(nonce[5], 1100)); + + // This should be behind the horizon now: + SetNonce(nonce[5], 1101, kOrbit); + nonce[5][31] = 10; + ASSERT_FALSE(set.Insert(nonce[5], 1100)); +} + +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)); + 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)) { + memcpy(orbit_, orbit, sizeof(orbit_)); + } + + bool Insert(const uint8 nonce_bytes[32], const uint32 current_time_external) { + 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 false; + } + const uint32 nonce_time = + ExternalTimeToInternal(TimeFromBytes(nonce_bytes)); + // We have dropped one or more nonces with a time value of |horizon_|, so + // we have to reject anything with a timestamp less than or equal to that. + if (nonce_time <= horizon_) { + return false; + } + + // 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 false; + } + + string nonce; + nonce.reserve(32); + nonce += + string(reinterpret_cast<const char*>(&nonce_time), sizeof(nonce_time)); + nonce += + string(reinterpret_cast<const char*>(nonce_bytes) + sizeof(nonce_time), + 32 - sizeof(nonce_time)); + + set<string>::const_iterator it = nonces_.find(nonce); + if (it != nonces_.end()) { + return false; + } + + if (nonces_.size() == max_entries_) { + DropOldestEntry(); + } + + nonces_.insert(nonce); + return true; + } + + 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) { + 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<string>::iterator oldest = nonces_.begin(), it; + uint32 oldest_time = + TimeFromBytes(reinterpret_cast<const uint8*>(oldest->data())); + + for (it = oldest; it != nonces_.end(); it++) { + uint32 t = TimeFromBytes(reinterpret_cast<const uint8*>(it->data())); + if (t < oldest_time || + (t == oldest_time && memcmp(it->data(), oldest->data(), 32) < 0)) { + oldest_time = t; + oldest = it; + } + } + + nonces_.erase(oldest); + horizon_ = oldest_time; + } + + const unsigned max_entries_; + const unsigned window_secs_; + const uint32 creation_time_; + uint8 orbit_[8]; + uint32 horizon_; + + set<string> nonces_; +}; + +TEST(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 bool r2 = s2->Insert(nonce, time); + const bool r1 = s1->Insert(nonce, time); + + if (r1 != r2) { + break; + } + + if (i % 10 == 0) { + s1->Validate(); + } + } + + if (i != kMaxIterations) { + FAIL() << "Failed after " << i << " iterations"; + } +} + +} // anonymous namespace |