This is the mail archive of the
mailing list for the glibc project.
Re: [PATCH v2] Improve performance of strstr
> in this case a large slowdown is not a real vulnerability.
Absolutely, performance varies quite dramatically with different inputs. That
is true for all algorithms even they are "real-time". Caches and branch
predictors are not going away.
> i think even doing memcmp at every byte position is not a
> denial of service concern if the needle is <= 256 bytes.
> (maybe we should use a lower limit? <= 64?)
It couldn't be since its worst case isn't actually much worse (~2.2 times for
needle size of 256). A simple memcmp at every character is significantly
faster than Two-way on the first bad needle, and about the same performance
on the second.
Also when reducing the size of the needle to 31 from 255 on my algorithm,
there is only a 73% speedup for its worst case (bad needle 2). So reducing the
cutoff doesn't really help the worst case since we're clearly not quadratic.