Adds a MerkleAuditProof struct to net/cert.

net/cert/merkle_audit_proof_unittest.cc

+// Copyright 2016 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/merkle_audit_proof.h"
+
+#include "base/logging.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+namespace ct {
+namespace {
+
+TEST(MerkleAuditProofTest, CalculatesAuditPathLengthCorrectly) {
+  // Test all leaves up to a tree size of 4:
+  EXPECT_EQ(0u, CalculateAuditPathLength(0, 1));
+  EXPECT_EQ(1u, CalculateAuditPathLength(0, 2));
+  EXPECT_EQ(1u, CalculateAuditPathLength(1, 2));
+  EXPECT_EQ(2u, CalculateAuditPathLength(0, 3));
+  EXPECT_EQ(2u, CalculateAuditPathLength(1, 3));
+  EXPECT_EQ(1u, CalculateAuditPathLength(2, 3));
+  EXPECT_EQ(2u, CalculateAuditPathLength(0, 4));
+  EXPECT_EQ(2u, CalculateAuditPathLength(1, 4));
+  EXPECT_EQ(2u, CalculateAuditPathLength(2, 4));
+  EXPECT_EQ(2u, CalculateAuditPathLength(3, 4));
+  // Boundary cases for a larger tree size:
+  EXPECT_EQ(9u, CalculateAuditPathLength(0, 257));
+  EXPECT_EQ(9u, CalculateAuditPathLength(255, 257));
+  EXPECT_EQ(1u, CalculateAuditPathLength(256, 257));
+  // Example from CT over DNS draft RFC:
+  EXPECT_EQ(20u, CalculateAuditPathLength(123456, 999999));
+  // Test data from
+  // https://github.com/google/certificate-transparency/blob/af98904302724c29aa6659ca372d41c9687de2b7/python/ct/crypto/merkle_test.py:
+  EXPECT_EQ(22u, CalculateAuditPathLength(848049, 3630887));
+}
+
+#if DCHECK_IS_ON()
+
+TEST(MerkleAuditProofDeathTest, DiesIfLeafIndexIsGreaterThanOrEqualToTreeSize) {

[eroman, 2016/05/26 00:39:43]

This test sounds fishy.

(a) if it is reachable code (i.e. leaf_index and tree_size are attacker
controlled), then it should be checking in production code and not using a
DCHECK()

(b) if it really is unreachable (and a programmer error for the caller of this
function) then testing that DCHECK is reached doesn't seem very valuable.

I don't particular care if we have a test for this or not, but want to make sure
it isn't situation (a).

[Rob Percival, 2016/05/26 03:17:13]

The tree size will come from a signed, verified data structure delivered by the
component updater, so that's highly unlikely to be attacker controlled. The leaf
index will have been received over DNS, so that could, conceivably, be attacker
controlled. I'll upgrade the check to CHECK(). I can't imagine to what ends an
attacker would abuse this function but I'm sure that's just down to a lack of
imagination on my part!

[Rob Percival, 2016/05/26 16:00:57]

Done.

+  EXPECT_DEATH_IF_SUPPORTED(CalculateAuditPathLength(0, 0),
+                            "leaf_index < tree_size");
+  EXPECT_DEATH_IF_SUPPORTED(CalculateAuditPathLength(10, 10),
+                            "leaf_index < tree_size");
+  EXPECT_DEATH_IF_SUPPORTED(CalculateAuditPathLength(11, 10),
+                            "leaf_index < tree_size");
+}
+
+#endif
+
+}  // namespace
+}  // namespace ct
+}  // namespace net