ax_node_position_fuzzer.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410
  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_enums.mojom.h"
  5. #include "ui/accessibility/ax_node.h"
  6. #include "ui/accessibility/ax_node_data.h"
  7. #include "ui/accessibility/ax_node_position.h"
  8. #include "ui/accessibility/ax_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_fuzzer_util.h"
  14. #include "ui/accessibility/ax_tree_id.h"
  15. #include "ui/accessibility/ax_tree_update.h"
  16. #include "ui/accessibility/test_ax_tree_manager.h"
  17. // Max amount of fuzz data needed to create the next position
  18. const size_t kNextNodePositionMaxDataSize = 4;
  19. // Min/Max node size for generated tree.
  20. const size_t kMinNodeCount = 10;
  21. const size_t kMaxNodeCount = kMinNodeCount + 50;
  22. // Min fuzz data needed for fuzzer to function.
  23. // Tree of minimum size with text for each node + 2 positions.
  24. const size_t kMinFuzzDataSize =
  25. kMinNodeCount * AXTreeFuzzerGenerator::kMinimumNewNodeFuzzDataSize +
  26. kMinNodeCount * AXTreeFuzzerGenerator::kMinTextFuzzDataSize +
  27. 2 * kNextNodePositionMaxDataSize;
  28. // Cap fuzz data to avoid slowness.
  29. const size_t kMaxFuzzDataSize = 20000;
  30. using TestPositionType =
  31. std::unique_ptr<ui::AXPosition<ui::AXNodePosition, ui::AXNode>>;
  32. using TestPositionRange =
  33. ui::AXRange<ui::AXPosition<ui::AXNodePosition, ui::AXNode>>;
  34. // Helper to create positions in the given tree.
  35. class AXNodePositionFuzzerGenerator {
  36. public:
  37. AXNodePositionFuzzerGenerator(ui::AXTree* tree,
  38. ui::AXNodeID max_id,
  39. FuzzerData& fuzzer_data);
  40. TestPositionType CreateNewPosition();
  41. TestPositionType GenerateNextPosition(TestPositionType& current_position,
  42. TestPositionType& previous_position);
  43. static void CallPositionAPIs(TestPositionType& position,
  44. TestPositionType& other_position);
  45. private:
  46. static ax::mojom::MoveDirection GenerateMoveDirection(unsigned char byte);
  47. static ax::mojom::TextAffinity GenerateTextAffinity(unsigned char byte);
  48. static ui::AXPositionKind GeneratePositionKind(unsigned char byte);
  49. static ui::AXPositionAdjustmentBehavior GenerateAdjustmentBehavior(
  50. unsigned char byte);
  51. static ui::AXMovementOptions GenerateMovementOptions(
  52. unsigned char behavior_byte,
  53. unsigned char detection_byte);
  54. TestPositionType CreateNewPosition(ui::AXNodeID anchor_id,
  55. int child_index_or_text_offset,
  56. ui::AXPositionKind position_kind,
  57. ax::mojom::TextAffinity affinity);
  58. ui::AXTree* tree_;
  59. const ui::AXNodeID max_id_;
  60. FuzzerData& fuzzer_data_;
  61. };
  62. AXNodePositionFuzzerGenerator::AXNodePositionFuzzerGenerator(
  63. ui::AXTree* tree,
  64. ui::AXNodeID max_id,
  65. FuzzerData& fuzzer_data)
  66. : tree_(tree), max_id_(max_id), fuzzer_data_(fuzzer_data) {}
  67. TestPositionType AXNodePositionFuzzerGenerator::CreateNewPosition() {
  68. return CreateNewPosition(fuzzer_data_.NextByte(), fuzzer_data_.NextByte(),
  69. GeneratePositionKind(fuzzer_data_.NextByte()),
  70. GenerateTextAffinity(fuzzer_data_.NextByte()));
  71. }
  72. TestPositionType AXNodePositionFuzzerGenerator::CreateNewPosition(
  73. ui::AXNodeID anchor_id,
  74. int child_index_or_text_offset,
  75. ui::AXPositionKind position_kind,
  76. ax::mojom::TextAffinity affinity) {
  77. // To ensure that anchor_id is between |ui::kInvalidAXNodeID| and the max ID
  78. // of the tree (non-inclusive), get a number [0, max_id - 1) and then shift by
  79. // 1 to get [1, max_id)
  80. anchor_id = (anchor_id % (max_id_ - 1)) + 1;
  81. ui::AXNode* anchor = tree_->GetFromId(anchor_id);
  82. DCHECK(anchor);
  83. switch (position_kind) {
  84. case ui::AXPositionKind::TREE_POSITION:
  85. // Avoid division by zero in the case where the node has no children.
  86. child_index_or_text_offset =
  87. anchor->GetChildCount()
  88. ? child_index_or_text_offset % anchor->GetChildCount()
  89. : 0;
  90. return ui::AXNodePosition::CreateTreePosition(
  91. tree_->GetAXTreeID(), anchor_id, child_index_or_text_offset);
  92. case ui::AXPositionKind::TEXT_POSITION: {
  93. // Avoid division by zero in the case where the node has no text.
  94. child_index_or_text_offset =
  95. anchor->GetTextContentLengthUTF16()
  96. ? child_index_or_text_offset % anchor->GetTextContentLengthUTF16()
  97. : 0;
  98. return ui::AXNodePosition::CreateTextPosition(
  99. tree_->GetAXTreeID(), anchor_id, child_index_or_text_offset,
  100. affinity);
  101. case ui::AXPositionKind::NULL_POSITION:
  102. NOTREACHED();
  103. return ui::AXNodePosition::CreateNullPosition();
  104. }
  105. }
  106. }
  107. ax::mojom::MoveDirection AXNodePositionFuzzerGenerator::GenerateMoveDirection(
  108. unsigned char byte) {
  109. constexpr unsigned char max_value =
  110. static_cast<unsigned char>(ax::mojom::MoveDirection::kMaxValue);
  111. return static_cast<ax::mojom::MoveDirection>(byte % max_value);
  112. }
  113. ax::mojom::TextAffinity AXNodePositionFuzzerGenerator::GenerateTextAffinity(
  114. unsigned char byte) {
  115. constexpr unsigned char max_value =
  116. static_cast<unsigned char>(ax::mojom::TextAffinity::kMaxValue);
  117. return static_cast<ax::mojom::TextAffinity>(byte % max_value);
  118. }
  119. ui::AXPositionKind AXNodePositionFuzzerGenerator::GeneratePositionKind(
  120. unsigned char byte) {
  121. return byte % 2 ? ui::AXPositionKind::TREE_POSITION
  122. : ui::AXPositionKind::TEXT_POSITION;
  123. }
  124. ui::AXPositionAdjustmentBehavior
  125. AXNodePositionFuzzerGenerator::GenerateAdjustmentBehavior(unsigned char byte) {
  126. return byte % 2 ? ui::AXPositionAdjustmentBehavior::kMoveBackward
  127. : ui::AXPositionAdjustmentBehavior::kMoveForward;
  128. }
  129. ui::AXMovementOptions AXNodePositionFuzzerGenerator::GenerateMovementOptions(
  130. unsigned char behavior_byte,
  131. unsigned char detection_byte) {
  132. return ui::AXMovementOptions(
  133. static_cast<ui::AXBoundaryBehavior>(behavior_byte % 3),
  134. static_cast<ui::AXBoundaryDetection>(detection_byte % 3));
  135. }
  136. TestPositionType AXNodePositionFuzzerGenerator::GenerateNextPosition(
  137. TestPositionType& current_position,
  138. TestPositionType& previous_position) {
  139. switch (fuzzer_data_.NextByte() % 55) {
  140. case 0:
  141. default:
  142. return CreateNewPosition();
  143. case 1:
  144. return current_position->AsValidPosition();
  145. case 2:
  146. return current_position->AsTreePosition();
  147. case 3:
  148. return current_position->AsLeafTreePosition();
  149. case 4:
  150. return current_position->AsTextPosition();
  151. case 5:
  152. return current_position->AsLeafTextPosition();
  153. case 6:
  154. return current_position->AsDomSelectionPosition();
  155. case 7:
  156. return current_position->AsUnignoredPosition(
  157. GenerateAdjustmentBehavior(fuzzer_data_.NextByte()));
  158. case 8:
  159. return current_position->CreateAncestorPosition(
  160. previous_position->GetAnchor(),
  161. GenerateMoveDirection(fuzzer_data_.NextByte()));
  162. case 9:
  163. return current_position->CreatePositionAtStartOfAnchor();
  164. case 10:
  165. return current_position->CreatePositionAtEndOfAnchor();
  166. case 11:
  167. return current_position->CreatePositionAtStartOfAXTree();
  168. case 12:
  169. return current_position->CreatePositionAtEndOfAXTree();
  170. case 13:
  171. return current_position->CreatePositionAtStartOfContent();
  172. case 14:
  173. return current_position->CreatePositionAtEndOfContent();
  174. case 15:
  175. return current_position->CreateChildPositionAt(fuzzer_data_.NextByte() %
  176. 10);
  177. case 16:
  178. return current_position->CreateParentPosition(
  179. GenerateMoveDirection(fuzzer_data_.NextByte()));
  180. case 17:
  181. return current_position->CreateNextLeafTreePosition();
  182. case 18:
  183. return current_position->CreatePreviousLeafTreePosition();
  184. case 19:
  185. return current_position->CreateNextLeafTextPosition();
  186. case 20:
  187. return current_position->CreatePreviousLeafTextPosition();
  188. case 21:
  189. return current_position->AsLeafTextPositionBeforeCharacter();
  190. case 22:
  191. return current_position->AsLeafTextPositionAfterCharacter();
  192. case 23:
  193. return current_position->CreatePreviousCharacterPosition(
  194. GenerateMovementOptions(fuzzer_data_.NextByte(),
  195. fuzzer_data_.NextByte()));
  196. case 24:
  197. return current_position->CreateNextWordStartPosition(
  198. GenerateMovementOptions(fuzzer_data_.NextByte(),
  199. fuzzer_data_.NextByte()));
  200. case 25:
  201. return current_position->CreatePreviousWordStartPosition(
  202. GenerateMovementOptions(fuzzer_data_.NextByte(),
  203. fuzzer_data_.NextByte()));
  204. case 26:
  205. return current_position->CreateNextWordEndPosition(
  206. GenerateMovementOptions(fuzzer_data_.NextByte(),
  207. fuzzer_data_.NextByte()));
  208. case 27:
  209. return current_position->CreatePreviousWordEndPosition(
  210. GenerateMovementOptions(fuzzer_data_.NextByte(),
  211. fuzzer_data_.NextByte()));
  212. case 28:
  213. return current_position->CreateNextLineStartPosition(
  214. GenerateMovementOptions(fuzzer_data_.NextByte(),
  215. fuzzer_data_.NextByte()));
  216. case 29:
  217. return current_position->CreatePreviousLineStartPosition(
  218. GenerateMovementOptions(fuzzer_data_.NextByte(),
  219. fuzzer_data_.NextByte()));
  220. case 30:
  221. return current_position->CreateNextLineEndPosition(
  222. GenerateMovementOptions(fuzzer_data_.NextByte(),
  223. fuzzer_data_.NextByte()));
  224. case 31:
  225. return current_position->CreatePreviousLineEndPosition(
  226. GenerateMovementOptions(fuzzer_data_.NextByte(),
  227. fuzzer_data_.NextByte()));
  228. case 32:
  229. return current_position->CreateNextFormatStartPosition(
  230. GenerateMovementOptions(fuzzer_data_.NextByte(),
  231. fuzzer_data_.NextByte()));
  232. case 33:
  233. return current_position->CreatePreviousFormatStartPosition(
  234. GenerateMovementOptions(fuzzer_data_.NextByte(),
  235. fuzzer_data_.NextByte()));
  236. case 34:
  237. return current_position->CreateNextFormatEndPosition(
  238. GenerateMovementOptions(fuzzer_data_.NextByte(),
  239. fuzzer_data_.NextByte()));
  240. case 35:
  241. return current_position->CreatePreviousFormatEndPosition(
  242. GenerateMovementOptions(fuzzer_data_.NextByte(),
  243. fuzzer_data_.NextByte()));
  244. case 36:
  245. return current_position->CreateNextSentenceStartPosition(
  246. GenerateMovementOptions(fuzzer_data_.NextByte(),
  247. fuzzer_data_.NextByte()));
  248. case 37:
  249. return current_position->CreatePreviousSentenceStartPosition(
  250. GenerateMovementOptions(fuzzer_data_.NextByte(),
  251. fuzzer_data_.NextByte()));
  252. case 38:
  253. return current_position->CreateNextSentenceEndPosition(
  254. GenerateMovementOptions(fuzzer_data_.NextByte(),
  255. fuzzer_data_.NextByte()));
  256. case 39:
  257. return current_position->CreatePreviousSentenceEndPosition(
  258. GenerateMovementOptions(fuzzer_data_.NextByte(),
  259. fuzzer_data_.NextByte()));
  260. case 40:
  261. return current_position->CreateNextParagraphStartPosition(
  262. GenerateMovementOptions(fuzzer_data_.NextByte(),
  263. fuzzer_data_.NextByte()));
  264. case 41:
  265. return current_position
  266. ->CreateNextParagraphStartPositionSkippingEmptyParagraphs(
  267. GenerateMovementOptions(fuzzer_data_.NextByte(),
  268. fuzzer_data_.NextByte()));
  269. case 42:
  270. return current_position->CreatePreviousParagraphStartPosition(
  271. GenerateMovementOptions(fuzzer_data_.NextByte(),
  272. fuzzer_data_.NextByte()));
  273. case 43:
  274. return current_position
  275. ->CreatePreviousParagraphStartPositionSkippingEmptyParagraphs(
  276. GenerateMovementOptions(fuzzer_data_.NextByte(),
  277. fuzzer_data_.NextByte()));
  278. case 44:
  279. return current_position->CreateNextParagraphEndPosition(
  280. GenerateMovementOptions(fuzzer_data_.NextByte(),
  281. fuzzer_data_.NextByte()));
  282. case 45:
  283. return current_position->CreatePreviousParagraphEndPosition(
  284. GenerateMovementOptions(fuzzer_data_.NextByte(),
  285. fuzzer_data_.NextByte()));
  286. case 46:
  287. return current_position->CreateNextPageStartPosition(
  288. GenerateMovementOptions(fuzzer_data_.NextByte(),
  289. fuzzer_data_.NextByte()));
  290. case 47:
  291. return current_position->CreatePreviousPageStartPosition(
  292. GenerateMovementOptions(fuzzer_data_.NextByte(),
  293. fuzzer_data_.NextByte()));
  294. case 48:
  295. return current_position->CreateNextPageEndPosition(
  296. GenerateMovementOptions(fuzzer_data_.NextByte(),
  297. fuzzer_data_.NextByte()));
  298. case 49:
  299. return current_position->CreatePreviousPageEndPosition(
  300. GenerateMovementOptions(fuzzer_data_.NextByte(),
  301. fuzzer_data_.NextByte()));
  302. case 52:
  303. return current_position->CreateNextAnchorPosition();
  304. case 53:
  305. return current_position->CreatePreviousAnchorPosition();
  306. case 54:
  307. return current_position->LowestCommonAncestorPosition(
  308. *previous_position, GenerateMoveDirection(fuzzer_data_.NextByte()));
  309. }
  310. }
  311. void AXNodePositionFuzzerGenerator::CallPositionAPIs(
  312. TestPositionType& position,
  313. TestPositionType& other_position) {
  314. // Call APIs on the created position. We don't care about any of the results,
  315. // we just want to make sure none of these crash or hang.
  316. std::ignore = position->GetAnchor();
  317. std::ignore = position->GetAnchorSiblingCount();
  318. std::ignore = position->IsIgnored();
  319. std::ignore = position->IsLeaf();
  320. std::ignore = position->IsValid();
  321. std::ignore = position->AtStartOfWord();
  322. std::ignore = position->AtEndOfWord();
  323. std::ignore = position->AtStartOfLine();
  324. std::ignore = position->AtEndOfLine();
  325. std::ignore = position->GetFormatStartBoundaryType();
  326. std::ignore = position->GetFormatEndBoundaryType();
  327. std::ignore = position->AtStartOfSentence();
  328. std::ignore = position->AtEndOfSentence();
  329. std::ignore = position->AtStartOfParagraph();
  330. std::ignore = position->AtEndOfParagraph();
  331. std::ignore = position->AtStartOfInlineBlock();
  332. std::ignore = position->AtStartOfPage();
  333. std::ignore = position->AtEndOfPage();
  334. std::ignore = position->AtStartOfAXTree();
  335. std::ignore = position->AtEndOfAXTree();
  336. std::ignore = position->AtStartOfContent();
  337. std::ignore = position->AtEndOfContent();
  338. std::ignore = position->LowestCommonAnchor(*other_position);
  339. std::ignore = position->CompareTo(*other_position);
  340. std::ignore = position->GetText();
  341. std::ignore = position->IsPointingToLineBreak();
  342. std::ignore = position->IsInTextObject();
  343. std::ignore = position->IsInWhiteSpace();
  344. std::ignore = position->MaxTextOffset();
  345. std::ignore = position->GetRole();
  346. }
  347. // Entry point for LibFuzzer.
  348. extern "C" int LLVMFuzzerTestOneInput(const unsigned char* data, size_t size) {
  349. if (size < kMinFuzzDataSize || size > kMaxFuzzDataSize)
  350. return 0;
  351. AXTreeFuzzerGenerator generator;
  352. FuzzerData fuzz_data(data, size);
  353. const size_t node_count =
  354. kMinNodeCount + fuzz_data.NextByte() % kMaxNodeCount;
  355. generator.GenerateInitialUpdate(fuzz_data, node_count);
  356. ui::AXNodeID max_id = generator.GetMaxAssignedID();
  357. ui::AXTree* tree = generator.GetTree();
  358. // Run with --v=1 to aid in debugging a specific crash.
  359. VLOG(1) << tree->ToString();
  360. // Check to ensure there is enough fuzz data to create two positions.
  361. if (fuzz_data.RemainingBytes() < kNextNodePositionMaxDataSize * 2)
  362. return 0;
  363. AXNodePositionFuzzerGenerator position_fuzzer(tree, max_id, fuzz_data);
  364. // Having two positions allows us to test "more interesting" APIs that do work
  365. // on multiple positions.
  366. TestPositionType previous_position = position_fuzzer.CreateNewPosition();
  367. TestPositionType position = position_fuzzer.CreateNewPosition();
  368. while (fuzz_data.RemainingBytes() > kNextNodePositionMaxDataSize) {
  369. // Run with --v=1 to aid in debugging a specific crash.
  370. VLOG(1) << position->ToString() << fuzz_data.RemainingBytes();
  371. position_fuzzer.CallPositionAPIs(position, previous_position);
  372. // Determine next position to test:
  373. TestPositionType next_position =
  374. position_fuzzer.GenerateNextPosition(position, previous_position);
  375. previous_position = std::move(position);
  376. position = std::move(next_position);
  377. }
  378. return 0;
  379. }