Abstraction example – Integers
Abstraction example – Integers
‹#›
Variable semantics
What does the following line of code do?
unsigned k = 0;
Allocates space for the variable
Associates the space with a variable name
Defines how the data in the storage is interpreted
Initialises the stored data
Let’s test this
‹#›
Example
#include
int main() {
int i;
int sum = 0;
for (i = 0; i < 10; i++)
sum += i;
printf("The sum is %d\n", sum);
}
_main:
pushq %rbp
movq %rsp, %rbp
leaq L_.str(%rip), %rdi
movl $45, %esi
xorl %eax, %eax
callq _printf
xorl %eax, %eax
popq %rbp
retq
L_.str:
.asciz "The sum is %d\n"
‹#›
Compiler abstractions
The compiler generates a concrete implementation of an abstract program description
Preserves semantics (to some extent)
Changes implementation details
May not match intuition
We need to understand the abstraction
‹#›
Unsigned integers
What is the output from:
$ count 4
$ count 2949
$ count 67295
#include
#include
int main(int c, char **v) {
unsigned i, n;
n = strtoul(v[1], NULL, 0);
for (i = n; i < n+10; i++) printf("%u\n", i); } ‹#› Unsigned integer representation Collection of n bits b0…bn-1 Represents the number n depends on the type size and on the implementation An overflow occurs when a result is larger than 2n All arithmetic is modulo 2n ‹#› Signed Integers One sign bit s and n-1 value bits b0…bn-2 Three possible interpretations: Sign magnitude Ones' complement Two's complement Most modern processors use two's complement ‹#› Signed integer overflow Undefined behaviour Use modulo 2n-1 arithmetic Return maximum or minimum values Return zero Do nothing Cause a trap Launch $500M fireworks ‹#› ‹#› Integer overflow vulnerabilities ‹#› Stagefright Before After Why not use chunk_size+size >= SIZE_MAX ?
‹#›
Type Conversion
bool isValidAddition(uint16_t x, uint16_t y)
{
if (x + y < x)
return false;
return true;
}
if ((uint16_t)(x + y) < x)
‹#›
CVE-2017-7602 (LibTIFF)
ma is positive
mb >= size
(overflow ignored)
Test removed!
‹#›
Fix: test for overflow
‹#›
Best practices
Know the language
Undefined behaviours are dangerous
Test user input for overflow
Special attention to input that affects allocation
Use safe tests
Subtract from maximum
Use explicit casts when using types smaller than int
‹#›
Language Support
Java:
Math.multiplyExact, Math.addExact, etc.
C/C++ compilers:
-fwrapv, -ftrapv
-fsanitize
C#
checked
‹#›
bi ⋅2
i
i=0
n−1
∑
b
i
×2
i
i=0
n-1
å
(1− 2s) bi ⋅2
i
i=0
n−2
∑
(1-2s)b
i
×2
i
i=0
n-2
å
(1− 2s) (bi ⊕ s) ⋅2
i
i=0
n−2
∑
(1-2s)(b
i
Ås)×2
i
i=0
n-2
å
bi ⋅2
i
i=0
n−2
∑ − s2n−1
b
i
×2
i
i=0
n-2
å
-s2
n-1
/docProps/thumbnail.jpeg