Homework 1

CS155, Spring 2005

Due: Thursday, April 28


Problem 1

(a) Give sample C code that is vulnerable to a heap integer overflow attack. Explain how the vulnerability could be exploited.

(b) Can you propose a mechanism that would defend against such attacks?

Problem 2

TENEX was an operating system developed by Bolt, Beranek and Newman (BBN). The OS was later purchased by Digital Equipment Corporation and used as the starting point for the TOPS-20 system. TENEX provided password protection on individual files. Two features made it possible to figure out the password associated with a file relatively efficiently: a feature of paged memory, and a feature of the password comparison algorithm. The memory feature is that data can be stored on a sequence of pages, but if a process tries to read across a page, and the second page is not in memory, a page fault occurs. Since a user can test to see whether a page fault has occurred, a user can test if a process tried to read a given page. The password comparison algorithm compares user input to the file password one character at a time, stopping at the first character that does not match.

Explain how you could use a combination of data extending over multiple pages, and characteristics of the password algorithm, to compute the password for file f of length n in time proportional to n.

Problem 3

In class we described how LibSafe defends against stack buffer overflows. Can you adapt this mechanism to work in the heap? If so explain how and what additional functionality you would need from the memory manager. If not, explain why not.

Problem 4

Coding rules and program execution rules may be expressed using finite automata. When the Meta-Compilation (MC) system is used to check source code for security problems, the checks are given by finite automata. For example, lecture 4 contains a slide showing an automata for the rule, "when an integer is received from an untrusted source, an upper bound and a lower bound check must be applied before calling any of the functions memcpy, copyin, copyout, using the integer in an array reference, or using the integer as a bound in an iterative loop." This automaton has a state labelled ERROR. The idea is that as MC reads code, it keeps track of the current state in the automaton. If a state labelled ERROR is ever reached, then MC reports an error in the code. We say that an automaton enforces a rule if the ERROR state is reached whenever program source code violates the rule. Draw finite automata representing the following rules, to be enforced in source code by something like the MC system. If you think the rule cannot be expressed by a finite automaton, explain why.

(a) If a program reads from a file, it must open the file first

(b) There must be an assignment d[n-1] = '\0' after after each call strncpy(d,s,n).

(c) A memory location must be allocated before it is read.

(d) A memory location must  not be freed twice.

(e) A program must open a file before reading from it and eventually close it afterwards,

(f) The return value of a call to strdup must be checked to make sure it is not null.

Problem 5

One idea used in virus checkers is loop through all the entry points to a file, and look for possible viruses in the next sequence of bytes.

(a) Why would a virus writer design virus code to place infections just after program entry points?

(b) How would a virus writer circumvent virus checkers that only look at file entry points?