Algorithmic complexity of matches
by Bobby Martin
Is there a way to configure Hyperscan to use only DFA state machines, or
otherwise restrict the time complexity of matches to be polynomial at worst?
We need to ensure the algorithmic complexity of our matches doesn't go
exponential in the size of the searched string, as NFA can for degenerate
cases
We understand that this is incompatible with some regular expression
features such as backreferences.
Thanks!
Bobby
2 years
Hyperscan release 5.1
by Chang, Harry
Hi all,
We have just released Hyperscan v5.1.0 on Github at https://github.com/intel/hyperscan/releases
We add DFA wide-state compression to reduce bytecode.
We refined the interpreter and optimized pure literal matching scenarios.
In addition, we fixed bugs in logical combinations and dependency issues.
[5.1.0] 2019-01-31
New Features:
- Improve DFA state compression by wide-state optimization to reduce bytecode
size.
- Improve interpreter runtime handling for pure literal patterns to boost the
performance of pure literal matching.
- Improve representation of interpreter to boost overall performance.
Known Issues and Limitations:
There are no known issues with this release.
Resolved Issues:
- Bugfix for logical combinations: fix error reporting combination's match in
case of sub-expression has EOD match under streaming mode.
- Bugfix for logical combinations: fix miss reporting combination's match under
vacuous input.
- Bugfix for issue #104: fix compile error with Boost 1.68.0.
- Bugfix for issue #127: avoid pcre error for hscollider with installed PCRE
package.
- Update version of PCRE used by testing tools as a syntax and semantic
reference to PCRE 8.41 or above.
- Fix github repo address in doc.
Thanks,
Harry
2 years
