  Domain generation algorithms (DGAs) can be categorized into three types:
zero-knowledge, partial-knowledge, and full-knowledge. While prior research
merely focused on zero-knowledge and full-knowledge types, we characterize
their anti-detection ability and practicality and find that zero-knowledge DGAs
present low anti-detection ability against detectors, and full-knowledge DGAs
suffer from low practicality due to the strong assumption that they are fully
detector-aware. Given these observations, we propose PKDGA, a partial
knowledge-based domain generation algorithm with high anti-detection ability
and high practicality. PKDGA employs the reinforcement learning architecture,
which makes it evolve automatically based only on the easily-observable
feedback from detectors. We evaluate PKDGA using a comprehensive set of
real-world datasets, and the results demonstrate that it reduces the detection
performance of existing detectors from 91.7% to 52.5%. We further apply PKDGA
to the Mirai malware, and the evaluations show that the proposed method is
quite lightweight and time-efficient.
