This paper introduces a new Internet trace technique for generating frequent episode rules to characterize Internet traffic events. These episode rules are used to distinguish anomalous sequences of TCP, UDP, or ICMP connections from normal traffic episodes. Fundamental pruning techniques are introduced to reduce the rule search space by 70%. The new detection scheme was tested over real-life Internet trace data at USC. Our anomaly detection scheme results in a success rate of 47% for DoS, R2L, and port-scanning attacks. These results demonstrate an average of 51% improvement over the use of association rules. We experienced 20 or less false alarms over 200 network attacks in 9 days of tracing experiments. This anomaly detection scheme can be used jointly with signature-based IDS to achieve even higher detection efficiency.