With so much to be sad about in the world today, it is with a hopeful eye that we turn to D. J. Bernstein, professor of mathematics and computer science. You may know about Bernstein because his First Amendment lawsuit forced the government to stop banning export of computer encryption software. Or you may know of him because of his mathematical breakthroughs. Or you may know of him because his software, including qmail and djbdns, does important things with grace and without bugs.

In any event, Prof. Bernstein has recently posted a statement of selected research activities [PDF] which provides more hope in these dark times.

Bernstein is getting back on track:

I haven’t published much software in the last few years; my department colleagues have made clear to me that they don’t value anything other than papers. Fortunately, my promotion has now been approved by the department and the dean, so I can return to a healthy balance between papers and software.

Protecting the Internet:

Cryptography on the Internet is in a sorry state. Every serious Internet protocol now has some sort of “security” extension, but only a tiny fraction of data on the Internet is actually cryptographically protected. Sometimes the security extensions are too hard to use. Sometimes the extensions are usable but too slow for busy servers.

I’m adding link-level cryptographic protection to the Internet mail system. … Unlike existing mail “security” protocols, this will be fast enough to use for every message, and it will protect against attackers actively misdirecting messages.

…

The Domain Name System is a distributed database that maps domain names, such as cr.yp.to, to IP addresses (and other data), such as 131.193.178.160 [which explain where to find a specific computer].

Today’s DNS records are not cryptographically protected. By giving fake IP addresses to your computer, an attacker can easily steal your incoming and outgoing mail, substitute fake web pages, etc.

DNSSEC, a project to cryptographically sign DNS records, has been under development for ten years by a large (and obviously rather incompetent) team of protocol developers. I’ve designed a new DNS security system, DNSSEC2, with several advantages over DNSSEC: it’s faster; it uses much stronger cryptographic tools; it protects against denial of service; it allows end-to-end security without help from the centralized root servers; and, most importantly, it works with existing DNS database software, so it’s much easier than DNSSEC to deploy. See http://cr.yp.to/talks.html#2004.04.28. I plan to release the DNSSEC2 software this year.

Writing software without bugs:

All the cryptographic protection in the world won’t stop an attacker who exploits a bug, such as a buffer overflow, to seize control of your computer. Some of the most widely deployed programs on the Internet—the BIND DNS server, for example, and the Sendmail SMTP server (post-office program)—have had thousands of bugs, including many bugs that allowed attackers to seize control.

For more than a decade I have been systematically identifying error-prone programming habits—by reviewing the literature, by analyzing other people’s mistakes, and by analyzing my own mistakes—and redesigning my programming environment to eliminate those habits. …

There were several non-security bugs in qmail, and a few in djbdns. My error rate has continued to drop since then. I’m no longer surprised to whip up a several-thousand-line program and have it pass all its tests the first time.

Bug-elimination research, like other user-interface research, is highly nonmathematical. The goal is to have users, in this case programmers, make as few mistakes as possible in achieving their desired effects. We don’t have any way to model this—to model human psychology—except by experiment. We can’t even recognize mistakes without a human’s help. (If you can write a program to recognize a class of mistakes, great—we’ll incorporate your program into the user interface, eliminating those mistakes—but we still won’t be able to recognize the remaining mistakes.) I’ve seen many mathematicians bothered by this lack of formalization; they ask nonsensical questions like “How can you prove that you don’t have any bugs?” So I sneak out of the department, take off my mathematician’s hat, and continue making progress towards the goal.

And protecting your computer from other people’s bugs:

The software installed on my newest home computer contains 78 million lines of C and C++ source code. Presumably there are hundreds of thousands of bugs in this code. Removing all of those bugs would be quite expensive. Fortunately, there’s a less expensive way to eliminate most security problems.

Consider, for example, a compressed music track. The UNIX ogg123 program and underlying libraries contain 50000 lines of code whose sole purpose is to read a compressed music track in Ogg Vorbis format and write an uncompressed music track in wave format.

UNIX makes it possible (though unnecessarily difficult) to build a safeogg program that does the same conversion and that has no other power over the system. Bugs in the 50000 lines of code are then irrelevant to security: if the input is from an attacker who seizes control of safeogg, the most the attacker can do is write arbitrary output, which is what the input source was authorized to do anyway. …

Do all transformations have this property? Of course not. There are some transformations that produce output trusted more highly than the input; these transformations have to be bug-free. … But these exceptions account for only a small fraction of the code in a system. …

I expect this strategy to produce invulnerable computer systems: restructure programs to put almost all code into extreme sandboxes; eliminate bugs in the small volume of remaining code. I won’t be satisfied until I’ve put the entire security industry out of work.

posted January 08, 2005 03:29 PM (Technology) (1 comments) #

D. J. Bernstein writes (and Aaron quotes),

“The goal is to have users, in this case programmers, make as few mistakes as possible in achieving their desired effects.”

Given my own horrific programming skills, it would be interesting to see some numbers on how well the “paired programming” concept works in some “agile” approaches.

When I think about Quality, I’m surprised at how resistent people are to following a basic approach: When a bug occurs, record it and categorize it. Try to figure out where in the system life cycle it was introduced, and its root cause. Once you have enough data points to make some intelligent guesses, design preventive measures and then observe to see if the bug counts go down (or if the “preventive” measure actually introduces more/different bugs.

The most interesting thing I’ve read on this topic is “Orthogonal Defect Classification - A Concept for In-Process Measurements” in the IEEE Transactions on Software Engineering by Ram Chillarege, Inderpal S. Bhandari, Jarir K. Chaar, Michael J. Halliday, Diane S. Moebus, Bonnie K. Ray, and Man-Yuen Wong. (They propose a technique that is a little more scientifc than my “intelligent guesses.”)

posted by Russ Schwartz at January 10, 2005 06:42 AM #