Homework 1

CS155, Spring 2003

Due: Tuesday, April 29th, 2003.

Problem 1

In Lecture 4, we saw how the Meta-Compilation (MC) system can be used to check source code for security problems. In the MC system, a rule us presented as a finite automaton  (diagram with circles and arrows , as shown in the "Sanitize integers before use" slide). Here is code from a Linux driver that contains an error

    /* 2.4.4­ac8/drivers/block/cciss.c: cciss—ioctl */ 
    if (copy—to—user(...)){ 
        cmd—free(NULL, c); 
        if (buff != NULL) kfree(buff); 
        return( ­EFAULT); 
    if (iocommand.Direction == XFER—READ) 
        if (copy—to—user(...)){ 
            cmd—free(NULL, c); 
     cmd—free(NULL, c); 
     if (buff != NULL) kfree(buff); 

Write an automaton that catches this kind of error in freeing buffers and explain how the automaton will find an error here. On what line will your automaton first detect and report an error? Explain briefly.

Problem 2

In Lecture 5, we saw that the following steps can be used to break out of a chroot jail:

    mkdir(/temp) /* create temp directory */
    chroot(/temp) /* now current dir is outside jail */
    chdir(“ ../../../.”) /* move current dir to true root dir */
    chroot(“.”) /* out of jail

One reason this works is that the string argument to the third command (or system call) moves the current working directory up to the true root directory. As written, the command assumes that the current directory is only a couple of levels below the true root. However, the command can be repeated as many times as it is needed. Propose a method for modifying the implementation (or wrapping) chdir that will prevent this attack. Your modified chdir should allow ".." to appear in the argument.

Problem 3

This problem is about safety properties of programs. For the purposes of this problem, a program defines a set of executions, and each execution is a sequence of states.  For example, suppose the program G has the following behavior: reads from an input file; if the word "dog" appears in the input, write some string to an output file. Then the set of executions of G include a single state in which the input file is empty and G does nothing, a sequence of states in which G reads from an input file that does not contain the word "dog" and halts, and a sequence of states where G reads from a file containing "dog" and writes to the output file.

Suppose P is some program property, i.e., for every program G, either P(G) is true or P(G) is false. Assume that P(G) depends only on the set of executions of G, so that if G and H have the same executions, P(G) iff P(H). 

Property P is a safety property if there is some set S of finite sequences of states such that for all programs G, the property P(G) is false iff there is some sequence s from S that is an initial segment of some execution of G. The idea is that sequences in S should not happen, and P(G) is false if some execution begins by doing some forbidden sequence s from S and then (possibly) some other things afterwords.

Here is an example safety property: a program should not read from /etc/passwd and then write to standard output. The forbidden set S is all execution sequences s that contain a read  from /etc/passwd and then write to standard output.

For each of the following properties, say whether it is a safety property and give the forbidden set. If it is not a safety property, explain why.

(a) A program should not write to memory outside of its allocated segment.

(b) A program should write at most 1MB of file space.

(c) If a program opens a file, it should close it.

(d) A program should terminate.

(e) If a program reads from /etc/passwd and writes to standard output, the output it writes should not depend on whether user joe appears of /etc/passwd.

Problem 4

Consider the following code snippet:

  if (!stat("./file.dat", buf)) return;   // Abort if file exists.
  sleep(10);                              // Sleep for 10 seconds.
  fp = fopen("./file.dat", ``w'');
  fprintf(fp, ``Hello world'');

a. Suppose this code is running in a setuid root program. Give an example of how this code can lead to unexpected behavior that could cause a security problem. (try using symbolic links.)

b. Suppose the sleep(10) is removed from the code above. Could the problem you identified in part (a) still occur? Explain.

c. How would you fix the code to prevent the problem from part (a)?

Problem 5

We discussed password management very briefly in class. Read the description of a password maintenance shareware program at http://www.softdd.com/password-manager/index.htm and think about the kind of security provided. Compare the three options mentioned (plaintext file on your pc, encrypted file on your pc, and plaintext file on a diskette) to the options of (i) trying to remember all of your passwords or (ii) storing them in a text file using a standard editor. In your comparison, list the kinds of attacks that could be carried out. What techniques considered in this class might be useful in running shareware like this?

Important note: this is not a recommendation for a particular piece of software.  We do not know anything about the program described on this page; we have not installed or tried it. 

Problem 6

A recent proposal for preventing stack buffer overflow attacks is based on encrypting the return address on the stack. When the program starts it generates a random number K and stores K in some fixed memory location. Whenever a function is called a new stack frame is created. However, rather than writing the return address R in the stack frame, the code writes R ^ K where ^ stands for bit-by-bit XOR. When the function terminates and is about to return to the caller it first XOR's the return address location on the stack with the value K and only then executes the return.

a. Explain why this mechanism can potentially make it harder to mount a buffer overflow attack.

b. Give sample code that is vulnerable to a buffer overflow exploit even if this mechanism is used. Hint: use a double overflow where the first exposes K. Recall that K is stored in a fixed memory address.