According to the report of International Data Corporation (IDC), Android OS has dominated the worldwide smart phone Operating System (OS) Market with a 78% share at the first quarter of 2015; also, in the report of F-Secure, 99% of new smart phone threats emerged in the first quarter of 2014 are designed for Android. In recent years, many kinds of malware, such as Botnet, Backdoor, Rootkits, and Trojans, start to attack smart phones for conducting crimes such as fraud, service misuse, information stealing, and root access. In general, they have some shared characteristics, such as constantly scanning for Bluetooth to shorten the device's battery life, accessing the GPS to send the position information to Internet, and jamming the communication between device and the base station to paralyze the wireless network. According to these characteristics, there are a lot of detection method proposed, such as behavior checking, permission-based analysis, and Static Analysis, applied in malware detection software and anti-virus software. However, advanced hackers can utilize some techniques, such as emulator detection, packer, and code obfuscation, to prevent their attacks from being detected. This paper focuses on reviewing the malware evolution which makes malware detection more and more difficult, as well as the development of malware detection software which makes smart phones safer. Finally, our survey gives an insight into the malware evolution trend to increase the detecting rate of unknown malware for malware detection software.