Evading network anomaly detection systems: formal reasoning and practical techniques

ABSTRACT

Attackers often try to evade an intrusion detection system (IDS) when launching their attacks. There have been several published studies in evasion attacks, some with available tools, in the research community as well as the "hackers'' community. Our recent empirical case study showed that some payload-based network anomaly detection systems can be evaded by a polymorphic blending attack (PBA). The main idea of a PBA is to create each polymorphic instance in such a way that the statistics of attack packet(s) match the normal traffic profile. In this paper, we present a formal framework for the open problem: given an anomaly detection system and an attack, can one automatically generate its PBA instances? We show that in general, generating a PBA that optimally matches the normal traffic profile is a hard problem (NP-complete). However, the problem of finding a PBA can be reduced to the SAT or ILP problems so that solvers available in those domains can be used to find a near-optimal solution. We also present a heuristic (hill-climbing) to find an approximate solution. Our framework can not only expose how the IDS can be exploited by a PBA but also suggest how the IDS can be improved to prevent the PBA. We have experimented with our framework using the PAYL 1-gram and 2-gram anomaly detection system, and the results have validated our framework.

References

1. P. Akritidis, E. P. Markatos, M. Polychronakis, and K. Anagnostakis. Stride: Polymorphic sled detection through instruction sequence analysis. In 20th IFIP International Information Security Conference, 2005.
2. M. Barreno, B. Nelson, R. Sears, A. D. Joseph, and J. D. Tygar. Can machine learning be secure? In Proceedings of the ACM Symposium on Information, Computer, and Communication Security (ASIACCS), 2006.
3. M. Christodorescu, S. Jha, S. Seshia, D. Song, and R. Bryant. Semantics-aware malware detection. In Proceedings of the IEEE Symposium on Security and Privacy, 2005.
4. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms. The MIT Press/McGraw-Hill, 1990.
5. T. Detristan, T. Ulenspiegel, Y. Malcom, and M. Underduk. Polymorphic shellcode engine using spectrum analysis. Phrack Issue 0x3d, 2003.
6. S. T. Eckmann, G. Vigna, and R. A. Kemmerer. Statl: An attack language for state-based intrusion detection. JOURNAL OF COMPUTER SECURITY, 10:71--104, 2002.
7. H. Feng, J. Giffin, Y. Huang, S. Jha, W. Lee, and B. Miller. Formalizing sensitivity in static analysis for intrusion detection. In Proceedings of the IEEE Symposium on Security and Privacy, 2004.
8. H. Feng, O. Kolesnikov, P. Fogla, W. Lee, and W. Gong. Anomaly detection using call stack information. In Proceedings of the IEEE Symposium on Security and Privacy, 2003.
9. Firew0rker. Windows media services remote command execution exploit. http://www.k-otik.com/exploits/07.01.nsiilog-titbit.cpp.php, 2003.
10. P. Fogla, M. Sharif, R. Perdisci, O. M. Kolesnikov, and W. Lee. Polymorphic blending attacks. In 15th USENIX Security Symposium, 2006.
11. C. Kaufman, R. Perlman, and M. Speciner. Network security: Private communication in a public world. Prentice Hall, 2002.
12. C. Kruegel, E. Kirda, D. Mutz, W. Robertson, and G. Vigna. Automating mimicry attacks using static binary analysis. In 14th Usenix Security Symposium, 2005.
13. C. Kruegel, E. Kirda, D. Mutz, W. Robertson, and G. Vigna. Polymorphic worm detection using structural information of executables. In Recent Advances in Intrusion Detection (RAID), 2005.
14. C. Kruegel, T. Toth, and E. Kirda. Service specific anomaly detection for network intrusion detection. In Proceedings of the ACM SIGSAC, 2002.
15. C. Kruegel and G. Vigna. Anomaly detection of web-based attacks. In Proceedings of the ACM Conference on Computer and Communication Security (ACM CCS), pages 251--261, 2003.
16. Ktwo. Admmutate: Shellcode mutation engine. http://www.ktwo.ca/ADMmutate-0.8.4.tar.gz, 2001.
17. Z. Liang and R. Sekar. Fast and automated generation of attack signatures: a basis for building self-protecting servers. Proceedings of the 12th ACM Conference on Computer and Communications Security (ACM CCS), pages 213--222, 2005.
18. M. Mahoney. Network traffic anomaly detection based on packet bytes. In Proceedings of the ACM SIGSAC, 2003.
19. M. Mahoney and P.K. Chan. Learning nonstationary models of normal network traffic for detecting novel attacks.
20. J. Newsome, B. Karp, and D. Song. Polygraph: Automatically generating signatures for polymorphic worms. In Proceedings of the IEEE Symposium on Security and Privacy, 2005.
21. Martin Roesch. Snort-lightweight intrusion detection for networks. In Proceedings of the 13th USENIX conference on System administration, pages 229--238, 1999.
22. S. Rubin, S. Jha, and B. P. Miller. Language-based generation and evaluation of nids signatures. In Proceedings of the IEEE Symposium on Security and Privacy, 2005.
23. S. Rubin, S. Jha, and B.P. Miller. Automatic generation and analysis of nids attacks. In Annual Computer Security Applications Conference (ACSAC), 2004.
24. R. Sekar, M. Bendre, D. Dhurjati, and P. Bollineni. A fast automaton-based method for detecting anomalous program behaviors. In Proceedings of the IEEE Symposium on Security and Privacy, 2001.
25. R. Sekar, A. Gupta, J. Frullo, T. Shanbhag, A. Tiwari, H. Yang, and S. Zhou. Specification-based anomaly detection: A new approach for detecting network intrusions. In Proceedings of the ACM conference on Computer and communications security (ACM CCS), 2002.
26. C. Sinz. Towards an optimal cnf encoding of boolean cardinality constraints. In Principles and Practice of Constraint Programming, pages 827--831, 2005.
27. P. Szor. Advanced code evolution techniques and computer virus generator kits. The Art of Computer Virus Research and Defense, 2005.
28. T. Toth and C. Kruegel. Accurate buffer overflow detection via abstract payload execution. In Recent Advances in Intrusion Detection (RAID), 2002.
29. G. Vigna, W. Robertson, and D. Balzarotti. Testing network-based intrusion detection signatures using mutant exploits. In Proceedings of the ACM Conference on Computer and Communication Security (ACM CCS), pages 21--30, 2004.
30. D. Wagner and P. Soto. Mimicry attacks on host-based intrusion detection systems. In Proceedings of the ACM Conference on Computer and Communication Security (ACM CCS), 2002.
31. K. Wang and S. Stolfo. Anomalous payload-based network intrusion detection. In Recent Advances in Intrusion Detection (RAID), 2004.
32. K. Wang and S. Stolfo. Anomalous payload-based worm detection and signature generation. In Recent Advances in Intrusion Detection (RAID), 2005.
33. T. Yetiser. Polymorphic viruses: Implementation, detection, and protection. Technical Report, VDS Advanced Research Group, 1993.

Index Terms

• Security and privacy

  • Network security