Chain Optimization

Angrop includes a sophisticated optimization system that discovers advanced gadget combinations and enables complex ROP chain generation. This guide explains how optimization works and when to use it.

What is Optimization?

After finding gadgets, angrop can run an optimization phase that:

Discovers multi-gadget capabilities - Combines simple gadgets to create complex operations
Normalizes non-self-contained gadgets - Makes advanced gadgets usable
Builds register move graphs - Finds efficient paths to move data between registers
Enables harder chains - Makes previously impossible chains possible

Optimization is enabled by default when calling find_gadgets(optimize=True). For large binaries, optimization can take significant time but dramatically improves chain generation success rates.

The `optimize` Parameter

The optimize parameter controls whether optimization runs after gadget finding.

In `find_gadgets()`

import angr
import angrop

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()

# Optimization enabled (default)
rop.find_gadgets(optimize=True)

# Optimization disabled (faster, but less capable)
rop.find_gadgets(optimize=False)

In `find_gadgets_single_threaded()`

# Single-threaded mode also supports optimize parameter
rop.find_gadgets_single_threaded(optimize=True)

In `load_gadgets()`

# When loading cached gadgets, you can optimize separately
rop.load_gadgets("/tmp/gadgets.cache", optimize=True)

# Or load without optimizing and optimize later
rop.load_gadgets("/tmp/gadgets.cache", optimize=False)
rop.optimize(processes=4)  # Run optimization manually

Manual Optimization

You can run optimization separately for better control:

import time
import angr
import angrop
from multiprocessing import cpu_count

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()

# Find gadgets without optimization
start = time.time()
rop.find_gadgets(optimize=False)
print(f"Gadget finding: {time.time() - start:.2f}s")

# Run optimization separately
start = time.time()
rop.optimize(processes=cpu_count())
print(f"Optimization: {time.time() - start:.2f}s")

Method Signature

rop.optimize(processes=4)

Parameters:

processes: Number of processes to use for parallel optimization (default: 4)

Real-World Example: Linux Kernel

From angrop’s kernel test suite (examples/linux_escape_chain/solve.py):

import os
import time
from multiprocessing import cpu_count
import angr
import angrop

proj = angr.Project("./vmlinux_sym")
rop = proj.analyses.ROP(
    fast_mode=False,
    only_check_near_rets=False,
    max_block_size=12,
    kernel_mode=True
)

cpu_num = cpu_count()
cache = "/tmp/linux_gadget_cache"

# Phase 1: Find gadgets (404 seconds on 16-core machine)
start = time.time()
if os.path.exists(cache):
    rop.load_gadgets(cache, optimize=False)
else:
    rop.find_gadgets(processes=cpu_num, optimize=False)
    rop.save_gadgets(cache)
print(f"Gadget finding time: {time.time() - start}s")

# Phase 2: Optimize (10 seconds on 16-core machine)
start = time.time()
rop.optimize(processes=cpu_num)
print(f"Graph optimization time: {time.time() - start}s")

# Phase 3: Generate chain (0.7 seconds)
start = time.time()
chain = rop.func_call("commit_creds", [0xffffffff8368b220])
print(f"Chain generation time: {time.time() - start}s")

For large binaries (especially kernels), separating optimization from gadget finding provides better progress visibility and allows you to cache gadgets without optimization, then optimize as needed.

What Happens During Optimization

Angrop runs several optimization passes:

1. Register Mover Optimization

From the source code (reg_mover.py:302-343), angrop:

Build register move graph

Creates a directed graph where:

Nodes are registers
Edges are possible register moves
Edge weights are gadget efficiency (stack change, etc.)

Normalize complex gadgets

Converts non-self-contained gadgets into usable register moves:

# Example: gadget does "mov rax, rbx; jmp rcx"
# Optimization normalizes it to set rcx properly
# Result: usable "rax = rbx" move

Find push/pop move chains

Discovers register moves via push/pop sequences:

# Chains like:
# push rax; pop rdi  => Move rax to rdi
# Even if these are separate gadgets!

2. Register Setter Optimization

From the source code (reg_setter.py:432-448), angrop:

Optimize with register moves

Uses the register move graph to discover new ways to set registers:

# If we can set rax and move rax→rbx:
# Now we can set rbx (even without direct pop rbx)

Optimize with complex gadgets

Normalizes gadgets that:

Require setup (non-self-contained)
Have symbolic memory accesses
Use conditional branches

Makes them usable by building setup chains automatically.

3. Graph Reduction

From the source code (reg_setter.py:451-473), angrop:

Limits gadgets per edge to top 5 (by efficiency)
Builds a “giga graph” for constraint solving
Optimizes gadget selection for minimal overhead

Benefits of Optimization

Before Optimization

import angr
import angrop

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()
rop.find_gadgets(optimize=False)

# May fail on complex chains
try:
    chain = rop.move_regs(r15='rax')  # No direct move gadget
except angrop.errors.RopException:
    print("Failed: can't move rax to r15")

After Optimization

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()
rop.find_gadgets(optimize=True)

# Now succeeds by chaining gadgets
chain = rop.move_regs(r15='rax')
# Might generate: rax→rbx→r15 using multiple gadgets
chain.pp()

Performance Characteristics

Small Binaries (< 1MB)

import time
import angr
import angrop

proj = angr.Project("/bin/ls")  # ~140KB
rop = proj.analyses.ROP()

start = time.time()
rop.find_gadgets(optimize=True)
print(f"Total time: {time.time() - start:.2f}s")
# Typical: 5-15 seconds including optimization

Medium Binaries (1-10MB)

proj = angr.Project("/bin/bash")  # ~1.2MB
rop = proj.analyses.ROP()

start = time.time()
rop.find_gadgets(processes=16, optimize=True)
print(f"Total time: {time.time() - start:.2f}s")
# Typical: 30-120 seconds including optimization

Large Binaries (> 10MB)

proj = angr.Project("./vmlinux_sym")  # ~60MB kernel
rop = proj.analyses.ROP(kernel_mode=True)

start = time.time()
rop.find_gadgets(processes=16, optimize=False)
print(f"Finding: {time.time() - start:.2f}s")
# Typical: 400-1000 seconds

start = time.time()
rop.optimize(processes=16)
print(f"Optimizing: {time.time() - start:.2f}s")
# Typical: 10-30 seconds

Optimization time is proportional to:

Number of gadgets found
Number of registers in architecture
Complexity of gadget relationships
Number of CPU cores available

Optimization Strategies

Strategy 1: Always Optimize for Production

# For actual exploits, always optimize
rop.find_gadgets(optimize=True)

Why: Maximizes chain generation success rate

Strategy 2: Skip for Quick Testing

# During development, skip optimization for speed
rop.find_gadgets(optimize=False)

# Test basic chains
chain = rop.set_regs(rax=0x1234)  # Simple chains still work

Why: Faster iteration during development

Strategy 3: Separate Phases for Large Binaries

# Cache gadgets without optimization
if not os.path.exists(cache):
    rop.find_gadgets(processes=16, optimize=False)
    rop.save_gadgets(cache)

# Load and optimize when needed
rop.load_gadgets(cache, optimize=False)
if need_complex_chains:
    rop.optimize(processes=16)

Why: Better control and caching for slow gadget finding

Strategy 4: Incremental Optimization

# Start without optimization
rop.find_gadgets(optimize=False)

# Try building chain
try:
    chain = rop.move_regs(r15='rax')
except angrop.errors.RopException:
    # Failed, try with optimization
    print("Optimizing...")
    rop.optimize()
    chain = rop.move_regs(r15='rax')

Why: Only pay optimization cost when necessary

Advanced: Understanding Optimization Internals

Normalization Process

From the source code (builder.py), “normalization” means:

Identify dependencies - What registers/memory does gadget need?
Build setup chain - Generate chain to satisfy dependencies
Combine gadget with setup - Create self-contained “RopBlock”
Cache result - Reuse normalized gadget in future chains

Example:

# Gadget: mov [rax], rbx; jmp rcx
# Dependencies: rax (address), rbx (data), rcx (return)

# Normalization creates:
# 1. Chain to set rax, rbx
# 2. Chain to set rcx to "ret" gadget
# 3. Combined chain that acts like: mov [rax], rbx; ret

Register Move Graph

From the source code (reg_mover.py:345-361):

# Pseudocode of register move graph
graph = {
    'rax': {
        'rbx': [gadget1, gadget2],  # rax→rbx moves
        'rcx': [gadget3],            # rax→rcx moves
    },
    'rbx': {
        'rdx': [gadget4],            # rbx→rdx moves
    },
    # ...
}

# Optimization finds paths:
# rax→rbx→rdx (two gadgets)
# Enables: rop.move_regs(rdx='rax')

Constraint-Based Gadget Selection

Angrop uses constraint solving to find optimal gadget combinations:

# When building chains, angrop:
# 1. Identifies all possible gadget sequences
# 2. Encodes constraints (preserve registers, avoid badbytes, etc.)
# 3. Solves for shortest/most efficient sequence
# 4. Verifies chain via symbolic execution

Optimization and Badbytes

Optimization respects badbyte restrictions:

import angr
import angrop

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()
rop.set_badbytes([0x00, 0x0a])

# Optimization only uses gadgets at safe addresses
rop.find_gadgets(optimize=True)

# Generated chains avoid badbytes
chain = rop.set_regs(rax=0x0a0a0a0a)  # Badbyte in value
# Optimization enables arithmetic construction

Disabling Optimization for Speed

When you don’t need complex chains:

import angr
import angrop

# Fast mode: skip optimization
proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP(fast_mode=True)
rop.find_gadgets(optimize=False)

# Basic operations still work
chain = rop.set_regs(rax=0x1234, rbx=0x5678)
chain += rop.func_call("system", [0x61b100])

# Complex operations may fail
try:
    chain = rop.move_regs(r15='rax')  # Might not work
except angrop.errors.RopException:
    print("Optimization needed for this operation")

Troubleshooting Optimization

Long Optimization Times

import time
import angr
import angrop

proj = angr.Project("./large_binary")
rop = proj.analyses.ROP()

start = time.time()
rop.find_gadgets(processes=16, optimize=False)
print(f"Found {len(rop.rop_gadgets)} gadgets in {time.time()-start:.1f}s")

if len(rop.rop_gadgets) > 10000:
    print("WARNING: Many gadgets, optimization will be slow")
    # Consider:
    # 1. Using fast_mode=True
    # 2. Restricting gadget search
    # 3. Running optimization overnight

start = time.time()
rop.optimize(processes=16)
print(f"Optimized in {time.time()-start:.1f}s")

To speed up optimization:

Use more CPU cores (processes=cpu_count())
Enable fast_mode=True to find fewer gadgets
Set stricter badbytes to eliminate gadgets early
Cache optimized gadgets for reuse

Optimization Failures

Optimization can fail to run in some cases:

import angr
import angrop

proj = angr.Project("/bin/bash")
rop = proj.analyses.ROP()
rop.find_gadgets(optimize=False)

if len(rop.rop_gadgets) < 10:
    print("Too few gadgets for meaningful optimization")
    # Optimization won't help much
else:
    rop.optimize()

Best Practices

Always optimize for production exploits - Maximizes success rate
Cache gadgets with optimization - Save time on repeated use
Use parallel optimization - Set processes=cpu_count()
Separate phases for large binaries - Better progress tracking
Profile your workflow - Measure time spent in each phase
Skip optimization during development - Faster iteration

Measuring Optimization Impact

import angr
import angrop

proj = angr.Project("/bin/bash")

# Test without optimization
rop_no_opt = proj.analyses.ROP()
rop_no_opt.find_gadgets(optimize=False)

# Test with optimization  
rop_opt = proj.analyses.ROP()
rop_opt.find_gadgets(optimize=True)

# Compare capabilities
test_cases = [
    ("set_regs", lambda r: r.set_regs(rax=0x1234)),
    ("move_regs", lambda r: r.move_regs(r15='rax')),
    ("func_call", lambda r: r.func_call("system", [0x61b100])),
]

for name, test in test_cases:
    without_opt = True
    with_opt = True
    
    try:
        test(rop_no_opt)
    except:
        without_opt = False
    
    try:
        test(rop_opt)
    except:
        with_opt = False
    
    print(f"{name}: without_opt={without_opt}, with_opt={with_opt}")

Next Steps

Finding Gadgets - Configure gadget discovery for optimization
Building Chains - Use optimized gadgets in complex chains
Badbytes - Understand optimization with byte restrictions

Getting Started

Core Concepts

Guides

CLI Tool

​What is Optimization?

​The optimize Parameter

​In find_gadgets()

​In find_gadgets_single_threaded()

​In load_gadgets()

​Manual Optimization

​Method Signature

​Real-World Example: Linux Kernel

​What Happens During Optimization

​1. Register Mover Optimization

​2. Register Setter Optimization

​3. Graph Reduction

​Benefits of Optimization

​Before Optimization

​After Optimization

​Performance Characteristics

​Small Binaries (< 1MB)

​Medium Binaries (1-10MB)

​Large Binaries (> 10MB)

​Optimization Strategies

​Strategy 1: Always Optimize for Production

​Strategy 2: Skip for Quick Testing

​Strategy 3: Separate Phases for Large Binaries

​Strategy 4: Incremental Optimization

​Advanced: Understanding Optimization Internals

​Normalization Process

​Register Move Graph

​Constraint-Based Gadget Selection

​Optimization and Badbytes

​Disabling Optimization for Speed

​Troubleshooting Optimization

​Long Optimization Times

​Optimization Failures

​Best Practices

​Measuring Optimization Impact

​Next Steps

Build docs developers (and LLMs) love

What is Optimization?

The `optimize` Parameter

In `find_gadgets()`

In `find_gadgets_single_threaded()`

In `load_gadgets()`

Manual Optimization

Method Signature

Real-World Example: Linux Kernel

What Happens During Optimization

1. Register Mover Optimization

2. Register Setter Optimization

3. Graph Reduction

Benefits of Optimization

Before Optimization

After Optimization

Performance Characteristics

Small Binaries (< 1MB)

Medium Binaries (1-10MB)

Large Binaries (> 10MB)

Optimization Strategies

Strategy 1: Always Optimize for Production

Strategy 2: Skip for Quick Testing

Strategy 3: Separate Phases for Large Binaries

Strategy 4: Incremental Optimization

Advanced: Understanding Optimization Internals

Normalization Process

Register Move Graph

Constraint-Based Gadget Selection

Optimization and Badbytes

Disabling Optimization for Speed

Troubleshooting Optimization

Long Optimization Times

Optimization Failures

Best Practices

Measuring Optimization Impact

Next Steps