  Android malware is a spreading disease in the virtual world. Anti-virus and
detection systems continuously undergo patches and updates to defend against
these threats. Most of the latest approaches in malware detection use Machine
Learning (ML). Against the robustifying effort of detection systems, raise the
\emph{evasion attacks}, where an adversary changes its targeted samples so that
they are misclassified as benign. This paper considers two kinds of evasion
attacks: feature-space and problem-space. \emph{Feature-space} attacks consider
an adversary who manipulates ML features to evade the correct classification
while minimizing or constraining the total manipulations.
\textit{Problem-space} attacks refer to evasion attacks that change the actual
sample. Specifically, this paper analyzes the gap between these two types in
the Android malware domain. The gap between the two types of evasion attacks is
examined via the retraining process of classifiers using each one of the
evasion attack types. The experiments show that the gap between these two types
of retrained classifiers is dramatic and may increase to 96\%. Retrained
classifiers of feature-space evasion attacks have been found to be either less
effective or completely ineffective against problem-space evasion attacks.
Additionally, exploration of different problem-space evasion attacks shows that
retraining of one problem-space evasion attack may be effective against other
problem-space evasion attacks.
