1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // NB: Modelled after Mozilla's code (originally written by Pamela Greene,
6 // later modified by others), but almost entirely rewritten for Chrome.
7 // (netwerk/dns/src/nsEffectiveTLDService.cpp)
8 /* ***** BEGIN LICENSE BLOCK *****
9 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
10 *
11 * The contents of this file are subject to the Mozilla Public License Version
12 * 1.1 (the "License"); you may not use this file except in compliance with
13 * the License. You may obtain a copy of the License at
14 * http://www.mozilla.org/MPL/
15 *
16 * Software distributed under the License is distributed on an "AS IS" basis,
17 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
18 * for the specific language governing rights and limitations under the
19 * License.
20 *
21 * The Original Code is Mozilla Effective-TLD Service
22 *
23 * The Initial Developer of the Original Code is
24 * Google Inc.
25 * Portions created by the Initial Developer are Copyright (C) 2006
26 * the Initial Developer. All Rights Reserved.
27 *
28 * Contributor(s):
29 * Pamela Greene <pamg.bugs@gmail.com> (original author)
30 * Daniel Witte <dwitte@stanford.edu>
31 *
32 * Alternatively, the contents of this file may be used under the terms of
33 * either the GNU General Public License Version 2 or later (the "GPL"), or
34 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
35 * in which case the provisions of the GPL or the LGPL are applicable instead
36 * of those above. If you wish to allow use of your version of this file only
37 * under the terms of either the GPL or the LGPL, and not to allow others to
38 * use your version of this file under the terms of the MPL, indicate your
39 * decision by deleting the provisions above and replace them with the notice
40 * and other provisions required by the GPL or the LGPL. If you do not delete
41 * the provisions above, a recipient may use your version of this file under
42 * the terms of any one of the MPL, the GPL or the LGPL.
43 *
44 * ***** END LICENSE BLOCK ***** */
45
46 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
47
48 #include "base/check_op.h"
49 #include "base/notreached.h"
50 #include "base/strings/string_util.h"
51 #include "base/strings/utf_string_conversions.h"
52 #include "net/base/lookup_string_in_fixed_set.h"
53 #include "net/base/net_module.h"
54 #include "net/base/url_util.h"
55 #include "url/gurl.h"
56 #include "url/origin.h"
57 #include "url/third_party/mozilla/url_parse.h"
58 #include "url/url_util.h"
59
60 namespace net {
61 namespace registry_controlled_domains {
62
63 namespace {
64 #include "net/base/registry_controlled_domains/effective_tld_names-reversed-inc.cc"
65
66 // See make_dafsa.py for documentation of the generated dafsa byte array.
67
68 const unsigned char* g_graph = kDafsa;
69 size_t g_graph_length = sizeof(kDafsa);
70
71 struct MappedHostComponent {
72 size_t original_begin;
73 size_t original_end;
74
75 size_t canonical_begin;
76 size_t canonical_end;
77 };
78
79 // This version assumes we already removed leading dots from host as well as the
80 // last trailing dot if it had one.
GetRegistryLengthInTrimmedHost(base::StringPiece host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)81 size_t GetRegistryLengthInTrimmedHost(base::StringPiece host,
82 UnknownRegistryFilter unknown_filter,
83 PrivateRegistryFilter private_filter) {
84 size_t length;
85 int type = LookupSuffixInReversedSet(
86 g_graph, g_graph_length, private_filter == INCLUDE_PRIVATE_REGISTRIES,
87 host, &length);
88
89 DCHECK_LE(length, host.size());
90
91 // No rule found in the registry.
92 if (type == kDafsaNotFound) {
93 // If we allow unknown registries, return the length of last subcomponent.
94 if (unknown_filter == INCLUDE_UNKNOWN_REGISTRIES) {
95 const size_t last_dot = host.find_last_of('.');
96 if (last_dot != base::StringPiece::npos)
97 return host.size() - last_dot - 1;
98 }
99 return 0;
100 }
101
102 // Exception rules override wildcard rules when the domain is an exact
103 // match, but wildcards take precedence when there's a subdomain.
104 if (type & kDafsaWildcardRule) {
105 // If the complete host matches, then the host is the wildcard suffix, so
106 // return 0.
107 if (length == host.size())
108 return 0;
109
110 DCHECK_LE(length + 2, host.size());
111 DCHECK_EQ('.', host[host.size() - length - 1]);
112
113 const size_t preceding_dot =
114 host.find_last_of('.', host.size() - length - 2);
115
116 // If no preceding dot, then the host is the registry itself, so return 0.
117 if (preceding_dot == base::StringPiece::npos)
118 return 0;
119
120 // Return suffix size plus size of subdomain.
121 return host.size() - preceding_dot - 1;
122 }
123
124 if (type & kDafsaExceptionRule) {
125 size_t first_dot = host.find_first_of('.', host.size() - length);
126 if (first_dot == base::StringPiece::npos) {
127 // If we get here, we had an exception rule with no dots (e.g.
128 // "!foo"). This would only be valid if we had a corresponding
129 // wildcard rule, which would have to be "*". But we explicitly
130 // disallow that case, so this kind of rule is invalid.
131 // TODO(https://crbug.com/459802): This assumes that all wildcard entries,
132 // such as *.foo.invalid, also have their parent, foo.invalid, as an entry
133 // on the PSL, which is why it returns the length of foo.invalid. This
134 // isn't entirely correct.
135 NOTREACHED() << "Invalid exception rule";
136 return 0;
137 }
138 return host.length() - first_dot - 1;
139 }
140
141 DCHECK_NE(type, kDafsaNotFound);
142
143 // If a complete match, then the host is the registry itself, so return 0.
144 if (length == host.size())
145 return 0;
146
147 return length;
148 }
149
GetRegistryLengthImpl(base::StringPiece host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)150 size_t GetRegistryLengthImpl(base::StringPiece host,
151 UnknownRegistryFilter unknown_filter,
152 PrivateRegistryFilter private_filter) {
153 if (host.empty())
154 return std::string::npos;
155
156 // Skip leading dots.
157 const size_t host_check_begin = host.find_first_not_of('.');
158 if (host_check_begin == base::StringPiece::npos)
159 return 0; // Host is only dots.
160
161 // A single trailing dot isn't relevant in this determination, but does need
162 // to be included in the final returned length.
163 size_t host_check_end = host.size();
164 if (host.back() == '.')
165 --host_check_end;
166
167 size_t length = GetRegistryLengthInTrimmedHost(
168 host.substr(host_check_begin, host_check_end - host_check_begin),
169 unknown_filter, private_filter);
170
171 if (length == 0)
172 return 0;
173
174 return length + host.size() - host_check_end;
175 }
176
GetDomainAndRegistryImpl(base::StringPiece host,PrivateRegistryFilter private_filter)177 base::StringPiece GetDomainAndRegistryImpl(
178 base::StringPiece host,
179 PrivateRegistryFilter private_filter) {
180 DCHECK(!host.empty());
181
182 // Find the length of the registry for this host.
183 const size_t registry_length =
184 GetRegistryLengthImpl(host, INCLUDE_UNKNOWN_REGISTRIES, private_filter);
185 if ((registry_length == std::string::npos) || (registry_length == 0))
186 return base::StringPiece(); // No registry.
187 // The "2" in this next line is 1 for the dot, plus a 1-char minimum preceding
188 // subcomponent length.
189 DCHECK(host.length() >= 2);
190 if (registry_length > (host.length() - 2)) {
191 NOTREACHED() <<
192 "Host does not have at least one subcomponent before registry!";
193 return base::StringPiece();
194 }
195
196 // Move past the dot preceding the registry, and search for the next previous
197 // dot. Return the host from after that dot, or the whole host when there is
198 // no dot.
199 const size_t dot = host.rfind('.', host.length() - registry_length - 2);
200 if (dot == std::string::npos)
201 return host;
202 return host.substr(dot + 1);
203 }
204
205 // Same as GetDomainAndRegistry, but returns the domain and registry as a
206 // StringPiece that references the underlying string of the passed-in |gurl|.
207 // TODO(pkalinnikov): Eliminate this helper by exposing StringPiece as the
208 // interface type for all the APIs.
GetDomainAndRegistryAsStringPiece(base::StringPiece host,PrivateRegistryFilter filter)209 base::StringPiece GetDomainAndRegistryAsStringPiece(
210 base::StringPiece host,
211 PrivateRegistryFilter filter) {
212 if (host.empty() || url::HostIsIPAddress(host))
213 return base::StringPiece();
214 return GetDomainAndRegistryImpl(host, filter);
215 }
216
217 // These two functions append the given string as-is to the given output,
218 // converting to UTF-8 if necessary.
AppendInvalidString(base::StringPiece str,url::CanonOutput * output)219 void AppendInvalidString(base::StringPiece str, url::CanonOutput* output) {
220 output->Append(str.data(), static_cast<int>(str.length()));
221 }
AppendInvalidString(base::StringPiece16 str,url::CanonOutput * output)222 void AppendInvalidString(base::StringPiece16 str, url::CanonOutput* output) {
223 std::string utf8 = base::UTF16ToUTF8(str);
224 output->Append(utf8.data(), static_cast<int>(utf8.length()));
225 }
226
227 // Backend for PermissiveGetHostRegistryLength that handles both UTF-8 and
228 // UTF-16 input. The template type is the std::string type to use (it makes the
229 // typedefs easier than using the character type).
230 template <typename Str>
DoPermissiveGetHostRegistryLength(base::BasicStringPiece<Str> host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)231 size_t DoPermissiveGetHostRegistryLength(base::BasicStringPiece<Str> host,
232 UnknownRegistryFilter unknown_filter,
233 PrivateRegistryFilter private_filter) {
234 std::string canonical_host; // Do not modify outside of canon_output.
235 canonical_host.reserve(host.length());
236 url::StdStringCanonOutput canon_output(&canonical_host);
237
238 std::vector<MappedHostComponent> components;
239
240 for (size_t current = 0; current < host.length(); current++) {
241 size_t begin = current;
242
243 // Advance to next "." or end.
244 current = host.find('.', begin);
245 if (current == std::string::npos)
246 current = host.length();
247
248 MappedHostComponent mapping;
249 mapping.original_begin = begin;
250 mapping.original_end = current;
251 mapping.canonical_begin = static_cast<size_t>(canon_output.length());
252
253 // Try to append the canonicalized version of this component.
254 int current_len = static_cast<int>(current - begin);
255 if (!url::CanonicalizeHostSubstring(
256 host.data(), url::Component(static_cast<int>(begin), current_len),
257 &canon_output)) {
258 // Failed to canonicalize this component; append as-is.
259 AppendInvalidString(host.substr(begin, current_len), &canon_output);
260 }
261
262 mapping.canonical_end = static_cast<size_t>(canon_output.length());
263 components.push_back(mapping);
264
265 if (current < host.length())
266 canon_output.push_back('.');
267 }
268 canon_output.Complete();
269
270 size_t canonical_rcd_len =
271 GetRegistryLengthImpl(canonical_host, unknown_filter, private_filter);
272 if (canonical_rcd_len == 0 || canonical_rcd_len == std::string::npos)
273 return canonical_rcd_len; // Error or no registry controlled domain.
274
275 // Find which host component the result started in.
276 size_t canonical_rcd_begin = canonical_host.length() - canonical_rcd_len;
277 for (const auto& mapping : components) {
278 // In the common case, GetRegistryLengthImpl will identify the beginning
279 // of a component and we can just return where that component was in the
280 // original string.
281 if (canonical_rcd_begin == mapping.canonical_begin)
282 return host.length() - mapping.original_begin;
283
284 if (canonical_rcd_begin >= mapping.canonical_end)
285 continue;
286
287 // The registry controlled domain begin was identified as being in the
288 // middle of this dot-separated domain component in the non-canonical
289 // input. This indicates some form of escaped dot, or a non-ASCII
290 // character that was canonicalized to a dot.
291 //
292 // Brute-force search from the end by repeatedly canonicalizing longer
293 // substrings until we get a match for the canonicalized version. This
294 // can't be done with binary search because canonicalization might increase
295 // or decrease the length of the produced string depending on where it's
296 // split. This depends on the canonicalization process not changing the
297 // order of the characters. Punycode can change the order of characters,
298 // but it doesn't work across dots so this is safe.
299
300 // Expected canonical registry controlled domain.
301 base::StringPiece canonical_rcd(&canonical_host[canonical_rcd_begin],
302 canonical_rcd_len);
303
304 for (int current_try = static_cast<int>(mapping.original_end) - 1;
305 current_try >= static_cast<int>(mapping.original_begin);
306 current_try--) {
307 std::string try_string;
308 url::StdStringCanonOutput try_output(&try_string);
309
310 if (!url::CanonicalizeHostSubstring(
311 host.data(),
312 url::Component(
313 current_try,
314 static_cast<int>(mapping.original_end) - current_try),
315 &try_output))
316 continue; // Invalid substring, skip.
317
318 try_output.Complete();
319 if (try_string == canonical_rcd)
320 return host.length() - current_try;
321 }
322 }
323
324 NOTREACHED();
325 return canonical_rcd_len;
326 }
327
SameDomainOrHost(base::StringPiece host1,base::StringPiece host2,PrivateRegistryFilter filter)328 bool SameDomainOrHost(base::StringPiece host1,
329 base::StringPiece host2,
330 PrivateRegistryFilter filter) {
331 // Quickly reject cases where either host is empty.
332 if (host1.empty() || host2.empty())
333 return false;
334
335 // Check for exact host matches, which is faster than looking up the domain
336 // and registry.
337 if (host1 == host2)
338 return true;
339
340 // Check for a domain and registry match.
341 const base::StringPiece& domain1 =
342 GetDomainAndRegistryAsStringPiece(host1, filter);
343 return !domain1.empty() &&
344 (domain1 == GetDomainAndRegistryAsStringPiece(host2, filter));
345 }
346
347 } // namespace
348
GetDomainAndRegistry(const GURL & gurl,PrivateRegistryFilter filter)349 std::string GetDomainAndRegistry(const GURL& gurl,
350 PrivateRegistryFilter filter) {
351 return GetDomainAndRegistryAsStringPiece(gurl.host_piece(), filter)
352 .as_string();
353 }
354
GetDomainAndRegistry(const url::Origin & origin,PrivateRegistryFilter filter)355 std::string GetDomainAndRegistry(const url::Origin& origin,
356 PrivateRegistryFilter filter) {
357 return GetDomainAndRegistryAsStringPiece(origin.host(), filter).as_string();
358 }
359
GetDomainAndRegistry(base::StringPiece host,PrivateRegistryFilter filter)360 std::string GetDomainAndRegistry(base::StringPiece host,
361 PrivateRegistryFilter filter) {
362 url::CanonHostInfo host_info;
363 const std::string canon_host(CanonicalizeHost(host, &host_info));
364 if (canon_host.empty() || host_info.IsIPAddress())
365 return std::string();
366 return GetDomainAndRegistryImpl(canon_host, filter).as_string();
367 }
368
SameDomainOrHost(const GURL & gurl1,const GURL & gurl2,PrivateRegistryFilter filter)369 bool SameDomainOrHost(
370 const GURL& gurl1,
371 const GURL& gurl2,
372 PrivateRegistryFilter filter) {
373 return SameDomainOrHost(gurl1.host_piece(), gurl2.host_piece(), filter);
374 }
375
SameDomainOrHost(const url::Origin & origin1,const url::Origin & origin2,PrivateRegistryFilter filter)376 bool SameDomainOrHost(const url::Origin& origin1,
377 const url::Origin& origin2,
378 PrivateRegistryFilter filter) {
379 return SameDomainOrHost(origin1.host(), origin2.host(), filter);
380 }
381
SameDomainOrHost(const url::Origin & origin1,const base::Optional<url::Origin> & origin2,PrivateRegistryFilter filter)382 bool SameDomainOrHost(const url::Origin& origin1,
383 const base::Optional<url::Origin>& origin2,
384 PrivateRegistryFilter filter) {
385 return origin2.has_value() &&
386 SameDomainOrHost(origin1, origin2.value(), filter);
387 }
388
SameDomainOrHost(const GURL & gurl,const url::Origin & origin,PrivateRegistryFilter filter)389 bool SameDomainOrHost(const GURL& gurl,
390 const url::Origin& origin,
391 PrivateRegistryFilter filter) {
392 return SameDomainOrHost(gurl.host_piece(), origin.host(), filter);
393 }
394
GetRegistryLength(const GURL & gurl,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)395 size_t GetRegistryLength(
396 const GURL& gurl,
397 UnknownRegistryFilter unknown_filter,
398 PrivateRegistryFilter private_filter) {
399 return GetRegistryLengthImpl(gurl.host_piece(), unknown_filter,
400 private_filter);
401 }
402
HostHasRegistryControlledDomain(base::StringPiece host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)403 bool HostHasRegistryControlledDomain(base::StringPiece host,
404 UnknownRegistryFilter unknown_filter,
405 PrivateRegistryFilter private_filter) {
406 url::CanonHostInfo host_info;
407 const std::string canon_host(CanonicalizeHost(host, &host_info));
408
409 size_t rcd_length;
410 switch (host_info.family) {
411 case url::CanonHostInfo::IPV4:
412 case url::CanonHostInfo::IPV6:
413 // IP addresses don't have R.C.D.'s.
414 return false;
415 case url::CanonHostInfo::BROKEN:
416 // Host is not canonicalizable. Fall back to the slower "permissive"
417 // version.
418 rcd_length =
419 PermissiveGetHostRegistryLength(host, unknown_filter, private_filter);
420 break;
421 case url::CanonHostInfo::NEUTRAL:
422 rcd_length =
423 GetRegistryLengthImpl(canon_host, unknown_filter, private_filter);
424 break;
425 default:
426 NOTREACHED();
427 return false;
428 }
429 return (rcd_length != 0) && (rcd_length != std::string::npos);
430 }
431
GetCanonicalHostRegistryLength(base::StringPiece canon_host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)432 size_t GetCanonicalHostRegistryLength(base::StringPiece canon_host,
433 UnknownRegistryFilter unknown_filter,
434 PrivateRegistryFilter private_filter) {
435 #ifndef NDEBUG
436 // Ensure passed-in host name is canonical.
437 url::CanonHostInfo host_info;
438 DCHECK_EQ(net::CanonicalizeHost(canon_host, &host_info), canon_host);
439 #endif
440
441 return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter);
442 }
443
PermissiveGetHostRegistryLength(base::StringPiece host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)444 size_t PermissiveGetHostRegistryLength(base::StringPiece host,
445 UnknownRegistryFilter unknown_filter,
446 PrivateRegistryFilter private_filter) {
447 return DoPermissiveGetHostRegistryLength<std::string>(host, unknown_filter,
448 private_filter);
449 }
450
PermissiveGetHostRegistryLength(base::StringPiece16 host,UnknownRegistryFilter unknown_filter,PrivateRegistryFilter private_filter)451 size_t PermissiveGetHostRegistryLength(base::StringPiece16 host,
452 UnknownRegistryFilter unknown_filter,
453 PrivateRegistryFilter private_filter) {
454 return DoPermissiveGetHostRegistryLength<base::string16>(host, unknown_filter,
455 private_filter);
456 }
457
SetFindDomainGraph()458 void SetFindDomainGraph() {
459 g_graph = kDafsa;
460 g_graph_length = sizeof(kDafsa);
461 }
462
SetFindDomainGraph(const unsigned char * domains,size_t length)463 void SetFindDomainGraph(const unsigned char* domains, size_t length) {
464 CHECK(domains);
465 CHECK_NE(length, 0u);
466 g_graph = domains;
467 g_graph_length = length;
468 }
469
470 } // namespace registry_controlled_domains
471 } // namespace net
472