91–100 of 180 posts
Earlier quoted context omitted.
Untrusted regexes to anything , where possible. There are fairly well-known ways to use those to run a DoS: https://en.wikipedia.org/wiki/ReDoS
I take it you don't use a web browser?
Earlier quoted context omitted.
Out of interest, what are some of these? I have a hard time believing that the implementors of the Perl regex engine chose to write it that way for no reason while the Thompson NFA figures are thrown about. I knew there must havevbeen something this 'implementation detail' was good for.
I believe backreferences require backtracking.
EDIT: you are correct, backreferences do require backtracking, my bad.
Earlier quoted context omitted.
If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.
Is there a quick and easy way to check if a particular regex could take exponential time?
But some regex engines accept non-regular expressions. [0] The usual notation for it is an escaped number: \1 or \2 or so on. They're used to refer back to capturing groups earlier in the expression, usually marked by parentheses.
Regular expressions don't have backreferences but various enhanced expressions add them. If you use those extensions, you are in danger of exponential execution time unless you are careful and know what you're doing. In particular you should know not to use regular expressions as your principal tool to build a parser.
Another counterexample to the idea that modern C++ written by experts is free of memory safety issues.
This library is old enough to drive...
Another counterexample to the idea that modern C++ written by experts is free of memory safety issues.
Why don't accept the fact someone decided to write $it, and move on with usefull comments? Enough hn this today.
Earlier quoted context omitted.
Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences . The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid ex…
From the RE2 wiki: "As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported." From your link: One common regular expression extension that does provide additional power is called backreferences. A backreference like \1 or \2 matches the string matched by a previous parenthesized expression, an…
There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset of patterns containing backreferences, such that /(cat|dog)\1/ for example decomposes into /catcat|dogdog/. The caveat is that this isn't fully generalizable for all patterns containing backreferences.
But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀
RE2 chooses not to support any PCRE-style backreferences, because RE2 is a pattern matching engine meant to support patterns that are actually regular, and backreferences are not regular.
Earlier quoted context omitted.
No, but not everything needs to be memory safe. That's what the kernel is there for. You can typically just restart the program. The classic program safety vs programmer time tradeoff.
If your program isn't memory safe, it's very often the case that someone can make your program run their program, at which point the kernel doesn't know that your program didn't intend to modify itself. W^X/NX bits and other technologies don't totally obviate the issue, as ROP gadgets can be used to defeat it. And so on, there's a whole domain of computer science dedicated to that arms race and no evidence that it's…
Earlier quoted context omitted.
You can look at a well known (but not very complete) benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long, the fastest c++ implementation (using re2) takes twice as long. I don't know of a fuzz comparison, but there has been fuzzing done on the rust library without finding anything bad, e.g. see this issue [1]. [0] http://benchmarksgame.alioth.debian.org/u64q/p…
> benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long With PHP at #2? Doesn't seem credible, or the thing being tested isn't meaningfully language-dependent.