If this is a core feature requirement, then as far as I know your only option is to change languages to something where you can rigidly sandbox. Your nearest option in programming space would be Perl and some variant of Safe (that's a CPAN module name). Otherwise, if you can live with a gentleman's agreement, you're fine. This may make the automatic-online-matchup really tricky, though.
Another option I was thinking about for this purpose is parsing the python to make sure they don't get up to anything fishy, but I have no idea how hard a Python parser would be. My guess is very.
Or we put them into separate proceses, as swolchok suggested.
If that was safe, it would have been bundled up into a module. This is a Frequently Asked Question for Python, and the answer is, you can't.
I thought of process separation, but it won't work. The best performance would be one persistent process that runs the cell computations, but it's too easy for Python code to find places to hide data persistently for communication above and beyond what you expect.
For example, would you have thought to block the following?
Python 2.4.3 (...)
Type "help", ...
>>> def f():
... f.i = f.i + 1
... print f.i
...
>>> f.i = 1
>>> f()
2
>>> f()
3
And mind you, that's one example, and not a very sophisticated one. If you're answer was "no", or indeed anything other than "duh, of course, I've known about that for years", then you don't stand a chance at the sophisticated stuff.
You can't fork at cell-run-time, because while a process couldn't write anything back out to the parent, it could still grovel over the parent's data space which could still be used to advantage, and depending on the rest of your code may still make an out-of-band channel available.
You could fork a process per cell before anything "incriminating" has been instantiated in the parent process, but that's got a lot of problems even on one machine (including the 32K process limit), let alone a hosted service, and you'd still end up with the possibility of a "cell history" being recorded that could be potentially exploited.
Python does not give you the necessary primitives to accomplish this task. I see three options: Live with it (a viable option except online), spawn one process per team and officially bless that level of communication (though it radically changes the nature of the game), or change languages.
To be honest, Python is going to cause you other problems on your online server too, such as the extreme difficulty you're going to face in isolating Python functions to a certain amount of CPU time. (Same problem, as long as the Python code cooperates it might be possible (and it might not really) but if it starts hostilely modifying the parent code you lose.) Other languages have support for that too.
Unfortunately, you're really bashing on Python's weaknesses here.
Forking and execing prevents this.
And will be uselessly slow, which is why I dismissed it with hardly any thought.
# time bash -c "for i in {1..1000}; do python -c '1'; done"
real 0m9.351s
user 0m6.439s
sys 0m2.868s
Probably for now the best solution would be to make this form of cheating a bit hard, and then living with it, and having provisions on the ladder server to erase all scores based on a cheating genome if it is detected.
And given that you are willing to live with that, Python is otherwise a pretty good language, very easy to pick up, etc. I love this in general, I'm explaining this so you don't end up burning time in a tarpit and instead use it to build something that will actually work. :)
If you sandboxed the Python process running agent code to limit the mischief to that particular process, that would go a pretty long way, and that sort of thing is certainly possible by restricting syscalls at the OS level.
I would wait to say PyPy has "perfect" sandboxing until it has been attacked for a while, though. CPython used to have a sandbox module, too. But at least PyPy has been designed with this use case in mind.
It might not be ready for prime-time in some very critical systems (like a web browser for example) but it's honestly probably good enough for this, especially in combination with process jailing as you suggest. I might consider trying to patch Cells up to use PyPy's sandbox instead of the non-solution currently implemented (I cried (okay, groaned) when I heard about it-- yeagh), when I have time, and if nobody else does it first. I'm a bit worried anything I write now would get lost or broken in the incoming tide of patches/changes anyway.
The main problems with using PyPy's sandboxing is probably with communication to/out of the sandbox, which is apparently problematic. I also anticipate some complaints about relying on PyPy in the first place, which is rather abnormal compared to using CPython-- using and relying on PyPy-specific features is pretty much unheard of.