On Online Judging, Part 4: a Java-Specific Sandbox

If you've been following along this far in our creation of a sandbox for an online judging system, you may recall this requirement we set out with:

The sandbox must be easy to expand to support more runtimes. Language-specific sandboxes are unacceptable, simply due to the effort of maintaining them.

While this is true in the general case, exceptions do have to be made for popular runtimes that need a little extra flexibility in judging — which brings us to today's topic, a Java-specific sandbox.

Scenario: you have a problem that asks contestants to do something nontrivial, which is made trivial by a specific library Java comes with. For example, a problem that asks users to implement big integers is rendered trivial by java.math.BigInteger. We need to be able to disallow access to that particular class, while allowing users to program their own implementations of a big integer in Java.

Solution: we can use the little-known java.lang.instrument API to filter through which classes are allowed to load, and throw an exception during class instrumentation if it's not. It's acceptable to run the rest of the application through our regular sandbox, though we may also make use of the Java security policy APIs.

Introduction: the Instrumentation API

java.lang.instrument is what allows your favourite Java IDE to do fancy things like breakpoints, profiling, and so forth. You can instrument applications straight from their launch by specifying a -javaagent parameter, or during runtime by using the Oracle-specific Attach API (tools like jstack do this, but this is a topic best left for a future post). We'll only be needing the "from launch" option, as we control process startup.

A Simple Solution to Ban BigInteger

Using the instrumentation API is really best explained with a functioning example. Below, we have a simple agent that disallows all access to java.math.BigInteger.

package ca.dmoj.java;

import java.io.*;
import java.lang.instrument.*;
import java.security.*;

public class SubmissionAgent {

    public static void premain(String argv, Instrumentation inst) {
        // We need to know the main Thread, because our ClassFileTransformer can be called from any Thread,
        // and raising an exception in another Thread won't kill the main application like we want
        final Thread selfThread = Thread.currentThread();

        inst.addTransformer(new ClassFileTransformer() {
            @Override
            public byte[] transform(ClassLoader loader, String className, Class<?> classBeingRedefined,
                                    ProtectionDomain protectionDomain, byte[] classfileBuffer)
                                    throws IllegalClassFormatException {
                // If the class ever loaded it's because a submission used it
                if (className.equals("java/math/BigInteger")) {
                    selfThread.getUncaughtExceptionHandler().uncaughtException(selfThread, new RuntimeException());
                }
                
                // Don't actually retransform anything
                return classfileBuffer;
            }
        });
    }
}

Of course, this agent is incomplete for the needs of a real online judge (for example, BigInteger banning should be configurable per-problem, BigDecimal is still allowed, etc.), however, this is enough to demonstrate the general approach.

Let's run through what happens when a submission using BigInteger is loaded with this instrumentation agent attached.

  1. the JVM initializes; loads our agent into memory and calls premain
  2. the JVM loads the user's submission
  3. the user's submission passes through our ClassFileTransformer — it doesn't match our java/math/BigInteger class, so we simply return
  4. the user's submission begins executing — our agent is not called
  5. the user's submission reaches the first instantiation of a BigInteger object
  6. the JVM searches for where to load BigInteger from, and proceeds to load it
  7. our ClassFileTransformer is called for the BigInteger class
  8. we throw an exception, because the user shouldn't be using BigInteger
  9. the JVM exits with an error

It may seem like a mouthful, but it follows logically from Java's class-loading procedure (specifically, that a class is only loaded when it is first needed).

The instrumentation API can do far more than we are doing here — it can entirely rewrite the raw bytes of any class — but this is enough to solve our problem with a minimal amount of code written.

Putting it All Together

All that remains is to package our agent such that the JVM will allow loading it. We need a specific declaration in our MANIFEST.MF file to tell Java that our jarfile is in fact an agent.

Manifest-Version: 1.0
Premain-Class: ca.dmoj.java.SubmissionAgent
Sealed: true

A short breakdown of what's defined here:

  • Manifest-Version: is always 1.0
  • Premain-Class: tells Java where to look for our premain function
  • Sealed: prevent user code from being defined in the ca.dmoj.java package

If we build our jarfile with our agent and the specified manifest file, seeing it in action is as simple as running:

$ java -javaagent:agent.jar UserSubmission

Conclusion

That wraps up the banning of particular classes for Java! The creative reader may also have noticed that since we have code running in the same process as the submission, we may do further things useful to online judging, like disabling output buffering (for interactive problems), increasing output buffering (for everything but interactive problems), and so on.

The code backing DMOJ's Java executor is open-source, and you may browse it to see the above ideas in practice.