Some interesting responses came out of a previous post asking how to
make a safe sublanguage that could be made available to a an untrusted
user.
I would like to continue with a question in the same vein, but with
slightly more clarified goals.
I want a CLish language that has the following properties.
1. The capabilities that the CL-sublanguage has should be controlled
by restricting and extending the environment of the user as needed. A
more detailed description of of what I'm thinking of is given in "A
Security Kernel Based on the Lambda-Calculus" by Jonathan Rees.
2. Time and Space given to the user should be limited. By this I mean
that there would be strict bounds on the amount of time over which the
code would be executed, and the amount of consing that would be
allowed.
The suggestions that were given in the previous thread (as I read it)
for creating a safe sub-language were as follows.
1. Create an interpreter.
Of course this can be made to work with all of the above requirements,
but it may end up being a fairly extensive project. The time issue is
can be solved fairly easily by introducing threads to the interpreter
and having a special scheduler that does checkup. Someone also
mentioned only allowing programs that can be shown to halt. This is
really more restictive then I would like as it rejects many programs
which may in fact halt. However the solution to the consing problem
seems extremely difficult to solve.
2. Modify an existing lisp, (probably by making a modified reader?)
This is also tricky. It probably can't be done portably (as far as I
can tell) in that one would need to make use of threads. Also the
situation with consing looks bad here.
Is there some way that the space problem can be delt with?
Additionally I don't care to much about the issue of portability, so
I'm also interested in platform specific solutions.
Gavin Mendel-Gleason wrote:
> 2. Time and Space given to the user should be limited. By this I mean
> that there would be strict bounds on the amount of time over which the
> code would be executed, and the amount of consing that would be
> allowed.
You should read about Orbitz, the air travel ticket search engine. It
had limits on both the time and space. Consing was from a preallocated
pool, with no GC. Exhausting the pool, or time limits, caused
termination of the search. I saw no details of how this was done, sorry.
I imagine the cons pool thing is pretty easy, when you're actually
looking at the allocator code in your favourite Lisp's source code.
> The suggestions that were given in the previous thread (as I read it)
> for creating a safe sub-language were as follows.
I still think the code walker which tests that all referenced functions
come from a list of those allowed is the way to go.
--
Cameron MacKinnon
Toronto, Canada
From: Christopher C. Stacy
Subject: Re: Capabilities and sandboxed sublanguages.
Date:
Message-ID: <ullljp8mt.fsf@news.dtpq.com>
>>>>> On Mon, 29 Mar 2004 17:19:44 -0500, Cameron MacKinnon ("Cameron") writes:
Cameron> Exhausting the pool, or time limits, caused termination of
Cameron> the search. I saw no details of how this was done, sorry.
You do time limits the same way in Lisp as in any other language --
you can timeout things using the multiprocessing timers built into
most implementations, or you could just strategically place calls to
check in your own functions. Storage limits are done by writing
weird obsessive code that does not cons, and managing resource pools
instead. When you ask for an object from the pool, you also tell it
who you are or whatever, and it decides whether to give you one or
return NIL or signal or whatever. No mysteries.
·····@yahoo.com (Gavin Mendel-Gleason) writes:
> 1. Create an interpreter.
>
> Of course this can be made to work with all of the above requirements,
> but it may end up being a fairly extensive project.
Seriously, try it. The reason that interpreters are textbook examples
all over the place, is that they're really easy to write.
For time issues, just set a timer. For space issues, use a GC hook.
In SBCL, you could use something like this:
(defun eval-user-code (form)
"Return the result(s) of evaluating FORM, or +error+ if time/space
limits are exceeded."
(labels ((quit () (return-from eval-user-code +error+)))
(setf (sb-ext:bytes-consed-between-gcs) *user-space-limit*)
(let ((sb-ext:*after-gc-hooks*
(append sb-ext:*after-gc-hooks* (list #'quit))))
(sb-ext:with-timeout *user-time-limit*
(return-from eval-user-code (user-eval form)))
(quit))))
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
From: Marco Baringer
Subject: Re: Capabilities and sandboxed sublanguages.
Date:
Message-ID: <m2d66uzriw.fsf@bese.it>
·····@yahoo.com (Gavin Mendel-Gleason) writes:
> 1. Create an interpreter.
really your only option.
> Of course this can be made to work with all of the above requirements,
> but it may end up being a fairly extensive project. The time issue is
> can be solved fairly easily by introducing threads to the interpreter
> and having a special scheduler that does checkup. Someone also
> mentioned only allowing programs that can be shown to halt. This is
> really more restictive then I would like as it rejects many programs
> which may in fact halt. However the solution to the consing problem
> seems extremely difficult to solve.
The "time" issue:
cps transform it. add trampolining. pogo stick it 'till you want to
stop.
The "space" issue:
At some point you're going to have to define each and every function
which can be called and at what level of safety it can be called. when
you do this just annotate how much memory it uses. then keep track of
who called what. This would even allow, for example, limits on number
of objects (and of which type), number of lists, special functions
without these limits, etc.
The "someone could manage to get around it" issue:
yup. they'll just attach gdb (rooting your box if neccessary) and
start poking around memory. get over it.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen