Mitigate spoofing attempt using Latin letters.

components/url_formatter/url_formatter.cc

Index: components/url_formatter/url_formatter.cc
diff --git a/components/url_formatter/url_formatter.cc b/components/url_formatter/url_formatter.cc
index d54b67913ce76d400907266963475bae6920cdd9..6e9eb07497573b0cd2994644882edbadcfa9d07a 100644
--- a/components/url_formatter/url_formatter.cc
+++ b/components/url_formatter/url_formatter.cc
@@ -6,11 +6,14 @@
 
 #include <algorithm>
 #include <utility>
+#include <vector>
 
 #include "base/lazy_instance.h"
+#include "base/lookup_string_in_fixed_set.h"
 #include "base/macros.h"
 #include "base/numerics/safe_conversions.h"
 #include "base/strings/string_piece.h"
+#include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_offset_string_conversions.h"
 #include "base/strings/utf_string_conversions.h"
@@ -19,8 +22,10 @@
 #include "third_party/icu/source/common/unicode/uidna.h"
 #include "third_party/icu/source/common/unicode/uniset.h"
 #include "third_party/icu/source/common/unicode/uscript.h"
+#include "third_party/icu/source/common/unicode/utypes.h"
 #include "third_party/icu/source/common/unicode/uvernum.h"
 #include "third_party/icu/source/i18n/unicode/regex.h"
+#include "third_party/icu/source/i18n/unicode/translit.h"
 #include "third_party/icu/source/i18n/unicode/uspoof.h"
 #include "url/gurl.h"
 #include "url/third_party/mozilla/url_parse.h"
@@ -191,6 +196,55 @@ base::string16 FormatViewSourceUrl(
   return result;
 }
 
+// A helper class for IDN Spoof checking, used to ensure that no IDN input is
+// spoofable per Chromium's standard of spoofability. For a more thorough
+// explanation of how spoof checking works in Chromium, see
+// http://dev.chromium.org/developers/design-documents/idn-in-google-chrome .
+class IDNSpoofChecker {
+ public:
+  IDNSpoofChecker();
+
+  // Returns true if |label| is safe to display as Unicode. When the TLD is
+  // ASCII, check if a label is entirely made of Cyrillic letters that look like
+  // Latin letters. In the event of library failure, all IDN inputs will be
+  // treated as unsafe.
+  bool Check(base::StringPiece16 label, bool is_tld_ascii);
+
+  // Returns true if |hostname| or the last few components of |hostname| looks
+  // similar to one of top N domains (N=500). Two checks are done:
+  //   1. Calculate the skeleton of |hostname| based on the Unicode confusable
+  //   character list and look it up in the pre-calculated skeleton list of
+  //   top N domains.
+  //   2. Look up the diacritic-free version of |hostname| in the list of
+  //   top N domains.
+  bool SimilarToTopDomains(const base::string16& hostname);
+
+ private:
+  void SetAllowedUnicodeSet(UErrorCode* status);
+  bool IsMadeOfLatinAlikeCyrillic(const icu::UnicodeString& label_string);
+  bool GetSkeleton(const base::string16& hostname, std::string* skeleton);
+  bool RemoveDiacritics(const base::string16& input, std::string* accent_free);
+
+  USpoofChecker* checker_;
+  icu::UnicodeSet deviation_characters_;
+  icu::UnicodeSet non_ascii_latin_letters_;
+  icu::UnicodeSet kana_letters_exceptions_;
+  icu::UnicodeSet cyrillic_letters_;
+  icu::UnicodeSet cyrillic_letters_latin_alike_;
+  icu::UnicodeSet latin_letters_n_ascii_;
+  icu::Transliterator* transliterator_;
+
+  DISALLOW_COPY_AND_ASSIGN(IDNSpoofChecker);
+};
+
+base::LazyInstance<IDNSpoofChecker>::Leaky g_idn_spoof_checker =
+    LAZY_INSTANCE_INITIALIZER;
+base::ThreadLocalStorage::StaticSlot tls_index = TLS_INITIALIZER;
+
+void OnThreadTermination(void* regex_matcher) {
+  delete reinterpret_cast<icu::RegexMatcher*>(regex_matcher);
+}
+
 // TODO(brettw): We may want to skip this step in the case of file URLs to
 // allow unicode UNC hostnames regardless of encodings.
 base::string16 IDNToUnicodeWithAdjustments(
@@ -212,6 +266,7 @@ base::string16 IDNToUnicodeWithAdjustments(
   // Do each component of the host separately, since we enforce script matching
   // on a per-component basis.
   base::string16 out16;
+  bool has_idn_component = false;
   for (size_t component_start = 0, component_end;
        component_start < input16.length();
        component_start = component_end + 1) {
@@ -227,6 +282,7 @@ base::string16 IDNToUnicodeWithAdjustments(
       converted_idn =
           IDNToUnicodeOneComponent(input16.data() + component_start,
                                    component_length, is_tld_ascii, &out16);
+      has_idn_component |= converted_idn;
     }
     size_t new_component_length = out16.length() - new_component_start;
 
@@ -239,43 +295,14 @@ base::string16 IDNToUnicodeWithAdjustments(
     if (component_end < input16.length())
       out16.push_back('.');
   }
-  return out16;
-}
-
-// A helper class for IDN Spoof checking, used to ensure that no IDN input is
-// spoofable per Chromium's standard of spoofability. For a more thorough
-// explanation of how spoof checking works in Chromium, see
-// http://dev.chromium.org/developers/design-documents/idn-in-google-chrome .
-class IDNSpoofChecker {
- public:
-  IDNSpoofChecker();
 
-  // Returns true if |label| is safe to display as Unicode. When the TLD is
-  // ASCII, check if a label is entirely made of Cyrillic letters that look like
-  // Latin letters. In the event of library failure, all IDN inputs will be
-  // treated as unsafe.
-  bool Check(base::StringPiece16 label, bool is_tld_ascii);
-
- private:
-  void SetAllowedUnicodeSet(UErrorCode* status);
-  bool IsMadeOfLatinAlikeCyrillic(const icu::UnicodeString& label_string);
-
-  USpoofChecker* checker_;
-  icu::UnicodeSet deviation_characters_;
-  icu::UnicodeSet non_ascii_latin_letters_;
-  icu::UnicodeSet kana_letters_exceptions_;
-  icu::UnicodeSet cyrillic_letters_;
-  icu::UnicodeSet cyrillic_letters_latin_alike_;
-
-  DISALLOW_COPY_AND_ASSIGN(IDNSpoofChecker);
-};
-
-base::LazyInstance<IDNSpoofChecker>::Leaky g_idn_spoof_checker =
-    LAZY_INSTANCE_INITIALIZER;
-base::ThreadLocalStorage::StaticSlot tls_index = TLS_INITIALIZER;
-
-void OnThreadTermination(void* regex_matcher) {
-  delete reinterpret_cast<icu::RegexMatcher*>(regex_matcher);
+  if (has_idn_component &&
+      g_idn_spoof_checker.Get().SimilarToTopDomains(out16)) {
+    if (adjustments)
+      adjustments->clear();
+    return input16;
+  }
+  return out16;
 }
 
 IDNSpoofChecker::IDNSpoofChecker() {
@@ -339,7 +366,32 @@ IDNSpoofChecker::IDNSpoofChecker() {
       icu::UnicodeSet(UNICODE_STRING_SIMPLE("[[:Cyrl:]]"), status);
   cyrillic_letters_.freeze();
 
-  DCHECK(U_SUCCESS(status));
+  // This set is used to determine whether or not to apply a slow
+  // transliteration to remove diacritics to a given hostname for accent-free
+  // comparison with top domain names. If it has any character outside the set,
+  // the expensive step will be skipped because it cannot match any of top
+  // domain names.
+  // The last ([\u0300-\u0331] is a shorthand for "[:Identifier_Status=Allowed:]
+  // & [:Script_Extensions=Inherited:] - [\\u200C\\u200D]". The latter is a
+  // subset of the former but it does not matter because hostnames with
+  // characters outside the latter set would be rejected in an earlier step.
+  latin_letters_n_ascii_ = icu::UnicodeSet(UNICODE_STRING_SIMPLE(
+      "[[:Latin:] [0-9\\u002e_\\u002d] [\\u0300-\\u0331]]"), status);
+  latin_letters_n_ascii_.freeze();
+
+  // Used for diacritics-agnostic comparison. Add "ł > l; ø > o; đ > d" that
+  // are not handled by "NFD; Nonspacing mark removal; NFC".
+  UParseError parse_error;
+  transliterator_ = icu::Transliterator::createFromRules(
+      UNICODE_STRING_SIMPLE("DropAcc"),
+      icu::UnicodeString("::NFD; ::[:Nonspacing Mark:] Remove; ::NFC;"
+                         " ł > l; ø > o; đ > d;"),
+      UTRANS_FORWARD, parse_error, status);
+  DCHECK(U_SUCCESS(status))
+      << "Spoofchecker initalization failed due to an error: "
+      << u_errorName(status);
+  if (U_FAILURE(status))
+    transliterator_ = nullptr;
 }
 
 bool IDNSpoofChecker::Check(base::StringPiece16 label, bool is_tld_ascii) {
@@ -437,6 +489,79 @@ bool IDNSpoofChecker::Check(base::StringPiece16 label, bool is_tld_ascii) {
   return !dangerous_pattern->find();
 }
 
+bool IDNSpoofChecker::GetSkeleton(const base::string16& hostname,
+                                  std::string* skeleton) {
+  skeleton->clear();
+  icu::UnicodeString ustr_host(FALSE, hostname.data(), hostname.length());
+  // TODO(jshin): Consider supplementing the confusable list by replacing some
+  // characters with their confusable counterpart (e.g. U+04CF => 'l').
+  UErrorCode status = U_ZERO_ERROR;
+  icu::UnicodeString ustr_skeleton;
+  uspoof_getSkeletonUnicodeString(checker_, 0, /* not used. deprecated. */
+                                  ustr_host, ustr_skeleton, &status);
+  if (U_FAILURE(status))
+    return false;
+  ustr_skeleton.toUTF8String(*skeleton);
+  return true;
+}
+
+#include "components/url_formatter/top_domains/alexa_10k_names_and_skeletons-inc.cc"
+// All the domains in the above file have 3 or fewer labels.
+const size_t kNumberOfLabelsToCheck = 3;
+
+bool LookupStringInSet(const std::string& needle,
+                       const unsigned char* fixed_set,
+                       size_t set_len,
+                       int value) {
+  return base::LookupStringInFixedSet(fixed_set, set_len, needle.data(),
+                                      needle.length()) == value;
+}
+
+bool LookupMatchInTopDomains(const std::string& hostname, int value) {
+  // When 'hostname' is a skeleton instead of actual hostname, it's assumed
+  // that no character other than '.' among those allowed in IDN will have
+  // '.' as its skeleton.
+  auto labels = base::SplitStringPiece(hostname, ".", base::KEEP_WHITESPACE,
+                                       base::SPLIT_WANT_ALL);
+
+  while (labels.size() > kNumberOfLabelsToCheck)
+    labels.erase(labels.begin());
+
+  while (labels.size() > 1) {
+    std::string partial_hostname = base::JoinString(labels, ".");
+    if (LookupStringInSet(partial_hostname, kDafsa, arraysize(kDafsa), value))
+      return true;
+    labels.erase(labels.begin());
+  }
+  return false;
+}
+
+bool IDNSpoofChecker::RemoveDiacritics(const base::string16& input,
+                                       std::string* accent_free) {
+  if (!transliterator_)
+    return false;
+  icu::UnicodeString ustr_input(FALSE, input.data(), input.length());
+  // If input has any characters outside Latin and [._-], there is no point in
+  // getting rid of diacritics because it will not match any of top domain
+  // names even after diacritics removal.
+  if (latin_letters_n_ascii_.span(ustr_input, 0, USET_SPAN_CONTAINED) !=
+      ustr_input.length())
+    return false;
+  transliterator_->transliterate(ustr_input);
+  ustr_input.toUTF8String(*accent_free);
+  return true;
+}
+
+bool IDNSpoofChecker::SimilarToTopDomains(const base::string16& hostname) {
+  std::string skeleton;
+  if (GetSkeleton(hostname, &skeleton) && LookupMatchInTopDomains(skeleton, 0))

[ncarter (slow), 2017/04/20 23:37:22]

If it's possible to efficiently obtain the skeleton (or do the diacritical
removal) one input character at a time, then it might be worthwhile to use
FixedSetIncrementalLookup here: we'd probably be done after one or two
characters most of the time, since the first multibyte UTF-8 character would
exhaust the DAFSA search.

[jungshik at Google, 2017/04/21 20:16:33]

Yeah, I saw that API and thought about trying one character at a time, but
didn't try. 

AccentRemoval is rather expensive. Before switching over to DAFSA, I used
sortkey with primary strength - meaning accents are ignored when generating
sortkey. It's faster to calculate sortkey, but sortkey uses almost all the bytes
( 0x00 ~ 0xFF) so that DAFSA cannot be used for sortkey look-up. OTOH, not being
able to use DAFSA means that I have to initialize hash table of sortkeys at
runtime. 

Moreover, I found about dozens of domains registered in '.com' with 'base Latin
letter + combining mark' (there's no precomposed form for those sequences so
that normalization wouldn't get rid of them). One character at a time
accent-removal would not work for them.

As for the skeleton calculation, it should be (a lot) cheaper than
accent-removal. again 'combining marks' above are problematic for one character
at a time calculation. 

Perhaps, I can branch depending on whether there's a combing mark in the input.
If there is, use the current approach. Otherwise, take a fast path for skeleton
lookup. 

+    return true;
+
+  std::string accent_free_name;
+  return RemoveDiacritics(hostname, &accent_free_name) &&
+         LookupMatchInTopDomains(accent_free_name, 1);

[ncarter (slow), 2017/04/20 23:37:22]

Should we (could we) do GetSkeleton() on the RemoveDiacritics string? (Is
rñicrosoft.com a concern)?

If we did, then we might be able to reduce DAFSA size (only needing to store the
skeletons) -- a smaller DAFSA is a faster DAFSA.

Also, as above, it's worth asking if FixedSetIncrementalLookup could provide a
speedup here.

[jungshik at Google, 2017/04/21 20:16:33]

That's a good one !! Thank you for the suggestion. I haven't thought about it.
(and ..... ick ...) 

In terms of performance, though, we might lose more ground by accent-removal
first (accent-removal is slow.) than gaining thanks to a faster DAFSA lookup. 
Related to that is how much saving we'd get if we can have a'value-free' DAFSA
(if we just store skeletons, the only thing I want is a membership. I don't care
about values). 
Yeah..

BTW, before trying to optimize further, I'd rather have a sense of how critical
speed up is for URL formatting in omnibox and elsewhere. 

+}
+
 bool IDNSpoofChecker::IsMadeOfLatinAlikeCyrillic(
     const icu::UnicodeString& label_string) {
   // Collect all the Cyrillic letters in |label_string| and see if they're