Fast and Black-box Exploit Detection and Signature Generation for Commodity Software

ABSTRACT

In biology, a vaccine is a weakened strain of a virus or bacterium that is intentionally injected into the body for the purpose of stimulating antibody production. Inspired by this idea, we propose a packet vaccine mechanism that randomizes address-like strings in packet payloads to carry out fast exploit detection and signature generation. An exploit with a randomized jump address behaves like a vaccine: it will likely cause an exception in a vulnerable program’s process when attempting to hijack the control flow, and thereby expose itself. Taking that exploit as a template, our signature generator creates a set of new vaccines to probe the program in an attempt to uncover the necessary conditions for the exploit to happen. A signature is built upon these conditions to shield the underlying vulnerability from further attacks. In this way, packet vaccine detects exploits and generates signatures in a black-box fashion, that is, not relying on the knowledge of a vulnerable program’s source and binary code. Therefore, it even works on the commodity software obfuscated for the purpose of copyright protection. In addition, since our approach avoids the expense of tracking the program’s execution flow, it performs almost as fast as a normal run of the program and is capable of generating a signature of high quality within seconds or even subseconds. We present the design of the packet vaccine mechanism and an example of its application. We also describe our proof-of-concept implementation and the evaluation of our technique using real exploits.

REFERENCES

• 1: K. G. Anagnostakis , S. Sidiroglou , P. Akritidis , K. Xinidis , E. Markatos , A. D. Keromytis, Detecting targeted attacks using shadow honeypots, Proceedings of the 14th conference on USENIX Security Symposium, p.9-9, July 31-August 05, 2005, Baltimore, MD
• 2: Associated Press. 2006. Microsoft warns against outside fixes. http://biz.yahoo.com/ap/060331/microsoft_s_security_snags.html?.v=4.
• 3: Ballista. 2006. The Ballista@ Project: COTS Software Robustness Testing. http://www.ece.cmu.edu/~koopman/ballista/.
• 4: Barton, J. H., Czeck, E. W., Segall, Z. Z., and Siewiorek, D. P. 1990. Fault injection.
• 5: David Brumley , James Newsome , Dawn Song , Hao Wang , Somesh Jha, Towards Automatic Generation of Vulnerability-Based Signatures, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.2-16, May 21-24, 2006 [doi>10.1109/SP.2006.41]
• 6: Carrette, G. J. 2006. CRASHME: Random input testing. http://people.delphiforums.com/gjc/crashme.html.
• 7: Manuel Costa , Jon Crowcroft , Miguel Castro , Antony Rowstron , Lidong Zhou , Lintao Zhang , Paul Barham, Vigilante: end-to-end containment of internet worms, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 8: Jedidiah R. Crandall , Frederic T. Chong, Minos: Control Data Attack Prevention Orthogonal to Memory Model, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.221-232, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.26]
• 9: Jedidiah R. Crandall , Zhendong Su , S. Felix Wu , Frederic T. Chong, On deriving unknown vulnerabilities from zero-day polymorphic and metamorphic worm exploits, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102152]
• 10: Crandall, J. R., Wu, S. F., and Chong, F. T. 2005. Experiences Using Minos as a Tool for Capturing and Analyzing Novel Worms for Unknown Vulnerabilities. In Proceedings of the GI International Conference on Detection of Intrusions & Malware, and Vulnerability Assessment (DIMVA’’05). 32--50.
• 11: Weidong Cui , Marcus Peinado , Helen J. Wang , Michael E. Locasto, ShieldGen: Automatic Data Patch Generation for Unknown Vulnerabilities with Informed Probing, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.252-266, May 20-23, 2007 [doi>10.1109/SP.2007.34]
• 12: Dreger, H., Kreibich, C., Paxson, V., and Sommer, R. 2005. Enhancing the accuracy of network-based intrusion detection with host-based context. In Proceedings of the GI International Conference on Detection of Intrusions & Malware, and Vulnerability Assessment (DIMVA’’05). 206--221.
• 13: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060309]
• 14: HoneyNet. 2006. http://www.honeynet.org/.
• 15: Ghani A. Kanawati , Nasser A. Kanawati , Jacob A. Abraham, FERRARI: A Flexible Software-Based Fault and Error Injection System, IEEE Transactions on Computers, v.44 n.2, p.248-260, February 1995 [doi>10.1109/12.364536]
• 16: Hyang-Ah Kim , Brad Karp, Autograph: toward automated, distributed worm signature detection, Proceedings of the 13th conference on USENIX Security Symposium, p.19-19, August 09-13, 2004, San Diego, CA
• 17: Christian Kreibich , Jon Crowcroft, Honeycomb: creating intrusion detection signatures using honeypots, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972384]
• 18: Kruegel, C., Kirda, E., Mutz, D., Robertson, W., and Vigna, G. 2005. Polymorphic worm detection using structural information of executables. In Proceedings of the International Symposium on Recent Advances in Intrusion Detection (RAID’05). 207--226.
• 19: Zhenkai Liang , R. Sekar, Automatic Generation of Buffer Overflow Attack Signatures: An Approach Based on Program Behavior Models, Proceedings of the 21st Annual Computer Security Applications Conference, p.215-224, December 05-09, 2005 [doi>10.1109/CSAC.2005.12]
• 20: Zhenkai Liang , 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, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102150]
• 21: Zhenkai Liang , R. Sekar , Daniel C. DuVarney, Automatic synthesis of filters to discard buffer overflow attacks: a step towards realizing self-healing systems, Proceedings of the annual conference on USENIX Annual Technical Conference, p.21-21, April 10-15, 2005, Anaheim, CA
• 22: Locasto, M. E., Sidiroglou, S., and Keromytis, A. D. 2006. Software self-healing using collaborative application communities. In Proceedings of the 13th Annual Network and Distributed Systems Security Symposium (NDSS’06).
• 23: Locasto, M. E., Wang, K., Keromytis, A. D., and Stolfo, S. J. 2005. Flips: Hybrid adaptive intrusion prevention. In Proceedings of the International Symposium on Recent Advances in Intrusion Detection (RAID’05).
• 24: Marty, R. 2002. Thor: A tool to test intrusion detection systems by variations of attacks. Master thesis, ETH Zurich.
• 25: MemView. 2006. http://www2.biglobe.ne.jp/ sota/memview-e.html.
• 26: Microsoft. 2007. Microsoft debuging tools: Overview. http://www.microsoft.com/whdc/devtools/debugging/default.mspx.
• 27: Mockapetris, P. 1987. DOMAIN NAMES - IMPLEMENTATION AND SPECIFICATION. RFC 3425. http://www.ietf.org/rfc/rfc1035.txt.
• 28: Musa, J., Fuoco, G., Irving, N., Juhlin, B., and Kropfl, D. 1996. Handbook of Software Reliability Engineering. McGraw-Hill, New York, 167--216.
• 29: Gleb Naumovich , Nasir Memon, Preventing Piracy, Reverse Engineering, and Tampering, Computer, v.36 n.7, p.64-71, July 2003 [doi>10.1109/MC.2003.1212692]
• 30: Newsome, J., Brumley, D., and Song, D. 2005. Vulnerability-specific execution filtering for exploit prevention on commodity software. In Proceedings of the 13th Annual Network and Distributed Systems Security Symposium (NDSS’05).
• 31: James Newsome , Brad Karp , Dawn Song, Polygraph: Automatically Generating Signatures for Polymorphic Worms, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.226-241, May 08-11, 2005 [doi>10.1109/SP.2005.15]
• 32: Newsome, J. and Song, D. 2005. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of the 12th Annual Network and Distributed System Security Symposium (NDSS’05). San Diego, CA.
• 33: Pasupulati, A., Coit, J., Levitt, K., Wu, S., Li, S., Kuo, R., and Fan, K. 2004. Buttercup: On network-based detection of polymorphic buffer overflow vulnerabilities. In Proceedings of the IEEE/IFIP Network Operation and Management Symposium (NOMS’04).
• 34: Roberto Perdisci , David Dagon , Wenke Lee , Prahlad Fogla , Monirul Sharif, MisleadingWorm Signature Generators Using Deliberate Noise Injection, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.17-31, May 21-24, 2006 [doi>10.1109/SP.2006.26]
• 35: Portokalidis, G. and Bos, H. 2005. SweetBait: Zero-hour worm detection and containment using honeypots. Tech. rep. IR-CS-015, Vrije Universiteit Amsterdam.
• 36: James C. Reynolds , James Just , Larry Clough , Ryan Maglich, On-Line Intrusion Detection and Attack Prevention Using Diversity, Generate-and-Test, and Generalization, Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS'03) - Track 9, p.335.2, January 06-09, 2003
• 37: David W. Richardson , Steven D. Gribble , Edward D. Lazowska, The limits of global scanning worm detectors in the presence of background noise, Proceedings of the 2005 ACM workshop on Rapid malcode, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103626.1103638]
• 38: SecurityFocus. 2006. http://www.securityfocus.com.
• 39: Hovav Shacham , Matthew Page , Ben Pfaff , Eu-Jin Goh , Nagendra Modadugu , Dan Boneh, On the effectiveness of address-space randomization, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030124]
• 40: Colleen Shannon , David Moore, The Spread of the Witty Worm, IEEE Security and Privacy, v.2 n.4, p.46-50, July 2004 [doi>10.1109/MSP.2004.59]
• 41: Stelios Sidiroglou , Michael E. Locasto , Stephen W. Boyd , Angelos D. Keromytis, Building a reactive immune system for software services, Proceedings of the annual conference on USENIX Annual Technical Conference, p.11-11, April 10-15, 2005, Anaheim, CA
• 42: Sumeet Singh , Cristian Estan , George Varghese , Stefan Savage, Automated worm fingerprinting, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.4-4, December 06-08, 2004, San Francisco, CA
• 43: Lance Spitzner, Honeypots: Catching the Insider Threat, Proceedings of the 19th Annual Computer Security Applications Conference, p.170, December 08-12, 2003
• 44: Sudarshan M. Srinivasan , Srikanth Kandula , Christopher R. Andrews , Yuanyuan Zhou, Flashback: a lightweight extension for rollback and deterministic replay for software debugging, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 27-July 02, 2004, Boston, MA
• 45: G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 46: Tang, Y. and Chen, S. 2005. Defending against internet worms: A signature-based approach. In Proceedings of the Annual IEEE Conference on Computer Communications (INFOCOM’05). Miami, FL.
• 47: Telescope. 2006. http://www.caida.org/analysis/security/telescope/.
• 48: Toth, T. and Krügel, C. 2002. Accurate buffer overflow detection via abstract payload execution. In Proceedings of the International Symposium on Recent Advances in Intrusion Detection (RAID’02). 274--291.
• 49: Timothy K. Tsai , Ravishankar K. Iyer, Measuring Fault Tolerance with the FTAPE Fault Injection Tool, Proceedings of the 8th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation: Quantitative Evaluation of Computing and Communication Systems, p.26-40, September 20-22, 1995
• 50: Joseph Tucek , James Newsome , Shan Lu , Chengdu Huang , Spiros Xanthos , David Brumley , Yuanyuan Zhou , Dawn Song, Sweeper: a lightweight end-to-end system for defending against fast worms, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
• 51: US-CERT. Microsoft windows metafile handler setabortproc gdi escape vulnerability. http://www.kb.cert.org/vuls/id/181038.
• 52: van Oorschot, P. C. 2003. Revisiting software protection. In Proceedings of the Information Security Conference (ISC’03). 1--13.
• 53: Giovanni Vigna , William Robertson , Davide Balzarotti, Testing network-based intrusion detection signatures using mutant exploits, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030088]
• 54: Vulnerabilities 2006. http://www.securityfocus.com/vulnerabilities.
• 55: Helen J. Wang , Chuanxiong Guo , Daniel R. Simon , Alf Zugenmaier, Shield: vulnerability-driven network filters for preventing known vulnerability exploits, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 56: Wang, K. and Stolfo, S. J. 2004. Anomalous payload-based network intrusion detection. In Proceedings of the International Symposium on Recent Advances in Intrusion Detection (RAID’04). 203--222.
• 57: XiaoFeng Wang , Zhuowei Li , Jun Xu , Michael K. Reiter , Chongkyung Kil , Jong Youl Choi, Packet vaccine: black-box exploit detection and signature generation, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180412]
• 58: Xinran Wang , Chi-Chun Pan , Peng Liu , Sencun Zhu, SigFree: a signature-free buffer overflow attack blocker, Proceedings of the 15th conference on USENIX Security Symposium, July 31-August 04, 2006, Vancouver, B.C., Canada
• 59: Wasson, S. 2004. The NX bit. http://techreport.com/reviews/2004q4/pentium4-570j/index.x?pg=1.
• 60: Whyte, D., Kranakis, E., and van Oorschot, P. 2005. DNS-based detection of scanning worms in an enterprise network. In Proceedings of the 12th Network and Distributed System Security Symposium (NDSS). 181--195.
• 61: Jun Xu , Peng Ning , Chongkyung Kil , Yan Zhai , Chris Bookholt, Automatic diagnosis and response to memory corruption vulnerabilities, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102151]
• 62: Vinod Yegneswaran , Jonathon T. Giffin , Paul Barford , Somesh Jha, An architecture for generating semantics-aware signatures, Proceedings of the 14th conference on USENIX Security Symposium, p.7-7, July 31-August 05, 2005, Baltimore, MD
• 63: Cliff C. Zou , Don Towsley , Weibo Gong , Songlin Cai, Routing Worm: A Fast, Selective Attack Worm Based on IP Address Information, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.199-206, June 01-03, 2005 [doi>10.1109/PADS.2005.24]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security

Keywords:
black-box defense, exploit detection, signature generation, vaccine injection, worm