Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2629343002:
Password reuse look-up optimization (Closed)
DescriptionPassword reuse look-up optimization.
In the current implementation of the password reuse detection:
1.Passwords are stored in map<password, set<domains>> passwords_
2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_).
This optimization:
1.Paswords stored are in the same structure but, keys are ordered(i.e. passwords) are ordered lexicographical as reversed strings.
2.So now it's needed to find a key in |passwords_| which is a suffix of |input|. If a key in |passwords_| that is suffix of |input| exists then the longest such key is the largest key in reverse lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key.
BUG=657041, 668155
Review-Url: https://codereview.chromium.org/2629343002
Cr-Commit-Position: refs/heads/master@{#443911}
Committed: https://chromium.googlesource.com/chromium/src/+/ceaa547b121efaac5504b656826247b7b93259de
Patch Set 1 #Patch Set 2 : Added tests #
Total comments: 12
Patch Set 3 : Rebase #Patch Set 4 : Addressed reviewer comments #Patch Set 5 : Comments updated #Patch Set 6 : Comments #Patch Set 7 : Small fix #
Total comments: 8
Patch Set 8 : Addressed comments and compilation fix #
Messages
Total messages: 22 (15 generated)
Description was changed from ========== Password reuse look-up optimization BUG=None ========== to ========== Password reuse look-up optimization. BUG=657041, 668155 ==========
Description was changed from ========== Password reuse look-up optimization. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the first implementation of password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ==========
Description was changed from ========== Password reuse look-up optimization. In the first implementation of password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ==========
Description was changed from ========== Password reuse look-up optimization. In the current implementation of password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ==========
Description was changed from ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.passwords are stored in map<pass, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.passwords are stored in map<password, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ==========
Description was changed from ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.passwords are stored in map<password, set<domains>> passwords_ 2.string |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.paswords stored in the same structure but, key are reversed as strings. 2.string |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.Passwords are stored in map<password, set<domains>> passwords_ 2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.Paswords stored are in the same structure but, keys (i.e. passwords) are reversed as strings. 2.String |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key in |passwords_| that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key. BUG=657041, 668155 ==========
dvadym@chromium.org changed reviewers: + vasilii@chromium.org
Hi Vasilii, could you please review this CL? Regards, Vadym
I agree with that sort of optimization. But I disagree with the practice of reversing strings everywhere. It will lead us to bugs. Instead std::map should be customized with a different comparator. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detection_manager.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detection_manager.cc:33: input_characters_ = text + input_characters_; |text| isn't guarantied to be just one char. insert() will be more effective. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:57: GetRegistryControlledDomain(GURL(domain)); kMinPasswordLengthToCheck isn't used here. But it can be also a performance improvement. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:97: return passwords_.end(); Looks like it's excessive. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:101: if (it != passwords_.end() && it->first == input) { I recommend equal_range() instead. Then you don't need to compare the strings but just compare the iterators (faster). https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector.h (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.h:59: const passwords_iterator FindSavedPassword(const base::string16& input); I don't see a reason for "const iterator" https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector_unittest.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector_unittest.cc:44: std::vector<std::unique_ptr<PasswordForm>> GetPasswordStoreResult( I'd prefer a more generic name as the functions has nothing to do with any password store.
Thanks Vasilii for comments! That's very good point that using reversed strings as arguments for detector could lead to subtle bugs. I've redone with a custom comparator of map keys, and this simplified this CL significantly. PTAL. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detection_manager.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detection_manager.cc:33: input_characters_ = text + input_characters_; On 2017/01/13 15:32:57, vasilii wrote: > |text| isn't guarantied to be just one char. > insert() will be more effective. I've removed reversing of strings, so now += operator is used again, as far as I understand no extra string copy is done with +=. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:57: GetRegistryControlledDomain(GURL(domain)); On 2017/01/13 15:32:57, vasilii wrote: > kMinPasswordLengthToCheck isn't used here. But it can be also a performance > improvement. Thanks, make sense. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:97: return passwords_.end(); On 2017/01/13 15:32:57, vasilii wrote: > Looks like it's excessive. Discussed offline, I like code better with this condition, because it's more explicit what happens when there are no passwords and it's not immediately clear that without this condition nothing happens. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.cc:101: if (it != passwords_.end() && it->first == input) { On 2017/01/13 15:32:57, vasilii wrote: > I recommend equal_range() instead. Then you don't need to compare the strings > but just compare the iterators (faster). Discussed offline, using equal_range and iterators comparions saves one string comparison, but anyway lower_bound requires log(|passwords_|) string comparison, so it's not so important, but on other hand current code is shorter and more clear. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector.h (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector.h:59: const passwords_iterator FindSavedPassword(const base::string16& input); On 2017/01/13 15:32:57, vasilii wrote: > I don't see a reason for "const iterator" thanks, I meants const_iterator, I've updated passwords_iterator to const_iterator and removed const here. https://codereview.chromium.org/2629343002/diff/20001/components/password_man... File components/password_manager/core/browser/password_reuse_detector_unittest.cc (right): https://codereview.chromium.org/2629343002/diff/20001/components/password_man... components/password_manager/core/browser/password_reuse_detector_unittest.cc:44: std::vector<std::unique_ptr<PasswordForm>> GetPasswordStoreResult( On 2017/01/13 15:32:57, vasilii wrote: > I'd prefer a more generic name as the functions has nothing to do with any > password store. GetPasswordStoreResult -> GetForms
lgtm https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... File components/password_manager/core/browser/password_reuse_detector.cc (right): https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.cc:21: // Returns true iff |prefix_candidate| is a prefix of |str|. Fix the comment https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.cc:113: bool ReverseStringLess::operator()(const base::string16& lhs, Move to the top to match the declaration order. https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... File components/password_manager/core/browser/password_reuse_detector.h (right): https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.h:24: std::map<base::string16, std::set<std::string>>::const_iterator; Can you move to "private" as it's used only there? https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.h:28: bool operator()(const base::string16& lhs, const base::string16& rhs); mark the operator as const.
The CQ bit was checked by dvadym@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Thanks Vasilii for review! https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... File components/password_manager/core/browser/password_reuse_detector.cc (right): https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.cc:21: // Returns true iff |prefix_candidate| is a prefix of |str|. On 2017/01/16 15:48:59, vasilii wrote: > Fix the comment Done. https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.cc:113: bool ReverseStringLess::operator()(const base::string16& lhs, On 2017/01/16 15:48:59, vasilii wrote: > Move to the top to match the declaration order. Done. https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... File components/password_manager/core/browser/password_reuse_detector.h (right): https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.h:24: std::map<base::string16, std::set<std::string>>::const_iterator; On 2017/01/16 15:48:59, vasilii wrote: > Can you move to "private" as it's used only there? Done. https://codereview.chromium.org/2629343002/diff/120001/components/password_ma... components/password_manager/core/browser/password_reuse_detector.h:28: bool operator()(const base::string16& lhs, const base::string16& rhs); On 2017/01/16 15:48:59, vasilii wrote: > mark the operator as const. Done.
Description was changed from ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.Passwords are stored in map<password, set<domains>> passwords_ 2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.Paswords stored are in the same structure but, keys (i.e. passwords) are reversed as strings. 2.String |input| is also reversed. 3.So now it's needed to find a key in |passwords_| which is a prefix of |input|. If a key in |passwords_| that is prefix of |input| exists then the longest such key is the largest key in usual lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.Passwords are stored in map<password, set<domains>> passwords_ 2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.Paswords stored are in the same structure but, keys are ordered(i.e. passwords) are ordered lexicographical as reversed strings. 2.So now it's needed to find a key in |passwords_| which is a suffix of |input|. If a key in |passwords_| that is suffix of |input| exists then the longest such key is the largest key in reverse lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key. BUG=657041, 668155 ==========
The CQ bit was unchecked by dvadym@chromium.org
The CQ bit was checked by dvadym@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from vasilii@chromium.org Link to the patchset: https://codereview.chromium.org/2629343002/#ps140001 (title: "Addressed comments and compilation fix")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 140001, "attempt_start_ts": 1484585977985820,
"parent_rev": "111729eca220e769c24b8570b879967b8eaedf81", "commit_rev":
"ceaa547b121efaac5504b656826247b7b93259de"}
Message was sent while issue was closed.
Description was changed from ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.Passwords are stored in map<password, set<domains>> passwords_ 2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.Paswords stored are in the same structure but, keys are ordered(i.e. passwords) are ordered lexicographical as reversed strings. 2.So now it's needed to find a key in |passwords_| which is a suffix of |input|. If a key in |passwords_| that is suffix of |input| exists then the longest such key is the largest key in reverse lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key. BUG=657041, 668155 ========== to ========== Password reuse look-up optimization. In the current implementation of the password reuse detection: 1.Passwords are stored in map<password, set<domains>> passwords_ 2.String |input| contains keystrokes from earliest till latest, and it needed to check any suffix of |input| for occurrence in |passwords_|.That requre m*n*log(n) operations, where m = len(input), n = len(passwords_). This optimization: 1.Paswords stored are in the same structure but, keys are ordered(i.e. passwords) are ordered lexicographical as reversed strings. 2.So now it's needed to find a key in |passwords_| which is a suffix of |input|. If a key in |passwords_| that is suffix of |input| exists then the longest such key is the largest key in reverse lexicographical order that not bigger that |input|. Usual map<> find method is used for finding such key. BUG=657041, 668155 Review-Url: https://codereview.chromium.org/2629343002 Cr-Commit-Position: refs/heads/master@{#443911} Committed: https://chromium.googlesource.com/chromium/src/+/ceaa547b121efaac5504b6568262... ==========
Message was sent while issue was closed.
Committed patchset #8 (id:140001) as https://chromium.googlesource.com/chromium/src/+/ceaa547b121efaac5504b6568262... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
