ROP chain generation via backtracking and state machine

Date: 2024–09–26

As the trend continues to automate the generation of ROP (Return-Oriented Programming) chains, I have explored various approaches and come to the conclusion that employing an SMT (Satisfiability Modulo Theories) solver can be quite complex.

The primary challenge when using an SMT solver lies in maintaining the execution order of operations. For instance, while tools like Z3 can indicate that a solution is “sat,” they do not provide insights into the specific order of operations used to arrive at that solution.

Given this complexity, I decided to explore alternative methods that do not rely on SMT solvers. I concluded that maintaining a context of execution through a state machine is crucial for effective ROP chain generation.

I began by creating a structured list of gadget semantics

gadgets_table = [
    {'type': 'add', 'addr': 0x401207, 'W': 'eax', 'R': 0x32,  'instruction': 'add eax, 0x32 ; ret'},
    {'type': 'add', 'addr': 0x402c09, 'W': 'eax', 'R': 0x45,  'instruction': 'add eax, 0x45 ; ret'},
    {'type': 'add', 'addr': 0x403a0e, 'W': 'eax', 'R': 0x1,   'instruction': 'add eax, 0x1 ; ret'},
    {'type': 'sub', 'addr': 0x404f1a, 'W': 'eax', 'R': 0x13,  'instruction': 'sub eax, 0x13 ; ret'},
    {'type': 'sub', 'addr': 0x405212, 'W': 'eax', 'R': 0x2,   'instruction': 'sub eax, 0x2 ; ret'},
    {'type': 'sub', 'addr': 0x406215, 'W': 'eax', 'R': 0x1,   'instruction': 'sub eax, 0x1 ; ret'},
    {'type': 'mov', 'addr': 0x441ba7, 'W': 'ecx', 'R': 'eax', 'instruction': 'mov ecx, eax ; ret'},
    {'type': 'mov', 'addr': 0x441ba7, 'W': 'edx', 'R': 'ecx', 'instruction': 'mov edx, ecx ; ret'},
    # Add more gadgets as necessary
]

Next, I established a state machine to track the register values

self.ctx = {
    'eax': 0,
    'ebx': 0,
    'ecx': 0,
    'edx': 0,
    'edi': 0,
    'esi': 0,
}

The approach I adopted involves backtracking until the current context matches the target context. During each iteration, I maintain an execution order, which serves as my trace.

Here is a simplified script to demonstrate the implementation

# poc.py
from struct import pack
import sys

class Context:
    def __init__(self):
        self.ctx = {
            'eax': 0,
            'ebx': 0,
            'ecx': 0,
            'edx': 0,
            'edi': 0,
            'esi': 0,
        }
        self.tgt = {
            'eax': 511,
            'ebx': 0,
            'ecx': 0,
            'edx': 0,
            'edi': 0,
            'esi': 0,
        }

    def solve(self):
        # Implement the backtracking and execution order logic
        # This is where you would find the ROP chain
        pass

if __name__ == '__main__':
    context = Context()

    # Set the current state of registers at the crash point
    context.ctx['eax'] = 0

    # Solve for the ROP chain
    context.solve()
    sys.exit(0)

Running the script yields output similar to this

$ time ./poc.py
[+] ROP chain generation based on backtracking and state machine
[+] Current context:    {'edi': 0, 'eax': 0, 'edx': 0, 'ebx': 0, 'esi': 0, 'ecx': 0}
[+] Target context:     {'edi': 0, 'eax': 511, 'edx': 0, 'ebx': 0, 'esi': 0, 'ecx': 0}

[+] Gadgets available:
    - 0x401207: add eax, 0x32 ; ret
    - 0x402c09: add eax, 0x45 ; ret
    - 0x403a0e: add eax, 0x1 ; ret
    - 0x404f1a: sub eax, 0x13 ; ret
    - 0x405212: sub eax, 0x2 ; ret
    - 0x406215: sub eax, 0x1 ; ret
    - 0x441ba7: mov ecx, eax ; ret
    # More gadgets...

[+] Let's find a solution...
[+] Execution order found
    add eax, 0x32 ; ret
    add eax, 0x45 ; ret
    # More instructions...

[+] ROP chain:
    p = b''
    p += pack('<I', 0x401207) # add eax, 0x32 ; ret
    p += pack('<I', 0x402c09) # add eax, 0x45 ; ret
    # More instructions...

./poc.py  0.15s user 0.00s system 99% cpu 0.150 total

The execution time is efficient (0.15s). The next step is to restart the backtracking with different trace orders to discover alternative solutions that use fewer instructions.

Through this iterative process, I’ve identified an optimal solution to achieve eax = 511 using minimal instructions

Best solution for eax = 511:
add eax, 0x1 ; ret
shl eax, 0x3 ; ret
# Additional operations...

Once I refine my approach for ROP chain generation, I plan to document my findings in a blog post and integrate this functionality into ROPgadget.

Taylor Christian Newsome.