Static Analysis of Binary Executables Using Structural SVMs

Nikos KarampatziakisNeurIPS 2010 · OpenReview

Static analysis—the art of understanding what a program does without actually running it—is a cornerstone of modern cybersecurity. But before you can analyze a program's logic, you first have to solve a deceptively difficult puzzle: where does the code actually start and end?

In his paper, Static Analysis of Binary Executables Using Structural SVMs, Nikos Karampatziakis moves away from the brittle, heuristic-based tools of the past and proposes a robust machine-learning framework to segment binary files into code and data.

TL;DR

This paper treats the identification of code blocks in a binary file as a sequence segmentation problem. By framing the task as a "heaviest path" problem on a trellis graph, the author develops a linear-time inference algorithm that allows Structural Support Vector Machines (SVMs) to accurately distinguish code from data in massive binary files, significantly outperforming traditional heuristic and Hidden Markov Model (HMM) based methods.

What Problem Does This Paper Address?

When a CPU runs a program, it knows exactly which bytes are instructions. However, looking at a "dead" binary file (static analysis) is much harder. In architectures like Intel x86, instructions have variable lengths, and compilers often interleave "data" (like lookup tables or padding) directly into the code sections.

Traditional tools use recursive disassembly: they start at a known entry point and follow the "flow" of jumps and calls. But malware authors are clever; they use indirect jumps or "junk" bytes to desynchronize these tools, leading to incorrect analysis. The challenge is to create a model that can look at the entire sequence of bytes and globally decide what is code and what is data, even when the structure is intentionally confusing.

Methods

The author's core contribution is a structured prediction model that balances expressiveness with speed.

  1. The Trellis Graph: The binary is represented as a directed graph (a trellis). Nodes represent the possibility that a code block starts or ends at a specific byte, or that a byte is part of a data block. Any valid "path" through this graph represents a valid segmentation of the file.
Trellis graph representation of a binary sequence, showing valid paths for code and data segmentation.
  1. Weighted Interval Scheduling: Instead of using computationally expensive models like semi-CRFs (which can be cubic in complexity), the author shows that finding the best segmentation is equivalent to finding the "heaviest path" in this trellis. This allows for linear-time inference, which is essential because even small programs are hundreds of thousands of bytes long.
  2. Structural SVMs: To train the model, the author uses a Structural SVM. Unlike a standard SVM that predicts a single label, a Structural SVM predicts a complex object (in this case, a full segmentation).
  3. Custom Loss Functions: The paper introduces two specific ways to penalize the model during training:
  4. Block Loss: Penalizes the model for missing the start of a code block.
  5. Instruction Loss: A more nuanced metric that penalizes the model based on how many individual CPU instructions it misidentifies.

Datasets

The study used a dataset of 200 common programs taken from a standard Windows XP installation.

  • Ground Truth: Because "perfect" labels are hard to find, the author used the output of OllyDbg (a popular heuristic-based debugger) as the gold standard, manually verifying results against another tool, IdaPro, to ensure low noise.
  • Features: The model uses 2.3 million features, including byte-level patterns (e.g., "does the byte 0xC3 appear before this position?") and instruction-level histograms (e.g., "how many mov instructions are in this candidate block?").

Key Insights and Ideas

  • The "Text Analogy": The author compares a binary to a "masked" letter from the Revolutionary War. If you read the whole letter, it looks like one thing; if you apply a mask (the code segmentation), a hidden message (the actual instructions) appears.
  • Global vs. Local: Heuristics make local, independent decisions. This model makes a global decision, ensuring that the chosen code blocks are consistent with the overall structure of the file.
  • Linearity is King: The jump from $O(n^3)$ to $O(n)$ complexity is what makes this research practical. By restricting the "grammar" of how code and data can transition, the author reclaimed the efficiency needed for real-world software.
  • Hamming Loss is Useless: The paper argues that standard "Hamming loss" (counting how many bytes are labeled correctly) is a poor metric for code. If you are off by just one byte at the start of a block, every subsequent instruction in that block will be decoded incorrectly. This justifies the need for the specialized "Block" and "Instruction" losses.

Key Results

The proposed model, SVM-WIS (Weighted Interval Scheduling), was compared against a "Greedy" baseline and a discriminative Hidden Markov Model (SVM-HMM).

Performance comparison showing SVM-WIS models achieving the lowest error rates across various loss metrics compared to Greedy and HMM baselines.
  • Accuracy: The SVM-WIS models consistently achieved the lowest error rates across all metrics (Hamming, Block, and Instruction loss).
  • Superiority over HMMs: While HMMs are good at sequence labeling, they struggle with the variable-length nature of x86 instructions. The SVM-WIS model's ability to "see" entire blocks at once gave it a significant edge.
  • Robustness: The models trained specifically on "Block Loss" tended to perform best overall, even when evaluated on other metrics, suggesting that identifying the start of code is the most critical factor in successful disassembly.

Limitations and Future Work

  • Ground Truth Circularity: The model was trained on data from heuristic tools (OllyDbg). If those tools have systematic biases, the model might learn to replicate those biases rather than finding the "true" code. The author suggests using data from the compilation/linking process in the future to get cleaner labels.
  • Call Consistency: The current model doesn't strictly enforce that a "call" instruction must point to a valid function start (an NP-hard problem). Future work could involve approximating these constraints to improve accuracy.
  • Malware Application: While motivated by security, this paper focuses on "benign" programs. The next step is extending the model to jointly segment and classify files as malicious or benign.

Summary updated

Abstract

We cast the problem of identifying basic blocks of code in a binary executable as learning a mapping from a byte sequence to a segmentation of the sequence. In general, inference in segmentation models, such as semi-CRFs, can be cubic in the length of the sequence. By taking advantage of the structure of our problem, we derive a linear-time inference algorithm which makes our approach practical, given that even small programs are tens or hundreds of thousands bytes long. Furthermore, we introduce two loss functions which are appropriate for our problem and show how to use structural SVMs to optimize the learned mapping for these losses. Finally, we present experimental results that demonstrate the advantages of our method against a strong baseline.
BibTeX
@inproceedings{karampatziakis2010static,
  author = {Nikos Karampatziakis},
  title = {{Static Analysis of Binary Executables Using Structural SVMs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=S1WSrDZuWr},
}
Figure