OSDev.org

mystran wrote: This is what I have too. As it is, after Hurd people tried to build their system over L4, they noticed that wasting the few cycles in IPC to do capability validation will translate into lots of overhead reduction in userspace. Hence, L4.sec, the status which I must confess I haven't followed really.

I'm not sure how it's going on either - there aren't many mentions of it on the L4 mailing lists, and no public source code release. I think I read that some people were trying to put Hurd on top of Coyotos, too...

As for copying capabilities, my capability move (no copies in general case) invalidates the capability from sender, by writing a single pointer, and saves the capability as part of the message (two pointers). So it's about as fast as sending two pointers, too.

My kernel isn't finished yet - I started it again and haven't really had time to work on it much - so I'm not sure if capability transfer will be moving or copying. Moving capabilities does look rather nice...

- as general: proven to be universal (as in equivalent in power to Turing/Lambda....)

The pi-calculus looks at first glance to be similar to a capability system (it has processes, which you can send across channels, and little else). I haven't had much of a chance to look at it, but I wonder if it could be useful...(for example, there's a type system for the pi-calculus which prevents deadlock, and I wonder if a similar thing might work in a capability system.)

One example that you don't mention, but which my system allows, is doing system virtualization with little extra effort: in my system every process gets one capability too ("master" capability), but this capability is used to access all kernel services as well.

So any process can implement proxies for kernel services, and start other processes (provided it's own master allows), so that running a virtual copy of the system under system is just a matter of writing a suitable server. The processes running within the virtualized system can't (theoretically) tell whether they are running in a virtual system, and still might have direct access to some subdirectory (or well, subnamespace) of the global namespace, avoiding overhead there.

Well, I did mention something similar:

nick8325 wrote:Other kernel resources also have capabilities. For example, to set the priority of a thread you'd need a capability for it. There could be capabilities for processes and memory regions and things like that, and capabilities for privileged things (such as a disable-interrupts capability). That means that the kernel can forget about security policies, too, and user mode can organise security of kernel things.

In fact, the only operation in my kernel is [tt]invoke[/tt], which sends to a capability and awaits a reply. For example, you can map memory by invoking a memory-region capability. So you can certainly virtualise everything by changing the capabilities

Now, ofcourse the principal problem is how to maintain the capability table, when the number of capabilities per process grows. But this is little different from maintaining a list of file descriptors in a Unix process...

Distributing the capabilities correctly at startup could be a bit tricky, too, although using name servers could make it a lot easier. I think EROS tried to solve this by adding orthogonal persistence, so there was never any need to start up

One thing I'm unsure about: should messaging be symmetric or asymmetric. If client/server model is assumed anyway, then would it make sense to support that directly, instead of a general P2P mechanism (which can't take some shortcuts).

In mine it's synchronous and somewhat asymmetric: normally (it depends on the particular capability) if you send a message to a capability, the server will get a reply-capability for the client. When the server sends to that capability, the client will wake up and the reply-capability will be destroyed. (Come to think of it, a reply-capability is more like a continuation than an object, like you mentioned above.)

Brendan wrote: Imagine I've got a single threaded "keyboard macro" utility. The keyboard driver/process can send a "key was pressed" message to it and the GUI can send a "set new keyboard shortcut" message to it, but the GUI can't send a "key was pressed" message and the keyboard driver can't send a "set new keyboard shortcut" message. In addition, if the keyboard driver/process is a PS/2 driver and has a seperate thread for handling the PS/2 mouse, then this second thread can't send anything (even though it's part of the same process). Also, all threads might be allowed to send a "who are you" message, and any kernel thread might be able to send some messages (shutdown, restart, etc).

Here's how I might do it:

The macro utility will create a key-press capability and a key-shortcut capability. It will accept "key pressed" messages from the first and "set a new keyboard shortcut" messages from the second. It will give those capabilities to its parent when it starts, or to some sort of service manager process that knows how to distribute the capabilities correctly. After that, it can forget about security: if it gets a message of the correct type on a capability, the sender must have the capability. It can just receive messages and act on them.

The system (e.g. some sort of service manager process) will arrange for the keyboard driver to get the key-press capability and the GUI to get the key-shortcut capability. Now the GUI and keyboard driver can only send the messages they should be allowed to (and nothing else can send messages, unless they've been sent a capability by the GUI or keyboard driver).

The overhead of this is low - in my kernel, 8 bytes for each capability for now.

As for the other parts you mentioned:

If the keyboard driver/process is a PS/2 driver and has a seperate thread for handling the PS/2 mouse, then this second thread can't send anything (even though it's part of the same process).

If the two threads are running in the same process, they'll be unprotected, so the mouse driver thread could just modify the keyboard driver thread if it really wanted to send keypresses. If two threads are authorised to access different things, they should be separate processes. (The two threads could have separate capability tables, but as they're unprotected I don't see the point.)

All threads might be allowed to send a "who are you" message.

If a process doesn't have a capability for the macro utility, it won't be able to address it - it won't even know it exists. So it should have no need to send a "who are you" message. Any processes that should be allowed to send a message like that should have a capability for it. (I suppose you could have a process-tree capability that you could use to traverse the process tree from some root.)

Any kernel thread might be able to send some messages (shutdown, restart, etc).

Just add another capability. If every process is meant to respond to these messages, perhaps the kernel can make a capability automatically when the process starts.

mystran wrote: Specifically, you do NOT have capability system (you just have a fine-grained ACL, and yes, I'm ignoring some complications) if a process tells what service it wants to access, and system then checks whether this is allowed. In capability system, the process tells which capability it wants to use, and the ownership of the capability (which names the actual resouce) automatically implies access.

I don't think Brendan ever claimed to have a capability system, though

EDIT: mind you, your explanation is very good, certainly better than mine.

Does the IPC system in Singularity qualify as a capability system? If each "resource" (managed by some other server process) can only be used by invoking it via a channel endpoint, then are the endpoints themselves capabilities?

Colonel Kernel wrote: Does the IPC system in Singularity qualify as a capability system? If each "resource" (managed by some other server process) can only be used by invoking it via a channel endpoint, then are the endpoints themselves capabilities?

It's hard to say for sure, because I'm not familiar with Singularity (I really should find out more about it one of these days). But it seems that you can send endpoints as part of messages, so it looks at first sight like endpoints are capabilities.

Whether channel endpoints qualify as capabilities depends mainly on whether you can get channel endpoints by means other than through other endpoints.

But actually, since Singularity verifies all (untrusted) code to be typesafe, this is already a capability system in itself: typesafe, unforgeable object references are sufficient to maintain most definititions for capabilities.

As long as Singularity doesn't provide any loopholes, it trivially gets capability security for free, simply by mandating a typesafe language.

mystran wrote:Whether channel endpoints qualify as capabilities depends mainly on whether you can get channel endpoints by means other than through other endpoints.

No, you can't, at least not at run-time. One of the papers mentioned how the administrator can configure applications to start with a certain set of endpoints already available (e.g. -- to the name server), but after that the only way to get endpoints is from other endpoints.

But actually, since Singularity verifies all (untrusted) code to be typesafe, this is already a capability system in itself: typesafe, unforgeable object references are sufficient to maintain most definititions for capabilities.

As long as Singularity doesn't provide any loopholes, it trivially gets capability security for free, simply by mandating a typesafe language.

I see what you mean, but isn't it the cross-process nature of channel endpoints that make them capabilities? In other words, what does it mean to have capabilities that allow you to do things within your own process? Can't you do those things anyway (as long as you don't violate type safety of course)...?

Or are you just examining the not-so-useful degenerate case of the definition of "capabilities"?

(I really should find out more about it one of these days)

I highly recommend that research paper I linked to (Language-based Support for Reliable Message Passing). Their IPC system is quite brilliant IMO -- especially the way they use type-safe contracts with state machines to guarantee that no process can ever try to send into a full message queue. Static program analysis is very powerful!

Colonel Kernel wrote: I highly recommend that research paper I linked to (Language-based Support for Reliable Message Passing). Their IPC system is quite brilliant IMO -- especially the way they use type-safe contracts with state machines to guarantee that no process can ever try to send into a full message queue.

OK. I'm in the middle of exams at the moment but once they've finished I'll have a good read of it

Static program analysis is very powerful!

It certainly is - some of the things people do with static type systems are crazy (static checking of x86 assembly language, types which can specify pre- and postconditions (using dependent types) (e.g. "a function of this type takes a list of data and returns a sorted list of that data", with the compiler only accepting correct sorting functions), region-based memory management to give less need for a garbage collector, ...). But there's a lot of it I don't yet understand

Colonel Kernel wrote: I see what you mean, but isn't it the cross-process nature of channel endpoints that make them capabilities? In other words, what does it mean to have capabilities that allow you to do things within your own process? Can't you do those things anyway (as long as you don't violate type safety of course)...?

I guess that depends on whether you think of capabilities as necessarily remote typesafe pointers, or possibly remote typesafe pointers. I prefer the latter view.. in which case local typesafe pointers are just a special case of more general case of possibly-remote capabilities. (I hate the word capabilities btw)

If OTOH you choose not to think of local typesafe pointers as capabilities, then you can say that a system with mandated typesafety doesn't need capabilities.

In fact, local procedure (or method) call is similarly just a special case of synchronous IPC invocation, just like synchronous IPC invocation is really just a special case of asynchronous IPC invocation.

I highly recommend that research paper I linked to (Language-based Support for Reliable Message Passing). Their IPC system is quite brilliant IMO -- especially the way they use type-safe contracts with state machines to guarantee that no process can ever try to send into a full message queue. Static program analysis is very powerful!

Yeah well, theoretically. The trouble with static analysis that it needs the program to be static. This basicly means no dynamic linking or plugin loading, no clever just in time compiling, no reflection, no dynamic discovery... in short, it does reduce practical positive hacking potential as well. Interesting nontheless.

It is also pretty interesting, that if you take a sealed (as in all code known) program in dynamic language (say Lisp?) you could still do static analysis for example to get rid of all implicit runtime checks, by first doing type inference to convert it into a statically typed language, and then checking that whenever types are mixed, they are explicitly dispatched.

mystran wrote:Yeah well, theoretically. The trouble with static analysis that it needs the program to be static. This basicly means no dynamic linking or plugin loading,

IMO dynamic linking is a hack anyway. It's a way to extend applications that doesn't incur the cost of address space switching at run-time. It's also complex and a source of many bugs and security holes (ActiveX anyone?)

Plug-ins should run in separate processes. This may be too expensive when using separate address spaces, but in Singularity there are no separate address spaces thanks to... static analysis!

I won't miss dynamic linking.

no clever just in time compiling,

Do you mean JIT in the .NET/Java sense, or do you mean run-time code generation?

I think JIT is a nice idea for today's systems, since they allow for a certain amount of optimization, but not nearly as much as whole-program optimization on a "sealed" program. Again, I won't miss it.

For code generation, where is this most used today? From my own experience, I can think of two examples from .NET: compiled regular expressions, and custom serializers. In the former case, you can use the regex interpreter instead with a slight performance hit, or someone could come up with a regex pre-compiler similar in spirit to lex or flex. In the latter case, again I think pre-compiling is the answer (I believe this is how XML serialization works in Java when you use XDoclet... take that with a grain of salt since I'm no Java expert).

no reflection, no dynamic discovery...

This is a harder one to overcome, although without dynamic code generation (e.g. -- the regex example above), there is less reason to use reflection.

Part of the Singularity project includes work on "compile-time reflection", basically a preprocessor-like extension to their Spec# language. This is already the direction that C++ is moving in with its template metaprogramming and traits classes. I believe that ultimately, the same class of problems can be solved with static tools, just at a different time (compile time instead of run-time).

in short, it does reduce practical positive hacking potential as well. Interesting nontheless.

For all the reasons I've listed, I believe the trade-off is well worth it.

It is also pretty interesting, that if you take a sealed (as in all code known) program in dynamic language (say Lisp?) you could still do static analysis for example to get rid of all implicit runtime checks, by first doing type inference to convert it into a statically typed language, and then checking that whenever types are mixed, they are explicitly dispatched.

This is one of the reasons why Singularity is so fast.

Colonel Kernel wrote: Do you mean JIT in the .NET/Java sense, or do you mean run-time code generation?

I think JIT is a nice idea for today's systems, since they allow for a certain amount of optimization, but not nearly as much as whole-program optimization on a "sealed" program. Again, I won't miss it.

I was mainly thinking of "scripting" languages...

For code generation, where is this most used today? From my own experience, I can think of two examples from .NET: compiled regular expressions, and custom serializers. In the former case, you can use the regex interpreter instead with a slight performance hit, or someone could come up with a regex pre-compiler similar in spirit to lex or flex.

Well, regex is just one example of language you might want to compile on the fly. Ofcourse you still could compile your regular expression or your script into a separate process, and convert the compiled scripting languages API into message protocol.

Ofcourse, if you do this, you lose much of the benefits of static analysis.

Anyway: why bother with processes at all? Why not instead simply have typesafe memory space, where new code can be installed by writing it into a suitable buffer, and then asking the system verifier to give you a pointer to callable, verified version of the code.

Even if you could only have bytecode verified, if the system had even half-decent bytecode->nativecode conversion, you could still do interesting special purpose on-the-fly code generation.

This is a harder one to overcome, although without dynamic code generation (e.g. -- the regex example above), there is less reason to use reflection.

Ofcourse all these things can be rebuilt (assuming Turing completeness) with one or more level of indirection, but we don't wanna trade hardware protection into software interpretation, do we?

Part of the Singularity project includes work on "compile-time reflection", basically a preprocessor-like extension to their Spec# language. This is already the direction that C++ is moving in with its template metaprogramming and traits classes. I believe that ultimately, the same class of problems can be solved with static tools, just at a different time (compile time instead of run-time).

Well, the LEAST interesting part of Singularity IMHO is what they are doing with their C# derivative. While C# isn't totally bad language, it's still a continuation of the imperative tradition of language design. There's much more interesting work on metaprogramming done with certain functional languages, from Scheme to ML to Haskell (and others, ofcourse).

Lisp has had defmacro since ages ago, and much work has gone into trying to make something of (almost?) equal power, but without some of the problems that make it hard to reason about, like unintentional variable capture or lack of any sane model for typing whatsoever (with defmacro there's no way to do typing without doing macro expansion first).

And I admit, that much of what you would use reflection in existing languages, is indeed solved by a proper metaprogramming model.

mystran wrote:Anyway: why bother with processes at all? Why not instead simply have typesafe memory space, where new code can be installed by writing it into a suitable buffer, and then asking the system verifier to give you a pointer to callable, verified version of the code.

With this "typesafe memory space", are you assuming dynamic code loading again? Otherwise, you'd still be mapping each app/driver/plug-in to its own "typesafe memory space", and suddenly "typesafe memory space" == process. I think we're probably talking about the same thing. Processes in Singularity need not (and usually do not) live in separate address spaces.

Actually I had a single space in mind, with dynamic code loading, yes, but with some restrictions on how blocks of code loaded at separate times can interact with each other.

I guess you could call them processes, though.

In any case, many of the difficulties of static analysis disappear even in presence of dynamic code loading, if we get rid of any implicitly shared namespaces, including global environment, so called "static members" in classes, and anything else that is traditionally "per-process".

You still have to do some typechecking at either load or run time for whatever interface is used between such blocks, and you can't do global optimizations over compilation blocks easily, but .. well...

I guess what I'm trying to say is that I think that the restriction of starting a process at a time would go away, if we'd get rid of any of the things that define a process.

Without per-process resources, there isn't any need to prove anything about use of those resources, and hence process boundaries aren't important anymore..

But well.. just thinking here..