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 |