| 1 |
// This set of tests is different from regression_fuzz in that the tests start |
| 2 |
// from the fuzzer data directly. The test essentially duplicates the fuzz |
| 3 |
// target. I wonder if there's a better way to set this up... Hmmm. I bet |
| 4 |
// `cargo fuzz` has something where it can run a target against crash files and |
| 5 |
// verify that they pass. |
| 6 |
|
| 7 |
// This case found by the fuzzer causes the meta engine to use the "reverse |
| 8 |
// inner" literal strategy. That in turn uses a specialized search routine |
| 9 |
// for the lazy DFA in order to avoid worst case quadratic behavior. That |
| 10 |
// specialized search routine had a bug where it assumed that start state |
| 11 |
// specialization was disabled. But this is indeed not the case, since it |
| 12 |
// reuses the "general" lazy DFA for the full regex created as part of the core |
| 13 |
// strategy, which might very well have start states specialized due to the |
| 14 |
// existence of a prefilter. |
| 15 |
// |
| 16 |
// This is a somewhat weird case because if the core engine has a prefilter, |
| 17 |
// then it's usually the case that the "reverse inner" optimization won't be |
| 18 |
// pursued in that case. But there are some heuristics that try to detect |
| 19 |
// whether a prefilter is "fast" or not. If it's not, then the meta engine will |
| 20 |
// attempt the reverse inner optimization. And indeed, that's what happens |
| 21 |
// here. So the reverse inner optimization ends up with a lazy DFA that has |
| 22 |
// start states specialized. Ideally this wouldn't happen because specializing |
| 23 |
// start states without a prefilter inside the DFA can be disastrous for |
| 24 |
// performance by causing the DFA to ping-pong in and out of the special state |
| 25 |
// handling. In this case, it's probably not a huge deal because the lazy |
| 26 |
// DFA is only used for part of the matching where as the work horse is the |
| 27 |
// prefilter found by the reverse inner optimization. |
| 28 |
// |
| 29 |
// We could maybe fix this by refactoring the meta engine to be a little more |
| 30 |
// careful. For example, by attempting the optimizations before building the |
| 31 |
// core engine. But this is perhaps a little tricky. |
| 32 |
#[test] |
| 33 |
fn meta_stopat_specialize_start_states() { |
| 34 |
let data = include_bytes!( |
| 35 |
"testdata/crash-8760b19b25d74e3603d4c643e9c7404fdd3631f9", |
| 36 |
); |
| 37 |
let _ = run(data); |
| 38 |
} |
| 39 |
|
| 40 |
// Same bug as meta_stopat_specialize_start_states, but minimized by the |
| 41 |
// fuzzer. |
| 42 |
#[test] |
| 43 |
fn meta_stopat_specialize_start_states_min() { |
| 44 |
let data = include_bytes!( |
| 45 |
"testdata/minimized-from-8760b19b25d74e3603d4c643e9c7404fdd3631f9", |
| 46 |
); |
| 47 |
let _ = run(data); |
| 48 |
} |
| 49 |
|
| 50 |
// This input generated a pattern with a fail state (e.g., \P{any}, [^\s\S] |
| 51 |
// or [a&&b]). But the fail state was in a branch, where a subsequent branch |
| 52 |
// should have led to an overall match, but handling of the fail state |
| 53 |
// prevented it from doing so. A hand-minimized version of this is '[^\s\S]A|B' |
| 54 |
// on the haystack 'B'. That should yield a match of 'B'. |
| 55 |
// |
| 56 |
// The underlying cause was an issue in how DFA determinization handled fail |
| 57 |
// states. The bug didn't impact the PikeVM or the bounded backtracker. |
| 58 |
#[test] |
| 59 |
fn fail_branch_prevents_match() { |
| 60 |
let data = include_bytes!( |
| 61 |
"testdata/crash-cd33b13df59ea9d74503986f9d32a270dd43cc04", |
| 62 |
); |
| 63 |
let _ = run(data); |
| 64 |
} |
| 65 |
|
| 66 |
// This input generated a pattern that contained a sub-expression like this: |
| 67 |
// |
| 68 |
// a{0}{50000} |
| 69 |
// |
| 70 |
// This turned out to provoke quadratic behavior in the NFA compiler. |
| 71 |
// Basically, the NFA compiler works in two phases. The first phase builds |
| 72 |
// a more complicated-but-simpler-to-construct sequence of NFA states that |
| 73 |
// includes unconditional epsilon transitions. As part of converting this |
| 74 |
// sequence to the "final" NFA, we remove those unconditional espilon |
| 75 |
// transition. The code responsible for doing this follows every chain of |
| 76 |
// these transitions and remaps the state IDs. The way we were doing this |
| 77 |
// before resulted in re-following every subsequent part of the chain for each |
| 78 |
// state in the chain, which ended up being quadratic behavior. We effectively |
| 79 |
// memoized this, which fixed the performance bug. |
| 80 |
#[test] |
| 81 |
fn slow_big_empty_chain() { |
| 82 |
let data = include_bytes!( |
| 83 |
"testdata/slow-unit-9ca9cc9929fee1fcbb847a78384effb8b98ea18a", |
| 84 |
); |
| 85 |
let _ = run(data); |
| 86 |
} |
| 87 |
|
| 88 |
// A different case of slow_big_empty_chain. |
| 89 |
#[test] |
| 90 |
fn slow_big_empty_chain2() { |
| 91 |
let data = include_bytes!( |
| 92 |
"testdata/slow-unit-3ab758ea520027fefd3f00e1384d9aeef155739e", |
| 93 |
); |
| 94 |
let _ = run(data); |
| 95 |
} |
| 96 |
|
| 97 |
// A different case of slow_big_empty_chain. |
| 98 |
#[test] |
| 99 |
fn slow_big_empty_chain3() { |
| 100 |
let data = include_bytes!( |
| 101 |
"testdata/slow-unit-b8a052f4254802edbe5f569b6ce6e9b6c927e9d6", |
| 102 |
); |
| 103 |
let _ = run(data); |
| 104 |
} |
| 105 |
|
| 106 |
// A different case of slow_big_empty_chain. |
| 107 |
#[test] |
| 108 |
fn slow_big_empty_chain4() { |
| 109 |
let data = include_bytes!( |
| 110 |
"testdata/slow-unit-93c73a43581f205f9aaffd9c17e52b34b17becd0", |
| 111 |
); |
| 112 |
let _ = run(data); |
| 113 |
} |
| 114 |
|
| 115 |
// A different case of slow_big_empty_chain. |
| 116 |
#[test] |
| 117 |
fn slow_big_empty_chain5() { |
| 118 |
let data = include_bytes!( |
| 119 |
"testdata/slow-unit-5345fccadf3812c53c3ccc7af5aa2741b7b2106c", |
| 120 |
); |
| 121 |
let _ = run(data); |
| 122 |
} |
| 123 |
|
| 124 |
// A different case of slow_big_empty_chain. |
| 125 |
#[test] |
| 126 |
fn slow_big_empty_chain6() { |
| 127 |
let data = include_bytes!( |
| 128 |
"testdata/slow-unit-6bd643eec330166e4ada91da2d3f284268481085", |
| 129 |
); |
| 130 |
let _ = run(data); |
| 131 |
} |
| 132 |
|
| 133 |
// This fuzz input generated a pattern with a large repetition that would fail |
| 134 |
// NFA compilation, but its HIR was small. (HIR doesn't expand repetitions.) |
| 135 |
// But, the bounds were high enough that the minimum length calculation |
| 136 |
// overflowed. We fixed this by using saturating arithmetic (and also checked |
| 137 |
// arithmetic for the maximum length calculation). |
| 138 |
// |
| 139 |
// Incidentally, this was the only unguarded arithmetic operation performed in |
| 140 |
// the HIR smart constructors. And the fuzzer found it. Hah. Nice. |
| 141 |
#[test] |
| 142 |
fn minimum_len_overflow() { |
| 143 |
let data = include_bytes!( |
| 144 |
"testdata/crash-7eb3351f0965e5d6c1cb98aa8585949ef96531ff", |
| 145 |
); |
| 146 |
let _ = run(data); |
| 147 |
} |
| 148 |
|
| 149 |
// This is the fuzz target function. We duplicate it here since this is the |
| 150 |
// thing we use to interpret the data. It is ultimately what we want to |
| 151 |
// succeed. |
| 152 |
fn run(data: &[u8]) -> Option<()> { |
| 153 |
if data.len() < 2 { |
| 154 |
return None; |
| 155 |
} |
| 156 |
let mut split_at = usize::from(data[0]); |
| 157 |
let data = std::str::from_utf8(&data[1..]).ok()?; |
| 158 |
// Split data into a regex and haystack to search. |
| 159 |
let len = usize::try_from(data.chars().count()).ok()?; |
| 160 |
split_at = std::cmp::max(split_at, 1) % len; |
| 161 |
let char_index = data.char_indices().nth(split_at)?.0; |
| 162 |
let (pattern, input) = data.split_at(char_index); |
| 163 |
let re = regex::Regex::new(pattern).ok()?; |
| 164 |
re.is_match(input); |
| 165 |
Some(()) |
| 166 |
} |