Mailing-List: contact dev-help@tomcat.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Tomcat Developers List" <dev@tomcat.apache.org>
Received-SPF: neutral (nike.apache.org: local policy)
Message-ID: <4F11ABB1.7020308@christopherschultz.net>
Date: Sat, 14 Jan 2012 11:22:09 -0500
From: Christopher Schultz <chris@christopherschultz.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7;
 rv:9.0) Gecko/20111222 Thunderbird/9.0.1
MIME-Version: 1.0
To: Tomcat Developers List <dev@tomcat.apache.org>
Subject: Re: [SECURITY] Apache Tomcat and the hashtable collision DoS
 vulnerability
References: <4EFB9800.5010106@apache.org>
 <4EFC8AC4.5010407@christopherschultz.net> <4EFC8C1A.5010802@apache.org>
 <03E840D17E263A48A5766AD576E0423A03D9C15F7A@exch-mbx-111.vmware.com>
 <4EFCCCCB.5030904@christopherschultz.net>
In-Reply-To: <4EFCCCCB.5030904@christopherschultz.net>
Content-Type: multipart/signed; micalg=pgp-sha1;
 protocol="application/pgp-signature";
 boundary="------------enigFE4000EFB620E3586FE70538"

--------------enigFE4000EFB620E3586FE70538
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

All,

On 12/29/11 3:25 PM, Christopher Schultz wrote:
> On 12/29/11 12:35 PM, Luke Meyer wrote:
>> Worth noting that TreeMap makes all storage O(log n), so the normal
>> case takes a hit in order to mitigate the worst case (i.e. malicious
>> case).
>=20
> When n is small, though, O(n) ~=3D O(log n).
>=20
> I'd be interested to see the relative performance of each of these
> implementations. A straightforward test can be performed to test raw
> speed, but the memory-versus-protection issue is really a subjective on=
e.

I have some performance numbers along with the code below. It looks like
the performance trade-off for a TreeMap becomes viable around 10000
elements. Coincidentally, that's about the same time that the hashtable
collision becomes a vulnerability.

We could have HttpSession switch from using a HashMap to a TreeMap when
the size hits 10000 elements, and even make that an option on the <Contex=
t>.

Here are 3 runs, all single-threaded on this machine (though virtualized)=
:

model name    : Intel(R) Xeon(R) CPU           E5430  @ 2.66GHz
stepping	      : 10
cpu MHz       : 2666.758
cache size    : 6144 KB

> $ java -server -showversion HashCollissionTest
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
>=20
> Initializing strings...
> Done
> Running tests...
>                        Regular Strings           Colliding Strings
>          |     HashMap     TreeMap  Speedup     HashMap     TreeMap  Sp=
eedup
>       10 |     44989ns    315370ns     0.1x     63690ns     67143ns    =
 0.9x
>       10 |     16196ns     40469ns     0.4x     28379ns     37904ns    =
 0.7x
>      100 |     86546ns    460331ns     0.2x    790022ns    444854ns    =
 1.8x
>      100 |     87558ns    465158ns     0.2x    769854ns    422202ns    =
 1.8x
>     1000 |    442763ns  18439396ns     0.0x   3079022ns   5555242ns    =
 0.6x
>     1000 |    317509ns  15997482ns     0.0x  20380195ns  14069753ns    =
 1.4x
>    10000 |  13289497ns   3096187ns     4.3x 336093160ns   3080478ns   1=
09.1x
>    10000 |    700149ns  19021731ns     0.0x 348387091ns   3070681ns   1=
13.5x
>   100000 |  22356925ns  58920791ns     0.4x 40533164686ns  63963787ns  =
 633.7x
>   100000 |   9270803ns  49062417ns     0.2x 40312204850ns  51424106ns  =
 783.9x
>
>=20
> Initializing strings...
> Done
> Running tests...
>                        Regular Strings           Colliding Strings
>          |     HashMap     TreeMap  Speedup     HashMap     TreeMap  Sp=
eedup
>       10 |     46390ns    315255ns     0.1x     60600ns     67837ns    =
 0.9x
>       10 |     15968ns     40223ns     0.4x     25688ns     37451ns    =
 0.7x
>      100 |    105515ns    447747ns     0.2x    779985ns    452651ns    =
 1.7x
>      100 |     93377ns    450803ns     0.2x    791133ns    456755ns    =
 1.7x
>     1000 |    902098ns  14199242ns     0.1x   2515629ns   5648127ns    =
 0.4x
>     1000 |    388018ns   5921296ns     0.1x   2525295ns   6146751ns    =
 0.4x
>    10000 |  17576565ns   4645257ns     3.8x 302281637ns   3338971ns    =
90.5x
>    10000 |    695921ns   2903437ns     0.2x 294269766ns   3032316ns    =
97.0x
>   100000 |  17441705ns  39965677ns     0.4x 31082207714ns  61067533ns  =
 509.0x
>   100000 |  20723029ns  38217266ns     0.5x 31028693562ns  62811819ns  =
 494.0x
>
>
> Initializing strings...
> Done
> Running tests...
>                        Regular Strings           Colliding Strings
>          |     HashMap     TreeMap  Speedup     HashMap     TreeMap  Sp=
eedup
>       10 |     45661ns    322867ns     0.1x     74707ns     68256ns    =
 1.1x
>       10 |     14978ns     40684ns     0.4x     25526ns     39590ns    =
 0.6x
>      100 |    101775ns    465944ns     0.2x    804610ns    449270ns    =
 1.8x
>      100 |     89553ns    469063ns     0.2x    937187ns    438083ns    =
 2.1x
>     1000 |    492615ns   8732361ns     0.1x   2530423ns   5512348ns    =
 0.5x
>     1000 |    312919ns   5770171ns     0.1x   2585771ns   5942987ns    =
 0.4x
>    10000 |  10493163ns  15081198ns     0.7x 292524677ns   6026717ns    =
48.5x
>    10000 |    692544ns   2697905ns     0.3x 306244958ns   2736476ns   1=
11.9x
>   100000 |  10415660ns  55898980ns     0.2x 34549577192ns  56967692ns  =
 606.5x
>   100000 |  17369651ns  46201996ns     0.4x 34596484935ns  56857149ns  =
 608.5x

Here is the code for the above test:

import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;

public class HashCollissionTest
{
  public static void main(String[] args)
  {
    // Prime the JIT
    System.out.println("Running tests...");
    System.out.println("                       Regular Strings
 Colliding Strings");
    System.out.println(String.format("%8s | %11s %11s %8s %11s %11s
%8s", "", "HashMap", "TreeMap", "Speedup", "HashMap", "TreeMap",
"Speedup"));
    test(10);
    test(10);
    test(100);
    test(100);
    test(1000);
    test(1000);
    test(10000);
    test(10000);
    test(100000);
    test(100000);
  }

  static void test(int iterations)
  {
    HashMap<Object,Boolean> hashMap =3D new HashMap<Object,Boolean>();
    TreeMap<Object,Boolean> treeMap =3D new TreeMap<Object,Boolean>();

    long elapsed_hs =3D System.nanoTime();
    test(hashMap, iterations, strings);
    elapsed_hs =3D System.nanoTime() - elapsed_hs;
    hashMap.clear();
    hashMap =3D null;
    System.gc();

    long elapsed_ts =3D System.nanoTime();
    test(treeMap, iterations, strings);
    elapsed_ts =3D System.nanoTime() - elapsed_ts;

    treeMap.clear();
    treeMap =3D null;
    System.gc();

    hashMap =3D new HashMap<Object,Boolean>();
    long elapsed_hss =3D System.nanoTime();
    test(hashMap, iterations, stupidStrings);
    elapsed_hss =3D System.nanoTime() - elapsed_hss;

    hashMap.clear();
    hashMap =3D null;
    System.gc();

    treeMap =3D new TreeMap<Object,Boolean>();
    long elapsed_tss =3D System.nanoTime();
    test(treeMap, iterations, stupidStrings);
    elapsed_tss =3D System.nanoTime() - elapsed_tss;

    double p_s  =3D (double)elapsed_hs / (double)elapsed_ts;

    double p_ss =3D (double)elapsed_hss / (double)elapsed_tss;

    System.out.println(String.format("%8d | %9dns %9dns % 7.1fx %9dns
%9dns % 7.1fx", iterations, elapsed_hs, elapsed_ts, p_s, elapsed_hss,
elapsed_tss, p_ss));

    treeMap.clear();
    treeMap =3D null;
    System.gc();
  }

  static class StupidString
    implements Comparable
  {
    private String _s;

    public StupidString(String s)
    {
      _s =3D s;
    }

    public int hashCode() { return 0; }
    public String toString() { return _s; }
    public boolean equals(Object o) { return _s.equals(o); }
    public int compareTo(Object o) { return
_s.compareTo(((StupidString)o)._s); }
  }

  static void test(Map<Object,Boolean> map, int iterations, Object[] keys=
)
  {
      if(iterations > MAX_ITERATIONS)
        throw new IllegalArgumentException("Requested " + iterations + "
while " + MAX_ITERATIONS + " is the limit");

      for(int i=3D0; i<iterations; ++i)
        map.put(keys[i], Boolean.FALSE);
  }

    static final int MAX_ITERATIONS =3D 999999;
    static String[] strings;
    static StupidString[] stupidStrings;
    static
    {
      System.out.println("Initializing strings...");
      stupidStrings =3D new StupidString[MAX_ITERATIONS];
      strings =3D new String[MAX_ITERATIONS];

      for(int i=3D0; i < MAX_ITERATIONS; ++i)
        stupidStrings[i] =3D new StupidString(strings[i] =3D String.value=
Of(i));

      System.out.println("Done");
    }
}


-chris


--------------enigFE4000EFB620E3586FE70538
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk8Rq7MACgkQ9CaO5/Lv0PB4jwCgq25AVtgIf6tNAUptH3rrXWPQ
9UIAoLY7dxqUoP3HC4vjbhJ3oHbhJGQh
=wolY
-----END PGP SIGNATURE-----

--------------enigFE4000EFB620E3586FE70538--