Portscan detectors in network intrusion detection products are easy to evade. They classify a portscan as more than N distinct probes within M seconds from a single source. This paper begins with an analysis of the scan detection problem, and then presents Spice (Stealthy Probing and Intrusion Corr elation Engine), a portscan detector that is effective against stealthy scans yet operationally practical. Our design maintains records of event likelihood, from which we approximate the anomalousness of a given packet. We use simulated annealing to cluster anomalous packets together into portscans using heuristics developed from real scans. Packets are kept around longer if they are more anomalous. This should enable us to detect all the scans detected by current techniques, plus many stealthy scans, with manageable false positives. We also discuss detection of other activity such as stealthy worms, and DDOS control networks.