In one embodiment, a device in a network tracks traffic features indicated by header information of packets of an encrypted traffic flow over time. The encrypted traffic flow is associated with a particular host in the network. The device detects an operating system start event based on the traffic features and provides data regarding the detected operating system start event as input to a machine learning-based malware detector to determine whether the particular host with which the encrypted traffic flow is associated is infected with malware. The device causes performance of a mitigation action in the network when the malware detector determines that the particular host is infected with malware.