ax_tree_fuzzer_util.cc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355
  1. // Copyright 2022 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 "ui/accessibility/ax_tree_fuzzer_util.h"
  5. #include "ui/accessibility/ax_enums.mojom.h"
  6. #include "ui/accessibility/ax_node.h"
  7. #include "ui/accessibility/ax_node_data.h"
  8. #include "ui/accessibility/ax_node_position.h"
  9. #include "ui/accessibility/ax_range.h"
  10. #include "ui/accessibility/ax_role_properties.h"
  11. #include "ui/accessibility/ax_tree.h"
  12. #include "ui/accessibility/ax_tree_data.h"
  13. #include "ui/accessibility/ax_tree_id.h"
  14. #include "ui/accessibility/ax_tree_update.h"
  15. FuzzerData::FuzzerData(const unsigned char* data, size_t size)
  16. : data_(data), data_size_(size), data_index_(0) {}
  17. size_t FuzzerData::RemainingBytes() {
  18. return data_size_ - data_index_;
  19. }
  20. unsigned char FuzzerData::NextByte() {
  21. CHECK(RemainingBytes());
  22. return data_[data_index_++];
  23. }
  24. const unsigned char* FuzzerData::NextBytes(size_t amount) {
  25. CHECK(RemainingBytes() >= amount);
  26. const unsigned char* current_position = &data_[data_index_];
  27. data_index_ += amount;
  28. return current_position;
  29. }
  30. ui::AXTree* AXTreeFuzzerGenerator::GetTree() {
  31. return tree_manager_.GetTree();
  32. }
  33. void AXTreeFuzzerGenerator::GenerateInitialUpdate(FuzzerData& fuzz_data,
  34. int node_count) {
  35. max_assigned_node_id_ = 1;
  36. ui::AXTreeUpdate initial_state;
  37. initial_state.root_id = max_assigned_node_id_++;
  38. initial_state.has_tree_data = true;
  39. initial_state.tree_data.tree_id = ui::AXTreeID::CreateNewAXTreeID();
  40. ui::AXNodeData root;
  41. root.id = initial_state.root_id;
  42. root.role = ax::mojom::Role::kRootWebArea;
  43. std::stack<size_t> parent_index_stack;
  44. parent_index_stack.push(initial_state.nodes.size());
  45. initial_state.nodes.push_back(root);
  46. // As we give out ids sequentially, starting at 1, the
  47. // ...max_assigned_node_id_... is equivalent to the node count.
  48. while (fuzz_data.RemainingBytes() >= kMinimumNewNodeFuzzDataSize &&
  49. max_assigned_node_id_ < node_count) {
  50. size_t extra_data_size =
  51. fuzz_data.RemainingBytes() - kMinimumNewNodeFuzzDataSize;
  52. ui::AXNodeData& parent = initial_state.nodes[parent_index_stack.top()];
  53. // Create a node.
  54. ui::AXNodeData node = CreateChildNodeData(parent, max_assigned_node_id_++);
  55. // Determine role.
  56. node.role = GetInterestingRole(fuzz_data.NextByte(), parent.role);
  57. // Add role-specific properties.
  58. AddRoleSpecificProperties(
  59. fuzz_data, node,
  60. parent.GetStringAttribute(ax::mojom::StringAttribute::kName),
  61. extra_data_size);
  62. // Determine the relationship of the next node from fuzz data. See
  63. // implementation of `DetermineNextNodeRelationship` for details.
  64. size_t ancestor_pop_count;
  65. switch (DetermineNextNodeRelationship(node.role, fuzz_data.NextByte())) {
  66. case kChild:
  67. CHECK(CanHaveChildren(node.role));
  68. parent_index_stack.push(initial_state.nodes.size());
  69. break;
  70. case kSibling:
  71. initial_state.nodes.push_back(node);
  72. break;
  73. case kSiblingToAncestor:
  74. ancestor_pop_count = 1 + fuzz_data.NextByte() % kMaxAncestorPopCount;
  75. for (size_t i = 0;
  76. i < ancestor_pop_count && parent_index_stack.size() > 1; ++i) {
  77. parent_index_stack.pop();
  78. }
  79. break;
  80. }
  81. initial_state.nodes.push_back(node);
  82. }
  83. // Run with --v=1 to aid in debugging a specific crash.
  84. VLOG(1) << "Input accessibility tree:\n" << initial_state.ToString();
  85. tree_manager_.SetTree(std::make_unique<ui::AXTree>(initial_state));
  86. }
  87. // Pre-order depth first walk of tree. Skip over deleted subtrees.
  88. void AXTreeFuzzerGenerator::RecursiveGenerateUpdate(
  89. const ui::AXNode* node,
  90. ui::AXTreeUpdate& tree_update,
  91. FuzzerData& fuzz_data,
  92. std::set<ui::AXNodeID>& updated_nodes) {
  93. // Stop traversing if we run out of fuzz data.
  94. if (fuzz_data.RemainingBytes() <= kMinimumNewNodeFuzzDataSize)
  95. return;
  96. size_t extra_data_size =
  97. fuzz_data.RemainingBytes() - kMinimumNewNodeFuzzDataSize;
  98. AXTreeFuzzerGenerator::TreeUpdateOperation operation = kNoOperation;
  99. if (!updated_nodes.count(node->id()))
  100. operation = DetermineTreeUpdateOperation(node, fuzz_data.NextByte());
  101. switch (operation) {
  102. case kAddChild: {
  103. // Determine where to insert the node.
  104. // Create node and attach to parent.
  105. ui::AXNodeData parent = node->data();
  106. ui::AXNodeData child =
  107. CreateChildNodeData(parent, max_assigned_node_id_++);
  108. // Determine role.
  109. child.role = GetInterestingRole(fuzz_data.NextByte(), node->GetRole());
  110. // Add role-specific properties.
  111. AddRoleSpecificProperties(
  112. fuzz_data, child,
  113. node->GetStringAttribute(ax::mojom::StringAttribute::kName),
  114. extra_data_size);
  115. // Also add inline text child if we can.
  116. ui::AXNodeData inline_text_data;
  117. if (ui::CanHaveInlineTextBoxChildren(child.role)) {
  118. inline_text_data = CreateChildNodeData(child, max_assigned_node_id_++);
  119. inline_text_data.role = ax::mojom::Role::kInlineTextBox;
  120. inline_text_data.SetName(
  121. child.GetStringAttribute(ax::mojom::StringAttribute::kName));
  122. }
  123. // Add both the current node (parent) and the child to the tree update.
  124. tree_update.nodes.push_back(parent);
  125. tree_update.nodes.push_back(child);
  126. updated_nodes.emplace(parent.id);
  127. updated_nodes.emplace(child.id);
  128. if (inline_text_data.id != ui::kInvalidAXNodeID) {
  129. tree_update.nodes.push_back(inline_text_data);
  130. updated_nodes.emplace(inline_text_data.id);
  131. }
  132. break;
  133. }
  134. case kRemoveNode: {
  135. const ui::AXNode* parent = node->GetParent();
  136. if (updated_nodes.count(parent->id()))
  137. break;
  138. // Determine what node to delete.
  139. // To delete a node, just find the parent and update the child list to
  140. // no longer include this node.
  141. ui::AXNodeData parent_update = parent->data();
  142. parent_update.child_ids.erase(
  143. std::remove(parent_update.child_ids.begin(),
  144. parent_update.child_ids.end(), node->id()),
  145. parent_update.child_ids.end());
  146. tree_update.nodes.push_back(parent_update);
  147. updated_nodes.emplace(parent_update.id);
  148. // This node was deleted, don't traverse to the subtree.
  149. return;
  150. }
  151. case kTextChange: {
  152. // Modify the text.
  153. const ui::AXNode* child_inline_text = node->GetFirstChild();
  154. if (!child_inline_text ||
  155. child_inline_text->GetRole() != ax::mojom::Role::kInlineTextBox) {
  156. break;
  157. }
  158. ui::AXNodeData static_text_data = node->data();
  159. ui::AXNodeData inline_text_data = child_inline_text->data();
  160. size_t text_size =
  161. kMinTextFuzzDataSize + fuzz_data.NextByte() % kMaxTextFuzzDataSize;
  162. if (text_size > extra_data_size)
  163. text_size = extra_data_size;
  164. extra_data_size -= text_size;
  165. inline_text_data.SetName(
  166. GenerateInterestingText(fuzz_data.NextBytes(text_size), text_size));
  167. static_text_data.SetName(inline_text_data.GetStringAttribute(
  168. ax::mojom::StringAttribute::kName));
  169. tree_update.nodes.push_back(static_text_data);
  170. tree_update.nodes.push_back(inline_text_data);
  171. updated_nodes.emplace(static_text_data.id);
  172. updated_nodes.emplace(inline_text_data.id);
  173. break;
  174. }
  175. case kNoOperation:
  176. break;
  177. }
  178. // Visit subtree.
  179. for (auto iter = node->AllChildrenBegin(); iter != node->AllChildrenEnd();
  180. ++iter) {
  181. RecursiveGenerateUpdate(iter.get(), tree_update, fuzz_data, updated_nodes);
  182. }
  183. }
  184. // When building a tree update, we must take care to not create an
  185. // unserializable tree. If the tree does not serialize, things like
  186. // TestAXTreeObserver will not be able to handle the incorrectly serialized
  187. // tree. This will require us to abort the fuzz run.
  188. bool AXTreeFuzzerGenerator::GenerateTreeUpdate(FuzzerData& fuzz_data,
  189. size_t node_count) {
  190. ui::AXTreeUpdate tree_update;
  191. std::set<ui::AXNodeID> updated_nodes;
  192. RecursiveGenerateUpdate(tree_manager_.GetRootAsAXNode(), tree_update,
  193. fuzz_data, updated_nodes);
  194. return GetTree()->Unserialize(tree_update);
  195. }
  196. ui::AXNodeID AXTreeFuzzerGenerator::GetMaxAssignedID() const {
  197. return max_assigned_node_id_;
  198. }
  199. ui::AXNodeData AXTreeFuzzerGenerator::CreateChildNodeData(
  200. ui::AXNodeData& parent,
  201. ui::AXNodeID new_node_id) {
  202. ui::AXNodeData node;
  203. node.id = new_node_id;
  204. // Connect parent to this node.
  205. parent.child_ids.push_back(node.id);
  206. return node;
  207. }
  208. // Determine the relationship of the next node from fuzz data.
  209. AXTreeFuzzerGenerator::NextNodeRelationship
  210. AXTreeFuzzerGenerator::DetermineNextNodeRelationship(ax::mojom::Role role,
  211. unsigned char byte) {
  212. // Force this to have a inline text child if it can.
  213. if (ui::CanHaveInlineTextBoxChildren(role))
  214. return NextNodeRelationship::kChild;
  215. // Don't allow inline text boxes to have children or siblings.
  216. if (role == ax::mojom::Role::kInlineTextBox)
  217. return NextNodeRelationship::kSiblingToAncestor;
  218. // Determine next node using fuzz data.
  219. NextNodeRelationship relationship =
  220. static_cast<NextNodeRelationship>(byte % 3);
  221. // Check to ensure we can have children.
  222. if (relationship == NextNodeRelationship::kChild && !CanHaveChildren(role)) {
  223. return NextNodeRelationship::kSibling;
  224. }
  225. return relationship;
  226. }
  227. AXTreeFuzzerGenerator::TreeUpdateOperation
  228. AXTreeFuzzerGenerator::DetermineTreeUpdateOperation(const ui::AXNode* node,
  229. unsigned char byte) {
  230. switch (byte % 4) {
  231. case 0:
  232. // Don't delete the following nodes:
  233. // 1) The root. TODO(janewman): implement root changes in an update.
  234. // 2) Inline text. We don't want to leave Static text nodes without inline
  235. // text children.
  236. if (ax::mojom::Role::kRootWebArea != node->GetRole())
  237. return kRemoveNode;
  238. ABSL_FALLTHROUGH_INTENDED;
  239. case 1:
  240. // Check to ensure this node can have children. Also consider that we
  241. // shouldn't add children to static text, as these nodes only expect to
  242. // have a inline text single child.
  243. if (CanHaveChildren(node->GetRole()) && !ui::IsText(node->GetRole()))
  244. return kAddChild;
  245. ABSL_FALLTHROUGH_INTENDED;
  246. case 2:
  247. if (ax::mojom::Role::kStaticText == node->GetRole())
  248. return kTextChange;
  249. ABSL_FALLTHROUGH_INTENDED;
  250. default:
  251. return kNoOperation;
  252. }
  253. }
  254. void AXTreeFuzzerGenerator::AddRoleSpecificProperties(
  255. FuzzerData& fuzz_data,
  256. ui::AXNodeData& node,
  257. const std::string& parentName,
  258. size_t extra_data_size) {
  259. // TODO(janewman): Add ignored state.
  260. // Add role-specific properties.
  261. if (node.role == ax::mojom::Role::kInlineTextBox) {
  262. node.SetName(parentName);
  263. } else if (node.role == ax::mojom::Role::kLineBreak) {
  264. node.SetName("\n");
  265. } else if (ui::IsText(node.role)) {
  266. size_t text_size =
  267. kMinTextFuzzDataSize + fuzz_data.NextByte() % kMaxTextFuzzDataSize;
  268. if (text_size > extra_data_size)
  269. text_size = extra_data_size;
  270. extra_data_size -= text_size;
  271. node.SetName(
  272. GenerateInterestingText(fuzz_data.NextBytes(text_size), text_size));
  273. }
  274. }
  275. ax::mojom::Role AXTreeFuzzerGenerator::GetInterestingRole(
  276. unsigned char byte,
  277. ax::mojom::Role parent_role) {
  278. if (ui::CanHaveInlineTextBoxChildren(parent_role))
  279. return ax::mojom::Role::kInlineTextBox;
  280. // Bias towards creating text nodes so we end up with more text in the tree.
  281. switch (byte % 7) {
  282. default:
  283. case 0:
  284. case 1:
  285. case 2:
  286. return ax::mojom::Role::kStaticText;
  287. case 3:
  288. return ax::mojom::Role::kLineBreak;
  289. case 4:
  290. return ax::mojom::Role::kParagraph;
  291. case 5:
  292. return ax::mojom::Role::kGenericContainer;
  293. case 6:
  294. return ax::mojom::Role::kGroup;
  295. }
  296. }
  297. bool AXTreeFuzzerGenerator::CanHaveChildren(ax::mojom::Role role) {
  298. switch (role) {
  299. case ax::mojom::Role::kInlineTextBox:
  300. return false;
  301. default:
  302. return true;
  303. }
  304. }
  305. std::u16string AXTreeFuzzerGenerator::GenerateInterestingText(
  306. const unsigned char* data,
  307. size_t size) {
  308. std::u16string wide_str;
  309. for (size_t i = 0; i + 1 < size; i += 2) {
  310. char16_t char_16 = data[i] << 8;
  311. char_16 |= data[i + 1];
  312. // Don't insert a null character.
  313. if (char_16)
  314. wide_str.push_back(char_16);
  315. }
  316. return wide_str;
  317. }