Documentation of uevalrun

uevalrun is a self-contained computation sandbox for Linux, using User-mode Linux for both compilation and execution of the program to be sandboxed. The program can be written in C, C++, Python, Ruby, Perl, JavaScript, Lua or PHP. uevanrun enforces memory limits, timeouts and output size limits in the sandbox. The primary use case for uevalrun is evaluation of solution programs submitted by contestants of programming contests: uevalrun compiles the solution, runs it with the test input, compares its output against the expected output, and writes a status report.

Installation

A 32-bit (x86, i386) or 64-bit (x86_64, amd64) Linux system is required with enough RAM for both compilation and execution, plus 6 MB memory overhead. The Linux distribution doesn't matter, because uevalrun uses statically linked binaries, and it's self-contained: it contains all the tools it needs, including the C and C++ compilers (from the uClibc gcc-4.1.2 toolchain).

uevalrun doesn't need root privileges: it runs as a simple user.

uevalrun needs about 160MB of disk space, most of which is consumed by the C compiler (31MB extracted + 17MB compressed), the scripting language interpreters (9MB compressed), and the virtual disk images (77MB, uncompressed). After removing all temporary files, 80MB will be enough.

Download and compile:

$ svn co http://pts-mini-gpl.googlecode.com/svn/trunk/uevalrun uevalrun
$ cd uevalrun
$ ./make  # This downloads some more files during compilation.

Try it (the italic parts are displayed by the program):

$ (echo '#! perl'; echo 'print "Hello"x2, "\n"') >foo.pl
$ echo HelloHello >expected.txt
$ ./uevalrun -M 10 -T 9 -E 9 -s foo.pl -t /dev/null -e expected.txt
...
@ result: pass
$ echo '/**/ int main() { return!printf("HelloHello\n"); }' >foo.c
$ ./uevalrun -M 10 -T 9 -E 9 -U 19 -N 32 -C 9 \
  -s foo.c -t /dev/null -e expected.txt
...
@ result: pass

How to use

TODO(pts): Write this section.

Requirements

Security is the most important requirement of uevalrun, followed by high performance and usability.

The sandboxing must be secure, more specifically:

The sandbox must be fast and waste few resources, more specifically:

The sandbox must be easy to use and versatile, more specifically:

Design

To fullfill the requirements, the following fundamental building blocks are used.

User-mode Linux (UML) is used for virutalization: both compilation and execution is performed in a UML guest, reading data from the host system using virtual block devices (ubd), and writing its output to its /dev/tty1 (con0), which can be read by a process on the host. A UML guest kernel (currently 2.6.31.1) tailered to the sandboxing requirements (security and performance) is configured and compiled. Some kernel patches are applied to increase security, reliability and performance. (Please note that these patches apply to the UML guest kernel only, so the host remains unpatched, and rebooting is not needed either.) Networking and the virtual file system are disabled in the UML guest kernel for increased security. All unnecessary drivers and features are removed from the UML guest kernel to get fast boot times and to reduce the overhead.

The underlying virtualization technology used by UML is ptrace(), which doesn't need root privileges or a kernel module or kernel modifications in the host. As an alternative to UML, Seccomp could be used for sendboxing, but that's quite cumbersome, because the sandboxed process cannot allocate memory for itself (see the Google Chrome Seccomp sandbox for a generic solution), but it's still prohibitively cumbersome to sandbox GCC this way (with its requirements for forking and creating temporary files). Most sandboxing approaches on Linux require root privileges for a short amount of time (for chroot, PID namespaces (see clone(2)) and other namespaces). Most virtualization approaches (like KVM, Xen, VirtualBox, except possibly for QEMU) need loading of kernel modules or patching the kernel, and support only slow guest boot times.

With UML, it's possibly to boot the UML guest, run a hello-world binary, and halt the UML guest in less than 0.02 second (sustained). For that speed, one needs a (guest) kernel patch (included and automatically applied in uevalrun) which skips the Calibrating delay loop kernel startup step, which usually takes 0.33 second. The memory overhead of UML is also quite low (6 MB with a stripped-down kernel).

All software running inside and outside UML is written in C (for high performance) and compiled with uClibc and linked statically to avoid depending on the libc on the host, and to avoid the need for installing a libc in the guest. (The total size of these custom-built binaries is less than 100kB.) There is no Linux distribution installed the guest – only a few custom binaries are copied, like a custom /sbin/init, which mounts /proc, sets up file descriptors and resource limits, and starts the sandboxed program, and then halts the guest. The /lib directory in the guest is empty, except for compilation, where /lib contains libc.a, libstdc++.a etc.

BusyBox (statically linked with uClibc) is used as a Swiss Army Knife tool for scripting and automation (of the build and the setup process), both inside and outside UML. Please note, however, that once all the binaries are built and the filesystem images are created, BusyBox is not used anymore for running sandboxed programs and evaluating their output (except for temporary filesystem creation) because of performance reasons, but work is done by the small and fast custom C tools just compiled.

Sandboxed program sources can be written in C (using a large subset of uClibc as the system library), C++ (using uClibc and libstdc++), Python (using all the built-in Python modules), Ruby (using just the built-in Ruby modules and classes which are implemented in C), Perl (using only the few dozen most common modules), JavaScript (with SpiderMonkey 1.8 smjs-1.8.0, containing readline and print), Lua (with the full luajit-1.1.6 available), or PHP (using just the built-in PHP functions which are implemented in C).

For C and C++ compilation, a GCC 4.1.2 toolchain is used which is based on uClibc and produces statically linked executables.

Interpreters for Python, Ruby, Perl, JavaScript, Lua and PHP are provided as precompiled, self-contained, single, statically linked, 32-bit (i386) Linux executables. It's easy to copy them to the /bin directory of the UML guest.

All tools used for building the software are either shipped with the software, or the software downloads them during compilation. All binary tools are statically linked, 32-bit (i386) Linux executables. This provides maximum host system compatibility and reproducible behavior across systems.

In our speed measurements, CPU-intensive programs running inside UML run 1% slower than outside UML, but I/O-intensive programs (such as C++ compilation with GCC) can be about 15 times slower.

The Minix filesystem is used in the UML guests for both read-only filesystems (e.g. the root filesystem with the scripting language interpreters) and read-write filesystems (such as /tmp for the temporary assembly files created by GCC). The Minix filesystem was chosen instead of ext2 and other usual Linux filesystem, because it has less size overhead, it's codebase is smaller, and it has equally good performance for the small and mostly read-only filesystems it is used for.

How to make it faster?

User-mode Linux runs CPU-bound programs only a few percent slower than how fast they run natively on the host. But for programs that do lots of I/O (such as compiling a C++ hello-world program containing #include <iostream> with g++), User-mode Linux can be about 15 times slower than native execution. (On some machines, the same bechmark is only 6 time slower.)

For sandboxing C and C++ compilation with GCC we could use a method which less overhead than User-mode Linux to reduce the slowdown factor of 15. One direction is to use a more lightweight ptrace()-based approach (thus running everything in userspace), and another direction is to use a Linux kernel module (such as apparmor) for sandboxing.

We've tried sydbox for sandboxing, and measured its speed versus native execution and User-mode Linux. The result is surprising: User-Mode Linux is faster. Here are the details:

$ cat scat.cc
//
#include <iostream>
using namespace std;
int main() {
  (cerr << "error1\n").flush();
  cout << "Hi!\nHello, C++ World!\n";
  cerr << "error2" << endl;
  return 0;
}

$ time $CXX -static -o /tmp/prog -W -Wall -s -O2 scat.cc 
real    0m0.326s
user    0m0.310s
sys     0m0.030s

$ ls -l sydbox
-rwxr-x--- 1 pts eng 525804 Jan  1 17:20 sydbox
# sydbox and pinktrace downloaded from their GIT repo on 2011-01-01.
$ file sydbox
sydbox: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, stripped
$ time ./sydbox -c t.conf -- $CXX -static -o /tmp/prog2 -W -Wall -s -O2 scat.cc 
real    0m6.576s
user    0m1.790s
sys     0m1.880s

$ ls -l uevalrun.linux.uml
-rwxr-x--- 1 pts eng 1087212 Jan  1 15:02 ../uevalrun.linux.uml
$ file uevalrun.linux.uml
uevalrun.linux.uml: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, stripped
$ time ./uevalrun.linux.uml con=null ssl=null con0=fd:-1,fd:1 mem=38M \
  ubdar=uevalrun.rootfs.gcx.minix.img ubdbr=scat.cc ubdcr=answer.in \
  ubddr=uevalrun.guestinit ubde=tmp.minix.img solution_format=gxx \
  init=/dev/ubdd root=98:0 >/tmp/t.bin
real    0m4.833s
user    0m0.920s
sys     0m1.760s

Our conclusion is that it would be hard to beat the speed decrease of 15 provided by User-mode Linux — maybe we would have to write a speed-optimized ptrace()-based sandbox in C from scratch. In theory, this can work, because strace -f -e getppid g++ is only about 2.64 times slower than regular g++, so our optimized implementation can be 3 times slower. We should also measure G++ with another ptrace()-based sandboxing method first.

Similar software

codepad is similar to uevalrun: it compiles and runs arbitrary user-submitted code in many languages. It uses a custom sandboxing based on ptrace(), implemented in Haskell (User-mode Linux used by uevalrun is also based in ptrace()).

License

uevanrun has been released under the GNU GPL v2.

Bugs? Problems? Contact the author. Send feedback!

Please add your feedback to the issue tracker. All feedbacks are welcome.