Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

Nikita Danilov (Nikita@Namesys.COM)
Fri, 30 May 2003 17:48:04 +0400


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.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/