  In this paper we present an elaborated graph-based algorithmic technique for
efficient malware detection. More precisely, we utilize the system-call
dependency graphs (or, for short ScD graphs), obtained by capturing taint
analysis traces and a set of various similarity metrics in order to detect
whether an unknown test sample is a malicious or a benign one. For the sake of
generalization, we decide to empower our model against strong mutations by
applying our detection technique on a weighted directed graph resulting from
ScD graph after grouping disjoint subsets of its vertices. Additionally, we
have developed a similarity metric, which we call NP-similarity, that combines
qualitative, quantitative, and relational characteristics that are spread among
the members of known malware families to archives a clear distinction between
graph-representations of malware and the ones of benign software. Finally, we
evaluate our detection model and compare our results against the results
achieved by a variety of techniques proving the potentials of our model.
