A method of detecting malware may include: a) examining header data in each PDU transferred by a port of an access switch to identify PDUs transferred from a local network device, b) extracting a far-end device address for PDUs based at least in part on examination of an address portion of the corresponding header data, c) maintaining fan-out information indicative of a quantity of unique far-end device addresses extracted from the PDUs during consecutive time windows, d) determining a current trend based on the fan-out information for a current time window, e) comparing the current trend to an expected trend, and f) identifying a suspected malware infection in the local network device when the current trend exceeds the expected trend by a trend threshold. A network element that may implement the method may include a header data processing unit, data storage logic, data processing logic, and malware identification logic.