Mobile malware is one of today's greatest threats in computer security. Furthermore, new mobile malware is emerging daily that introduces new security risks. However, while existing security solutions generally protect mobile devices against known risks, they are vulnerable to as yet unknown risks. How anti-malware software reacts to new, unknown malicious software is generally difficult to predict. Therefore, anti-malware software is in continuous development in order to be able to detect new malware or new variants of existing malware. Similarly, as long as anti-malware software develops, malware writers also develop their malicious code by using various evasion strategies, such as obfuscation and encryption. This is the lifecycle of malicious and anti-malware software. In this paper, the use of evolutionary computation techniques are investigated, both for developing new variants of mobile malware which successfully evades anti-malware systems based on static analysis and for developing better security solutions against them automatically. A coevolutionary arms race mechanism has always been considered a potential candidate for developing a more robust system against new attacks and for system testing. To the best of the authors' knowledge, this paper is the first application of coevolutionary computation to address this problem.