Found by inspection.

On some inputs, DoReplaceSubstringsAfterOffset (which powers
base::ReplaceSubstringsAfterOffset) never terminates, and writes past 
the bounds of its buffer. For example:

  ReplaceSubstringsAfterOffset(std::string('aaabaa'), 0, 'aa', 'ccc');

The root cause of this is an algorithmic bug, where it was assumed that
string::rfind and string::find would return the same matches in reversed order.
The fix should be to not call rfind(), and instead only scan forward using
find().

EXPLOITABILITY

On triggering the bug, the code appears never to terminate, and will keep searching/
memmoving for string matches until it hits an invalid memory region. This might
make it hard to use in an exploit.

Three conditions are necessary to trigger the overrun in practice, and most
non-test calls to ReplaceSubstringAfterOffset seem to not satisfy (1) or (2):
  1. |find_this| must be a string that overlaps with itself (it has a prefix
     that is also a suffix). E.g. 'aa'.
  2. |replace_with| must be longer than |find_this|.
  3. |str| must have overlapping occurances of |find_this| that are not
     adjacent to the last match, in string.

I see only one case where there might be potential for abusing this: https://cs.chromium.org/chromium/src/chrome/browser/extensions/api/settings_overrides/settings_overrides_api.cc?type=cs&sq=package:chromium&l=44

Possible fix: https://codereview.chromium.org/2979393002
 

Found by inspection.

On some inputs, DoReplaceSubstringsAfterOffset (which powers
base::ReplaceSubstringsAfterOffset) never terminates, and writes past 
the bounds of its buffer. For example:

  ReplaceSubstringsAfterOffset(std::string("aaabaa"), 0, "aa", "ccc");

The root cause of this is an algorithmic bug, where it was assumed that
string::rfind and string::find would return the same matches in reversed order.
The fix should be to not call rfind(), and instead only scan forward using
find().

EXPLOITABILITY

On triggering the bug, the code appears never to terminate, and will keep searching/
memmoving for string matches until it hits an invalid memory region. This might
make it hard to use in an exploit.

Three conditions are necessary to trigger the overrun in practice, and most
non-test calls to ReplaceSubstringAfterOffset seem to not satisfy (1) or (2):
  1. |find_this| must be a string that overlaps with itself (it has a prefix
     that is also a suffix). E.g. 'aa'.
  2. |replace_with| must be longer than |find_this|.
  3. |str| must have overlapping occurances of |find_this| that are not
     adjacent to the last match, in string.

I see only one case where there might be potential for abusing this: https://cs.chromium.org/chromium/src/chrome/browser/extensions/api/settings_overrides/settings_overrides_api.cc?type=cs&sq=package:chromium&l=44

Possible fix: https://codereview.chromium.org/2979393002
 

Found by inspection.

On some inputs, DoReplaceSubstringsAfterOffset (which powers
base::ReplaceSubstringsAfterOffset) never terminates, and writes past 
the bounds of its buffer. For example:

  ReplaceSubstringsAfterOffset(std::string("aaabaa"), 0, "aa", "ccc");

The root cause of this is an algorithmic bug, where it was assumed that
string::rfind and string::find would return the same matches in reversed order.
The fix should be to not call rfind(), and instead only scan forward using
find().

EXPLOITABILITY

On triggering the bug, the code appears never to terminate, and will keep searching/
memmoving for string matches until it hits an invalid memory region. This might
make it hard to use in an exploit.

Three conditions are necessary to trigger the overrun in practice, and most
non-test calls to ReplaceSubstringAfterOffset seem to not satisfy (1) or (2):
  1. |find_this| must be a string that overlaps with itself (it has a prefix
     that is also a suffix). E.g. 'aa'.
  2. |replace_with| must be longer than |find_this|.
  3. |str| must have overlapping occurences of |find_this| that are not
     adjacent to the last match, in string.

I see only one case where there might be potential for abusing this: https://cs.chromium.org/chromium/src/chrome/browser/extensions/api/settings_overrides/settings_overrides_api.cc?type=cs&sq=package:chromium&l=44

Possible fix: https://codereview.chromium.org/2979393002