Malware detection is still a very challenging topic in the cybersecurity field. This is mainly due to the use of obfuscation techniques. To solve this issue, researchers proposed to extract frequent API (Application Programming Interface) call sequences and then use them as behavior indicators. Several methods aiming at generating malware detection rules have been proposed with the goal to come up with a set of rules that is able to accurately detect malicious code patterns. However, the rules generation process heavily depends on the training database content which will affect the detection rate of the model when confronted to new variants of malicious patterns. In order to assess a rule's detection accuracy, we need to execute the rule on the whole malware database which makes the detection rule quality evaluation very sensitive to the database content. To solve this issue, we suggest in this paper to consider the detection rules generation process as a BLOP (Bi-Level Optimization Problem), where a lower-level optimization task is embedded within the upper-level one. The goal of the upper-level is to generate a set of detection rules in the form of: trees of combined patterns. Those rules are able to detect not only the real patterns from the base of examples but also the artificial patterns generated by the lower-level. The lower-level aims to generate a set of artificial malicious patterns that escape the rules of the upper-level. An efficient co-evolutionary algorithm is adopted as a search engine to ensure optimization at both levels. Such an automated competition between the two levels makes our new method BMD (Bilevel Malware Detection) able to produce effective detection rules that are capable of detecting new predictable malicious behaviors in addition to existing ones. Based on the statistical analysis of the experimental results, our BMD method has shown its merits when compared to several relevant state-of-the-art malware detection techniques on different Android malware datasets.