CSE 378 Winter 2011 Homework 2

Due: Monday, February 7^th at 11:00pm

The goal of this assignment is to learn about MIPS functions, calling conventions, and stack layout. There are two parts.

Part A: Implementing Binary Search

For this part of the assignment you'll write your old friend binary search - a recursive, average-case O(logN) searching routine - in assembly. However, instead of searching a sorted array of integers, you'll search a lexicographically-sorted array of strings. The pseudo-code for the binary search of a non-decreasing lexicographically-sorted array of strings from array index low to array index high, inclusive, looks like this:

/*
   Recursively searches data from index [low, high] for key, 
   returning the smallest index at which key occurs or -1 if 
   key does not occur in data between indexes low and high.
*/
int binarySearch(char* data[], char* key, int low, int high):
   if( low > high ): 
      return -1
   else: 
      int mid = (low + high) / 2
      int cmp = strcmp(data[mid], key)
         if( cmp == 0 )
            return mid
         else if( cmp < 0 )
            return binarySearch(data, key, mid + 1, high)
         else
            return binarySearch(data, key, low, mid - 1)

The template calls binarySearch on an array of sorted strings using the function signature in the pseudocode. We provide the strcmp() function. Of course, you don't have to follow the pseudocode exactly as long as you implement binarySearch in a recursive fashion and call the provided strcmp() function.

We will test your implementation on multiple string arrays with interesting properties. You may want to modify the string and array data in the template to try other values. A component of your grade will also be based on your adherence to the MIPS32 function calling conventions.

What you should do for Part A:

Start by downloading the SPIM template file.
Implement the body of the binarySearch() function.
Test your solution with SPIM.

Part B: Smashing the Stack

Now you'll use your knowledge of MIPS stack layout to "take over" a program. You will write a function in the MIPS assembly language that smashes the program's stack frame and verify it in SPIM.

Exploiting a Vulnerable Program's Stack

This simple assembly program reads in a student's NetID, verifies that the NetID is in the correct format, and returns the class grade of the student. The problem with this program is that the local, stack-allocated buffer used for holding the NetID (inside the string_sanitize() function) is of fixed size, and the replace_spaces() function does not check that the destination buffer is large enough to hold what's copied into it. If the NetID is too big for the destination buffer, replace_spaces() will just keep writing past the end and overwrite whatever happens to be adjacent in memory.

You will write a function, attack_string(), to modify the netid_buffer so that a student is automatically awarded with a grade of A+ whenever the professor attempts to reduce his/her grade to a C-. To accomplish this, the netid_buffer must be changed such that when the program executes, the stack frame of validate_netid() gets smashed and the return address of validate_netid() gets overwritten. You need to inject the address of the automatic_a_plus() function on the stack so that when validate_netid() returns, it transfers the flow of control to the automatic_a_plus() function and runs the code in automatic_a_plus().

You need to change only one part of the program, marked with the word "TODO" near the bottom of the file. All other source code should remain intact.

Sample Run

The output of this unmodified code looks like this:

Accessing student record...
ajmiller is a valid NetID.
Student grade: C-
-- Connection to Student Records terminated --

After you have implemented the attack_string() function, the program output should look like this:

Accessing student record...
ajmiller is a valid NetID.
Student grade: A+
-- Connection to Student Records terminated --

Some Advice

It may be helpful to sketch out the stack layout and size at the time that the string_sanitize() function is called, so that you know what value on the stack you have to smash.

You will have to consider endian-ness issues when crafting your value for input_buffer.

What you should do for part B:

Start by downloading the stack-smashing SPIM template file.
Modify the parts of the code marked "TODO".
Load your program into SPIM and execute it. If your code works, you will see output indicating that your program correctly displays a grade of A+.

Turn IN

Turn-in your completed assembly code files to the course's Catalyst CollectIt dropbox. Be sure you have commented your code as necessary to help your TAs give you as much partial credit as possible. Also ensure you've placed your name in the block of comments at the top of each file.


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to perkins]