Friday, March 6, 2009

Capabilities for Python?

I received an email recently from Mark Miller, quoting a post from Zooko to the cap-talk mailing list (which I do not read). Mark asked me to clarify my position about capabilities (in Python, presumably). Since the last thing I need is another mailing list subscription, I'm posting my clarification here. I'm sure that through the magic of search engines it will find its way to the relevant places.

In his post, Zooko seems to believe that I am hostile to the very idea of capabilities, and seems to draw a link between this assumed attitude and my experience with the use of password-based capabilities in Amoeba. This is odd for several reasons. First, the way I remember it, Amoeba's capabilities weren't based on passwords, but on one-way functions and random numbers (and secure Ethernet wall-sockets, which is perhaps why the idea didn't catch on :-). Second, I don't believe my experience with capabilities in Amoeba made a difference in how I think about capabilities being offered by some modern programming languages like E, or about the various proposals over the years to add capabilities to Python, perhaps starting with an old proposal by Ka-Ping Yee and Ben Laurie. (It would be better to think of this as a subtraction rather than an addition, since such proposals invariably end up limiting the user to a substantially reduced subset of Python. More about that below.)

But the biggest surprise to me is that people are reading so much in my words. I'm not the Pope! I'm a hacker who likes to think aloud about design problems. Often enough I get it wrong. If you think you disagree with me, or have a question about what I said, just respond in the forum where I post (e.g. python-dev or python-ideas, or this blog), but please don't go forwarding my messages to lists I don't read and speculate about them.

With that off my mind, and with the caveat that this entire post is thinking alound, let me try to expose some of my current thoughts about capabilities and Python.

Note that I'm trying to limit myself to Python. Languages specifically written to support capabilities exist (e.g. E) and may well become successful, though I expect they will have a hard time gaining popularity until they also sprout some other highly attractive features: most developers see security as a necessary evil.

This attitude, of course, is the reason why the idea of adding security features to an existing language keeps coming back: it's assumed to be much more likely to convince the "unwashed masses" to switch to a slightly different version of a language they already know, than to get them to even try (let alone adopt) a wholly new language. This argument not limited to security zealots of course. The same reasoning is common in the larger world of "language marketing": C++ made compatibility with C a principle overruling all others, Java chose to resemble C or C++ for ease of adoption, and it is well known that Larry Wall picked many of Perl's syntactic quirks because the initial target audience was already using sed and sh.

I'll be the first to admit that wasn't completely free of this attitude for Python's design, although I didn't do it with the intent of gaining popularity: whenever I borrowed from another language, I did so either because I recognized a good idea, or because I didn't think I had anything to add to current practice, but not because I was concerned about market share. (If I had been, I wouldn't have used indentation for grouping. :-)

Anyway, regardless of the merits of this idea, it keeps coming back. A recent incarnation is Mark Seaborn's CapPython. Skimming through this wiki page it seems that Mark is well aware of the limitations: the section labeled "problem areas" takes up more than half of the page. And the most recent discussion (which also triggered Zooko's post I believe) started with a blog post by Tav where he proposes (with my encouragement) some modest additions to CPython's existing restricted execution mode and challenges the world to break into it. In a follow-up post, Tav provides a better history of this topic than I could provide myself.

And yet, I remain extremely skeptical of this whole area. The various attacks on Tav's supervisor code show how incredibly subtle it is to write a secure supervisor. CPython's restricted execution model lets sandboxed (= untrusted) code call into the supervisor, where the supervisor's Python code runs with full permissions. In Tav's version, the sandbox is given access to the supervisor only through a small collection of function objects which the supervisor passes into the sandbox. Tav's proposed changes remove some introspection attributes from function and class objects that would otherwise give the sandboxed code access to data or functions that the supervisor is trying to hide from the sandbox. This basic idea works well and nobody has yet found a way to break out of the sandbox directly -- so far it looks like no other attributes need to be removed in order to secure the sandbox.

However, several attacks found non-obvious weaknesses in Tav's supervisor code itself: it is deceptively easy to trick the supervisor into calling seemingly safe built-in functions with arguments carefully crafted by the code inside the sandbox so as to make it reveal a secret. This uses an approach that was devised years ago by Samuele Pedroni to dispell doubt that restricted execution was unsafe in Python 2.2 and beyond.

Samuele's approach combines two properties of (C)Python: built-ins invoked by the supervisor run with the supervisor's permissions, and there are many places in Python where implicit conversions attempt to call various specially-named attributes on objects given to them. The sandboxed exploit defines a class with one of these "magic" attributes set to some built-in, and voila, the built-in is called with the supervisor's permissions. It takes some added cleverness to pass an interesting argument to the built-in and to get the result back, but it can be done: for details, see Tav's blog.

My worry about this approach is that a supervisor that provides a reasonably large subset of Python will have to implement some pretty complex functionality: for example, you'll have to support a secure way to import modules. My confidence in the security of the supervisor goes down exponentially as the its complexity goes up. In other words, while Tav may be able to evolve the toy supervisor in "safelite.py" into an impenetrable bastion after enough iterations of exploit-and-patch, I don't think this approach will converge in a realistic timeframe (e.g. decades) for a more fully-featured supervisor.

This lets me segue into another, perhaps more generic, concern with the idea of providing a secure subset of Python, whether it's based on restricted execution, capabilities, or restricting attribute references (like CapPython and Zope's RestrictedPython). Python's claim to fame comes largely from its standard library. People's proficiency with the language is not just measured by how well they can construct efficient algorithm implementations using lists and dicts: to a large extent it depends on how much of the standard library they master as well. Python's standard library is large compared to many other languages. Only Java seems to have more stuff that's assumed to be "always there" (except in certain embedded environments).

For a "secure" version of Python to succeed, it will need to support most of the standard library APIs. I'm distinguishing between the implementations and APIs here, for it is likely that many standard library modules use features of the language that aren't available by the secure subset under consideration. This doesn't have to be a show-stopper as long as an alternate implementation can be provided that uses only the secure subset.

Unfortunately, I expect that, due to a combination of factors, it will be impractical to provide a sufficiently large subset of the standard library for a sufficiently secure subset of Python. One problem is that Python, being a highly dynamic language, it supports introspection at many levels, including some implementation-specific levels, like access to bytecode in CPython, which has no equivalent in Jython, IronPython or other implementations. Because of the language's dynamic and introspective features, there is often no real distinction between a module's API and its implementation. While this is an occasional source of frustration for Python users (see e.g. the recent discussion about asyncore on python-dev), in most cases it works quite well, and often APIs can be simpler because of certain dynamic features of the language. For example, there are several ways that dynamic attribute lookup can enhance an API: automatic delegation is just one of the common patterns that it enables; command dispatch is another. All this leads me to think that a secure version of Python is unlikely to become complete enough to attract enough users to become viable. I'd be happy to be proven wrong, but it seems that the people most attracted to the idea are hoping that adding capabilities Python will somehow provide a shortcut to success. Unfortunately, I don't think it's a shortcut at all.

I should mention that I have some experience in this area: Google's App Engine (to which I currently contribute most of my time) provides a "secure" variant of Python that supports a subset of the standard library. I'm putting "secure" in scare quotes here, because App Engine's security needs are a bit different than those typically proposed by the capability community: an entire Python application is a single security domain, and security is provided by successively harder barriers at the C/Python boundary, the user/kernel boundary, and the virtual machine boundary. There is no support for secure communication between mutually distrusting processes, and the supervisor is implemented in C++ (crucial parts of it live in a different process).

In the App Engine case, the dialect of the Python language supported is completely identical to that implemented by CPython. The only differences are at the library level: you cannot write to the filesystem, you cannot create sockets or pipes, you cannot create threads or processes, and certain built-in modules that would support backdoors have been disabled (in a few cases, only the insecure APIs of a module have been disabled, retaining some useful APIs that are deemed safe). All these are eminently reasonable constraints given the goal of App Engine. And yet almost every one of these restrictions has caused severe pain for some of our users.

Securing App Engine has required a significant use of internal resources, and yet the result is still quite limiting. Now consider that App Engine's security model is much simpler than that preferred by capability enthusiasts: it's an all-or-nothing model that pretty much only protects Google from being attacked by rogue developers (though it also helps to prevent developers from attacking each other). Extrapolating, I expect that a serious capability-based Python would require much more effort to secure, and yet would place many more constraints on developers. It would have to have a very attractive "killer feature" to make developers want to use it...Link

Thursday, January 29, 2009

Detecting Cycles in a Directed Graph

I needed an algorithm for detecting cycles in a directed graph. I came up with the following. It's probably something straight from a textbook, but I couldn't find a textbook that had one, so I came up with this myself. I like the simplicity. I also like that there's a well-defined point in the algorithm where you can do any additional processing on each node for which you find that is not part of a cycle.

The function makes few assumptions about the representation of the graph; instead of a graph object, it takes in two function arguments that are called to describe the graph:
  • def NODES(): an iterable returning all nodes
  • def EDGES(node): an iterable returning all nodes reached via node's outgoing edges
In addition it takes a third function argument which is called once for each node:
  • def READY(node): called when we know node is not part of any cycles
The function returns None upon success, or a list containing the members of the first cycle found otherwise. Here's the algorithm:
def find_cycle(NODES, EDGES, READY):
todo = set(NODES())
while todo:
node = todo.pop()
stack = [node]
while stack:
top = stack[-1]
for node in EDGES(top):
if node in stack:
return stack[stack.index(node):]
if node in todo:
stack.append(node)
todo.remove(node)
break
else:
node = stack.pop()
READY(node)
return None
Discussion: The EDGES() function may be called multiple times for the same node, and the for loop does some duplicate work in that case. A straightforward fix for this inefficiency is to maintain a parallel stack of iterators that is pushed and popped at the same times at the main stack, and at all times contains iter(node). I'll leave that version as an excercise.

Update: Fixed a typo in the algorithm (EDGES(top)) and renamed all to todo.

Tuesday, January 13, 2009

The History of Python - Introduction

Python is 19 years old now. I started the design and implementation of the language on a cold Christmas break in Amsterdam, in late December 1989. It started out as a typical hobby project. Little did I know where it would all lead.

With Python's coming of age, I am going to look back on the history of the language, from the conception as a personal tool, through the the early years of community building, (If Guido was hit by a bus?), all the way through the release of Python 3000, almost 19 years later. It's been quite an adventure, for myself as well as for the users of the language.

This won't be an ordinary blog post -- it'll be an open-ended series. I may invite guest writers. I'll be touching upon many aspects of the language's history and evolution, both technical and social.

I'll start with the gradual publication of material I wrote a few years ago, when I was invited to contribute an article on Python to HOPL-III, the third installment of ACM's prestigious History of Programming Languages conference, held roughly every ten years. Unfortunately, the demands of the rather academically inclined reviewers were too much for my poor hacker's brain. Once I realized that with every round of review the amount of writing left to do seemed to increase rather than decrease, I withdrew my draft. Bless those who persevered, but I don't believe that the resulting collection of papers gives a representative overview of the developments in programming languages of the past decade.

The next destination of the draft was a book on Python to be published by Addison-Wesley. Again, the mountain of raw material that I had collected was too large and at the same time too incomplete to serve as a major section of the book, despite the editing help I received from David Beazley, a much better writer than I am.

As they tell prospective Ph.D. students, the best way to eat an elephant is one meal at a time. So today I am publishing the first bit of the elephant, perhaps still somewhat uncooked, but at least it's out there. Hopefully others who were there at the time can help clear up the inevitable omissions and mistakes. I have many more chapters, each still requiring some editing, and I expect this to be a long-running series. Therefore I am starting a separate blog title for this, unimaginatively called The History of Python. Follow the link and enjoy!

Thursday, December 18, 2008

The Emperor's New Mind

I recently re-read Roger Penrose's The Emperor's New Mind. I read it first in 1990, soon after it came out, and I still find it a stunning book, despite disagreeing with Penrose's speculations about consciousness somehow being boosted by quantum effect.

What makes the book so great in my view is that, in order to make his point, he has written an incredibly accessible textbook about a large number of topics in mathematics, physics and computer science. Penrose doesn't dumb down anything: he assumes the reader is an intelligent layperson, and explains each topic without compromise (though without getting into the technicalities of proofs).

Mathematical/computer topics include the theories of computability and algorithm complexity, Gödel's theorem, the Mandelbrot set, Turing machines (there's an appending with several pages of ones and zeros encoding a universal Turing machine -- I haven't checked it, but I'm sure that Penrose did), the Church-Turing thesis, and so on. In physics, he explains Maxwell's theory of electromagnetism (this was the first time I understood it), Phase space, special and general relativity, quantum theory, cosmology, black holes, space-time singularities and more. The table of contents reads like an overview of modern "hard" science. In the mean time Penrose also manages to explain Penrose tiling (the nonperiodic tiling of the plane, which he invented in the 1970s), the physics of nerve signals, Platonism, and important topics from the modern history of mathematics like Hilbert's program and Bertrand Russel's Principia Mathematica.

It's not surprising that Penrose shows prominently in the acknowledgments for Neil Stephenson's novel Anathem (in fact finding it there made me pick up my copy and start re-reading it).

Despite all this, I disagree with Penrose's claims about consciousness. Penrose does a good job separating his opinions on this topic from the science he presents, and in the end he cannot prove his hunches about consciousness any more than I can mine. Personally, I think that evolution is a perfectly fine explanation for our brains -- in other words, Richard Dawkins did a better job convincing me than Penrose. (I cannot recommend Dawkins' books enough -- you can skip The God Delusion though, just stick to his many excellent works about evolution and memes.)

Monday, December 8, 2008

In the Cloud or Not?

Some people love the cloud. (As in cloud computing, e.g. Google App Engine, Amazon EC2, Microsoft Azure.) Others hate it. They gripe about lock-in, proprietary APIs and so on. (I would provide links to examples of both attitudes, but I don't have time right now, and you can fill those in yourself easily. :-)

I wonder if, apart from the field being young, the differences of opinion may be similar to the different attitude towards home ownership: some folks hate renting, citing landlord conflicts, noisy neighbors and so on. Others hate home ownership, due to the outsize financial commitment and risk (all too clear to many these days), the never-ending maintenance (new roof, new fence, new furnace, new bathroom, new kitchen, it never ends). I'm kind of in the middle myself, having had good landlords in the past, and disliking the maintenance effort/cost for my own home these days, but enjoying the independence.

Obviously cloud computing would be more similar to renting, while traditional datacenter ownership to home ownership (though without the aspect of building up wealth through ownership :-). Someone else can take the analogy further, and compare different styles of cloud services to different ways landlords can run their business. (E.g. with Google App Engine you get carpet and furniture as part of the deal, and meals delivered as an option, while Amazon EC2 rents out bare concrete units where you can do as you please. There's a market for both.)

If that's the case, we should expect that the love/hate posts will never stop, and we'll never convince all haters to love the cloud. But there will be plenty of business for the landlords from those who prefer not to own their own servers, and we might as well cater to them rather than be discouraged by the cloud haters.

Friday, November 21, 2008

Scala?

I received a free copy of the Scala eBook by Martin Odersky, Lex Spoon, and Bill Venners. I tried to read it on my CalTrain commute, but ended up only skimming -- at 700+ pages it's a hefty tome. I'm also not in the primary target audience, as its focus seems to bounce between trying to entice Java programmers to try a better language, and an introduction to programming that happens to use Scala. I ended up going to the Scala website where I downloaded various other documents, such as a tutorial, a more technical overview paper, and the language reference.

Sad to say, I'm quite disappointed (in the language -- can't really say much about the quality of the eBook except that it's as big as the language). One of the first times I heard Scala mentioned it was a talk by Steve Yegge at Google I/O last May. Steve characterized Scala as "static typic's revenge" (I'm paraphrasing -- too lazy to watch the video to find that section) and went on to make fun of the incredible complexity of Scala's type system, which contains such esoteric concepts as type erasures, variance annotations, existential types, polymorphic method types, and many more (just scan the ToC of the language reference).

I have to agree with Steve -- if this is what it takes to have compile-time type-safety in a language, I'll take dynamic typing any day. There's got to be a better way -- perhaps Haskell? Haskell is a pure functional language with a fast implementation that seems to have solved the I/O problem of functional languages well -- while its Monads are truly deep and take real work to create, their use seems quite straightforeward.

Perhaps my biggest disappointment in Scala is that they have so many rules to make it possible to write code that looks straightforward, while being anything but -- these rules all seem to have innumerable exceptions, making it hard to know when writing simple code will work and when not. For example, the Scala book explains that you can use multiple 'if' qualifiers in its for-statement, but points out that you have to insert a semicolon in a position where you'd expect it to be inferred by the parser. To make matters even more mysterious, if you were to use curly braces instead of parentheses, you can omit the semicolon. All this is presented without any explanation. I found the explanation by combining two seemingly unrelated rules in the reference manual: first, the for-statement (technically called for-comprehension) allows both braces or parentheses with exactly the same semantics, but the rules for inferring semicolons are different inside braces than they are inside parentheses. Obvious, eh! :-)

Friday, November 14, 2008

Overheard

"All you can do with a shell script is make it worse. But since this is Python, you can make it better."