Narrow the strike register window in both directions when tracking many

net/quic/crypto/strike_register_test.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/crypto/strike_register.h"
 
 #include <set>
 #include <string>
 
 #include "base/basictypes.h"
@@ skipping 26 matching lines @@
   // The set must reject values created on or before its own creation time.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 999, kOrbit);
   ASSERT_FALSE(set.Insert(nonce, 1000));
   SetNonce(nonce, 1000, kOrbit);
   ASSERT_FALSE(set.Insert(nonce, 1000));
 
-  EXPECT_EQ(0u, set.EffectiveWindowSecs(1000 /* current time */));
-  EXPECT_EQ(49u, set.EffectiveWindowSecs(1050 /* current time */));
-  EXPECT_EQ(99u, set.EffectiveWindowSecs(1100 /* current time */));
-  EXPECT_EQ(199u, set.EffectiveWindowSecs(1200 /* current time */));
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1300 /* current time */));
+  EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1000 /* current time */));
+  EXPECT_EQ(0u, set.GetCurrentValidWindowSecs(1100 /* current time */));
+  EXPECT_EQ(1u, set.GetCurrentValidWindowSecs(1101 /* current time */));
+  EXPECT_EQ(50u, set.GetCurrentValidWindowSecs(1150 /* current time */));
+  EXPECT_EQ(100u, set.GetCurrentValidWindowSecs(1200 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
 }
 
 TEST(StrikeRegisterTest, NoStartupMode) {
   // Check that a strike register works immediately if NO_STARTUP_PERIOD_NEEDED
   // is specified.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::NO_STARTUP_PERIOD_NEEDED);
   uint8 nonce[32];
   SetNonce(nonce, 1000, kOrbit);
   ASSERT_TRUE(set.Insert(nonce, 1000));
   ASSERT_FALSE(set.Insert(nonce, 1000));
 
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1000 /* current time */));
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1050 /* current time */));
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1100 /* current time */));
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1200 /* current time */));
-  EXPECT_EQ(200u, set.EffectiveWindowSecs(1300 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1000 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1050 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1200 /* current time */));
+  EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1300 /* current time */));
 }
 
 TEST(StrikeRegisterTest, WindowFuture) {
   // The set must reject values outside the window.
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
   ASSERT_FALSE(set.Insert(nonce, 1000));
@@ skipping 11 matching lines @@
   SetNonce(nonce, 1101, kBadOrbit);
   ASSERT_FALSE(set.Insert(nonce, 1100));
 }
 
 TEST(StrikeRegisterTest, OneValue) {
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
-  ASSERT_TRUE(set.Insert(nonce, 1100));
+  ASSERT_TRUE(set.Insert(nonce, 1101));
 }
 
 TEST(StrikeRegisterTest, RejectDuplicate) {
   // The set must reject values with the wrong orbit
   StrikeRegister set(10 /* max size */, 1000 /* current time */,
                      100 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
-  ASSERT_TRUE(set.Insert(nonce, 1100));
-  ASSERT_FALSE(set.Insert(nonce, 1100));
+  ASSERT_TRUE(set.Insert(nonce, 1101));
+  ASSERT_FALSE(set.Insert(nonce, 1101));
 }
 
 TEST(StrikeRegisterTest, HorizonUpdating) {
   StrikeRegister::StartupType startup_types[] = {
     StrikeRegister::DENY_REQUESTS_AT_STARTUP,
     StrikeRegister::NO_STARTUP_PERIOD_NEEDED
   };
 
   for (size_t type_idx = 0; type_idx < arraysize(startup_types); ++type_idx) {
     StrikeRegister set(5 /* max size */, 500 /* current time */,
                        100 /* window secs */, kOrbit,
                        startup_types[type_idx]);
     uint8 nonce[6][32];
     for (unsigned i = 0; i < 5; i++) {
       SetNonce(nonce[i], 1101 + i, kOrbit);
       nonce[i][31] = i;
       ASSERT_TRUE(set.Insert(nonce[i], 1100));
     }
 
-    // Effective horizon is still 2 * window.
-    EXPECT_EQ(200u, set.EffectiveWindowSecs(1100));
+    // Valid window is still equal to |window_secs + 1|.
+    EXPECT_EQ(101u, set.GetCurrentValidWindowSecs(1100));
 
     // This should push the oldest value out and force the horizon to
     // be updated.
     SetNonce(nonce[5], 1110, kOrbit);
-    ASSERT_TRUE(set.Insert(nonce[5], 1100));
+    ASSERT_TRUE(set.Insert(nonce[5], 1110));
     // Effective horizon is computed based on the timestamp of the
     // value that was pushed out.
-    EXPECT_EQ(98u, set.EffectiveWindowSecs(1100));
+    EXPECT_EQ(9u, set.GetCurrentValidWindowSecs(1110));
 
     SetNonce(nonce[5], 1111, kOrbit);
-    EXPECT_TRUE(set.Insert(nonce[5], 1100));
-    EXPECT_EQ(97u, set.EffectiveWindowSecs(1100));
+    EXPECT_TRUE(set.Insert(nonce[5], 1110));
+    EXPECT_EQ(8u, set.GetCurrentValidWindowSecs(1110));
 
     // This should be behind the horizon now:
     SetNonce(nonce[5], 1101, kOrbit);
     nonce[5][31] = 10;
-    ASSERT_FALSE(set.Insert(nonce[5], 1100));
+    EXPECT_FALSE(set.Insert(nonce[5], 1110));
+
+    // Insert beyond the valid range.
+    SetNonce(nonce[5], 1117, kOrbit);
+    nonce[5][31] = 2;
+    EXPECT_FALSE(set.Insert(nonce[5], 1110));
+
+    // Insert at the upper valid range.
+    SetNonce(nonce[5], 1116, kOrbit);
+    nonce[5][31] = 1;
+    EXPECT_TRUE(set.Insert(nonce[5], 1110));
+
+    // This should be beyond the upper valid range now:
+    SetNonce(nonce[5], 1116, kOrbit);
+    nonce[5][31] = 2;
+    EXPECT_FALSE(set.Insert(nonce[5], 1110));
   }
 }
 
 TEST(StrikeRegisterTest, InsertMany) {
   StrikeRegister set(5000 /* max size */, 1000 /* current time */,
                      500 /* window secs */, kOrbit,
                      StrikeRegister::DENY_REQUESTS_AT_STARTUP);
 
   uint8 nonce[32];
   SetNonce(nonce, 1101, kOrbit);
@@ skipping 60 matching lines @@
 
     set<pair<uint32, string> >::const_iterator it = nonces_.find(nonce);
     if (it != nonces_.end()) {
       return false;
     }
 
     nonces_.insert(nonce);
     return true;
   }
 
-  uint32 EffectiveWindowSecs(const uint32 current_time_external) const {
-    const uint32 future_horizon =
-        ExternalTimeToInternal(current_time_external) + window_secs_;
-    if (horizon_ > future_horizon) {
+  uint32 GetCurrentValidWindowSecs(const uint32 current_time_external) const {
+    const uint32 current_time = ExternalTimeToInternal(current_time_external);
+    if (horizon_ > current_time) {
       return 0;
     }
-    return min(future_horizon - horizon_, 2 * window_secs_);
+    return 1 + min(current_time - horizon_, window_secs_);
   }
 
  private:
   // TimeFromBytes returns a big-endian uint32 from |d|.
   static uint32 TimeFromBytes(const uint8 d[4]) {
     return static_cast<uint32>(d[0]) << 24 |
            static_cast<uint32>(d[1]) << 16 |
            static_cast<uint32>(d[2]) << 8 |
            static_cast<uint32>(d[3]);
   }
@@ skipping 49 matching lines @@
     // There are 2048 possible nonce values:
     const uint32 v = rand() % 2048;
     nonce[30] = v >> 8;
     nonce[31] = v;
 
     const bool r2 = s2->Insert(nonce, time, time);
     const bool r1 = s1->Insert(nonce, time);
     EXPECT_EQ(r1, r2);
     // Inserts succeed after the startup period.
     EXPECT_EQ(time > current_time + window, r1);
-    EXPECT_EQ(s1->EffectiveWindowSecs(time),
-              s2->EffectiveWindowSecs(time));
+    EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
+              s2->GetCurrentValidWindowSecs(time));
 
     if (i % 10 == 0) {
       s1->Validate();
     }
 
     if (HasFailure()) {
       break;
     }
   }
 
@@ skipping 41 matching lines @@
     SetNonce(nonce, time, kOrbit);
 
     // There are 2048 possible nonce values:
     const uint32 v = rand() % 2048;
     nonce[30] = v >> 8;
     nonce[31] = v;
 
     const bool r2 = s2->Insert(nonce, time, time);
     const bool r1 = s1->Insert(nonce, time);
     EXPECT_EQ(r1, r2);
-    EXPECT_EQ(s1->EffectiveWindowSecs(time),
-              s2->EffectiveWindowSecs(time));
+    EXPECT_EQ(s1->GetCurrentValidWindowSecs(time),
+              s2->GetCurrentValidWindowSecs(time));
 
     if (i % 10 == 0) {
       s1->Validate();
     }
 
     if (HasFailure()) {
       break;
     }
   }
 
   if (i != kMaxIterations) {
     FAIL() << "Failed after " << i << " iterations";
   }
 }
 
 }  // anonymous namespace