Despite the existing anti-malware techniques and their interesting achieved results to "hook" attacks, the unstoppable evolution of malware makes the need for more capable malware detection systems overriding. In this paper, we propose a new malware detection technique named Bilevel-Roughset based Malware Detection (BLRDetect) that is based on, and exploits the benefits of, Bilevel optimization and Rough Set Theory. The upper-level of the Bilevel optimization component uses a Genetic Programming Algorithm in its chase of generating powerful detection rules while the lower-level leans on both a Genetic Algorithm and a Rough-Set module to produce high quality, and reliable, malware samples that escape, to their best, the upper-level's generated detection rules. Both levels interact with each other in a competitive way in order to produce populations that depend on one another. Our detection technique has proven its outperformance when tested against various stateof-the-art malware detection systems using common evaluation metrics.