APKHash: Structural Similarity Graphs as Evidence of Noise in Malware Family Labeling

• Felipe Duarte UFPR
• Eloiza Rossetto UFPR
• João Pincovscy Cepesc / UnDF
• Paulo Lisboa de Almeida UFPR
• André Grégio UFPR

DOI: https://doi.org/10.5753/sbseg.2026.29313

Abstract

In this work, we present APKHash, an approach based on opcode n-grams, MinHash/LSH, and similarity graphs for the structural analysis of Android applications. The methodology was evaluated on 12,000 APKs from 24 malware families collected between 2022 and 2024. The results show that heterogeneous components persist even in restrictive settings, indicating shared structural patterns between families or inconsistencies in dataset labeling. Regarding performance, the use of MinHash/LSH as APKHash main approach reduced the search space by approximately 97%. APKHash captures relevant structural relationships and reveals strong intra-family cohesion, but also limitations in separating malware families. The approach proves useful for structural analysis and for diagnosing the quality of large-scale malware datasets labeling.

References

Allix, K., Bissyandé, T. F., Klein, J., and Traon, Y. L. (2016). AndroZoo: Collecting millions of Android apps for the research community. In Proceedings of the 13th International Conference on Mining Software Repositories, MSR ’16, pages 468–471. ACM.

Canfora, G., De Lorenzo, A., Medvet, E., Mercaldo, F., and Visaggio, C. A. (2015). Effectiveness of opcode ngrams for the detection of multi family android malware.

Crussell, J., Gibler, C., and Chen, H. (2015). Andarwin: Scalable detection of android application clones based on semantics. IEEE Transactions on Mobile Computing, 14(10):2007–2019.

Dai, J., Luo, M., Zhang, Y., Yang, M., and Yang, M. (2025). Apkdiffer: Accurate and scalable cross-version diffing analysis for android applications. Proc. ACM Program. Lang., 9(OOPSLA2).

De Ghein, R., Abrath, B., De Sutter, B., and Coppens, B. (2022). Apkdiff: Matching android app versions based on class structure. In Proceedings of the 2022 ACM Workshop on Research on Offensive and Defensive Techniques in the Context of Man At The End (MATE) Attacks, Checkmate ’22, page 1–12, New York, NY, USA. Association for Computing Machinery.

Frenklach, T., Cohen, D., Shabtai, A., and Puzis, R. (2021a). Android malware detection via an app similarity graph. Computers & Security, 109:102386.

Frenklach, T., Cohen, D., Shabtai, A., and Puzis, R. (2021b). Android malware detection via an app similarity graph. Computers Security, 109:102386.

Guan, Q., Huang, H., Luo, W., and Zhu, S. (2016). Semantics-based repackaging detection for mobile apps. In Engineering Secure Software and Systems, volume 9639 of Lecture Notes in Computer Science, pages 89–105. Springer.

Hadi, H. J., Khalid, A., Hussain, F. B., Ahmad, N., and Alshara, M. A. (2025). FLSH: A framework leveraging similarity hashing for android malware and variant detection. IEEE Access.

Hurier, M., Suarez-Tangil, G., Dash, S. K., Bissyandé, T. F., Traon, Y. L., Klein, J., and Cavallaro, L. (2017). Euphony: Harmonious unification of cacophonous anti-virus vendor labels for android malware. In Proceedings of the 14th International Conference on Mining Software Repositories, pages 425–435. IEEE Press.

Joyce, R. J., Everett, D., Fuchs, M., Raff, E., and Holt, J. (2025). Claravy: A tool for scalable and accurate malware family labeling. In Companion Proceedings of the ACM on Web Conference 2025, pages 277–286.

Júnior, C. T., Filho, D. F., Pincovscy, J., and Grégio, A. (2025). Artemis: Uma plataforma modular para execução, monitoração e investigação de aplicativos android suspeitos. In Anais do XXV Simpósio Brasileiro de Cibersegurança, pages 147–162, Porto Alegre, RS, Brasil. SBC.

Kang, B., Yerima, S. Y., Sezer, S., and McLaughlin, K. (2016). N-gram opcode analysis for android malware detection. International Journal on Cyber Situational Awareness, 1(1):231–254.

Karbab, E. B., Debbabi, M., Derhab, A., and Mouheb, D. (2020). Scalable and robust unsupervised android malware fingerprinting using community-based network partitioning. Computers & Security, 96:101932.

Kim, H. M., Song, H. M., Seo, J. W., and Kim, H. K. (2019). ANDRO-SIMNET: Android malware family classification using social network analysis.

Lee, S., Jung, W., Kim, S., Lee, J., and Kim, J.-S. (2019). Dexofuzzy: Android malware similarity clustering method using opcode sequence. Virus Bulletin.

Li, T., Shou, P., Wan, X., Li, Q., Wang, R., Jia, C., and Xiao, Y. (2024). A fast malware detection model based on heterogeneous graph similarity search. Computer Networks, 254:110799.

Paulevé, L., Jégou, H., and Amsaleg, L. (2010). Locality sensitive hashing: A comparison of hash function types and querying mechanisms. Pattern Recognition Letters, 31(11):1348–1358.

Saarinen, M. J. and Aumasson, J. P. (2015). The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC). RFC 7693.

Shen, L., Fang, M., and Xu, J. (2024). Ghgdroid: Global heterogeneous graph-based android malware detection. Computers Security, 141:103846.

Simoni, M., Saracino, A., et al. (2025). Matrix: A comprehensive graph-based framework for malware analysis and threat research. In Proceedings of the 22nd International Conference on Security and Cryptography, SECRYPT, pages 11–13.

Wang, L., Wang, H., Zhang, T., Xu, H., Meng, G., Gao, P., Wei, C., and Wang, Y. (2024). Android malware family labeling: Perspectives from the industry. In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering, ASE ’24, page 2176–2186, New York, NY, USA. Association for Computing Machinery.

Wu, Y., Shi, J., Wang, P., Zeng, D., and Sun, C. (2023). Deepcatra: Learning flow- and graph-based behaviours for android malware detection. IET Information Security, 17(1):118–130.