aw_safe_browsing_allowlist_manager.cc 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242
  1. // Copyright 2017 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. #include "android_webview/browser/safe_browsing/aw_safe_browsing_allowlist_manager.h"
  5. #include <map>
  6. #include <memory>
  7. #include <utility>
  8. #include "base/bind.h"
  9. #include "base/containers/adapters.h"
  10. #include "base/logging.h"
  11. #include "base/strings/string_piece.h"
  12. #include "base/strings/string_split.h"
  13. #include "base/strings/string_util.h"
  14. #include "base/task/sequenced_task_runner.h"
  15. #include "base/task/task_runner_util.h"
  16. #include "base/threading/thread_task_runner_handle.h"
  17. #include "net/base/url_util.h"
  18. #include "url/url_util.h"
  19. namespace android_webview {
  20. // This is a simple trie structure designed for handling host/domain matches
  21. // for Safebrowsing allowlisting. For the match rules, see the class header.
  22. //
  23. // It is easy to visualize the trie edges as hostname components of a url in
  24. // reverse order. For example an allowlist of google.com will have a tree
  25. // tree structure as below.
  26. // root
  27. // | com
  28. // Node1
  29. // google/ \ example
  30. // Node2 Node3
  31. //
  32. // Normally, a search in the tree should end in a leaf node for a positive
  33. // match. For example in the tree above com.google and com.example are matches.
  34. // However, the allowlisting also allows matching subdomains if there is a
  35. // leading dot, for example, see ."google.com" and a.google.com below:
  36. // root
  37. // | com
  38. // Node1
  39. // | google
  40. // Node2
  41. // | a
  42. // Node3
  43. // Here, both Node2 and Node3 are valid terminal nodes to terminate a match.
  44. // The boolean is_terminal indicates whether a node can successfully terminate
  45. // a search (aka. whether this rule was entered to the allowlist) and
  46. // match_prefix indicate if this should match exactly, or just do a prefix
  47. // match.
  48. // The structure is optimized such that if a node already allows a prefix
  49. // match, then there is no need for it to have children, or if it has children
  50. // these children are removed.
  51. struct TrieNode {
  52. std::map<std::string, std::unique_ptr<TrieNode>> children;
  53. bool match_prefix = false;
  54. bool is_terminal = false;
  55. };
  56. namespace {
  57. void InsertRuleToTrie(const std::vector<base::StringPiece>& components,
  58. TrieNode* root,
  59. bool match_prefix) {
  60. TrieNode* node = root;
  61. for (const auto& hostcomp : base::Reversed(components)) {
  62. DCHECK(!node->match_prefix);
  63. std::string component(hostcomp);
  64. auto child_node = node->children.find(component);
  65. if (child_node == node->children.end()) {
  66. std::unique_ptr<TrieNode> temp = std::make_unique<TrieNode>();
  67. TrieNode* current = temp.get();
  68. node->children.emplace(component, std::move(temp));
  69. node = current;
  70. } else {
  71. node = child_node->second.get();
  72. // Optimization. No need to add new nodes as this node matches prefixes.
  73. DCHECK(node);
  74. if (node->match_prefix)
  75. return;
  76. }
  77. }
  78. DCHECK_NE(node, root);
  79. // Optimization. If match_prefix is true, remove all nodes originating
  80. // from that node.
  81. if (match_prefix) {
  82. node->match_prefix = true;
  83. node->children.clear();
  84. }
  85. node->is_terminal = true;
  86. }
  87. std::vector<base::StringPiece> SplitHost(const GURL& url) {
  88. std::vector<base::StringPiece> components;
  89. if (url.HostIsIPAddress()) {
  90. components.push_back(url.host_piece());
  91. } else {
  92. components =
  93. base::SplitStringPiece(url.host_piece(), ".", base::KEEP_WHITESPACE,
  94. base::SPLIT_WANT_NONEMPTY);
  95. }
  96. DCHECK_GT(components.size(), 0u);
  97. return components;
  98. }
  99. // Rule is a UTF-8 wide string.
  100. bool AddRuleToAllowlist(base::StringPiece rule, TrieNode* root) {
  101. if (rule.empty()) {
  102. return false;
  103. }
  104. // Leading dot means to do an exact match.
  105. bool started_with_dot = false;
  106. if (rule.front() == '.') {
  107. rule.remove_prefix(1); // Strip it for the rest of the handling.
  108. started_with_dot = true;
  109. }
  110. // With the dot removed |rule| should look like a hostname.
  111. GURL test_url("http://" + std::string(rule));
  112. if (!test_url.is_valid()) {
  113. return false;
  114. }
  115. bool has_path = test_url.has_path() && test_url.path() != "/";
  116. // Verify that it is a hostname.
  117. if (!test_url.has_host() || has_path || test_url.has_port() ||
  118. test_url.has_query() || test_url.has_password() ||
  119. test_url.has_username() || test_url.has_ref()) {
  120. return false;
  121. }
  122. bool match_prefix = false;
  123. if (test_url.HostIsIPAddress()) {
  124. // leading dots are not allowed for IP addresses. IP addresses are always
  125. // exact match.
  126. if (started_with_dot) {
  127. return false;
  128. }
  129. match_prefix = false;
  130. } else {
  131. match_prefix = !started_with_dot;
  132. }
  133. InsertRuleToTrie(SplitHost(test_url), root, match_prefix);
  134. return true;
  135. }
  136. bool AddRules(const std::vector<std::string>& rules, TrieNode* root) {
  137. for (auto rule : rules) {
  138. if (!AddRuleToAllowlist(rule, root)) {
  139. LOG(ERROR) << " invalid allowlist rule " << rule;
  140. return false;
  141. }
  142. }
  143. return true;
  144. }
  145. bool IsAllowed(const GURL& url, const TrieNode* node) {
  146. std::vector<base::StringPiece> components = SplitHost(url);
  147. for (const base::StringPiece& component : base::Reversed(components)) {
  148. if (node->match_prefix) {
  149. return true;
  150. }
  151. auto child_node = node->children.find(std::string(component));
  152. if (child_node == node->children.end()) {
  153. return false;
  154. } else {
  155. node = child_node->second.get();
  156. DCHECK(node);
  157. }
  158. }
  159. // DCHECK optimization. A match_prefix node should have no children.
  160. DCHECK(!node->match_prefix || node->children.empty());
  161. // If trie search finished in a terminal node, host is found in trie. The
  162. // root node is not a terminal node.
  163. return node->is_terminal;
  164. }
  165. } // namespace
  166. AwSafeBrowsingAllowlistManager::AwSafeBrowsingAllowlistManager(
  167. const scoped_refptr<base::SequencedTaskRunner>& background_task_runner,
  168. const scoped_refptr<base::SequencedTaskRunner>& io_task_runner)
  169. : background_task_runner_(background_task_runner),
  170. io_task_runner_(io_task_runner),
  171. ui_task_runner_(base::ThreadTaskRunnerHandle::Get()),
  172. allowlist_(std::make_unique<TrieNode>()) {}
  173. AwSafeBrowsingAllowlistManager::~AwSafeBrowsingAllowlistManager() {}
  174. void AwSafeBrowsingAllowlistManager::SetAllowlist(
  175. std::unique_ptr<TrieNode> allowlist) {
  176. DCHECK(io_task_runner_->RunsTasksInCurrentSequence());
  177. allowlist_ = std::move(allowlist);
  178. }
  179. // A task that builds the allowlist on a background thread.
  180. void AwSafeBrowsingAllowlistManager::BuildAllowlist(
  181. const std::vector<std::string>& rules,
  182. base::OnceCallback<void(bool)> callback) {
  183. DCHECK(background_task_runner_->RunsTasksInCurrentSequence());
  184. std::unique_ptr<TrieNode> allowlist(std::make_unique<TrieNode>());
  185. bool success = AddRules(rules, allowlist.get());
  186. DCHECK(!allowlist->is_terminal);
  187. DCHECK(!allowlist->match_prefix);
  188. ui_task_runner_->PostTask(FROM_HERE,
  189. base::BindOnce(std::move(callback), success));
  190. if (success) {
  191. // use base::Unretained as AwSafeBrowsingAllowlistManager is a singleton and
  192. // not cleaned.
  193. io_task_runner_->PostTask(
  194. FROM_HERE,
  195. base::BindOnce(&AwSafeBrowsingAllowlistManager::SetAllowlist,
  196. base::Unretained(this), std::move(allowlist)));
  197. }
  198. }
  199. void AwSafeBrowsingAllowlistManager::SetAllowlistOnUIThread(
  200. std::vector<std::string>&& rules,
  201. base::OnceCallback<void(bool)> callback) {
  202. DCHECK(ui_task_runner_->RunsTasksInCurrentSequence());
  203. // use base::Unretained as AwSafeBrowsingAllowlistManager is a singleton and
  204. // not cleaned.
  205. background_task_runner_->PostTask(
  206. FROM_HERE, base::BindOnce(&AwSafeBrowsingAllowlistManager::BuildAllowlist,
  207. base::Unretained(this), std::move(rules),
  208. std::move(callback)));
  209. }
  210. bool AwSafeBrowsingAllowlistManager::IsUrlAllowed(const GURL& url) const {
  211. DCHECK(io_task_runner_->RunsTasksInCurrentSequence());
  212. if (!url.has_host()) {
  213. return false;
  214. }
  215. return IsAllowed(url, allowlist_.get());
  216. }
  217. } // namespace android_webview