As long as anti-malware software develops, malware writers also develop their malicious code by using various evasion strategiessuch as obfuscation and encryption. This is the lifecycle of malicious and anti-malware software. In this study, 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. 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 study is the first application of coevolutionary computation to address this problem.