CS155: Homework #1

Spring 2010

Due: Tuesday, Apr. 27

Problem 1: Trusting trust

In class, we discussed Ken Thompson's paper, "Reflections on trusting trust," in which he describes a technique for installing an undetectable login backdoor by adding a second backdoor to the compiler. The backdoored compiler inserts the appropriate backdoors when compiling the login program and the compiler itself. Once the binary of the compiler, used for bootstrapping future systems, implements the backdoor, any trace of tampering can be removed from the source. In this problem, we will explore a technique for detecting such an attack.

Assume we have two C-language compilers, for example GCC and MSVC. We suspect that nefarious hackers have inserted the Thompson backdoor into the GCC binary on our Linux system, but we believe that these hackers are believers in the free-software movement, and so wouldn't cooperate with Microsoft's compiler division. It's impractical to build an entire Linux system with MSVC, since Linux programs are written to expect GCC's extensions to the C language. But we should be able to get MSVC to build GCC; though this would most likely require some modication to GCC. Describe how we can reliably detect the presence of a GCC backdoor by building GCC with MSVC.

Problem 2: Control hijacking

(a) In x86 the stack grows downwards. Explain how a stack-based overflow attack would work if the stack grew upwards instead.

(b) How would you implement StackGuard in an architecture where the stack grows upwards? What would be different from StackGuard on the x86?

(c) How would you implement LibSafe in an architecture where the stack grows upwards? What would be different from LibSafe on the x86?

(d) Suppose you find a memory leak in a third-party library, e.g. the library cleanup function forgets to call free on a certain pointer p. You notice that some applications fix the problem by freeing the memory themselves. How could you fix the library cleanup function to free p without introducing a double-free vulnerability in applications that free the memory themselves? You are only allowed to change the library. If you need to make an assumption about how the free function works, make sure to state your assumption explicitly.

Problem 3: Sandboxing

(a) Explain when would you use VM-based sanboxing rather than system call interposition.

(b) Explain when would you use system call interposition rather than VM-based sanboxing.

(c) In class we discussed a covert channel between two VMs based on CPU utilization and a synchronized clock between the VMs. One might try to block this covert channel by preventing the VMs from synchronizing their clocks, e.g. by presenting each VM with a different time of day. You may assume the clocks run at normal speed, but are shifted by a random amount for each VM. Explain how an attacker can defeat this defense.

(d) Suggest another method by which the covert channel based on CPU utilization can be blocked.

Problem 4: Confidentiality and integrity

In lecture 4, we discussed the Bell-LaPadula and Biba access control models.

(a) Identify which model is sometimes summarized with the statement, "Read below, write above." Explain why this principle preserves confidentiality or integrity.

(b) Identify which model is sometimes summarized with the statement, "Read above, write below." Explain why this principle preserves confidentiality or integrity.

(c) Is it possible for an access control system to support both models and provide both confidentiality and integrity? Explain.

Problem 5: Code analysis

In lecture 5, we discussed taint analysis and one of the readings for that lecture discusses the tainted object propagation problem. Taint analysis is a general approach for finding many kinds of program bugs. In most forms of taint analysis, a value from an unknown or untrusted source is considered tainted. If the value is tested or manipulated in some way, then it may become untainted. If a tainted value is used an argument to a sensitive operation, then an error is reported. For example, PERL user input is considered tainted, and an error is reported if tainted values are used in system calls. If a tainted PERL value is compared to a pattern that is contained literally in the program, and not read from some other source, then it is considered untainted.

Taint analysis can be used to find buffer overflow vulnerabilities in source code by disallowing tainted array indices. Explain why a value should be considered untainted only if there are checks to make sure it is bigger than some minimum value and smaller than some maximum value - it is not enough to just check that it is less than some maximum value. You may want to refer to the following Linux device driver code.

 
    /* 2.4.5/drivers/char/drm/i810_dma.c */
    if (copy_from_user(&d, (drm_i810_copy_t *)arg, sizeof(d)))
            return -EFAULT;
 
    if(d.idx > dma->buf_count) return -EINVAL;
    buf = dma->buflist[ d.idx ];
    buf_priv = buf->dev_private;
    if (buf_priv->currently_mapped != I810_BUF_MAPPED) return -EPERM;
 
    if (copy_from_user(buf_priv->virtual, d.address, d.used))
            return -EFAULT;

Taint analysis can be applied to source code, by simulated execution that keeps track of whether the values of variables could be tainted or not, or applied at run-time by keeping track (in an interpreter, for example) of whether the actual value is tainted. In a project for detecting malware via runtime taint analysis, researchers at CMU automatically insert taint tracking instructions. For example, the following code
```
 
     recv(socketfd, buf1, …);
     memcpy(buf2, buf1, …);
     y = x;
     strcpy(dummy->buf, buf1);
     dummy->fnptr();
```
is instrumented by inserting the indented lines
```
 
     recv(socketfd, buf1, …);
          NewTaint(buf1, …);
     memcpy(buf2, buf1, …);
          PropTaint(buf2, buf1, …);
     y = x;
          PropTaint(&y, &x, …);
     strcpy(dummy->buf, buf1);
          PropTaint(dummy->buf, buf1, …);
          TaintAssert(&fnptr, …); 
     dummy->fnptr();
```
The first function call creates a new taint tracking flag for buf1. The next call sets the taint flag for buf2 to the flag value for buf1, and so on. The TaintAssert function makes sure that the taint flag for the given argument does not indicate that the value is tainted. If TaintAssert is called with a tainted argument, and error is reported. Explain the error in this code and how tainting analysis catches it.

CS155: Computer and Network Security