Please note that these Trac pages are no longer being updated. Wiki contents/documentation have moved to GitHub.

EducationalAssignments/SecureTuringCompleteSandboxChallengeBuild

Version 4 (modified by justinc, 7 years ago)

--

Secure Turing Complete Sandbox Challenge -- Building the Sandbox

The Secure Turing Complete Sandbox Challenge attempts to provide some evidence for or against the possibility of constructing 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.


Turing Completeness


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:

  1. 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).
  2. 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.
  3. 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.
  4. The sandbox can be written in any language you choose.
  5. The programming environment of your sandbox must be documented and cannot be so limited as to be completely unusable.


Example Programs For Your Sandbox


To demonstrate the usability of your sandbox, you must implement several programs within it.

  1. You must implement a program that counts from 10 to 1, either outputting them or placing these numbers in the first ten positions in memory.
  2. You must provide a program computing the first ten fibonacci numbers. The resulting program should output these numbers or place the first ten numbers in these memory locations when exiting.

Extra credit:

  1. 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.


Threat Model


You should assume that an adversary will be supplying the program and data to run in your sandbox. This program can perform any operation supported by your sandbox. The adversary should not be able to perform actions like write files arbitrarily with the permissions of the sandbox's user (for example, overwriting the sandbox code).


What To Turn In


You must turn in a zip-file or tarball containing the following:

  1. 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.
  2. The source code for the turing-complete sandbox
  3. The binary source for the example programs must be included.
  4. A Makefile that builds the turing-complete sandbox from source on an Ubuntu 10.04 VM.
  5. A README file that explains how to build the sandbox and run the example programs from the command line.