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