Computer Architecture
Instructions
Instructions are the means by which the developer tells the CPU what task to accomplish. Intel x86 and x64 architectures provides a rich set of instructions to perform many tasks.
In this module we discuss the how the instructions are form to accomplish this task.
As a part of that the discussion we will include the following topics:
• Addressing modes
• Data types
• Math operations and Float-point numbers
• Stack structure
• Calling convention (x86 and x64)
• Interrupts and exceptions
• Instruction encoding
Intel -Instruction Format
Below is the form that all instructions follow. You will notice that some fields are optional which will cause the instructions to vary in length.
Intel Manual Volume 2 – 2.1 page 527
Instruction Prefix
This is an optional 8 bit value; which can be one of the following grouping:
• Lock and Repeat
• Lock is related to shared memory use
• Repeat instruction. Eg REPNE used with MOVS + other string functions
• Segment Override
• Used with branch instructions
• Used to override with segment registers, not explained well.
• Operand Size override
• Allows switching of operand size from the current default. Eg if operand size is 16 bits, switch to 32 bits etc.
• Address-size override
• Allows switching to address size from the current default. Eg if address size is 16
bits switch to 32 bits etc.
Intel Manual Volume 2 – 2.1.1 page 527
Instruction Prefix
• “Not all instructions require a REX prefix in 64-bit mode.
• A prefix is necessary only if an instruction references one of the
extended registers or uses a 64-bit operand.
• If a REX prefix is used when it has no meaning, it is ignored.”
0100 1000 REX.W If W is set 1 You will see in opcode 48
0100WRXB
Opcodes
• Opcodes or Operation codes are sequences that tell the CPU what operation it will be performing. They can be 1-3 bytes in length and can include an optional addressing form specifier (Mod, Reg/Opcode, R/M) sequence.
• There can also be an optional Scale Index Base (SIB) byte, as well an Address displacement (none, 1, 2, or 4 bytes) and an Immediate data (none, 1, 2, or 4 bytes) field.
• The addressing form specifier can be used to encode an additional 3-bits if needed by the opcode.
• Opcodes are used to create shellcodes (payloads) in exploitation See Intel Software Developer Manual Volume 2A – 2.1.2 p2-3
Page 529
ModR/M
Mod (modifier) field: Combines with the R/M field, resulting 5 bits total.
How many possible values does 5 bits represent?
Reg/opcode (Register or Opcode) field: Either a register number or 3 bits of opcode information.
R/M (register or modifier) field: Register as operand or combined with the mod field to encode an addressing mode. e.g
Mod
00 Memory
01 Memory with displacement [disp8]
10 Memory with displacement [disp16] or [disp32 ]
11 General Purpose Register
00001111
Mod Reg/Opcode R/M
00 001 111
Registry Field from ModR/M
The reg field in the ModR/M byte specifies a general-purpose register operand.
Intel Vol. 2D B-3 Appendix B Instructions Formats and Encoding page 2667
SIB
SIB (Scale, Index, Base) : A second addressing byte for some instructions. Think arrays:
•Scale (1 – char, 2 – short, 4 – integer) is a multiplier •Index – Register number holding the array index
•Base – Register number holding the array base address
char array[10] EAX[EBX*ECX] == EAX + (ECX * EBX)
See Intel Software Developer Manual Volume 2A – 2.1.2 p2-3 Page 529
Displacement and Immediate
Some instructions will require a displacement value of 1, 2 or 4 bytes.
The displacement represents another offset value.
Some instructions will also require an immediate value this value will always follow the Displacement value.
Decoding instructions
Instructions are rarely decoded or encoded by hand. This is primarily done in educational institutions to give students the perspective of how difficult this can be.
To do so, one would use the following resources from the Intel 64 and IA-32 Architectures Software Developers Manual (Vol 2A – Chapter 2) 525 and (Vol 2D – Appendix A):
1. Instruction Format
2. Opcode Map
Opcode Map
The first digit is the table row and second digit is the table column. Notice the mnemonic ADD, TEST and more covers multiple columns in a row.
Example Decoding
Let’s work through a simple example:
You get the following machine code: 89 45 FC
1. First get the Intel SW manual
2. Search for opcodes on opcode table -Manual Volume 2D A-7 or A-8 pg 2641
3. Take the first byte and find the related instruction:
1. 8 – represents the row
2. 9 – represents the column
3. This translates to MO V Ev, Gv
4. What is Ev and Gv
1. After a bit of searching we find that the E and G are codes for Addressing Method and the
v is for Operand Type
2. E – means a ModR/M byte follows the opcode, where the operand is either a register or
Memory address
3. G – means the register field of ModR/M byte selects a General purpose register
4. The v could be W, DW or QW based on operand size attribute (in instruction)
Intel Appendix A –Opcode map contains opcode abbreviations Page 2635
Example Decoding – continued
From the image on Slide 3 we know the following: (p529)
1. 2. 3. 4.
5.
6.
There is no prefix
The opcode is 89 45 fc – 89 is the instruction MOV Ev,Gv
To find the format Ev,Gv, the next byte 45 needs to be decoded.
Convert 0x45 to binary (MOD – 01, Reg/Opcode – 000, R/M – 101)
No prefix 0x89 0x45 – 0100 0101 No SIB 0xFC No Immediate
000 Reg/code field based is EAX based on table in 2667 then Gv = EAX → Mov Ev, EAX To find out Ev we use information on Table 2-2 on manual vol 2A 2-3 page 532 and find
Mod and R/M values, in this case Mod 01 and R/M 101 (0x45) .
Example Decoding – continued
7. We found effective address [EBP]+disp8 → mov [ebp] +disp8, eax
8. Based on Instruction format after ModR/M is displacement value in this example is 0xfc and the Two’s complement of 0xfc is -4 (-0x4) . Check with calculator NOT FC + 1 = FFFF FFFF FFFF FF04
9. The instruction is mov [ebp + 0xfc] , eax
or mov 0xfc[ebp], eax
or mov -0x4[ebp],eax
or mov [ebp-0x4],eax
or mov -0x4(%ebp), eax in AT&T
Understanding the stack
• “The stack is a contiguous array of memory locations. It is contained in a segment and identified by the segment selector in the SS register.
• When using the flat memory model, the stack can be located anywhere in the linear address space for the program.
• A stack can be up to 4 GBytes long, the maximum size of a segment.” Ref: Intel Manual Vol 1 chapter 6 6-1 page 151
• Programmer perspective: The stack is a data structure that allows functions to temporarily store local variables, arguments and context to be used during the lifetime of that function. It also stores the location EIP should return to after the function is done. All these data stored in the stack and needed by the called function is called stack frame
• Each function will have its own stack frame. That stack frame is demarked by the EBP and ESP registers.
• The stack contains many stack frames
The Stack PUSH and POP instructions
• The stack is a Last In First Out (LIFO) structure. This means that as new items are added (PUSH instruction) to the stack, and later removed (POP instruction), the last item is the first to be removed.
• PUSH and POP instructions can handle 16, 32 or 64 bits operandschapter4 page 1689
The Stack EBP Instruction
• There are specific registers used by the stack: EBP, ESP
• EBP contains stack-frame based pointer. It is used as fixed reference
point for all local variables within the function currently being executed.
• To used the stack-frame , the called procedure copies the content of ESP register into EBP register before any local variable is pushed onto the stack
• After ESP is copied into EBP, the stack-frame base pointer allows access to data structures passed on the stack, to the return EIP and to the local variables push onto the stack by the called procedure
• EBP register (Base Pointer) for a particular frame is located at the high address. (bottom of the stack)
• Why is the EBP stationary?
The Stack ESP Instructions
• The ESP can move up or down as new variables are pushed onto or popped off from the stack.
• When an item is pushed onto the stack, the processor decrements the ESP register. PUSH Decrements the stack pointer (ESP) and then stores the source operand on the top of the stack. IntelVolume2B 4-513Page1680
• When an item is popped off the stack, the processor reads the item from the top of stack, then increments the ESP register.
• The stack grows down in memory (towards lesser addresses) when items are pushed on the stack and shrinks up (towards greater addresses) when the items are popped from the stack.
• “POP Loads the value from the top of the stack to the location specified with the destination operand and then increments the stack pointer (ESP). The destination operand can be a general- purpose register, memory location, or segment register”.. Intel Volume 2B 4-390 Page 1566
Set up the Stack
• Each task (process) can be given its own stack. The number of stacks in a system depends on max number of segments and available RAM
• Only one stack (current stack) can be active at a time. The current stack is the one contained in the segment referenced by the SS register.
• To set a stack and establish it as the current stack, the program or operating system/executive must do the following:
• •
•
1. Establish a stack segment.
2. Load the segment selector for the stack segment into the SS register using a MOV, POP, or LSS instruction.
3. Load the stack pointer for the stack into the ESP register using a MOV,
POP,
Ref: Intel Manual Vol 1 chapter 6 6-2 page 152
Understanding the stack – 2.0
• Stack Top – Location of lowest address where ESP currently points
• Stack Bottom – Location currently pointed to by EBP
• As items are added to the top of the stack, the ESP is automatically updated.
• The stack stores two pointers necessary to put back things the way were when
the function was called. The saved frame pointer (SFP) used to restore EBP to previous value and the return address (ret instruction) used to restore EIP to next instruction found after function call
Is the stack a random access structure?
• Assembly Functions normally used with ESP: PUSH (including variants), POP (including variants), SUB, ADD
Stack and Function Call
Bottom of the stack has higher address and is highlighted below.
EIP,JMP,CALL AND RET INSTRUCTIONS
• EIP register cannot be accessed directly by software; it is controlled implicitly by control- transfer instructions such as JMP, CALL and RET, interrupts and exceptions
• To read EIP register, CALL instruction needs to be executed, then read value of return instruction pointer from stack
• Before jumping to the first instruction of the called procedure, the CALL instruction pushes the address in the EIP register into the stack and will be called return-instruction pointer and it points to the instruction where execution of the calling procedure should resume following a return from the called procedure.
• After returning from a called procedure, the RET instruction pops the return-instruction pointer from the stack back into the EIP register. Execution of the calling procedure then resumes.
• EIP register can be loaded indirectly by modifying the value of a return instruction pointer on the procedure stack and executing a return instruction (RET)
• A common way to reset the stack pointer to the point to the return-instruction pointer is to move the contents of the EBP register into the ESP register. If
Ref: Intel Manual Vol 1 chapter 6 6-3 page 153
Procedure Calls –CALL and RET
• CALL instruction saves procedure linking information on the stack and branches to the called procedure specified using the target operand. The target operand specifies the address of the first instruction in the called procedure. The operand can be an immediate value, a general-purpose register, or a memory location.
• It can be used to execute the following calls:
• Near call procedures within the same current code segment. It
provides access to local procedures within the current running task
(process)
• Far call are usually used to access operating system procedures or
procedures in a different task.
• The CALL instruction does the following:
1. Pushes the value of the EIP register (which contains the offset
of the instruction following the CALL instruction) on the stack (for use later as a return-instruction pointer).
2. Causes the update of ESP
3. Updates the EIP to the address of the first instruction in the CALLEE
RET Instruction – Volume 2B 4-555
• The RET instruction does the exact opposite of the CALL instruction.
• RET instruction transfers program control to a return address located on the top of the stack. The address is usually placed on the stack by a CALL instruction, and the return is made to the instruction that follows the CALL instruction. Intel Volume 2B page 1731
• RET instruction allows a program to increment the stack pointer on a return to release parameters from the stack. The number of bytes released from the stack is determined by an optional argument (n) to the RET instruction
• The final step being to set the EIP to be the address previously stored on the stack.
• The RET instruction also allows near and far returns to match the near and far versions
of the CALL instruction.
• The optional source operand can be used to release parameters from the stack that were passed to the called procedure and are no longer needed
Near and Far Calls
Procedure Calls
The ENTER instruction does the exact same task as the CALL. It goes a step further and sets up the stack. A set of steps referred to as the prolog.
The LEAVE instruction does the same task as RET. It goes a step further and cleans the stack frame. This step is referred to as the epilog.
EIP,JMP,CALL AND RET INSTRUCTIONS
• push x -Decrements rsp by the size of the operand, then store x in [rsp]
• pop x -Move [rsp] into x, then increment rsp by the size of the operand
• jnz label -If the processor’s Z (zero) flag, is set, jump to the given label
• call label Push the address of the next instruction, then jump to the label
• ret Pop into the instruction pointer (eip)
Calling Convention2
There are a few calling conventions available to the various Application Programming interfaces.
A calling convention is a predefined process that is used by functions in determining how they will communicate.
For example:
1. How will arguments be passed onto the stack
2. Which function will perform the stack clean-up.
• This has been the source of much debate (Linux and Unix) The following pages will describe the conventions available.
C Declaration Convention
CDECL aka C declaration The convention used by GCC
1. Arguments are passed to the stack from right to left
2. Stack Cleanup is completed by the Caller
3. Return value from the function is return in the EAX register
Standard Call Convention
STDCALL
The convention used by Windows
1. Arguments are passed to the stack from right to left
2. Stack Cleanup is completed by the Callee
3. Return value from the function is return in the EAX register
x86-64 SystemV
The convention used by Linux (GCC, intel compiler)
1. Arguments are passed to via registers in the following order
1. RDI, RSI, RDX, RCX, R8, R9
2. Return value from the function is returned in the EAX register
3. Caller cleans up stack
4. Stack aligned on 16 byte boundary
x86-64 Microsoft
The convention used by Microsoft
1. Arguments are passed to via registers
1. RCX, RDX, R8, R9
2. Return value from the function is returned in the EAX register
3. Stack aligned on 16 byte boundary
4. Stack cleanup by caller
Memory Management -Segmentation
Manual Vol 3A Chapter 3 page 2883
IA-32 architecture memory management has two mechanisms:
1. Segmentation –isolates code ,data and stack modules so multiple tasks can run on the same processor without interfering with one another.
• It provides a mechanism to divide processor’s linear address space into space called segments.
• To locate a byte in a particular segment a logical address must be provided. Each segment has a segment descriptor, which specifies the location of the first byte of the segment in the linear address space (called the base address of the segment). The offset part of the logical address is added to the base address for the segment to locate a byte within the segment.
• The base address plus the offset thus forms a linear address in the processor’s linear address space.
Memory Management -Paging
2. Paging – Implements demand paging. Virtual memory is mapped into physical memory as needed. Multitasking systems requires more linear address than physical then the virtual address has to be converted into physical address which is handle by processor’ paging mechanism
• In paging each segment is divide into pages usually 4KB = 4096 bytes
• Operating systems maintain a page directory and page tables to keep track of the pages
• When a task attempts to access an address location in the linear address space, the
processor uses the page directory and page tables to translate the linear address into a physical address and then performs the requested operation (read or write) on the memory location.
Intel Manual Vol 3A
32- bit Paging
• The processor translates every logical address into a linear address. A linear address is a 32-bit address. (2^32) bytes (4 GBytes). This is the address space that the processor can address on its address bus. With addresses ranging continuously from 0 to FFFFFFFFH
• 32-bit paging uses a hierarchy of paging structures to produce a translation for a linear address. CR3 is used to locate the first paging-structure, the page directory.
• A page directory (PD) for pages of 4KB is located at the physical address specified in bits 31:12 of CR3 register
• A page directory comprises 1024 32-bit entries (PDEs).
• A PDE is selected using the physical address defined as follows:
➢Bits 39:32 are all 0.
➢Bits 31:12 are from CR3.
➢Bits 11:2 are bits 31:22 of the linear address. ➢Bits 1:0 are 0
Linear Address Translation e.g
If the following Linear address, Page Directory Entry, Page Table Entry and CR3 addresses are provided what is the physical address for the following page 0x797EEA63?
a. Linear Address (Virtual address VA): 0xA0B780C0
b. PDE: 0x71A0E828
c. P TE: 0x41D05BC0
d. CR3: 0x118C8502
1. Convert Linear Address in Binary and separate the bits into 10 +10 + 12 1010 0000 1011 0111 1000 0000 1100 0000
2. Next find the address to read from PDE as follows
▪ Identify first 20 bits from CR3 known as base address 0x118C8
▪ Calculate the offset (12 bits). The offset is the combination of the first
10 bits from Linear address (MSB of VA) 1010 0000 10 + 00 (as
described in Intel manual page 2906 the bits 1:0 should be 0) 1010 0000 1000 = A08 .
▪ PDE 0x71A0E828 is at address 0x118C8A08
Linear Address Translation e.g
3. Next find the address to read from PTE as follows:
▪ ▪
Identifythefirst20bitsfromPDE0x71A0E Calculatetheoffset(12bits).Theoffsetisthecombinationofthenext10bitsfromLinear address (VA) 11 0111 1000+ 00 = 1101 1110 0000 = DE0
PTE 0x41D05BC0 is at address 0x71A0EDE0 4. Now we can find the physical address as follows:
• Identify the first 20 bits of PTE: 0x41D05
• The offset is the offset of the Linear Address (Virtual Address). The 12 LSB of VA
0000 1100 0000 = 0C0
• Page 0x797EEA63 is located at physical address 0x41D050C0
▪