Abstract: In order to achieve an efficient detection of malicious software on Android, a method to analyze the malware in Android devices using Dalvik instructions has been proposed. The Dalvik executable format (DEX) files are segmented based on its format without decompile. Through the formalize description of Dalvik instructions the features of the program can be simplified and extracted. Using the MOSS algorithm and the Minkowski distance algorithm, it can be determined that whether the current software which will be tested contains malicious code based on the similarity threshold. Finally, a prototype system is built to validate the method with large amounts of random samples. Taking applications which in Android application stores as example, the extraction and description of signatures using this method proves that not only can this static detection method based on Dalvik instructions detect malicious code quickly, but also has a very low rate of false positives and false negatives. Experiments results confirm that the method proposed by this paper is feasible and credible and it is applicable for rapid detection of Android malicious code.