  Over the last decade, researchers have extensively explored the
vulnerabilities of Android malware detectors to adversarial examples through
the development of evasion attacks; however, the practicality of these attacks
in real-world scenarios remains arguable. The majority of studies have assumed
attackers know the details of the target classifiers used for malware
detection, while in reality, malicious actors have limited access to the target
classifiers. This paper introduces EvadeDroid, a problem-space adversarial
attack designed to effectively evade black-box Android malware detectors in
real-world scenarios. EvadeDroid constructs a collection of problem-space
transformations derived from benign donors that share opcode-level similarity
with malware apps by leveraging an n-gram-based approach. These transformations
are then used to morph malware instances into benign ones via an iterative and
incremental manipulation strategy. The proposed manipulation technique is a
query-efficient optimization algorithm that can find and inject optimal
sequences of transformations into malware apps. Our empirical evaluations,
carried out on 1K malware apps, demonstrate the effectiveness of our approach
in generating real-world adversarial examples in both soft- and hard-label
settings. Our findings reveal that EvadeDroid can effectively deceive diverse
malware detectors that utilize different features with various feature types.
Specifically, EvadeDroid achieves evasion rates of 80%-95% against DREBIN,
Sec-SVM, ADE-MA, MaMaDroid, and Opcode-SVM with only 1-9 queries. Furthermore,
we show that the proposed problem-space adversarial attack is able to preserve
its stealthiness against five popular commercial antiviruses with an average of
79% evasion rate, thus demonstrating its feasibility in the real world.
