Propagation Rules in MemorySanitizer
MemorySanitizer
It takes time for me to fully understand its Shadow propagation rules so I want to write down my explanation
The paper assumed all newly allocated memory is “poisoned”, i.e. corresponding shadow memory is filled with 0xFF, signifying that all bits of this memory are uninitialized.
Given an instruction A = op B, C, we generate one or more instructions implementing A′ = op′ B, C, B′, C′, where A′ stands for the shadow value corresponding to the application value A
| original op | shadow operations |
|---|---|
| A = load P | check P ′, A′ = load (P & ShadowMask) |
| store P, A | check P ′, store (P & ShadowMask), A′ |
| A = const | A′ = 0 |
| A = undef | A′ = 0xff |
| A = B & C | A′ = (B′ & C′) |(B & C′) |(B′ & C) |
| A = B | C | A′ = (B′ & C′) |(∼B & C′) |(B′ & ∼C) |
| A = B xor C | A′ = B′ | C′ |
| A = B ≪ C | A′ = (sign-extend(C′ != 0)) |(B′ ≪ C) |
The design of propagation must satisfy If one of the operands has a non-zero shadow bit in a location where corresponding value bit affects the operation result, then the result shadow must be non-zero. Therefore, the core issue is how to decide which bit affects the operation
and
1
2
3
4
5
6
7
8
9
# A = B & C
if B&C:
A' = B' | C'
elif B:
A' = C'
elif C:
A' = B'
else:
A' = B' & C'
| B | C | op |
|---|---|---|
| 1 | 1 | A’=B’ | C’ |
| 0 | 0 | A’=B’ & C’ |
| 1 | 0 | C’ |
| 0 | 1 | B’ |
| This equals to A′ = (B′ & C′) | (B & C′) | (B′ & C) |
or
1
2
3
4
5
6
7
8
9
# A = B | C
if !B & !C:
A' = B' | C'
elif B & !C:
A' = B'
elif !B & C:
A' = C'
else:
A' = B' & C'
| B | C | op |
|---|---|---|
| 1 | 1 | A’=B’ & C’ |
| 0 | 0 | A’=B’ | C’ |
| 1 | 0 | B’ |
| 0 | 1 | C’ |
This equals to A′ = (B′ & C′) |(∼ B & C′) |(B′ & ∼ C)
xor
1
2
# A = B xor C
A' = B' | C'
This is because B and C both contribute to A in every match of B and C
Similar, for any computing operation, the both of the inputs contribute to the result. For example, A = B+C => A' = B'|C'
left shift
1
2
3
# A = B << C
if C' != 0:
A' = B' << C
The A’ is set to B' << C when C’ is not initialized
My Comment
In my view, I do not think it is necessary to use Memory Sanitizer, since the overhead for uninitialized if too big and Address Sanitizer can handle most of them. Indeed, the propagation rules can decrease the false positive rate, while I willing to consider the false positive as a warning for the developers. I believe every usage of uninitialized values is wrong.