Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

[Nikita Danilov <Nikita@Namesys.COM>]

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.