How I Learned To Stop Reversing And Love The Strings

How I Learned To Stop Reversing And Love The Strings

Speakers: Paolo Montesel (mhackeroni)

Conference: HITB Phuket

YouTube: https://www.youtube.com/watch?v=10gttboOSuU

Overview

In this insightful talk from HITB Phuket, Paolo Montesel, known as mhackeroni, presents "How I Learned To Stop Reversing And Love The Strings," a project aimed at drastically reducing the time reverse engineers spend analyzing already-solved problems. Montesel addresses a common frustration: dedicating significant effort to reverse-engineer a proprietary binary, only to discover it contains statically linked, readily available open-source code. This talk details his journey and the technical solution developed to build a comprehensive database of strings from open-source projects, enabling rapid identification of known components within unknown binaries.

The core problem tackled by Montesel is the inefficiency inherent in traditional reverse engineering workflows. When faced with a binary, analysts often resort to manual string searches on platforms like Google or GitHub Code Search. This process is time-consuming, prone to error, and often fails to identify components that are nested within other statically linked libraries. Montesel's "Big Match" research project, undertaken while contracting with re revenge (now re.ai), proposes an automated, data-driven approach to overcome these challenges, fundamentally altering how reverse engineers approach binary analysis.

The significance of this work extends beyond mere convenience for reverse engineers. By quickly identifying known open-source components, security professionals can more efficiently pinpoint potential vulnerabilities, enhance supply chain security audits, and improve malware classification. The project demonstrates a practical application of data science principles to a long-standing security problem, offering a blueprint for creating intelligent tools that augment human analysis, rather than replacing it.

Background

▶ Watch: The core problem: unknowingly reversing open-source code (0:36)

The "life of a reverser," as Montesel describes it, typically involves opening a program in a decompiler like Ghidra, extracting interesting strings, and then performing web searches on platforms such as Google, GitHub Code Search, or Sourcegraph. The hope is to find matching open-source code, thus avoiding redundant reverse engineering efforts. However, this seemingly straightforward process is fraught with difficulties. Strings can be too generic (e.g., "error"), too unique to be indexed effectively by search engines, or simply not present in the right context to lead to the correct open-source project. Furthermore, the advent of AI-driven search engines can sometimes make string-based queries less effective than traditional literal searches.

A critical challenge arises with statically linked libraries. A proprietary binary often bundles multiple open-source libraries, and identifying these nested components through simple string searches can be incredibly difficult. Montesel illustrates this with a personal anecdote from 2018. While reversing libam.so (part of a popular messaging app's VoIP stack), he initially identified libsrtp. However, he wasted a full week before discovering that libsrtp was itself part of a larger, also open-source, library called PJSIP. This experience underscored the need for a more robust method to identify such dependencies.

Strings were chosen as the primary identifier for several compelling reasons. They are easy to see and easy to search for. Crucially, they are compiler independent (remaining consistent regardless of GCC, Clang, or specific compilation flags) and platform independent (working equally well across mobile, x86, or ARM targets). Moreover, strings rarely change throughout the lifetime of a library or repository, making them stable indicators. Despite these advantages, strings are not perfect. Issues like non-unique strings, "too weird" strings that search engines struggle with, and obfuscation (which the project intentionally ignored for its proof-of-concept phase) present limitations.

The proposed solution to these challenges was ambitious: build a massive database of strings extracted from all C and C++ projects on GitHub, de-duplicate the data, hash the strings, store them, and then develop a query system to identify matching components in target binaries. This approach aimed to automate the tedious and often fruitless manual search process, directly addressing the pain points of reverse engineers.

Key Findings

▶ Watch: Challenges of building a large string database (5:00)

The "Big Match" project successfully demonstrated the viability of a string-based approach for identifying open-source components in binaries. Despite initial complexities, Montesel and his team built a proof-of-concept that significantly streamlines the reverse engineering workflow.

A major discovery centered on data acquisition and management. Leveraging GitHub Torrent, a project initiated by TU Delft, proved instrumental. This resource provided a continuously updated, SQL-like view of GitHub's public events and metadata, allowing the team to filter and de-duplicate repositories before cloning them. This was crucial for handling the immense scale of GitHub's codebase, which for the top 100K C/C++ projects, amounted to over a terabyte of gzipped source code.

The challenge of repository de-duplication was a significant hurdle. GitHub is rife with forks, and distinguishing genuinely independent projects from numerous variations of the same codebase is complex. Montesel recounts the "Octocat Spoon Knife" incident involving the LibreCAD repository, illustrating how irregular Git history merges could confound de-duplication algorithms. The team devised a custom algorithm based on identifying "parentless commits" and grouping repositories by their shared commit history, ultimately prioritizing the most-starred repository within each group. While acknowledging its imperfections, this method proved "good enough" for the PoC.

For string processing, the fast and efficient ripgrep utility was used for extraction, followed by a custom Python library for de-escaping special characters. The strings were then hashed for storage and comparison, allowing for perfect matching without revealing the string content to the server.

The core of the search engine was built upon a Vector Space Model (VSM). This well-established technique, commonly used in information retrieval, was adapted to represent repositories and query binaries as vectors, where string hashes served as dimensions. Through experimentation with a synthetic dataset built using Gen2 (which allowed building static libraries with known origins), Montesel found that TF-IDF (Term Frequency-Inverse Document Frequency) was the most effective weighting scheme for string importance, and cosine similarity provided the best scoring algorithm for comparing vectors.

A crucial finding for improving query accuracy was the identification and removal of useless strings. By analyzing the popularity distribution of strings, the team determined that removing the top 10,000 most popular strings (e.g., "error," "return") significantly enhanced the relevance of search results. This filtering step was carefully validated to ensure that important, albeit common, strings like GF89A (the magic number for GIF files) were retained.

Even after de-duplication and string filtering, search results often contained numerous forks or slightly different versions of the same library clustered together. To address this, Spectral co-clustering was applied to the search results. This advanced clustering algorithm proved "magically" effective at grouping related repositories, presenting the user with distinct "diagonal blocks" of results, each representing an independent library. This significantly improved the clarity and usability of the search output.

Finally, a second de-duplication step was implemented post-vectorization. The database initially consumed too much RAM (an average of 40K per repo, with some repos having 23K strings). An additional Bash-implemented algorithm used Jaccard similarity to compare repos of similar size, removing redundant large projects like Linux or Android forks that had slipped through earlier de-duplication stages.

Technical Deep Dive

▶ Watch: Core search engine concept: Vector Space Model (18:00)

The "Big Match" project's technical architecture is a testament to resourceful engineering under limited resources, prioritizing simplicity and effectiveness.

Data Acquisition with GitHub Torrent:

The initial step involved gathering a massive dataset of C and C++ projects from GitHub. Instead of directly cloning repositories, which would be prohibitively slow and bandwidth-intensive, Montesel leveraged GitHub Torrent. This project, started by a professor at TU Delft in 2012, continuously pulled the GitHub public event API, creating a live, SQL-like (or MongoDB) database view of GitHub's metadata. This allowed Montesel to query project information (stars, forks, commit history) locally, enabling intelligent filtering and de-duplication without needing to download any source code initially. While GitHub Torrent is now defunct, its utility for large-scale GitHub data analysis was pivotal for this project. MongoDB dumps were eventually chosen over MySQL for better performance when processing the vast amount of metadata.

Repository De-duplication Strategy:

De-duplicating GitHub repositories is notoriously difficult due to the prevalence of forks and varying definitions of what constitutes a "unique" project. The initial goal was to eliminate forks to improve search accuracy and reduce storage. GitHub Torrent provided some information on forks created via the platform's "fork" button, but not for "push forks" (where a repository is simply pushed to GitHub without explicit linking).

Montesel's ideal, but impractical, algorithm involved cloning every repo, building a colossal graph database of all commits, identifying root commits (the first commit in a repository's history), and then keeping only the most-starred repo for each root commit.

The practical workaround, constrained by resources, used GitHub Torrent's partial commit history. The algorithm proceeds as follows:

1. Identify "parentless commits" – commits for which GitHub Torrent has no parent information (either true root commits or missing data).
2. Construct history subgraphs by following parent-to-child commit edges upwards from these parentless commits.
3. Group all repositories associated with each subgraph into a "repository group."
4. Within each group, identify the repository with the most stars and designate it as the "parent," with others as "children."
5. Finally, only the "parent" repositories (those without an identified parent in their group) are retained for analysis.

This heuristic, while imperfect (as demonstrated by the Octocat Spoon Knife incident, where a bizarre merge linked LibreCAD's history to a tutorial repo), proved sufficiently effective for the PoC to balance throwing away too much data against retaining too many duplicates.

String Extraction and Processing:

Once the de-duplicated list of repositories was established, the source code was downloaded. String extraction was performed using ripgrep, a highly optimized, fast, and feature-rich command-line tool for searching files. This choice bypassed the complexities and performance overhead of parsing C/C++ code directly.

Extracted strings were then processed using a custom Python library to de-escape them (e.g., converting \n into an actual newline character). This standardization was crucial for consistent matching. Finally, the de-escaped strings were hashed using an unspecified hashing algorithm, ensuring that actual string content was not stored directly or transmitted to the server, enhancing privacy.

The Vector Space Model Search Engine:

The core of the "Big Match" search engine is an adaptation of the Vector Space Model (VSM). In VSM, documents (in this case, code repositories) and queries (the strings extracted from a target binary) are represented as high-dimensional vectors. Each unique string hash in the entire dataset forms a dimension in this vector space. If a repository contains a particular string, its vector will have a corresponding value in that dimension; otherwise, it's zero.

To refine the vector representation, TF-IDF (Term Frequency-Inverse Document Frequency) weighting was applied. TF-IDF assigns higher weights to strings that are frequent within a specific repository but rare across the entire dataset, thus highlighting unique and discriminative strings. Conversely, very common strings (like "error") receive lower weights.

The similarity between a query vector (from the target binary) and each repository vector was calculated using cosine similarity. This metric measures the cosine of the angle between two vectors, with values closer to 1 indicating higher similarity.

The entire data pipeline, from string extraction to vectorization, was, perhaps surprisingly, implemented primarily in Bash. Montesel humorously noted, "it's all bash, not my choice honestly."

String Filtering and Result Clustering:

To improve the signal-to-noise ratio, Montesel identified that the top 10,000 most popular strings across GitHub were largely unhelpful for identification. These strings (e.g., common error messages, generic keywords) appeared in too many projects, leading to irrelevant matches. By analyzing a log-log plot of string popularity, a "knee" was identified around the 10K mark, indicating a point where string utility for differentiation sharply decreased. Removing these high-frequency strings significantly boosted the accuracy of search results without discarding valuable identifiers like GF89A (the GIF magic number).

Even with improved weighting and filtering, results often contained many similar entries (e.g., 50 forks of zlib followed by 50 forks of libssl). To address this, Spectral co-clustering was applied. This powerful clustering algorithm groups both rows (repositories) and columns (strings) simultaneously, revealing underlying block structures in the similarity matrix. This effectively clustered related repositories together, presenting the user with distinct groups of libraries rather than a long, undifferentiated list.

Second-Stage De-duplication:

Despite earlier de-duplication, the database still contained very large repositories with an excessive number of strings (an average of 23,000 strings per repo, leading to 40K RAM usage per repo). A final, Bash-based de-duplication pass was implemented. This algorithm compared repositories of similar size using Jaccard similarity on their string sets. If the similarity exceeded a certain threshold, one of the duplicate repositories was removed. This targeted large, redundant projects like extensive Linux kernel forks or Android platform components that consumed disproportionate resources.

Demo / Proof of Concept

▶ Watch: Improving search results with Spectra co-clustering (23:10)

Montesel presented a web-based demo of the "Big Match" system, showcasing its practical application. The demo allowed a user to upload a binary file. For the purpose of demonstration, Montesel used the libam.so file from his 2018 anecdote, the very binary that inspired the project.

Upon uploading, a client-side JavaScript component extracted the strings from the binary, mimicking the functionality of the standard strings command. These extracted strings (or their hashes, consistent with the system's design to maintain privacy) were then sent to the backend search engine.

The system's strength was immediately apparent in the results. For the libam.so example, the search returned a clustered list of matching open-source projects. The very first cluster correctly identified PJSIP, the large open-source VoIP library that Montesel had originally struggled to find manually. This was followed by other relevant clusters, such as libtomcrypt and a JSON parsing library, demonstrating the system's ability to identify multiple components within a single binary.

The demo highlighted that while the system offers high probability, it's not "sure" in the absolute sense; users would still need to double-check the identified libraries. However, it provides a highly accurate starting point, dramatically reducing the initial reconnaissance phase of reverse engineering. Montesel also noted some practical limitations for the demo, such as potential failures with "too big" files and the necessity for the target binary to contain "good strings" for effective matching. The visual presentation of clustered results, showing distinct groups of related projects, clearly illustrated the power of the spectral co-clustering step.

Defensive Implications

▶ Watch: Future applications: version guessing and monorepo analysis (30:00)

The "Big Match" project offers several significant implications for cybersecurity defenders, providing tools and methodologies to enhance various security practices.

Firstly, it enables faster open-source component identification within proprietary or untrusted binaries. Defenders frequently encounter firmware, IoT device images, or third-party software for which source code is unavailable. This system allows them to quickly ascertain if these binaries incorporate known open-source libraries, significantly speeding up the initial analysis phase.

Secondly, this capability directly translates to improved vulnerability management. Once open-source components are identified, security teams can rapidly cross-reference them against databases of known vulnerabilities (e.g., CVEs). Montesel even suggested the potential to infer a version range for identified libraries based on their string sets, allowing defenders to drill down to specific GitHub repositories and pinpoint exact vulnerable versions. This proactive identification can be crucial for patching or mitigating risks in a timely manner.

Thirdly, the approach has strong applications in malware analysis. Identifying unique string patterns or common library components within malware samples can aid in malware classification and understanding its functionality. A friend of Montesel, working in malware-related fields, confirmed using similar string-based techniques for this purpose.

Fourthly, the system enhances software supply chain security. Many large projects use monorepos that bundle numerous libraries. Traditional vulnerability scanners might miss embedded, outdated, or vulnerable libraries within these complex structures. Montesel explicitly stated that "something like this" could be used to find outdated dependencies in big monorepos on GitHub that conventional scanners overlook. By extracting strings from compiled binaries or even source code files, defenders can audit their dependencies more thoroughly.

Finally, the underlying methodology is extensible. While the PoC focused on strings, Montesel noted that the approach is equally applicable to magic numbers and other constant values found in binaries. This broadens its utility, allowing defenders to identify various forms of embedded data that signify specific components or functionalities. Montesel also envisioned this system as a feature within future decompilers, automatically renaming functions or code blocks based on identified string patterns, further streamlining binary analysis. The current limitation of requiring perfect string matches means that obfuscated binaries or those with heavily modified strings would pose a challenge, but the foundation laid by "Big Match" is robust.

Key Takeaways

• Identifying statically linked open-source libraries within proprietary binaries using string analysis can dramatically reduce reverse engineering time and effort.
• The project successfully adapted a Vector Space Model (VSM), utilizing TF-IDF weighting and cosine similarity, to effectively compare strings from target binaries against a database of open-source projects.
• Robust de-duplication strategies and careful string filtering (e.g., removing the top 10,000 most common strings) are essential for building a clean and accurate string database from large codebases like GitHub.
• Spectral co-clustering is a powerful technique for organizing search results, presenting users with actionable clusters of related repositories rather than a long list of individual matches.
• Beyond reverse engineering, this string-based identification approach has significant applications in vulnerability management, supply chain security, and malware classification.
• The "Big Match" project demonstrates that powerful binary analysis tools can be developed with modest resources and without relying on complex machine learning, proving the efficacy of a data-driven, analytical approach.

About the Speaker(s)

Paolo Montesel, who goes by the nickname mhackeroni, is a self-employed professional with a diverse background in reverse engineering, data science, and machine learning. Hailing from the northeast of Italy, Montesel is an active member of the "macaroni" CTF team, which recently achieved success by winning a "hack a satellite" competition (though he humbly notes his primary contribution was video and media). He also mentioned their aspiration to win Defcon CTF in the future.

The "Big Match" research project discussed in this talk was undertaken by Montesel as a personal "20% kind of thing" while he was contracting with an Italian company called re revenge (now known as re.ai). This company specializes in developing an LLVM-based decompiler, binary analysis, reverse engineering, and offers highly skilled C++ and LLVM consulting services. Montesel's work on "Big Match" was envisioned as a potential feature for their upcoming decompiler product.