tomcat-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Christopher Schultz <ch...@christopherschultz.net>
Subject Re: [SECURITY] Apache Tomcat and the hashtable collision DoS vulnerability
Date Sat, 14 Jan 2012 16:22:09 GMT
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).
> 
> When n is small, though, O(n) ~= O(log n).
> 
> 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 one.

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 <Context>.

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)
> 
> Initializing strings...
> Done
> Running tests...
>                        Regular Strings           Colliding Strings
>          |     HashMap     TreeMap  Speedup     HashMap     TreeMap  Speedup
>       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   109.1x
>    10000 |    700149ns  19021731ns     0.0x 348387091ns   3070681ns   113.5x
>   100000 |  22356925ns  58920791ns     0.4x 40533164686ns  63963787ns   633.7x
>   100000 |   9270803ns  49062417ns     0.2x 40312204850ns  51424106ns   783.9x
>
> 
> Initializing strings...
> Done
> Running tests...
>                        Regular Strings           Colliding Strings
>          |     HashMap     TreeMap  Speedup     HashMap     TreeMap  Speedup
>       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  Speedup
>       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   111.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 = new HashMap<Object,Boolean>();
    TreeMap<Object,Boolean> treeMap = new TreeMap<Object,Boolean>();

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

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

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

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

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

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

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

    double p_ss = (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 = null;
    System.gc();
  }

  static class StupidString
    implements Comparable
  {
    private String _s;

    public StupidString(String s)
    {
      _s = 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=0; i<iterations; ++i)
        map.put(keys[i], Boolean.FALSE);
  }

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

      for(int i=0; i < MAX_ITERATIONS; ++i)
        stupidStrings[i] = new StupidString(strings[i] = String.valueOf(i));

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



-chris


Mime
View raw message