Tuesday, August 2, 2011

Origins: The Rollout of Introduction to Computer Systems

Dave O’Hallaron and I taught the first version of 15-213 Introduction to Computer Systems in the Fall of 1998.  It was a great experience right from the start., with the students and the teaching staff feeling like we were pioneers in a new way of teaching and learning about computer systems.  We could feel that we had hit a sweet spot in selecting material that the students found interesting and that would get them ready for later courses.  We still have the course web pages online.

What really made a difference in 15-213 was our ability to present interesting and engaging lab exercises, all done on computers.  We had a set of Alpha 21164 processors (Digital Equipment Corporation---may they rest in peace---was always a great friend to CMU) that the students accessed over the network.  Some of them were connected together via a separate Ethernet cable so that we could allow students to snoop packets in promiscuous mode.

Here are some of labs we offered that fall:

  • ·Data Lab.  A set of “puzzles” that require implementing standard logical and arithmetic operations with a restricted set of C expressions.  For example, compute the absolute value of a number without using any conditionals.
  • ·Bomb Lab.  This was the invention of our teaching assistant, Chris Colohan.  It involved reverse engineering an executable program, given in binary form, and devising a set of strings that would “defuse” six different phases.  This lab continues to be the centerpiece of the course.  It gets students to learn about machine-level programming, the use of tools such as GDB, and the general strategies of reverse engineering.
  • Malloc Lab.  Students implement their own malloc packages.  This lab has also stood the test of time. The challenge for most students is that all the casting and pointer hacking involved means that many bugs  are not caught by the compiler, and tracking down bugs can be very difficult.
  • Performance Lab.  Students write programs and both analyze and optimize their cache performance.  For this lab, we used matrix transpose as the problem to be solved
  •  Network Lab.  The students reverse-engineered a simple network protocol by sniffing packets.  It was fun to finally figure out the packet format and suddenly have messages (from “Dr. Evil”) coming through.
Over the years, we’ve added new labs and removed old ones, but the basic spirit of learning about computer systems by programming them and running tools on them still persists.

Instructors for our upper-level systems courses have come to appreciate the preparation that 15-213 provides.  Dave Eckhardt, one of our OS instructors, says that he can reliably predict how well a student will do in their course based on how they did with the Malloc lab.  15-213 has become a prerequisite for courses in operating systems, networking, compilers, computer graphics (they want students to understand floating point), embedded systems, and computer architecture.  The course is now required of all CS and ECE majors.

One sign of our success is the course ratings.  Here’s my average scores for “instructor effectiveness” on a five-point scale:

Not bad!  I went from being an under-performer with respect to the rest of the department to one who ranked near the top.  Not only did the students like the material and the labs, I also found it more fun to teach the course than was the case with computer architecture, and the students responded well to my enthusiasm.

I have now taught the course eleven times, and I still really enjoy it, as do the students.  Dave has also taught the course many times, sometimes with me and sometimes with other instructors.  He received the CMU School of Computer Science’s Herbert A. Simon Award for Teaching Excellence in Computer Science in 2004, based largely on our students’ appreciation of his efforts in teaching 15-213.

Randy Bryant


  1. Dear David and Randy,

    Thanks for providing this blog as a discussion forum. I have been using your textbook and several labs inspired by the CMU labs for many years in our computer architecture course here at Middlebury College.  One of the favorite labs has been the buffer overflow attack.  I saw that you removed this lab from the second edition of the book, presumably since (as you discuss in the second edition) modern Linux version make such attacks more difficult.  But I also saw that at CMU and other schools buffer overflow labs are still being assigned, with instructions to mount the attack on a designated machine running an older, less secure, version of Linux.  My question is if there is a specific version of Linux that you could recommend people like me could install on a special machine, and any other advice you could provide for a successful buffer overflow lab.



    Daniel Scharstein
    Professor of Computer Science and Chair
    Department of Computer Science
    Middlebury College
    Middlebury, VT 05753

  2. Daniel:

    We removed the homework problem on buffer overflow, but the buffer lab is still alive and well. You can get a copy from the instructor site: http://csapp.cs.cmu.edu/public/labs.html.

    You're right that it's harder to do buffer overflow exploits with modern Linux systems, but we created a work around that doesn't require you to tweak any of the system settings. Instead, we use mmap to allocate a block of memory at a fixed address, and set the block parameters to allow this region to contain executable code. Then, with a bit of embedded assembly code, we redirect the stack pointer to the block. The overflow exploits take place within this region.

    We got this idea from a U of Michigan PhD student who was interviewing for a faculty position several years ago. I am blanking on his name.

    One hack in this version is that we chose an address for the mmap'ed block by trial and error, but it seems to have worked just fine on many different systems.

    BTW: We have found it best to run this lab in 32-bit mode. Buffer overflow is much more interesting in IA32 than in x86-64, since more of the program state is held on the stack.