Internet worms pose a serious threat to networks. Most current Intrusion Detection Systems (IDSs) take signature matching approach to detect worms. Given the fact that most signatures are developed manually, generating new signatures for each variant of a worm incurs significant overhead. In this paper, we propose a difference-based scheme which differences worm flows and normal flows to generate robust worm signatures. The proposed scheme is based on two observational facts - worm flows contain several invariant portions in their payloads, and core worm codes do not exist in normal flows. It uses samples of worm flows detected by available means to extract common tokens. It then differences the set of these tokens with those of normal flows and generates signature candidates. By using such signatures within enterprises, out of reach of worm writers, the possibility of being tricked by worm writers can be reduced. We evaluate the proposed scheme using real network traffic traces that contains worms. Experiment results show that the proposed scheme exhibits high detection rate with low false positives.