CSCI 2021 Project 3: Assembly Coding and Debugging

As discussed in class, one can generate assembly code from C code with appropriate compiler flags. This can be useful for getting oriented and as a beginning to the code your assembly versions of the functions. However, code that is clearly compiler-generated with no hand coding will receive 0 credit.

• No credit will be given on manual inspection
• Penalties will be assessed for Automated Tests which lower credit to 0

Do not let that dissuade you from looking at compiler-generated assembly code from you C solution to the functions. Make sure that you take the following steps which are part of the manual inspection criteria.

1. Get your editor set up to make coding assembly easier. If you are using VS Code, the following video will show you how to install an extension to do syntax highlighting and block comment/uncomment operations in assembly: https://youtu.be/AgmXUFOEgIw
2. Be disciplined about your register use: comment what "variables" are in which registers as it is up to you to keep track. The #1 advice from past students to future students is "Comment the Crap out of your assembly code" on this project.

3. Be Careful with constants: forgetting a $ in constants will lead to a bare, absolute memory address which will likely segfault your program. Contrast:

      movq    $0,%rax                 # rax = 0
      movq    0, %rax                 # rax = *(0): segfault
                                      # bare 0 is memory address 0 - out of bounds
   

   Running your programs, assembly code included, in Valgrind can help to identify these problems. In Valgrind output, look for a line number in the assembly code which has absolute memory addresses or a register that has an invalid address.

4. Recognize that in x86-64 function parameters are passed in registers for up to 6 arguments. These are arranged as follows

   1. rdi / edi / di (arg 1)
   2. rsi / esi / si (arg 2)
   3. rdx / edx / dx (arg 3)
   4. rcx / ecx / cx (arg 4)
   5. r8 / r8d / r8w (arg 5)
   6. r9 / r9d / r9w (arg 6)

   and the specific register corresponds to how argument sizes (64 bit args in rdi, 32 bit in edi, etc). The functions you will write have few arguments so they will all be in registers.

5. Use registers sparingly. The following registers (64-bit names) are "scratch" registers or "caller save." Functions may alter them freely (though some may contain function arguments).

   rax rcx rdx rdi rsi r8 r9 r10 r11  # Caller save registers
   

   No special actions need to be taken at the end of the function regarding these registers except that rax should contain the function return value.

   Remaining registers are "callee save": if used, their original values must be restored before returning from the function.

   rbx rbp r12 r13 r14 r15            # Callee save registers
   

   This is typically done by pushing the callee registers to be used on the stack, using them, them popping them off the stack in reverse order. Avoid this if you can (and you probably can in our case).

6. Be careful to adjust the stack pointer using pushX/popX or subq/addq . Keep in mind the stack must be aligned to 16-byte boundaries for function calls to work correctly. Above all, don't treat rsp as a general purpose register.

7. When using the idivX instruction, incorrect results can be included if you don't fully extend the sign of the ax-family register. As demoed in the assembly basics lecture, the right way to do this for a 16-bit value and a 64-bit division is as follows:

      movw $-17, %ax                  # load rax with a 16-bit value
      cwtl                            # extend sign to eax
      cltq                            # extend sign to rax
      cqto                            # extend sign across to rdx
      movq $3, %rcx                   # set up divisor in rcx
      idivq %rcx                      # perform division of -17 / 3
   

   Using different sequences or small division like idivw may work but many students have encountered problems when not following the above sequence.

For reference, here is a picture that appears in the lecture slides that summarizes the names and special uses for the registers in x86-64.

With working C versions of the three required functions, you should be able to employ an iterative strategy while developing assembly versions: focus on one assembly function while using working C functions for the remaining code. The Makefile and support code are specifically set up for this and details iterative development are as follows.

1. In clock_update_asm.s, comment all code/declarations of global symbols except for set_tod_from_sec.
2. In clock_update.c, comment out the definition of the set_tod_from_sec() function. This leaves working C versions of the other two functions.

3. Write some assembly code for set_tod_from_sec. Attempt to compile it on its own with

      > make clock_update_asm.o 
      gcc -Wall -Werror -g -c clock_update_asm.s
   

   which will report assembler errors if any are present.

4. When there appear to be no assembler errors, create a hybrid main program which will combine the uncommented assembly and C functions

   >> make hybrid_main
   gcc -Wall -Wno-comment -Werror -g  -c clock_main.c
   gcc -Wall -Wno-comment -Werror -g  -c clock_sim.c
   gcc -Wall -Wno-comment -Werror -g  -c clock_update_asm.s
   gcc -Wall -Wno-comment -Werror -g  -c clock_update.c
   gcc -Wall -Wno-comment -Werror -g  -o hybrid_main clock_main.o clock_sim.o clock_update_asm.o clock_update.o
   

5. One can then experiment with the hybrid_main to see if the written assembly function is working correctly.

   >> ./hybrid_main 3812
   TIME_OF_DAY_SEC set to: 3812
   result = set_tod_from_secs(  3812, &tod );
   result: 0
   tod = {        
     .hours   = -15
     .minutes = 0
     .seconds = 1206
     .ampm    = 17
   }              
   ...
   

   Something clearly looks wrong in the above so some debugging of the assembly function seems in order.

6. When ready, run the "hybrid tests" which will do automated testing on the hybrid codes.

   >> make test-hybrid
   gcc -Wall -Wno-comment -Werror -g  -o test_hybrid_update test_clock_update.o clock_sim.o clock_update_asm.o clock_update.o
   ...
   ./testy test_hybrid.org 
   ============================================================
   == test_hybrid.org : Problem 1 test_hybrid_update and hybrid_main tests
   == Running 35 / 35 tests
   1)  test_hybrid_update tod-midnight           : ok
   2)  test_hybrid_update tod-after-midnight     : ok
   3)  test_hybrid_update tod-after-1am          : ok
   4)  test_hybrid_update tod-nearly-noon        : ok
   5)  test_hybrid_update tod-is-noon            : ok
   ...
   

7. When all seems to be working correctly with the first assembly function, move on. Comment another C function and uncomment the corresponding assembly, write some code and repeat.

Below is a rough outline of the structure of required assmebly file. Consider copying this file as you get started and commenting parts of it out as needed.

.text
.global  set_tod_from_secs
        
## ENTRY POINT FOR REQUIRED FUNCTION
set_tod_from_secs:
        ## assembly instructions here

        ## a useful technique for this problem
        movX    SOME_GLOBAL_VAR(%rip), %reg  # load global variable into register
                                             # use movl / movq / movw / movb
                                             # and appropriately sized destination register

### Data area associated with the next function
.data
	
my_int:                         # declare location an single int
        .int 1234               # value 1234

other_int:                      # declare another accessible via name 'other_int'
        .int 0b0101             # binary value as per C '0b' convention

my_array:                       # declare multiple ints in a row 
        .int 10                 # for an array. Each are spaced
        .int 20                 # 4 bytes from each other
        .int 30


.text
.global  set_display_from_tod

## ENTRY POINT FOR REQUIRED FUNCTION
set_display_from_tod:
        ## assembly instructions here

	## two useful techniques for this problem
        movl    my_int(%rip),%eax    # load my_int into register eax
        leaq    my_array(%rip),%rdx  # load pointer to beginning of my_array into rdx


.text
.global clock_update
        
## ENTRY POINT FOR REQUIRED FUNCTION
clock_update:
	## assembly instructions here

int set_tod_from_secs(int time_of_day_sec, tod_t *tod);
// Accepts time of day in seconds as an argument and modifies the
// struct pointed at by tod to fill in its hours, minutes,
// etc. fields.  If time_of_day_sec is invalid (negative or larger
// than the number of seconds in a day) does nothing to tod and
// returns 1 to indicate an error. Otherwise returns 0 to indicate
// success. This function DOES NOT modify any global variables
//
// CONSTRAINT: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU.

Note that this function uses a tod_t struct which is in clock.h described here:

// Breaks time down into 12-hour format
typedef struct{
  short hours;
  short minutes;
  short seconds;
  char ampm;
} tod_t;

Available only on Lab Machines or Vole

More details on these are described in subsequent sections.

The nature of this problem is similar to the previous project's puzzlebox: there is a program called bomb which expects certain inputs from a parameter file or typed as input. If the inputs are "correct", a phase will be "defused" earning points and allowing access to a subsequent phases. The major change is that the bomb program is in binary so must be debugged in assembly.

Below is a summary of useful information concerning the binary bomb.

Bombs are Individual

The bomb you will download contains subtle variations so that the solution to yours will not work on other bombs. Feel free to discuss general techniques with classmates but know that you'll need to ultimately defuse your own bomb.

Bombs are Binary

A small amount of C code with the main() function is included but the bulk of the code is binary which will require using gdb to debug the assembly code.

Bombs only Run on Lab Machines

To stay in contact with the scoring server, bombs won't run on your laptop. You'll need to work on them on lab machines.

Bombs Take Input

Similar to puzzlebox, create an input.txt file which will contain your answers. Run bombs with this input file. Note that if the bomb runs out of input, you can type input directly into the bomb though this may look a little funny in the debugger.

Defusing Phases Earns Points

As with the earlier puzzlebox, points for this problem are earned based on how many phases are completed. Each phase that is completed will automatically be logged with the scoring server

Bomb Explosions Lose Points

If incorrect input is entered and the bomb runs to completion, it will "explode" which causes credit to be deducted. See the scoring system for details. This can be prevented by setting breakpoints prior to the explosion sequence and restarting the bomb when those breakpoints are hit.

Use GDB to work with Bombs

The debugger is the best tool to work with running bombs. It may be tempting to try to brute force the bomb by trying many possible inputs but this may lead to many explosions or crashing the scoring server. Both of these are a bad idea so work with your bomb by hand.

The binary bomb makes frequent contact with a scoring server so you can only run it on a list of prescribed machines. These comprise most of the valid CSELabs machines and are listed in the table below.

Attempting to run a bomb on an un-authorized machine will error out immediately as in

> ./bomb
Initialization error: illegal host 'ck-laptop'.
Legal hosts are as follows:
  csel-apollo
  csel-atlas
  csel-vole-01
  csel-vole-02
  ...

• Download your bomb from the following web address
  • http://atlas.cselabs.umn.edu:15213/
• This site must be accessed from wired UMN machines or Vole as it is behind the campus firewall. Using a browser on Vole or a FASTX connection is the easiest way get a bomb onto your CSELabs account when you are working remotely (and will let you tell friends "I've used a browser inside a browser.").
• Enter your UMN X.500 information in the required fields: IDs that don't correspond to members of the class will be rejected. If you have problems getting a bomb, mail Prof Kauffman.

• The bomb will download as a .zip file. On Unix machines, extract the contents using the command unzip as in

    > ls
    bomb10.zip
    
    > unzip bomb10.zip
    bomb10/README
    bomb10/bomb.c
    bomb10/bomb
    
    > ls
    bomb10.zip    bomb10/
    
    > cd bomb10
    > ls
    bomb*  bomb.c  README
  

• The resulting bomb is unique for the downloader and the owner is in the README and logged on the download server.
• The file bomb (sometimes listed with a * to indicate it is executable) is a compiled binary so employ your assembly gdb skills to cracking it.

• Create a file input.txt. The bomb can be run with it as in

  > ./bomb input.txt
  

  but you'll likely want to do this in gdb to avoid exploding the bomb.

• Unlike previous puzzles, if input.txt runs out of input, the bomb will prompt for you to type input. This can be a way to explore ahead a little bit in the bomb after solving a phase.

It is possible to download multiple bombs but this will NOT reset your explosion count. Quite the opposite: the default scoring system for the server uses the following conventions.

• Only the maximum phase defused in any bomb adds points
• Total explosions across ALL bombs subtract points with each separately downloaded bomb contributing up to -5.

Since more bombs likely means more explosions, you are strongly advised to download a single bomb and work with it.

• If you accidentally run the bomb from the command line, you can kill it with the Unix interrupt key sequence Ctrl-c (hold control, press C key).

    > ./bomb
    Welcome to my fiendish little bomb. You have 6 phases with
    which to blow yourself up. Have a nice day!
    ^C
    So you think you can stop the bomb with ctrl-c, do you?
    Well...OK. :-)
    > 
  

• Most of the time you should run the bomb in gdb as in

  > gdb ./bomb
  

  Refer to the Quick Guide to GDB if you have forgotten how to use gdb and pay particular attention to the sections on debugging assembly.

• Figure out what the explosion routine is called and always set a breakpoint there. This will allow you to stop the bomb
• Make use of other tools to analyze the binary bomb aside from the debugger. Some of these are described at the end of the Quick Guide to GDB. They will allow you to search for "interesting" data in the executable bomb. The author of the bomb is encoded in the binary as a string somewhere which may be relevant to inputs for some phases.
• Disassemble the executable to look at its entire source assembly code as a text file. The Quick Guide to GDB shows how to use objdump to do this. Looking at the whole source code reveals that one cannot hide secrets easily in programs.
• Feel free to do some internet research. The "bomb lab" assignment has a long history and there are some useful guides out there that can help you through rough patches. Keep in mind that your bomb will differ but the techniques to defuse it may be similar to others.