A malicious behavior detector (100) for detecting malicious behavior on a network, comprises a processor unit (120) and associated system memory (130) containing computer program code. The computer program code provides a signature matching module (132) to perform malicious partial signature detection by reading the contents of packets of data passing through the network to look for partial signatures associated with malicious programs; a Domain Name Service, DNS, request and/or response detection module (134) to monitor the requests made by hosts connected to the network and/or responses thereto; and an evidence assessment module (138) to analyze the results of the partial signature detection and the DNS monitoring make a determination of the suspected presence of malicious behavior on the network based upon the analysis of the results of both the partial signature detection and the DNS monitoring.