![Spritely's Oaken mascot]()
Hi! I’m Daphne Preston-Kendal! You may remember me from such programming languages as the Revised⁷ Report on the Algorithmic Language Scheme. In this guest post, I’m going to explain the work I’m doing for Spritely, funded by NLnet: developing a new secure Scheme sublanguage for running untrusted code, like modifications to an existing app, in a safe way!
Usually, loading some random third-party code into your program is considered a security risk. Games are probably the most popular category of app these days where it’s normal for them to be moddable by adding more code, but we can see what a security disaster this is. Hardly a week goes by without yet another story of some rascal sharing a Minecraft mod pack on a forum or uploading a mod to the Steam Workshop which, in reality, exists to steal browser cookies or passwords.
If fun things like games can’t stop malicious mods, what hope do we have to build more serious moddable apps which get deployed on major server systems? What if a malicious mod got onto servers with sensitive data about thousands or millions of people?
Obviously, though, not all code is evil: probably most code isn’t, at least not deliberately. Do we really have to throw out the entire idea of running third-party modifications to our software just because some small amount of it might do bad stuff?
What code can you trust?
Here’s a pop quiz! What potential security problems could the following Scheme code cause? (Assume that we are working on a fully-conformant implementation of the R6RS, and this is evaluated with just the (rnrs base (6)) library imported.)
(lambda (x) (+ x 1))
Go ahead – it’s not a trick question!
The answer, obviously, is none! Evaluating this expression can’t access any system resources; once evaluated, you get a procedure, and the worst thing that can happen then is that someone gives it something that’s not a number (which will just safely raise an exception). This code will never steal your bank account information, eat all the cheese in your fridge, cause demons to fly out of your nose, etc.
So obviously, we can trust some code. For a simple procedure like this, we can audit it and see what it does! But for more complex code, it’s not reasonable to carefully read thousands of lines to try and find anything that looks nefarious. Attackers also keep finding new ways to hide malicious code from human auditors, from weird tricks with Unicode control characters to just putting loads of spaces at the start of lines so you have to scroll horizontally to see the evil code.
What if we could automatically audit code to be sure that it doesn’t do anything dodgy? Could that avoid human errors (like failing to notice a horizontal scrollbar)?
To do that, we have to go a level further and consider how we came to the conclusion that procedures like the one above are safe. How do we know? Well, + is a pure function: it takes some input value and returns a new, completely different output value. It doesn’t change anything about the input value: if you call ((lambda (x) (+ x 1)) sensitive-number), the value of sensitive-number itself won’t have changed when the add-one procedure is done with it. It doesn’t open any files or connect to any other remote computers, so your sensitive-number won’t be leaked to any bad guys. Also, it doesn’t allocate any memory or loop. Even a pure-functional program can do that – but at scale, that causes resource exhaustion, which could make an important service inaccessible until the tied-up resources are released. Well, we can treat any pure functional program as safe, so pretty much everything in the (rnrs base (6)) library is okay – and maybe when we run it we’ll be sure to watch it to make sure it doesn’t use too many CPU cycles.
So we’ve got our first idea – but, sorry, I’ve gotta interrupt this blog post now because Christine just sent me some code she thinks I should put in my next program. It looks pretty nifty – it’s a square root procedure written in just Scheme! Hey, you know what, let’s take a look together:
(library (dustyweb square-root)
(export square-root)
Looks good so far!
(import (rnrs base (6))
(rnrs io ports (6)))
Uh-oh. Why does a square root procedure need port I/O? Square-root should be a pure function, but that library gives Christine’s code complete access to my filesystem. What’s she up to? Is she trying to read my private data? Or has thinking about all those evil Minecraft mods and how to detect them made me paranoid??
(define (close-enough? guess x)
(< (abs (- (* guess guess) x)) 0.01))
(define (improve-guess guess x)
(/ (+ guess (/ x guess))
2))
(define (square-root x)
(call-with-port
(open-file-output-port "sqrt-log.txt"
(file-options no-fail)
(buffer-mode line)
(native-transcoder))
(lambda (log-port)
(put-string log-port "finding square root of: ")
(put-datum log-port x)
(put-char log-port #\newline)
(let loop ((guess 1.0))
(put-string log-port "guess: ")
(put-datum log-port guess)
(put-char log-port #\newline)
(cond ((close-enough? guess x)
(put-string log-port "good enough, ship it!\n")
guess)
(else
(loop (improve-guess guess x)))))))))
Well, actually, that looks perfectly innocent as far as uses of the filesystem go. Christine probably wanted to log the guesses so she could debug her code. Still, if I already have any file called sqrt-log.txt, this will inadvertently delete and write over it. Also, I wanted to use this procedure in a program to work out how much perspective distortion I should expect with various lenses on some of the weird and wacky film formats I photograph on. (The amount of perspective distortion is proportional to a function of the difference between the focal length and the corner-to-corner diagonal of the image plane.) but what weird and wacky film formats I use is my own private business, and I don’t necessarily want it sent to Christine’s server: imagine if instead of (rnrs io ports (6)), she’d imported (srfi :106) (socket library) and sent all that data off to her server to spy on the square roots I’m calculating! I can’t just trust any code Christine sends me.
Hmm. Maybe we’ve learned something here, though – something we can use to improve our intuition about what code we can trust in general. I’m fine with recording what square roots I take, and what steps were taken to calculate them – on my own computer. Can we reformulate Christine’s library so that she can still have her debugging information, but it still only imports the (rnrs base (6)) library? Then we know we can trust her code just by looking at the import list!
How about something like this?
(library (dustyweb square-root)
(export square-root)
(import (rnrs base (6)))
(define (close-enough? guess x)
(< (abs (- (* guess guess) x)) 0.01))
(define (improve-guess guess x)
(/ (+ guess (/ x guess))
2))
(define (square-root x debug-log)
(debug-log "finding square root of" x)
(let loop ((guess 1.0))
(debug-log "guess" guess)
(cond ((close-enough? guess x)
(debug-log "good enough, ship it!")
guess)
(else
(loop (improve-guess guess x)))))))
Now when I write my perspective-distortion program, I call square-root like this:
(square-root (+ (square image-width)
(square image-height))
ignore)
where ignore is a procedure I wrote and trust that accepts any number of arguments, does nothing with them, and returns nothing of interest. In other words, the logging calls do nothing for me because they’re not very interesting to me. Meanwhile, when Christine is debugging her program, she can write a debug-log procedure that looks like this:
(define (make-debug-log-procedure log-port)
(case-lambda
((message)
(put-string log-port message)
(put-char log-port #\newline))
((message value)
(put-string log-port message)
(put-string log-port ": ")
(put-datum log-port value)
(put-char log-port #\newline))))
(define debug-log (make-debug-log-procedure
(open-file-output-port "sqrt-log.txt"
(file-options no-fail)
(buffer-mode line)
(native-transcoder))))
What happened here? Square-root can still do I/O, but suddenly we’re able to trust it because we know that the library it’s in only has access to procedures we trust. In other words, we only have to look at that one line in the program to know that we can completely trust the whole program! But, somehow, it can still do the I/O for the debug log Christine wants. The reason is that when we call it, we explicitly give it the ability to do I/O in a limited way: we write code ourselves – code we trust to access libraries like (rnrs io ports (6)) or (srfi :106) – and pass in a procedure from outside that exposes the capabilities of those libraries in a specific, limited way. Even if I did want to log what square-root is doing, using Christine’s debug-log procedure would only let it write to one specific file, and in a very specific way. It couldn’t use that ability to start reading my browser cookies like it could if I gave it the full (rnrs io ports (6)) library. Even better, if you do want to get the log, you can change where it goes just by passing a different port to make-debug-log-procedure!
Make-debug-log-procedure uses a technique called closure so that its own argument, the log-port, is available to the debug-log procedure even though it isn’t an argument to it. (We say that the debug-log procedure is closed over the log-port variable – or more informally, that it’s closed over the port itself.) Once make-debug-log-procedure returns, the debug-log procedure it creates has access to that port and exposes it in a limited way, which means the (dustyweb square-root) library doesn’t need to import (rnrs io ports (6)) any more. But Christine can still use open-file-input-port when she writes a debugging procedure like make-debug-log-port, because she obviously trusts herself to use it responsibly. In fact, anyone who actually uses her library can trust themselves to access their own files.
It would still be nice to be able to use square-root as if it were a pure function, not having to pass in this ugly debug-log argument. That gives me an idea: could we close the whole library over a procedure like debug-log? That would mean Christine could also extend her library to include all sorts of useful functions, like cube roots or inverse square roots – all of them safely debug-logging away – and I would only need to pass in the debug-log argument once when I import her library.
Now we’ve actually arrived at a much better idea than trying to audit all the third-party code we might possibly want to use. Instead of doing that, we just make sure it only uses safe procedures or ones we’ve given it!
Unfortunately, neither R6RS nor R7RS Scheme provides the ability to make an entire library into a closure. But maybe we can design a system that does have this ability – that’s Oaken!
Taming libraries to stop them eating resources
In programming security research, this kind of trick of using language features to turn an unsafe library into a safer one is called ‘taming’. Like humans tamed wolves into dogs to stop them eating their sheep programmers can tame libraries to stop them providing access to the procedures that could create a security vulnerability.
I can go down to the pet shop and buy a dog and train it to recognize me as its owner. As its owner, I’m in charge and I can do all the things the dog isn’t allowed to do in my household – sleep on the human bed, eat food from the dinner table, dig holes in the garden, etc. In security terminology, this kind of general permission is called ‘ambient authority’. But, as a treat, I could let the dog do some of those things sometimes, but only when I allow it. The dog doesn’t get the ambient authority to do these things all of the time: it’s only allowed to do it in the way I let it and when I say so.
We are in charge of our own programs and our own computers. We get to do everything, but the code we pull in from some library should only be able to do things we allow it to do. We’ve seen how we could do this by closing those libraries over procedures giving more limited access to a resource, but we should really have a standard library for systematically controlling access to the resources which could cause security problems if evil code uses them in evil ways.
We’re not going to support every use case in the initial version of Oaken: full taming is a really hard problem. (Like any red-blooded programmer, I initially thought it was going to be easy, and then all the individual little difficulties slowly started to dawn on me. In fact, I still keep realizing new problems almost every day.) But we’ll provide some very basic tamings that should be good enough to start off with: the idea of Oaken is that the library system supports taming as a general concept, so more advanced controls can follow later.
Filesystem and network abuse
It should be obvious that giving untrusted code unrestricted read/write access to the whole computer filesystem is a bad idea. In combination with unrestricted ability to connect to other computers over the internet, it’s an even worse idea.
We already saw a simple idea for taming filesystem access in the square root example, but real-world libraries might legitimately want to create and read their own files to provide some useful functionality to the trusted code which uses those libraries.
We already have a real world example of how this could work. When you upload a file to a website in your browser, the web site can’t directly read the files on your computer. Instead, your browser, which does have that unrestricted filesystem access, pops up a file selection dialogue box and asks you to choose a file. The browser then makes that file available to the website by giving it a File object which it can use to read that file – and only that file. This pattern of passing limited access to some restricted resource to untrusted code is called the ‘powerbox pattern’.
Just as you give a website access to one file, with Oaken you can close a library over a version of the file-system access library which, for example, only gives access to one directory. That means the code could never go snooping outside that directory and steal or destroy information that doesn’t belong to it. Simple!
Unfortunately, file access is really tricky to fully tame. We can easily make it so that a tamed library can only access one directory on the disk, but it’s not so easy to stop that library from writing files in that directory which would eventually eat up all space on the drive. Ideally, you’d be able to limit how much disk space untrusted code can use and not just access to individual files. But that would require looking at what special support the operating system can give us and how to make use of the tools it has to restrict storage abuse, so full taming of filesystem access – beyond restricting code’s access to a single file or directory – is probably out of scope for the initial version of Oaken.
But what about network access? Should we instantiate each library a different time, passing it in multiple times, for each server and port it wants to access? That sounds a bit annoying. Maybe it would be better to use a different mechanism for powerboxing than the one the library system provides. I’ll be thinking a lot about this and trying to come up with a workable design!
Timing attacks
Another surprising source of security issues in apps comes just from giving programs access to a simple system clock. Timing attacks can let untrusted code find out information about what’s going on inside of trusted procedures they shouldn’t be able to extract information from, or see the inner workings of; or they can let two untrusted bits of code communicate with one another when they shouldn’t. Mark S. Miller, an influential researcher in the area of secure programming systems, talks about this as ‘prisoners tapping on the pipes’ – sending messages to one another in their cells with Morse code or whatever. You really do have to be careful to ensure that all potential back-channels for unwanted communication are closed off.
Preventing this particular kind of attack seems quite simple – there’s no real taming to be done. It’s just a matter of making sure a library only has access to the system clock if you explicitly give it access when you instantiate it, which is an all-or-nothing proposition – unlike carefully controlling which individual files or directories a procedure could access and how. But something I’ve already learned in planning this project is that if something looks simple, I probably haven’t thought about it enough yet, so maybe there are more problems lurking beneath the surface here.
Exhaustion attacks
It’s not only external resources like files, the network, or the system clock which can pose a security risk. The computer’s CPU and memory are all you need for another kind of attack: a denial of service. If you tie up all the computer’s memory and processor time with nonsense, you can make a service inaccessible to people who actually need to use it. Typically, attackers find some request they can make to a service that takes massively, disproportionately more resources for the service to respond to than it does for them to make the request.
What tools do you need for this kind of attack? Could we restrict those through the library system too? Unfortunately, that approach won’t work here. In fact, all you need to cause a denial-of-service attack is lambda, as in this example that’s often shown while explaining how the fixed-point combinator is derived:
((lambda (x) (x x)) (lambda (x) (x x)))
By conjuring up two procedures which call each other forever, this cute little Scheme expression will peg one of your CPUs until you find a way to stop it. This isn’t good! But this kind of vulnerability to resource-exhaustion attack can happen entirely by accident: just the other day I was hacking on a procedure and accidentally made it loop infinitely on some input.
It’s mathematically impossible to always detect this kind of bug in advance. Moreover, even if a program eventually stops looping (and there is a useful subset of programs whose halting behaviour is provable), it might still take too much CPU to return its result. (Even just a badly behaved regular expression implementation can make resource exhaustion attacks possible!) So the best we can do is put a limit on the amount of computation an untrusted procedure is allowed to do.
Guile already includes a little library called (ice-9 sandbox) which lets you call code with limits on how much time it can take and how much memory it can allocate. Unfortunately, (ice-9 sandbox) limits wall-clock time, not actual processor resources, which is not ideal. For example, wall-clock time includes time spent waiting for user input! You don’t want your procedure getting killed for DoSing the system when in fact it’s sitting there doing nothing while a hunt-and-peck typist is writing up their life story into a text box. Worse, there’s no way to powerbox time usage with (ice-9 sandbox).
But there might be a solution: engines! Engines are a Scheme idea introduced by Kent Dybvig and Bob Hieb. The basic concept is that the system runtime keeps track of how many units of computation (‘ticks’) have been executed, and when that number exceeds a certain limit (the amount of ‘fuel’ in the engine), it pauses execution and returns the unfinished task back to whoever started it. They can then decide whether to stop running the computation, or give it more fuel and carry on.
The ticks can be measured in any unit – with the right support from the OS, you could even make it actual CPU time – but Dybvig and Hieb suggest counting procedure calls. That works well in Scheme because, once you expand all your macros, everything you could do that might cause CPU exhaustion – in particular, looping – involves a procedure call.
The Guile manual also describes a few problems with the memory limiter in (ice-9 sandbox). For now, we’ll probably have to live with those and a few more, like the fact that it’s also not possible to powerbox memory usage. Guile is getting a new garbage collector soon, thanks to Andy Wingo’s sterling work on Whippet; as the migration from BDW to Whippet progresses, maybe it will become possible to fix some of these issues in future. But here also, many operating systems (cough Linux) make things difficult: we can’t really do anything about the kernel deciding that the Guile process has had quite enough memory for tonight and that it’s time to go home.
Capability attentuation
So far we’ve only considered one level of delegation of trust: you have your dog/program, and the dog/program is only allowed to sleep in the dog bed you gave it/use only the files you gave it. But in reality, software dependencies form a much more complex graph, and it should be possible for the things you trust in some limited way to place their trust in other things in even more limited ways.
Let’s say I have my program, and within it I gave your library access to a key-value store where it gets to store up to 100 MB of data in its own namespace. Your library might want to import some other library, giving it some smaller slice of that data in turn, like 10 MB, and its own subnamespace. So your library needs to be able to take the version of the library you gave it, which is closed over the limit of 100 MB and one namespace, and close it over a different limit and a different, subordinate namespace.
At the moment, I’m still in the early stages of designing the library system, and supporting this use case seems kind of hard! It’s easy to think about a one-level system where the main, trusted program gets to instantiate every (potentially untrusted) library with some fixed limitations. It’s a lot harder to design a system where it’s easy to start with an existing instantiated, untrusted library and impose even stricter limitations on it to create another library with the same interface but even tighter controls.
Onward
I’m looking forward to hacking on Oaken over the next couple of months! Oaken is one of the more intriguing parts of the Spritely Institute’s vision for decentralized internet infrastructure. Imagine spreadsheet macros that won’t make off with your sensitive financial data; imagine not just safe mods to existing games, but even something like the ability to send a whole new multiplayer game to your friends in a chat program, who could then just run it right in place on their computer with no security fears; imagine the Shepherd where each service ran in its own capability sandbox! Oaken will enable all of this by working alongside other Spritely projects like Hoot and Goblins.
Let a thousand Oaken forests bloom!
Further reading
The canonical paper on using Scheme variable scope for security is Jonathan Rees’s Ph.D. dissertation, ‘A Security Based on the Lambda Calculus’. That dissertation is a direct inspiration for Oaken, and Jonathan is advising me on the project.
As far as I know, the idea of closing modules over things, in the way procedures can be closed over things, comes from the Standard ML programming language. David MacQueen’s paper ‘Modules for Standard ML’ explains how it was designed. We’re not the first people to try adapting this idea for Scheme: the Scheme 48 module system, also designed by Jonathan Rees, worked this way. But Oaken will be the first such library system in Scheme specifically designed for security purposes, released for general use, and with a standard library for tamed access to important resources.
The E programming language pioneered many aspects of capability-based security within a programming language, and the Emaker library system is also an inspiration for Oaken. The same idea was proposed for JavaScript as FrozenRealms which evolved into Endo.
