Assignment 2, Solutions

Part of the homework for 22C:169, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: The Unix operating system does not include any explicit mechanism to enlarge the stack segment. Initially, the stack segment is just big enough to hold the initial stack (the values pushed by the exec system call that launches an application).

    A Problem: Given that there is no explicit system call "make my stack bigger", how can the system possibly know when to enlarge the stack. (1.0 points)

    The MMU forces a trap whenever the application references a page that is currently not allocated. The trap handler can examine the instruction and the memory address referenced by the instruction that caused the trap. The trap handler has access to the entire saved state of the application program at the time of the trap.

    If the interrupt was caused by a store operation to memory a memory address in the page just beyond the end top of the stack segment, the stack segment can be enlarged by one page and then the trap handler can return in such a way that instruction that caused the trap is re-executed, this time successfully.

  2. Background: Suppose the system always loads programs at a random virtual address each time an application is launched. This prevents exploiting a buffer overflow to force execution of some specific subroutine. The buffer overflow can still cause random actions.

    On Unix, the above defense must be modified somewhat because whenever there are multiple processes running the same application, the code segment is shared.

    a) On most machines, a shared code segment must be at the same virtual address in all processes that share it. Why? This is a question about computer architecture. Knowledge of assembly language programming is essential to answering it. (0.5 points)

    It must always be at the same virtual address if any of the memory addresses in the code are absolute memory addresses of other parts of the code. Thus, we can only share a code segment at different addresses in each process that shares that segment if all branches, jumps and calls use position independent addressing, for example, using a PC-relative addresing mode.

    b) Assume that shared code is seen to be in the same virtual address by all processes that share that code, but that the load address is randomized each time the code is loaded -- that is, when nobody was using it and then someone launched it, what could an attacker do that would not work if code was not shared between processes and each execution of a program involved loading it again? (0.5 points)

    We could start one process using the code we want to attack for a long time, for example, doing nothing. For example, if we are attacking an editor, open an editing window and do the minimum work needed to keep the editor alive in that window while using other windows to attack the editor.

    Now, do experiments to explore the vulnerabilities of the program under attack in other processes, confident that holding the first process is pinning the victim down so it can't relocate into different memory addresses.

  3. Background: Consider a process on a Unix system. Each process in this system has a code segment that always starts at virtual address zero, a stack segment that grows down from the highest virtual address, a and a static segment. Executable object files can be executed by directly copying them into code segment.

    a) Explain what part of the function of execve() on this system could be implemented using the semantics of unmap() and mmap(). (0.5 points)

    First, gathering the program parameters and environment from the caller.

    Second, unmap the former code segment, then map the new one. The new program segment is mapped with PROT_EXEC and PROT_READ access, and MAP_FILE and MAP_SHARED flags. The segment is mapped to the code portion of the object file.

    Third, unmap the former static segment, then map the new one. The new static segment is mapped with PROT_READ and PROT_WRITE access, and MAP_FILE and MAP_PRIVATE flags. The segment is mapped to the static portion of the object file to get the initial values.

    Finally, unmap the former stack segment and then map the new one. The new stack segment is mapped with PROT_READ and PROT_WRITE access, and with MAP_ANON and MAP_PRIVATE flags. After mapping, the environment and parameters are pushed before calling the main program in the code segment.

    b) What, if anything, does mmap() do that shmat() does not do, and visa versa. (Note: These two Unix kernel services exist entirely because there were separate independent streams of development that each produced shared memory models. Both models are supported in modern Linux systems. More evidence of "intelligent" design.) (0.5 points)

    mmap() maps memory regions, shared or not, to files. shmat() does not do this. Note that shmat() uses a new address space described by values of the shmid flag, while mmap() use the identity of a file to name a shared segment. It is clear that the basic mechanism underlying both sets of primitives for supporting shared memory must be the same.

  4. A Problem: Empirically determine, for example, by writing some small C programs, using a debugger, or by other means, the organization of the address space of a user program on the Linux system of your choice. What system did you use, and on that system, Note that your code from the first homework assignment for printing out the value of a pointer will be immensely valuable in solving this problem. (1 point)
    #include <stdio.h>
    #include <stdlib.h>
     * Program to print out the addresses of various variables       *
     * Author:  Douglas W. Jones                                     *
    int global;
    void routine()
           int local;
           int * p = malloc(sizeof(int));
           printf("Address of a variable on the stack: %lx\n", &local);
           printf("Address of some code: %lx\n", routine);
           printf("Address of a variable in the static segment: %lx\n", &global);
           printf("Address of a variable on the heap: %lx\n", p);
    int main() {

    The results will, of course, depend on where you run this code. On my old Power Mac, I got this output:

    Address of a variable on the stack: bffffaac
    Address of some code: 29cc
    Address of a variable in the static segment: 30c4
    Address of a variable on the heap: 500120

    On the departmental linux server, I got:

    Address of a variable on the stack: 7fffd575e424
    Address of some code: 400504
    Address of a variable in the static segment: 600a08
    Address of a variable on the heap: 1310010

  5. A Problem: On most modern CPU architectures, all of the address space is one virtual address space, so incrementing or decrementing an address in the stack segment by an appropriate amount will produce a value in the code segment, the static segment, or elsewhere. In effect, pointers have no type, so while we may think of code pointers as a different type from data pointers, the hardware is unable to enforce the difference.

    a) How can the MMU be used to prevent, for example, a stack overflow into the static segment? (0.5 points)

    Always ensure that there is at least one page marked "no access" between them, because most stack growth is in units smaller than a page. This is not foolproof, but it is helpful.

    b) How can the MMU be used to prevent, for example, accidental execution of data on the stack, or accidental modification of code in the program segment? (0.5 points)

    Mark the program segment read-execute only, and mark the stack segment read-write.