When analyzing compiled software, security analysts and automated tools frequently need to answer a fundamental question: What is this code actually doing, and where did it come from? Whether trying to identify vulnerable third-party libraries (TPLs) embedded in an Android app, classify an evolving strain of Windows malware, or verify an AI-generated code watermark, traditional code analysis relies heavily on surface-level, syntactic features. These features include package names, variable identifiers, flat lists of API calls, or fuzzy method signatures.
The fatal flaw of syntactic analysis is its fragility. Code is highly malleable. Through common compilation optimizations or intentional code obfuscation, a program's surface appearance can be completely transformed without changing its underlying behavior.
To bypass this vulnerability, a powerful research direction has emerged: shifting from surface-level syntax to graph-based structural fingerprinting. By representing code as topological networks—such as class dependency graphs, inter-procedural call graphs, and control flow graphs—investigators can extract semantic signatures that remain invariant even when the code is heavily obscured.
The Core Intuition: Why Topology Outperforms Syntax
To understand why graph-based representations work, consider an analogy to a social network. If you want to track a specific group of individuals, relying on their names or the clothes they wear (syntactic features) is unreliable; they can easily change their names or put on disguises. However, if you map the network of who talks to whom, who is related to whom, and how information flows through the group (topological features), the underlying structure remains recognizable regardless of surface-level changes.
In software, obfuscators routinely employ techniques like variable renaming, junk code insertion, package flattening, and runtime packing. While these techniques completely scramble text-based or token-based signatures, they are strictly constrained by a fundamental rule: they must preserve the program's execution logic and semantic correctness.
Because the program must still run and achieve the same outcome, the core relationships between its components cannot be easily destroyed. Graph-based fingerprinting exploits this constraint by capturing the structural skeleton of the software, which compilers and obfuscators are forced to leave intact.
Decoupling Modules via Class Dependency Graphs
In mobile application security, identifying third-party libraries is critical for tracking known vulnerabilities. However, modern obfuscators frequently use "package flattening" or directory scrambling, which dissolves the clean folder structures that typically isolate a library from the host application code.
To counter this, researchers developed techniques to isolate library boundaries by tracking internal class dependencies rather than relying on directory metadata.
Syntactic View (Fragile):
[com.google.analytics] ──> Contains Class A, Class B
(Obfuscator flattens this into a single root directory, breaking the detector)
Structural View (Resilient):
[Class A] ── Inherits From ──> [Class B] ── Calls Method In ──> [Class C]
(The relationships form an isolated, highly interconnected cluster or "module")
As demonstrated by Xian Zhan et al. in their empirical evaluation of Android TPL detection tools, frameworks that rely on simple syntactic matching fail under advanced obfuscation, whereas tracking class inheritance graphs and method invocation relationships maintains high resilience (Automated Third-Party Library Detection for Android Applications: Are We There Yet?).
By treating the application as a graph of interacting classes, tools can perform "module decoupling." This process identifies clusters of tightly coupled classes that represent distinct software components.
- Yuan Zhang et al. leveraged this in their system, LIBPECKER, showing that dependency-based class signatures (capturing internal inheritance, fields, and method prototypes) remain stable and recognizable even when class and method names are completely randomized (Detecting third-party libraries in Android applications with high precision and recall).
- This insight was further validated by Xian Zhan et al. in a systematic assessment, confirming that deep structural analysis of control flow graphs and class-level dependencies is necessary for robust identification in adversarial environments (A Systematic Assessment on Android Third-party Library Detection Tools).
- The authors applied this exact structural paradigm to isolate library components for version and vulnerability detection in their ATVHunter framework (ATVHunter: Reliable Version Detection of Third-Party Libraries for Vulnerability Identification in Android Applications), as well as for tracking Application Performance Management (APM) libraries (A Systematical Study on Application Performance Management Libraries for Apps).
This graph-based decoupling is not limited to high-level managed code like Java or Dalvik bytecode. In the domain of compiled binaries, Can Yang et al. introduced ModX, which decomposes binary code into semantically coherent modules based on structural execution flow and function behavior, allowing the detection of libraries even when only a fraction of their code has been partially imported (ModX: Binary Level Partially Imported Third-Party Library Detection via Program Modularization and Semantic Matching).
Abstracting Execution via Call and Control Flow Graphs
While class dependency graphs capture the macro-architecture of an application, lower-level graph representations capture how a program executes. This is particularly valuable in malware classification, where authors intentionally inject dead code or reorder instructions within individual functions to evade signature-based detection.
To achieve immunity against these "intra-procedural" modifications, models can look exclusively at the Call Graph topology—the inter-procedural network mapping which functions call which other functions.
Intra-Procedural Obfuscation (Function Level):
Function_A() {
x = 1 + 1; // Junk code
y = rename_me();
call Function_B();
}
Inter-Procedural Topology (Graph Level):
[Function_A] ───────> [Function_B]
(The edge between A and B remains completely unchanged)
In a study by Federico Errica et al., Deep Graph Networks (DGNs) were trained to classify malware families using only the skeleton of the program's call graph topology (Robust Malware Classification via Deep Graph Networks on Call Graph Topologies). Because the model ignores the internal code of the functions and focuses entirely on their connectivity, common evasion techniques like variable renaming or junk code insertion fail to degrade classification accuracy.
When dealing with compiled binaries that undergo severe structural changes over time—known as concept drift—focusing on the structural execution flow allows models to generalize across versions. Adrian Shuai Li et al. demonstrated that graph-based adversarial domain adaptation frameworks can detect evolved Windows malware with minimal samples, because the structural execution flow remains highly resilient against aggressive protection mechanisms like runtime packing or encryption (Revisiting Concept Drift in Windows Malware Detection: Adaptation to Real Drifted Malware with Minimal Samples).
Extending Invariance to Code Watermarking
The utility of structural invariance extends beyond security auditing and malware analysis into the domain of intellectual property protection for Large Language Models (LLMs). As LLMs generate increasingly sophisticated source code, proving AI authorship requires embedding watermarks that cannot be easily stripped out by a user paraphrasing the output.
Just as an obfuscator breaks syntactic malware detectors, a developer can easily change variable names or swap a for loop for a while loop to break token-based watermarks. To solve this, Zhimeng Guo et al. proposed anchoring code watermarks directly to the structural logic of the generated code (Practical and Effective Code Watermarking for Large Language Models). By embedding the watermark within the underlying control flow and logical dependencies, the watermark survives superficial token distributions and remains intact through subsequent user refactoring.
Conclusion
The shared insight across these diverse applications is clear: syntax is fragile, but topology is robust. By abstracting software into hierarchical graph representations—from macro-level class dependencies down to micro-level control flow graphs—modern analysis frameworks exploit the fundamental requirement that code must preserve its logic to remain functional. This structural paradigm shift ensures that whether analyzing an Android app, a malicious binary, or AI-generated code, the underlying identity of the software remains visible through the noise of obfuscation.
Key Foundational Work
Automated Third-Party Library Detection for Android Applications: Are We There Yet? (2020) — contributed 5 concept elements to this direction.
Detecting third-party libraries in Android applications with high precision and recall (2018) — contributed 2 concept elements to this direction.