CSE 378 Winter 2011
 CSE Home About Us Search Contact Info

 Home Administrative Academic Misconduct Syllabus Homework Homework 0 Homework 1    (strcmp.s) (atoi.s) Homework 2 Homework 3 Homework 4 Due 3/12 Labs Lab 1 SW + HW Due 1/21 Lab 2 SW + HW Due 2/4 Lab 3 SW Due 2/22 Lab 4 SW + HW Due 3/11 Resources Lectures Exams Lab Wiki Lab Info Green Sheet (PDF) Green Sheet Magic MIPS Resources Communications Discussion Board Mail List Archives Turnin GradeBook

# CSE 378 Winter 2011 Homework 2

## Due: Monday, February 7th 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:

2. Implement the body of the binarySearch() function.

3. 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.
-- 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.
-- Connection to Student Records terminated --
```

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.