Improve documentation and readability of CTLogVerifier tests

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>
@@ skipping 23 matching lines @@
     ret >>= 1;
 
   return ret;
 }
 
 // The following structures, TestVector and ProofTestVector are used for
 // definining test proofs later on.
 
 // A single hash node.
 struct TestVector {
-  const char* const str;
-  size_t length_bytes;
+  const char* const str;  // hex string
+  size_t length_bytes;    // number of bytes represented by |str|
 };
 
 // A single consistency proof. Contains the old and new tree sizes
 // (snapshot1 and snapshot2), the length of the proof (proof_length) and
 // at most 3 proof nodes (all test proofs will be for a tree of size 8).
 struct ProofTestVector {
   uint64_t snapshot1;
   uint64_t snapshot2;
   size_t proof_length;
   TestVector proof[3];
 };
 
 // All test data replicated from
 // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
 // A hash of the empty string.
 const TestVector kSHA256EmptyTreeHash = {
     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32};
 
-// Node hashes for a sample tree of size 8 (each element in this array is
-// a node hash, not leaf data; order represents order of the nodes in the tree).
+// Incremental roots from building the sample tree of size 8 leaf-by-leaf.
+// The first entry is the root at size 0, the last is the root at size 8.
 const TestVector kSHA256Roots[8] = {
     {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
     {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
     {"aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32},
     {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32},
     {"4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32},
     {"76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32},
     {"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32},
     {"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32}};
 
-// A collection of consistency proofs between various sub-trees of the tree
-// defined by |kSHA256Roots|.
+// A collection of consistency proofs between various nodes of the sample tree.
 const ProofTestVector kSHA256Proofs[4] = {
     // Empty consistency proof between trees of the same size (1).
     {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
     // Consistency proof between tree of size 1 and tree of size 8, with 3
     // nodes in the proof.
     {1,
      8,
      3,
      {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
       {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
@@ skipping 20 matching lines @@
 // Decodes a hexadecimal string into the binary data it represents.
 std::string HexToBytes(const char* hex_data, size_t hex_data_length) {
   std::vector<uint8_t> output;
   std::string result;
   std::string hex_data_input(hex_data, hex_data_length);
   if (base::HexStringToBytes(hex_data, &output))
     result.assign(reinterpret_cast<const char*>(&output[0]), output.size());
   return result;
 }
 
+std::string HexToBytes(const TestVector& x) {
+  std::string bytes = HexToBytes(x.str, x.length_bytes * 2);
+  CHECK_EQ(x.length_bytes, bytes.size());
+  return bytes;
+}
+
 std::string GetEmptyTreeHash() {
-  return HexToBytes(kSHA256EmptyTreeHash.str,
-                    kSHA256EmptyTreeHash.length_bytes);

[Ryan Sleevi, 2016/07/26 18:25:14]

Wait, so this whole time, the empty tree hash was truncated by 32-bytes, and
nothing failed?

[Eran Messeri, 2016/07/26 18:32:08]

Turns out it wasn't, because of a bug in the HexToBytes variant that takes a
(const char*, size_t):
It constructed  hex_data_input of type std::string using only half the hex bytes
(truncating it), but never used the hex_data_input string, passing the input
const char* instead to base::HexStringToBytes (which presumably constructed a
std::string with the entire hex string as it is null-terminated).

 

[Ryan Sleevi, 2016/07/26 18:36:24]

So why does this CL leave the bug in place then? (Line 112)

My gripe is that from a reviewers point, there's something that very glaringly
seems a behaviour change (the *2), without documenting in the CL description or
reviewer notes. Even if it's benign, that's totally something that *should* have
been documented, to avoid the first set of questions. Arguably, however, if
we're saying it's a bug, we shouldn't add a workaround for the bug (line 118)
and not even fix the bug (line 112) - pick one or the other. Either we should
remove the length variant from HexToBytes or properly use hex_data_input

[Rob Percival, 2016/08/25 16:23:34]

I've broken out a fix for this into https://codereview.chromium.org/2275353002.
I'll rebase this change on top of that, so that this is pretty much just a
documentation change.

+  return HexToBytes(kSHA256EmptyTreeHash);
 }
 
 // Creates a ct::MerkleConsistencyProof and returns the result of
 // calling log->VerifyConsistencyProof with that proof and snapshots.
 bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
                             uint64_t old_tree_size,
                             const std::string& old_tree_root,
                             uint64_t new_tree_size,
                             const std::string& new_tree_root,
                             const std::vector<std::string>& proof) {
@@ skipping 241 matching lines @@
   EXPECT_FALSE(VerifyConsistencyProof(log_, 1, empty_tree_hash, 1,
                                       empty_tree_hash, proof));
 }
 
 TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) {
   std::vector<std::string> proof;
   std::string root1, root2;
 
   // Known good proofs.
   for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) {
+    SCOPED_TRACE(i);
     proof.clear();
     for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
       const TestVector& v = kSHA256Proofs[i].proof[j];
-      proof.push_back(HexToBytes(v.str, v.length_bytes));
+      proof.push_back(HexToBytes(v));
     }
     const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
     const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
     const TestVector& old_root = kSHA256Roots[snapshot1 - 1];
     const TestVector& new_root = kSHA256Roots[snapshot2 - 1];
-    VerifierConsistencyCheck(
-        snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes),
-        HexToBytes(new_root.str, new_root.length_bytes), proof);
+    VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root),
+                             HexToBytes(new_root), proof);
   }
 }
 
 const char kLeafPrefix[] = {'\x00'};
 
 // Reference implementation of RFC6962.
 // This allows generation of arbitrary-sized Merkle trees and consistency
 // proofs between them for testing the consistency proof validation
 // code.
 class TreeHasher {
  public:
-  static std::string HashEmpty() {
-    return HexToBytes(kSHA256EmptyTreeHash.str,
-                      kSHA256EmptyTreeHash.length_bytes);
-  }
+  static std::string HashEmpty() { return HexToBytes(kSHA256EmptyTreeHash); }
 
   static std::string HashLeaf(const std::string& leaf) {
     SHA256HashValue sha256;
     memset(sha256.data, 0, sizeof(sha256.data));
 
     std::unique_ptr<crypto::SecureHash> hash(
         crypto::SecureHash::Create(crypto::SecureHash::SHA256));
     hash->Update(kLeafPrefix, 1);
     hash->Update(leaf.data(), leaf.size());
     hash->Finish(sha256.data, sizeof(sha256.data));
@@ skipping 68 matching lines @@
 
 // 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) {

[Ryan Sleevi, 2016/07/26 18:40:29]

Since you're improving documentation, this test is woefully under-documented as
to what's being tested.

It came up on the caching CL that it's not entirely obvious what's being tested
(it looks like you're testing the path from every possible leaf to the root, but
it's entirely probable I'm misreading this.

[Rob Percival, 2016/08/25 16:23:34]

Done.

   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);
     }
   }
 }
 
 }  // namespace
 
 }  // namespace net