| CPSC 220 | Introduction to Computer Architecture | Fall 2008 |
In this lab, you will write and work with programs that use the stack to store local subroutine data. You should make sure you understand your lecture notes on the stack and chapter 10 from the textbook before starting this lab.
Create a lab11 directory within the ~/cs220 directory that you created in lab 1 for use in this lab. Change to the newly-created lab11 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab11 to your new lab11 directory. The following commands should work (note: the "-r" in the cp command allows for copying directories as well as files):
bash$ mkdir ~/cs220/lab11 bash$ cd ~/cs220/lab11/ bash$ cp -r /classes/f08/cs220/labs/lab11/* ~/cs220/lab11/
Note: the rest of this lab assumes you are in your lab11 directory.
Your directory should also now contain 3 files for assembling, running, and debugging Larc programs: asm, sim, and db. See the previous lab assignments for details on how to run these. Note: you will not be using a trap handler in this assignment, so you do not have to use the special assembling and simulating options from lab 10.
Your directory should also contain a file print-reverse.s which contains a program for printing a sequence of inputted numbers in reverse. It contains a buffer overflow vulnerability and in the second exercise, you will use this vulnerability to subvert the program.
There are two exercises for this week's lab due in one week.
In this exercise, you will write a complete assembly program called gcd.s, which will use the stack for storing local subroutine data. It will prompt the user for two positive numbers and print out the greatest common divisor (GCD) of those two numbers. It will use recursion to find the GCD.
In particular, your program will need four subroutines, which must follow the specifications below (if you do not follow the specifications you will not receive full credit):
main. A main subroutine that follows ".text". This will call the other subroutines and exit when finished. In particular, it will call get_number (discussed below) twice to get two positive numbers from the user. It will then call gcd (discussed below) to compute the greatest common divisor of those two numbers. Finally, it will exit.
get_number. This subroutine will prompt the user for a positive number and read in the number. If the number is not positive, it should print an error message and continue reading a number until it receives a positive number. It will return this number to main in register 1 (note: it must use register 1).
gcd. This subroutine will find the greatest common divisor (GCD) between the two numbers, taken as parameters from main. It will use recursion to find the GCD. In particular, it will use Euclid's algorithm:
gcd(x,y) = x -- if y is 0
gcd(y,x%y) -- otherwise
Note: x%y is the remainder of x divided by y. gcd will call the subroutine rem (discussed below) to compute x%y. Note also: your subroutine must follow the definition above, i.e., it must use recursion (it cannot use loops). Finally, gcd must take the first parameter (i.e., the first number) in register 2, the second parameter (i.e., the second number) in register 3, and return the result in register 1 (note: it must use these particular registers).
rem. This subroutine computes the remainder when dividing one number by another (i.e., modulus -- %). It returns the result to the caller (i.e., gcd). rem must take the first parameter (i.e., the first number) in register 2, the second parameter (i.e., the second number) in register 3, and return the result in register 1 (note: it must use these particular registers).
In addition, each subroutine must preserve the values of all registers except register 1. In other words, the values of each register besides register 1 should be the same when the subroutine starts as when it finishes. Each subroutine must save its registers to the stack. At the beginning of each subroutine, a new stack frame must be allocated (as discussed in class) and the modified registers besides 1 must be saved to that frame. At the end of each subroutine, just before returning, the stack frame must be deallocated and each modified register must be restored. Note: this must be done even if the subroutine is not recursive, although you can omit this if the subroutine does not need to preserve any registers.
As in previous labs, make sure you comment your code so that it is easy to read and understand.
In this exercise, you will play the role of a hacker trying to subvert a program. (Note: I am not encouraging you to become a hacker, but to prevent computer attacks you must be able to think like an attacker). The program reads in a sequence of numbers (terminated when the user enters 0) and prints them out in reverse order. To do this, the program reads the numbers in and stores them into an array in reverse order. It then prints them out, which prints them in reverse since they were stored in reverse order.
For example, here is an example run of the program (user input is underlined):
Enter number: 1 Enter number: 2 Enter number: 3 Enter number: 0 array: 3 2 1
Unfortunately, the program fails to check whether the length of the array in memory is exceeded (which is 15 in this case). Therefore, a clever hacker can overflow the array, corrupt a return address, execute their own attacker code, and subvert the program. Your task is to do this and force the program to print out "zoinks!\n" to the screen and exit. You have been given the assembly program to look at, but you cannot modify it (since the attacker has no way of doing this). Instead, you must supply the original program with appropriate inputs, which hijack the program, print "zoinks!\n" to the screen, and exit.
Here are some details about the program you must subvert. It is made up of three subroutines. A main subroutine stores an array of 15 elements on the stack and calls read_array_backwards. It gives read_array_backwards the address of the last element of the array. read_array_backwards reads in the numbers storing them in reverse order. It fails to check whether it has exceeded the length of the array, and consequently, this subroutine has a buffer overflow vulnerability. When it returns (assuming it wasn't subverted), main then calls print_array giving it the starting address of the array. print_array prints the elements of the array (which will be in reverse since they were stored in reverse). Note: it does not print out elements with value 0 since these were either not entered by the user or were the terminating value. This subroutine actually does check the length and does not have a buffer overflow vulnerability.
In more detail, your job is to overflow the buffer when entering numbers in read_array_backwards (by entering more than 15 numbers) and corrupt some return address. The return address should point back into the buffer where you've entered a short program, which will print "zoinks!\n" to the screen and exit. Therefore, when you run the program with these inputs, the program should be interrupted in the middle of its execution, "zoinks!\n" should be printed to the screen, and the program should exit.
You should store your attacker input in a file called print-reverse.input along with annotations that indicate what each separate inputted-number means. You will be graded based on this file.
Verify that your lab11 folder contains all of the files you created or modified for this lab (e.g., gcd.s and print-reverse.input), then copy your entire lab11 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). For example, if your working directory is ~/cs220/lab11/ then you could do the following:
cp -r ~/cs220/lab11 ~mcorliss/handin/cs220/username
where username is replaced with your particular username (e.g., mcorliss).