Add transport security state generator tests.

net/tools/transport_security_state_generator/trie/trie_writer_unittest.cc

Index: net/tools/transport_security_state_generator/trie/trie_writer_unittest.cc
diff --git a/net/tools/transport_security_state_generator/trie/trie_writer_unittest.cc b/net/tools/transport_security_state_generator/trie/trie_writer_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..5f6f71667a890a4b80021b616065d10607b37797
--- /dev/null
+++ b/net/tools/transport_security_state_generator/trie/trie_writer_unittest.cc
@@ -0,0 +1,396 @@
+// Copyright 2017 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 <memory>
+
+#include "base/memory/ptr_util.h"
+#include "net/tools/transport_security_state_generator/bit_writer.h"
+#include "net/tools/transport_security_state_generator/huffman/huffman_builder.h"
+#include "net/tools/transport_security_state_generator/transport_security_state_entry.h"
+#include "net/tools/transport_security_state_generator/trie/trie_bit_buffer.h"
+#include "net/tools/transport_security_state_generator/trie/trie_writer.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+namespace transport_security_state {
+
+namespace {
+
+std::vector<uint8_t> StringToVector(const std::string& input) {
+  std::vector<uint8_t> output;
+  for (const auto& character : input) {
+    output.push_back(character);
+  }
+  return output;
+}
+
+void appendEntry(const std::string& hostname,
+                 TransportSecurityStateEntries* entries) {
+  std::unique_ptr<TransportSecurityStateEntry> entry =
+      base::MakeUnique<TransportSecurityStateEntry>();
+  entry->hostname = hostname;
+  entry->include_subdomains = true;
+  entry->force_https = true;
+
+  entries->push_back(std::move(entry));
+}
+
+}  // namespace
+
+class TrieWriterTest : public testing::Test {
+ protected:
+  void SetUp() override {
+    // Create a Huffman representation that is 8bit ASCII.
+    for (uint8_t i = 0; i <= 127; ++i) {
+      HuffmanRepresentation representation;
+      representation.bits = i;
+      representation.number_of_bits = 8;
+      huffman_table_[i] = representation;
+    }
+
+    domain_ids_map_["BADSSL_COM"] = 1;
+    domain_ids_map_["EXAMPLE_ORG"] = 2;
+    domain_ids_map_["OVERFLOW_TLD"] = 512;
+
+    report_uris_map_["https://report.badssl.com/upload"] = 1;
+    report_uris_map_["https://report.example.org/upload"] = 2;
+    report_uris_map_["https://report.overflow.tld/upload"] = 16;
+
+    pinsets_map_["pinset_a"] = 1;
+    pinsets_map_["pinset_b"] = 2;
+    pinsets_map_["pinset_overflow"] = 16;
+  }
+
+  std::unique_ptr<TrieWriter> GetTrieWriter() {
+    return base::MakeUnique<TrieWriter>(huffman_table_, domain_ids_map_,
+                                        report_uris_map_, report_uris_map_,
+                                        pinsets_map_, nullptr);
+  }
+
+  bool TestWriteEntry(TrieWriter* trie_writer,
+                      const TransportSecurityStateEntry& entry,
+                      std::initializer_list<uint8_t> expected) {
+    TrieBitBuffer buffer;
+    if (!trie_writer->WriteEntry(&entry, &buffer)) {
+      return false;
+    }
+
+    BitWriter bit_writer;
+    buffer.WriteToBitWriter(&bit_writer);
+    bit_writer.Flush();
+
+    EXPECT_EQ(std::vector<uint8_t>(expected), bit_writer.bytes());
+    return true;
+  }
+
+ private:
+  HuffmanRepresentationTable huffman_table_;
+  NameIDMap domain_ids_map_;
+  NameIDMap report_uris_map_;
+  NameIDMap pinsets_map_;
+};
+
+TEST_F(TrieWriterTest, SingleEntryTrie) {
+  TransportSecurityStateEntries entries;
+  appendEntry("hsts.badssl.com", &entries);
+
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+
+  uint32_t root_position;
+  ASSERT_TRUE(trie_writer->WriteEntries(entries, &root_position));
+
+  EXPECT_EQ(0U, root_position);
+  EXPECT_EQ(157U, trie_writer->position());
+
+  trie_writer->Flush();
+  EXPECT_EQ(20U, trie_writer->bytes().size());
+
+  // The expected bits are, starting at |root_position|:
+  // 0xFF 0XFE: 15 ones followed by a zero indicating a prefix of 15 characters.
+  //
+  // The prefix follows immediately (8 bits per character):
+  // 0x6D 0x6F 0x63 0x2E 0x6C 0x73 0x73 0x64 0x61 0x62 0x2E 0x73 0x74 0x73 0x68
+  // and decodes to "moc.lssdab.stsh".
+  //
+  // The prefix is followed by 0x0 (kTerminalValue) which indidicates the end
+  // of the prefix. What follows is the encoded entry for "hsts.badssl.com":
+  // 0xC3 0xF8. The entry (first 5 bits) is followed be 0x7F (kEndOfTabelValue).
+  // The remaining bits are padding.
+  EXPECT_THAT(
+      trie_writer->bytes(),
+      testing::ElementsAreArray({0xFF, 0xFE, 0x6D, 0x6F, 0x63, 0x2E, 0x6C,
+                                 0x73, 0x73, 0x64, 0x61, 0x62, 0x2E, 0x73,
+                                 0x74, 0x73, 0x68, 0x0,  0xC3, 0xF8}));
+}
+
+TEST_F(TrieWriterTest, MultiPrefixTrie) {
+  TransportSecurityStateEntries entries;
+  appendEntry("hsts.badssl.com", &entries);
+  appendEntry("expect-ct.badssl.com", &entries);
+  appendEntry("expect-staple.badssl.com", &entries);
+
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+
+  uint32_t root_position;
+  ASSERT_TRUE(trie_writer->WriteEntries(entries, &root_position));
+
+  EXPECT_EQ(273U, root_position);
+  EXPECT_EQ(440U, trie_writer->position());
+
+  trie_writer->Flush();
+  EXPECT_EQ(56U, trie_writer->bytes().size());
+
+  EXPECT_THAT(trie_writer->bytes(),

[martijnc, 2017/02/08 20:58:21]

I've verified that these expectations are correct (like the one above) and tried
to write down the reasoning but that got very complicated and hard to follow.
The encoded bytes here don't align with the bytes in the expectations so you
have to constantly juggle bits. There are also 'jumps' from position to position
(within bytes) which complicates things further.

Are there better ways to define these expectations?

[Ryan Sleevi, 2017/02/08 21:45:29]

That's a really tough question. You're effectively measuring pristine input.

I suppose the question here is: What invariants of the (public) API are you
trying to test? That is, in thinking about "Test the interface, not the
implementation" - what is the contract that the interface of TrieWriter
guarantees? Can we change the implementation at all?

For example, if we changed the entry/endOfTableValue or something like that, how
should that work?

In thinking about those questions and how to answer them, one suggestion would
be "Is the interface such that TrieWriter outputs something that returns the
same input via [TrieReader/whatever?]"? If so, then you could write the test
such that it does a round-trip - that you get the same output for input.

However, if the interface is such that you output these exact bytes, then I
suppose that's valid. However, it does seem to make it more likely that anytime
someone changes the implementation, they'll have these tests fail, then say
"Ugh, how do I regenerate and why are these tests here", and just copy the
'actual' value to the 'expected' value and call it a day.

+              testing::ElementsAreArray(
+                  {0xff, 0xf3, 0x63, 0x83, 0xb,  0xa3, 0x99, 0x6b, 0xa3, 0x1b,
+                   0x2b, 0x83, 0xc3, 0x28, 0x6,  0x1f, 0xf9, 0xd1, 0xcd, 0xa0,
+                   0x3,  0xf,  0xff, 0xe6, 0x32, 0xd7, 0x46, 0x36, 0x57, 0x7,
+                   0x86, 0x50, 0xc,  0x3f, 0xff, 0xf3, 0x6b, 0x7b, 0x19, 0x73,
+                   0x63, 0x9b, 0x9b, 0x23, 0xb,  0x11, 0x73, 0x2a, 0x62, 0x2e,
+                   0x70, 0x82, 0x74, 0x31, 0x7f, 0x0}));
+}
+
+TEST_F(TrieWriterTest, MultiMixedPrefixTrie) {
+  TransportSecurityStateEntries entries;
+  appendEntry("hsts.badssl.com", &entries);
+  appendEntry("expect-ct.badssl.com", &entries);
+  appendEntry("example.org", &entries);
+  appendEntry("badssl.com", &entries);
+
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+
+  uint32_t root_position;
+  ASSERT_TRUE(trie_writer->WriteEntries(entries, &root_position));
+
+  EXPECT_EQ(423U, root_position);
+  EXPECT_EQ(476U, trie_writer->position());
+
+  trie_writer->Flush();
+  EXPECT_EQ(60U, trie_writer->bytes().size());
+
+  EXPECT_THAT(
+      trie_writer->bytes(),
+      testing::ElementsAreArray(
+          {0xff, 0xce, 0x4d, 0xe5, 0xcc, 0xad, 0x8e, 0xd,  0xac, 0x2f,
+           0xc,  0xa0, 0x18, 0x7f, 0xe7, 0x47, 0x36, 0x80, 0xc,  0x3f,
+           0xff, 0x98, 0xcb, 0x5d, 0x18, 0xd9, 0x5c, 0x1e, 0x19, 0x40,
+           0x30, 0xfe, 0x73, 0x44, 0x7b, 0xa1, 0x8b, 0xff, 0xfc, 0xde,
+           0xc6, 0x5c, 0xd8, 0xe6, 0xe6, 0xc8, 0xc2, 0xc4, 0x1,  0x82,
+           0xe3, 0x5c, 0xfe, 0x67, 0x4e, 0x9d, 0xb6, 0x32, 0xd7, 0xf0}));
+}
+
+TEST_F(TrieWriterTest, WriteEntryHSTS) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+  TransportSecurityStateEntry entry;
+  entry.hostname = "example.org";
+
+  entry.force_https = true;
+  entry.include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xC0}));
+
+  entry.force_https = false;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x80}));
+
+  entry.include_subdomains = false;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x0}));
+
+  entry.force_https = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x40}));
+}
+
+TEST_F(TrieWriterTest, WriteEntryHPKP) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+  TransportSecurityStateEntry entry;
+  entry.hostname = "example.org";
+
+  entry.pinset = "pinset_a";
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x22, 0x2, 0x0}));
+
+  entry.hpkp_include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x22, 0x2, 0x80}));
+
+  // Should ignore |entry.hpkp_include_subdomains|.
+  entry.include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xA2, 0x2, 0x0}));
+
+  // Should result in an "empty" HPKP state.
+  entry.pinset = "";
+  entry.include_subdomains = false;
+  entry.hpkp_include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x0}));
+
+  // Unknown pinset.
+  entry.pinset = "not_found";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+
+  // Overflow for the pinset ID.
+  entry.pinset = "pinset_overflow";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+
+  // Set a valid pinset for the other tests.
+  entry.pinset = "pinset_a";
+
+  // Overflow for the domain ID.
+  entry.hostname = "overflow.tld";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+
+  // Unknown domain ID.
+  entry.hostname = "unknown.tld";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+}
+
+TEST_F(TrieWriterTest, WriteEntryExpectStaple) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+  TransportSecurityStateEntry entry;
+  entry.hostname = "example.org";
+
+  entry.expect_staple = true;
+  entry.expect_staple_report_uri = "https://report.example.org/upload";
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x08, 0x80}));
+
+  entry.expect_staple_include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x0C, 0x80}));
+
+  // This should result in an "empty" expect-staple state.
+  entry.expect_staple = false;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x0}));
+
+  // Enable expect-staple for the other tests.
+  entry.expect_staple = true;
+
+  // Invalid report URI ID.
+  entry.expect_staple_report_uri = "https://report.overflow.tld/upload";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+
+  // Unknown report URI.
+  entry.expect_staple_report_uri = "https://report.unknown.tld/upload";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+}
+
+TEST_F(TrieWriterTest, WriteEntryExpectCT) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+  TransportSecurityStateEntry entry;
+  entry.hostname = "example.org";
+
+  entry.expect_ct = true;
+  entry.expect_ct_report_uri = "https://report.example.org/upload";
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x12, 0x0}));
+
+  // This should result in an "empty" expect-staple state.
+  entry.expect_ct = false;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x0}));
+
+  // Enable expect-staple for the other tests.
+  entry.expect_ct = true;
+
+  // Invalid report URI ID.
+  entry.expect_ct_report_uri = "https://report.overflow.tld/upload";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+
+  // Unknown report URI.
+  entry.expect_ct_report_uri = "https://report.unknown.tld/upload";
+  EXPECT_FALSE(TestWriteEntry(trie_writer.get(), entry, {}));
+}
+
+TEST_F(TrieWriterTest, WriteEntryCombination) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+  TransportSecurityStateEntry entry;
+  entry.hostname = "example.org";
+
+  entry.force_https = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0x40}));
+
+  entry.include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xC0}));
+
+  entry.pinset = "pinset_a";
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xE2, 0x2, 0x0}));
+
+  // Should have no effect.
+  entry.hpkp_include_subdomains = true;
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xE2, 0x2, 0x0}));
+
+  entry.expect_ct = true;
+  entry.expect_ct_report_uri = "https://report.example.org/upload";
+  EXPECT_TRUE(TestWriteEntry(trie_writer.get(), entry, {0xE2, 0x2, 0x90}));
+
+  entry.expect_staple = true;
+  entry.expect_staple_report_uri = "https://report.example.org/upload";
+  EXPECT_TRUE(
+      TestWriteEntry(trie_writer.get(), entry, {0xE2, 0x2, 0x94, 0x40}));
+
+  entry.expect_staple_include_subdomains = true;
+  EXPECT_TRUE(
+      TestWriteEntry(trie_writer.get(), entry, {0xE2, 0x2, 0x96, 0x40}));
+}
+
+TEST_F(TrieWriterTest, ReverseName) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+
+  EXPECT_EQ(StringToVector(std::string("moc.elpmaxe\0", 12)),
+            trie_writer->ReverseName("example.com"));
+  EXPECT_EQ(StringToVector(std::string("moc.lssdab.stsh\0", 16)),
+            trie_writer->ReverseName("hsts.badssl.com"));
+}
+
+TEST_F(TrieWriterTest, LongestCommonPrefix) {
+  std::unique_ptr<TrieWriter> trie_writer = GetTrieWriter();
+
+  TransportSecurityStateEntry entry1;
+  entry1.hostname = "sub.sub.example.com";
+  TransportSecurityStateEntry entry2;
+  entry2.hostname = "sub.example.com";
+  TransportSecurityStateEntry entry3;
+  entry3.hostname = "www.sub.example.com";
+  TransportSecurityStateEntry entry4;
+  entry4.hostname = "example.com";
+  TransportSecurityStateEntry entry5;
+  entry5.hostname = "badssl.com";
+  TransportSecurityStateEntry entry6;
+  entry6.hostname = "example.org";
+
+  ReversedEntries reversed_entries;
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry1.hostname), &entry1));
+
+  EXPECT_EQ(StringToVector("moc.elpmaxe.bus.bus"),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry2.hostname), &entry2));
+  EXPECT_EQ(StringToVector("moc.elpmaxe.bus"),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry3.hostname), &entry3));
+  EXPECT_EQ(StringToVector("moc.elpmaxe.bus"),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry4.hostname), &entry4));
+  EXPECT_EQ(StringToVector("moc.elpmaxe"),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry5.hostname), &entry5));
+  EXPECT_EQ(StringToVector("moc."),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+
+  reversed_entries.push_back(base::MakeUnique<ReversedEntry>(
+      trie_writer->ReverseName(entry6.hostname), &entry6));
+  EXPECT_EQ(StringToVector(""),
+            trie_writer->LongestCommonPrefix(reversed_entries.cbegin(),
+                                             reversed_entries.cend()));
+}
+
+}  // transport_security_state
+
+}  // namespace net