💻 computer science

Transparent Malware Detection With Granular Assembly Flow Explainability via Graph Neural Networks

This paper proposes a novel malware detection framework that utilizes Assembly Flow Graphs (AFG) and a Meta-Coarsening approach to enable Graph Neural Networks (GNNs) to achieve both high inference performance and granular, transparent explainability, validated on the CIC-DGG-2025 dataset.

Original authors: Griffin Higgins, Roozbeh Razavi-Far, Hossein Shokouhinejad, Ali A. Ghorbani

Published 2026-02-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Griffin Higgins, Roozbeh Razavi-Far, Hossein Shokouhinejad, Ali A. Ghorbani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Black Box" Detective

Imagine you have a super-smart security guard (an AI) that can look at a computer program and instantly tell you if it's a virus (malware) or safe. This guard is very good at its job. However, there's a catch: the guard won't tell you why it made that decision.

If the guard says, "This file is dangerous," you might ask, "Why? Is it the part that steals passwords? Is it the part that deletes files?" The guard just shrugs. In the world of cybersecurity, this is dangerous. If you don't know why something is flagged, you can't trust the guard, and you can't fix the problem effectively.

The Solution: A New Map (The AFG)

The authors of this paper wanted to build a guard that not only catches viruses but also points a finger at the exact line of code causing the trouble. To do this, they created a new way of looking at computer programs called an Assembly Flow Graph (AFG).

The Old Way (CFG): Imagine a program as a map of cities (Basic Blocks). You can see the roads connecting the cities, but you can't see the individual houses inside the cities. If the AI says "City X is bad," you don't know which house in City X is the criminal.
The New Way (AFG): The authors zoomed in. They turned the map so that every single instruction (every house) is a node on the map. Now, the AI can see the entire neighborhood down to the individual bricks. This allows for granular explanations—pointing exactly to the specific instruction that is suspicious.

The Challenge: The Map is Too Big

Here is the problem: A computer program is huge. If you draw a map of every single instruction, it becomes a giant, tangled web with millions of dots and lines. Trying to analyze this giant web with a computer is like trying to solve a puzzle with a billion pieces while wearing oven mitts. It takes too long and crashes the computer.

The Trick: "Meta-Coarsening" (The Shrink Ray)

To solve the "too big" problem, the authors invented a method called Meta-Coarsening. Think of this as a "Shrink Ray" for the map.

Step 1: The Rough Sketch (Coarsening the CFG): First, they take the giant map and group the cities together into "Super-Cities." They shrink the map down to a manageable size. This is fast and easy to process.
Step 2: The Detective Work: They run their AI detective on this small, shrunk map. The AI finds the "Super-City" that looks suspicious.
Step 3: The Zoom Back In (Backtracking): Once the AI points to a "Super-City," the authors use a special map key to "un-shrink" just that part. They zoom back in to the original, giant map to see exactly which specific instructions (houses) inside that Super-City are the culprits.

This is like a detective looking at a satellite photo of a whole country to find a bad neighborhood, and then using a high-powered telescope to zoom in on that specific neighborhood to arrest the exact criminal.

The Results: What Did They Find?

The team tested this method on a large dataset of computer programs. Here is what happened:

It Works: The AI could still tell the difference between good and bad programs even after shrinking the map. In fact, shrinking it a little bit actually helped the AI generalize better (like how squinting at a blurry image sometimes helps you see the big picture).
It Explains Better: The most important result is that they could finally explain why a program was bad. They could point to specific assembly instructions.
The "Beta" Score: They created a new test (called the Beta score) to see if the explanation was truly at the instruction level. They found that without their new method, the AI was vague (like saying "the whole city is bad"). With their method, the AI was precise (saying "this specific street is bad").
Good vs. Bad Programs: Interestingly, they found that it was easier to explain why a program was safe (benign) than why it was malicious. Malware is often designed to be sneaky and confusing, making it harder to pinpoint the exact "bad" instruction compared to the straightforward logic of safe software.

The Bottom Line

This paper introduces a way to make AI malware detectors transparent. By creating a detailed map of every instruction (AFG) and using a smart shrinking technique (Meta-Coarsening) to handle the size, they can now tell security experts exactly which line of code is dangerous. This moves us from "The AI thinks this is bad" to "The AI knows this specific instruction is bad because..."

Technical Summary: Transparent Malware Detection With Granular Assembly Flow Explainability via Graph Neural Networks

Problem Statement

As malware becomes increasingly sophisticated and evasive, detection systems must evolve to be equally intelligent and transparent. While Graph Neural Networks (GNNs) applied to Control Flow Graphs (CFGs) have shown promise in malware detection, they suffer from a lack of intrinsic explainability. Existing GNN-based explainability methods applied to CFGs face a critical limitation: CFG nodes represent "basic blocks" (sequences of non-branching instructions), meaning the individual assembly instructions within those blocks are obscured. Consequently, GNNs cannot provide granular, instruction-level explanations, leaving ambiguity regarding which specific instructions drive a malicious prediction. Furthermore, the sheer scale of Assembly Flow Graphs (AFGs), which represent every instruction as a node, makes direct application of GNNs computationally intractable for preprocessing, embedding, and training.

Methodology

The authors propose a novel framework centered on the Assembly Flow Graph (AFG) and a Meta-Coarsening approach to enable granular explainability while maintaining computational feasibility.

1. Graph Construction

Assembly Flow Graph (AFG): Unlike traditional CFGs where nodes are basic blocks, the AFG substitutes every CFG node with a singly linked list of its constituent sequential assembly instructions. Edges are re-routed to connect the head and tail of these instruction lists, creating a graph where every node represents a single instruction.
Instruction Encoding: Instructions are encoded using a 1,103-bit vector derived from the Capstone library, capturing opcodes, prefixes, and various flags.

2. Meta-Coarsening Approach

To address the computational cost of large AFGs, the authors introduce a two-stage "Meta-Coarsening" pipeline:

Phase 1: CFG Coarsening (C-CFG): Instead of coarsening the massive AFG directly, the authors coarsen the underlying CFG (the "meta-structure"). This is computationally tractable and preserves structural similarity to the AFG. A GNN is trained on these Coarsened CFGs (C-CFGs), and an explainer identifies important subgraphs at this level.
Phase 2: Backtracking and B-AFG Training: The important subgraphs identified in the C-CFG are "backtracked" through the hierarchy to the original AFG, creating a Backtracked AFG (B-AFG) dataset. This B-AFG contains only the specific instruction-level nodes relevant to the explanation. A second, separate GNN is trained on these B-AFGs to generate final, granular explanations at the assembly instruction level.

3. Evaluation Metrics

The paper introduces and utilizes several metrics to quantify explanation quality:

Fidelity Scores ( $fid^+$ and $fid^-$ ): Measuring necessity (removing the subgraph changes the prediction) and sufficiency (keeping only the subgraph maintains the prediction).
Characterization Score ( $\lambda$ ): A weighted harmonic mean of fidelity scores, adapted to measure the agreement between the C-CFG and B-AFG levels.
$\beta$ Indicator Score: A novel metric to detect ambiguity. It returns 0 if explanations are binary (clear) and positive if they are non-binary (ambiguous), specifically highlighting the difference between basic block-level (ambiguous) and instruction-level (unambiguous) explanations.

Key Contributions

Assembly Flow Graph (AFG): The proposal of a novel graph representation that captures the full assembly instruction flow of a binary executable, enabling instruction-level granularity.
Meta-Coarsening: A novel approach to improve computational tractability by coarsening the CFG to approximate AFG coarsening, allowing for the training of GNNs on large-scale data while retaining the ability to backtrack to the instruction level.
Granular Explainability: The first demonstration of GNN-based malware detection that provides explanations at the specific assembly instruction level, resolving the ambiguity inherent in basic block-level CFGs.
Novel Metrics: The definition of the $\beta$ indicator score to empirically measure explanation granularity and the adaptation of the $\lambda$ score to evaluate cross-level explanation consistency.
Hyperparameter Control: The identification of hyperparameters (coarsening coefficient $r$ and selection policy $\epsilon$ ) that allow users to balance computational requirements with explanation expressiveness.

Experimental Results

The approach was evaluated using the CIC-DGG-2025 dataset, containing Windows PE x86 binaries.

Inference Performance: The Meta-Coarsening approach achieved competitive to superior accuracy compared to baselines. Specifically, the Kron coarsening method with a coefficient $r=0.25$ and Variation Edges with $r=0.75$ yielded the best results (up to 89.8% average accuracy), suggesting that moderate coarsening can act as a regularizer, improving generalization.
Explainability:
- The $\lambda$ score was highest (0.713) for Kron with $r=0.25$ , indicating strong agreement between the coarse and fine-grained explanations.
- Fidelity Analysis: The C-CFG level showed high necessity ( $fid^+$ ), meaning removing identified subgraphs caused misclassification. The B-AFG level showed high sufficiency ( $fid^-$ ), meaning the selected instruction subgraphs alone were sufficient to maintain the correct prediction.
- Granularity: The $\beta$ indicator was 1 for all (C-)CFG levels (indicating ambiguity) and 0 for all B-AFG levels (indicating unambiguous, binary instruction-level explanations).
Class Differences: The study observed that benign samples were generally more explainable than malicious samples. Malicious classes showed lower characterization scores, suggesting they are harder to explain or predict consistently.

Significance and Claims

The paper claims to be the first to consider granular explainability in malware detection using GNNs at the assembly instruction level. The authors emphasize that while prior works have utilized CFGs or opcode graphs, they could not provide unambiguous, instruction-level insights due to the aggregation of instructions into basic blocks.

The significance of this work lies in its ability to:

Provide transparent detection systems where defenders can understand exactly which instructions contribute to a malicious classification.
Overcome the computational barriers of applying GNNs to massive instruction-level graphs via the Meta-Coarsening strategy.
Offer a framework for controlling the trade-off between graph size and explanation detail through hyperparameters.

The authors conclude that their approach successfully provides assembly-level explanations, serving as a foundation for future work in large-scale malware detection explainability and assisting defenders in characterizing malware behavior. They acknowledge limitations regarding generalization to other binary formats and the potential for adversarial evasion, noting that future work could explore adversarial training or static generation methods to mitigate these issues.