- This paper presents a fast and scalable method for detecting threats in large-scale DNS logs. In such logs, queries about “abnormal” domain strings are often correlated with malicious behavior. With our method, a language model algorithm learns “normal” domain-names from a large dataset to rate the extent of domain-name “abnormality” within a big data stream of DNS queries in the organization. Variable-order Markov Models (VMMs) serve as out underlying algorithmic tool since their running time is linear in the input sequence while their memory requirements are constantly bounded from above, both very appealing characteristics. Our experimental study indicates that the proposed method can detect domain names generated by a genuine Domain Generation Algorithm, used in Advanced Persistent Threat attack scenarios, with less than 5% false-negative and 1% false-positive rates. This detection rate is similar to more computationally intensive methods that are not scalable for big data environments.