Last year's Battlecode engine did JVM instrumentation to sandbox players on the same team from each other, and to limit the amount of computation they were allowed to do. We found two fun vulnerabilities related to the latter part.
The process by which the bytecode instruction limitation was done was by decompiling .class files, adding in instruction-counting instructions in relevant places, and them re-compiling them and running the modified executable. More concretely, say the program contained a method like:
public void f(int x) {
while (x != 0) {
System.out.println(x);
}
}then this was disassembled into (javap -c):
0: iload_1
1: ifeq 14
4: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream;
7: iload_1
8: invokevirtual #3 // Method java/io/PrintStream.println:(I)V
11: goto 0
14: return
and we add function calls of the form "decrease remaining bytecodes by K; if <= 0, end turn" at the end of every non-interruptible piece of code. (E.g., there is no point in adding a decrement+check between instructions 7 and 8, because instruction 7 cannot fail, and no goto enters between those instructions.)
Not every bytecode is counted the same -- e.g. certain function calls are treated as non-interruptible and with a hard-coded bytecode cost. Most interestingly, some bytecodes can even cost different things depending on inputs: prominently, arrays, which have a cost equal to the number of array elements (or in the case of multi-dimensional arrays, the product of the dimensions).
Now, the "decrease bytecodes" function looked roughly as follows:
class Counter {
int remaining = 10000; // or so
void decrease(int x) {
decreaseNoYield(x);
if (remaining <= 0) yield();
}
void decreaseNoYield(int x) {
if (x < 0) return; // if someone tries to do something iffy
remaining -= x;
}
}where the array code called decreaseNoYield to avoid interrupting code in the middle of a line (I think).
That overflow avoidance wasn't perfect! If you call Counter.decreaseNoYield with really large arguments (i.e., allocate huge arrays),
remaining would underflow and you'd get Integer.MAX_VALUE more bytecode instructions to finish your turn.
Actually exploiting this, however, was tricky. The obvious attempt looks like:
byte[] dummy = new byte[Integer.MAX_VALUE];
expensive instruction that underflows the counter;and it fails due to out-of-memory. Our second try looked like:
byte[] dummy = new byte[1 << 20]; dummy = null; // null out "dummy", hope the old version gets GC'd
dummy = new byte[1 << 20]; dummy = null;
dummy = new byte[1 << 20]; dummy = null;
// repeat 1 << 11 + eps timesand this failed for more mysterious reasons, by yielding... After some debugging, it turned out that the disassembly library had generated "labels" (not a JVM term, but rather one used by the library to model jump targets etc.) at every line, for accurate debug info (e.g. correct stack traces in the assembled code). The sandbox then treated those labels as possible interrupt points, and added counter checking...
Thus, our third and final try looked like:
byte[] dummy = new byte[1 << 20]; dummy = null; dummy = new byte[1 << 20]; dummy = null; dummy = new byte[1 << 20]; ...
// repeat 1 << 11 + eps times, *on a single line*and hilariously this works and gives us a unlimited amounts of bytecodes to use for the rest of our turn. It's still rather non-practical -- it requires us to allocate a total of 2^31 bytes of memory.
Remember how the cost of allocating multi-dimensional arrays was said to be the product of its dimensions? We could try to exploit this to get integer overflows/underflows, but it doesn't really help, given the out of memory issues. But it does have another problem: if some dimension is 0, the cost is set to zero. But this isn't accurate: if you do
byte[][] ar = new byte[1000][0];each of ar[0], ar[1], ... holds a separate zero-sized array. We could use this as a boolean array,
where a zero-sized array is treated as false, and null (or any other array) is treated as true, thus getting boolean array allocation for free.
How could we fix the latter issue? One way would be to change the cost computation from:
int cost = 1;
for (int dim = 0; dim < dims; dim++) {
cost *= size[dim];
}
to
int cost = 1;
for (int dim = 0; dim < dims; dim++) {
cost *= Math.max(size[dim], 1);
}
This would have been a pretty nice fix, because it's simple, and only adds two bytecode instructions to the loop code
(which was manually coded in bytecode). There's nothing really wrong with it ... except that it makes the first exploit
rather easier to use! With that fix, we could do byte[][] dummy = new byte[0][Integer.MAX_VALUE] to underflow the
bytecode counter in constant time.
Since the fix itself is legit, it would have had rather high plausible deniability, and the idea of introducing a backdoor (of sorts) with the fix for another, more minor, security vulnerability would probably have gotten it a pretty high rating were this an entry to an Underhanded Java challenge. :) It's not, though, so we didn't do this, but rather sent the devs a detailed write-up of the vulnerabilities found. They were nice enough to give us a bug bounty for it.
(As a parting thought, another way of avoiding the out-of-memory problem might be to get the JVM to optimize away the allocation, e.g. by doing it in a hot loop and not using the result. We didn't experiment with that, however.)