Cheating in the ball game was hard. Only three great Java minds managed to crack it: mihi, polygenelubricants and crazybob.
As a reminder, here’s the puzzle:
package game;
public final class Game {
private final Ball ball = new Ball();
private volatile long score;
public final class Ball extends Throwable {
private volatile long caught;
private Ball() {
}
public synchronized void caught() {
if (caught++ < score++) {
// The goal is to reach this line
System.out.println("You cheated!");
}
}
}
public void play() throws Ball {
throw ball;
}
}
The approach
If you couldn’t throw a ball, it wouldn’t be any fun. But extending Throwable also makes it implements Serializable, and that’s where the real fun starts. Using serialization, we can create a ball that supposedly has been caught as many times as our serialized data claims.
The Game looks like it spoils the fun. You can’t throw it; but more importantly you can’t serialize it. If you try to naively serialize a ball directly, it will also try to serialize the game it is attached to, leading to a NotSerializableException.
Note that technically the reference from the ball to its game is just a field called something like this$0. With “attach” I mean assigning to that field. So this problem is equivalent to serializing an object that has a normal field that is not serializable.
The catch is that we don’t need to serialize the game and ball at all. We only need to deserialize the ball, and attach it to a Game. The Game instance doesn’t need to come directly from the serialized stream. We can put a substitute in its place, and override readResolve to replace it with a Game before it gets attached to the Ball.
Cheating in practice
There are multiple ways to create the raw data (byte array) that contains such a ball attached to a substitute game. Here’s mine; there are other ways in the comments below.
We create a class similar to Ball (Ba). We give it the same serialVersionUID as Ball and our desired caught value. It’s attached to our substitute implementing readResolve (Player). We serialize that and replace just the name of the Ba class with the Ball class. Converting the byte[] to a String and back allows us to use String.replace for that.
The name Ba is chosen so that play.Player$Ba has the same length as game.Game$Ball. Without that, directly replacing one with the other would corrupt the stream.
package play;
import game.Game;
import game.Game.Ball;
import java.io.*;
public class Player implements Serializable {
public static void main(String[] args) throws Exception {
ByteArrayOutputStream bos = new ByteArrayOutputStream();
new ObjectOutputStream(bos).writeObject(new Player().new Ba());
byte[] bytes = new String(bos.toByteArray(), "ISO-8859-1")
.replace("play.Player$Ba", "game.Game$Ball")
.getBytes("ISO-8859-1");
Ball ball = (Ball) new ObjectInputStream(new ByteArrayInputStream(bytes))
.readObject();
ball.caught();
}
class Ba implements Serializable {
static final long serialVersionUID = -7172046060844866133L;
private long caught = -1;
}
Object readResolve() {
return new Game();
}
}
This is what happens:
- When calling
readObject(), first theBallgets deserialized, andcaughtset to-1. - The value for
Ball.this$0that gets deserialized is an instance ofPlayer. - Before
Playergets assigned to that field (which would fail, because it’s of the wrong type), itsreadResolvemethod is called, creating a newGamewithscore0 - That
Gamegets assigned toBall.this$0, andreadObject()returns theBall. ball.caught()is called withcaught == -1andthis$0.score == 0, and you are caught cheating!
Conclusion
Creating serializable objects that have a reference to a non-serializable object is a bad idea because you cannot serialize them. But with some dirty tricks, you can still deserialize them.
Java serialization is full of nasty unexpected possibilities. You could do a whole series of puzzles about just that. But if you’re really into that nastiness, all you need to do is look at the JDK security vulnerabilities over the last years.
