Hacker News Reader

Comment by 0x0 | Hacker News Reader

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)

View on HN

This look like https://bugs.openjdk.java.net/browse/JDK-8203864, which has the following additional information:

"While working on a proper complexity analysis of the algorithm, we realised that there was an error in the last paper reporting such a bug (http://envisage-project.eu/wp-content/uploads/2015/02/sortin...). This implies that the correction implemented in the Java source code (changing Timsort stack size) is wrong and that it is still possible to make it break. This is explained in full details in our analysis: https://arxiv.org/pdf/1805.08612.pdf"

That is not additional information. That bug was created by the authors of this post, and the link is a reference to the exact paper linked to in this post.

Crashing out of execution doesn't really seem like an actionable attack vector, unless that exception bubbles all the way to the application invocation.

Causing a crash is an excellent vector for a denial-of-service attack.

If you can make your service allocate 10G of memory, it's already a denial of service attack.

Usually unexpected exception results in a HTTP 500 response (or something similar) and few lines in the log. It does not result in stopped server.

It's an exception, not a crash.

Java http servers don't work this way. An exception bubbles up until something catches it; it only crashes the process if there is no handler. Every java http server wraps the request processing loop and catches exceptions so that it can provide a 500 Internal Server Error response.

There are likely a million ways malformed input can make a java server throw an exception; that's typically how java handles malformed input. It just gets caught and returned as an error to the client.

Chances are you'll get an OutOfMemoryException first :)

The Java text file has a comment asking the user to allocate more memory for jvm.

Yes but that hardly works when you try to exploit a system..

  arrayToSort[sum] = 1;

This is just blatant programmer error. The code is attempting to assign a value to a slot in an array of a fixed size, which does not exist.

Use:

  Integer[] arrayToSort = new Integer[2000000000];

No error.

You are incorrect. Look at the error message more closely:

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49
        at java.util.ComparableTimSort.pushRun(Unknown Source)
        at java.util.ComparableTimSort.sort(Unknown Source)
        at java.util.Arrays.sort(Unknown Source)
        at Test.main(Test.java:80)

The error occurs inside TimSort, not at

    arrayToSort[sum] = 1;

It's a bug with TimSort going out of bounds (which obviously shouldn't happen ever), not the Test.

The equivalent Python code works fine, though.

    >>> a=[0]*sum(rls)
    >>> sum=-1
    >>> for i in rls:
    ...   sum += i
    ...   a[sum] = 1
    ... 
    >>> a.sort()
    >>>

Takes a real good while, too.

That's because the array to be sorted is packed and inflated, so as to be the worst possible input for that kind of sort.

Worst-case complexity.

Also, I needed to bump my JVM heap up to 16GB (not 9GB as recommended), just to run it.

Reply on news.ycombinator.com