15-410 Homework 2

This homework assignment is due Friday, December 9th 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, XyWriter, 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 pgp.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 - Nuts & Bolts

In "the old days" before ELF, Unix systems used an executable file format called "a.out" which contained text, data, and bss sections, but no rodata section. This was more or less "ok" because back in those days C didn't contain the "const" (read-only constant) keyword. However, this meant it was possible for programs to go wrong in subtle ways.

Consider this program:

void editstr(char *s)
{
  if(strcmp(s + 1, "red") == 0)
	strcpy(s + 1, "lup");
}

int main(int argc, char *argv[])
{
  printf("%s\n", "fred");
  editstr("fred");
  printf("%s\n", "fred");
  return(0);
}

Exactly what this program meant was unclear. On some systems it would print

  fred
  fred

but on others it would print

  fred
  flup

Part A

How could the second output happen?

Part B

ANSI C changed the type of a quoted string from "char *" to "const char *", meaning that "fred" now means a pointer to an array of five read-only chars ('f', 'r', ...), so the program above is clearly illegal and implementations are encouraged to treat invocations of editstr() such as the one above harshly, such as by delivering a SIGSEGV.

Imagine you are the implementor of a shiny new ANSI C compiler and associated utilities on an old legacy a.out system. How could you arrange for this program to crash even though the Unix kernel you're running on doesn't have the concept of an rodata region?

Question 3 - Platform Issues

What class of problem can be addressed on a uniprocessor but not a multiprocessor by disabling interrupts? Explain why the technique doesn't work on multiprocessors and briefly explain a technique that will work. If "class of problem" doesn't make sense to you, give us three specific examples.

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-f05/pub/access_hw2

[Last modified Saturday December 03, 2005]