The Secure Turing Complete Sandbox Challenge attempts to provide some evidence about whether it is possible to construct a secure sandbox. The core question is whether it is feasible to build a Turing-complete sandbox that does not possess a security vulnerability using common, off-the-shelf tools. In the first part of this challenge, you will construct a Turing-complete sandbox that other students will try to discover and expose vulnerabilities in.
Put intuitively, a Turing-complete sandbox (with infinite memory) can be used to compute any computable problem. A Turing-complete sandbox takes a program and data as input. (The program and data can be stored in the same area or separate ones.) Any Turing-complete sandbox can compute any problem that can be computed by any other sandbox.
Your sandbox only needs to handle computation. If you elect, you can support some form of I/O, but apart from having a mechanism to provide an initial program and data, this is not required except as specified below.
For our purposes, such a sandbox can make several simplifying assumptions that are common for many systems:
- The amount of memory can be restricted to a specific value. This is common for assembly language, C code, or byte code interpreters (like the JVM).
- The I/O of the sandbox can be very limited. It is not necessary to support file I/O, network I/O, or keyboard interaction. It is permissible to require that the program's source and data are loaded into memory when the sandbox is initialized.
- If the sandbox does not support output, the sandbox must have an option that prints out the first 10 bytes of memory when the program exits.
- The sandbox can be written in any language you choose.
- The programming environment of your sandbox must be documented and cannot be so limited as to be completely unusable.
To demonstrate the usability of your sandbox, you must implement several programs within it.
- You must implement a program that computes the powers of two from 1 to 128, either outputting them or placing these numbers into positions in memory that are always printed when the sandbox exits.
- You must provide a program computing the first ten fibonacci numbers. The resulting program should output these numbers or place them in the first ten memory locations when exiting.
Extra credit:
- You can implement a Turing-complete sandbox within your sandbox. This can be your sandbox or can be a classic Turing machine. Note that if you are implementing your sandbox, it is fine to have this sandbox have less memory available than your full sandbox.
Note: Your sandbox must be able to execute other programs! It cannot simply execute the above programs and nothing else.
You should assume that an adversary will be supplying the program and data to run in your sandbox. The adversary must not be able to perform actions like write files arbitrarily with the permissions of the sandbox's user (for example, overwriting the sandbox code).
You must turn in the URL and SHA1 hash of the head of your GitHub project. The project must contain the following:
- Detailed documentation explaining the file format and operations supported by your Turing-complete sandbox. The example programs must be referenced and their execution explained in the documentation. If you did not do the extra credit, you must explain in the document why you believe your sandbox is Turing-complete. This must be in PDF format.
- The source code for the Turing-complete sandbox
- The source for the example programs must be included. If these programs are in binary because of your file format, this is fine.
- A Makefile that builds the Turing-complete sandbox from source on an Ubuntu 12.X VM.
- A README file that explains how to build the sandbox and run the example programs from the command line.