MalCommunity: Reimagining Malware Ground Truth through Community Detection

TL;DR

Evaluating malware clustering is notoriously difficult because "Ground Truth" is often a moving target of inconsistent labels. MalCommunity breaks this cycle by transforming AV labels into a Malware Relation Graph and using community detection (Fast Newman) to evaluate clustering quality via modularity. It provides a scalable, noise-immune benchmark that outperforms traditional voting mechanisms and database-heavy models like VAMO.

Context: The Ground Truth Paradox

In malware analysis, clustering is the "holy grail" for reducing manual workloads. However, how do we know if a clustering algorithm is actually good?

• AV Labels are Noisy: Different engines use different naming conventions (e.g., Delf vs. Duch).
• Granularity Inconsistency: One engine might group variants into one large family (Agent), while another splits them into precise sub-families.
• Voting Failures: Simple majority voting (like AVclass) loses the underlying structural relationships between samples that "almost" matched.

Methodology: From Labels to Topological Communities

The core innovation of MalCommunity is the Malware Relation Graph (MRG).

1. Building the Relation Graph

Instead of just voting on a name, the authors look at the co-occurrence of samples within the labels of 15 selected AV engines. If two samples are consistently labeled as the same family across multiple engines, the edge weight between them increases.

2. High-Performance Optimization

To avoid the $O(N^2)$ complexity of a massive adjacency matrix, the authors use a Virtual Graph approach. They create virtual nodes representing "AV-Family" pairs. A sample node connects to a virtual family node; two samples are considered "neighbors" if they can reach each other via a two-hop path through these virtual nodes. This allows for lightning-fast graph construction without maintaining a global database.

3. Modularity-Based Evaluation

Rather than comparing clusters directly (which fails when granularities differ), MalCommunity uses the Fast Newman algorithm to find the optimal division of the graph. It then uses Modularity ($Q$)—a measure of the density of links within communities versus between communities—to score the target clustering result.

• Evaluation Score: $M/M_{FN}$
• Where $M$ is the modularity of the result being tested, and $M_{FN}$ is the reference modularity from the Fast Newman algorithm at the same granularity.

Experimental Proof: Resilience to Noise

The authors tested the model against VAMO and AVclass under two primary noise conditions:

Classification Inconsistency

When labels are flipped to simulate AV engine errors, MalCommunity remains stable, closely trailing VAMO in precision but significantly beating it in execution speed as the dataset scales.

Granularity Inconsistency

This is where MalCommunity shines. Even when AV engines provide extremely coarse labels (e.g., labeling 1000 samples as one family), MalCommunity's F1 score stays near 1.0. In contrast, AVclass and VAMO collapse as the granularity becomes skewed.

Real-World Application: APT28 Analysis

The authors applied MalCommunity to evaluate a clustering system for APT28 (Fancy Bear) samples.

1. The target system produced 26 clusters.
2. MalCommunity calculated the reference modularity for 26 clusters ($0.371$).
3. The system's actual modularity was $0.352$.
4. Final Score: 0.949. This quantitative score provides an objective "grade" for researchers to compare different feature extraction methods (e.g., static disassemble vs. dynamic behavior).

Critical Insight & Conclusion

The brilliance of MalCommunity lies in its Self-Contained Logic. By treating the test set as a standalone manifold of relationships, it eliminates the dependency on the "historical accuracy" of a vendor database.

Limitations: While robust, the model still depends on the initial selection of the 15 AV engines. If all selected engines share the same flaw (e.g., mislabeling a new zero-day family), the "community" will be built on a false foundation.

Future Outlook: Integrating this modularity-based approach with deep embedding spaces (like those from LLM-based binary analysis) could create the first truly "autonomous" malware triage system that validates its own findings.