matching_unittest.cc 34 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957
  1. // Copyright 2020 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 "third_party/zxcvbn-cpp/native-src/zxcvbn/matching.hpp"
  5. #include <algorithm>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <vector>
  9. #include "testing/gmock/include/gmock/gmock.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. #include "third_party/zxcvbn-cpp/native-src/zxcvbn/adjacency_graphs.hpp"
  12. #include "third_party/zxcvbn-cpp/native-src/zxcvbn/common.hpp"
  13. #include "third_party/zxcvbn-cpp/native-src/zxcvbn/frequency_lists.hpp"
  14. using ::testing::ElementsAre;
  15. using ::testing::IsEmpty;
  16. namespace zxcvbn {
  17. namespace {
  18. struct Variation {
  19. std::string password;
  20. idx_t i;
  21. idx_t j;
  22. };
  23. // takes a pattern and list of prefixes/suffixes
  24. // returns a bunch of variants of that pattern embedded
  25. // with each possible prefix/suffix combination, including no prefix/suffix
  26. // returns a list of triplets [variant, i, j] where [i,j] is the start/end of
  27. // the pattern, inclusive
  28. std::vector<Variation> gen_pws(const std::string& pattern,
  29. std::vector<std::string> prefixes,
  30. std::vector<std::string> suffixes) {
  31. if (std::find(prefixes.begin(), prefixes.end(), "") == prefixes.end())
  32. prefixes.insert(prefixes.begin(), "");
  33. if (std::find(suffixes.begin(), suffixes.end(), "") == suffixes.end())
  34. suffixes.insert(suffixes.begin(), "");
  35. std::vector<Variation> result;
  36. for (const auto& prefix : prefixes) {
  37. for (const auto& suffix : suffixes) {
  38. result.push_back({prefix + pattern + suffix, prefix.size(),
  39. prefix.size() + pattern.size() - 1});
  40. }
  41. }
  42. return result;
  43. }
  44. struct ExpectedDictionaryMatch {
  45. idx_t i;
  46. idx_t j;
  47. std::string token;
  48. std::string matched_word;
  49. rank_t rank;
  50. bool l33t;
  51. bool reversed;
  52. std::unordered_map<std::string, std::string> sub;
  53. };
  54. bool operator==(const Match& lhs, const ExpectedDictionaryMatch& rhs) {
  55. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  56. lhs.get_pattern() == MatchPattern::DICTIONARY &&
  57. lhs.get_dictionary().matched_word == rhs.matched_word &&
  58. lhs.get_dictionary().rank == rhs.rank &&
  59. lhs.get_dictionary().l33t == rhs.l33t &&
  60. lhs.get_dictionary().reversed == rhs.reversed &&
  61. lhs.get_dictionary().sub == rhs.sub;
  62. }
  63. struct ExpectedSpatialMatch {
  64. idx_t i;
  65. idx_t j;
  66. std::string token;
  67. GraphTag graph;
  68. unsigned turns;
  69. idx_t shifted_count;
  70. };
  71. bool operator==(const Match& lhs, const ExpectedSpatialMatch& rhs) {
  72. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  73. lhs.get_pattern() == MatchPattern::SPATIAL &&
  74. lhs.get_spatial().graph == rhs.graph &&
  75. lhs.get_spatial().turns == rhs.turns &&
  76. lhs.get_spatial().shifted_count == rhs.shifted_count;
  77. }
  78. struct ExpectedSequenceMatch {
  79. idx_t i;
  80. idx_t j;
  81. std::string token;
  82. SequenceTag sequence_tag;
  83. bool ascending;
  84. };
  85. bool operator==(const Match& lhs, const ExpectedSequenceMatch& rhs) {
  86. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  87. lhs.get_pattern() == MatchPattern::SEQUENCE &&
  88. lhs.get_sequence().sequence_tag == rhs.sequence_tag &&
  89. lhs.get_sequence().ascending == rhs.ascending;
  90. }
  91. struct ExpectedRepeatMatch {
  92. idx_t i;
  93. idx_t j;
  94. std::string token;
  95. std::string base_token;
  96. };
  97. bool operator==(const Match& lhs, const ExpectedRepeatMatch& rhs) {
  98. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  99. lhs.get_pattern() == MatchPattern::REPEAT &&
  100. lhs.get_repeat().base_token == rhs.base_token;
  101. }
  102. struct ExpectedRegexMatch {
  103. idx_t i;
  104. idx_t j;
  105. std::string token;
  106. RegexTag regex_tag;
  107. };
  108. bool operator==(const Match& lhs, const ExpectedRegexMatch& rhs) {
  109. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  110. lhs.get_pattern() == MatchPattern::REGEX &&
  111. lhs.get_regex().regex_tag == rhs.regex_tag;
  112. }
  113. struct ExpectedDateMatch {
  114. idx_t i;
  115. idx_t j;
  116. std::string token;
  117. std::string separator;
  118. unsigned year;
  119. unsigned month;
  120. unsigned day;
  121. };
  122. bool operator==(const Match& lhs, const ExpectedDateMatch& rhs) {
  123. return lhs.i == rhs.i && lhs.j == rhs.j && lhs.token == rhs.token &&
  124. lhs.get_pattern() == MatchPattern::DATE &&
  125. lhs.get_date().separator == rhs.separator &&
  126. lhs.get_date().year == rhs.year && lhs.get_date().month == rhs.month &&
  127. lhs.get_date().day == rhs.day;
  128. }
  129. } // namespace
  130. TEST(ZxcvbnTest, DictionaryMatching) {
  131. std::vector<std::vector<base::StringPiece>> test_dicts = {
  132. {"motherboard", "mother", "board", "abcd", "cdef"},
  133. {"z", "8", "99", "$", "asdf1234&*"},
  134. };
  135. {
  136. // matches words that contain other words
  137. std::string password = "motherboard";
  138. RankedDicts test_dicts_processed(test_dicts);
  139. std::vector<Match> matches =
  140. dictionary_match(password, test_dicts_processed);
  141. EXPECT_THAT(matches, ElementsAre(
  142. ExpectedDictionaryMatch{
  143. .i = 0,
  144. .j = 5,
  145. .token = "mother",
  146. .matched_word = "mother",
  147. .rank = 2,
  148. },
  149. ExpectedDictionaryMatch{
  150. .i = 0,
  151. .j = 10,
  152. .token = "motherboard",
  153. .matched_word = "motherboard",
  154. .rank = 1,
  155. },
  156. ExpectedDictionaryMatch{
  157. .i = 6,
  158. .j = 10,
  159. .token = "board",
  160. .matched_word = "board",
  161. .rank = 3,
  162. }));
  163. }
  164. {
  165. // matches multiple words when they overlap
  166. std::string password = "abcdef";
  167. std::vector<Match> matches =
  168. dictionary_match(password, RankedDicts(test_dicts));
  169. EXPECT_THAT(matches, ElementsAre(
  170. ExpectedDictionaryMatch{
  171. .i = 0,
  172. .j = 3,
  173. .token = "abcd",
  174. .matched_word = "abcd",
  175. .rank = 4,
  176. },
  177. ExpectedDictionaryMatch{
  178. .i = 2,
  179. .j = 5,
  180. .token = "cdef",
  181. .matched_word = "cdef",
  182. .rank = 5,
  183. }));
  184. }
  185. {
  186. // ignores uppercasing
  187. std::string password = "BoaRdZ";
  188. std::vector<Match> matches =
  189. dictionary_match(password, RankedDicts(test_dicts));
  190. EXPECT_THAT(matches, ElementsAre(
  191. ExpectedDictionaryMatch{
  192. .i = 0,
  193. .j = 4,
  194. .token = "BoaRd",
  195. .matched_word = "board",
  196. .rank = 3,
  197. },
  198. ExpectedDictionaryMatch{
  199. .i = 5,
  200. .j = 5,
  201. .token = "Z",
  202. .matched_word = "z",
  203. .rank = 1,
  204. }));
  205. }
  206. {
  207. // identifies words surrounded by non-words
  208. std::string word = "asdf1234&*";
  209. for (const auto& variation : gen_pws(word, {"q", "%%"}, {"%", "qq"})) {
  210. std::vector<Match> matches =
  211. dictionary_match(variation.password, RankedDicts(test_dicts));
  212. EXPECT_THAT(matches, ElementsAre(ExpectedDictionaryMatch{
  213. .i = variation.i,
  214. .j = variation.j,
  215. .token = word,
  216. .matched_word = word,
  217. .rank = 5,
  218. }));
  219. }
  220. }
  221. {
  222. // matches against all words in provided dictionaries
  223. for (const auto& test_dict : test_dicts) {
  224. rank_t expected_rank = 0;
  225. for (base::StringPiece ranked_word : test_dict) {
  226. expected_rank++;
  227. // skip words that contain others
  228. if (ranked_word == "motherboard")
  229. continue;
  230. std::vector<Match> matches =
  231. dictionary_match(std::string(ranked_word), RankedDicts(test_dicts));
  232. EXPECT_THAT(matches, ElementsAre(ExpectedDictionaryMatch{
  233. .i = 0,
  234. .j = ranked_word.size() - 1,
  235. .token = std::string(ranked_word),
  236. .matched_word = std::string(ranked_word),
  237. .rank = expected_rank,
  238. }));
  239. }
  240. }
  241. }
  242. {
  243. // default dictionaries
  244. SetRankedDicts(RankedDicts({{"wow"}}));
  245. std::vector<Match> matches =
  246. dictionary_match("wow", default_ranked_dicts());
  247. EXPECT_THAT(matches, ElementsAre(ExpectedDictionaryMatch{
  248. .i = 0,
  249. .j = 2,
  250. .token = "wow",
  251. .matched_word = "wow",
  252. .rank = 1,
  253. }));
  254. }
  255. }
  256. TEST(ZxcvbnTest, ReverseDictionaryMatching) {
  257. std::vector<std::vector<base::StringPiece>> test_dicts = {
  258. {"123", "321", "456", "654"},
  259. };
  260. // matches against reversed words
  261. std::string password = "0123456789";
  262. std::vector<Match> matches =
  263. reverse_dictionary_match(password, RankedDicts(test_dicts));
  264. EXPECT_THAT(matches, ElementsAre(
  265. ExpectedDictionaryMatch{
  266. .i = 1,
  267. .j = 3,
  268. .token = "123",
  269. .matched_word = "321",
  270. .rank = 2,
  271. .reversed = true,
  272. },
  273. ExpectedDictionaryMatch{
  274. .i = 4,
  275. .j = 6,
  276. .token = "456",
  277. .matched_word = "654",
  278. .rank = 4,
  279. .reversed = true,
  280. }));
  281. }
  282. TEST(ZxcvbnTest, L33tMatching) {
  283. std::vector<std::pair<std::string, std::vector<std::string>>> test_table = {
  284. {"a", {"4", "@"}},
  285. {"c", {"(", "{", "[", "<"}},
  286. {"g", {"6", "9"}},
  287. {"o", {"0"}},
  288. };
  289. {
  290. // reduces l33t table to only the substitutions that a password might be
  291. // employing
  292. struct {
  293. std::string pw;
  294. std::unordered_map<std::string, std::vector<std::string>> expected;
  295. } tests[] = {
  296. {"", {}},
  297. {"abcdefgo123578!#$&*)]}>", {}},
  298. {"a", {}},
  299. {"4", {{"a", {"4"}}}},
  300. {"4@", {{"a", {"4", "@"}}}},
  301. {"4({60",
  302. {{"a", {"4"}}, {"c", {"(", "{"}}, {"g", {"6"}}, {"o", {"0"}}}},
  303. };
  304. for (const auto& test : tests) {
  305. EXPECT_EQ(relevant_l33t_subtable(test.pw, test_table), test.expected);
  306. }
  307. }
  308. {
  309. // enumerates the different sets of l33t substitutions a password might be
  310. // using
  311. struct {
  312. std::unordered_map<std::string, std::vector<std::string>> table;
  313. std::vector<std::unordered_map<std::string, std::string>> subs;
  314. } tests[] = {
  315. {{}, {{}}},
  316. {{{"a", {"@"}}}, {{{"@", "a"}}}},
  317. {{{"a", {"@", "4"}}}, {{{"@", "a"}}, {{"4", "a"}}}},
  318. {{{"a", {"@", "4"}}, {"c", {"("}}},
  319. {{{"@", "a"}, {"(", "c"}}, {{"4", "a"}, {"(", "c"}}}},
  320. };
  321. for (const auto& test : tests) {
  322. EXPECT_EQ(enumerate_l33t_subs(test.table), test.subs);
  323. }
  324. }
  325. {
  326. std::vector<std::vector<base::StringPiece>> dicts = {
  327. {"aac", "password", "paassword", "asdf0"},
  328. {"cgo"},
  329. };
  330. auto lm = [&](const std::string& password) {
  331. return l33t_match(password, RankedDicts(dicts), test_table);
  332. };
  333. // doesn't match ""
  334. EXPECT_THAT(lm(""), IsEmpty());
  335. // doesn't match pure dictionary words
  336. EXPECT_THAT(lm("password"), IsEmpty());
  337. // matches against common l33t substitutions
  338. struct {
  339. std::string password;
  340. std::string pattern;
  341. std::string word;
  342. rank_t rank;
  343. idx_t i;
  344. idx_t j;
  345. std::unordered_map<std::string, std::string> sub;
  346. } tests[] = {
  347. {"p4ssword", "p4ssword", "password", 2, 0, 7, {{"4", "a"}}},
  348. {"p@ssw0rd", "p@ssw0rd", "password", 2, 0, 7, {{"@", "a"}, {"0", "o"}}},
  349. {"aSdfO{G0asDfO", "{G0", "cgo", 1, 5, 7, {{"{", "c"}, {"0", "o"}}},
  350. };
  351. for (const auto& test : tests) {
  352. EXPECT_THAT(lm(test.password), ElementsAre(ExpectedDictionaryMatch{
  353. .i = test.i,
  354. .j = test.j,
  355. .token = test.pattern,
  356. .matched_word = test.word,
  357. .rank = test.rank,
  358. .l33t = true,
  359. .sub = test.sub,
  360. }));
  361. }
  362. // matches against overlapping l33t patterns
  363. EXPECT_THAT(lm("@a(go{G0"), ElementsAre(
  364. ExpectedDictionaryMatch{
  365. .i = 0,
  366. .j = 2,
  367. .token = "@a(",
  368. .matched_word = "aac",
  369. .rank = 1,
  370. .l33t = true,
  371. .sub = {{"@", "a"}, {"(", "c"}},
  372. },
  373. ExpectedDictionaryMatch{
  374. .i = 2,
  375. .j = 4,
  376. .token = "(go",
  377. .matched_word = "cgo",
  378. .rank = 1,
  379. .l33t = true,
  380. .sub = {{"(", "c"}},
  381. },
  382. ExpectedDictionaryMatch{
  383. .i = 5,
  384. .j = 7,
  385. .token = "{G0",
  386. .matched_word = "cgo",
  387. .rank = 1,
  388. .l33t = true,
  389. .sub = {{"{", "c"}, {"0", "o"}},
  390. }));
  391. // doesn't match when multiple l33t substitutions are needed for the same
  392. // letter
  393. EXPECT_THAT(lm("p4@ssword"), IsEmpty());
  394. // doesn't match single-character l33ted words
  395. EXPECT_THAT(l33t_match("4 1 @", {}, {}), IsEmpty());
  396. // doesn't match with subsets of possible l33t substitutions
  397. EXPECT_THAT(lm("4sdf0"), IsEmpty());
  398. }
  399. }
  400. TEST(ZxcvbnTest, SpatialMatching) {
  401. // doesn't match 1- and 2-character spatial patterns
  402. for (const std::string& password : {"", "/", "qw", "*/"}) {
  403. EXPECT_THAT(spatial_match(password, {}), IsEmpty());
  404. }
  405. // for testing, make a subgraph that contains a single keyboard
  406. Graphs test_graphs = {{GraphTag::QWERTY, graphs().at(GraphTag::QWERTY)}};
  407. std::string pattern = "6tfGHJ";
  408. std::vector<Match> matches =
  409. spatial_match("rz!" + pattern + "%z", test_graphs);
  410. EXPECT_THAT(matches, ElementsAre(ExpectedSpatialMatch{
  411. .i = 3,
  412. .j = 3 + pattern.size() - 1,
  413. .token = pattern,
  414. .graph = GraphTag::QWERTY,
  415. .turns = 2,
  416. .shifted_count = 3,
  417. }));
  418. struct {
  419. std::string pattern;
  420. GraphTag keyboard;
  421. unsigned turns;
  422. idx_t shifts;
  423. } tests[] = {
  424. {"12345", GraphTag::QWERTY, 1, 0},
  425. {"@WSX", GraphTag::QWERTY, 1, 4},
  426. {"6tfGHJ", GraphTag::QWERTY, 2, 3},
  427. {"hGFd", GraphTag::QWERTY, 1, 2},
  428. {"/;p09876yhn", GraphTag::QWERTY, 3, 0},
  429. {"Xdr%", GraphTag::QWERTY, 1, 2},
  430. {"159-", GraphTag::KEYPAD, 1, 0},
  431. {"*84", GraphTag::KEYPAD, 1, 0},
  432. {"/8520", GraphTag::KEYPAD, 1, 0},
  433. {"369", GraphTag::KEYPAD, 1, 0},
  434. {"/963.", GraphTag::MAC_KEYPAD, 1, 0},
  435. {"*-632.0214", GraphTag::MAC_KEYPAD, 9, 0},
  436. {"aoEP%yIxkjq:", GraphTag::DVORAK, 4, 5},
  437. {";qoaOQ:Aoq;a", GraphTag::DVORAK, 11, 4},
  438. };
  439. for (const auto& test : tests) {
  440. Graphs test_graphs = {{test.keyboard, graphs().at(test.keyboard)}};
  441. std::vector<Match> matches = spatial_match(test.pattern, test_graphs);
  442. EXPECT_THAT(matches, ElementsAre(ExpectedSpatialMatch{
  443. .i = 0,
  444. .j = test.pattern.size() - 1,
  445. .token = test.pattern,
  446. .graph = test.keyboard,
  447. .turns = test.turns,
  448. .shifted_count = test.shifts,
  449. }));
  450. }
  451. }
  452. TEST(ZxcvbnTest, SequenceMatching) {
  453. // doesn't match 0- and 1-character sequences
  454. for (const std::string& password : {"", "a", "1"}) {
  455. EXPECT_THAT(sequence_match(password), IsEmpty());
  456. }
  457. {
  458. // matches overlapping patterns
  459. std::vector<Match> matches = sequence_match("abcbabc");
  460. EXPECT_THAT(matches, ElementsAre(
  461. ExpectedSequenceMatch{
  462. .i = 0,
  463. .j = 2,
  464. .token = "abc",
  465. .sequence_tag = SequenceTag::kLower,
  466. .ascending = true,
  467. },
  468. ExpectedSequenceMatch{
  469. .i = 2,
  470. .j = 4,
  471. .token = "cba",
  472. .sequence_tag = SequenceTag::kLower,
  473. .ascending = false,
  474. },
  475. ExpectedSequenceMatch{
  476. .i = 4,
  477. .j = 6,
  478. .token = "abc",
  479. .sequence_tag = SequenceTag::kLower,
  480. .ascending = true,
  481. }));
  482. }
  483. {
  484. // matches embedded sequence patterns
  485. std::string pattern = "jihg";
  486. for (const auto& variation : gen_pws(pattern, {"!", "22"}, {"!", "22"})) {
  487. std::vector<Match> matches = sequence_match(variation.password);
  488. EXPECT_THAT(matches, ElementsAre(ExpectedSequenceMatch{
  489. .i = variation.i,
  490. .j = variation.j,
  491. .token = pattern,
  492. .sequence_tag = SequenceTag::kLower,
  493. .ascending = false,
  494. }));
  495. }
  496. }
  497. {
  498. struct {
  499. std::string pattern;
  500. SequenceTag sequence_tag;
  501. bool ascending;
  502. } tests[] = {
  503. {"ABC", SequenceTag::kUpper, true},
  504. {"CBA", SequenceTag::kUpper, false},
  505. {"PQR", SequenceTag::kUpper, true},
  506. {"RQP", SequenceTag::kUpper, false},
  507. {"XYZ", SequenceTag::kUpper, true},
  508. {"ZYX", SequenceTag::kUpper, false},
  509. {"abcd", SequenceTag::kLower, true},
  510. {"dcba", SequenceTag::kLower, false},
  511. {"jihg", SequenceTag::kLower, false},
  512. {"wxyz", SequenceTag::kLower, true},
  513. {"zxvt", SequenceTag::kLower, false},
  514. {"0369", SequenceTag::kDigits, true},
  515. {"97531", SequenceTag::kDigits, false},
  516. };
  517. for (const auto& test : tests) {
  518. std::vector<Match> matches = sequence_match(test.pattern);
  519. EXPECT_THAT(matches, ElementsAre(ExpectedSequenceMatch{
  520. .i = 0,
  521. .j = test.pattern.size() - 1,
  522. .token = test.pattern,
  523. .sequence_tag = test.sequence_tag,
  524. .ascending = test.ascending,
  525. }));
  526. }
  527. }
  528. }
  529. TEST(ZxcvbnTest, RepeatMatching) {
  530. // doesn't match 0- and 1-character repeat patterns
  531. for (const std::string& password : {"", "#"}) {
  532. EXPECT_THAT(repeat_match(password), IsEmpty());
  533. }
  534. {
  535. // matches embedded repeat patterns
  536. std::string pattern = "&&&&";
  537. for (const auto& variation : gen_pws(pattern, {"@", "y4@"}, {"u", "u%7"})) {
  538. std::vector<Match> matches = repeat_match(variation.password);
  539. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  540. .i = variation.i,
  541. .j = variation.j,
  542. .token = pattern,
  543. .base_token = "&",
  544. }));
  545. }
  546. }
  547. {
  548. // matches repeats with base character
  549. for (size_t length : {3, 12}) {
  550. for (char chr : {'a', 'Z', '4', '&'}) {
  551. std::string pattern(length, chr);
  552. std::vector<Match> matches = repeat_match(pattern);
  553. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  554. .i = 0,
  555. .j = pattern.size() - 1,
  556. .token = pattern,
  557. .base_token = std::string(1, chr),
  558. }));
  559. }
  560. }
  561. }
  562. {
  563. // matches multiple adjacent repeats
  564. std::vector<Match> matches = repeat_match("BBB1111aaaaa@@@@@@");
  565. EXPECT_THAT(matches, ElementsAre(
  566. ExpectedRepeatMatch{
  567. .i = 0,
  568. .j = 2,
  569. .token = "BBB",
  570. .base_token = "B",
  571. },
  572. ExpectedRepeatMatch{
  573. .i = 3,
  574. .j = 6,
  575. .token = "1111",
  576. .base_token = "1",
  577. },
  578. ExpectedRepeatMatch{
  579. .i = 7,
  580. .j = 11,
  581. .token = "aaaaa",
  582. .base_token = "a",
  583. },
  584. ExpectedRepeatMatch{
  585. .i = 12,
  586. .j = 17,
  587. .token = "@@@@@@",
  588. .base_token = "@",
  589. }));
  590. }
  591. {
  592. // matches multiple repeats with non-repeats in-between
  593. std::vector<Match> matches =
  594. repeat_match("2818BBBbzsdf1111@*&@!aaaaaEUDA@@@@@@1729");
  595. EXPECT_THAT(matches, ElementsAre(
  596. ExpectedRepeatMatch{
  597. .i = 4,
  598. .j = 6,
  599. .token = "BBB",
  600. .base_token = "B",
  601. },
  602. ExpectedRepeatMatch{
  603. .i = 12,
  604. .j = 15,
  605. .token = "1111",
  606. .base_token = "1",
  607. },
  608. ExpectedRepeatMatch{
  609. .i = 21,
  610. .j = 25,
  611. .token = "aaaaa",
  612. .base_token = "a",
  613. },
  614. ExpectedRepeatMatch{
  615. .i = 30,
  616. .j = 35,
  617. .token = "@@@@@@",
  618. .base_token = "@",
  619. }));
  620. }
  621. {
  622. // matches multi-character repeat pattern
  623. std::string pattern = "abab";
  624. std::vector<Match> matches = repeat_match(pattern);
  625. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  626. .i = 0,
  627. .j = pattern.size() - 1,
  628. .token = pattern,
  629. .base_token = "ab",
  630. }));
  631. }
  632. {
  633. // matches aabaab as a repeat instead of the aa prefix
  634. std::string pattern = "aabaab";
  635. std::vector<Match> matches = repeat_match(pattern);
  636. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  637. .i = 0,
  638. .j = pattern.size() - 1,
  639. .token = pattern,
  640. .base_token = "aab",
  641. }));
  642. }
  643. {
  644. // identifies ab as repeat string, even though abab is also repeated
  645. std::string pattern = "abababab";
  646. std::vector<Match> matches = repeat_match(pattern);
  647. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  648. .i = 0,
  649. .j = pattern.size() - 1,
  650. .token = pattern,
  651. .base_token = "ab",
  652. }));
  653. }
  654. {
  655. // identifies äö as repeat string, even though äöäö is also repeated.
  656. // verifies that match.i and match.j operate in code point counts, and not
  657. // in bytes.
  658. std::string pattern = "\u00E4\u00F6\u00E4\u00F6\u00E4\u00F6\u00E4\u00F6";
  659. std::vector<Match> matches = repeat_match(pattern);
  660. EXPECT_THAT(matches, ElementsAre(ExpectedRepeatMatch{
  661. .i = 0,
  662. .j = 7,
  663. .token = pattern,
  664. .base_token = "\u00E4\u00F6",
  665. }));
  666. }
  667. }
  668. TEST(ZxcvbnTest, RegexMatching) {
  669. struct {
  670. std::string pattern;
  671. RegexTag regex_tag;
  672. } tests[] = {
  673. {"1922", RegexTag::RECENT_YEAR},
  674. {"2017", RegexTag::RECENT_YEAR},
  675. };
  676. for (const auto& test : tests) {
  677. std::vector<Match> matches = regex_match(test.pattern, REGEXEN());
  678. EXPECT_THAT(matches, ElementsAre(ExpectedRegexMatch{
  679. .i = 0,
  680. .j = test.pattern.size() - 1,
  681. .token = test.pattern,
  682. .regex_tag = test.regex_tag,
  683. }));
  684. }
  685. }
  686. TEST(ZxcvbnTest, DateMatching) {
  687. // matches dates that use `sep` as a separator
  688. for (const std::string& sep : {"", " ", "-", "/", "\\", "_", "."}) {
  689. std::string password = "13" + sep + "2" + sep + "1921";
  690. std::vector<Match> matches = date_match(password);
  691. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  692. .i = 0,
  693. .j = password.size() - 1,
  694. .token = password,
  695. .separator = sep,
  696. .year = 1921,
  697. .month = 2,
  698. .day = 13,
  699. }));
  700. }
  701. // matches dates with `order` format
  702. for (std::string order : {"mdy", "dmy", "ymd", "ydm"}) {
  703. order.replace(order.find('y'), 1, "88");
  704. order.replace(order.find('m'), 1, "8");
  705. order.replace(order.find('d'), 1, "8");
  706. std::vector<Match> matches = date_match(order);
  707. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  708. .i = 0,
  709. .j = order.size() - 1,
  710. .token = order,
  711. .separator = "",
  712. .year = 1988,
  713. .month = 8,
  714. .day = 8,
  715. }));
  716. }
  717. {
  718. // matches the date with year closest to REFERENCE_YEAR when ambiguous
  719. std::string password = "111504";
  720. std::vector<Match> matches = date_match(password);
  721. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  722. .i = 0,
  723. .j = password.size() - 1,
  724. .token = password,
  725. .separator = "",
  726. .year = 2004,
  727. .month = 11,
  728. .day = 15,
  729. }));
  730. }
  731. {
  732. struct {
  733. unsigned day;
  734. unsigned month;
  735. unsigned year;
  736. } tests[] = {
  737. {1, 1, 1999},
  738. {21, 8, 2000},
  739. {19, 12, 2005},
  740. {22, 11, 1551},
  741. };
  742. for (const auto& test : tests) {
  743. std::string password = std::to_string(test.year) +
  744. std::to_string(test.month) +
  745. std::to_string(test.day);
  746. std::vector<Match> matches = date_match(password);
  747. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  748. .i = 0,
  749. .j = password.size() - 1,
  750. .token = password,
  751. .separator = "",
  752. .year = test.year,
  753. .month = test.month,
  754. .day = test.day,
  755. }));
  756. }
  757. for (const auto& test : tests) {
  758. std::string password = std::to_string(test.year) + "." +
  759. std::to_string(test.month) + "." +
  760. std::to_string(test.day);
  761. std::vector<Match> matches = date_match(password);
  762. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  763. .i = 0,
  764. .j = password.size() - 1,
  765. .token = password,
  766. .separator = ".",
  767. .year = test.year,
  768. .month = test.month,
  769. .day = test.day,
  770. }));
  771. }
  772. }
  773. {
  774. // matches zero-padded dates
  775. std::string password = "02/02/02";
  776. std::vector<Match> matches = date_match(password);
  777. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  778. .i = 0,
  779. .j = password.size() - 1,
  780. .token = password,
  781. .separator = "/",
  782. .year = 2002,
  783. .month = 2,
  784. .day = 2,
  785. }));
  786. }
  787. {
  788. // matches embedded dates
  789. std::string pattern = "1/1/91";
  790. for (const auto& variation : gen_pws(pattern, {"a", "ab"}, {"!"})) {
  791. std::vector<Match> matches = date_match(variation.password);
  792. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  793. .i = variation.i,
  794. .j = variation.j,
  795. .token = pattern,
  796. .separator = "/",
  797. .year = 1991,
  798. .month = 1,
  799. .day = 1,
  800. }));
  801. }
  802. }
  803. {
  804. // matches overlapping dates
  805. std::string password = "12/20/1991.12.20";
  806. std::vector<Match> matches = date_match(password);
  807. EXPECT_THAT(matches, ElementsAre(
  808. ExpectedDateMatch{
  809. .i = 0,
  810. .j = 9,
  811. .token = "12/20/1991",
  812. .separator = "/",
  813. .year = 1991,
  814. .month = 12,
  815. .day = 20,
  816. },
  817. ExpectedDateMatch{
  818. .i = 6,
  819. .j = 15,
  820. .token = "1991.12.20",
  821. .separator = ".",
  822. .year = 1991,
  823. .month = 12,
  824. .day = 20,
  825. }));
  826. }
  827. {
  828. // matches dates padded by non-ambiguous digits
  829. std::string password = "912/20/919";
  830. std::vector<Match> matches = date_match(password);
  831. EXPECT_THAT(matches, ElementsAre(ExpectedDateMatch{
  832. .i = 1,
  833. .j = 8,
  834. .token = "12/20/91",
  835. .separator = "/",
  836. .year = 1991,
  837. .month = 12,
  838. .day = 20,
  839. }));
  840. }
  841. }
  842. TEST(ZxcvbnTest, Omnimatch) {
  843. EXPECT_THAT(omnimatch(""), IsEmpty());
  844. SetRankedDicts(RankedDicts({{"rosebud", "maelstrom"}}));
  845. std::string password = "r0sebudmaelstrom11/20/91aaaa";
  846. std::vector<Match> matches = omnimatch(password);
  847. struct {
  848. MatchPattern pattern;
  849. idx_t i;
  850. idx_t j;
  851. } tests[] = {
  852. {MatchPattern::DICTIONARY, 0, 6},
  853. {MatchPattern::DICTIONARY, 7, 15},
  854. {MatchPattern::DATE, 16, 23},
  855. {MatchPattern::REPEAT, 24, 27},
  856. };
  857. for (const auto& test : tests) {
  858. bool included =
  859. std::any_of(matches.begin(), matches.end(), [&test](const auto& match) {
  860. return std::make_tuple(match.get_pattern(), match.i, match.j) ==
  861. std::make_tuple(test.pattern, test.i, test.j);
  862. });
  863. EXPECT_TRUE(included);
  864. }
  865. }
  866. } // namespace zxcvbn