Makes an expensive CTLogVerifier test into a value-parameterized test

net/cert/ct_log_verifier_unittest.cc

 // Copyright 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/cert/ct_log_verifier.h"
 
 #include <stdint.h>
 
 #include <memory>
 #include <string>
+#include <tuple>
+#include <utility>
+#include <vector>
 
 #include "base/strings/string_number_conversions.h"
 #include "base/time/time.h"
 #include "crypto/secure_hash.h"
 #include "net/base/hash_value.h"
 #include "net/cert/ct_log_verifier_util.h"
 #include "net/cert/merkle_consistency_proof.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/signed_tree_head.h"
 #include "net/test/ct_test_util.h"
@@ skipping 457 matching lines @@
     // doesn't contain the root of snapshot1, so set have_root1 = false.
     subproof = ReferenceSnapshotConsistency(&inputs[split], snapshot2 - split,
                                             snapshot1 - split, false);
     proof.insert(proof.end(), subproof.begin(), subproof.end());
     // Record the hash of the left subtree (equal in both trees).
     proof.push_back(ReferenceMerkleTreeHash(&inputs[0], split));
   }
   return proof;
 }
 
-// Times out on Win7 test bot.  http://crbug.com/598406
-#if defined(OS_WIN)
-#define MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator \
-  DISABLED_VerifiesValidConsistencyProofsFromReferenceGenerator
-#else
-#define MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator \
-  VerifiesValidConsistencyProofsFromReferenceGenerator
-#endif
-TEST_F(CTLogVerifierTest,
-       MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator) {
+// Generates all valid combinations of tree size and snapshot size / leaf index
+// (assuming the leaf index is 1-based). Combinations will be generated for all
+// tree sizes from 1 to |max_tree_size|.
+// This is useful for exhaustive testing of consistency proof and audit proof
+// verification.
+std::vector<std::pair<uint64_t, uint64_t>> GenerateTestParams(
+    size_t max_tree_size) {
+  std::vector<std::pair<uint64_t, uint64_t>> params;
+  params.reserve(max_tree_size * (max_tree_size + 1) / 2);
+  for (uint64_t tree_size = 1; tree_size <= max_tree_size; ++tree_size) {
+    for (uint64_t x = 1; x <= tree_size; ++x) {
+      // |x| could be a tree snapshot size (for consistency proof tests) or a
+      // leaf index (for inclusion proofs tests).
+      params.emplace_back(tree_size, x);
+    }
+  }
+  return params;
+}
+
+class CTLogVerifierTestUsingReferenceGenerator
+    : public CTLogVerifierTest,
+      public ::testing::WithParamInterface<std::pair<uint64_t, uint64_t>> {};
+
+TEST_P(CTLogVerifierTestUsingReferenceGenerator,
+       VerifiesValidConsistencyProof) {
   std::vector<std::string> data;
   for (int i = 0; i < 256; ++i)
     data.push_back(std::string(1, i));
 
-  std::vector<std::string> proof;
-  std::string root1, root2;
-  // More tests with reference proof generator.
-  for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
-    root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
-    // Repeat for each snapshot in range.
-    for (size_t snapshot = 1; snapshot <= tree_size; ++snapshot) {
-      proof =
-          ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
-      root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
-      VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
-    }
-  }
+  uint64_t tree_size, snapshot;
+  std::tie(tree_size, snapshot) = GetParam();
+  std::string root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
+  std::string root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
+  std::vector<std::string> proof =
+      ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
+  VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
 }
 
+// Test verification of consistency proofs between all tree sizes from 1 to 128.
+INSTANTIATE_TEST_CASE_P(RangeOfTreeSizesAndSnapshots,
+                        CTLogVerifierTestUsingReferenceGenerator,
+                        testing::ValuesIn(GenerateTestParams(128)));

[Ryan Sleevi, 2016/07/28 16:46:50]

Doesn't this 128 magic value tightly couple with the 256 on line 517?

Regarding the right level of sharding of the test and the # of tests vs
performance overhead - did you look at moving the inner loop from 501-505 to be
part of the test (that is, moving 520-526 to be inside a loop)

That is, the GetParam() returns the tree_size to test, and the test itself tests
all leaves within that tree_size. That should still considerably shorten the
tests, but reduces the number of tests to just being 128 tests.

INSTANTIATE_TEST_CASE_P(..., ..., testing::Range(1, 128))

[Rob Percival, 2016/07/28 17:39:24]

Indeed it does - I've created a constant to link them.
Done. That strikes a better balance between individual test duration (each test
case now takes ~250ms) and overall test duration (~18s).

+
 }  // namespace
 
 }  // namespace net