Topology-Inspired Method Recovers Obfuscated Term Information From Induced Software Call-Stacks

Kelly Maggs, Vanessa RobinsFrontiers in Applied Mathematics and Statistics 2021 · DOI

Abstract

Fuzzing is a systematic large-scale search for software vulnerabilities achieved by feeding a sequence of randomly mutated input files to the program of interest with the goal being to induce a crash. The information about inputs, software execution traces, and induced call stacks (crashes) can be used to pinpoint and fix errors in the code or exploited as a means to damage an adversary’s computer software. In black box fuzzing, the primary unit of information is the call stack: a list of nested function calls and line numbers that report what the code was executing at the time it crashed. The source code is not always available in practice, and in some situations even the function names are deliberately obfuscated (i.e., removed or given generic names). We define a topological object called the call-stack topology to capture the relationships between module names, function names and line numbers in a set of call stacks obtained via black-box fuzzing. In a proof-of-concept study, we show that structural properties of this object in combination with two elementary heuristics allow us to build a logistic regression model to predict the locations of distinct function names over a set of call stacks. We show that this model can extract function name locations with around 80% precision in data obtained from fuzzing studies of various linux programs. This has the potential to benefit software vulnerability experts by increasing their ability to read and compare call stacks more efficiently.

Introduction: The Challenge of Obfuscated Call Stacks

When software developers or security researchers perform fuzzing—bombarding a program with random inputs to find bugs—the result is often a "call stack." This is a list of frames showing exactly which functions were running when the program crashed. However, in many real-world scenarios, such as analyzing malware or proprietary binaries, function names are deliberately obfuscated or stripped to hinder analysis. This makes "crash triage"—the process of grouping similar crashes to find the root cause—incredibly difficult. This research addresses the challenge of "Term Removal": can we reconstruct the structure of a call stack and identify where distinct functions should be, even if we do not know their names?

Methodology: A Topological Framework for De-obfuscation

The proposed method treats the data within call stacks as a finite topological space. The process involves several key steps:

  1. Call-Stack Topology: Each individual crash (call stack) is treated as an "open set" containing various terms, including modules, functions, and line numbers.
  2. Kolmogorov Quotients: To simplify the data, terms that always appear together in the same set of crashes are grouped into "equivalence classes."
  3. The Call-Stack Poset: A partial order is defined where term $A \le B$ if every crash that contains $B$ also contains $A$. This creates a hierarchy (a poset) reflecting the underlying dependency structure of the software without requiring access to the source code.
  4. Reconstruction via Machine Learning: A logistic regression model is trained using structural features of this poset, such as weighted in-degree and out-degree, to identify which equivalence classes likely contain hidden function names.
  5. Heuristics: Two "programming convention" heuristics are applied to pair predicted functions with specific line numbers: multiple line numbers in an equivalence class usually share a function, and a single line number in a class is often paired with a function in the frame immediately above it.

Experimental Evaluation and Datasets

The researchers evaluated their method using six common Linux programs fuzzed with the afl (American Fuzzy Lop) algorithm. The dataset consisted of thousands of raw crashes, which were pre-processed and de-duplicated into smaller sets of unique "distinct" crashes for analysis. The programs included SoX (mp3 and wav processing), Librsvg (SVG rendering), Libtiff (TIFF image handling), Freetype (Font rendering), and Libxml2 (used primarily for training the model).

Frequency distribution of crashes for the Freetype library.
Frequency distribution of crashes for the SoX (wav) utility.

Results and Key Insights

The model achieved a mean precision of 0.77 to 0.84, depending on the probability threshold. This indicates that when the algorithm predicts a function location, it is correct approximately 80% of the time. Precision and recall were relatively stable across different programs, proving the robustness of the topological approach.

A key mathematical finding is that removing function names does not destroy the topological relationships between the remaining modules and line numbers; the "skeleton" of the program's execution logic remains intact. Furthermore, the model trained on Libxml2 performed well on entirely different binaries, such as SoX or Freetype. This "transference" indicates that the topological features of call stacks are generalized enough to be used as a pre-trained tool for de-obfuscation.

Conclusion and Future Directions

While the study demonstrated high precision, it was performed on a relatively small dataset of fewer than 100 distinct crashes per program. Future work may explore if this precision holds in massive, highly diverse crash sets. Additionally, the current method relies on simple heuristics for pairing functions and line numbers; more sophisticated graph learning techniques could potentially improve recall, which currently sits around 40–50%. This research provides a foundation for software vulnerability experts to read and compare obfuscated call stacks more efficiently by restoring structural clarity.

Summary updated

Abstract

Fuzzing is a systematic large-scale search for software vulnerabilities achieved by feeding a sequence of randomly mutated input files to the program of interest with the goal being to induce a crash. The information about inputs, software execution traces, and induced call stacks (crashes) can be used to pinpoint and fix errors in the code or exploited as a means to damage an adversary’s computer software. In black box fuzzing, the primary unit of information is the call stack: a list of nested function calls and line numbers that report what the code was executing at the time it crashed. The source code is not always available in practice, and in some situations even the function names are deliberately obfuscated (i.e., removed or given generic names). We define a topological object called the call-stack topology to capture the relationships between module names, function names and line numbers in a set of call stacks obtained via black-box fuzzing. In a proof-of-concept study, we show that structural properties of this object in combination with two elementary heuristics allow us to build a logistic regression model to predict the locations of distinct function names over a set of call stacks. We show that this model can extract function name locations with around 80% precision in data obtained from fuzzing studies of various linux programs. This has the potential to benefit software vulnerability experts by increasing their ability to read and compare call stacks more efficiently.
BibTeX
@inproceedings{maggs2021topology,
  author = {Kelly Maggs and Vanessa Robins},
  title = {{Topology-Inspired Method Recovers Obfuscated Term Information From Induced Software Call-Stacks}},
  booktitle = {Frontiers in Applied Mathematics and Statistics},
  year = {2021},
  doi = {10.3389/fams.2021.668082},
}
Figure