4 ms·
No, I don't believe that the future is languages that are not Turing-complete, mostly because halting is not the property most people care about. I believe that
by geofft 11y ago
No, I don't believe that the future is languages that are not Turing-complete, mostly because halting is not the property most people care about. I believe that a large part of the future will be languages that are not Turing-complete, for applications where that's appropriate (e.g., C compilers) but not where it's not (e.g., interpreters). I also don't think that "well, that's how we've always done it" is a particularly compelling argument given how young the field of programming languages is.
For instance, another wonderful example of requiring code to cooperate with the proof process is Google's Native Client. NaCl doesn't care about halting; what it cares about is that the code in question only accesses its own memory, or makes specific pre-defined calls into the supervising code. You can do this with hardware support (and they did, with segmentation, where available), but you can also do this with software support.
The NaCl technique is straightforward. You're required to lay out your assembly so that every 32-byte alignment boundary separates instructions; you must insert NOPs as necessary. Any fixed read, write, or jump must be within an address within a mask (or to a predefined address in privileged code), and any computed read, write, or jump must be immediately preceded, within the same 32-byte block, by a mask operation on the relevant register. For data, the mask enforces that only data is accessed; for jumps, the mask enforces that the jump target is within the code area and also 32-byte aligned.
Now you've proven a fairly complicated property of the code, that control flow never escapes to privileged code except at well-defined entry points. Doing so on arbitrary x86 would be impossible (unless you resort to binary translation), but this is a very minor modification to arbitrary x86, and a regular C compiler can be easily modified to emit it. The resulting restricted variant of x86 remains Turing-complete.
And it is entirely reasonable for the NaCl verifier to say "Uh, what are you doing, please try again" if presented with code that is technically non-malicious but does not follow the rules. The NaCl verifier doesn't claim to detect malicious code (that's the antivirus problem, and unsolvable). It claims to take code that makes a specific promise about not being malicious, and verifies that property.
- dllthomas 11y ago"halting is not the property most people care about" I agree that non-Turing complete languages are hugely interesting and likely to be more important as we go forward. But not for this reason. Most of the non-trivial properties people do care about can be used to tell you if a program is going to halt in a finite amount of time. Want an upper bound on memory? This program doesn't have one? Well, then it never halts. It has one? Well, then we know it halts or loops within 2^bits steps - run it for that many steps and you know which. I think non-Turing-complete will prove interesting because our programs are currently described in Turing complete languages, but run in more constrained contexts anyway. A program that always halts after running for 2^100 steps is not Turing complete. A program that halts if it tries to use more than 2^100 bytes of memory is not Turing complete. Applying these constraints in this way doesn't help us with analysis much, but it hints that we can probably find other ways to constrain our programs which won't get in the way of what we're trying to accomplish, and it's quite possible that some of those will let us build languages more amenable to analysis (and further possible that the gains in analysis will make up for a limited amount of getting-in-the-way).
- gugagore 11y agoI don't know where this thinking gets us. My computer, once I disconnect it from the internet, is actually a finite state machine and not a Turing machine, which I think you acknowledge. How does that help with anything? If my program uses one kebibyte of memory -- no I/O and harddrive, then it loops or halts within 2^(2^10) steps. For me to detect that, in general I need to store a history of length 2^(2^10), which is more than 10^300. That's 10^301 bytes that I need to detect if a 1kb RAM program loops.
- dllthomas 11y agoIt is a proof that we can get what we need to done in a language that is not Turing complete. The hope would be that there is some sweet spot we can find wherein we can say things that are dramatically more useful than "it will finish inside 2^(2^100) steps" without impacting usability tremendously more than "it won't use more than a kebibyte of memory" - which is already enough to defang the theoretical objection.
- wyldfire 11y ago> The NaCl technique is straightforward. You're required to ... Wow, what a great idea. Does anyone use anything like this to create an entire OS distro? Modified compiler behavior + binfmt verifier? What's the impact on executable performance/cache performance?
- geofft 11y agohttp://research.google.com/pubs/archive/34913.pdf http://research.google.com/pubs/archive/34913.pdf section 4 discusses performance: "The worst case performance overhead is [the SPEC2000 benchmark named] crafty at about 12%, with other benchmarks averaging about 5% overall." For some applications, there is no slowdown or even a minor speedup because of weird caching behavior and alignment. I haven't seen this used for a general-purpose OS distro (I suppose you'd use it for running a VM-like thing as an unprivileged user, without access to any hardware features) but I agree it would be cool.
- wyldfire 11y agoOh, perhaps I misunderstood, then. Is it not likely that the vast majority of C/C++ userspace programs could survive this change-in-compiler-output-to-meet-restriction without functionality impact?
- geofft 11y agoYes, you could apply this change in compiler output without functionality impact to existing userspace applications. But you'd have to recompile everything, and it's not clear how it'd be useful; part of the question is what the privileged interfaces should be. For Chrome this is useful because they want Chrome itself to be an unprivileged application, and they want to be essentially a recursive kernel to untrusted web content: there are multiple "users" (websites) that shouldn't be able to access each other's content, and certainly shouldn't be able to mess with the browser itself, and they get a restricted filesystem-like thing, screen-like thing, etc. For a general-purpose OS, the OS is assumed to have control of the CPU and can just use normal hardware protection. So it's primarily useful if you want to build an OS that can be installed inside an unprivileged user account on another OS. But in practice, most people grant their unprivileged user account enough privilege to use hardware-assisted virtualization.