Graph Eigenvector-based Android Program Similarity Comparison Algorithm Study

Among mobile applications from various Android markets, many have beenrepackaged, resigned and redistributed from legal applications. Existing studies onAndroid applications’ similarity suffer from difficulties for the extracted features todescribe the applications’ code, complexity of feature-extracting algorithms andinefficiency of detection and processing. How to systematically identify theserepackaged applications among huge amounts of Android applications in a fast andaccurate way? Is it possible to quickly and accurately detect repackaged apps so as toefficiently manage the abundance of application submission? Can we help usersefficiently decide whether an application is legal or contains malicious load? Theseare the challenges inAndroid study.Faced with these questions, this paper is based on the feature model of grapheigenvector, combined with cosine algorithm, Normalized Compression Distancealgorithm and similarity analysis between applications, and proposes a time-efficientalgorithm. This algorithm basically conducts static analysis of Android applicationfrom the Dalvik bytecode level and discovers the dependence between classes. Thispaper proposes a model based on graph eigenvector according to class relationsbetween decompiled Android code. This model preserves inter-vertex call relationsand structural invariable information in the class dependence graph, it can fight wellagainst the above technologies.We first compute the transitive probability matrix based on class dependencegraph, and then map the transitive probability matrix to a multi-dimensionaleigenvector to conduct similarity analysis. This can quickly and efficiently identifyrepackaged apps among huge amounts of Android apps. We use machine learning toanalyze the results so as to discover underlying pirated and malicious code in Androidapplications.The algorithm proposed by this paper is good in both detection rate and accuracy.The findings will provide a better external environment for Android developers, and itreduces the risks smartphone users take when they install third-party applications.