代写 R C android Java math compiler security CSCI2467: Systems Programming Concepts

CSCI2467: Systems Programming Concepts
Slideset 3: Integer values and arithmetic (CS:APP 2.2, 2.3)
Instructor: Matthew Toups
Spring 2019
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

A few announcements
Keep working on datalab! We will discuss more today Check correctness with ./btest
Test for illegal operators with ./dlc bits.c
Get final score with ./driver.pl
(all of this is on page 3 of writeup; keep it close by)
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Overview
Course notes
1 Signed and Unsigned ints
History
Two’s complement Ranges
Why does this matter?
2 Conversion, casting Conversion
Mixing signed and unsigned Possible sources of error Preserving the sign bit
3 Integer arithmetic
Addition Multiplication Summary
4 Bytes in memory & security Addressing memory
Ordering multi-byte values Strings
Security implications
Common vulnerabilities involving signed/unsigned
5 Magic
XOR is magic!
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

How we got here
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Comparing Integer Representations
We‛ve finally arrived at the end of our competition. Let‛s see that scoreboard!
We‛ve finally arrived at the end of our competition. Let‛s see that scoreboard!
Unsigned Sign Magnitude
Compa
The Thrilling Conclusion!
a
Representations
a
r
R
r
r
r
i
i
i
n
n
n
g
I
g
I
g
I
n
n
n
t
e e e
g
t
g
t
g
N
N
?
N
?
e
e
e
T
g g g
onclusion! C
Zero = 0000 0000
T
o
T
o
g
g
g
h
h
h
Negation?
a
t
a
t
a
t
e
T
e
T
e
T
i
i
i
o
o
o
n
n
n
h
h
h
?
r
r
r
i
i
i
l
i
l
i
l
i
l l l
r
e
e
e
n
C
n
C
n
r
R
One Zero?
Unsigned
One‛s Complement
Sign Magnitude Two‛s Complement
Bias One‛s Complement
Two‛s Complement
Well, well! It appears we have a three-way tie among Unsigned, Two‛s Complement,
O O O
n
? ? ?
n
o
n
o
e
Z
e
Z
e
Z
e
r
e
r
e
r
o
0 0 0
0 0 0
0
o
0 0 0
Z
Z
o
= = =
Z
o
0
0
0
0
e
r
e
r
e
r
0
0 0 0
0
0
0
0
0
0
Continuous?
Continuous?
Monotonically Increasing?
Bias
and Bias! We can certainly give each of our winners a prize, though!
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic
Monotonic Increasin
unsigned char foo = 24;

Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Encoding Integer values
Unsigned
w−1 B2U(X)=􏰁xi ·2i
Signed B2T(X)=−xw−1·2w−1+􏰁xi ·2i
i=0
w−2 i=0
Change: Sign bit! Example using short int in C (2 bytes):
Change: Sign bit!
B2T(X)=−xw−1 ·2w−1 +􏰁xi ·2i
w−2 i=0
Decimal
Hex
Binary
2467 -2467
09A3 F65D
00001001 10100011 11110110 01011101
–
–
This is called Two’s complement Sign bit indicates sign
0 for non-negative
1 for negative
Course notes
Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Unsigned Integers
23 = 8
22 = 4
21 = 2
20 = 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
[0001] [0101] [1011] [1111]
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Signed Integers
[1011] [1111]
– 23 = –8 23 = 8
22 = 4
21 = 2
20 = 1
–8–7–6–5–4–3–2–1 0 1 2 3 4 5 6 7 8 9 10 111213141516
+16
+16
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Back to the 2’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
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Numeric Ranges
Unsigned values
– UMin=0
000 … 0
– UMax=2w −1
111 … 1
Two’s complement values – TMin=−2w−1
100…0
– TMax=2w−1−1
011…1
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
Values for w = 16 (short int)
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

16-bit sheep counter
Source: xkcd.com
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Values for Different Word Sizes
W (bits) 81632 64
UMax TMax TMin
255
127 -128
65535
32767 -32768
4,294,967,295
2,147,483,647 -2,147,483,648
18,446,744,073,709,551,615 9,223,372,036,854,775,807 -9,223,372,036,854,775,808
Observations:
|TMin| = TMax + 1 (Asymmetric range) UMax = 2∗TMax +1
C Programming #include Defines constants: ULONG MAX
LONG MAX
LONG MIN
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Data Types in C
C Data Type char short
int
long
float double long double
pointer
Typical 32-bit 1
2
4
4
4 8 –
4
Typical 64-bit 1
2
4
8
4 8 –
8
x86-64 1
2
4
8
4
8 10/16
8
Size in Bytes
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Unsigned & Signed Numeric Values
Unsigned & Signed Numeric Values
X
0000
0001
0100
0101
B2U(X)
0
4
B2T(X)
¢ Equivalence
§ Same encodings for nonnega;ve
values
¢ Uniqueness
§ Every bit paTern represents
unique integer value
§ Each representable integer has unique bit encoding
¢ ⇒ Can Invert Mappings § U2B(x) = B2U-1(x)
§ Bit paTern for unsigned integer
§ T2B(x) = B2T-1(x)
§ Bit paTern for two’s comp integer
0
1
1
0010
2
2
0011
3
3
4
5
5
0110
6
6
0111
1000
7
7
8
–8
1001
9
–7
1010
1100
1101
10
12
–6
1011
11
–5
–4
13
–3
1110
14
–2
1111
15
–1
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 20

Real-world problems!
Why does any of this matter? Rocket science (Fatal bug in Patriot missile, Ariane-5 explosion)
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Course notes
1 Signed and Unsigned ints
History
Two’s complement Ranges
Why does this matter?
2 Conversion, casting Conversion
Mixing signed and unsigned Possible sources of error Preserving the sign bit
3 Integer arithmetic
Addition Multiplication Summary
4 Bytes in memory & security Addressing memory
Ordering multi-byte values Strings
Security implications
Common vulnerabilities involving signed/unsigned
5 Magic
XOR is magic!
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Mapping Between Signed & Unsigned
Mapping Between Signed & Unsigned
Two’s Complement
Unsigned
x ux
B2U
Maintain Same Bit PaTern
Unsigned
Two’s Complement
T2B
T2U
X
U2T
ux x
Maintain Same Bit PaTern
¢ Mappings between unsigned and two’s complement numbers: Keep bit representa6ons and reinterpret
U2B
B2T
X
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 22
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Unsigned → Signed (U2T)
2w
2w–1 +2w–1 Unsigned
00 –2w–1
Two’s complement
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Signed → unsigned (T2U)
2w +2w–1 2w–1
Two’s 0 0 complement
–2w–1
Unsigned
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Mapping Signed ↔ Unsigned
Carnegie Mellon
Mapping Signed ↔ Unsigned
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
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Mapping Signed ↔ Unsigned
Carnegie Mellon
Mapping Signed ↔ Unsigned
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
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Carnegie Mellon
Relation between Signed & Unsigned
Rela6on between Signed & Unsigned
Two’s Complement
Unsigned
T2B
B2U
T2U
X
x ux
Maintain Same Bit PaTern
w–1 0 ux +++ ••• +++
-++ ••• +++
Large nega6ve weight
becomes
Large posi6ve weight
x
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 25
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Conversion Visualized
Carnegie Mellon
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
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Carnegie Mellon
Signed vs. Unsigned in C
Signed vs. Unsigned in C
¢ Constants
§ By default are considered to be signed integers § Unsigned if have “U” as suffix
0U, 4294967259U
¢ Cas6ng
§ Explicit cas;ng between signed & unsigned same as U2T and T2U
int tx, ty;
unsigned ux, uy;
tx = (int) ux;
uy = (unsigned) ty;
§ Implicit cas;ng also occurs via assignments and procedure calls tx = ux;
uy = ty;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 27
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Casting surprises!
Expression Evaluation:
If there is a mix of unsigned and signed in single expression, signed values implicitly cast to unsigned
includes comparison operations > < == <= >=
When W=32: TMIN= -2,147,483,648 TMAX= 2,147,483,647
Constant1 Relation Constant2
0 0U
0 == 0U
-1 0
-1 < 0 -1 0U -1 > 0U 2147483647 -2147483647-1 2147483647 > -2147483647-1 2147483647U -2147483647-1 2147483647U < -2147483647-1 Evaluation unsigned signed unsigned signed unsigned Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic -1 -2 -1 > -2 signed

Casting Signed ↔ Unsigned: Basic rules
Bit pattern is maintained
… but reinterpreted
Can have unexpected effects: adding or subtracting 2w Expression containing signed and unsigned int:
int is cast to unsigned ! (implicitly)
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Pitfalls of unsigned
Don’t use unsigned without understanding implications: It is easy to make mistakes!
unsigned i;
for (i = cnt-2; i >= 0; i–)
a[i] += a[i+1];
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Pitfalls of unsigned
Don’t use unsigned without understanding implications: It is easy to make mistakes!
unsigned i;
for (i = cnt-2; i >= 0; i–)
a[i] += a[i+1];
Can be very subtle:
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DELTA >= 0; i-= DELTA)
…
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Counting down with unsigned
A better way to use loop index:
unsigned i;
for (i = cnt-2; i < cnt; i--) a[i] += a[i+1]; C Standard guarantees that unsigned addition will behave like modular arithmetic: 0 − 1 → UMax Modular arithmetic is useful in many situations. Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Why even use unsigned then? Do use when performing modular arithmetic (multiprecision arithmetic) Do use when using bits to represent sets Logical right shift → no sign extension Java? no unsigned! Everything is signed. introduces >>> for logical shift (>> is arithmetic shift)
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Sign extension
Sign Extension
¢ Task:
§ Given w-bit signed integer x
§ Convert it to w+k-bit integer with same value
¢ Rule:
§ Make k copies of sign bit:
§ Xʹ′= xw–1,…,xw–1,xw–1,xw–2,…,x0
k copies of MSB
w
•••
X
•••
Xʹ′
••• •••
kw
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 31
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Sign extension example
short int x = 2467; int ix = (int) x; short int y = -2467; int iy = (int) y;
Decimal
Hex
Binary
x ix y iy
2467
2467 -2467 -2467
09 A3 00 00 09 A3 F6 5D FF FF F6 5D
00001001 10100011 00000000 00000000 00001001 10100011 11110110 01011101 11111111 11111111 11110110 01011101
Converting from smaller to larger integer data type: C automatically performs sign extension
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Carnegie Mellon
Unsigned addition
Unsigned Addi6on
•••
Operands: w bits True Sum: w+1 bits
u +v
u+v UAddw(u , v)
•••
•••
Discard Carry: w bits
¢ Standard Addi6on Func6on
•••
§ Ignores carry output
¢ Implements Modular Arithme6c
s = UAddw(u,v) = u+v mod2w
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 35
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Visualizing (Mathematical) Integer addition
Visualizing (Mathema6cal) Integer Addi6on
¢
Integer Addi6on
§ 4-bit integers u, v
§ Compute true sum Add4(u , v)
§ Values increase linearly with u and v
§ Forms planar surface
Add4(u , v)
CS:APP3e Figure 2.21: With a 4-bit word size, the sum could require 5 bits.
Integer Addition
32 28 24
20 16 12
14
8 46v
12
10 8
0
022
4
u4 6 8 10
14
0 12
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 36

Visualizing Unsigned addition
Visualizing Unsigned Addi6on
¢
Wraps Around § If true sum ≥ 2w § At most once
True Sum
2w+1 2w
0
Overflow
Overflow
Modular Sum
CS:APP3e Figure 2.23: With a 4-bit word size, addition is performed modulo 16.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 37
UAdd4(u , v)
16 14 12 10
8
6 12
4 2 0
u
14 10
8v 4
0246 2
6
8 10 12
0
14
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Two’s Complement Addition
•••
Operands: w bits u
•••
True Sum: w+1 bits
Discard Carry: w bits TAddw(u , v)
+v u+v
•••
•••
¢ TAdd and UAdd have Iden6cal Bit-Level Behavior § Signed vs. unsigned addi;on in C:
int s, t, u, v;
s = (int) ((unsigned) u + (unsigned) v); t=u+v
§ Will give s == t
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 38
Two’s Complement Addi6on

TAdd Overflow
TAdd Overflow
¢
Func6onality
§ True sum requires w+1
bits
§ Drop off MSB
§ Treat remaining bits as 2’s comp. integer
0 111…1 0 100…0 0 000…0 1 011…1 1 000…0
True Sum
2w–1 2w –1–1
0
–2w –1 –2w
PosOver
TAdd Result
011…1 000…0 100…0
NegOver
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 39

Visualizing Two’s Complement Addition
Visualizing 2’s Complement Addi6on
¢
¢
NegOver
Values
§ 4-bit two’s comp.
§ Range from -8 to +7
Wraps Around
§ If sum ≥ 2w–1
§ Becomes nega;ve § At most once
§ If sum < –2w–1 § Becomes posi;ve § At most once TAdd4(u , v) 8 6 4 2 0 6 -2 4 -4 -6 -8 2 0 -2 -4 v PosOver -8 -2 -6 -4 -6 u 02 -8 4 6 Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 40 Multiplication ¢ ¢ ¢ Goal: Compu6ng Product of w-bit numbers x, y § Either signed or unsigned But, exact results can be bigger than w bits § Unsigned: up to 2w bits § Resultrange:0≤x*y≤(2w –1)2 = 22w –2w+1 +1 § Two’s complement min (nega;ve): Up to 2w-1 bits § Result range: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1 § Two’s complement max (posi;ve): Up to 2w bits, but only for (TMinw)2 § Result range: x * y ≤ (–2w–1) 2 = 22w–2 So, maintaining exact results... § would need to keep expanding word size with each product computed § is done in soNware, if needed § e.g., by “arbitrary precision” arithme;c packages Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 41 Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Mul6plica6on Unsigned Mul6plica6on in C Unsigned Multiplication in C ••• ••• u *v UMultw(u , v) ¢ Standard Mul6plica6on Func6on § Ignores high order w bits ¢ Implements Modular Arithme6c UMultw(u , v)= u ·∙ v mod 2w Operands: w bits True Product: 2*w bitsu · v ••• ••• Discard w bits: w bits ••• Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 42 Signed Mul6plica6on in C Signed Multiplication in C ••• ••• Operands: w bits True Product: 2*w bitsu · v Discard w bits: w bits u *v TMultw(u , v) ••• ••• ¢ Standard Mul6plica6on Func6on § Ignores high order w bits § Some of which are different for signed vs. unsigned mul;plica;on § Lower bits are the same ••• Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 43 Power-of-2 Multiply with Shift ¢ Opera6on § u << k gives u * 2k § Both signed and unsigned k Operands: w bits True Product: w+k bits Discard k bits: w bits u · 2k u * 2k UMultw(u , 2k) TMultw(u , 2k) 0 ••• 0 1 0 ••• 0 0 ••• Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 44 ••• 0 0 ¢ Examples § u<<3 == u*8 § (u<<5)–(u<<3)== u*24 § Most machines shiN and add faster than mul;ply § Compiler generates this code automa;cally ••• ••• ••• 0 0 0 0 Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Power-of-2 Mul6ply with ShiY Carnegie Mellon Unsigned Power-of-2 Divide with Shift ¢ Quo6ent of Unsigned by Power of 2 § u>>kgives ⎣u/ 2k⎦ § Uses logical shiN
Operands:
u ••• k •••
/ 2k 0 ••• 0 1 0 ••• 0 0
BinaryPoint
Division: u/2k 0 ••• 00 Result: ⎣u/2k⎦ 0 ••• 0 0
••• . ••• •••
H
x 15213 15213 3B 6D 00111011 01101101
1 0 0
Division
Division
Computed
Computed
ex Hex
Binary Binary
x
x> x>
> 1 > 4 > 8
2467
7606.5 950.8125
1233.5
59.4257813
154.1875
9.63671875
Computer Systems: A Programmer’s
59
154 Perspec;ve, Third Edi;on 9
2467
7606 950
09 A3
D B6 000 3 B6 000
00001001 10100011
11101 10110110 00011 10110110
x >> 1 x>
1233
04 D1
0 3B 000
00000100 11010001
00000 00111011
x >> 4
00 9A 00 09
00000000 10011010
x >> 8
Bryant and O’Hallaron,
00000000 00001001
45
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic
Unsigned Power-of-2 Divide with ShiY

Summary of Arithmetic Rules
Arithme6c: Basic Rules
¢ Addi6on:
§ Unsigned/signed: Normal addi;on followed by truncate,
same opera;on on bit level
§ Unsigned: addi;on mod 2w
§ Mathema;cal addi;on + possible subtrac;on of 2w
§ Signed: modified addi;on mod 2w (result in proper range)
§ Mathema;cal addi;on + possible addi;on or subtrac;on of 2w ¢ Mul6plica6on:
§ Unsigned/signed: Normal mul;plica;on followed by truncate, same opera;on on bit level
§ Unsigned: mul;plica;on mod 2w
§ Signed: modified mul;plica;on mod 2w (result in proper range)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 47
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

C int Puzzles!
If…
x < 0 x&7==7 x > y
x>0&&y>0 x ≥ 0
x ≤ 0
true for all values, or false? ⇒ (x ∗ 2) < 0 ux ≥ 0 ⇒(x <<30)<0 ux > −1
⇒ −x < −y x∗x≥0 ⇒x+y>0
⇒ −x ≤ 0
⇒ −x ≥ 0
(x | −x)>>31==−1 ux >> 3 == ux/8
x >> 3 == x/8
x & (x − 1) ! = 0
int x = foo(); int y = bar(); unsigned ux = x; unsigned uy = y;
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Byte-Oriented Memory Organiza6on
Byte-oriented memory organization
• • •!
¢
Programs refer to data by address
§ Conceptually, envision it as a very large array of bytes § In reality, it’s not, but can think of it that way
§ An address is like an index into that array
§ and, a pointer variable stores an address
Note: system provides private address spaces to each “process”
¢
§ Think of a process as a program being executed
§ So, a program can clobber its own data, but not that of others
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 52

Machine Words
Machine Words
¢ Any given computer has a “Word Size” § Nominal size of integer-valued data
§ and of addresses
§ Un;l recently, most machines used 32 bits (4 bytes) as word size
§ Limits addresses to 4GB (232 bytes)
§ Increasingly, machines have 64-bit word size
§ Poten;ally, could have 18 EB (exabytes) of addressable memory § That’s 18.4 X 1018
§ Machines s;ll support mul;ple data formats § Frac;ons or mul;ples of word size
§ Always integral number of bytes
Coursenotes BryantandSOig’Hnaelladroann,dCoUmpnustiegrnSeydsteimntss:AProgrammeCr’soPnevrseprescio;vne,,TchaisrdtiEndgi;on Integerarithmetic Bytesinmemory&security53 Magic

Word-Oriented Memory Organiza6on
Word-oriented memory organization
¢
Addresses Specify Byte
Loca6ons
§ Address of first byte in word
§ Addresses of successive words differ by 4 (32-bit) or 8 (64-bit)
32-bit! 64-bit! Bytes! Addr.! Words! Words!
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
Addr ! =! 0?0?00
Addr ! =! 0?0?12
Addr ! =! 0?0?00
Addr ! =! 0?0?04
Addr ! =! 0?0?08
Addr ! =! 0?0?08
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspec;ve, Third Edi;on 54
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

ExampElexDaamta pRleprDeseantatiRonespresenta6ons
C Data Type
Typical 32-bit
Typical 64-bit
x86-64
char
1
1
1
short
2
2
2
int
4
4
4
long
4
8
8
float
4
4
4
double
8
8
8
long double
−
−
10/16
pointer
4
8
8
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Byte Ordering
Byte ordering
¢ So, how are the bytes within a mul6-byte word ordered in memory?
¢ Conven6ons
§ Big Endian: Sun, PPC Mac, Internet
§ Least significant byte has highest address
§ LiTle Endian: x86, ARM processors running Android, iOS, and
Windows
§ Least significant byte has lowest address
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Byte Ordering Example
Byte ordering example
¢ Example
§ Variable x has 4-byte value of 0x01234567 § Address given by &x is 0x100
Big Endian! Little Endian!
0x100 0x101 0x102 0x103
0x100 0x101 0x102 0x103
01
23
45
67
67
45
23
01
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Representing strings
¢
Strings in C
§ Represented by array of characters
§ Each character encoded in ASCII format
§ Standard 7-bit encoding of character set § Character “0” has code 0x30
– Digit i has code 0x30+i
§ String should be null-terminated
§ Final character = 0
char S[6] = “18213”;
IA32! Sun!
31
31
38
38
32
32
31
31
33
33
¢ Compa6bility
§ Byte ordering not an issue
00
00
Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic
Represen6ng Strings

Code security example
Similar to FreeBSD’s implementation of getpeername()1
/* Kernel memory region holding user-accessible data */
#define KSIZE 1024 char kbuf[KSIZE];
/*Copy at most maxlen bytes from kernel region to user buffer*/
int copy_from_kernel(void *user_dest , int maxlen) {
/* Byte count len is minimum of buffer size and maxlen */ int len = KSIZE < maxlen ? KSIZE : maxlen; memcpy(user_dest, kbuf, len); return len; } #define MSIZE 528 void getstuff () { char mybuf[MSIZE]; copy_from_kernel(mybuf, MSIZE); printf("%s\n", mybuf); } 1See CVE-2002-0973 for more info on this real-world security vulnerability. Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Malicious usage /* Declaration of library function memcpy */ void *memcpy(void *dest, void *src, size_t n); /* Kernel memory region holding user-accessible data */ #define KSIZE 1024 char kbuf[KSIZE]; /*Copy at most maxlen bytes from kernel region to user buffer*/ int copy_from_kernel(void *user_dest , int maxlen) { /* Byte count len is minimum of buffer size and maxlen */ int len = KSIZE < maxlen ? KSIZE : maxlen; memcpy(user_dest, kbuf, len); return len; } #define MSIZE 528 void getstuff () { char mybuf[MSIZE]; copy_from_kernel(mybuf, -MSIZE); printf("%s\n", mybuf); } Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic Overview Course notes 1 Signed and Unsigned ints History Two’s complement Ranges Why does this matter? 2 Conversion, casting Conversion Mixing signed and unsigned Possible sources of error Preserving the sign bit 3 Integer arithmetic Addition Multiplication Summary 4 Bytes in memory & security Addressing memory Ordering multi-byte values Strings Security implications Common vulnerabilities involving signed/unsigned 5 Magic XOR is magic! Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic XOR is magic XOR (^) has magic powers! temp = a; a = b; b = temp; Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic XOR is magic Swap a and b without a temporary variable! a = a ^ b; b = a ^ b; a = a ^ b; Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic XOR is magic How the magic works: (see page 54 in CS:APP text) x = y = // // x = // // // // x x y x x ^ y ; // x == A, y == B ^ y ; // x == A ^ B, y == B == (A ^ B) ^ B == A ^ (B ^ B) ==A ^0 ^ y ; // == ( ==( ==0 ==B A ^ A^ ^B x == A ^ B, y == A B ) ^ A A)^B Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic XOR magic is crucial If we have 3 “data” bits and 1 “parity” bit... Course notes Signed and Unsigned ints Conversion, casting Integer arithmetic Bytes in memory & security Magic

Related Posts