#structured allocations

[mentalisttraceur-software]

execve(2): insecure by default

a rant that ended up flowing into "structured privileges"

Thinking about the execve(2) interface of UNIX, particularly with elevated privileges - especially in combination with the UNIX philosophy of little tools that do small jobs well.

This generalizes, actually - the same ideas of privilege segregation could apply within a process if languages and runtimes took advantage of modern kernels' support for it - at least in Linux, where processes and threads are basically the same kernel primitive, with just a few configuration differences.

Anyway, it bothers me that the default behavior is that if I start a root program, everything it executes is also root. In some sense, the ideal default for a program with a privileged effective UID and an unprivileged real ID is that the execve system call drops privileges - and if you want to keep privileges, that should be an explicit flag.

Even more ideally, this wouldn't be a flag that you, as the program with privileged effective UID or effective capability set or whatever, get to just set however you want - this should be some sort of object, like a file descriptor or a 128-bit random key or a pointer into read-only mapped memory, which is given to you by the caller who gave you elevated privileges. So your options are either "drop privileges" or "keep any privileges that your caller allowed you to keep" - notably absent from your options is an unconditional "keep privileges".

Of course, one problem here is that at some levels of abstraction, forking another process should be an implementation detail - when I call a program as root, I shouldn't have to know "this program wants to fork a child", let alone details like which child programs, how many, how deep the process tree goes, and so on.

So execve isn't exactly the right boundary here, at least not always. But here are a couple examples where the execve boundary is user-facing and explicit, and is the right boundary:

Suppose I want to run a privileged `find` program - because it needs to look inside directories that only root can read, and then I want to run some un-privileged command per file path - the most secure thing, especially if I don't have time to audit the command's source and build and binary for problems, is to prefix my exec arguments for find with something like sudo -iu "$USER" so that the child process of find drops privileges back down to my user before running the command.

For another example, suppose I want to run something like fzf on a list of paths, and then I want fzf to use `bat` to preview those files. bat could need read-only root privileges if some of those files are only root-readable, but there's no great way to give those privileges to just bat instead of fzf - at best, I run sudo once before running fzf, sudo caches my credentials, and then I set the preview argument of fzf to include a sudo call. But this isn't friendly to building larger programs: if the fzf call is inside some larger script, that script now has to either unconditionally include that sudo call, or include it or not based on either a flag that is passed in or if it already has special privileges.

Going back to how this generalizes, this same problem happens with libraries - instead of calling into another program, you call into some library, but either way, you probably don't have time to audit the whole thing, and it often doesn't need all the elevated privileges that you have - if I've got code to parse YAML inside my process, those instructions don't need any privileges besides access to the input bytes and enough memory to return the parsed result, and yet I have to go out of my way to isolate them and drop privileges if I want to be safe from some exploitable parser bug.

Ideally, code should have to go out of its way to explicitly take privileges that it either needs or can optionally use, as a kind of parameter. The whole system, from the ground up, would be built with APIs which have a bias towards dropping privileges and which require every privilege to be passed in from higher up in the call tree. Then the path of least resistance aligns with security: if you're writing code which doesn't need privileges, you don't go out of your way to take them from the caller - if you need privileges to do something, you have no choice but to reveal it in the API.

The only wrinkle here is that people should be able to write middleware which doesn't know or care about privileges, but is transparent to them. The simplest solution is to do what Go did with its context type - force middleware to take that parameter, and pass it through just in case the thing it calls needs it. This is... better than privilege use being invisible, but it's still pretty bad, especially when we generalize it to a granular "permissions" object, since middleware would need an arbitrarily permissive type: instead of knowing if we're calling something that requires privileges, we are back to calling something that might use any of the privileges we fed into it, and we can't know without inspecting the middleware.

In languages with templates, the permissions could be expressed as a template parameter, and then it's at least clear that the middleware takes whatever permissions its callee requires - and someone higher up in the call stack is defining the callee, so they have the responsibility and knowledge of those permissions. But this still isn't really enough, that's just a nice way to make the type system transparently propagate information about elevated privileges to the places where a developer is most served by knowing it.

But at runtime, we need a distinction between a usable privilege, and an unusable "sealed" privilege which is just being passed through code from a higher caller to a transitive callee which has what they need to unseal it.

This has been on my mind for a couple years now, at least. The overarching theme here is that ideally software has a reified representation of all interesting privileges, which ideally is both visible in the type system and actually enforced at runtime, and that code should be forced to be explicit whenever it uses or passes privileges to do anything.

(I call this "structured privileges", and it's yet another special case of the general/abstract idea that unifies structured programming, structured concurrency, my structured preemption idea, and so on. If we fully generalize the concept, the most appropriate term is something like "structured capabilities", because it comes to encompass the ability to do anything that we might want to explicitly manage in some parts of code. More on that soon, hopefully.)

[mentalisttraceur-software]

Structured Stack Allocation

Imagine this weird approach to writing code for a moment. I will use C as an example because C has the fewest implicit memory allocations and is conceptually pretty close to what a real computer is doing with memory as it executes, but you can map this concept pretty easily to other languages:

you are unable to declare any local variables in a function

instead, all local variable declarations go in a struct definition, and

each function receives a pointer to that "local variables" struct as a parameter.

What happens if we do this? Well, if a function call needs stack space, then:

I as the caller know exactly how much stack space it will use - it's whatever `sizeof` on that struct returns.

The easiest way for me to give a function the stack space it needs is for me to create a local variable of that struct type in my function - which of course now has to go in my "local variables" struct.

If I am going to call multiple functions one after the other, I can combine all their "local variables" structs into a union.

So any given function has an accurate account, available at compile time, of how much stack space any call it does will need - technically it can see the full tree of possible stack depths.

`main` starts with a full nested tree of unions of "local variable" structs for the whole program.

If you have been writing complex code for embedded microcontrollers that go in medical devices keeping people alive or in spacecraft trying to land, you immediately see something huge here. If you ever wanted to be robust against the Linux out-of-memory killer, or to just fail fast if there won't be enough stack memory, you may have noticed it too.

We've been treating "stack" memory as effectively free and big enough at the language level since before C, long before languages with automatic memory management started also treating "heap" memory as effectively free and big enough. And that's usually fine - for most code, most of the time, those details are irrelevant concerns, and the code is better for being decoupled from them.

But sometimes it isn't free, and sometimes it's very important to know if it's big enough. Sometimes the exact amount of stack space you use is part of your API, or ought to be.

Note how if we just add a "grow the stack if possible and allowed" API, then

the "local variable" union tree can hold the minimum needed to even run stack space, and

spots in the code that want to gracefully handle a lack of stack space can use that API.

Note also how regular dynamic memory allocation gives you the same big-picture semantics as stack memory allocation that can fail, so you can - today - play with the concept as described so far.

Finally note how callers can predict and control stack usage even better if the "grow the stack if possible and allowed" API is paired with an API to reduce the "allowed" limit for all functions that you call, and so on leafwards on the call tree.

A tougher challenge is situations where the needed "local variable" space can be, especially without whole-program optimizations, impossible to know until runtime:

functions that take pointers to other functions to call - need to add the local variable space needs of the function being called and the function being pointed to, and

recursion, both direct and indirect, needs a multiplication of stack space.

Ultimately I think in this paradigm you have to handle these with the "grow the stack if possible and allowed" API, and this is a good thing for code where space cost of each function matters, just as in fixed-size arrays versus dynamic allocation, it is good when code whose relevant costs are not predictable before execution have to look different.

Of course, the above was just sketching out the idea manually in C. In a mature implementation:

there is no need to reveal the struct contents up the call stack and across interface boundaries - just a simple size of the needed space would do;

for separately compiled linkable code objects, we would want each function's current stack size requirement to be stored along with the function's machine code in a way that the linker and other code can access;

the idea of manually gathering up all your local variables in a struct and explicitly passing pointers to the space was just a way to easily see the concept - any compiler already figures out how much stack space it will need when it builds the function, it just needs to expose that information;

this can be zero overhead and zero change for most machine code - once the sum of the minimum required stack size is known, startup code can check if it can get enough space, and code that never asks for more than its minimum can run as normal;

that "grow stack if possible and allowed" API can be optimized to an integer comparison against the remaining limit.

And just like that, we have come up with a way of expressing call frame space as an optionally manually-managed resource at the source code level, and a reasonably efficient way to manage it at runtime - both of which bring this behavior and resource in line with the hierarchical orderly call tree structure of the whole program.