2003

September 2003

Dear Alumni and Friends:

I am pleased to report, once again on our department's activities this year. Overall, another good year - exciting research, bright students, good weather. What else could one ask for? Well, there is one thing one could ask for: a better economy!

The economic slump has indeed arrived at Gates Hall; we are challenged because university funds, television income, and gifts are all down. In response, we have had to institute some budget cuts. The good news is that the cuts have not affected our research and teaching excellence. And fortunately, our graduates are still getting good jobs, as far as I can tell.

Anyway, here is my report on this year's activities. Incidentally, I have added Web links at various places. If you do not want to type in all these URLs, you may want to visit the electronic version of this newsletter at CS News (http://cs.stanford.edu/News/), where you will find the live links.

Research Activities

The enormous growth of the Internet is bringing on a “success-disaster,” as the Internet is running out of addresses. Yet who could argue with the obvious solution adopted by the Internet community - namely migrate to a new standard, IPv6, with larger addresses. Well, David Cheriton and the Distributed Systems Group, that's who. For the past several years, Cheriton and his students have been exploring key issues with the Internet architecture under the DARPA-sponsored� TRIAD Project (http://www-dsg.stanford.edu/triad/index.html). Their work has focused on dramatically improving the availability and attack-resistance of DNS naming by integrating naming and routing. By basing end-to-end identification and reliability on names, the long, expensive, and uncertain migration to IPv6 is simply not necessary. Key aspects such as security of the Internet are significantly improved. Their work is continuing, with increasing focus on making the Internet attack-resistant, studying vulnerable areas such as routing, mobile access and virtual private networks.

Speaking of security, Dan Boneh and his students have been examining the security of existing systems and designing new security mechanisms. Here is one example of a vulnerability they recently found, and an example of a new security mechanism they built:

• Timing attacks on SSL web servers. Dan & Co. recently showed that by repeatedly measuring the time that a web server takes to complete an SSL handshake, an attacker can completely expose that server's private key. Once the private key is exposed, the attacker can eavesdrop on all future traffic to the web server. Dan & Co. designed the attack against the implementation of SSL on an Apache web server. Using a remote machine they were able to extract the private key from an Apache web server in about two hours. The attack applies to many other security systems such as OpenSSH and stunnel. Dan alerted software vendors to this significant vulnerability before publishing the paper.

• SiRiUS:� an easy to deploy secure file system for remote storage. Secure file systems have been around for many years, yet very few of them are being used. One problem is the difficulty of deploying secure file systems. Most often one needs to completely upgrade the storage infrastructure to deploy the system. SiRiUS is a new secure file system mechanism designed for ease of deployment. The system implements access control via cryptographic techniques. It is designed to work with existing file systems such as NSF and CIFS, Web based file storage, and P2P storage systems. SiRiUS overlays access control on top of the underlying file storage system. The system supports file sharing between users, granting of read or write access, and provides data freshness guarantees.

If you want to learn more about this work, as well as other activities in the security area, please visit the home page of our Security Lab� (http://crypto.stanford.edu/seclab/), a collaborative effort among Dan Boneh, David Dill, Dawson Engler, Ed Feigenbaum, Monica Lam, John Mitchell, Mendel Rosenblum, and many others.

Daphne Koller, together with her PhD student Eran Segal and several other students, have been working on understanding genetic processes from a variety of genomic data sets, using techniques from machine learning and probabilistic models. In one recent project, they considered the problem of gene regulation. All of the cells in our body contain exact the same DNA, but the behavior of different cells can vary radically. The reason is that some genes are activated in some cells and dormant in others. Understanding the regulatory processes that cause genes to activate has important implications on comprehending how cells function. It also affects how diseases that involve breakdown in regulatory processes, such as cancer, can develop. In their recent work, published in the highly prestigious journal Nature Genetics, Daphne and Eran, together with several other collaborators (including Stanford alum Nir Friedman, now at Hebrew University), provided a high-throughput computational method for extracting regulatory circuits from large collections of gene expression measurements. The method identified modules of genes that are co-regulated and determined the regulatory genes that tell each module of genes to turn on or off — in other words, to start or stop making proteins. The proteins from each module, in turn, are responsible for a different cell process. The results of the analysis were shown to reproduce many regulatory relationships that were previously discovered. More interesting, in collaboration with Prof. David Botstein's group (Stanford, Genetics Department), they also tested some of the method's novel predictions in real wet-lab experiments. They “knocked out” a regulator under the conditions where it is predicted to be active. In the tested knock outs, three out of three turned out to regulate predicted genes. This showed that the method works, and allowed the characterization of three previously uncharacterized genes.

Two other papers by Daphne and Eran that applied the same framework to other computational problems in genomics were awarded the best paper and the best student paper awards at the recent Symposium on Intelligent Systems in Molecular Biology (ISMB 2003). It was a clean sweep of the awards!

Since his retirement at the beginning of 2003, Jeff Ullman has been working with PhD alum Ramana Yerneni, systems programmer Alan Beck and former research associate Murthy Valiveti of Gautami Software to develop a teaching aid called OTC (On-line Testing Center). Their goal is to reduce the cost of education by automating those parts of a course that are most easily replicated. Using a technique called “root questions,” OTC encourages students to work ordinary long-answer homework, and then samples their knowledge in a way that allows automatic grading of the work. The system also includes a number of laboratories for database courses that automatically check the student's programming in languages such as SQL. OTC supported a number of database courses at Stanford during the 2002-03 academic year. Servers at Stanford also supported courses at North Carolina State, UC Santa Cruz, National Technical University of Athens, and the University of Leipzig. Except for the course in Athens, which was a discrete-math course, these were all database courses. However, the system can be used for courses in almost any discipline. There are plans to develop course materials in Bioinformatics and in a number of subfields of CS during this year. A demo, from the point of view of the student, is available at OTC Demo (http://bess.stanford.edu:8181/CS145-demo/). There also is on-line documentation available, including OTC Documentation (PPT) (http://www-db.stanford.edu/~ullman/pub/145com.ppt) and OTC Documentation (PDF) (http://www-db.stanford.edu/~ullman/pub/otc.pdf).

To close this research summary, here is an update on a project I mentioned in last year's newsletter. As you may recall, Marc Levoy and his students digitized 1,186 fragments of the Forma Urbis Romae, a giant marble map of ancient Rome. With guidance from Prof. Jennifer Trimble in the Classics department, Marc and his students have creating a geometric, photographic, and textual database of the map. With help from Leo Guibas in our department and his students, they're trying to solve the jigsaw puzzle. Well, this June, Marc and his student David Koller traveled to Rome to test the half-dozen matches David has found (so far). Let me quote from an email I recently got from Marc. This sounds like it came straight out of an Indiana Jones movie!� (And here is a picture of David “supervising” the activity.)

“It was an incredibly hot, incredibly exhausting, incredibly exciting day. When we reached the Museum of Roman Civilizations, we found that they had moved the 20 crates containing the Forma Urbis Romae fragments upstairs into a gigantic, un-air-conditioned exhibition hall. It was easily 100 degrees in there. We also discovered a bigger crowd than expected. Half a dozen archaeologists had traepsed [sic] out from the city to watch us open the crates.

David Koller and I were nervous as hell. It seemed to take forever for the beefy guys the museum hired for the job to actually open the crates, lift the fragments out, unwrap them, and lay them down on long tables. But then the moment of truth for each proposed match came in rapid-fire sequence.

The first match David found (back in February) included one of the fragments that was discovered two years ago and sent to Stanford for scanning. [.] Well, that match actually locks together with its mate; it *feels* like a fit. [.] The archaeologist who had found the painted fragment in his excavation pit two years ago performed the test. When he saw that they locked, he excited yelled for everybody else to come over and look, “Ragazzi, attacca!” ("Guys, it fits!").

In fact, every match we tested today seems right!� Due to erosion, none of the other matches lock together - some are many centimeters apart, but all the clues seem right: fragment thickness, veining direction, hairline fracture patterns, crystalline structure, etc. Some of these clues are things too fine for us to see in our 3D models. All the archaeologists present agreed that these matches look right. (Of course, authoritative acceptance of them will only come with time.)”

Marc does not say in his email whether putting the pieces together suddenly unlocked the secret trap door leading to the long-lost Roman treasure room where Julius Cesar hid all his wealth. I am waiting for Marc to return with all the gold; that ought to solve our budget crisis!!

New Faculty

I am delighted to report that three new faculty will be joining the department.

Alex Aiken was a professor at UC Berkeley until he “saw the light” and decided to come here! His research involves tools for detecting errors and checking specifications of software, type systems, static program analysis and abstract interpretation, constraint resolution algorithms, parallel programming, and language design. Alex received his BS in Computer Science and Music from Bowling Green University in 1983 and his PhD from Cornell University in 1988. Alex was a Research Staff Member at the IBM Almaden Research Center before joining the Berkeley faculty in 1993.

Sebastian Thrun was a professor at CMU until he too “saw the light” and decided to come here! Sebastian is interested in artificial intelligence, machine learning, and robotics. The questions that drive his research include: How can we build software that enables robots to accommodate the uncertainty that arises naturally in real-world domains? What mechanisms can enable robots to learn from interaction with the environment and with people? How can we build robots that learn and improve over their entire lifetime? Sebastian received his PhD from the University of Bonn.

Tim Roughgarden also saw the light, and will be joining us next year (September 2004). Tim recently got his PhD from Cornell, and will be spending a post doc at Berkeley this year. Tim received his BS from our department. In fact, some of you may remember him from your days here when he was also a disc jockey at KZSU, I am told. But I do not know if he was any good. as a disc jockey, that is. as a computer scientist he is great! He works on game theory applied to computer networks, among other things.

Promotions & Retirements

I am also delighted to report that three of our faculty have been promoted to the rank of associate professors with tenure: Dan Boneh, Nick McKeown, and Balaji Prabhakar.

Dan works in the computer security area (see above), while Nick and Balahji work on computer networks. If you are interested in our networking activities, please take a look at the home page of our Stanford Networking Research Center (http://snrc.stanford.edu).

Jeff Ullman retired in December 2002. However, little has changed for Jeff. He is still teaching and doing research at Stanford. As Jeff himself says, the only thing that's changed is that we no longer pay him! Anyway, to celebrate Jeff distinguished career, we held a symposium in his honor in December. About 60 of Jeff's former and current students and collaborators attended. You can see photos of the event here.

In Memoriam

I again have some sad news to report in this newsletter.

Bob Engelmore passed away on March 25, 2003, while vacationing with his family in Hawaii. Bob joined the Stanford Computer Science Department in 1970 and retired in 1998. He served as Director of the Heuristic Programming Project and Executive Director of the Knowledge Systems Lab (KSL). In addition to his research role in KSL, Bob was a willing and valued contributor to the department; he served on committees, advised students, and worked with the Computer Forum.

John G. "Jack" Herriot joined the Math Department in 1942 and again in 1946 after two years as a physicist with Ames Aeronautical Laboratory at Moffett Field. In 1953, Stanford University received its first computer and Professor Herriot, a pure mathematician, became the first director of the newly founded Computation Center. In the spring of 1955, he taught the first programming course, “Theory and Operation of Computing Machines,” to 25 students using an IBM Card Programmed Calculator, Model II. In January 1965, he moved to the Computer Science Department, which was being formed. He served as acting department chairman from 1966-67 and 1972-73. His principal interests were in numerical analysis, especially in the development and description of algorithms useful for solving various problems arising in numerical analysis.

Professor Herriot passed away March 16, 2003, at the age of 87. The John Herriot Memorial Fund is being established to sponsor events and students in his name. Contributions may be sent to Stanford University, c/o Computer Science Department, Gates #275, Stanford, CA 94305-9020.

One of our undergraduates, Vusumzi Silwana (Class 2001) passed away. Vusi had been on leave from our program, but since he had completed his requirements, he was awarded a posthumous BS in Computer Systems Engineering at our commencement ceremony on June 15.� His advisor was Julie Zelenski.� A copy of the letter written about Vusi by a couple of his friends, and which was read by Julie at Commencement, can be found here.� The letter was originally published in the Stanford Daily on April 25, 2003.

Professor Andrew Kosoresow, Columbia University, passed away in early June. Andrew had received his PhD under the direction of Professor Nils Nilsson.

Faculty Awards

Daphne Koller, associate professor of computer science, was honored with the 2003 Allan V. Cox Medal. The medal is awarded annually to a faculty member who has established a record of excellence directing undergraduate research over a number of years. The award is given once a year, and Daphne was the first person from Stanford Engineering to ever win it! One of Daphne's major contributions was starting our CURIS program, which provides research opportunities for our undergraduate students. Every summer, 30 to 40 undergrads sign up to work with faculty in our department. It is a great experience for the students and for the faculty. At the end of the summer, the students present their work at a big poster session, and you can see photos of last summer's poster session here.

John McCarthy, professor emeritus of computer science and a pioneer in artificial intelligence (AI), received the Benjamin Franklin Medal in Computer and Cognitive Science. The Franklin Institute in Philadelphia bestowed the award, lauding McCarthy for “multiple contributions to the foundations of artificial intelligence and computer science, including the development of the LISP language, the invention of time-sharing interactive programming, and key developments in the application of formal logic to commonsense reasoning.”

Nils Nilsson received the Research Excellence Award at the forthcoming International Joint Conference on Artificial Intelligence (IJCAI-03) in Acapulco, Mexico.

Bill Dally became a fellow of the Association for Computing Machinery (ACM).

The SIGCSE Award for Outstanding Contribution to Computer Science Education was presented to Eric Roberts, Professor of Computer Science and Senior Associate Dean of Engineering.

Mendel Rosenblum was awarded the 2002 ACM/SIGOPS Mark Weiser Award for creativity and innovation in operating systems research.

David Cheriton won the 2003 Sigcomm Award. This is a very prestigious award - arguably the most prestigious in networking.

Pat Hanrahan was designated the 2003 winner of the Steven A. Coons Award for outstanding creative contributions to computer graphics. This award is made once every other year, usually to a very senior member of the graphics community who is an outstanding leader and mentor. The award is the highest honor a researcher in computer graphics can receive.

Oussama Khatib became an IEEE Fellow and an Honorary Professor at Harbin Institute of Technology (HIT) in Harbin, China. He is also the President of the International Foundation of Robotics Research, IFRR.

Ron Fedkiw hit the jackpot this year with a Packard Fellowship and an Alfred P. Sloan Fellow award.

Ken Salisbury received an Okawa Award for “significant contributions to information communications research.”

Ed McCluskey� received the IEEE Computer Society Test Technology Technical Council (TTTC) lifetime Achievement Award in October, 2002, and the IEEE VLSI Test Symposium Best Panel Award� in April 2003.

Your truly was elected to the National Academy of Engineering.

Jennifer Widom and her student Glen Jeh received a Best Paper Award at the 2003 World Wide Web (WWW) Conference in Budapest, for their paper “Scaling Personalized Web Search.”

And finally for the awards category, Don Knuth received another honorary PhD. I'll quote here from an email Eric Roberts sent describing the event (see photo):

“I just got back from a delightful event here in Thessaloniki that I thought was worth sharing with all of you back at Stanford. At the conclusion of this year's Innovation and Technology in Computer Science Education (ITiCSE), the University of Macedonia awarded honorary doctorates to Don Knuth and Christos Papadimitriou, both of whom had been keynote speakers at the conference. The awarding of the degrees was an interesting mix of formal ceremony on one hand and light-heartedness on the other. Don gave a charming talk on "Theory and Practice" laced with wonderful stories, Greek etymologies, and some serious thoughts about the mutual dependence of these two foundations of our discipline. Christos -- speaking in Greek with simultaneous translation -- gave a more serious talk on "Economics, Computer Science, and the Internet" that looked at the application of game theory to networking, citing specifically the work of Tim Roughgarden, our newest faculty colleague. But the pi�ce de r�sistance came at the end of the evening when Don and Christos sat down together at the piano to play a duet by Debussy, the first movement from "Six Epigraphes Antiques."� Given that Debussy wrote this music as background to a cycle of Sapphic poems and that the first movement was designated as an "Ode to Pan, god of the summer wind," the choice was perfectly suited to the Greek setting (not to mention the 100+ degree temperatures).”

Computer Forum News

The Annual Affiliates Meeting relocated to the Alumni Center. It received rave reviews for the keynote speaker, Dr. Robert J.T. Morris, Director of IBM's Almaden Research Center and banquet speech from Professor Matthew Scott, Chair of Bio-X. The 5th Security Workshop expanded once more, as 100 attendees from industry and academia crowded the Fisher Conference Center.

As a result of the economy, hundreds of CS/EE students swamped the sixteen recruiting companies at the Job Fair 2003. Paying no heed to the supposed downturn, students sold their souls for T-Shirts, bouncy balls, and Rubik's Cubes.

If newsletters are your thing (you are reading this one after all), be sure to sign up for the monthly Forum News (subscribe@cs.stanford.edu). While we are in “shameless promotion mode,” I should mention the Seminar Calendar (http://forum.stanford.edu/calendar), a new feature launched this year. In order to expand our capability to interact with our affiliates, the Forum is creating a database of Computer Science and Systems Research Projects to allow them to discover where their research interests lie in the multitude of labs and groups. As ever, the Forum, with your help, will proudly take on this new challenge!

Awards and Honors

Computer Science was this year's recipient of the Stanford's Outstanding Departmental Advising Award. This award has been given each year for the last four or five to the major department or program that distinguishes itself in providing an excellent advising experience for its undergraduates. Students nominate departments for the award and a committee at the Undergraduate Advising Center makes the final decision after reviewing submitted materials.

Claire Stager was a recipient of the 2003 Amy Blue Award. These are given to Stanford staff who are dedicated to accomplishment, committed to people, and are energetic and passionate about their work. Claire certainly fits the bill!

Distinguished Service Awards went to Jam Kiattinant and Kathi DiTommaso.

Each year, we get to nominate one PhD thesis for the ACM Thesis Award. This year, we nominated the thesis of Eyal Amir, entitled “Dividing and Conquering.”

Other News

Ron Fedkiw received a screen credit on the Terminator 3 movie that was released July 4. The work Ron did on that movie included simulations of the liquid female terminator, nuclear explosions, and cloth for digital doubles. �I can't wait to see it!

David Dill has been leading an effort to improve electronic voting. To quote from a site David and others have set up to make people aware of the issues: “As a result of problems with elections in recent years, funding is being made available at all levels of government to upgrade election equipment. Unfortunately, some of the equipment being purchased, while superficially attractive to both voters and election officials, poses unacceptable risks to election integrity - risks of which election officials and the general public are largely unaware. [Because of these problems it is] crucial that voting equipment provide a voter-verifiable audit trail, by which we mean a permanent record of each vote that can be checked for accuracy by the voter before the vote is submitted, and is difficult or impossible to alter after it has been checked.”� If you are interested in issues related to electronic voting, visit David's site at Electronic Voting (http://www.verifiedvoting.org/).

Armando Fox's work on Recovery-Oriented Computing (ROC) was the cover article in the June 2003 issue of Scientific American. Accepting that transient software and hardware failures are facts of life, his group's work on “design for recovery” includes developing techniques such as software-component-level “micro-reboots” to make partial recovery inexpensive, and building dedicated state stores that are “crash-only.” In other words, it's safe to crash any node at any time without losing data or imperiling online availability. The techniques were tried out in prototype form this past summer at Microsoft Research and BEA Systems. ROC also included other projects being done jointly with Dave Patterson at UC Berkeley.

Professor Emeritus Ed Feigenbaum, and his former undergrad CS student David Brunner had their book “The Japanese Entrepreneur: Making the Desert Bloom” published in Japan in December 2002. It was published only in Japanese by Nihon Keisai Shimbun (the financial news group of Japan). The manuscript, of course, was written in English, and is available at the Stanford Japan Center website here (http://www.stanford-jc.or.jp/research/publication/books/20021217.html).� In this book, Feigenbaum and Brunner enter the political debate on the establishment in Japan of “special economic zones.” After analyzing problems of the Japanese entrepreneurial environment that inhibit the growth of startup companies, they argue for the establishment of “special entrepreneurial zones.” The goal is to experiment with the conditions required for startup growth in Japan and to create some success stories.

As you probably know, our undergraduates organize various social events during the year. I happened to take my camera to the Disco Bowling Night.� You can see my photos here.

At the beginning o each academic year, we have a party to welcome all our new CS and CSL students.� You can see some pictures of the event here.� Take a look and see how much fun we had. Don't you wish you were still a student here???

As I reported last year, we have a yearly Stanford-Berkeley Day, where students and faculty from both CS departments get together. (Our friends at Berkeley incorrectly call the event the Berkeley-Stanford Day.)� This year we met at Berkeley, and attended sessions on artificial intelligence, bio-informatics, and computer science theory.� You can see pictures of the event here.

As I mentioned earlier, our department's budget was reduced, so we had to become more fiscally responsible. One of the first things to go was our bottled water. This created an uproar, and for a while there I was afraid of losing my job! To convince my colleagues that drinking tap water was not going to kill them, I organized a water tasting test at our Faculty Retreat. I had several unlabeled bottles of water, some bottled, some tap. Everyone was asked to guess which was which. (Between the sips of water, people had to cleanse their palate by drinking wine!)� You can see the photos of the water tasting event here (photos A50 through A69).� Overall result: a couple of people got lucky and were able to detect the tap water. The rest could not tell the difference! Incidentally, next year our faculty retreat will NOT be in Santa Cruz due to budget constraints.

In case you are still not tired of seeing my photos, here are some of this year's graduation ceremony.� Terry Winograd gave a short speech, and then, while Russ Shackelford read the names of the graduates (and later John Mitchell read the names of PhD graduates), and I handed out the diplomas.

In closing last year, I told you about the palm tree curse. Well, unfortunately, as you can see, the palm tree is still missing.� Let's hope palm tree #4 will show up by the next newsletter.� However, to end on a positive note, the Bio-X Clark Center (right next to Gates Hall) is almost finished, as you can see here and here.� Profs. Latombe, Batzoglu, Salisbury and Khatib have already moved into the new building.

That is it for this year. Have a wonderful 2003-04!

Till next year,

Hector Garcia-Molina

P.S. Please send any alumni news to alumninews@cs.stanford.edu so I can include the information in next year's newsletter.