Final exam

Due 5:00PM Monday, June 5, 2023

Submit via Moodle as final.tar. Include your answers in final.pdf or final.txt, with source code (if any) in appropriately named C files.

There are some "draw a diagram" tasks below. If you wish, feel free to draw your diagrams by hand and include images in your PDF submission. If you do so, please make sure the images are legible.

This is a takehome exam. You may use your textbook and online sources, as long as you cite them clearly. You may not speak with anyone other than Jeff Ondich about the content of this exam. That means in particular that you may not talk with your classmates or post questions on online forums. You may, however, ask questions during class and via the #questions channel of our class Slack workspace (and, of course, via Slack direct message to Jeff).

When answering questions on this exam, you should show your work to get full credit. For example, in the very first question 1(a), it's not sufficient to provide the correct 8-digit hexadecimal number. You must also explain (concisely and clearly) why that particular 32-bit number represents the given real number.

  1. Floating point numbers

    Read Section 2.4 ("Floating Point") of your textbook. All of the following questions refer to the IEEE 754 single precision (32-bit) representation of real numbers.

    1. [2] What is the representation of the real number -27.625? Give your answer as a single 8-digit hexadecimal number.
    2. [2] To what real number does the 32-bit IEEE 754 representation 0x40caaaab correspond? Please express your answer as a fraction. (Note: since the significand appears to have a repeating pattern, you may find that extending that pattern infinitely gives you a much simpler fraction than the rounded off version stored in this 32-bit float.)
    3. [1] What is the 32-bit representation of NaN? (i.e., "not a number"). Show your answer as an 8-digit hexadecimal number.
    4. [1] Show a small amount of C code that can be used to cause a float-type variable x to contain NaN. (You can test this using a printf("%f", x); statement.)

  2. Bytes in context

    Suppose we have a UTF8-encoded text file named letter.txt containing my latest missive to my Canadian friend Marie, and that file starts like so:

    Chère Marie, I plan to arrive in Montréal on July 17...

    This really is just a text file (without a byte order mark), so the very first byte of the file is 0x43 (that is, a capital C).

    For each of the following questions, you may assume that we are going to execute this C code:

    int file_descriptor = open("letter.txt", O_RDONLY); if (file_descriptor < 0) { perror("Trouble opening file"); exit(1); } // Here, do whatever the question asks. // ... close(file_descriptor);

    That is, for each question below, you open the file, you do the thing the question requires you to do, and then you close the file. Let's get started.

    1. [2] Suppose you read the first sizeof(int) bytes of the file into an int variable and then print that variable as a decimal integer. What gets printed, and why?
    2. [1] Same question, but for sizeof(long) bytes into a long variable.
    3. [2] Same question, but for sizeof(float) bytes into a float variable (and print as a real number, not as an integer).
    4. [2] Suppose you read the first line of text, not including the newline character, from letter.txt into a character buffer char buffer[20]. What bytes are found in buffer[0],...,buffer[7], inclusive, and why?
    5. [2] Suppose you read the first line of text, not including the newline character, from letter.txt into a character buffer char buffer[20]. Suppose you then manage to get the program to jump (or retq, or whatever) to the address of buffer[0] and start executing code there. What is the first instruction it will try to execute? How did you figure that out?

  3. Educating Jeff. [2] Is there a book, a movie, a podcast, a website, a game, a writer, a musician, etc. etc. you think I should know about? Let me know about it!

  4. Exploring an executable

    Consider the executable program problem4. If you run this program on mantis like so:

    ./problem4 -h

    it will tell you only that the expected command-line syntax is:

    ./problem4 items_file item

    For the questions below, you will investigate what this program does, how it does it, and how it might be vulnerable to a buffer overflow attack.

    1. [1] If you view the first few bytes of problem4, you'll see that three of those bytes spell "ELF". What is ELF, and why does it show up in this executable program?
    2. [2] Provide a list of functions contained in problem4. (Don't include obvious system functions like strncmp or exit.) How did you obtain this list?
    3. [2] What does the function q_sort do? How do you know?
    4. [2] What does the function b_search do? How do you know?
    5. [1] The function b_search is recursive. At which address would you place a breakpoint if you wanted to break when b_search first encounters its base case? Explain.

    6. [3] Suppose you download the file items-sample.txt, set the breakpoint from the previous question, and then execute:

      ./problem4 items-sample.txt cat

      Once you have broken at the base case of b_search, draw a detailed diagram of the stack from the top (lowest address) of the stack frame form the most recent call of b_search down to the bottom (highest address) of the stack frame for main. Explain as clearly and in as much detail as possible why the of the stack contains what it contains.

      Suggestion: use gdb and x/48xw $rsp or x/24xg $rsp or whatever to produce a printout of the actual contents of the stack at the desired time. Then draw rectangles around chunks of this printout, with arrows and annotations explaining what those chunks mean. You can do this with software, of course, but you may also do it with paper, colored markers, careful handwriting, and a clear photo in good lighting.

    7. [2] What does problem4 do? That is, what simple computational problem is it trying to solve? How do you know?
    8. [3] This program is vulnerable to a buffer overflow. In particular, it is possible to specify inputs (i.e., an items file and an item) that will cause problem4 to run to completion without crashing but give the wrong answer (see the previous question for what "right answer" is supposed to be). Explain how you can make this error happen, and why it happens.

    HINT: Even though it's usually bad practice to do so, problem4's main loads the lines of the items file into a fixed-size 2D array (specifically, this 2D array has 12 rows of 8 chars each). I recommend that early on, you figure out where in main's stack frame the items_file contents and the item are stored.

  5. Have a great summer and/or life in the world beyond Carleton!. [2] (Points to be awarded preemptively on the assumption that you'll try to do so.) Thanks for being a wonderful class. It was a pleasure working with you.