Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

Nikita Danilov
2003-05-30T13:34:52Z

Scott A Crosby writes:
> Hello. We have analyzed this software to determine its vulnerability
> to a new class of DoS attacks that related to a recent paper. ''Denial
> of Service via Algorithmic Complexity Attacks.''
>
> This paper discusses a new class of denial of service attacks that
> work by exploiting the difference between average case performance and
> worst-case performance. In an adversarial environment, the data
> structures used by an application may be forced to experience their
> worst case performance. For instance, hash tables are usually thought
> of as being constant time operations, but with large numbers of
> collisions will degrade to a linked list and may lead to a 100-10,000
> times performance degradation.

Another nice way to experience "worst case performance", is to create
deeply nested directory structure, like

0/1/2/3/4/.../99999/100000

try to unmount and see how shrink_dcache_parent/prune_dcache consume
100% of CPU without allowing preemption. Not recommended on a single
processor machine.

> Because of the widespread use of hash
> tables, the potential for attack is extremely widespread. Fortunately,
> in many cases, other limits on the system limit the impact of these
> attacks.
>

[...]

>
> Scott

Nikita.