Intrusion detection systems (IDSs) are essential entities in a network topology aiming to safeguard the integrity and availability of sensitive assets in the protected systems. In misuse detection systems, which is the topic of the paper at hand, the detection process relies on specific attack signatures (rules) in an effort to distinguish between legitimate and malicious network traffic. Generally, three major challenges are associated with any IDS of this category: identifying patterns of new attacks with high accuracy, ameliorating the human-readability of the detection rules, and rightly designating the category these attacks belong to. To this end, we propose Dendron, a methodology for generating new detection rules which are able to classify both common and rare types of attacks. Our methodology takes advantage of both Decision Trees and Genetic Algorithms for the sake of evolving linguistically interpretable and accurate detection rules. It also integrates heuristic methods in the evolutionary process aiming to deal with the challenging nature of the network traffic, which generally biases machine learning techniques to neglect the minority classes of a dataset. The experimental results, using KDDCup’99, NSL-KDD and UNSW-NB15 datasets, reveal that Dendron is able to achieve superior results over other state-of-the-art and legacy techniques under several classification metrics, while at the same time is able to significantly detect rare intrusive incidents.