In one embodiment, a traffic analysis service identifies a client in a network having an associated traffic flow that was blocked by a firewall. The traffic analysis service obtains traffic telemetry data regarding one or more subsequent traffic flows associated with the identified client that are subsequent to the blocked flow. The traffic analysis service uses a machine learning-based classifier to determine that the identified client is exhibiting evasive network behavior, based on the obtained traffic telemetry data. The traffic analysis service initiates a mitigation action in the network, based on the determination that the identified client is exhibiting evasive network behavior.