How to create a lightweight C code sandbox?

Question

Since the C standard is much too broad to be allowed, you would need to go the other way around: specify the minimum subset of C which you need, and try to implement that. Even ANSI C is already too complicated and allows unwanted behaviour.

The aspect of C which is most problematic are the pointers: the C language requires pointer arithmitic, and those are not checked. For example:

char a[100];
printf("%p %p\n", a[10], 10[a]);

will both print the same address. Since a[10] == 10[a] == *(10 + a) == *(a + 10).

All these pointer accesses cannot be checked at compile time. That's the same complexity as asking the compiler for 'all bugs in a program' which would require solving the halting problem.

Since you want this function to be able to run in the same process (potentially in a different thread) you share memory between your application and the 'safe' module since that's the whole point of having a thread: share data for faster access. However, this also means that both threads can read and write the same memory.

And since you cannot prove compile time where pointers end up, you have to do that at runtime. Which means that code like 'a[10]' has to be translated to something like 'get_byte(a + 10)' at which point I wouldn't call it C anymore.

Google Native Client

So if that's true, how does google do it then? Well, in contrast to the requirements here (cross-platform (including embedded systems)), Google concentrates on x86, which has in additional to paging with page protections also segment registers. Which allows it to create a sandbox where another thread does not share the same memory in the same way: the sandbox is by segmentation limited to changing only its own memory range. Furthermore:

• a list of safe x86 assembly constructs is assembled
• gcc is changed to emit those safe constructs
• this list is constructed in a way that is verifiable.
• after loading a module, this verification is done

So this is platform specific and is not a 'simple' solution, although a working one. Read more at their research paper.

Conclusion

So whatever route you go, you need to start out with something new which is verifiable and only then you can start by adapting an existing a compiler or generating a new one. However, trying to mimic ANSI C requires one to think about the pointer problem. Google modelled their sandbox not on ANSI C but on a subset of x86, which allowed them to use existing compilers to a great extend with the disadvantage of being tied to x86.

I think you would get a lot out of reading about some of the implementation concerns and choices Google made when designing Native Client, a system for executing x86 code (safely, we hope) in the browser. You may need to do some source-rewriting or source-to-source compilation to make the code safe if it's not, but you should be able to rely on the NaCL sandbox to catch your generated assembly code if it tries to do anything too funky.

If I were going to do this, I would investigate one of two approaches:

• Use CERN's CINT to run sandboxed code in an interpreter and see about restricting what the interpreter permits. This would probably not give terribly good performance.
• Use LLVM to create an intermediate representation of the C++ code and then see if it's feasible to run that bytecode in a sandboxed Java-style VM.

However, I agree with others that this is probably a horribly involved project. Look at the problems that web browsers have had with buggy or hung plugins destabilizing the entire browser. Or look at the release notes for the Wireshark project; almost every release, it seems, contains security fixes for problems in one of its protocol dissectors that then affect the entire program. If a C/C++ sandbox were feasible, I'd expect these projects to have latched onto one by now.

I stumbled upon Tiny C Compiler (TCC). This may be what I need:

*  SMALL! You can compile and execute C code everywhere, for example on rescue disks (about 100KB for x86 TCC executable, including C preprocessor, C compiler, assembler and linker).
* FAST! tcc generates x86 code. No byte code overhead. Compile, assemble and link several times faster than GCC.
* UNLIMITED! Any C dynamic library can be used directly. TCC is heading torward full ISOC99 compliance. TCC can of course compile itself.
* SAFE! tcc includes an optional memory and bound checker. Bound checked code can be mixed freely with standard code.
* Compile and execute C source directly. No linking or assembly necessary. Full C preprocessor and GNU-like assembler included.
* C script supported : just add '#!/usr/local/bin/tcc -run' at the first line of your C source, and execute it directly from the command line.
* With libtcc, you can use TCC as a backend for dynamic code generation.

It's a very small program which makes hacking on it a viable option (hack GCC?, not in this lifetime!). I suspect it will make an excellent base to build my own restricted compiler from. I'll remove support for language features I can't make safe and wrap or replace the memory allocation and loop handling.

TCC can already do bounds checking on memory accesses, which is one of my requirements.

libtcc is also a great feature, since I can then manage code compilation internally.

I don't expect it to be easy but it gives me hope I can get performance close to C with less risks.

Still want to hear other ideas though.