Slashdot Mirror

What about Ken Thompson's famous backdoor C compiler? The source code looked fine, but when one compiled the login program a back door was automatically compiled in...and if you tried to recompile the compiler, you had to use the compiler and you're right back where you started.

That's actually easy - just read Reflections on trusting trust by Ken Thompson. This paper is absolutely recommended reading, and was groundbreaking when first published in August 1984. It's also one of /.'s top ten hacks of all time... Of course it would only work if your NSA Linux code was compiled on a system running NSA Linux from binaries, but that would probably apply a fair amount of the time.

lets take a look at how many 1k bytes of code could be inserted throughout the SE Linux OS to

It seems to me that this would be double-damned hard in an open source system.
[...]
How would all you clever hackers out there hide a function in an open source system in a way that it can escape detection even if all the source is read?

Ken Thompson's discussion of how he did this is available at http://www.acm.org/classics/sep95/. To summarize, I've blindly copied from Ignatius' post in an earlier Slashdot discussion below:

Check out the " back door" entry of the Jargon File to learn about one of the IMHO most creative hacks of all time:

[...] Ken Thompson's 1983 Turing Award lecture to the ACM admitted the existence of a back door in early Unix versions that may have qualified as the most fiendishly clever security hack of all time. In this scheme, the C compiler contained code that would recognize when the `login' command was being recompiled and insert some code recognizing a password chosen by Thompson, giving him entry to the system whether or not an account had been created for him.
Normally such a back door could be removed by removing it from the source code for the compiler and recompiling the compiler. But to recompile the compiler, you have to use the compiler -- so Thompson also arranged that the compiler would recognize when it was compiling a version of itself, and insert into the recompiled compiler the code to insert into the recompiled `login' the code to allow Thompson entry -- and, of course, the code to recognize itself and do the whole thing again the next time around! And having done this once, he was then able to recompile the compiler from the original sources; the hack perpetuated itself invisibly, leaving the back door in place and active but with no trace in the sources. [...]

A detailed description of the hack by Ken Thompson himself can be found here.

--

lets take a look at how many 1k bytes of code could be inserted throughout the SE Linux OS to

It seems to me that this would be double-damned hard in an open source system.
[...]
How would all you clever hackers out there hide a function in an open source system in a way that it can escape detection even if all the source is read?

Ken Thompson's discussion of how he did this is available at http://www.acm.org/classics/sep95/. To summarize, I've blindly copied from Ignatius' post in an earlier Slashdot discussion below:

Check out the " back door" entry of the Jargon File to learn about one of the IMHO most creative hacks of all time:

[...] Ken Thompson's 1983 Turing Award lecture to the ACM admitted the existence of a back door in early Unix versions that may have qualified as the most fiendishly clever security hack of all time. In this scheme, the C compiler contained code that would recognize when the `login' command was being recompiled and insert some code recognizing a password chosen by Thompson, giving him entry to the system whether or not an account had been created for him.
Normally such a back door could be removed by removing it from the source code for the compiler and recompiling the compiler. But to recompile the compiler, you have to use the compiler -- so Thompson also arranged that the compiler would recognize when it was compiling a version of itself, and insert into the recompiled compiler the code to insert into the recompiled `login' the code to allow Thompson entry -- and, of course, the code to recognize itself and do the whole thing again the next time around! And having done this once, he was then able to recompile the compiler from the original sources; the hack perpetuated itself invisibly, leaving the back door in place and active but with no trace in the sources. [...]

A detailed description of the hack by Ken Thompson himself can be found here.

--

Actually, advisors seem fairly useless. At The University of Texas anyway, they were always a waste of time. I'm not saying this out of childhood spite either. They don't know the curriculum and will just read from the flowchart when suggesting courses or a major. Go see what they have to offer, but don't expect much help.

A far better idea is to join the ACM which is applicable to any major and looks good on the resume. Your school's ACM should have some good socialization opportunities, and you should use these during your first year to meet as many upper classman as you can.

Find one who knows his shit (not necessarily the person who gets straight A's mind you) and ask what he/she think about the curriculum and everything. If you find the right person, he/she will know what's up better than any Advisor and half the Faculty as well.

470 on BLASTOFF goto MOON

Who do these guys think they are? Every 1st year CS student knows that GOTO is considered harmful.

Let's do ourselves all a favor and never go to the moon again using a GOTO statement!

The ACM's code of ethics is a good place to start.

http://www.acm.org/constitution/code.html

There is a set of established code of ethics for computer professionals, at least for those who are members of IEEE or ACM.

IEEE Code of Ethics
ACM Code of Ethics and Professional Conduct
ACM/IEEE Computer Society Software Engineering Code of Ethics and Professional Practice

cb

There is a set of established code of ethics for computer professionals, at least for those who are members of IEEE or ACM.

IEEE Code of Ethics
ACM Code of Ethics and Professional Conduct
ACM/IEEE Computer Society Software Engineering Code of Ethics and Professional Practice

cb

I wasn't aware of this link, but the ethics guidelines there looks good to me. You may also want to check out ACM Code of Ethics and Professional Conduct

The ACM also has some mailling lists about AI, usability and education.

These sites aren't about the entire field of cognitive science but it's a start.

Here's some ideas on how to get started.

1. Do a search on-line. A quick query at google. For example, search for:
   • "structured programming" ISBN
     
   brought up a couple thousand hits. Browse through the results until you find something YOU find interesting.
2. Check out book publishers web pages, for example: Addison-Wesley
3. Go to a library (ideally a college/university which has programming courses) but if you are nice to the folks at the information desk... well, I've been AMAZED at what they've been able to do to help me find information.
4. Think of organizations that would have promulgated this info in the past and check out what they have to offer. Places like the ACM - Association for Computing Machinery which has been around since 1947 and which published journals on the latest in research in computer systems.
5. Check the bibliographies of any books or articles you find for pointers to other works.
6. It's been about 10 years since I last was active in this area, so I don't even remember what some of these acronyms stand for, but here are a few that I remember:
   • DFD (Data Flow Diagram)
   • DMD (Data Model Diagram)
   • LDM (Logical Data Model)
   • SASD (not sure, but IIRC Systems Design - was bin in the United Kingdom)
   • Structure Charts
   • AD/Cycle (A huge undertaking by IBM to bring all the major CASE (computer aided software engineering) companies at the time (Intersolv, Bachman, Knowledgeware?) together and to provide a central repository for all of the vendor's modeling information.)

Take a course in Data Structures, too. Of all the courses I took in college, this is one whose principles I still use each day. Knowing when to use scalars, vectors (arrays), linear or circular lists (singly- or doubly-linked), hashes, and databases... if the DATA is organized RIGHT, writing the algorithms to access it is GREATLY simplified! Use the right tools for the job.

I've seen too many programmers who just hack away at code until it seems to work -- great to see you trying to use other's knowledge and experience to bring some design and order into your programming! Good Luck!

I would definitely not trust a voting booth more because the source code was put under GPL. Why? Because there is no guarantee whatsoever that the stuff that is actually running things really was compiled from exactly the source that I (or someone I trust) saw/reviewed. Neither is there any guarantee that the actual compiler used for compiling it was "clean" and did not introduce any backdoors (even if that too is open source). For reference, consider Dennis Ritchie's famous compiler hack

On the contrary, if the source is open, just about any programer can build a modified version and set up a trojan voting booth. Millions of computer illerate people would never even think of this being possible, let alone be careful about where and how they cast their vote.

--

Debian does security audits and has an excellent central repository.

Debian is my favorite Linux distribution. However, the concept of having every component in the OS be a "Package" with many interrelated varying dependencies is more confusing (for me) to keep track of what's on your system, than if a certain set of utilities is just marked "Core", and it's all updatable / maintainable / compileable from a single point w/o having to worry about the complexities of package management. For /ADD-ON/ programs, I'm all for package management though.

Anyway, what's the point of compiling everything from source when you don't have to?

Read Reflections on Trusting Trust by Ken Thompson, author of Unix. Compiling everything from source means that you can be sure of everything that's going on. (And you can use different compilers to verify that your results are the same, etc.)

I believe Ken Thompson wrote a paper on it
Reflections on Trusting Trust (I remembered enough about it that Google didn't need much dredging).
--

Ken Thompson wrote an important article about this, back in 1984 (wow, that brings back memories), titled Reflections on Trusting Trust where he discussed his famous compiler-trojan which propagated itself even when the user had full access to the source code. The way it worked is the compiler had some code in it that recognized when it was compiling the compiler's own source. When it did, it inserted a bit of code which compiled the source not as a clean compiler but as another copy of the trojan. The user could read the sourcecode all he wanted, but he couldn't get around having to trust the compiler. The thrust of Thompson's article was that you have to put some trust in someone or something along the line.

The moral of the story is that unless you built your own processor, built your own hardware, built your own compiler from scratch, and read the source code and understood it completely, you're open to attack. Open-source itself is no magic bullet, and it's time the zealots figured that out.

Thalia

Ritchie's classic essay, "Reflections on Trusting Trust", is available from the ACM.

While I agree with your point completely, are you sure that your non-NSA Linux box doesn't have any gcc backdoors? Have you gone over it with a hex editor, or even gdb? Are you sure that your current system is any safer than anything the NSA may put out?

I haven't done any of that either; I'm as guilty as the next person of trusting the upstream sources. I'm just saying that I don't think that the NSA is the only party that would be susceptible to making stealthy changes to your system.

The Association for Computing Machinery has a "special interest group" devoted to APL: SIGAPL. SIGAPL publishes an informal journal, much of which is available online at their website.

The Association for Computing Machinery has a "special interest group" devoted to APL: SIGAPL. SIGAPL publishes an informal journal, much of which is available online at their website.

Recall also that KT showed how even open source cannot be trusted.

The user interface and CSCW research communities have done a lot of work on shared calendars. I strongly recommend you look through it. A good place to start is ACM's digital library.

Basically, there are two ways to preform replication: "lazy replication" and "eager replication". "Eager replication" means that all updates are atomic across all nodes and that transactions are serializable. However, the problem with "eager replication" is that as you increase the number of nodes n, the probability of deadlock increases on the order of n^5. The "solution", such as it is, is to remove the expectation of serializabilty, using timestamps for concurrency control, only allow commutative transactions on your data, and use two-tier replication. This works for banks and others whose database applications consist mainly of commutative transactions, but won't for many others: YMMV. (Gray's paper also details the differences between having a single "master" node that "owns" all db objects and having each node own several objects.)

IIRC, the way Notes does it is by queuing updates at the local node and using an optimistic concurrency control mechanism when the local node connects to replicate. This is great for the application domain that Notes caters to: I "own" my own calendar, and if I'm out of the office (and have my node -- notebook -- with me), you can't schedule me for an appointment until I come back. However, for many application domains, this won't work.

In any case, that's why Notes does it -- because it can, thanks to the nature of its data domain -- and why most people don't -- because it's hard/impossible for the general case.


~wog
PS -- If you can't get into the ACM Digital Library, check out these lecture notes from Stonebraker's anthology at Berzerkeley.

The article is available from the ACM in PDF format. A paid membership, or a small one-time fee, is required.

The article is available from the ACM in PDF format. A paid membership, or a small one-time fee, is required.

There was an SGI game whose name I sadly cannot recall which used the indy's onboard camera and you would make hand motions in front of it to control your character. This is just an even less sophisticated version of the same thing, and it's not free? Pshaw. Someone obviously needs to find the game I'm talking about. I did some websearching around, but couldn't find it, perhaps I was using the wrong words.

By the way, while I was searching for that, I came across this Input Devices Resources List which might be interesting to people reading this thread. Also see GestureVR. You might want to wade through This Page on VR Software Toolkits, but it's painful; This person has no idea what HTML is for.

Even before that there have been some amazing demos shown at SIGGRAPH. There is the work of Nadia Thalmann at Miralab and a cloth simulation paper was the cover of the SIGGRAPH 98 Proceedings. It was by David Baraff and Andrew Witkin, both I think are now at Pixar.

It will still take some time to get realtime cloth simulations, especially for simulating different types of cloths, with good collision detection (self and otherwise) and that it doesn't involve a square pice of cloth like a flag, but something more complex like garnments which are made from shaped pieces. Looking forward to it, but not holding my breath.

I think the philosophy expounded in the Anti-Mac article should be taken further. Why be limited just t o the GUI and the commands? We should be rethinking the entire thing, from the mouse to the keyboard to the display screen. Admittedly one can't get any better than a screen, but buttons? Certainly we need to think of something that takes into account all of the human hand's advantages and disadvantages. Ergonomic keyboards and mice are not enough.

--Sanatan

is quite funny: FreeBSD and Linux and other OSS CAN be proven to not have any back-doors. Microsoft software cannot.

Practically speaking, yes. Open source software can be proven not to have any back doors. However, impractically speaking, no software is safe. I'm sure you all have already read this, but just in case, check out Ken Thompson's Reflections on Trusting Trust.

As Treasurer of the Bucknell University ACM (Association for Computing Machinery), myself and the other officers help to persuade industry, faculty, and students computer experts or evangelists to (of OOP, OSS, Linux, etc) come to Bucknell to give a presentation. In the past year or so, we've had guests like Dan Quinlan of Transmeta, speaking on the Linux Standards Base, Ralph Droms (inventor of DHCP), a faculty member at Bucknell, John 'Maddog' Hall (Linux International executive director) on the Flexibility of the Linux OS, and many others. Currently, Eric S. Raymond has added us to his mailing list and will probably come Spring semester to talk about his ideals and beliefs when it comes to software.

What are our methods of obtaining guests? First, it helps to have some connections with someone related to the person you'd like a have speak at your school. Second, being at a top-notch college like Bucknell University tends to give some incentive, perhaps, for people to visit. Finally, persistance does pay off occassionally; if there's someone you really want, make sure you remind them via email or vmail every so often that you'd be absolutely delighted to have them grace you with their presence ;-D

Good luck!

According to a quick search, this: article says that our FOV is ~200 degrees horizontally, and ~150 vertically.

Hmm. Just now I had a profound thought. What about a new fraternal organization for the high-tech, you know, like the Elks, Masons, Moose, or Water Buffalos? Yeah, I could dig that... Anyone know of one? I think someone needs to get going on that right away.

Here is the original paper about Whisper as a PDF file. It was presented at an ACM, Computer Human Interaction conference last year. You may need to register to read it, but anyway, it is quite interesting.

The way you hold your hand looks to others as if you are talking on a really small mobile phone (so small they can't see it :-). So actually you don't look as crazy to others as you do with just a handsfree earpiece. And the sound conduction through your finger bones is very good. So good that it is actually easier to hear in a noisy environment than with a normal phone.

They also found that people didn't shout into their phone when using Whisper, because the finger in the ear gave better feedback to your voice volume.

Regards,

Jody

There is an interesting article at http://www.acm.org/sigchi/bu lle tin/1997.4/bass.html which is on a workshop on the topic of Wearable computing. If you notice, at the bottom of the page you notice that Masaaki Fukumoto participated in this. I wonder to what extent this played in his "finger phone."

For an article that he (Fukumoto) wrote on a wristwatch style wearable handset you can chek out http://w ww. acm.org/pubs/citations/proceedings/chi/302979/p112 -fukumoto/

There is an interesting article at http://www.acm.org/sigchi/bu lle tin/1997.4/bass.html which is on a workshop on the topic of Wearable computing. If you notice, at the bottom of the page you notice that Masaaki Fukumoto participated in this. I wonder to what extent this played in his "finger phone."

For an article that he (Fukumoto) wrote on a wristwatch style wearable handset you can chek out http://w ww. acm.org/pubs/citations/proceedings/chi/302979/p112 -fukumoto/

The ACM forum on risks, the usenet risks forum (comp.risks) and others have been talking about this for years. I always go to the back page of Communications of the ACM for a hair-raising chuckle. Unfortunately, recently the columns have been self-serving ads.

If you haven't recognized that people are the weakest link, where have you been?

Some reasons to vote for Barbara Simons:

1. Decades of activism: Barbara Simons has received the highest activist awards (EFF Pioneer 1998, CPSR Weiner Award 1992).

2. Leadership: Led the ACM (president 1998-2000) and USACM. Of all the nominees, I think she has the strongest proven ability to deal effectively with committees and opponents both in and out of government.

3. Computer science expertise: She has a CS PhD from Berkeley, has held senior research positions, been made a fellow of the ACM, AAAS, etc.

As for testing in small group, I do think it is important, in moderation. I've seen products that have been UI-tested to death and they come out looking like Frankenstein. When a problem arises, for some reason, corrections focus on that one issue (hack is probably too strong of a word), rather than considering the interface as a whole.

What you say is true, which is why it is so important to have a set of global interface guidelines in the first place. It keeps you from hacking away at specific situations that probably shouldn't have ever arisen in the first place. As far as testing in small groups goes, Apple used to do controlled experiments to find out what really did work best. Now, the biggest gripe I've heard with that is that the initial Mac interface was optimized for a novice who wasn't an especially good typist, which is why older versions of the OS could get a bit tedious (and why Anti-Mac can make almost as much sense). The situation did improve, of course, and some OS X features (like sheets) really will reward an expert user. But the "this window is too tall to resize" problem...words fail me. :-(

[Price is] a complex issue. Since they don't have the volume of say a Dell, they don't get all the discounts on the components.

Wow. Now *that* I don't buy. Apple's volumes are still pretty huge, they don't tend to offer bleeding edge anything, and the platform is now so standardized that for some things, I suspect their volumes and discounts are better than Dell's.

Plus there's just the issue of pure revenue. If they lower the prices, will that actually bring in significantly more buyers, or will it just reduce total revenue. I think the $799 iMac is a good test bed.

It could be, except that they "under-RAMed" that box in a serious way. I think there is now one too many levels of iMac, and the cheap box threatens to cannibalize sales on the basic iMac DV.

The Cube is probably too expensive, and poorly positioned, though. I'm not sure who's supposed to by it, except people with extra cash laying around.

The cube is a beautiful thing, and a quintessential Jobs creation. I mean, The Cube is so obviously Jobs' ultimate vision for the NeXT cube that never was. It's an aesthetic statement more than it is a product at this point. The real product based on the Cube is the Cube plus the 15" LCD; the problem is that won't sell very well unless the cost is $2000 or less.

In a perverse way, I'm glad that this is a disappointment so far, since it will return Apple's attention to being a bit more in tune with the market again.

bluGill wrote:

one of the early unix guys (Ken Thompson if I remember right) created a version of login with a backdoor for him to get in. Then he created a C compiler that could tell if login was being compiled and if so insert his backdoor. Then he modified the C compiler to check if it was compiling itself and if so insert both hacks. Soon he was able to (but claims he never did) distribute a C compiler that looked normal, yet would give him access to any machine.

The article you speak of is Reflections on Trusting Trust by Ken Thompson. While it's a scary scenario, you can still decompile the binary and check the algorithm for security. Compiling just once with a known-to-be-safe compiler also removes the hole.

How do I know I'm not running a trojan

The risk is the same when running ANY program that is downloaded, regardless of purpose.

The only way to be mostly sure, is to audit the source of every program you run, then compile and build yourself. Even then, you have to worry about the compiler, as the infamous compiler trojan illustrates, as described by Ken Thompson.

"The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code. In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode. As the level of program gets lower, these bugs will be harder and harder to detect. A well installed microcode bug will be almost impossible to detect. " http://www.acm.org/classics/sep95/

we should remember that unless we compile the software we use ourselves from our own source that we ourselves have checked, then we can never be sure if there exists a backdoor into our software.

This reminds me of Ken Thompson's Reflections on Trusting Trust Basically, he was talking about the login program in Unix.

How do you know that there isn't some special login that's universal? Ok, you say, "well, I'll just compile the source & run it myself".

His response would be, "how do you know that I didn't put something in gcc that figured out if it was compiling the login program and automatically added that one entry into the code?"

You would respond "So, I'll just recompile gcc"

And of course he'd say, "How do you know that I haven't put code into the compiled gcc that checks to see if your compiling gcc & add that code into the gcc binary?"

Even if you have the source, that isn't a 100% guarantee that there aren't any back doors. Surely everyone remembers the famous Ken Thompson article about the back door in login with support in the C compiler, which is even referenced in the Jargon File.

I couldn't find the reference on the ACM's web site, but I seem to recall that Dijkstra's article/letter was published sometime in 1968.

Vernor Vinge suggests something of this sort in his latest Hugo and Prometheus award winning novel A Deepness In The Sky. One of his characters speculates on the power of providing the underlying layers of increasingly componentized software. Furthermore, Ken Thompson, in his classic article Reflections on Trusting Trust, discusses a mechanism for hiding a back door in such a way that it will be replicated with each revision of the software, and the source code for it cannot be found.

The point I am driving at is that currently these security holes are believed to be accidental. We are not far from seeing instances of them that are deliberately created. Open source offers some protection from that, if the source is actively read by numerous competent people. But when the code is linked from many sources, the program becomes vulnerable to the weakest link in the chain, the least well reviewed library.

What we need is a lobby to represent our opinions. I'm a member of ACM, and they are active in issues like this. Check out:

http://www.acm.org/serving/cacm/outlaw.html

Speaking of which... could someone outline what the ACM is all about, i.e., who should join, and why?

You could always look here

To quote from their web page: ACM, the Association for Computing Machinery, is an international scientific and educational organization dedicated to advancing the arts, sciences, and applications of information technology. With a world-wide membership of 80,000, ACM functions as a locus for computing professionals and students working in the various fields of Information Technology.

Ultimately, this is a controversial topic. Perhaps the strongest contender would be Konrad Zuse , who developed a programmable computer in the 1940s. Interesting first person notes from an inventor in Nazi germany.

In the ACM archives , there is a paper on "Monitors, an operating system structuring concept" by C.A.R Hoare. Since this is from 1974, I guess it's not too old, but still an interesting paper.

Many have been posting about OS/360 (or 390) but while MVS was a major step in OS history, it wasn't the first. It was released in 1964, too late for the first OS.

Also interesting is a time article on the first computer

All the old stuff is fun to read.

w/m

~Socks.