🗜️ TRACE COMPRESSOR 🗜️

Algorithmic De-unrolling and Code Lifting for Massively Flat Execution Traces

---

📖 High-Level Overview

Imagine you are reading a book, but instead of saying "The clock ticked 60 times," the book literally prints the sentence "The clock ticked." sixty separate times. The book would be enormous and incredibly boring to read.

When software is protected by strong copy-protection or DRM, the original code (which might use small, neat loops) is intentionally "unrolled" into a massive, flat sequence of millions of instructions. If a researcher tries to compile or read this massive trace, their tools will crash or run out of memory.

Trace Compressor fixes this. It scans the millions of lines of code, mathematically detects the repeating patterns, and automatically writes a new, clean version of the code using small, neat loops again. It shrinks an 80-megabyte unreadable file back down into a fast, manageable program.

---

1. Introduction

A common technique in virtualization-based software protectors and white-box cryptography is extreme loop unrolling. By flattening the control flow graph, obfuscators successfully break traditional static analysis tools and exceed the AST size limits of standard compilers (e.g., Clang, GCC), rendering the lifted code impossible to recompile.

Trace Compressor introduces an algorithmic framework for detecting maximal repeating subsequences within massive, flat execution traces. By identifying semantically identical blocks of instructions, the framework parameterizes the variable operands and emits structured, loop-compressed code, typically achieving an 80%+ reduction in source code size.

2. Methodology & Architecture

The compression pipeline relies on advanced string-matching data structures applied to the execution trace domain.

2.1 Instruction Hashing and Normalization

Execution traces ($E$) are ingested as an array of instruction vectors. To account for varying registers in functionally identical blocks, the framework normalizes specific operand fields and generates a discrete hash for the instruction's opcodes and addressing modes.

2.2 Suffix Tree Matching

A generalized suffix tree is constructed over the hashed trace $E$. The algorithm traverses the tree to identify the longest repeated substrings that satisfy configurable thresholds (minimum block size and minimum occurrence frequency).

2.3 Template Parameterization and Code Generation

Once identical blocks are identified, the varying parameters (such as temporary register allocations) are lifted into function arguments. The engine emits parameterized template functions and a master execution loop that reconstructs the original trace semantics.

graph TD
    A[Raw Execution Trace] --> B(Sequence Hasher & Normalizer)
    B --> C{Suffix Tree Matcher}
    C -->|Identifies Repetitions| D[Template Extractor]
    D --> E(Parameterization Engine)
    E --> F[Code Generator]
    F --> G[Parameterized Templates.go]
    F --> H[Reconstructed Loop.go]

Loading

3. Practical Implementation

3.1 Compression Usage

package main

import (
    "fmt"
    "github.com/ParkWardRR/trace-compressor/compressor"
)

func main() {
    // 1. Ingest the unrolled execution trace
    trace := compressor.LoadTrace("path/to/obfuscated_trace.txt")

    // 2. Configure detection heuristics
    config := compressor.Config{
        MinBlockSize:   1000, // Minimum instructions per block
        MinOccurrences: 4,    // Must repeat at least 4 times
        OutputLanguage: "c",  // Emit C code
    }

    // 3. Execute algorithmic compression
    engine := compressor.NewEngine(config)
    result := engine.Compress(trace)

    fmt.Printf("Original AST Nodes: %d\n", result.OriginalCount)
    fmt.Printf("Compressed AST Nodes: %d\n", result.CompressedCount)
    fmt.Printf("Total Compression Ratio: %.2f%%\n", result.Ratio * 100)

    // 4. Export lifted source code
    result.Export("output_dir/")
}

4. Conclusion

Trace Compressor successfully mitigates trace explosion by applying $O(n)$ string-matching algorithms to reverse-engineered execution paths. The resulting lifted code benefits from drastically reduced compilation times and improved I-cache locality during dynamic re-execution.

License

Distributed under the Blue Oak Model License 1.0.0.