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
13namespace {
14
15using net::StrikeRegister;
16using std::set;
17using std::string;
18
19const 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.
23void 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
32TEST(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
44TEST(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
56TEST(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
68TEST(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
79TEST(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
88TEST(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
99TEST(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
120TEST(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.
143class 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
243TEST(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