|CSE Home||About Us||Search||Contact Info|
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 SearchFor 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:
Part B: Smashing the StackNow 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 StackThis 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 RunThe 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 AdviceIt 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:
Turn INTurn-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
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to perkins]