In today’s Java puzzle we play a very simple game. I throw a ball, and if you catch it you score a point. Your total score is the amount of times you caught the ball. Or is there another way to score?

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 same rules as usual apply; you must run with the security manager enabled (-Djava.security.manager). Your solution also must be in the play package. Putting anything else in the game package is not allowed.

If you found it, post your solution as a comment. These comments stay private, and become public later on the next blog post.

Can you program your way past airport security? The usual rules apply.

No liquids are allowed in your hand luggage:

package liquid;

import java.lang.String;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class Luggage {
    private final Collection<String> items;

    public Luggage(Collection<String> items) {
        items = Collections.unmodifiableCollection(new ArrayList<String>(items));
        for (String item : items) {
            if (item.contains("liquid")) {
                throw new SecurityException("No liquids allowed in your hand luggage!");
            }
        }
        this.items = items;
    }

    public Collection<String> getItems() {
        return items;
    }

    public void fly() {
        if (items.contains("liquid water")) {
            // The goal is to reach this line
            System.out.println("Oh no, water on a plane! We're all going to die!");
        }
    }
}

Can you, as a thirsty passenger, take some water with you anyways? Leave your answer in a comment. The comments will stay private for a while, and be published later in the next blog post.. Try to solve it, and then look at the solutions in the comments below!

Update: comments were briefly not moderated, already showing the solution immediately; sorry for that.
Update: Let’s try to do it differently from the other puzzles then! Only look at the comments below after you’re tried to solve it yourself!

Let’s see how we can get the upgraded car to break the speed limit. Take a closer look at the car:

package car;
 
public final class Car {
    private final int MAX_SPEED = 100;
 
    private int speed = 0;
 
    public synchronized void accelerate(int acceleration) {
        speed += acceleration;
        if (speed > MAX_SPEED)
            crash();
    }
 
    public synchronized void crash() {
        speed = 0;
    }
 
    public synchronized void vroom() {
        if (speed > MAX_SPEED * 10) {
            // The goal is to reach this line
            System.out.println("Vroom!");
        }
    }
}

Lesson to all you racers out there: We want the car to accelerate a lot (speed += acceleration must execute), but not do that thing where it hits the tree and comes to a full stop (speed = 0 must not execute).

What can happen between those two statements? The if (speed > MAX_SPEED) doesn’t help us any further, because speed really needs to be higher than MAX_SPEED. So all that’s left is the call to the crash() method. That one has to fail: We want crash() to crash!

We can do that by making sure there’s not enough space left on the stack to be able to call any method. If the stack is almost full when we call accelerate, we get a StackOverflowError on the call to crash(). How do we get the stack to be almost full? One way is to just brute-force it: an infinitely recursing method that just keeps trying.

package driver;

import car.Car;

public class Driver {
	private static Car car = new Car();
	
	public static void main(String args[]) {
		try {
			recurse();
		} catch (StackOverflowError e) {
		}
		
		car.vroom();
	}
	
	public static void recurse() {
		car.accelerate(1001);
		recurse();
	}
}

And that works!… On some systems at least. A problem here is that if you’re trying to accelerate so much and keep on crashing (after 1500 crashes on my system), the JVM does something no car maker ever would: it optimizes the car to ensure it can crash really fast. It in-lines the call to crash(), reducing it to essentially if (speed > MAX_SPEED) speed = 0;. That eliminates the possibility of a StackOverflowError.

We can work around that by being just a little gentler on the car: crash it a bit less, so the JVM doesn’t decide to optimise that. First grow the stack until it’s getting close to where it needs to be, and only then add the car into the equation. But the only way to know you’re getting close to the limit is by hitting it. Therefor we recurse without the car until we hit the stack overflow, then take a few steps back, and then apply the brute-forcing solution from above:

package driver;

import car.Car;

public class Driver {
    static Car car = new Car();
    static int a = 0;

    public static void main(String args[]) {
        recurse();
        car.vroom();
    }

    static void recurse() {
        try {
            recurse(); // recurse without the car
        } catch (StackOverflowError e) {
            // when we've hit the limit of the stack, just go back out
        }
        if (a++ == 10) { // after taking 10 steps back
            recurse2(); // recurse with the car
        }
    }

    static void recurse2() {
        car.accelerate(1001);
        recurse2();
    }
}

An alternative solution is to use Thread.stop. But it’s quite hard to time it right; it doesn’t work that reliable across systems. At first I expected it to be impossible in practice, but I was proven wrong. You can see the code in the comments below.
You do need a special permission to call that method, but that’s one of the very few things included in the default security policy file. The only other permissions in there are opening listening sockets on high ports, and reading some standard system properties.

Conclusion

Not many succeeded in solving this one. The ones who did, and their solutions can be admired below as time-travelling comments that were posted before this blog post appeared.

The fact that this hack is possible makes me wonder. Is all privileged code in Java itself really prepared to crash at any time? Including all native code? If an applet makes the loading of a class fail in this way; does that cause NoClassDefFoundErrors in other applets? How else could this be abused?…

Please, don’t try this at home. Car insurance usually doesn’t cover the failing of the crashing of the crash. Even if you first tried crashing without the car; running with your head straight into the tree. Blowing up the car right before it hits the tree is not appreciated either.

In the next puzzle we’ll sneak some goods passed airport security, so stay tuned!

Here’s the solution to the first part of the car puzzle. And, — for those who haven’t solved part one and seen it yet — we’ll toughen up the challenge for the second round. Here’s the method it’s all about:

    public synchronized void accelerate(int acceleration) {
        if (acceleration > MAX_SPEED - speed)
            crash();
        else
            speed += acceleration;
    }

How do we make this go over the speed limit?
The flaw is in the check of the acceleration: it checks if it’s too high, but it forgot to check if it’s too low. Put your gearbox in reverse, push the pedal to the metal (Integer.MIN_VALUE), and the speedometer will wrap around.

Car car = new Car();
car.accelerate(-1);
car.accelerate(Integer.MIN_VALUE);
car.vroom();

First we give it a little tap to set speed to -1. Then we push it all the way: the check if Integer.MIN_VALUE > 99 passes, giving us -1 + Integer.MIN_VALUE. That causes an underflow, putting the car in its real top speed: Integer.MAX_VALUE.

Let’s avoid that kind of mistake, by checking the resulting speed instead of the acceleration:

package car;

public final class Car {
    private final int MAX_SPEED = 100;

    private int speed = 0;

    public synchronized void accelerate(int acceleration) {
        speed += acceleration;
        if (speed > MAX_SPEED)
            crash();
    }

    public synchronized void crash() {
        speed = 0;
    }

    public synchronized void vroom() {
        if (speed > MAX_SPEED * 10) {
            // The goal is to reach this line
            System.out.println("Vroom!");
        }
    }
}

Can you still break the speed limit in this car?

The solutions (yes, that’s plural) to this are not always very reliable. How good they work may depend on the environment they’re running in. But with some tweaks and the right approach, it is possible to build a solution that should work all the time in practice without taking any significant time. 175 people solved the first part, but so far only 11 broke this part. If that doesn’t scare you off, good luck! You can try out your solution on this ugly site.

The solutions will follow tomorrow are available.

This java puzzle comes in two parts. You have to solve this part to see the next one.
To warm up the engine, we start with the easiest one. Part two will be harder.

This car crashes if you accelerate too much. But can you make it go ten times faster than its limit?

package car;

public final class Car {
    private static final int MAX_SPEED = 100;

    private int speed = 0;

    public synchronized void accelerate(int acceleration) {
        if (acceleration > MAX_SPEED - speed)
            crash();
        else
            speed += acceleration;
    }

    public synchronized void crash() {
        speed = 0;
    }

    public synchronized void vroom() {
        if (speed > MAX_SPEED * 10) {
            // The goal is to reach this line
            System.out.println("Vroom!");
        }
    }
}

As a driver, do what needs to be done to push the car over its limit. Anything in your code is allowed; any trick outside the code is not. You must run with -Djava.security.manager, so setAccessible won’t work. If in doubt, read the exact rules.

package driver;

import car.Car;

public class Driver {
    public static void main(String args[]) {
        // TODO break the speed limit
        Car car = new Car();
        car.accelerate(1001);
        car.vroom();
    }
}

If you’ve found the solution, post it into the ugly form over there. There it will be compiled and ran, and if it works, you will be directed to part two. When you’ve solved it, take a look at part 2.

To be notified of when the solution and next puzzles come out, follow the rss feed or twitter.

Time to dream the solution to the dreams puzzle. As a reminder, here’s the challenge:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;
	
	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

Solution

The synchronized on the dream method means that it takes the monitor (lock) of the Sleeper object when we enter it, and it releases it again when we leave it. No other thread can enter the method while the monitor is held.

But here’s the catch: the monitor isn’t necessarily held all the time while the method is running. With Object.wait you can release a monitor in the middle of a synchronized method.

How do we apply that to solve this puzzle? When we enter the outer dream, we use wait to release the monitor. But first we launch a separate thread, that will also enter a dream. Entering that inner dream makes the second thread take the monitor. So in the inner dream, we use wait a second time to release the monitor. That allows the main thread stop waiting, take the monitor back, and leave the outer dream. And there we are: we have woken up from the outer dream, back where we started in main, but the dream within the dream goes on in the second thread.

package dream;

import sleep.Sleeper;

public class Dream {
	private static void doWait(Sleeper s) {
		try {
			s.wait(200);
		} catch (InterruptedException e) {
		}
	}
	
	public void dream(final Sleeper s) {
		new Thread() {
			public void run() {
				s.enter(new Dream() {
					@Override
					public void dream(Sleeper s) {
						doWait(s);
					}
				});
			}
		}.start();
		
		doWait(s);
	}
}

And the winner is…

I got more answers than I expected. The first one came from David Shay. Congrats!

It’s a bit repetitive, but as promised, you can see and compare all dreams as comments below this post.

Conclusion

The moral of the story: synchronized on a method doesn’t mean two different threads can’t be in it at the same time. It only ensures that such threads cannot execute concurrently; at least one of them must be waiting.

You can prevent this kind of abuse and other problems, by using a private object as monitor:

public class Sleeper {
	private final Object lock = new Object();
	
	public int dream(Dream dream) {
		synchronized(lock) {
			...
		}
	}
}

But that still leaves me unsure if I actually woke up this morning.

Here’s another challenging Java Puzzle! The same rules as for the clowns puzzle apply. [Update: In short: anything in your code is allowed; any trick outside the code is not. You must run with -Djava.security.manager, so setAccessible won't work.].

We’ve learned our lesson from the clowns: There are no hidden calls behind the scenes here, and we embrace recursion; we count on it.

Have you ever woken up from a dream, to then discover that you’re actually still dreaming? If you then wake up, how do you know you’re back in reality? This puzzle implements a solution to that problem: you count the recursion level of your dreams as you enter and exit them:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;
	
	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

A sleeper starts sleeping and enters a dream (level one). He can have a dream within that dream, and even enter deeper dreaming levels. But when he leaves the outer dream, he’s awake again, so he should be at level zero again, right?

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

The counting of the levels looks really safe, so this seems impossible:

• Every time you enter a dream level is increased. Because of the finally block, there’s no way to leave a dream without decreasing it again.
• The synchronized block makes sure no other thread can call it concurrently. The level is returned from the dream method to make sure it’s read within the synchronized block.
• dream is the very first thing that’s called on the Sleeper, so the level must be zero when entering it. The value that’s returned from it must be zero too then, because even if we call it recursively we must enter as many dreams as we exit.

// this is the only file you're allowed to edit
package dream;

import sleep.Sleeper;

public class Dream {
	public void dream(Sleeper s) {
		// TODO implement me
	}
}

Do you eat Java, breathe Java, and even dream in Java? Can you find the flaw in this reasoning? Can you imagine a really weird dream, that would make the sleeper lose count? If so, leave your code in a comment here!

To give everyone a fair chance, those comments will stay were hidden for a while. They will become public soon are now public, together with a follow-up blog post.
To be notified of that and the next puzzles, follow the feed or twitter.

PS: This puzzle is appearing simultaneously in the Java Specialists’ Newsletter.

Spoiler warning: If you want to find out how you can fit 20 clowns into a Volkswagen, read on. If you haven’t seen or tried solving the clowns java puzzle yourself, do that first!

As a reminder: here’s the code it’s all about:

package clowns;

import java.util.HashSet;
import java.util.Set;

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Path to the solution

Imagine this was a real car with real clowns.

– It’s impossible to get twenty clowns in! There are only five seat belts, and this Volkswagen really insists on safety. When a clown enters, it first checks if there aren’t already five of them sitting in it. Only after that checks it allows another one to sit (clowns.add(clown)). As soon as there are five clown sitting, there’s no way to pass the check anymore, so no way to add any extra clown.
– You’re right that we can’t add them one by one. But there is a window of opportunity between the check when they enter the car, and when they really sit down. Make all twenty clowns simultaneously enter the car. They will all pass the check of the Volkswagen, because it only counts clowns that are already sitting down. And only after the check let them sit.
– The car’s synchronized protection prevents anyone else from doing anything with it between the check and the sitting down.
– Indeed, it prevents someone else from interfering. It doesn’t prevent the Volkswagen or the clown itself to do it if they’re given the opportunity (on the same thread).
– But they don’t get that opportunity; the car is a control freak. After the check it immediately makes them sit in their seats (in the Set).
– Did you have a look at those seats? They’re numbered, and they always first asks a person at which number they want to sit (.hashCode()). We’ve got some weird clowns here: when they’re given the opportunity to decide that, right before answering, they can quickly pull another clown into the car. And that clown then does exactly the same with another clown. That goes on until there’s a stack of twenty of them recursively pulling each other in. As long as their ass doesn’t touch the seat, the seat-belt sign won’t come on.
– That must be quite a sight.

The solution

Call Volkswagen.add recursively, by overriding Clown.hashCode():

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    static int counter = 0;
    static Volkswagen vw = new Volkswagen();

    public static void main(String args[]) {
        vw.add(new RecursiveClown());
        vw.done();
    }

    static class RecursiveClown extends Clown {
        public int hashCode() {
            if (++counter < 20) {
                vw.add(new RecursiveClown());
            }
            return super.hashCode();
        }
    }
}

And the winner is…

The first solution came from Heinz Kabutz, famous from The Java Specialists’ Newsletter. He actually pushed me to publish these puzzles in the first place and promoted them. To show my infinite gratitude I’m going to disqualify him for having seen the puzzle in advance.

I received 7 correct solutions that passed the clarified rules. All used the same principle: adding them simultaneously using hashcode. Half of them also danced around the Volkswagen a bit in different threads to accomplish that. That’s fine; there’s no ban on dancing clowns here.

Congrats to all of you, especially Manuel Alvarez who was the first, and runner-up Jean-Louis Willems with the first short solution.

Conclusion

A simple check at the beginning of a synchronized method is not enough to guarantee safety if you’re not very careful with which code you give control to. But should you really worry about crazy recursive clowns when writing your simple Volkswagen code?

No, you shouldn’t. Well, not unless it’s about privileged code handling a sandbox — such as code of the JDK itself when running an applet. But it sure is interesting to explore these dark corners of Java. We’ll continue on that track soon with a puzzle about dreams…

Introduction

This is the first in a series of Java puzzles, that put your Java skills to the test, in a challenging and fun way!
A puzzle consists of some given Java code with a line in it that seems to be impossible to reach. It’s up to you to find the hole in it, abuse a subtle behavior of Java to make execution reach that line anyways.

There almost aren’t any rules; any cheating inside your code is allowed; it is the whole point of the puzzle. [Clarification: Cheating the environment is not]. You must run with the security manager enabled (java -Djava.security.manager), otherwise it would be too easy (with setAccessible for example). [Update: Use common sense, and see the exact rules if you're in doubt].

The puzzle

How can you fit 20 clowns into a Volkswagen? Two classes are given: an empty Clown class, and a Volkswagen class to which you can add clowns. When you try to add a Clown, it is checked that it isn’t already full. But if you just try hard enough, there’s always room for some extra clowns…

package clowns;

public class Clown {
}

package clowns;

import java.util.HashSet;
import java.util.Set;

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Write a class that when executed pushes 20 clowns into the little car, and reaches the marked line. Here is one that won’t really work, just to get you started:

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    public static void main(String args[]) {
        // TODO put 20 clowns into a Volkswagen
        Volkswagen vw = new Volkswagen();
        for (int i = 0; i < 20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}

You can copy-paste the code into your IDE, or get it from github (zip).
If you’ve solved it, let me know (email or Twitter). If you’re the first, you’ll get… the honor of being the first. compare it to the solution posted here.
The solution and a new challenge will follow, so stay tuned!

Update: Don’t post answers as comments here, they will be blocked by moderation. You may comment, but no spoiler. If you have an alternative solution, post it as a comment on the solution post
Update 2: Added clarification of the rules.

My review of Vaadin‘s security revealed these vulnerabilities, now fixed in Vaadin 6.6.7.

What is Vaadin? In their own words: Vaadin is a Java framework for building modern web applications. Its server-side architecture [and] security mechanisms to prevent eg. man-in-the-middle and cross-site scripting attacks [...] make Vaadin one of the most secure UI frameworks in existence.

Separator injection

In a Vaadin application, the server sends updates to the client using JSON, but the client uses a custom format to send updates to the server. This format uses exotic characters as a separator between records/variables. But, prior to Vaadin 6.6.7, there is no mechanism to escape those characters when they occur within the data. If an attacker can trick a client into sending his crafted data to the server, he can perform actions in the user interface on behalf of the victim.
In other words, the result is similar to that of cross site request forgery (CSRF).
If certain UI components, such as the rich text area (which allows a user to set arbitrary HTML) are used anywhere in the application, this also leads to cross site scripting (XSS).

There are multiple ways a client can be tricked into sending such data. For example a user could be tricked into copy-pasting a certain string. But there is also an automated way: if the application uses the URL fragment (with the UriFragmentUtility), the characters can be injected in there. Whether that last trick actually works depends on the browser. It works on Chrome but doesn’t seem to work on Firefox, probably due to the way such characters are encoded.

More concretely, how does the format work? Suppose the user changes the text in a in a text field (with id PID1) to “test”, and then presses a button (PID2; setting “state” to true). The client could then send the following (slightly simplified), were [xx] is the character with the given hexadecimal ascii value:

0a09a5e2-3190-4f16-a75b-284b98d221ce[1D]test[1F]PID1[1F]text[1F]s[1E]true[1F]PID2[1F]state[1F]b
1D is the burst separator, 1F the field separator, and 1E the record separator. The “s” means type string, and “b” type boolean. The first part is the anti-CSRF token.

If the text value instead of “test” would have been true[1F]PID3[1F]state[1F]b, then the server would interprete that as the user clicking on the button PID3. That can be done in the url fragment, with a url like this: http://vaadin-application/#true%1FPID3%1Fstate%1Fb.

This is Vaadin ticket 7669.

Classpath directory traversal

The Servlet in Vaadin takes care of the communication, but also serves static resources (html, javascript, css, images…). It looks for these resources in the “VAADIN” directory on the web application’s classpath. Usually these resources would be found in a jar of the application, such as the Vaadin jar itself. But if the classpath also contains a directory (instead of only jars), also resources outside of the VAADIN directory can be retrieved using a simple /../ directory traversal. That allows an attacker to download the (byte)code of the application or configuration files (possibly containing passwords).

If this is exploitable in practice depends on how the application was packaged, and which servlet container is running it.

For example, creating a simple Vaadin application skeleton using the maven archetype with mvn archetype:generate -DarchetypeGroupId=com.vaadin -DarchetypeArtifactId=vaadin-archetype-clean -DarchetypeVersion=1.5.6 -DgroupId=tst -DartifactId=tst -Dversion=0 -Dpackaging=war and starting it with mvn package jetty:run, the main application class could be reached at the url /tst/VAADIN/../tst/MyVaadinApplication.class.

This is Vaadin ticket 7670.

Contributory XSS

There some places in the Vaadin framework that make it easy for a developer to introduce XSS problems. These are not directly exploitable by themselves, but in combination with other code can turn into vulnerabilities.

Exceptions on the server-side in handling updates from the client are often shown with an exclamation mark in a red circle next to the UI component that caused it; and hovering over that icon shows a tooltip with the exception stacktrace in it. HTML in that tooltip in the message of the exception (or its cause in the stacktrace) is not escaped.
For example, take a Vaadin application that shows a number in a text input field (without adding an explicit validator). If you paste HTML in that text field, parsing of that text to a number will fail with a NumberFormatException whose message includes the HTML text, that will then be shown unescaped.

I didn’t find an automated way to exploit this that doesn’t involve convincing a user to copy-paste some HTML. But this issue has the danger of turning another normal bug (that results in an otherwise harmless exception) into a security vulnerability.

This is Vaadin ticket 7671.

The src attribute of a number of UI components, which can contain a URL, is often handled without escaping. This seems to be the case for at least Embedded (when type is browser, i.e. an iframe), VWindow, VMenuBar, VFilterSelect, VView and Action. In an application where users are allowed to configure such a URL, which would then be used in such a component when shown to another user, this would be an exploitable XSS. That would be unusual, but not impossible; for example for the Embedded component, imagine a form where users can include an iframe in their posts.

This is Vaadin ticket 7672.

Finally, in a slightly different category, there are strings that are shown intentionally as HTML without escaping, in places where it is not clearly documented in the Vaadin API. This is the case in the tooltip (description) of all components, caption of a Panel or a notification (as in Window.showNotification). If you use user-provided text in any of those, you must take care of escaping yourself. Future versions of Vaadin (starting from 6.7) will provide plain-text modes at least for some of these.

Conclusion

Vaadin is still a framework with a particularly good security architecture and counter-measures. But no program or framework is completely immune to security vulnerabilities. Vaadin’s reaction to these vulnerabilities was quick and thorough.

Now it’s time to update your Vaadin applications to a newer version!