Security and Monoculture

Interesting research.

EDITED TO ADD (8/1): The paper is only viewable by subscribers. Here are some excerpts:

Fortunately, buffer-overflow attacks have a weakness: the intruder must know precisely what part of the computer's memory to target. In 1996, Forrest realised that these attacks could be foiled by scrambling the way a program uses a computer's memory. When you launch a program, the operating system normally allocates the same locations in a computer's random access memory (RAM) each time. Forrest wondered whether she could rewrite the operating system to force the program to use different memory locations that are picked randomly every time, thus flummoxing buffer-overflow attacks.

To test her concept, Forrest experimented with a version of the open-source operating system Linux. She altered the system to force programs to assign data to memory locations at random. Then she subjected the computer to several well-known attacks that used the buffer-overflow technique. None could get through. Instead, they targeted the wrong area of memory. Although part of the software would often crash, Linux would quickly restart it, and get rid of the virus in the process. In rare situations it would crash the entire operating system, a short-lived annoyance, certainly, but not bad considering the intruder had failed to take control of the machine.

Linux computer-security experts quickly picked up on Forrest's idea. In 2003 Red Hat, the maker of a popular version of Linux, began including memory-space randomisation in its products. "We had several vulnerabilities which we could downgrade in severity," says Marc J. Cox, a Red Hat security expert.

[...]

Memory scrambling isn't the only way to add diversity to operating systems. Even more sophisticated techniques are in the works. Forrest has tried altering "instruction sets", commands that programs use to communicate with a computer's hardware, such as its processor chip or memory.

Her trick was to replace the "translator" program that interprets these instruction sets with a specially modified one. Every time the computer boots up, Forrest's software loads into memory and encrypts the instruction sets in the hardware using a randomised encoding key. When a program wants to send a command to the computer, Forrest's translator decrypts the command on the fly so the computer can understand it.

This produces an elegant form of protection. If an attacker manages to insert malicious code into a running program, that code will also be decrypted by the translator when it is passed to the hardware. However, since the attacker's code is not encrypted in the first place, the decryption process turns it into digital gibberish so the computer hardware cannot understand it. Since it exists only in the computer's memory and has not been written to the computer's hard disc, it will vanish upon reboot.

Forrest has tested the process on several versions of Linux while launching buffer-overflow attacks. None were able to penetrate. As with memory randomisation, the failed attacks would, at worst, temporarily crash part of Linux - a small price to pay. Her translator program was a success. "It seemed like a crazy idea at first," says Gabriel Barrantes, who worked with Forrest on the project. "But it turned out to be sound."

[...]

In 2004, a group of researchers led by Hovav Shacham at Stanford University in California tried this trick against a copy of the popular web-server application Apache that was running on Linux, protected with memory randomisation. It took them 216 seconds per attack to break into it. They concluded that this protection is not sufficient to stop the most persistent viruses or a single, dedicated attacker.

Last year, a group of researchers at the University of Virginia, Charlottesville, performed a similar attack on a copy of Linux whose instruction set was protected by randomised encryption. They used a slightly more complex approach, making a series of guesses about different parts of the randomisation key. This time it took over 6 minutes to force a way in: the system was tougher, but hardly invulnerable.

[...]

Knight says that randomising the encryption on the instruction set is a more powerful technique because it can use larger and more complex forms of encryption. The only limitation is that as the encryption becomes more complicated, it takes the computer longer to decrypt each instruction, and this can slow the machine down. Barrantes found that instruction-set randomisation more than doubled the length of time an instruction took to execute. Make the encryption too robust, and computer users could find themselves drumming their fingers as they wait for a web page to load.

So he thinks the best approach is to combine different types of randomisation. Where one fails, another picks up. Last year, he took a variant of Linux and randomised both its memory-space allocation and its instruction sets. In December, he put 100 copies of the software online and hired a computer-security firm to try and penetrate them. The attacks failed. In May, he repeated the experiment but this time he provided the attackers with extra information about the randomised software. Their assault still failed.

The idea was to simulate what would happen if an adversary had a phenomenal amount of money, and secret information from an inside collaborator, says Knight. The results pleased him and, he hopes, will also please DARPA when he presents them to the agency. "We aren't claiming we can do everything, but for broad classes of attack, these techniques appear to work very well. We have no reason to believe that there would be any change if we were to try to apply this to the real world."

EDITED TO ADD (8/2): The article is online here.

Posted on August 1, 2006 at 6:26 AM • 47 Comments

Comments

MackAugust 1, 2006 7:56 AM

Bruce,

Only New Scientist subscribers can read that article, which is a shame cause it seems interesting.

AshokAugust 1, 2006 8:03 AM

It's a shame they're using domains like newscientisttech.com and newscientistjobs.com, rather than jobs.newscientist.com and so forth.
It becomes pretty easy to pick a new, credible-looking domain to fish from when companies do this kind of thing - and I broadly respect NewSci, so would expect them to do better than most.

SchemerAugust 1, 2006 11:20 AM

This seems like an excellent example of focusing on the symptom instead of the cause. It seems like most effort is spent keeping buffer overflow exploits from causing damage, when we should be putting far more effort into getting developers to use safe languages, safe libraries, heap-based allocation, static type-checkers, etc. in order to prevent the possibility of buffer overflows to begin with.

Christoph ZurniedenAugust 1, 2006 11:20 AM

"Fortunately, buffer-overflow attacks have a weakness [...]"

Let me guess what it isn't: the ability to change the line(s) of code causeing the buffer overflow in the first place.

Oh, my ... *sigh*

Why, for joves sake, do you want to treat the symptoms only instead of healing the desease?

The anti-virus companies do nearly the same, yes, but they earn some money with it at least and it is very difficult and therefore very expensive to repair a closed-source-system you don't own any rights for.

There are much better ways like e.g.separating executables from data at the hardwarelevel.
Or place automatic checks for buffer overflows with the compiler (e.g. http://www.trl.ibm.com/projects/security/ssp/).

And it's of cause much simpler to persuade the user to execute your malign code.


CZ

mdfAugust 1, 2006 11:27 AM

Perhaps unmentioned (or at least, unquoted here) is that these randomization defences can lead to the expression of extremely bizzare bugs/problems that can be very difficult to reproduce.

JoeAugust 1, 2006 11:37 AM

Anyone who's programmed on the late great VAX/VMS and OpenVMS systems should be familiar with the old %SYSTEM-F-ACCVIO or "Access Violation" error messages. Memory protection was one of the design principles of those operating systems and it forced programmers to do extensive input validation to prevent these errors. I remember a debate with a Windows PC programmer on whether memory protection was important and one of the arguments I made was that you could have someone execute code that you had not intended. The response I got was "Why would anyone want to do something like that?"

Years later, we dumped VAX VMS for Windows 2000 and I had to move on and learn more about Wild West programming on x86 and Windows. There is a sense of bitter irony when you see the last VAX or Alpha decommissioned in the same room where a bunch of sysadmins are busy patching and rebooting Windows 2003 machines.

Michael AshAugust 1, 2006 11:55 AM

@ Christoph Zurnieden

You want to treat the symptoms instead of the disease because curing the disease 100% is impossible. It is impossible to write bug-free code. That means there will always be vulnerabilities in software*. Given that, it is a good idea to have defense in depth by not only trying to write good software, but also making it more difficult to exploit the inevitable bugs. This is a compliment, not a replacement, for writing good code.

* These particular sorts of buffer overflows are much harder to have in programs written in higher level languages, but that just means these languages will have other sorts of bugs and vulnerabilities. They may well have fewer, but they won't have zero.

XyzAugust 1, 2006 12:31 PM

In response to CZ:

This doesn't seem to be about "treating the symptom and not the disease". It sounds like they're looking for ways to stop buffer overflow vulnerabilities right where they hit-- at the insertion. Though I'll concede that the encrypted instruction set idea seems gimmicky and probably isn't practical.

If there's a good way, it seems to make sense to make arbitrary code execution protection an OS level defense-- it's better than the alternative of relying on application code to be infallible.

Davi OttenheimerAugust 1, 2006 1:44 PM

@ Joe

"There is a sense of bitter irony when you see the last VAX or Alpha decommissioned in the same room where a bunch of sysadmins are busy patching and rebooting Windows 2003 machines."

Ha! Sorry, but when I worked with DEC in the early-mid 1990s we were told Windows would be the next evolution. OSF/1 was treated like a step-child. So your comment is even more ironic when you consider that the predecessor of today's Windows OS was in fact VMS. And wasn't the Alpha supposed to be the preferrred platform for Microsoft OS? Perhaps the hardware market was a little more open...

Mark Russinovich (now working for Microsoft) wrote about it in 1998:

http://www.windowsitpro.com/Articles/Index.cfm?IssueID=97&ArticleID=4494

"And now...the rest of the story: I'll take you on a short tour of NT's lineage, which leads back to Digital and its VMS OS. Most of NT's lead developers, including VMS's chief architect, came from Digital, and their background heavily influenced NT's development. After I talk about NT's roots, I'll discuss the more-than-coincidental similarities between NT and VMS, and how Digital reacted to NT's release. . . ."

Christoph ZurniedenAugust 1, 2006 2:06 PM

Thank you, Joe, for the reminiscence. It seems as if it is carefully forgotten that the PC-architecture was meant to be cheap and cheap only. It had to be able to run a single-user single-threaded OS and that was all it had to do.
There are some affords lastly by Intel, AMD and some others to reinstall the separation between executables and data but it is not used by many software writers.

> You want to treat the symptoms instead of the disease because curing the disease 100% is impossible.

The desease is "buffer overflow and related" (related are e.g. integer over/undeflows and so on) and is 100% curable simply by bounds checking. You do not need to do it yourself, your compiler can do it for you.

> It is impossible to write bug-free code.

That depends on the time of use of that particular software[BishBloom] ;-)

> That means there will always be vulnerabilities in software.

I can't see your conclusion. Yes, all software has bugs, but why _must_ these bugs include vulnerabilities?


CZ

(A bibliography in a blog comment? Good God!)
[BishBloom] P. Bishop, R. Bloomfield, "A Conservative Theory for Long-Term Reliability/Growth Prediction", IEEE Transactions on Reliability v. 45 no. 4 (Dec 96) pp 550
­560.

SamhAugust 1, 2006 2:16 PM

CZ wrote

"The desease is "buffer overflow and related" (related are e.g. integer over/undeflows and so on) and is 100% curable simply by bounds checking. You do not need to do it yourself, your compiler can do it for you."

I would be very surprised if you can get a compiler to protect against every single type of integer overflow without false positives.

I await your solution

JoeAugust 1, 2006 3:09 PM

@Davi

I'm familiar with NT's development roots and Cutler's leadership in building NT. In fact, there are some urban legends that say that WNT is VMS 1 letter shifted--as HAL (as in HAL 9000) is 1 letter shifted from IBM.

The point is that NT development had compromised some of the original design principles of VMS. For example, I remember when the GDI or graphics display subsystem moved from Ring 3 (user mode) to Ring 0 (kernel mode) for performance reasons. There was talk about moving it back in Vista--but I don't think that went anywhere.

The point is that good design principles went out the Windows when Bill Gates picked and chose only those that sold better going forward. I remember programmers complaining why they had to work extra hard on input validation when, on the Windows PC platform, it let them do whatever they want.

The lack of memory protection let the bad guys do whatever they want, too.

royAugust 1, 2006 3:19 PM

Compilers do not seem to understand buffer overflow problems.

The solution is idiot-simple in assembly language.

What's missing?

SamhAugust 1, 2006 3:28 PM

No, compilers such as GCC can handle stack overflows without issue, handling integer overflows 100% of the time without false positives is nigh on impossible. What could appear to the compiler as in integer overflow could actually be a legitimate operation which would not cause a problem.

Idiot-simple ? try writing it.

TimAugust 1, 2006 4:04 PM

If you were suffering from a terrible disease, which would you prefer:
1)Only the underlying cause was treated, leaving you in agony while you waited for a cure.
2)They worked on the cure, but gave you some painkiller.

Christoph ZurniedenAugust 1, 2006 4:19 PM

> "It is impossible to write bug-free code"
> It's a special case of "the halting problem"

It is indeed possible to write bug-free code, you just can't proof the code to be bug-free. That's no special case of the Halting-Problem it is the Halting-Problem.

> I would be very surprised if you can get a compiler to protect against every single type of integer overflow without false positives.

It might surprise you, but a modern Ada-compiler does such things quite well.


CZ

SamhAugust 1, 2006 4:26 PM

CZ, If you cannot prove your code is bug free, then how can you say it is possible to write bug free code ?

I am indeed surprised to hear Ada compilers are capable of preventing ALL possible integer overflows, I would have thought it would have more to do with the language symantics than the actual compiler. How about in C ?

ex-deccieAugust 1, 2006 5:08 PM

@Davi Ottenheimer: "Ha! Sorry, but when I worked with DEC in the early-mid 1990s we were told Windows would be the next evolution. OSF/1 was treated like a step-child. So your comment is even more ironic when you consider that the predecessor of today's Windows OS was in fact VMS."

The fact that people at the helm of the company were so misguided as to take that evangelical position isnt really the point. Digital had a long history of either hedging bets or making the wrong bet on desktop computing (however great or advanced their technology was) - decmate, rainbow et al, the macintosh marriage; windows was just the last in a line of vague attempts at 'me too'. The fact that they were eventually bought by a PC company once the vast IP assets had been sold in various fire sales to companies who have gone on to make a fortune from them is a tribute to Palmer's leadership, foresight and vision (note the dripping sarcasm).

And to call VMS the predecessor of Windows is a huge compliment to Windows and a huge insult to VMS. Just because something more recent is based on similar concepts and principles (some parts a direct ripoff) to something that preceded it doesnt mean that the people responsible for the more recent 'technology' didnt totally screw it up in the process.

Shame the linked article is another 'subsciber only' article, it would have been nice to read it and reflect more on how a good thing can be made rotten at the core.

Christoph ZurniedenAugust 1, 2006 5:09 PM

> If you cannot prove your code is bug free, then how can you say it is possible to write bug free code ?

Asume the (countable?) infinite set of all possible code includes bug-free code.
Let's take the simplest one: x = x, what goes in comes out, a virtual short piece of wire so to say. How can you prove that? You can't even test it, because you would have to test all possible values for x which are more than you can test.

Now let's assume the set of all code doesn't inlude any bug-free code.

Then even $x = x$ is wrong, which you can easily prove because, well, there is no bug-free code in the set.
But you still can't test it because of the same reasons as described above.

(It's not fully correct because of the width of the margin^W^W^W^Wsmall textarea, but I hope you are able to get the direction)

> How about in C ?

How is C different from Ada? According to Church et al. it's all the same.


CZ

SamhAugust 1, 2006 6:32 PM

CZ, you're point proves nothing, if you cannot prove that any piece of code is bug free, then you cannot say that it is possible to have bug free code because you cannot prove it. To believe it is possible to have bug free code is just that, a belief, it doesn't mean bug free code does not exist.

How does C differ from Ada ?

Under the hood of the compiler it does not, in language symantics it does, in what way they differ I cannot tell you, I can tell you that from a GCC point of view it is nigh on impossible to remove all possibility of integer overflows with 100% accuracy. If it cannot be done under the hood, it must be a question of the language itself.

Alan De SmetAugust 1, 2006 10:05 PM

While there are arguments to be made for more software to move to using managed languages that handle many of these attacks, it's not a complete. It takes a long time to reimplement major pieces of software; time that companies are hesistant to spend as it costs money with no direct increase in profit. Users aren't willing to pay for small security updates, let alone complete overhauls.

Davi OttenheimerAugust 1, 2006 10:31 PM

"And to call VMS the predecessor of Windows is a huge compliment to Windows and a huge insult to VMS"

Really? I'd see it the other way around. It's a compliment to VMS that Microsoft cherry-picked the lead developers to create their future OS. DEC certainly was a leader in the 1980s. Makes me wonder if the Itanium architects perhaps included some of the original Alpha 21x64 team. Anyway, in the end unix and x86, today both evolving through many "cultures", look like they will actually be far more successful and stable than most alternatives. Perhaps if UNIX had remained "proprietary", as Ken Olsen complained in 1988, and its supporters had not capitalized on the fact that it is easily extendable, simple and adaptive (hallmarks of multiculturalism), then it might have never have escaped his infamous "snake oil" gibe:

http://groups.google.com/group/comp.unix.wizards/msg/7bd1b3805722aeb2

Taneli HuuskonenAugust 2, 2006 2:12 AM

@Christoph Zurnieden:

I'm afraid your understanding of the Halting Problem and related issues is not quite accurate.

The Halting Problem is a special case of the more general problem of checking whether a given program meets given specifications. Its unsolvability implies that no matter how sophisticated proof methods you choose, there's always some spaghetti code that you can't handle with those methods - you can neither prove nor disprove that it'll eventually halt. However, it's trivial to write a one-liner that does nothing but halts, and another one that does nothing but goes into an infinite loop. It's equally easy to prove, in any halfway reasonable proof system, that the former will halt but the latter won't.

So, there's some code that you can prove to be bug-free, some that you can prove to be buggy, and some that you can't prove to be either, even for performing the extremely simple task of halting sooner or later. The same applies to a very wide class of specifications. Some software companies even use formal proofs of correctness in production. However, there's a catch. Such a proof can show that the program does what you told you wanted, not that it does what you actually want.

Matt WarrenAugust 2, 2006 4:11 AM

How far does Data Execution Prevention (DEP) go to solving these problems?

From my understanding, DEP works at the hardware level and prevents memory that hasn't been marked as executable from being run, so buffer overflows are stopped as they can only overwrite data memory, is this correct?

Are their buffer overflow attacks that DEP won't ever be able to stop?

Christoph ZurniedenAugust 2, 2006 6:34 AM

> I'm afraid your understanding of the Halting Problem and related issues is not quite accurate.

I do understand it, but english is not my native language and "Movable Type 3.2" does not have any kind of support for formulas, not even a tex2img or something similar.

I probably should have made it more clear that I wanted to show that you don't even need the halting problem to falsify the hypothesis "there is only buggy code".

> So, there's some code that you can prove to be bug-free, some that you can prove to be buggy, and some that you can't prove to be either, even for performing the extremely simple task of halting sooner or later.

The run doesn't halt if either the code is of infinite length which is not practically possible or it runs a piece of code with length >0 infinite times. (please don't kick me for that simplification immediatly, you will get your chance later, thank you) There is no halting problem if you don't allow infinite runtimes. It wouldn't be a turing complete language anymore, so you are free to do what you want and set for example arbitrary limits
for(i=0;i or set exit points
for(;;){
...
if(0>accept(...))
if(EAGAIN == errno || ...
continue;
else
...
exit(EXIT_FAILURE)
}
These problems are well known and solved, but with the advent of real multithreading (multiprocessor systems) others arose, the most famous is probably the deadlock, another incarnation of the halting problem. Arbitrary limits won't help in this case because of the simultaneousness of the locking attempts, you have to kill the simultaneousness, e.g. by adding different numbers of no-op's per thread after each failed locking attempt. Sleeping a random length of time, adding a random number of no-op's or releasing your time slice of the scheduler (e.g. with sched_yield() or similar) does not really solve it, btw!
Some deadlocks are even detectable at runtime, see for example fcntl(2) which can throw the error EDEADLK to give the programer the option to act accordingly.

So, most of the problems are known, there are solutions for them or workarounds; sometimes ugly band-aids and also try-another-way's of course if there is not even a mere band-aid known (in most cases a shiny sign of an error in the application logic). All of these solutions kill the turing completeness in one way or the other and that's one of two ways to handle the halting problem. The other way is with a shotgun. At least according to Larry Wall.

> Some software companies even use formal proofs of correctness in production.

Yes, I know, I have one of these ;-)

But a full proof is rarely done and needed. It would need a very expensive professional mathematician because you have to do that by hand. It's only done for easy to prove and small parts like the design and queries of an relational database or the like.
But it is quite common[1] here in Europe to use formal languages (mostly based on first-order predicate logic, like e.g. Z (ISO/IEC 13568:2002)) to describe the application logic exactly. It's even a mandatory 101 course in the UK, as far as I know.
The formal description together with a supportive language like SPARK-Ada (Ada without all of the bloat[2]) enables us to give the clients a warranty for fitness of purpose and that the applicaton is free of bugs[3].
With roughly the same development costs and -time as the "classic" approach and you can sell it for a much higher price too.
You can't solve all problems with that approach (The language is not turing complete anymore as described above) but all common daily problems like bookkeeping, inventory control systems and so on. You can even handle the german taxation system with it and that is a really hard problem every year[4].

> However, there's a catch. Such a proof can show that the program does what you told you wanted, not that it does what you actually want.

If you do not know what you actually want, well, that's your problem not the problem of the formal language, isn't it? ;-)

But it is more than sufficient if the program does what it's told to do. That's what the formal description is good for: an exact and unambiguous description of the application logic so you can write tests for it.

A simple example:

Description:
The application must put out "Hello world!"

Program 1:
cat /dev/random|grep "Hello world!"

Program 2:
head -c 1000m hi;
echo -n "Hello world!" >> hi;
head -c 1000m > hi;
cat hi;

Program 3:
echo -n "Goodbye world!"

Program 4:
echo -n "Hello world!"

Program 5:
echo "Hello world!"

Program 6:
#include
int main(void){
putchar('H');putchar('e');putchar('l');putchar('l');putchar('o');
putchar(' ');putchar('W');putchar('o');putchar('r');putchar('l');putchar('d');putchar('!');
exit(EXIT_SUCCESS);
}

So, please tell me: which one is correctly implementing the description?

As said above: it's not the solution for all problems but it's a really good tool to avoid a lot of them and should be a mandatory 101 class for every IT engineer because formal descriptions are the blueprints of computer engineers.


CZ


[1] OK, yes, you cannot call it "common" but it is in contrast to the USA. The only company I know to offer it there is IBM.

[2] Something for a start: http://www.praxis-his.com/sparkada/downloads.asp

[3] "bug-free" has only a legal meaning here: if a bug is found I have to repair it or give the money back and I'm also liable inside some legal and financial limits.

[4] some say that would prove P=NP. It doesn't of course but it's damn close.

exdeccie-2August 2, 2006 12:50 PM

The postings by "exdeccie" [August 1, 2006 05:08 PM] and “Joe��? [August 1, 2006 03:09 PM] are more correct than that of Davi Ottenheimer when discussing the relationship between NT and VMS. I was involved with, amongst other projects, low-level memory management software while at DEC in the 80s/90s. As soon as Gates overrode Cutler when Cutler tried to design a true OS, that is, a ring architecture OS using hardware-based support for different privilege levels, which includes not doing dumb things like architecting the software to run app level code (level or ring 3) with kernel privs (level 0), where level 0 code could see and manipulate non-virtualized address spaces (the real hardware), Gates perpetuating all the problems associated with DOS where all code was put in the position of being trusted code (had to be trusted). Put differently, in the Gatesian view of the world all code was simply presumed to act nicely. Once that was done, all protection is gone, period. Systems can, and have been, designed that do not allow app level code (untrusted code) to do anything but destroy itself and perhaps others using that app. Untrusted code cannot bring down the whole system or even other users not using the untrusted code (too long a discussion to explain in detail here). Finding an occasion code bug in a system designed this way is not the same as trying to make an inherently unsecure design “secure��?. That latter can’t be done. All of us are now forced to live with that Gatesian legacy. And yes, the management at DEC was absolutely terrible about all this as correctly pointed out by exdeccie, much to many, many people’s great sadness. We watched Olsen completely misread the small computer market, and then bring in the idiot Palmer to “save��? DEC (ha!). Anyway, the point is that Gates overrode the talent he hired away from DEC, and in that sense NT is NOT any kind of successor to VMS. NT is really a sort-of improved DOS, as influenced by people like Culter but as primarily controlled by Gates.

SamhAugust 2, 2006 1:20 PM

CZ wrote :
"These problems are well known and solved, but with the advent of real multithreading (multiprocessor systems) others arose, the most famous is probably the deadlock, another incarnation of the halting problem."

No, it's not. There are 4 conditions that create a situation that can cause deadlock, if you remove these, deadlock does not happen.

But we are getting away from the point, which is prevention of integer overflows by a compiler, unless everyone concedes, at least for the time being, that it isn't possible.

BennyAugust 2, 2006 3:56 PM

Samh, you're right, there are 4 conditions that lead to deadlock, and removing one of the four prevents deadlocks from happening (though often it is difficult or infeasible to remove one of the 4). But CZ is also right, that deadlock is an instance of the halting problem. More specifically, detecting a deadlock BEFORE it occurs is an instance of the halting problem.

MikeAugust 2, 2006 8:05 PM

Samh,

You solution to buffer overflow is here:

java.sun.com

:)

Oh my I know I know, but the fact remains, there are no buffer overlows in the language only in various implementaions of the runtime - easly fixed with proper C\C++ bounds checking.

Frankly, buffer overflows out to remain an problem until software quality improves. And that won't happen until software companies are liable for these flaws.

All of this other stuff is just a high tech way to let companies continue to write bad code.

Davi OttenheimerAugust 2, 2006 9:00 PM

@ exdeccie-2

We may be in violent agreement. My understanding was that Gates called Cutler at the end of the 80s and actually proposed the idea of a more stable "mission critical" version of Windows.

Gates managed to hire Cutler away from DEC even though he handed him an incredibly tight time-frame (three years to production?) and demanded a 16-bit Windows API and native support for Windows 3.x applications. Those were held up as *the* paramount goals by Gates but I think Cutler held on to a different view.

Here's an excerpt from Cutler in the forward of "Inside Windows NT" by Helen Custer, 1993:

"Our goals for the system included portability, security, POSIX compliance, compatibility, scalable performance (multi processor support), extensibility, and the ease of internationalization. Of all these goals, by far the one that was hardest to achieve and that had the most profound effect in the structure of the system was compatibility."

In that sense perhaps it was Cutler's mistake for believing that he could achieve stability in an OS that could achieve Gates' time and functionality requirements, no?

So while I agree with you that Gates' directives sacrificed the long-term quality of the product for short-term sales, but I do not think that dissolves the nature of NT's origins. From another perspective the initial platforms -- MIPS (DECstation) and Alpha -- were changed to x86 but that doesn't mean that Cutler did not try to support DEC hardware. He did...but it just didn't turn out that way.

So perhaps "predecessor" was too strong/precise a word but you can at least agree that Cutler was hired by Microsoft to build a new Windows OS based on principles and experiences from his prior creation, VMS for the VAX-11. Things just went awry from there.

Back to the main thread, those who said symptoms are not the best place to address exploits are correct technically, but decisions are not always just technical. In fact, if Cutler's original values had been honored by Microsoft from the start, it is very possible that the Windows platform might actually have been somewhat stable and resistant to attack. But on the other hand Gates' sacrifices have meant that the cost of mitigation, downtime and recovery from attacks on the Windows OS are burdens that consumers seem to continue to accept as the cost of doing business.

You may note that in the same book cited above, Cutler talks about the origins of VMS and concludes:

"Moral: The right thing to do technically isn't always the best thing to do financially."

AnonymousAugust 3, 2006 9:05 AM

> But we are getting away from the point,

We are already quite away from the topic, which is something in the line of "preventing usage of buffer overflows by obfuscating memory adresses", but as long as we don't get kicked by the moderators ...

> which is prevention of integer overflows by a compiler, unless everyone concedes, at least for the time being, that it isn't possible.

If it is possible in one turing compatible language (e.g. Ada) it is possible in every turing compatible language e.g. in C[1]. Main difference between C and Ada is that all the bounds-checking in Ada is done by the compiler (you have to switch them off explicitly. But be carefull with that off-switching: your rocket might explode) but must be done by hand within C. It's a repetitive task, so it's errorprone if done by humans, so it's a well suited task for a computer. Such scripts have been written several times, see for example the GCC patch I mentioned in an earlier post.


CZ

[1] this is not true of course for all of the arbitrary limits which kills the turing completeness needed for Church's thesis in general. It goes down to an individual similarity tests: if it is possible to describe on algorithm in all of the involved languages and one of these languages has a build-in bounds-checker it is also possible to build bounds-checking in all other languages.

Christoph ZurniedenAugust 3, 2006 9:11 AM

Oops, forgot to sign my posting about "signing", how embarrasing ;-)

CZ

exdeccie-2August 3, 2006 12:18 PM

@ Davi Ottenheimer

I agreed, we are in violent agreement. I mistook the short description of the VMS-NT relationship for what I thought may have been a deeper misunderstanding, but I can see now actually wasn't.

RvnPhnxAugust 3, 2006 2:34 PM

Ok, I guess most of the folks here are software types--I'm more from the hardware end of things in my interests myself and therefore noticed a few things about this article and its purported fixes.
Re: Memory Randomization
True memory randomization cannot be done in protected mode on x86 hardware in an "on the fly" manner. This is due to the whole basic idea of protected mode: that memory belongs to one specific application and only to that application. Therefore it is worth noting that in improving performance in applications by multithreading we can easily introduce potentially exploitable code into our applications. Using separate processes uses more resources, but can be considered more secure in that one respect.
That said, what is really going on with these "memory randomization" technologies is really that the base address of various segments becomes randomized. This does make cracking more difficult, but should not be confused with true randomization or even partial randomization (within the process' own address spaces--which can be a real nasty performance hit).
Re: Instruction Munging
I quote from the article: "Memory scrambling isn't the only way to add diversity to operating systems. Even more sophisticated techniques are in the works. Forrest has tried altering "instruction sets", commands that programs use to communicate with a computer's hardware, such as its processor chip or memory.

Her trick was to replace the "translator" program that interprets these instruction sets with a specially modified one. Every time the computer boots up, Forrest's software loads into memory and encrypts the instruction sets in the hardware using a randomised encoding key. When a program wants to send a command to the computer, Forrest's translator decrypts the command on the fly so the computer can understand it."
Umm What?! An applications or OS programmer can obscure the data being passed about between hardware and software or can run the whole danged thing in a VM if he wants, but he cannot actually encrypt the actual physical instructions. Either somebody is smoking something, selling snake oil, or frankly just has no idea what the hey they are talking about here. Frankly, running an "encrypted" instruction set in a vm is little different from running that vm (or more aptly emulator) with an undisclosed instruction set.
There is another problem with what is being stated in this article: If a new key is used on every boot then an unencrypted version of the original code must be made available at least once per boot cycle. This does not prevent code from being saved to the machine by a malicious third party and run at a later date. A problem like this can be mitigated by the use of some vm technologies, but bare (conventional) hardware is not (and cannot be as far as I know) up to this take alone.
As has been stated all too many times already there is a fix for the buffer attack: true and even physical separation between data (not executable) and (executable) program memory.

solinymAugust 4, 2006 9:09 AM

@CZ:

"It is indeed possible to write bug-free code, you just can't proof the code to be bug-free. That's no special case of the Halting-Problem it is the Halting-Problem."

Actually, you can't prove that arbitrary programs are bug-free. The null program is provably bug-free, albeit trivially. Of course writing a proof (one often writes the code around the proof, since the latter is more terse) takes skill, and yes due to Godel's Incompleteness Theorem, there is no perfect rule-based system for writing those proofs.

Provably correct code exists, there's just not very much of it. There may be bugs in the proof, in which case it's almost considered a design error, since the proofs are much more terse than most programming languages. One can only hope to write them in a language that is close to the problem domain, so that they aren't unnecessarily complex.

However, writing network daemons in a buffer-safe language (e.g., python, Perl, ruby, ocaml, java, just about anything written since C) would eliminate 50% of the remote root vulnerabilities (by volume). Not only that, but it's more efficient in terms of programmer time, most of the time. I go to great lengths to use the highest level tool for the job that I can get away with performance-wise; and I don't ratchet down until I've written the smaller, higher-level program and profiled it and found why it wasn't performing well enough. Then the HLL version serves as a template, so my C code can end up looking like, say, procmail, which has an excellent security history.

@RvnPhnx: I'm with you, I don't know how you'd encrypt your instructions, unless it's the program loader which decrypts them when loading them from disk into memory, or you've done something really damn crazy with the silicon that I won't be able to do at home. Can someone please clarify what they mean by encrypting the instructions? Are they by chance referring to the system calls, because that would be easy (and done before)? Basically if you change the system call number for execve(2) in libc, and recompile everything, then a foreign binary or exploit that pops a shell is pretty unlikely to work. You could even alarm that system call number so that it sets off klaxons, terminates the program, and kicks the person offline....

I concur with the general drift that worrying about the mechanics of buffer overflows is wrong-headed; just don't write in C! We've known about buffer overflows since ALGOL, join the last three decades of programming language design... if Unix wasn't so deeply wedded to C maybe people wouldn't start writing in it so often... some things are hard to do in HLLs, like privilege manipulation (setuid), ioctls, decently fast crypto... very little else. And even that stuff can be wrapped up in a library, and you can write the rest of the program in a HLL. Really, the python-to-C and ruby-to-C bindings are a snap.

BTW, threads are less secure yet more efficient than seperate processes because they don't cross a protection boundary; changing virtual memory mappings from one processes address space to another has a performance penalty of flushing the TLB, implementing new VM maps, reloading the segment registers (optionally, not done on Unix), reloading FP registers, etc. Actually that's done almost twice, since IPC has to be mediated by the kernel most of the time (mmap and SysV IPC excluded). There are research OSes like L5 and others that focus on trying to minimize the cost of IPC... see the archive.org version of Patrick Bridge's OS page.

If I had to name one thing that would improve Internet security that one coder could do, it would be to re-write the core Internet service daemons in a HLL. Then we'd be virtually guaranteed of no buffer overflows, and errors would probably be easier to find. Computers are fast, spend some cycles implementing defensive practices.

Christoph ZurniedenAugust 4, 2006 3:49 PM

@solinyn
I really should be much more carefull with my writings here, especially in the details ;-)

> [...] I don't ratchet down until I've written the smaller, higher-level program and profiled it and found why it wasn't performing well enough.

It is in most cases usefull to consider the acquisition of a bigger machine.
A good programer wants to see more than US$25/h but let's calculate with it. Including associated employer outlay it's probably around US$35-40/h and if he needs 100 hours for the port (inclusive testing and documenting!) it sums up to US$3,500-4,000.
It must be really slow or a very easy to port script before it's worth that money.
I guess that's one of the main reasons for ruby-on-rails and the like.


CZ

SpannerITWksAugust 22, 2006 9:12 PM

If all it takes for a Buffer-Overflow to occurr, is to have a string of more than eight digits, why can't the allocated space in the computer's memory be restricted " somehow " to only allow an 8 digit string, to prevent this from ever happening ?

Only asking !

Spanner

RogerAugust 23, 2006 3:34 AM

@SpannerITWks:
> why can't the allocated space in the computer's memory be restricted " somehow " to only allow an 8 digit string,

It can be, and in good programming, usually is. (It's not necessarily 8, by the way, it depends how much space the programmer thought would be needed.)

Buffer overflows are made possible by errors or oversights in programming, in particular memory management errors. They are nonexistent, or at least extremely rare, in languages which automatically manage memory for the programmer instead of requiring explicit coding for it (however this may be at the cost of reduced performance). In other languages they can be greatly reduced by good programming discipline and use of safer libraries. They frequently come from legacy code written before the problem was as widely appreciated; in new code, it is generally a sign of sloppiness.

SpannerITWksAugust 23, 2006 4:46 PM

Rodger

Aha, so it's the Programmers fault, and reliance on legacy sloppy code too !

So apart from the above, it sounds like they trade off good memory management etc for speed etc.

I wonder just much % trade off is involved, and these days with billy whiz bang GHz brains + Gbyte RAM and Fast HD's etc how much " noticable " difference there would actually be, if they did it properly ?

Maybe another factor could be using languages other than for eg C and it's variants and the like, and going for " easier " quicker fixes ? More room for more inbuilt errors/sloppiness etc !

I say " easier " not that i can programme, so i acknowledge even " easy " isn't all that easy, not to me anyway lol.

Thanx

Regards

Spanner

phred14October 20, 2006 7:51 AM

@solinym
>Actually, you can't prove that arbitrary programs are bug-free. The null program is provably bug-free, albeit trivially.

There's actually a chunk of humor behind this one... The classic "null program" was IBM's IEFBR14 that ran on mainframes. The name contained the program, it was "branch R14", where R14 contained the return address. One line of code, yet it managed to have something like 3 APARs against it. The APARs weren't actually with the one line of code, but the gobbledegook that had to surround it. Still, at something like 300%, it was the highest bug rate ever.

IEFBR14 was generally used in JCL in order to get side-effects. With JCL you attached files to a job step, with dispositions. The dispositions could be used to create, delete, etc files. The job step was typically IEFBR14, and all your really cared about was the disposition.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..