Computer Assembly/Architecture. Explain which two programs work with prime numbers and which two programs work with square numbers looking at the program assembly code below and explaining why.

Question

Computer Assembly/Architecture. Explain which two programs work with prime numbers and which two programs work with square numbers looking at the program assembly code below and explaining why.

There are two programs that work with prime numbers, and two programs that work with square numbers. For each number sequence, one of the programs will fill in an array of 100 quadword integers with the first 100 numbers in the sequence; the other program will fill in an array of 100 bytes with booleans indicating which of the numbers up to 100 is a member of the sequence. For example, the first-100-primes program will fill in an array of quadwords with 2, 3, 5, 7, …, while the primes-up-to-100 program will fill in an array of bytes with 0, 0, 1, 1, 0, 1, 0, 1, … (notice that the 1s are at indices 2, 3, 5, 7, …).

The task is to figure out which program is which, using the debugger. Don’t care a lot that you tell me which is which correctly; what is important is that you show the steps you went through in the debugger and your reasoning about which is which. These programs were compiled from C programs; I have taken care that the names of the files and the names of symbols won’t be a giveaway, but I have neither stripped the symbol tables (which would make it harder) nor added debugging symbols (which would make it easier).

Use the script program to record your debugging sessions. First, within the Environment, run script. It will say something like “Script started, file is typescript”. Proceed to run gdb and explore one of the programs. When you are done and have exited gdb, also exit the shell with exit or by pressing control-d. You should see “Script done, file is typescript”. There should now be a file named typescript that has a complete log of your debugging session.

Put together a document that explains your belief about which program is which, and why, with supporting evidence from typescripts recorded from debugging. You will not get credit for an answer that says which programs are which correctly but does not include evidence from the debugger. You can use the disas command (e.g. disas main) in the debugger to see the machine code as assembly code, as well as the other debugging techniques we discussed for previous assignments.

If in the disassembly you encounter instructions you are not familiar with, stop and look them up and figure out what the code is doing. You could probably figure out which program is which just by looking at how each one fills in its array, but it’s worth even more credit if you can reverse engineer how the programs are doing their work and sketch the algorithms in your document.

ProgA:

Dump of assembler code for function main:

  0x00000000000005fa <+0>: push %rbp

  0x00000000000005fb <+1>: mov %rsp,%rbp

  0x00000000000005fe <+4>: movq $0x2,0x200a37(%rip) # 0x201040

  0x0000000000000609 <+15>: movq $0x1,-0x20(%rbp)

  0x0000000000000611 <+23>: movq $0x3,-0x28(%rbp)

  0x0000000000000619 <+31>: movq $0x1,-0x18(%rbp)

  0x0000000000000621 <+39>: jmpq 0x6ac

  0x0000000000000626 <+44>: mov -0x18(%rbp),%rax

  0x000000000000062a <+48>: lea 0x0(,%rax,8),%rdx

  0x0000000000000632 <+56>: lea 0x200a07(%rip),%rax # 0x201040

  0x0000000000000639 <+63>: mov (%rdx,%rax,1),%rsi

  0x000000000000063d <+67>: mov -0x28(%rbp),%rax

  0x0000000000000641 <+71>: mov $0x0,%edx

  0x0000000000000646 <+76>: div %rsi

  0x0000000000000649 <+79>: mov %rax,-0x10(%rbp)

  0x000000000000064d <+83>: mov -0x18(%rbp),%rax

  0x0000000000000651 <+87>: lea 0x0(,%rax,8),%rdx

  0x0000000000000659 <+95>: lea 0x2009e0(%rip),%rax # 0x201040

  0x0000000000000660 <+102>: mov (%rdx,%rax,1),%rcx



ProgB:

Dump of assembler code for function main:

  0x00000000000005fa <+0>: push %rbp

  0x00000000000005fb <+1>: mov %rsp,%rbp

  0x00000000000005fe <+4>: movq $0x0,-0x10(%rbp)

  0x0000000000000606 <+12>: jmp 0x61e

  0x0000000000000608 <+14>: lea 0x200a31(%rip),%rdx # 0x201040

  0x000000000000060f <+21>: mov -0x10(%rbp),%rax

  0x0000000000000613 <+25>: add %rdx,%rax

  0x0000000000000616 <+28>: movb $0x0,(%rax)

  0x0000000000000619 <+31>: addq $0x1,-0x10(%rbp)

  0x000000000000061e <+36>: cmpq $0x63,-0x10(%rbp)

  0x0000000000000623 <+41>: jbe 0x608

  0x0000000000000625 <+43>: movq $0x1,-0x8(%rbp)

  0x000000000000062d <+51>: jmp 0x675

  0x000000000000062f <+53>: movq $0x0,-0x10(%rbp)

  0x0000000000000637 <+61>: jmp 0x669

  0x0000000000000639 <+63>: lea 0x200a00(%rip),%rdx # 0x201040

  0x0000000000000640 <+70>: mov -0x10(%rbp),%rax

  0x0000000000000644 <+74>: add %rdx,%rax

  0x0000000000000647 <+77>: movzbl (%rax),%eax

  0x000000000000064a <+80>: test %al,%al

Answer 1

To determine which program works with prime numbers and which works with square numbers, we need to analyze the assembly code for each program and understand their algorithms. Let's go through each program and reason about their functionality based on the provided assembly code.

ProgA:

1. The program starts with the assembly code at address 0x00000000000005fa.

2. It pushes the base pointer onto the stack.

3. It moves the stack pointer to the base pointer.

4. It moves the value 0x2 to the memory address 0x201040.

5. It moves the value 0x1 to the memory address at the base pointer offset by -0x20.

6. It moves the value 0x3 to the memory address at the base pointer offset by -0x28.

7. It moves the value 0x1 to the memory address at the base pointer offset by -0x18.

8. It jumps to address 0x6ac.

9. The code at address 0x0000000000000626 retrieves the value from memory at the base pointer offset by -0x18 into %rax.

10. It performs some calculations and stores the result in %rdx.

11. It retrieves a value from memory at the address calculated using %rdx and %rax into %rsi.

12. It retrieves the value from memory at the base pointer offset by -0x28 into %rax.

13. It performs a division operation and stores the result in %rax.

14. It moves the value in %rax to the memory address at the base pointer offset by -0x10.

15. It retrieves the value from memory at the base pointer offset by -0x18 into %rax.

16. It performs some calculations and stores the result in %rdx.

17. It retrieves a value from memory at the address calculated using %rdx and %rax into %rcx.

ProgB:

1. The program starts with the assembly code at address 0x00000000000005fa.

2. It pushes the base pointer onto the stack.

3. It moves the stack pointer to the base pointer.

4. It moves the value 0x0 to the memory address at the base pointer offset by -0x10.

5. It jumps to address 0x61e.

6. The code at address 0x0000000000000608 calculates the address and stores it in %rdx.

7. It retrieves the value from memory at the base pointer offset by -0x10 into %rax.

8. It adds %rdx and %rax, then stores the result in %rax.

9. It moves the value 0x0 to the memory address pointed by %rax.

10. It adds 0x1 to the value at the base pointer offset by -0x10.

11. It compares the value at the base pointer offset by -0x10 with 0x63.

12. If the comparison result indicates that the value is less than or equal to 0x63, it jumps to address 0x608.

13. It moves the value 0x1 to the memory address at the base pointer offset by -0x8.

14. It jumps to address 0x675.

15. The code at address 0x000000000000062f moves the value 0x0 to the memory address at the base pointer offset by -0x10.

16. It jumps to address 0x669.

17. The code at address 0x0000000000000639 calculates the address and stores it in %rdx.

18. It retrieves the value from memory at the base pointer offset by -0x10 into %rax.

19. It adds %rdx and %rax, then stores the result in %rax.

20. It zero-extends the value at %rax and stores it in %eax.

21. It tests %al (lower 8 bits of %eax) against itself.

Based on the analysis of the assembly code, we can make an informed guess about the functionality of each program:

1. ProgA: This program fills an array of 100 quadword integers with the first 100 prime numbers. The algorithm calculates and checks for prime numbers using division operations and stores the results in memory locations.

2. ProgB: This program fills an array of 100 bytes with booleans indicating which of the numbers up to 100 is a member of the sequence. The algorithm calculates addresses, stores the value 0 at those addresses, and increments the address until it reaches the value 99. After that, it sets the value 1 at the base pointer offset by -0x8. Finally, it performs some additional calculations with memory addresses and tests the lower 8 bits of the value stored at those addresses.

Therefore, based on the analysis, ProgA works with prime numbers, and ProgB works with square numbers.

To confirm our hypothesis, we would need to analyze the disassembly code for the main function in each program, specifically the loop structures and memory accesses. However, without the complete disassembly code, it is difficult to provide a definitive answer.