Fastest String Search Algorithm.

[Amit Choudhary]

On Fri, Jun 11, 2021 at 7:16 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com>
wrote:

> Hi Amit,
>
> For example an attacker finds an application that uses strstr and provides
> worst case inputs on purpose, causing the application to hang. That is a
> denial of service attack. GLIBC tries hard to avoid quadratic algorithms
> as a
> result.
>


This is a problem of the application that it is not limiting the input size.

Problems like these have happened in the past and that's why we have
strncpy(), etc.

If we don't have strncpy() then denial of service attack is possible
through strcpy() also.


This is not theoretical, slowdowns on rare inputs create serious issues.
> Math functions are a good example, there were cases where some math
> functions were 1000 or even 100000 times slower on some inputs.
> This caused such issues for HPC code that they used to advice not to use
> GLIBC for math code - a supercomputer taking weeks rather than hours to
> solve a problem because it hit slow cases is disastrous.
>


The worst case for a string matching function is different than for maths.

String matching is very simple - just compare characters.

But maths is different - calculating square roots, multiplying 20 floating
point numbers, calculating logarithmic values of large numbers,
factorization, etc. are very CPU intensive.

Regards,
Amit