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 304
