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 "base/rand_util.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14namespace {
15
16using net::InsertStatus;
17using net::StrikeRegister;
18using std::make_pair;
19using std::min;
20using std::pair;
21using std::set;
22using std::string;
23
24const uint8 kOrbit[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
25
26// StrikeRegisterTests don't look at the random bytes so this function can
27// simply set the random bytes to 0.
28void SetNonce(uint8 nonce[32], unsigned time, const uint8 orbit[8]) {
29  nonce[0] = time >> 24;
30  nonce[1] = time >> 16;
31  nonce[2] = time >> 8;
32  nonce[3] = time;
33  memcpy(nonce + 4, orbit, 8);
34  memset(nonce + 12, 0, 20);
35}
36
37TEST(StrikeRegisterTest, SimpleHorizon) {
38  // The set must reject values created on or before its own creation time.
39  StrikeRegister set(10 /* max size */, 1000 /* current time */,
40                     100 /* window secs */, kOrbit,
41                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
42  uint8 nonce[32];
43  SetNonce(nonce, 999, kOrbit);
44  EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
45  SetNonce(nonce, 1000, kOrbit);
46  EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
47
48  EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */));
49  EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */));
50  EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */));
51  EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */));
52  EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */));
53  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
54}
55
56TEST(StrikeRegisterTest, NoStartupMode) {
57  // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
58  // is specified.
59  StrikeRegister set(10 /* max size */, 1000 /* current time */,
60                     100 /* window secs */, kOrbit,
61                     StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
62  uint8 nonce[32];
63  SetNonce(nonce, 1000, kOrbit);
64  EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1000));
65  EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1000));
66
67  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */));
68  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */));
69  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */));
70  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */));
71  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
72}
73
74TEST(StrikeRegisterTest, WindowFuture) {
75  // The set must reject values outside the window.
76  StrikeRegister set(10 /* max size */, 1000 /* current time */,
77                     100 /* window secs */, kOrbit,
78                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
79  uint8 nonce[32];
80  SetNonce(nonce, 1101, kOrbit);
81  EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1000));
82  SetNonce(nonce, 999, kOrbit);
83  EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
84}
85
86TEST(StrikeRegisterTest, BadOrbit) {
87  // The set must reject values with the wrong orbit
88  StrikeRegister set(10 /* max size */, 1000 /* current time */,
89                     100 /* window secs */, kOrbit,
90                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
91  uint8 nonce[32];
92  static const uint8 kBadOrbit[8] = { 0, 0, 0, 0, 1, 1, 1, 1 };
93  SetNonce(nonce, 1101, kBadOrbit);
94  EXPECT_EQ(net::NONCE_INVALID_ORBIT_FAILURE, set.Insert(nonce, 1100));
95}
96
97TEST(StrikeRegisterTest, OneValue) {
98  StrikeRegister set(10 /* max size */, 1000 /* current time */,
99                     100 /* window secs */, kOrbit,
100                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
101  uint8 nonce[32];
102  SetNonce(nonce, 1101, kOrbit);
103  EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
104}
105
106TEST(StrikeRegisterTest, RejectDuplicate) {
107  // The set must reject values with the wrong orbit
108  StrikeRegister set(10 /* max size */, 1000 /* current time */,
109                     100 /* window secs */, kOrbit,
110                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
111  uint8 nonce[32];
112  SetNonce(nonce, 1101, kOrbit);
113  EXPECT_EQ(net::NONCE_OK, set.Insert(nonce, 1101));
114  EXPECT_EQ(net::NONCE_NOT_UNIQUE_FAILURE, set.Insert(nonce, 1101));
115}
116
117TEST(StrikeRegisterTest, HorizonUpdating) {
118  StrikeRegister::StartupType startup_types[] = {
119    StrikeRegister::DENY_REQUESTS_AT_STARTUP,
120    StrikeRegister::NO_STARTUP_PERIOD_NEEDED
121  };
122
123  for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) {
124    StrikeRegister set(5 /* max size */, 500 /* current time */,
125                       100 /* window secs */, kOrbit,
126                       startup_types[type_idx]);
127    uint8 nonce[6][32];
128    for (unsigned i = 0; i < 5; i++) {
129      SetNonce(nonce[i], 1101 + i, kOrbit);
130      nonce[i][31] = i;
131      EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[i], 1100));
132    }
133
134    // Valid window is still equal to |window_secs + 1|.
135    EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100));
136
137    // This should push the oldest value out and force the horizon to
138    // be updated.
139    SetNonce(nonce[5], 1110, kOrbit);
140    EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
141    // Effective horizon is computed based on the timestamp of the
142    // value that was pushed out.
143    EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110));
144
145    SetNonce(nonce[5], 1111, kOrbit);
146    EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
147    EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110));
148
149    // This should be behind the horizon now:
150    SetNonce(nonce[5], 1101, kOrbit);
151    nonce[5][31] = 10;
152    EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
153
154    // Insert beyond the valid range.
155    SetNonce(nonce[5], 1117, kOrbit);
156    nonce[5][31] = 2;
157    EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
158
159    // Insert at the upper valid range.
160    SetNonce(nonce[5], 1116, kOrbit);
161    nonce[5][31] = 1;
162    EXPECT_EQ(net::NONCE_OK, set.Insert(nonce[5], 1110));
163
164    // This should be beyond the upper valid range now:
165    SetNonce(nonce[5], 1116, kOrbit);
166    nonce[5][31] = 2;
167    EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce[5], 1110));
168  }
169}
170
171TEST(StrikeRegisterTest, InsertMany) {
172  StrikeRegister set(5000 /* max size */, 1000 /* current time */,
173                     500 /* window secs */, kOrbit,
174                     StrikeRegister::DENY_REQUESTS_AT_STARTUP);
175
176  uint8 nonce[32];
177  SetNonce(nonce, 1101, kOrbit);
178  for (unsigned i = 0; i < 100000; i++) {
179    SetNonce(nonce, 1101 + i/500, kOrbit);
180    memcpy(nonce + 12, &i, sizeof(i));
181    EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, set.Insert(nonce, 1100));
182  }
183}
184
185
186// For the following test we create a slow, but simple, version of a
187// StrikeRegister. The behaviour of this object is much easier to understand
188// than the fully fledged version. We then create a test to show, empirically,
189// that the two objects have identical behaviour.
190
191// A SlowStrikeRegister has the same public interface as a StrikeRegister, but
192// is much slower. Hopefully it is also more obviously correct and we can
193// empirically test that their behaviours are identical.
194class SlowStrikeRegister {
195 public:
196  SlowStrikeRegister(unsigned max_entries, uint32 current_time,
197                     uint32 window_secs, const uint8 orbit[8])
198      : max_entries_(max_entries),
199        window_secs_(window_secs),
200        creation_time_(current_time),
201        horizon_(ExternalTimeToInternal(current_time + window_secs) + 1) {
202    memcpy(orbit_, orbit, sizeof(orbit_));
203  }
204
205  InsertStatus Insert(const uint8 nonce_bytes[32],
206                      const uint32 nonce_time_external,
207                      const uint32 current_time_external) {
208    if (nonces_.size() == max_entries_) {
209      DropOldestEntry();
210    }
211
212    const uint32 current_time = ExternalTimeToInternal(current_time_external);
213
214    // Check to see if the orbit is correct.
215    if (memcmp(nonce_bytes + 4, orbit_, sizeof(orbit_))) {
216      return net::NONCE_INVALID_ORBIT_FAILURE;
217    }
218    const uint32 nonce_time =
219        ExternalTimeToInternal(TimeFromBytes(nonce_bytes));
220    EXPECT_EQ(ExternalTimeToInternal(nonce_time_external), nonce_time);
221    // We have dropped one or more nonces with a time value of |horizon_ - 1|,
222    // so we have to reject anything with a timestamp less than or
223    // equal to that.
224    if (nonce_time < horizon_) {
225      return net::NONCE_INVALID_TIME_FAILURE;
226    }
227
228    // Check that the timestamp is in the current window.
229    if ((current_time > window_secs_ &&
230         nonce_time < (current_time - window_secs_)) ||
231        nonce_time > (current_time + window_secs_)) {
232      return net::NONCE_INVALID_TIME_FAILURE;
233    }
234
235    pair<uint32, string> nonce = make_pair(
236        nonce_time,
237        string(reinterpret_cast<const char*>(nonce_bytes), 32));
238
239    set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce);
240    if (it != nonces_.end()) {
241      return net::NONCE_NOT_UNIQUE_FAILURE;
242    }
243
244    nonces_.insert(nonce);
245    return net::NONCE_OK;
246  }
247
248  uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const {
249    const uint32 current_time = ExternalTimeToInternal(current_time_external);
250    if (horizon_ > current_time) {
251      return 0;
252    }
253    return 1 + min(current_time - horizon_, window_secs_);
254  }
255
256 private:
257  // TimeFromBytes returns a big-endian uint32 from |d|.
258  static uint32 TimeFromBytes(const uint8 d[4]) {
259    return static_cast<uint32>(d[0]) << 24 |
260           static_cast<uint32>(d[1]) << 16 |
261           static_cast<uint32>(d[2]) << 8 |
262           static_cast<uint32>(d[3]);
263  }
264
265  uint32 ExternalTimeToInternal(uint32 external_time) const {
266    static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
267    uint32 internal_epoch = 0;
268    if (creation_time_ > kCreationTimeFromInternalEpoch) {
269      internal_epoch = creation_time_ - kCreationTimeFromInternalEpoch;
270    }
271
272    return external_time - internal_epoch;
273  }
274
275  void DropOldestEntry() {
276    set<pair<uint32, string> >::iterator oldest = nonces_.begin();
277    horizon_ = oldest->first + 1;
278    nonces_.erase(oldest);
279  }
280
281  const unsigned max_entries_;
282  const unsigned window_secs_;
283  const uint32 creation_time_;
284  uint8 orbit_[8];
285  uint32 horizon_;
286
287  set<pair<uint32, string> > nonces_;
288};
289
290class StrikeRegisterStressTest : public ::testing::Test {
291};
292
293TEST_F(StrikeRegisterStressTest, InOrderInsertion) {
294  // Fixed seed gives reproducibility for this test.
295  srand(42);
296
297  unsigned max_entries = 64;
298  uint32 current_time = 10000, window = 200;
299  scoped_ptr<StrikeRegister> s1(
300      new StrikeRegister(max_entries, current_time, window, kOrbit,
301                         StrikeRegister::DENY_REQUESTS_AT_STARTUP));
302  scoped_ptr<SlowStrikeRegister> s2(
303      new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
304
305  uint64 i;
306  const uint64 kMaxIterations = 10000;
307  for (i = 0; i < kMaxIterations; i++) {
308    const uint32 time = current_time + i;
309
310    uint8 nonce[32];
311    SetNonce(nonce, time, kOrbit);
312
313    // There are 2048 possible nonce values:
314    const uint32 v = rand() % 2048;
315    nonce[30] = v >> 8;
316    nonce[31] = v;
317
318    const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
319    const InsertStatus nonce_error1 = s1->Insert(nonce, time);
320    EXPECT_EQ(nonce_error1, nonce_error2);
321
322    // Inserts succeed after the startup period.
323    if (time > current_time + window) {
324      EXPECT_EQ(net::NONCE_OK, nonce_error1);
325    } else {
326      EXPECT_EQ(net::NONCE_INVALID_TIME_FAILURE, nonce_error1);
327    }
328    EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
329              s2->GetCurrentValidWindowSecs(time));
330
331    if (i % 10 == 0) {
332      s1->Validate();
333    }
334
335    if (HasFailure()) {
336      break;
337    }
338  }
339
340  if (i != kMaxIterations) {
341    FAIL() << "Failed after " << i << " iterations";
342  }
343}
344
345TEST_F(StrikeRegisterStressTest, Stress) {
346  // Fixed seed gives reproducibility for this test.
347  srand(42);
348  unsigned max_entries = 64;
349  uint32 current_time = 10000, window = 200;
350  scoped_ptr<StrikeRegister> s1(
351      new StrikeRegister(max_entries, current_time, window, kOrbit,
352                         StrikeRegister::DENY_REQUESTS_AT_STARTUP));
353  scoped_ptr<SlowStrikeRegister> s2(
354      new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
355  uint64 i;
356
357  // When making changes it's worth removing the limit on this test and running
358  // it for a while. For the initial development an opt binary was left running
359  // for 10 minutes.
360  const uint64 kMaxIterations = 10000;
361  for (i = 0; i < kMaxIterations; i++) {
362    if (rand() % 1000 == 0) {
363      // 0.1% chance of resetting the sets.
364      max_entries = rand() % 300 + 2;
365      current_time = rand() % 10000;
366      window = rand() % 500;
367      s1.reset(new StrikeRegister(max_entries, current_time, window, kOrbit,
368                                  StrikeRegister::DENY_REQUESTS_AT_STARTUP));
369      s2.reset(
370          new SlowStrikeRegister(max_entries, current_time, window, kOrbit));
371    }
372
373    int32 time_delta = rand() % (window * 4);
374    time_delta -= window * 2;
375    const uint32 time = current_time + time_delta;
376    if (time_delta < 0 && time > current_time) {
377      continue;  // overflow
378    }
379
380    uint8 nonce[32];
381    SetNonce(nonce, time, kOrbit);
382
383    // There are 2048 possible nonce values:
384    const uint32 v = rand() % 2048;
385    nonce[30] = v >> 8;
386    nonce[31] = v;
387
388    const InsertStatus nonce_error2 = s2->Insert(nonce, time, time);
389    const InsertStatus nonce_error1 = s1->Insert(nonce, time);
390    EXPECT_EQ(nonce_error1, nonce_error2);
391    EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
392              s2->GetCurrentValidWindowSecs(time));
393
394    if (i % 10 == 0) {
395      s1->Validate();
396    }
397
398    if (HasFailure()) {
399      break;
400    }
401  }
402
403  if (i != kMaxIterations) {
404    FAIL() << "Failed after " << i << " iterations";
405  }
406}
407
408}  // anonymous namespace
409