As per the  Issue 700259  owner, assigning this issue to @mmoroz.
@mmoroz -- Could you please look into this issue, kindly reassign if it has nothing to do with your changes.
Thanks.

Hey Paul (junyer@), I would appreciate your opinion. The following input:

$ cat clusterfuzz-testcase-5513279958155264 | xxd
00000000: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000010: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000020: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000030: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000040: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000050: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000060: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000070: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000080: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000090: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000a0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000b0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000c0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000d0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000e0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000000f0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000100: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000110: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000120: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000130: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000140: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000150: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000160: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000170: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000180: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000190: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000001a0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000001b0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000001c0: ffff ffff ffff ffff ffff ff28 2e2a 7cff  ...........(.*|.
000001d0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000001e0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
000001f0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000200: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000210: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000220: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000230: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000240: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000250: ffff ffff ffff ffff ffff ffff ffff ff28  ...............(
00000260: 7c29 297b 3631 7d3a                      |)){61}:



Takes several seconds to be processed by the re2 fuzzer: https://cs.chromium.org/chromium/src/third_party/re2/src/re2/fuzzing/re2_fuzzer.cc?q=re2_fuzzer&sq=package:chromium&l=88

Often, it even takes longer than 25 seconds and timeout crash happens.

However, if I append "\n" to the end of the input, it works very fast. Do you have any idea why? Is it expected behavior or might be a bug?

It's noteworthy that the fuzzer uses hash(input) to randomize some options. I took hash value from the original timeout input (1484886225), and fixated it when I was testing original input + "\n".

Deleted: clusterfuzz-testcase-5513279958155264 616 bytes

clusterfuzz-testcase-5513279958155264 616 bytes View Download

On my workstation, at least, unanchored matching takes ~10s and there are four calls involving unanchored matching, so the total wall time is ~41s. Investigating further.

The majority of the time is spent in reverse DFA execution, which is slow in this case because the regular expression is such that its reverse DFA states are expensive to compute *and* to store. This leads to several cache flushes per match call given the portion of the default memory budget (8MiB) that the reverse DFA state cache gets.

Bumping up the memory budget to 64MiB is sufficient to avoid cache flushes entirely, which means that the initial match call is slow, but the subsequent match calls are very much faster: on my workstation, the total wall time drops to ~10s.

Fixed in commit 4be7a14. Please verify. :)

P.S. I expect that the thing about appending "\n" is that the fuzzer testcase is used for the pattern and also for the text. ":" matches itself, but "\n" does not because the automaton will be looking for '\n' instead. As such, I assume that forward DFA execution wouldn't find a match and so reverse DFA execution wouldn't even occur.

Looks good when testing locally! Thanks a lot for the thoughtful analysis and for the fix. I've uploaded a CL to update re2: junyer@chromium.org

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/19d4ff3a9ad5c20228bfb602c6b7b44086852afc

commit 19d4ff3a9ad5c20228bfb602c6b7b44086852afc
Author: Max Moroz <mmoroz@chromium.org>
Date: Fri Oct 13 20:18:05 2017

Roll re2 ae9cb49..4be7a14.

https://chromium.googlesource.com/external/github.com/google/re2.git/+log/ae9cb49..4be7a14

R=mbarbella@chromium.org, ochang@chromium.org

Bug:  773953 
Change-Id: Ifb6e2859e07aaf9719dbd9d9c783fe31d14d4da4
Reviewed-on: https://chromium-review.googlesource.com/719439
Reviewed-by: Martin Barbella <mbarbella@chromium.org>
Reviewed-by: Oliver Chang <ochang@chromium.org>
Commit-Queue: Max Moroz <mmoroz@chromium.org>
Cr-Commit-Position: refs/heads/master@{#508795}
[modify] https://crrev.com/19d4ff3a9ad5c20228bfb602c6b7b44086852afc/DEPS

For more information, please see https://chromium.googlesource.com/chromium/src/+/master/testing/libfuzzer/reference.md.

The link referenced in the description is no longer valid.