Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:89486
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.213.49 as permitted sender)
MIME-Version: 1.0
Sender: morrison.levi@gmail.com
In-Reply-To: <CAF+90c_pVFVbzqThuPg1V3VDTV-7Ci4O6T6hNtY5XPgVb2Mt-Q@mail.gmail.com>
References: <CAF+90c_pVFVbzqThuPg1V3VDTV-7Ci4O6T6hNtY5XPgVb2Mt-Q@mail.gmail.com>
Date: Sun, 29 Nov 2015 13:49:41 -0700
Message-ID: <CAFMT4NoyGZYV3tkGEXKBfk-uhzZ_G6sd38xcwF4YAxDaTrScOQ@mail.gmail.com>
To: Nikita Popov <nikita.ppv@gmail.com>
Cc: PHP internals <internals@lists.php.net>, Anatol Belski <anatol.php@belski.net>, 
	Remi Collet <remi@php.net>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [PHP-DEV] HashDos protection
From: levim@php.net (Levi Morrison)

> 1. (Self-balancing binary trees). The idea here is that a balanced binary
> tree has worst-case insertion time O(log N), while the linked list we
> normally use has worst-case insertion time O(N). This means that the
> worst-case execution time for N insertions into a hashtable goes from
> O(N^2) to O(N log N), i.e. from catastrophic to "a few times slower than
> usual".
>
> I don't think this solution is viable for PHP. Supporting binary trees ne=
xt
> to linked list collision resolution will make the hashtable implementatio=
n
> *a lot* more complicated -- and it isn't exactly simple as is.

I have written self-balancing binary trees on multiple occasions. I
know that we want to minimize complexity but if the complexity
actually helps solve this issue I think it would be worth it. I assume
you didn't create a proof of concept for this option =E2=80=93 is that
correct?

I think fataling because of collisions is a poor solution to this
problem because fataling in some cases may contribute to a successful
DOS attack (I do not think Aerys is the only piece of software that
would be vulnerable to this). I am sure PHP is not the only language
that has experienced pain with HashDos =E2=80=93 how have other languages
handled it?