Requirements for a restricted execution runtime
I don't care what the language is, just please someone give me a runtime with these properties:
- Namespace restriction. Encapsulation. Capabilities. Whatever: the code should only be able to do what I say it can do.
- CPU timeslice restriction: Either I should be able to run some code for so long, pause it, and then resume it where it left off, or I should be able to run some code asynchronously, giving it 1/Nth CPU time.
- Memory allocation restrictions: this user's code should only be able to allocate up to N megabytes.
- Efficient at rather high scales: I should be able to run at least 500, maybe 1000 completely isolated functions concurrently. If all they're doing is sleep()ing, then this shouldn't put the host under heavy load.
- Some simple way to expose new, audited functions. This is pretty easy. If it can't run in a Python process and allow Python functions to be exposed to it, then I can at least run it in a separate process with method invocations going over a trivial RPC protocol.
- A decent set of secure built-in operations, but nothing really fancy. People are going to be interfacing with my API and nothing else, so they won't need a hugely rich core language API. It does need to be secure, though: large exponentiation should either be disallowed or interruptible, for example.
- Secure, ok? For example, don't talk to me about Python (as implemented by CPython). I have very little trust for any restricted execution system that's tacked onto an existing complex runtime.
In case you need some context for these requirements to make sense, think LambdaMOO or Second Life. Any user can upload code to run with their rights; it can manipulate the world through an audited "trusted" API. The code isn't allowed to interfere with the host system or other users' code. Another possible application is a wiki which allows people to upload code to be executed when a page is viewed.
Here's the list of things I've considered:
- PLT looks damned close with its sandbox library, but its execution limitation is in terms of wall-clock seconds, not CPU seconds, and it's not continuable.
- Monte could definitely do it some day, if its development remains steady.
- Lua... well, can Lua do it? I'd love it if someone would actually make a point on this.
- Haskell might be able to do it. Haskell can do anything, it seems. (I think I saw some code once which somehow implemented continuations in Haskell, for Haskell. Without being a Haskell runtime or compiler. What? I don't know.) The problem is it's inscrutable to me. I'd love it if someone commented about this.
- Javascript? Is there actually a usable standalone implementation of Javascript? Which of these properties does it have?
- PyPy with the sandbox translation option. It's very cool, but I'm not sure it's usable at the 1000 node scale, because I can't see a way to run multiple isolated interpreters within one process. It also misses things like CPU timeslice restriction and memory allocation restriction, as far as I can tell.
32 comments:
Check out PyPy... Search Google for "pypy sandbox"
anonymous: Hi, I'm radix on the #pypy channel on freenode :-)
I've been following PyPy for a long time. I'm familiar with the sandbox feature.
Although I hate to suggest it (I've tried to use it before, it ended badly) Lua fulfills many of those requirements.
It doesn't do cpu/memory so far as I know (although it may by now), but implementing new functions is easy and security is also easy: They don't get any "evil" functions except what you define for them, so they can't do any trickery (like you can in python) to get a real handle to os.unlink.
Yep, Lua indeed can do pretty much all of these tasks. CPU and memory limiting is possible too, and it's not hard. I have reasons to believe it's a good bet for what you want. ;-)
We can discuss it in more detail at some point, maybe while drinking some of that beer.
hi,
check out tinypy for something that aims to go where what you want.
A GSOC project aims to make it more secure, and it has been designed to be used for almost exactly your requirements.
However it currently isn't there yet - but aims to get there soon (6-12 months I'd guess).
The code is quite tiny(80KB and shrinking) - so it should be possible to audit it much more easily.
It is possible to have multiple VM's in one process.
It currently uses I think < 80KB of memory... some people are getting it running on embedded hardware, so it is quite small.
It compiles with small a libc - like uClibc... and I think no libc.
Have a look at: ulimit -a
For some OS level restrictions. You need to combine OS level restrictions, as well as language level restrictions. Including max cpu time, max memory, file descriptors etc. This is for *nix (*bsd, osx, linux) etc
I don't think it's possible to do what you want without OS level restrictions, open source, a small code base, a long period of peer review, and something designed from the beginning with this use case in mind.
Problem with tinypy is that it's still python-like: i.e., no encapsulation.
illume: The problem with relying on OS-level restrictions such as ulimit is with point #4. ulimit is per-process; that means I need a separate process for each isolated procedure. That's not going to scale up very much.
I'm not holding my breath for tinypy.
E? http://erights.org/
Allen short@
Can you please explain what you mean about encapsulation?
@christopher armstrong
Some of your assumptions about OS level processes are wrong.
Note, that it is possible to have OS processes that take up 8-12KB of ram each. Even 4KB I think... but you can't do much with that much ram.
Do some research into how linux does processes, and you'll be surprised at how many processes you can run. I have a webserver that uses over 10,000 separate OS level processes with ease. Especially if you don't use a big libc.
If your VM it doesn't use OS level protections - you fail to use a good layer of security available to you.
yeah, tinypy is a way off being useful for what you want - and may not every get there.
cheers,
Multiple solutions with haskell have been deployed. Lambabot, which runs on the #haskell irc channel on freenode does this natively in Haskell (http://www.haskell.org/haskellwiki/Lambdabot). Haskell is also the basis for Geordi (http://www.xs4all.nl/~weegen/eelis/geordi/) which does this for c++. The geordi engine was extended for codepad (http://codepad.org/about).
Never mind, Chris explained to me he doesn't think he wants encapsulation. (I do, but never mind. ;)
jsled, E is pretty rad, but Java and Common Lisp are not the easiest platforms to integrate with, and the Java version at least is extremely slow.
DGD and ColdC/Genesis both fit these requirements very well. Both are very lamdamoo like. DGD license is a bit restrictive on commercial side, and ColdC documentation is a bit lacking. Both are very small and efficient however.
I think you should look at Erlang.
Try virtualized Linux.
Stable. More features and tools than any of the other stuff.
Hi, I started writing a response to the question of how continuations are implemented in Haskell. It doesn't really require any Haskell-specific features to do, but it does require first class, higher order functions.
It got way too long for this small comment box though, so I made it into an article on the Haskell wiki
If you don't like that explanation, there are others you can look up. Use the keywords "continuation monad".
On your larger question, Haskell can be made to work in that problem space, but it's not altogether trivial. In #haskell on irc.freenode.net (an IRC channel which I'd heartily recommend if you're interested in learning Haskell), we have a bot that evaluates arbitrary Haskell expressions. This is made quite a lot safer by Haskell's typesystem, which reflects computations that may have side effects as values of a completely separate type from those which don't. However, there are still quite a number of considerations needed to make execution of untrusted code work smoothly.
It would be good to tear a lot of the security considerations out of lambdabot/runplugs itself and put it back into libraries like hs-plugins and the GHC API that handle dynamically loading Haskell code.
Look at ColdFusion8 sandbox mode
Have you considered using the jvm? Some of the things you need are supported out of the box and the rest should be covered by JSR 121. Unfortunately I don't know wether anybody cared to implement JSR 121 yet...
Why not use the the capabilities of the OS for sandboxing, along with a 'worker process pool' (like you would for threads and in order to avoid the overheads of starting new processes)?
You could then use some form of rpc to marshall data / objects from your master process to the workers and back - and use any arbitrary language in the worker processes.
Bonus points for packaging it as a Python module...
Building it on top of (underneath?) Pyprocessing might be a good way to go.
Also, Brett's restricted execution patches for Python seem pretty solid. I wouldn't rule it out too hastily.
Another alternative might be Mono and the .NET AppDomain security model.
I've not used it myself (AppDomains for restricted execution that is - I've used Mono and hold it in high regard).
Hosting a virtualized Linux OS and exposing it via a Python module would also be very cool!
I don't have time to respond to each person's comment right now, but let me just make one point:
If you're going to suggest something, can you make a reasonable effort at indicating which of the requirements it supports? I don't think anybody has suggested something yet which I've never thought of before. Maybe I haven't considered something enough, but I've crafted these requirements rather specifically because I got tired of attempting secure execution with runtimes that really don't support it well. For example, maybe I'm wrong in my debate with illume about the scalability of unix processes, but I'm pretty damned certain that running a thousand virtual Linux images on one host is out of the question for the time being :-)
"I'm pretty damned certain that running a thousand virtual Linux images on one host is out of the question for the time being"
That would be daft. One virtual Linux should be enough...
If you are looking for embeddable language with most control, then some form of forth would probably be your best bet, either ficl forth or 4th in particular. They can potentially meet all 7 of your criteria but would require more work on side, forth is pretty minimal. Already used in Mucks in the form of MUF. Syntax will be pretty alien compared to most languages.
http://www.xs4all.nl/~thebeez/4tH/index.html
http://ficl.sourceforge.net/
If you haven't looked at it, still highly recommend ColdC. Meets all requirements potentially with the exception of 5) Python integration. Though RPC would be totally doable, and its pretty light on resources.
http://cold.org/coldc/
I think you're going to have a hard time completely fulfilling #1 and #7 without some sort of OS-level virtualization. I mean, somebody can say something's secure and that they've audited it, but I'd put my money on securing access at the kernel level rather than at some likely comparatively poorly audited library or framework or VM level.
The problem with OS-level virtualization, of course, is #4, but if you can get past that, it can easily, given a few tweaks or tools, satisfy all of your other requirements.
So, based on 5 minutes with Google (and my own past experiences with virtualization), I'd suggest looking at OpenVZ, which seems to have the lowest per-instance overhead of the Linux virtualization tools (they show a benchmark where they run 150 instances on a 768 meg machine, think using a micro-distro running the Python VM, your interfacing/control app, and very little else), and Solaris Containers. In either of these cases you'll have to throw a lot of RAM at the problem to get the kind of scale you're talking about, but given the minefield that this problem represents, RAM at ~$32/gig is a cheap way to go.
A follow-up:
Take a look here, where it is claimed that OpenVZ scales linearly and you can get away with 320 OpenVZ instances on a 2 gig box (though given that the accompanying graph's response time zooms off to 4 secs, I'd figure maybe 500 instances in 4 gigs would have been a better ratio), and here, where OpenVZ is rigorously benchmarked.
Not sure if it meets those requirements, but you may want to take a peek at IO as well. (www.iolanguage.com)
I know some other people have addressed Lua, but here I'll break down exactly what it does and what it doesn't, as well as how to fit some of the requirements.
1. This is easy in Lua. You even have a choice for which standard libraries to expose to untrusted code. You can delete individual insecure functions from the standard libraries if necessary by simply removing them from the module table.
2. Gustavo Niemeyer seems to have a solution, but I don't know how.
3. This is easy in Lua. You can specify your own allocator function for the Lua code to use.
4. Lua is designed to be light-weight and fast. It's trivial to run multiple Lua interpreters because all of the interpreter globals are stored in a struct, as opposed to global variables like in Python.
5. It's easy to write your own functions in C and expose them to the embedded Lua environment.
6. Lua has a decent core library, and you can remove builtin functions or replace them with your own. You could limit large exponents, for example, by replacing the 'math.pow' library function with a version that checked for the size of the exponent before starting.
7. Lua wasn't built from the ground up to be secure, but the runtime is fairly small.
I've used Lua for a couple of scripting projects before, and the C interface is very clean to work with. The C interface is stack-based, which means that you don't have to worry about memory management but the C code can be hard to read. I haven't looked very deep into security issues for Lua, but I would recommend it for your project.
(t i m m a x w) -at- (g m a i l . c o m)
@tim: Thanks very much! Very informative comment.
Basically, Gustavo's suggestion amounts to using the Debugging API to register a hook on each bytecode operation to check if too much CPU time has passed.
This assumes that there are no bytecodes which can take unbounded time (which aren't otherwise avoidable), but it's looking good so far.
By the way, @Cale: Thank you as well, that was a very helpful comment. It seems GHC lacks a bit on the CPU timeslicing thing, at least in that I can't think of a way to do it. Lambdabot takes advantage of rlimits. This demands process-level isolation, which as I've discussed earlier in the thread, I'm not happy with.
Basically, Lua is looking the best so far. I'm going to try it out for a while and see how far I get.
I have been looking for a solution to a similar problem (but in a slightly different context to judge by your examples). TCL is almost there.
It does 1,4,6 and 7 using safe interpreters. You can control and redefine what commands are exposed.
5 can be done with Minotaur (http://www.equi4.com/minotaur/minotaur.html).
2 and 3 are more difficult but you should be able to implement at least an inexact solution.
Yeah, GHC is not suitable due to the way it decides when to run the schedular: it considers this only when allocating memory from the heap. If it is in a tight loop that does not allocate, no thread switches occur. In the past, this had usually only happened with code that was just plain wrong, but with improvements in optimization technology (whether in GHC itself or in libraries) this is becoming more common in useful code.
I think Lua does pretty much everything you need. We picked it for that reason for one of our projects. It can be embedded in Python to give restricted execution capabilities to Python.
It's a real shame that Python doesn't offer this capability.
I hope you haven't already considered it, because I'd hate to waste your time, but Spider Monkey, the Mozilla JavaScript engine looks like it might do what you need.
I haven't used it myself, but from what I've read it should be pretty secure (don't know about performance though).
Specifically, its designed with untrusted code in mind. It only exposes the objects and functions you allow (and some core JS stuff). It also provides the means to enforce your own arbitraty security policies through a callback mechanism.
Post a Comment