7 ms·

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java

by 0x0 8y ago

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java 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?)

sleepychu 8y ago
Crashing out of execution doesn't really seem like an actionable attack vector, unless that exception bubbles all the way to the application invocation.
- mcherm 8y ago
  Causing a crash is an excellent vector for a denial-of-service attack.
  - alexeiz 8y ago
    If you can make your service allocate 10G of memory, it's already a denial of service attack.
  - vbezhenar 8y ago
    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.
  - ryeguy 8y ago
    It's an exception, not a crash.
Insanity 8y ago
Chances are you'll get an OutOfMemoryException first :)
- mywtfmp3 8y ago
  The Java text file has a comment asking the user to allocate more memory for jvm.
  - Insanity 8y ago
    Yes but that hardly works when you try to exploit a system..
elygre 8y ago
This look like https://bugs.openjdk.java.net/browse/JDK-8203864 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/sorting.pdf 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" https://arxiv.org/pdf/1805.08612.pdf"
- andrewla 8y ago
  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.
iCannotEven 8y ago
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.
- toxik 8y ago
  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.
  - iCannotEven 8y ago
    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.
- sdinsn 8y ago
  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.
stickfigure 8y ago
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.

by 0x0 8y ago

sleepychu 8y ago

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

mcherm 8y ago
Causing a crash is an excellent vector for a denial-of-service attack.
- alexeiz 8y ago
  If you can make your service allocate 10G of memory, it's already a denial of service attack.
- vbezhenar 8y ago
  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.
- ryeguy 8y ago
  It's an exception, not a crash.

Insanity 8y ago

Chances are you'll get an OutOfMemoryException first :)

mywtfmp3 8y ago
The Java text file has a comment asking the user to allocate more memory for jvm.
- Insanity 8y ago
  Yes but that hardly works when you try to exploit a system..

elygre 8y ago

This look like https://bugs.openjdk.java.net/browse/JDK-8203864 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/sorting.pdf 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" https://arxiv.org/pdf/1805.08612.pdf"

andrewla 8y ago
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.

iCannotEven 8y ago

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.

toxik 8y ago
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.
- iCannotEven 8y ago
  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.
sdinsn 8y ago
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.

stickfigure 8y ago

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.