15-410 Homework 2

This homework assignment is due Friday, December 8th at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, please turn your solutions in on time.

Homework must be submitted (online) in either PostScript or PDF format (not: Microsoft Word, Word Perfect, Apple Works, LaTeX, XyWrite, WordStar, etc.). Except as otherwise directed (in the crypto question), turn in your answers as either .../$USER/hw2/$USER.pdf or .../$USER/hw2/$USER.ps. If you use another filename, there is some risk that your solutions will not be credited to you.

As usual, you may discuss this assignment with others, but you must then go off by yourself to write up the solution.

Question 1 - Public Key Practicum

This question is not hard, but it does take some time to do it right. Please don't leave this question to the last minute, and think carefully about what the various steps accomplish.

Follow the directions in gpg.html to generate a PGP key ring, containing public and private keys for digital signature and encryption purposes. Do not turn the key ring in to your hw2 directory. Instead, follow the directions on how to export the public key information from the key ring into a file, hw2/$USER.asc. Then create a secret message for the course staff, in hw2/$USER.secret.asc.

Question 2 - Kerberos

Imagine a hypothetical network printing service authenticated and encrypted via Kerberos. We will focus on a part of the service which allows a user to receive a status listing of the estimated completion time of each of the user's print jobs.

At a high level, a list-queue program acting on behalf of a user sends a LIST message to the print server, which sends back a message containing one long string describing the status of multiple jobs (you can imagine that each job appears on one "line" in the string). To avoid students becoming bitter at one another, we wish to avoid situations where one user can determine the status of another user's print jobs.

Part A

Assume the list-queue program has access to a valid, unexpired Kerberos ticket (as described in class) for the "printer" service. What information should the list-queue program send to the printer-server program in a LIST message? Try to use the notation from the lecture slides; be specific about what form each piece of information would take in the message and how the server would consider and use each piece of information.

Part B

Briefly yet convincingly explain this apparent paradox: Joe can see every message sent by list-queue from Kelly's machine to the print server, and see every reply sent from the print server, but doesn't know what commands Kelly is sending and can't read the print server's responses. If you can, explain why Joe remains in the dark even if he also sees all messages transmitted between Kelly's machine and the central Kerberos server.

Question 3 - Kernel Runtime Environment

Virtual memory works differently from one platform to another. For example, when a PowerPC CPU receives an interrupt or experiences an exception, including a system call, the hardware automatically and atomically performs these steps:

Copy two registers (roughly equivalent to %EFLAGS and %EIP) into designated backup registers (imagine %S_EFLAGS and %S_EIP),
Copy four general-purpose registers, %R0 through %R3 into backup registers %S_R0 through %S_R3
Adjust %EFLAGS to turn interrupts off, turn virtual memory off, and enter supervisor mode (as you can see, other architectures make do with fewer "special" registers than x86 uses),
Set %EIP to a specific hardcoded constant value depending on which "surprise" forced the processor into kernel mode (each surprise type invokes a small fixed-size scrap of code, something like eight instructions, which jumps to the "real" handler, so the page-fault handler might start at 0x0000E000 and the illegal-opcode handler might start at 0x0000E020)

By the way, the PowerPC equivalent of IRET atomically copies %SEFLAGS, into %EFLAGS and %SEIP into %EIP.

Part A

What requirement or requirements are forced on the authors of PowerPC kernels due as a result of all "surprises" turning VM off?

Part B

Do you agree or disagree with the decision to automatically disable interrupts in response to all "surprises"? Explain your reasoning.

Helpful Hint

By the way, if you think you are having AFS permission problems, try running the program located at
% /afs/cs.cmu.edu/academic/class/15410-f06/pub/access_hw2

[Last modified Monday December 04, 2006]