Modern botnets such as Zeus and Conficker commonly utilize a technique called domain fluxing or a domain generation algorithm to generate a large number of pseudo-random domain names (PDNs) dynamically for botnet operators to control their bots. These botnets are becoming one of the most serious threats to Internet security on a global scale. How to prevent their destructive action is one of the most pressing issues of today. In this paper, we focus on detecting domain-flux botnets within the monitored network based on Domain Name System (DNS) traffic features. This method passively captures all DNS traffic from the gateway of a monitored network and then extracts key features to identify PDN. Based on examining and analyzing a large number of legitimate domains as well as PDN generated by botnets, we have discovered that there is a discernible bias in the rules for constructing domain names. Therefore, we introduce a methodology that analyzes DNS traffic to extract the length and the expected value, which can distinguish between a domain name generated by humans or bots. In order to evaluate the effectiveness of the proposed approach, various machine learning algorithms are applied to train predictive models for our detection system. This proposed scheme is implemented and tested in a real local area network. The experimental results show that our proposed method achieves the highest detective efficiency for decision tree algorithms (J48) with an average overall accuracy of up to 92.3% and a false positive rate of 4.8%. Copyright (c) 2016 John Wiley & Sons, Ltd.