Detecting malwares in data streams of interest. In an embodiment, for each malware signature of interest, a malware sub-pattern that is likely to occur at low frequencies in clean data streams is identified. When scanning a data stream for malwares, each portion of the data stream is examined for match with a malware sub-pattern of a malware signature. If there is no match with any portion of the data stream, it is concluded that the data stream is free of a first malware corresponding to the malware signature. If there is a match with a first portion of the data stream, the data stream is examined around the first portion for the malware signature, wherein the data stream is concluded to contain the first malware if the data stream around the first portion is found to match the malware signature.