Graph-based malware detection on the Android phones

Abstract

With Android being the most popular smartphone operating system, it has become the main target to launch malware. The consequence can be severe once the smartphone is infected with malware. Therefore it is crucial that Android application market operators can effectively identify malware on the market. However with malwares getting increasingly sophisticated, traditional antivirus has lost its edge against it. As a result there is a need to explore alternate malware detection techniques that can detect malwares and its variants efficiently and effectively. One way is through the use of Program Dependency Graph. With it, we can exploit the semantics information that is difficult to alter even when the malware deployed code obfuscation. However the use of PDG through graph matching algorithm is not feasible because of subgraph isomorphism which is a NP-Complete problem and hence there is scalability issue. From here, we seek to explore different approach to utilize the PDG while making it scalable. The two main approaches will be through filtering approach to reduce the amount of graph to be matched and the use of data mining and features analysis of PDG structural information. After some evaluations, it is deemed that after applying filtering approach, the use of PDG is still not feasible as experiments have been conducted to query 7 malicious methods from 6 different malwares against 11 malwares (inclusive of the previous 6), and the filtering approach could not find any match within 10 minutes for each query, therefore the focus has been shifted to data mining and feature analysis approach