Remix: On-demand Live Randomization

Remix: On-demand Live Randomization
Yue Chen
, Zhi Wang, David Whalley, Long Lu*
Florida State University, Stony Brook University*
Background
Buffer Overflow -> Code Injection Attack
Background
Buffer Overflow -> Code Injection Attack
Defense: Data Execution Prevention (DEP)
Write XOR Execute: a block (page) of memory cannot
be marked as both writable and executable at the same
time.
Background
Buffer Overflow -> Code Injection Attack
Defense: Data Execution Prevention (DEP)
Write XOR Execute: a block (page) of memory cannot
be marked as both writable and executable at the same
time.
Return-oriented Programming (ROP) Attack
Discover gadgets from 
existing
 
code, and chain
them by 
ret
 instructions
Can be Turing complete
Code Reuse Attack
Existing Code
Chained Gadgets
ROP Defense Strategy
ROP is one example of a broad class of attacks that
require attackers to know or predict the locations of
binary features.
ROP Defense Strategy
ROP is one example of a broad class of attacks that
require attackers to know or predict the locations of
binary features.
Defense Goal
Frustrate such attacks by randomizing feature
space, or remove features
ASLR
A
ddress 
S
pace 
L
ayout 
R
andomization
Executable
Library1
Library1
Executable
First-time
Second-time
ASLR - Problem
Library1
Executable
Pointer Leak
ASLR - Problem
Library1
Executable
Pointer Leak
De-randomized
ASLR - Problem
Brute force 
attacks are still possible (When the
entropy is small. E.g., 32-bit systems.)
Randomized only 
once
.
Goal
Live
 randomization 
during runtime
Finer-grained
 randomization unit
Low
 performance overhead
Highly 
composable
Can and should be combined with other defenses
(traditional ASLR, function randomization, etc.)
Remix
Live basic block (BB) (re-)randomization
within
 functions
A
 
b
a
s
i
c
 
b
l
o
c
k
 
i
s
 
a
 
s
t
r
a
i
g
h
t
-
l
i
n
e
 
c
o
d
e
 
w
i
t
h
o
u
t
j
u
m
p
s
 
i
n
 
o
r
 
o
u
t
 
o
f
 
t
h
e
 
m
i
d
d
l
e
 
o
f
 
t
h
e
 
b
l
o
c
k
.
Remix
Live basic block (BB) (re-)randomization
within
 functions
Advantages:
Advantages:
No function pointer migration
Good spatial locality
A
 
b
a
s
i
c
 
b
l
o
c
k
 
i
s
 
a
 
s
t
r
a
i
g
h
t
-
l
i
n
e
 
c
o
d
e
 
w
i
t
h
o
u
t
j
u
m
p
s
 
i
n
 
o
r
 
o
u
t
 
o
f
 
t
h
e
 
m
i
d
d
l
e
 
o
f
 
t
h
e
 
b
l
o
c
k
.
Remix
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Space
 
for
Alignment
Other Functions
Function A
Remix
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Space
 
for
Alignment
Other Functions
Function A
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Other Functions
Function A
After
0.46 seconds
Remix
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Space
 
for
Alignment
Other Functions
Function A
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Other Functions
Function A
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Other Functions
Function A
After
0.46 seconds
After
2.13 seconds
Challenges
Chain randomized basic blocks together
Need extra space to chain basic blocks
Need to update instructions
Stale pointer migration
Extra Space
Case 1: Extra Jmp
Basic Block 1
Basic Block 2
Basic Block 3
Jmp to BB1
(1) At the beginning of a function
Extra Space
Case 1: Extra Jmp
Basic Block 1
Basic Block 2
Basic Block 3
Jmp to BB1
(1) At the beginning of a function
(2) At the end of a basic block that does 
not end with an instruction like 
jmp
/
ret
mov
 
add
 
mov
 
mov
 
add
 
jle
 
Extra Space
Case 2: Larger Displacement
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Jump to BB3
Before Remix
Extra Space
Case 2: Larger Displacement
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Jump to BB3
Jump to BB3
Before Remix
After Remix
Extra Space
Case 2: Larger Displacement
One-byte displacement:
jmp +0x10
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Jump to BB3
Jump to BB3
Four-byte displacement:
jmp +0x00001000
Before Remix
After Remix
Extra Space
Solution
With
 Source Code:
Modify the compiler to:
1.  
Insert an extra 5-byte NOP 
instruction after each basic block
2.  
Only generate instructions with
4-byte displacement
Enough Space Guaranteed!
Extra Space
Solution
With
 Source Code:
Modify the compiler to:
1.  
Insert an extra 5-byte NOP 
instruction after each basic block
2.  
Only generate instructions with
4-byte displacement
Enough Space Guaranteed!
Without
 Source Code:
Leverage existing NOP paddings:
Function alignment
Loop alignment
Can insert 
random bytes
 into NOP
space after randomization, making
attack even harder.
Instruction Update
Q:  Which instructions need updating ?
A:  
Control-flow
 related ones, to adjust displacement
Instruction Update
Two-step update 
(e.g., unconditional direct jmp)
:
Basic Block 1
Basic Block 2
Basic Block 3
Original
After BB reordering
Step one:
Jumps to original
address of BB 3
Step two:
Jumps to current
address of BB 3
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 1
Basic Block 2
Basic Block 3
jmp
Instruction Update
Direct call
: step-one update
Indirect call
: no update needed
Direct jump
: step-one and step-two update
Indirect jump
: discussed later
PC-relative addressing
: step-one update
Indirect Jump
Jump to functions – unchanged
PLT/GOT
Tail/Sibling Call
Jump to basic blocks – see next
Basic Block Pointer Conversion
Why?
-
Migrate stale 
pointers to basic blocks
, to ensure
correctness
Basic Block Pointer Conversion
Why?
-
Migrate stale 
pointers to basic blocks
, to ensure
correctness
Where?
-
Return address
-
Jump table (switch/case)
-
Saved context (e.g., setjmp/longjmp)
-
Kernel exception table
Call Foo
Return Site
main
Foo
Illustration - Return Address
Call Foo
Return Site
main
Foo
Illustration - Return Address
Call Foo
Return Site
main
Foo
Illustration - Return Address
Optimization
To Speed up the randomization procedure:
 
Pre-store
 the required information
 Basic block information (e.g., locations)
 Code/data that need updating
Optimization
To speed up execution:
 Probabilistic loop bundling
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Loop
Bundle
Optimization
To speed up execution:
 Probabilistic loop bundling
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Loop
Basic Block 1
Bundled BB
Basic Block 4
Basic Block 5
Bundle
Optimization
To speed up execution:
 Probabilistic loop bundling
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Loop
Basic Block 1
Bundled BB
Basic Block 4
Basic Block 5
Basic Block 1
Bundled BB
Basic Block 4
Basic Block 5
Randomize
Bundle
Optimization
To speed up execution:
 Probabilistic loop bundling
Basic Block 1
Basic Block 2
Basic Block 3
Basic Block 4
Basic Block 5
Loop
Basic Block 1
Bundled BB
Basic Block 4
Basic Block 5
The bundling layout is 
different
 from time to time. – 
Unpredictable
!
Basic Block 1
Bundled BB
Basic Block 4
Basic Block 5
Randomize
Implementation
Can work on source code using a slightly
modified LLVM, or work directly on binaries.
C
a
n
 
w
o
r
k
 
o
n
 
L
i
n
u
x
 
u
s
e
r
-
s
p
a
c
e
 
a
p
p
l
i
c
a
t
i
o
n
s
,
 
a
n
d
F
r
e
e
B
S
D
 
k
e
r
n
e
l
 
m
o
d
u
l
e
s
.
Evaluation - Security
Finer-grained randomization:
Adds about four bits of entropy to each instruction.
Live randomization during runtime:
Destroy discovered gadgets immediately after each
re-randomization.
Want more entropy? – Insert more NOP space!
Evaluation - Performance
SPEC CPU 2006 Performance Overhead (randomized once)
Evaluation - Performance
SPEC CPU 2006 Size Increase
Evaluation - Performance
Apache Web Server Performance Overhead (by ApacheBench)
Randomization Time Interval
Randomization time interval can be random !
Performance depends on hardware speed.
Evaluation - Performance
ReiserFS Performance Overhead (by IOZone)
Randomization Time Interval
Randomization time interval can be random !
Performance depends on hardware speed.
Q&A
Slide Note
Embed
Share

This content delves into defense mechanisms against code injection attacks, specifically focusing on techniques like Data Execution Prevention (DEP), Write XOR Execute, Return-oriented Programming (ROP), and ASLR. It explores how these strategies thwart attackers' attempts by randomizing feature space or removing features, ultimately aiming to protect systems from vulnerabilities and unauthorized access.

  • Code Injection
  • Defense Strategies
  • Data Execution Prevention
  • ROP
  • ASLR

Uploaded on Feb 23, 2025 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


  1. Remix: On-demand Live Randomization Yue Chen, Zhi Wang, David Whalley, Long Lu* Florida State University, Stony Brook University*

  2. Background Buffer Overflow -> Code Injection Attack

  3. Background Buffer Overflow -> Code Injection Attack Defense: Data Execution Prevention (DEP) Write XOR Execute: a block (page) of memory cannot be marked as both writable and executable at the same time.

  4. Background Buffer Overflow -> Code Injection Attack Defense: Data Execution Prevention (DEP) Write XOR Execute: a block (page) of memory cannot be marked as both writable and executable at the same time. Return-oriented Programming (ROP) Attack Discover gadgets from existing code, and chain them by ret instructions Can be Turing complete

  5. Code Reuse Attack Existing Code Chained Gadgets

  6. ROP Defense Strategy ROP is one example of a broad class of attacks that require attackers to know or predict the locations of binary features.

  7. ROP Defense Strategy ROP is one example of a broad class of attacks that require attackers to know or predict the locations of binary features. Defense Goal Frustrate such attacks by randomizing feature space, or remove features

  8. ASLR Address Space Layout Randomization Library1 Library1 Executable Executable First-time Second-time

  9. ASLR - Problem Pointer Leak Library1 Executable

  10. ASLR - Problem Pointer Leak Library1 De-randomized Executable

  11. ASLR - Problem Brute force attacks are still possible (When the entropy is small. E.g., 32-bit systems.) Randomized only once.

  12. Goal Live randomization during runtime Finer-grained randomization unit Low performance overhead Highly composable Can and should be combined with other defenses (traditional ASLR, function randomization, etc.)

  13. Remix Live basic block (BB) (re-)randomization within functions A basic block is a straight-line code without jumps in or out of the middle of the block.

  14. Remix Live basic block (BB) (re-)randomization within functions Advantages: No function pointer migration Good spatial locality A basic block is a straight-line code without jumps in or out of the middle of the block.

  15. Remix Function A Basic Block 1 Basic Block 2 Basic Block 3 Basic Block 4 Basic Block 5 Space for Alignment Other Functions

  16. Remix Function A Function A Basic Block 1 Basic Block 3 Basic Block 2 Basic Block 5 Basic Block 3 After 0.46 seconds Basic Block 4 Basic Block 2 Basic Block 5 Basic Block 4 Space for Alignment Basic Block 1 Other Functions Other Functions

  17. Remix Function A Function A Function A Basic Block 1 Basic Block 2 Basic Block 3 Basic Block 2 Basic Block 5 Basic Block 5 Basic Block 3 After 2.13 seconds After 0.46 seconds Basic Block 3 Basic Block 4 Basic Block 2 Basic Block 5 Basic Block 1 Basic Block 4 Space for Alignment Basic Block 4 Basic Block 1 Other Functions Other Functions Other Functions

  18. Challenges Chain randomized basic blocks together Need extra space to chain basic blocks Need to update instructions Stale pointer migration

  19. Extra Space Case 1: Extra Jmp (1) At the beginning of a function Jmp to BB1 Basic Block 3 Basic Block 2 Basic Block 1

  20. Extra Space Case 1: Extra Jmp (1) At the beginning of a function (2) At the end of a basic block that does not end with an instruction like jmp/ret Jmp to BB1 mov add mov Basic Block 3 Basic Block 2 mov add jle Basic Block 1

  21. Extra Space Case 2: Larger Displacement Before Remix Basic Block 1 Jump to BB3 Basic Block 2 Basic Block 3 Basic Block 4 Basic Block 5

  22. Extra Space Case 2: Larger Displacement Before Remix After Remix Basic Block 1 Basic Block 1 Jump to BB3 Jump to BB3 Basic Block 2 Basic Block 2 Basic Block 3 Basic Block 4 Basic Block 4 Basic Block 5 Basic Block 5 Basic Block 3

  23. Extra Space Case 2: Larger Displacement Before Remix After Remix Basic Block 1 Basic Block 1 Jump to BB3 Jump to BB3 Basic Block 2 Basic Block 2 One-byte displacement: jmp +0x10 Basic Block 3 Basic Block 4 Basic Block 4 Four-byte displacement: jmp +0x00001000 Basic Block 5 Basic Block 5 Basic Block 3

  24. Extra Space Solution With Source Code: Modify the compiler to: 1. Insert an extra 5-byte NOP instruction after each basic block 2. Only generate instructions with 4-byte displacement Enough Space Guaranteed!

  25. Extra Space Solution Without Source Code: With Source Code: Leverage existing NOP paddings: Modify the compiler to: 1. Insert an extra 5-byte NOP instruction after each basic block 2. Only generate instructions with 4-byte displacement Function alignment Loop alignment Can insert random bytes into NOP space after randomization, making attack even harder. Enough Space Guaranteed!

  26. Instruction Update Q: Which instructions need updating ? A: Control-flow related ones, to adjust displacement

  27. Instruction Update Two-step update (e.g., unconditional direct jmp): Step one: Jumps to original address of BB 3 Step two: Jumps to current address of BB 3 Original After BB reordering Basic Block 1 Basic Block 3 Basic Block 3 Basic Block 3 jmp Basic Block 2 Basic Block 2 Basic Block 2 Basic Block 2 Basic Block 3 Basic Block 1 Basic Block 1 Basic Block 1

  28. Instruction Update Direct call: step-one update Indirect call: no update needed Direct jump: step-one and step-two update Indirect jump: discussed later PC-relative addressing: step-one update

  29. Indirect Jump Jump to functions unchanged PLT/GOT Tail/Sibling Call Jump to basic blocks see next

  30. Basic Block Pointer Conversion Why? - Migrate stale pointers to basic blocks, to ensure correctness

  31. Basic Block Pointer Conversion Why? - Migrate stale pointers to basic blocks, to ensure correctness Where? - Return address - Jump table (switch/case) - Saved context (e.g., setjmp/longjmp) - Kernel exception table

  32. Illustration - Return Address main Foo Call Foo Return Site

  33. Illustration - Return Address main Foo Call Foo Return Site

  34. Illustration - Return Address main Foo Call Foo Return Site

  35. Optimization To Speed up the randomization procedure: Pre-store the required information Basic block information (e.g., locations) Code/data that need updating

  36. Optimization To speed up execution: Probabilistic loop bundling Basic Block 1 Basic Block 2 Loop Basic Block 3 Basic Block 4 Basic Block 5

  37. Optimization To speed up execution: Probabilistic loop bundling Basic Block 1 Basic Block 1 Basic Block 2 Loop Bundled BB Bundle Basic Block 3 Basic Block 4 Basic Block 4 Basic Block 5 Basic Block 5

  38. Optimization To speed up execution: Probabilistic loop bundling Basic Block 1 Basic Block 1 Bundled BB Basic Block 2 Loop Bundled BB Bundle Randomize Basic Block 3 Basic Block 1 Basic Block 4 Basic Block 4 Basic Block 5 Basic Block 5 Basic Block 5 Basic Block 4

  39. Optimization To speed up execution: Probabilistic loop bundling Basic Block 1 Basic Block 1 Bundled BB Basic Block 2 Loop Bundled BB Bundle Randomize Basic Block 3 Basic Block 1 Basic Block 4 Basic Block 4 Basic Block 5 Basic Block 5 Basic Block 5 Basic Block 4 The bundling layout is different from time to time. Unpredictable!

  40. Implementation Can work on source code using a slightly modified LLVM, or work directly on binaries. Can work on Linux user-space applications, and FreeBSD kernel modules.

  41. Evaluation - Security Finer-grained randomization: Adds about four bits of entropy to each instruction. Live randomization during runtime: Destroy discovered gadgets immediately after each re-randomization. Software Apache nginx lighttpd Average Basic Block Number per Function 15.3 18.8 14.4 Average NOP Space (bytes) per Function 19.3 26.2 22.1 Want more entropy? Insert more NOP space!

  42. Evaluation - Performance SPEC CPU 2006 Performance Overhead (randomized once)

  43. Evaluation - Performance SPEC CPU 2006 Size Increase

  44. Evaluation - Performance Randomization Time Interval Apache Web Server Performance Overhead (by ApacheBench) Performance depends on hardware speed. Randomization time interval can be random !

  45. Evaluation - Performance Randomization Time Interval ReiserFS Performance Overhead (by IOZone) Performance depends on hardware speed. Randomization time interval can be random !

  46. Q&A

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#