Messages in this thread | | | From | Nikita Danilov <> | Date | Fri, 30 May 2003 17:48:04 +0400 | Subject | Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code |
| |
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/
| |