Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
CSCI2467: Systems Programming Concepts
Midterm review
Instructor: Matthew Toups
Spring 2019
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
Scores so far
Your lab scores to date are posted in AutoLab (see gradebook)
Many folks lost points on datalab due to insufficient explanations in comments
Note that your grace day and late penalty are automatically applied by AutoLab
– Email if there appears to be an error
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
Upcoming exam
Midterm exam: Monday Feb 25, Wed Feb 27
Location: Math 102
– Given during class time, 50 minutes per day, closed book
– We will provide a sheet of notes and helpful values,
you will only bring something to write with.
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
Two exam dates
Monday: chapter 2 (2.1-2.4)
– no floating point
– see practice problems (in later slides)
– see activity handouts
– be able to explain datalab solutions
Wednesday: chapter 3 (3.1-3.6)
– will present problems in Intel assembly format
– see practice problems (in later slides)
– see activity handout problems
– be able to identify things you have seen in bomblab
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
Class updates
1 Midterm format
2 Chapter 2: Data operators
int
Conversion between signed & unsigned
3 Chapter 3: Machine-level programs Arithmetic
Control Activities
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs
Midterm format
Fill in a table with missing values
– small examples (less than 32-bit)
– using binary two’s complement representation of ints
– using binary operations, masking, arithmetic (w/ overflow)
– is an expression true for all values?
Datalab:
– Given some C code, fill in a blank or table of values
– Given a C function, fill in comments explaining how it is solved
Bomblab:
– Fill in missing C source code (based on given disassembly)
– Given multiple C functions, circle the correct one
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs operators
Class updates
1 Midterm format
2 Chapter 2: Data operators
int
Conversion between signed & unsigned
3 Chapter 3: Machine-level programs
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs operators
Boolean Algebra
Algebraic representation of logic, developed by Boole in 1850s Encodes “True” as 1 and “False” as 0
Binary AND:
A&B = 1 when
both A = 1 and B = 1
Binary OR:
A|B = 1 when
either A = 1 or B = 1
&01 |01 000 001 101 111
Binary NOT (complement): Exclusive-Or (XOR):
∼ A = 1 when A = 0 A ∧ B = 1 when either A = 1
or B = 1 but not both
∼1
01 ∧01 10 001
Based on Figure 2.7 in CS:APP3e
110
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs operators
Logical operators
Don’t confuse bitwise and logical operators! They look similar but are very different.
&&, || , !
– View 0 as “False”
– View anything non-zero as “True”
– Always return 0 or 1
– Early termination!
Examples:
!0x41 ⇒ 0x00
!0x00 ⇒ 0x01
!!0x41 ⇒ 0x01
0x69 && 0x55 ⇒ 0x01 0x69 || 0x55 ⇒ 0x01
a && 5/a (will never divide by zero) p && *p (avoids null pointer access)
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs operators
Shift operators
Left Shift: x << y
- Shift bitvector x left y positions
(Throw away extra bits on left)
- Fill with 0s on right
Right Shift: x >> y
– Shift bitvector x right y positions
(Throw away extra bits on right)
⋆ Logical shift: fill with 0s on left
⋆ Arithmetic shift: Replicate most significant bit on left
Undefined: Shift < 0 or ≥ word size
Examples
Argument x << 3 Log. >> 2 Arith. >> 2
01100010
00010000
00011000
00011000
Argument x << 3 Log. >> 2 Arith. >> 2
10100010
00010000
00101000
11101000
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs int
two’s complement encoding example
short int x= 2467: 00001001 10100011 short int y= -2467: 11110110 01011101
Weight
1 2 4 8
16 32 64
128
2467
11 12 00 00 00 1 32 00 1 128
-2467
11 00 14 18 1 16 00 1 64 00
256
512 1024 2048 4096 8192 16384 -32768
1 256 00 00 1 2048 00 00 00 00
00 1 512 1 1024 00 1 4096 1 8192 1 16384 1 -32768
Sum:
2467
-2467
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs int
Numeric Ranges
Unsigned values
– UMin=0
000 … 0
– UMax=2w −1
Two’s complement values – TMin=−2w−1
100…0
– TMax=2w−1−1
111 … 1
011…1 Values for w = 16 (short int)
Decimal
Hex
Binary
UMax TMax TMin -1
0
65535
32767 -32768 -1 0
FF FF 7F FF 80 00 FF FF 00 00
11111111 11111111 01111111 11111111 10000000 00000000 11111111 11111111 00000000 00000000
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
Carnegie Mellon
Mapping Between Signed & Unsigned
Mapping Between Signed & Unsigned
Two’s Complement
Unsigned
T2B
B2U
T2U
X
x ux
Maintain Same Bit PaTern
Unsigned
Two’s Complement
U2B
B2T
U2T
X
ux x
Maintain Same Bit PaTern
¢ Mappings between unsigned and two’s complement numbers: Keep bit representa6ons and reinterpret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 22
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
Mapping Signed ↔ Unsigned
Carnegie Mellon
↔
Bits
Signed
T2U U2T
Unsigned
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
4
0101
5
5
0110
6
6
0111
7
7
1000
-8
8
1001
-7
9
1010
-6
10
1011
-5
11
1100
-4
12
1101
-3
13
1110
-2
14
1111
-1
15
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 23
Mapping Signed Unsigned
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
Mapping Signed ↔ Unsigned
Carnegie Mellon
↔
Bits
Signed
=
+/- 16
Unsigned
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
4
0101
5
5
0110
6
6
0111
7
7
1000
-8
8
1001
-7
9
1010
-6
10
1011
-5
11
1100
-4
12
1101
-3
13
1110
-2
14
1111
-1
15
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 24
Mapping Signed Unsigned
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
Carnegie Mellon
Conversion Visualized
Conversion Visualized
¢ 2’s Comp. → Unsigned § Ordering Inversion
§ Nega;ve → Big Posi;ve
UMax UMax – 1
TMax + 1 TMax
TMax
Unsigned Range
2’s Complement Range
–2
TMin
00 –1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 26
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
Practice
CSCI 2467, Spring 2019
Class Activity: Two’s complement, bitwise and logical operators Friday, February 1
2467 Instructor: M. Toups mtoups@cs.uno.edu
1 Introduction
In this activity you will practice working with binary numbers, bitwise operators, and logical operators. This activity is based in part on material developed by Professor Saturnino Garcia of the University of San Diego and is used with permission.
Each group member will get a copy of the activity to keep. The group’s answers go into the response sheet, which will be turned in.
2 Review of Negative Integers
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Conversion between signed & unsigned
More practice
We strongly recommend you check out these practice problems from the text! Textbook problems:
2.1 through 2.4 2.6 through 2.9 2.12 through 2.16
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Arithmetic
Class updates
1 Midterm format
2 Chapter 2: Data
3 Chapter 3: Machine-level programs Arithmetic
Control Activities
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Arithmetic
Arithemetic operations
Two operand instructions
Pay attention to order of operands
No distinction between signed & unsigned. (why not?)
Format Operands add dest,src sub dest,src imul dest,src sal dest,src sar dest,src shr dest,src xor dest,src and dest,src or dest,src
Computation
dest = dest + src dest = dest – src dest = dest * src dest = dest << src dest = dest >> src dest = dest >> src dest = dest ∧ src dest = dest & src dest = dest — src
(also shl) (arithmetic) (logical)
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Arithmetic
Arithemetic operations
One operand instructions
Format Operand inc dest
dec dest
neg dest
Computation dest = dest + 1 dest = dest – 1 dest = – dest dest = ̃dest
not dest
See CSAPP3e for more on these operations.
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Arithmetic
Arithmetic expression example
long arith
(long x,long y,long z) {
long t1 = x+y;
long t2 = z+t1;
long t3 = x+4;
long t4 = y * 48; long t5 = t3 + t4; long rval = t2 * t5; return rval;
}
arith:
lea rax, [rdi+rsi] add rax , rdx
lea rcx, [rsi+rsi*2] sal rcx, 4
lea rcx, [rdi+4+rcx] imul rax, rcx
ret
Interesting instructions:
lea: address computation sal: shift left
imul: multiplication
(only used once!)
arith:
r
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Ca Control
CondJiutiomnapl ijnumgps
¢ jX Instruc�ons
§ Jump to different part of code depending on condi�on codes
jX
Condi�on
Descrip�on
jmp
1
Uncondi�onal
je
ZF
Equal / Zero
jne
~ZF
Not Equal / Not Zero
js
SF
Nega�ve
jns
~SF
Nonnega�ve
jg
~(SF^OF)&~ZF
Greater (Signed)
jge
~(SF^OF)
Greater or Equal (Signed)
jl
(SF^OF)
Less (Signed)
jle
(SF^OF)|ZF
Less or Equal (Signed)
ja
~CF&~ZF
Above (unsigned)
jb
CF
Below (unsigned)
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Control
Conditional branch example
long absdiff
(long x, long y)
{
long result; if (x > y)
result = x-y;
else
result = y-x;
return result; }
absdiff:
cmp rdi , rsi jle .L2
mov rax , rdi sub rax , rsi ret
.L2: # x <= y
mov rax , rsi sub rax , rdi ret
Compiled with: Register gcc −Og −S absdiff.c −masm=intel rdi
Use
argument x rsi argument y
rax return value
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Activities
CSCI 2467, Spring 2019
Class Activity: Understanding disassembled code Friday, February 15
2467 Instructor: Matthew Toups
Teaching assistants: Caitlin Boyce and Jerod Dunbar
1 Introduction
In this activity you will get practice reading assembly language code which has been disassembled – taken from an existing, compiled program. This “reverse-engineering” technique is especially useful for folks in the cyber security field who are studying malware and software vulnerabilities. It is also an excellent way for anyone to gain a deeper understanding of how their programs are actually compiled and executed. (The questions are from CS:APP3e by Bryant and O’Hallaron, chapter 3.)
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Activities
More practice
CS:APP3e textbook practice problems: 3.18
3.21 3.24 3.26 3.28
Class updates Midterm format Chapter 2: Data Chapter 3: Machine-level programs Activities
Get to work!
We have the rest of the class to work on: - bomblab: get help with gdb / etc
- midterm prep: ask questions