[1 of 4] Support prefix queries against the effective_tld_names DAFSA

net/base/lookup_string_in_fixed_set_unittest.cc

 // Copyright 2015 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/base/lookup_string_in_fixed_set.h"
 
 #include <string.h>
+
+#include <algorithm>
+#include <limits>
 #include <ostream>
+#include <utility>
+#include <vector>
 
+#include "base/base_paths.h"
+#include "base/files/file_path.h"
+#include "base/files/file_util.h"
+#include "base/path_service.h"
+#include "base/strings/string_util.h"
+#include "base/strings/stringprintf.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
 namespace {
+namespace effective_tld_names {
+#include "net/base/registry_controlled_domains/effective_tld_names-inc.cc"
+}
 namespace test1 {
 #include "net/base/registry_controlled_domains/effective_tld_names_unittest1-inc.cc"
 }
 namespace test3 {
 #include "net/base/registry_controlled_domains/effective_tld_names_unittest3-inc.cc"
 }
 namespace test4 {
 #include "net/base/registry_controlled_domains/effective_tld_names_unittest4-inc.cc"
 }
 namespace test5 {
@@ skipping 25 matching lines @@
 TEST_P(Dafsa1Test, BasicTest) {
   const Expectation& param = GetParam();
   EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
 }
 
 const Expectation kBasicTestCases[] = {
     {"", -1},      {"j", -1},          {"jp", 0}, {"jjp", -1}, {"jpp", -1},
     {"bar.jp", 2}, {"pref.bar.jp", 1}, {"c", 2},  {"b.c", 1},  {"priv.no", 4},
 };
 
+// Helper function for EnumerateDafsaLanaguage.
+void RecursivelyEnumerateDafsaLanguage(
+    const FixedSetIncrementalLookup& lookup,
+    std::string* sequence,
+    std::vector<std::pair<std::string, int>>* language) {
+  int result = lookup.GetResultForCurrentSequence();
+  if (result != kDafsaNotFound) {
+    language->emplace_back(std::string(sequence->begin(), sequence->end()),
+                           result);
+  }
+  // Try appending each char value.
+  for (char c = std::numeric_limits<char>::min();; ++c) {
+    FixedSetIncrementalLookup continued_lookup = lookup;
+    if (continued_lookup.Advance(c)) {
+      sequence->push_back(c);
+      size_t saved_language_size = language->size();
+      RecursivelyEnumerateDafsaLanguage(continued_lookup, sequence, language);
+      CHECK_LT(saved_language_size, language->size())
+          << "DAFSA includes a branch to nowhere at node: " << *sequence;
+      sequence->pop_back();
+    }
+    if (c == std::numeric_limits<char>::max())
+      break;
+  }
+}
+
+// Uses FixedSetIncrementalLookup to build a vector of every string in the
+// language of the DAFSA.
+template <typename Graph>
+std::vector<std::pair<std::string, int>> EnumerateDafsaLanguage(
+    const Graph& graph) {
+  FixedSetIncrementalLookup query(graph, sizeof(Graph));
+  std::string sequence;
+  std::vector<std::pair<std::string, int>> language;
+  RecursivelyEnumerateDafsaLanguage(query, &sequence, &language);
+  return language;
+}
+
 INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
                         Dafsa1Test,
                         ::testing::ValuesIn(kBasicTestCases));
 
 class Dafsa3Test : public LookupStringInFixedSetTest {};
 
 // This DAFSA is constructed so that labels begin and end with unique
 // characters, which makes it impossible to merge labels. Each inner node
 // is about 100 bytes and a one byte offset can at most add 64 bytes to
 // previous offset. Thus the paths must go over two byte offsets.
@@ skipping 82 matching lines @@
 
 const Expectation kJoinedSuffixesTestCases[] = {
     {"ia", 0},   {"jb", 4},   {"kaa", 0},   {"lbb", 4},
     {"aaa", -1}, {"bbb", -1}, {"maaaa", 0}, {"nbbbb", 0},
 };
 
 INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
                         Dafsa6Test,
                         ::testing::ValuesIn(kJoinedSuffixesTestCases));
 
+// Validates that the generated DAFSA contains exactly the same information as
+// effective_tld_names.gperf.

[Ryan Sleevi, 2017/01/25 19:11:04]

So in general, I try to push back on these "Test all input" tests, because I
don't think they're good to run every test run (versus every build), and what
you're really testing is the make_dafsa code here, not the implementation of the
dafsa bits.

For example, why is it necessary to test effective_tld_names.gperf - and isn't
that coupling the use of this class with an implementation detail?

[ncarter (slow), 2017/01/26 23:29:11]

Regarding coupling: these unittests are already written against the .gperf files
in net/base/registry_controlled_domains. This test belongs here, and not in
registry_controlled_domain_unittest.cc, because it doesn't call any functions in
registry_controlled_domain.cc.

Regarding cost: The test is currently medium-expensive: runs 300ms in debug,
30ms in release. We could make it a little faster if we restricted the range of
char values to a smaller subset, but this ways seemed fast enough.

Regarding the coverage value of this test, I see two purposes:
 - Validate that the produced dafsa is equivalent to the input gperf file. This
is a valuable test to have if we tinker with make_dafsa.py, or the decoder
(which this CL does do).
 - Together with the DCHECKs in the implementation, it validates that the
generated dafsa doesn't have any memory errors in the form of offsets past the
end of the array.

Doing this on effective_tld_names.gperf matters, I'd argue, because it's the
only one we ship right now -- this is a validation of that specific binary blob.
I'd support doing similar validation for other dafsas that get linked into the
production binary.

The second purpose could maybe be accomplished by the existing fuzzer, and
turning the DCHECKs into SECURITY_DCHECKs so that they're compiled into the
fuzzer (ASAN) build. However, SECURITY_DCHECK doesn't exist on base. Do you
think ASAN would be able to find memory bugs (out-of-range offsets) without the
|end_| checks?

The first purpose, however, seems like new and valuable test coverage; since
it's a much much stronger validation that there are no strings recognized by the
dafsa that aren't in the original input file.

There's actually such a theoretical bug in the old code, if it were passed an
input char with value 128, it would match a \0 (result code 0) node, and it's
not clear what happens after that. It's possible there would be an extra string
in the language, or an extra memory. -- see the code here
https://cs.chromium.org/chromium/src/net/base/lookup_string_in_fixed_set.cc?q...
.

I know that the input that Lookup currently receives currently has already been
canonicalized via GURL, which is why I describe this bug as theoretical. But,
since the dafsa mechanism is open to reuse for other purposes (and historically
has had other users), validating the inputs at the lookup_string_in_fixed_set
layer seems like not such a bad idea.

If you think this test is too expensive to run on every change, another option
might be to let the existing fuzzer do the work of probing the dafsa for memory
errors (accomplishing purpose 2), and doing the language-is-complete test
(accomplishing purpose 1) only on the unittest sample DAFSAs, where it will run
much faster, and we can just inline the expectation instead of having to read it
from the gperf file.

Let me know how you'd like to proceed. 

[Ryan Sleevi, 2017/01/27 00:08:24]

Yeah, this used to be an implementation detail of that file. I've held of
stamping the one that moves all this back into that file because both your CLs
and because of https://codereview.chromium.org/2613833002/
I'm torn on this argument, because it doesn't seem like a good approach to
testing to me - but I very well could be wrong here.

On the one hand, part of me thinks that testing the produced dafsa is correct is
something we'd want to do in make_dafsa.py's tests - perhaps as a golden master
comparison. On the other, I can see the argument that this is a systems test.

But when I think about other decoders - such as, say, JSON parsing, it feels
weird/wrong to think we'd decode JSON and then re-encode it, and compare - which
is effectively what we're doing here. We're also not testing the interface
(which is make_dafsa.py), but an implementation detail (how make_dafsa.py reads
the gperf), and that feels like a testing abstraction bleed.
I don't see why we'd need to compile them to SECURITY_DCHECKs to have the
fuzzers catch this. Am I missing something? ASAN should totally pick up if we're
reading past where the graph input was.
Sure, but this shouldn't need the 'live' file, should it?
Yeah, I lean towards that as the solution, but wanted to make sure I wasn't
missing something.

[ncarter (slow), 2017/02/15 23:42:11]

I've redone these unittests so that they just run against three of the test
DAFSAs, and dropped the dependency on the production .gperf file. This plus the
fuzzer gives sufficient coverage, IMO.

The DCHECKs remain DCHECKs. I agree with your point, that we can trust
ASAN+fuzzer to catch the out-of-range reads, without needing SECURITY_DCHECKs.

+TEST(LookupStringInFixedSetTest, TestDafsaLanguageMatchesGperfFile) {
+  // This test runs on the real effective TLD names file.
+  auto language = EnumerateDafsaLanguage(effective_tld_names::kDafsa);
+
+  // Generate a sorted list of every character sequence and result code that the
+  // DAFSA recognizes, mimicing the gperf format.
+  std::vector<std::string> regenerated_gperf;
+  for (const auto& rule : language) {
+    // Mimic the gperf format:  "<input-string>, <result-code-int>\n"
+    regenerated_gperf.emplace_back(
+        base::StringPrintf("%s, %d\n", rule.first.c_str(), rule.second));
+  }
+  // Our .gperf files happen to be sorted, so mimic that.
+  std::sort(regenerated_gperf.begin(), regenerated_gperf.end());
+
+  std::string regenerated_gperf_text =
+      base::JoinString(regenerated_gperf, base::StringPiece());
+
+  // Second, read the source .gperf file into memory (this is the file from
+  // which effective_tld_names::kDafsa was generated).
+  base::FilePath gperf_file_path;
+  PathService::Get(base::DIR_SOURCE_ROOT, &gperf_file_path);
+  gperf_file_path = gperf_file_path.AppendASCII("net")
+                        .AppendASCII("base")
+                        .AppendASCII("registry_controlled_domains")
+                        .AppendASCII("effective_tld_names.gperf");
+  std::string actual_gperf_text;
+  EXPECT_TRUE(base::ReadFileToString(gperf_file_path, &actual_gperf_text));
+  std::string key = "%%\n";
+  actual_gperf_text.erase(0, actual_gperf_text.find(key) + key.length());
+  actual_gperf_text.erase(actual_gperf_text.rfind(key));
+
+  // |regenerated_gperf_text| should match the body of the .gperf file exactly.
+  EXPECT_EQ(actual_gperf_text, regenerated_gperf_text);
+
+  // Sanity check to prevent trivial success.
+  EXPECT_GT(actual_gperf_text.length(), 30000U);
+}
+
 }  // namespace
 }  // namespace net