To combat the threats posed by Android malware, various Android malware detection (AMD) approaches have emerged, with graph-based methods showing particular promise due to their deeper semantic insights from Function Call Graphs (FCGs). However, these systems are still susceptible to adversarial attacks that seek to evade detection by perturbing FCGs. While some recent approaches have been proposed to attack FCG-based detectors, they are still ineffective due to the vast perturbation space, particularly across diverse models with varying features.

To address these challenges, we introduce FCGHUNTER, a novel robustness testing framework for FCG-based AMD systems. FCGHUNTER employs several innovative techniques to enhance exploration and exploitation within this huge search space. Initially, it identifies critical areas within the FCG related to malware behaviors to narrow down the perturbation space. We then develop dependency-aware crossover and mutation method to enhance the validity and diversity of perturbations, generating diverse FCGs. Furthermore, FCGHUNTER utilizes multi-objective feedback for selecting the perturbed FCGs, which considers both the model output and interpretation-driven feature changes. We conducted extensive evaluation across 40 different scenarios, incorporating eight types of features and five model variants. The results demonstrate that  FCGHUNTER achieves an average attack success rate of 87.9%, which substantially outperforms baselines by at least 47%. Its effectiveness is particularly pronounced in robust models; for instance, tool achieves a 100% success rate on the robust model (i.e., AdaBoost with MalScan), where baselines are either inapplicable or achieve only an 11% success rate. The usefulness of FCGHUNTER is further validated in real-world black-box settings (i.e., VirusTotal).