Actual traffic logs of network traffic to and from host devices in a network are collected over time. Artificial traffic logs for each of multiple artificial network address translation (NAT) devices are generated from the actual traffic logs. The actual traffic logs and the artificial traffic logs are labeled as being indicative of non-NAT devices and NAT devices, respectively, to produce labeled traffic logs. From the labeled traffic logs for each artificial NAT device and each non-NAT device, respective, correspondingly labeled, network traffic features indicative of whether the device behaves like a NAT device or a non-NAT device are extracted. A classifier device is trained using the network traffic features extracted for each artificial NAT device and each non-NAT device to classify between an actual NAT device and an actual non-NAT device based on further actual traffic logs.