Possible Timing Issues on Untrusted Patterns

[sno2]

Hello, I saw this crate on Twitter and decided to fuzz it with a primitive algorithm: simply generate a random pattern and match it to the original input. After running for quite a while, it came up with an input that took 4 seconds that was only 177 characters. Therefore, there is most likely some point where the code is getting stuck. Sadly, I do not have time to profile and investigate further at this time. However, this might want to be reviewed if users are to use this crate on untrusted patterns as this could most likely be exploited further if the cause was pinpointed. Anyways, here is the PoC:

use glob_match::glob_match;

fn main() {
  let start = std::time::Instant::now();
  let s = "{*{??*{??**,Uz*zz}w**{*{**a,z***b*[!}w??*azzzzzzzz*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!z[za,z&zz}w**z*z*}";
  assert!(!glob_match(s, s));
  println!(
    "{}",
    std::time::Instant::now()
      .duration_since(start)
      .as_secs_f32()
  );
}

Also notice that it only takes a long time when the pattern itself is matched with the pattern. I believe this is so because the pattern's * and named entries are being consumed by themselves in the matching process. Although, this still does not explain the slowdowns.

Thanks

Edit:

The following input string takes 800ms on my machine with 102 characters so it might help narrow down the issue:

"**** *{*{??*{??***\u{5} *{*{??*{??***\u{5},\0U\0}]*****\u{1},\0***\0,\0\0}w****,\0U\0}]*****\u{1},\0***\0,\0\0}w*****\u{1}***{}*.*\0\0*\0"

[devongovett]

Thanks! It's still sorta WIP, so I haven't had time to do any fuzzing myself just yet. Will take a look soon.

[devongovett]

Fixed some bugs in d19fb3d which seems to have improved performance on your example patterns by a lot.

If you find more, or want to share the program you used for fuzzing that would be helpful. Thanks again!

[sno2]

Thanks for the quick fixes. Would you like me to make a PR that adds a nested fuzz Cargo binary setup with two of my primitive fixtures using cargo fuzz or the scripts themselves?

Also, the fuzzer found a few other issues:

Pattern/Input (As Both)	Length	Time
}{*}{}{*}{*{*}{*} \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 ;};}	178	2.4s
}{*}{}{*}{*{*}{*} ;};}	146	1.64s

[devongovett]

Sure a cargo fuzz setup sounds good if you feel like it. Thanks!