US008074115B2
`
`(12) United States Patent
`Stolfo et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 8,074,115 B2
`Dec. 6, 2011
`
`(54)
`
`(75)
`
`METHODS, MEDIA AND SYSTEMS FOR
`DETECTING ANOMALOUS PROGRAM
`EXECUTIONS
`
`Inventors: Salvatore J. Stolfo, Ridgewood, NJ
`(US); Angelos D. Keromytis, New York,
`NY (US); Stelios Sidiroglou, New York,
`NY (US)
`
`(73)
`
`Assignee: The Trustees of Columbia University
`in the City of New York, New York, NY
`(Us)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,968,113 A * 10/1999 Haley et a1. ................... .. 714/38
`6,079,031 A *
`6/2000 Haley et a1.
`714/38
`6,154,876 A * ll/2000 Haley et a1.
`717/133
`7,155,708 B2 * 12/2006 Hammes et al. ............ .. 717/155
`7,490,268 B2
`2/2009 Keromytis et al.
`7,496,898 B1 *
`2/2009 Vu .............................. .. 717/127
`7,639,714 B2 12/2009 Stolfo et al.
`2005/0108562 A1 *
`5/2005 KhaZan et al. .............. .. 713/200
`
`OTHER PUBLICATIONS
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Hangal et al., Tracking down software bugs using automatic anomaly
`detection, Proceedings of the 24the international conference on soft
`ware engineering, May 2002, pp. 291-301.*
`
`(21)
`(22)
`
`(86)
`
`(87)
`
`(65)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`Appl. No.:
`
`12/091,150
`
`PCT Filed:
`
`Oct. 25, 2006
`
`PCT No.:
`§ 371 (0X1),
`(2), (4) Date:
`
`PCT/US2006/041591
`
`Jun. 15, 2009
`
`PCT Pub. No.: WO2007/050667
`PCT Pub. Date: May 3, 2007
`
`Prior Publication Data
`
`US 2010/0023810A1
`
`Jan. 28, 2010
`
`Related US. Application Data
`
`Provisional application No. 60/730,289, ?led on Oct.
`25, 2005.
`
`Int. Cl.
`(2006.01)
`G06F 11/00
`US. Cl. .................................................... .. 714/38.1
`Field of Classi?cation Search .............. .. 7l4/2il 0,
`7l4/25i29, 32, 33, 37*39, 47
`See application ?le for complete search history.
`
`(Continued)
`
`Primary Examiner * Nadeem Iqbal
`(74) Attorney, Agent, or Firm * Byrne Poh LLP
`
`(57)
`ABSTRACT
`Methods, media, and systems for detecting anomalous pro
`gram executions are provided. In some embodiments, meth
`ods for detecting anomalous program executions are pro
`vided, comprising: executing at least a part of a program in an
`emulator; comparing a function call made in the emulator to
`a model of function calls for the at least a part of the program;
`and identifying the function call as anomalous based on the
`comparison. In some embodiments, methods for detecting
`anomalous program executions are provided, comprising:
`modifying a program to include indicators of program-level
`function calls being made during execution of the program;
`comparing at least one of the indicators of program-level
`function calls made in the emulator to a model of function
`calls for the at least a part of the program; and identifying a
`function call corresponding to the at least one of the indicators
`as anomalous based on the comparison.
`
`42 Claims, 8 Drawing Sheets
`
`300
`
`\ MONITORING AN APPLICATION FOR VARIOUS TYPES
`OF FAILURES USING ONE OR MORE SENSORS
`
`3111
`
`PREDICTI'NG 'l'I-LAT A FAULT MAY OCCUR OR
`DETECTING A FAULT THAT OCCURRED IN AT LEAST 320
`A PORTION OF THE APPLICATION'S CODE (E.G.Y
`DETERMINING WHICH PORTIONS OF THE
`APPLICATION ARE VULNERAELE TO FAULTS
`AND/OR ATTACKS)
`
`UPON PREmcTmo THAT A PAULT MAY OCCUR OR 330
`DETECTING THAT A FAULT occumn, ISOLATING
`THE PORTION OF THE APPLICATION‘S CODE HAVING
`THE FAULTY INSTRUCTION
`
`I
`
`GENERATING AN INSTRUNEENTED VERSION OF THE
`PORTION OF THE APPLICATION'S CODE OR
`WRAPPING THAT PORTION OF THE APPLICATION'S
`CODE
`
`340
`
`350
`
`CONSTRUCTING AN EMULATOR‘EASED VACCINE
`
`360
`EMULATENG SEGMENTS OF AN APPLICATIONS
`CODE WI‘DZRE THE FAULT OCCURRED USING THE J
`EMULATOR-BASED VACCINE (E.G,, TESTING WITH
`THE INPUTS SEENS BEFORE THE FAULT OCCURRED)
`
`l
`
`IF THE FAULT OCCURS AGAIN, CAUSING THAT
`PORTION OF THE APPLICATION CODE TO RETURN
`WITH AN ERROR CODE, THEREBY SIMULATING A
`PROGRAMIMIED FAILURE
`
`370
`
`1
`
`SYMC 1001
`
`

`

`US 8,074,115 B2
`Page 2
`
`OTHER PUBLICATIONS
`
`Chan et al., A machine learning approach to anomaly detection,
`Technical Report, Dept. of computer science, Florida institute of
`technology, Mar. 2003, pp. 1-13.*
`M. Chew and D. Song, Mitigating Buffer Over?ows by Operating
`System Randomization, Technical Report CMUCS-02-197,
`Carnegie Mellon University, Dec. 2002.
`V. Prevelakis, A Secure Station for Network Monitoring and Control,
`In Proceedings of the 8th USENIX Security Symposium, Aug. 1999.
`J. Reynolds, J. Just, L. Clough, and R. Maglich, On-Line Intrusion
`Detection and Attack Prevention Using Diversity, Generate-and
`Test, and Generalization, In Proceedings of the 36th Annual Hawaii
`International Conference on System Sciences (HICSS), Jan. 2003.
`H. Shacham, M. Page, B. Pfaff, E. Goh, N. Modadugu, and D. Boneh,
`on the Effectiveness of Address-Space Randomization, In Proceed
`ings of the 11thACM Conference on Computer and Communications
`Security (CCS), pp. 298-307, Oct. 2004.
`S. Sidiroglou, M. Locasto, S. Boyd, and A. Keromytis, Building A
`Reactive Immune System for Software Services, In Proceedings of
`the 11th USENIX Annual Technical Conference, Apr. 2005.
`M. Stamp, Risk of Monoculture, Communications of the ACM,
`47(3):120, Mar. 2004.
`Using Network-Based Application Recognition and ACLs for Block
`ing the “Code Red” Worm, Technical report, Cisco Systems, Inc.
`Aleph One, Smashing the stack for fun and pro?t, Phrack, 7(49),
`1996.
`K. Ashcraft and D. Engler, Detecting Lots of Security Holes Using
`System-Speci?c Static Analysis, In Proceedings of the IEEE Syrn
`posium on Security and Privacy, May 2002.
`S. M. Bellovin, Distributed Firewalls, ;login: magazine, special issue
`on security, Nov. 1999.
`M. Bhattacharyya, M. G. Schultz, E. Eskin, S. Hershkop, and S. J.
`Stolfo, MET: An Experimental System for Malicious Email Track
`ing, In Proceedings of the New Security Paradigms Workshop
`(NSPW), pp. 1-12, Sep. 2002.
`Bulba and Kil3r, Bypassing StackGuard and StackShield, Phrack,
`5(56), May 2000.
`B. Chess, Improving Computer Security Using Extended Static
`Checking, In Proceedings of the IEEE Symposium on Security and
`Privacy, May 2002.
`M. Christodorescu and S. Jha, Static Analysis of Executables to
`Detect Malicious Patterns, In Proceedings of the 12th USENIX Secu
`rity Symposium, pp. 169-186, Aug. 2003.
`F. Cohen, Computer Viruses: Theory and Practice, Computers &
`Security, 6:22-35, Feb. 1987.
`C. Cowan, M. Barringer, S. Beattie, and G. Kroah-Hartman,
`Formatguard: Automatic protection from printf format string vulner
`abilities, In Proceedings of the 10th USENIX Security Symposium,
`Aug. 2001.
`C. Cowan, S. Beattie, C. Pu, P. Wagle, andV. Gligor, SubDomain:
`Parsimonious Security for Server Appliances, In Proceedings of the
`14th USENIX System Administration Conference (LISA 2000),
`Mar. 2000.
`C. Cowan, C. Pu, D. Maier, H. Hinton, J. Walpole, P. Bakke, S.
`Beattie, A. Grier, P. Wagle, and Q. Zhang, Stackguard: Automatic
`adaptive detection and prevention of buffer-over?ow attacks, In Pro
`ceedings of the 7th USENIX Security Symposium, Jan. 1998.
`D. Engler and K. Ashcraft, RacerX: Effective, Static Detection of
`Race Conditions and Deadlocks, Proceedings of ACM SOSP, Oct.
`2003.
`S. Forrest, A. Somayaji, and D. Ackley, Building Diverse Computer
`Systems, In Proceedings of the 6th HotOS Workshop, 1997.
`M. Frantzen and M. Shuey, StackGhost: Hardware facilitated stack
`protection, In Proceedings of the 10th USENIX Security Sympo
`sium, pp. 55-66, Aug. 2001.
`T. Gar?nkel, Traps and Pitfalls: Practical Problems in System Call
`Interposition Based Security Tools, In Proceedings of the Sympo
`sium on Network and Distributed Systems Security (SNDSS), pp.
`163-176, Feb. 2003.
`I. Goldberg, D. Wagner, R. Thomas, and E. Brewer, A Secure Envi
`ronment for Untrusted Helper Applications, In Proceedings of the
`1996 USENIX Annual Technical Conference, 1996.
`
`S. loannidis, A. Keromytis, S. Bellovin, and J. Smith, Implementing
`a Distributed Firewall, In Proceedings of the ACM Computer and
`Communications Security (CCS) Conference, pp. 190-199, Nov.
`2000.
`R. Janakiraman, M. Waldvogel, and Q. Zhang, Indra: A peer-topeer
`approach to network intrusion detection and prevention, In Proceed
`ings of the IEEE International Workshops on Enabling Technologies:
`Infrastructure for Collaborative Enterprises (WETICE), Workshop
`on Enterprise Security, Jun. 2003.
`R. Jones and P. Kelly, Backwards-compatible bounds checking for
`arrays and pointers in C programs, In Third International Workshop
`on Automated Debugging, 1997.
`J. Just, L. Clough, M. Danforth, K. Levitt, R. Maglich, J. C. Reynolds,
`and J. Rowe, Learning Unknown AttacksiA Start, In Proceedings of
`the 5th International Symposium on Recent Advances in Intrusion
`Detection (RAID), Oct. 2002.
`J. Kephart, A Biologically Inspired Immune System for Computers,
`In Arti?cial Life IV: Proceedings of the Fourth International Work
`shop on the Synthesis and Simulation of Living Systems, pp. 130
`139. MIT Press, 1994.
`M. Kodialam and T. V. Lakshman, Detecting Network Intrusions via
`Sampling: A Game Theoretic Approach, In Proceedings of the 22nd
`Annual Joint Conference of IEEE Computer and Communication
`Societies (INFOCOM), Apr. 2003.
`D. Larochelle and D. Evans, Statically Detecting Likely Buffer Over
`?owVulnerabilities, In Proceedings of the 10th Security Symposium,
`pp. 177-190, Aug. 2001.
`E. Larson and T. Austin, High Coverage Detection of Input-Related
`Security Faults, In Proceedings of the 12th Security Symposium, pp.
`121-136, Aug. 2003.
`K. Lhee and S. J. Chapin, Type-Assisted Dynamic Buffer Over?ow
`Detection. In Proceedings of the 11th Security Symposium, pp.
`81-90, Aug. 2002.
`M.-J. Lin, A. Ricciardi, and K. Marzullo, A New Model for Avail
`ability in the Face of Self-Propagating Attacks, In Proceedings of the
`New Security Paradigms Workshop, Nov. 1998.
`A. J. Malton, The Denotational Semantics of a Functional Tree
`Manipulation Language, Computer Languages, 19 (3): 157-168,
`1993.
`T. C. Miller and T. de Raadt, strlcpy and strlcat: Consistent, Safe,
`String Copy and Concatenation, In Proceedings of the USENIX
`Annual Technical Conference, Freenix Track, Jun. 1999.
`D. Moore, C. Shanning, and K. Claffy, Code-Red: a case study on the
`spread and victims of an Internet worm. In Proceedings of the 2nd
`Internet Measurement Workshop (IMW), pp. 273 -284, Nov. 2002.
`D. Moore, C. Shannon, G. Voelker, and S. Savage, Internet Quaran
`tine: Requirements for Containing Self-Propagating Code, In Pro
`ceedings of the IEEE Infocom Conference, Apr. 2003.
`C. Nachenberg, Computer Virus-Coevolution, Communications of
`the ACM, 50(1):46-51, 1997.
`D. Nojiri, J. Rowe, and K. Levitt, Cooperative Response Strategies
`for Large Scale Attack Mitigation, In Proceedings of the 3rd DARPA
`Information Survivability Conference and Exposition (DISCEX),
`pp. 293-302, Apr. 2003.
`D. S. Peterson, M. Bishop, and R. Pandey, A Flexible Containment
`Mechanism for Executing Untrusted Code, In Proceedings of the
`11th USENIX Security Symposium, pp. 207-225, Aug. 2002.
`M. Prasad and T. Chiueh, A Binary Rewriting Defense Against Stack
`based Buffer Over?ow Attacks, In Proceedings of the USENIX
`Annual Technical Conference, pp. 211-224, Jun. 2003.
`V. Prevelakis and D. Spinellis, Sandboxing Applications, In Proceed
`ings of the USENIX Technical Annual Conference, Freenix Track,
`pp. 119-126, Jun. 2001.
`N. Provos, M. Friedl, and P. Honeyman, Preventing Privilege Esca
`lation, In Proceedings of the 12th USENIX Security Symposium, pp.
`231-242, Aug. 2003.
`J. Reynolds, J. Just, E. Lawson, L. Clough, and R. Maglich, The
`Design and Implementation of an Intrusion Tolerant System, In Pro
`ceedings of the International Conference on Dependable Systems
`and Networks (DSN), Jun. 2002.
`M. Rosenblum, E. Bugnion, S. Devine, and S. A. Herrod, Using the
`SimOS Machine Simulator to Study Complex Computer Systems,
`Modeling and Computer Simulation, 7(1):78-103, 1997.
`
`2
`
`SYMC 1001
`
`

`

`US 8,074,115 B2
`Page 3
`
`R. Sekar, V. Venkatakrishnan, S. Basu, S. Bhatkar, and D. C.
`DuVaney, Model-Carrying Code: A Practice Approach for Safe
`Execution of Untrusted Applications, in Proceedings of ACM SOSP,
`Oct. 2003.
`N. Nethercote and J. Seward, Valgrind: A Framework for Heavy
`weight Dynamic Binary Instrumentation, PLDI ’07, Jun. 2007.
`J. F. Shoch and J. A. Hupp, The “worm” programs4early experi
`ments with a distributed computation, Communications of the ACM,
`22(3):172-180, Mar. 1982.
`Song, R. Malan, and R. Stone.,A Snapshot of Global Internet Worm
`Activity, Technical report, Arbor Networks, Nov. 2001.
`E. H. Spafford, The Internet Worm Program: An Analysis, Technical
`Report CSD-TR-823, Purdue University, 1988.
`S. Staniford, V. Paxson, and N. Weaver, How to Own the Internet in
`Your Spare Time, In Proceedings of the 11th USENIX Security
`Symposium, pp. 149-167, Aug. 2002.
`T. Toth and C. Kruegel, Connection-history Based Anomaly Detec
`tion, In Proceedings of the IEEE Workshop on Information Assur
`ance and Security, Jun. 2002.
`H. Toyoizumi and A. Kara, Predators: Good Will Mobile Codes
`Combat against Computer Viruses, In Proceedings of the New Secu
`rity Paradigms Workshop (NSPW), pp. 13-21, Sep. 2002.
`J. Twycross and M. M. Williamson, Implementing and testing a virus
`throttle, In Proceedings of the 12th USENIX Security Symposium,
`pp. 285-294, Aug. 2003.
`G. Venkitachalam and B.-H. Lim, Virtualizing i/o devices on vmware
`workstation’s hosted virtual machine monitor.
`C. Wang, J. C. Knight, and M. C. Elder, on Computer Viral Infection
`and the Effect of Immunization, In Proceedings of the 16th Annual
`Computer SecurityApplications Conference (ACSAC), pp. 246-256,
`2000.
`A. Whitaker, M. Shaw, and S. D. Gribble, Scale and Performance in
`the Denali Isolation Kernel, In Proceedings of the Fifth Symposium
`on Operating Systems Design and Implementation (OSDI), Dec.
`2002.
`J. Wilander and M. Kamkar, A Comparison of Publicly Available
`Tools for Dynamic Intrusion Prevention, In Proceedings of the Syrn
`posium on Network and Distributed Systems Security (SNDSS), pp.
`123-130, Feb. 2003.
`M. Williamson, ThrottlingViruses: Restricting Propagation to Defeat
`Malicious Mobile Code, Technical Report HPL-2002-172, HP Labo
`ratories Bristol, 2002.
`C. C. Zou, L. Gao, W. Gong, and D. Towsley, Monitoring and Early
`Warning for Internet Worms, In Proceedings of the 10th ACM Inter
`national Conference on Computer and Communications Security
`(CCS), pp. 190-199, Oct. 2003.
`C. C. Zou, W. Gong, and D. Towsley, Code Red Worm Propagation
`Modeling and Analysis, In Proceedings of the 9th ACM Conference
`on Computer and Communications Security (CCS), pp. 138-147,
`Nov. 2002.
`S. Hangal and M. Lam, Tracking Down Software Bugs Using Auto
`matic Anomaly Detection, ICSE ’02. May 19-25, 2002, pp. 291-301.
`P. Chan, M. Mahoney, andM. Arshad, A Machine Learning Approach
`to Anomaly Detection, Technical Report CS-2003 -06, Department of
`Computer Sciences, Florida Institute of Technology, Mar. 29, 2003.
`Interational Search Report and Written Opinion, International Appli
`cation No. PCT/US06/41591, dated Jun. 25, 2008.
`F. Apap, A. Honig, S. Hershkop, E. Eskin, and S. Stolfo, Detecting
`malicious software by monitoring anomalous windows registry
`accesses, Proceedings of the Fifth International Symposium on
`Recent Advances in Intrusion Detection (RAID 2002), 2002.
`D. Denning, An intrusion detection model, IEEE Transactions on
`Software Engineering, SE-13:222-232, Feb. 1987.
`E. Eskin, Anomaly detection over noisy data using learned probabil
`ity distributions, Proceedings of the Seventeenth International Con
`ference on Machine Learning (ICML-2000), 2000.
`S. Forrest, S. Hofmeyr, A. Somayaji, and T. Longstaff, A sense of self
`for unix processes, Proceedings of the IEEE Symposium on Research
`in Security and Privacy, pp. 120-128, 1996.
`N. Friedman andY. Singer, Ef?cient bayesian parameter estimation
`in large discrete domains, Advances in Neural Information Process
`ing Systems, 11, 1999.
`
`S. Hofmeyr, S. Forrest, and A. Somayaji, Intrusion detection using
`sequences of system calls, Journal ofComputer Security, 6: 151-180,
`1998.
`H. Javitz andA. Valdes, The nides statistical component: Description
`and justi?cation, Technical Report, SRI International, Computer Sci
`ence Laboratory, 1993.
`W. Lee, S. Stolfo, and P. Chan, Learning patterns from unix processes
`execution traces for intrusion detection, AAAI Workshop on AI
`Approaches to Fraud Detection and Risk Management, pp. 50-56,
`1997.
`W. Lee, S. Stolfo, and K. Mok, A data mining framework for building
`intrusion detection models, IEEE Symposium on Security and Pri
`vacy, pp. 120-132, 1999.
`W. Lee, S. Stolfo, and K. Mok, Data mining in work ?ow environ
`ments: Experiences in intrusion detection, Proceedings of the 1999
`Conference on Knowledge Discovery and Data Mining (KDD-99),
`1999.
`M. Mahoney and P. Chan, Detecting novel attacks by identifying
`anomalous network packet headers, Technical Report CS-2001-2,
`2001.
`B. Scholkopf, J. Platt, J. Shawe-Taylor, A. Smola, and R. Williamson,
`Estimating the support of a high dimensional distribution, Neural
`Computation, 13(7): 1443-1472, 2001.
`C. Warrender, S. Forrest, B. Pearlmutter, Detecting intrusions using
`system calls: Alternative data models, IEEE Symposium on Security
`and Privacy, pp. 133-145, 1999.
`A. Honig, A. Howard, E. Eskin, and S. Stolfo, Adaptive model gen
`eration: An architecture for the deployment of data mining-based
`intrusion detection systems, in Data Mining for Security Applica
`tions, Kluwer, 2002.
`S. White, Open problems in computer virus reseach, in Virus Bulletin
`Conference, 1998.
`CERT Advisory CA-2003-21: W32/Blaster Worm, http://wwwcert.
`org/advisories/CA-2003 -20.html, Aug. 2003.
`A. Baratloo, N. Singh, and T. Tsai, Transparent Run-Time Defense
`Against Stack Smashing Attacks, In Proceedings of the Annual Tech
`nical Conference, Jun. 2000.
`E. G. Barrantes, D. H. Ackley, S. Forrest, T. S. Palmer, D. Stefanovic,
`and D. D. Zovi, Randomized Instruction Set Emulation to Distrupt
`Binary Code Injection Attacks, in 10th ACM Conference on Com
`puter and Communications Security (CCS), Oct. 2003.
`D. Bruening, T. Garnett, and S. Amarasinghe, An Infrastructure for
`Adaptive Dynamic Optimization, In Proceedings of the International
`Symposium on Code Generation and Optimization, pp. 265-275,
`2003.
`G. Candea and A. Fox, Crash-Only Software, in Proceedings of the
`9th Workshop on Hot Topics in Operating Systems, May 2003.
`H. Chen and D. Wagner, MOPS: an Infrastructure for Examining
`Security Properties of Software, In Proceedings of the ACM Com
`puter and Communications Security (CC S) Conference, pp. 235 -244,
`Nov. 2002.
`S. A. Crosby and D. S. Wallach, Denial of Service via Algorithmic
`Complexity Attacks, In Proceedings of the 12th USENIX Security
`Symposium, pp. 29-44, Aug. 2003.
`B. Demsky and M. C. Rinard, Automatic Detection and Repair of
`Errors in Data Structures, In Proceedings of the 18th Annual ACM
`SIGPLAN Conference on Object Oriented Programming, Systems,
`Languages, and Applications, Oct. 2003.
`G. W. Dunlap, S. King, S. Cinar, M. A. Basrai, and P. M. Chen,
`ReVirt: Enabling Intrusion Analysis Through Virtual-Machine Log
`ging and Replay, In Proceedings of the Symposium on Operating
`Systems Design and Implementation (OSDI), Feb. 2002.
`C. Cowan et al., StackGuard: Automatic Adaptive Detection and
`Prevention of Buffer-Overow Attacks, In Proceedings of the 7th
`Security Symposium, Jan. 1998.
`T. Gar?nkel and M. Rosenblum, A Virtual Machine Introspection
`Based Architecture for Intrusion Detection, in 10th ISOC Sympo
`sium on Network and Distributed Systems Security (SNDSS), Feb.
`2003.
`T. Jim, G. Morrisett, D. Grossman, M. Hicks, J. Cheney, andY. Wang,
`Cyclone: A safe dialect of C, In Proceedings of the Annual Technical
`Conference, pp. 275-288, Jun. 2002.
`
`3
`
`SYMC 1001
`
`

`

`US 8,074,115 B2
`Page 4
`
`G. S. Kc, A. D. Keromytis, and V. Prevelakis, Countering Code
`Injection Attacks With Instruction-Set Randomization, in 10th ACM
`Conference on Computer and Communications Security (CCS), Oct.
`2003.
`S. T. King and P. M. Chen, Backtracking Intrusions, In 19th ACM
`Symposium on Operating Systems Principles (SOSP), Oct. 2003.
`S. T. King, G. Dunlap, and P. Chen, Operating System Support for
`Virtual Machines, In Proceedings of the Annual Technical Confer
`ence, Jun. 2003.
`V. Kiriansky, D. Bruening, and S. Amarasinghe, Secure Execution
`Via Program Shepherding, In Proceedings of the llth Security Syrn
`posium, Aug. 2002.
`D. Mosberger and T. Jin, httperf: A tool for measuring web server
`performance, In First Workshop on Internet Server Performance, pp.
`59-67, ACM, Jun. 1998.
`N. Nethercote and J. Seward, Valgrind: A Program Supervision
`Framework, In Electronic Notes in Theoretical Computer Science,
`vol. 89, 2003.
`J. Newsome and D. Dong, Dynamic Taint Analysis for Automatic
`Detection, Analysis, and Signature Generation of Exploits on Com
`modity Software, In The 12th Annual Network and Distributed Sys
`tem Security Symposium, Feb. 2005.
`J. Oplinger and M. S. Lam, Enhancing Software Reliability with
`Speculative Threads, In Proceedings of the 10th International Con
`ference on Architectural Support for Programming Languages and
`Operating Systems (ASPLOS X), Oct. 2002.
`N. Provos, Improving Host Security with System Call Policies, In
`Proceedings of the 12th USENIX Security Symposium, pp. 257-272,
`Aug. 2003.
`M. Rinard, C. Cadar, D. Dumitran, D. Roy, and T. Leu, A Dynamic
`Technique for Eliminating Buffer Overow Vulnerabilities (and Other
`Memory Errors), In Proceedings 20th Annual Computer Security
`Applications Conference (ACSAC), Dec. 2004.
`M. Rinard, C. Cadar, D. Dumitran, D. Roy, T. Leu, and J. W Beebee,
`Enhancing Server Availability and Security Through Failure-Oblivi
`ous Computing, In Proceedings 6th Symposium on Operating Sys
`tems Design and Implementation (OSDI), Dec. 2004.
`
`A. Rudys and D. S. Wallach, Transactional Rollback for Language
`Based Systems, In ISOC Symposium on Network and Distributed
`Systems Security (SNDSS), Feb. 2001.
`A. Rudys and D. S. Wallach, Termination in Language-based Sys
`tems, ACM Transactions on Information and System Security, 5(2),
`May 2002.
`S. Sidiroglou and A. D. Keromytis, A Network Worm Vaccine Archi
`tecture. In Proceedings of the IEEE Workshop on Enterprise Tech
`nologies: Infrastructure for Collaborative Enterprises (WET-ICE),
`Workshop on Enterprise Security, pp. 220-225, Jun. 2003.
`A. Smirnov and T. Chiueh, DIRA: Automatic Detection, Identica
`tion, and Repair of Control-Hij acking Attacks, In The 12th Annual
`Network and Distributed System Security Symposium, Feb. 2005.
`G. E. Suh, J. W. Lee, D. Zhang, and S. Devadas, Secure program
`execution via dynamic information ?ow tracking, SIGOPS Oper.
`Syst. Rev., 38(5):85-96, 2004.
`T. Toth and C. Kruegel, Accurate Buffer Over?ow Detection via
`Abstract Payload Execution, In Proceedings of the 5th Symposium
`on Recent Advances in Intrusion Detection (RAID), Oct. 2002.
`N. Wang, M. Fertig, and S. Patel, Y-Branches: When You Come to a
`Fork in the Road, Take It, In Proceedings of the 12th International
`Conference on Parallel Architectures and Compilation Techniques,
`Sep. 2003.
`J. Yin, J.-P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin,
`Separating Agreement from Execution for Byzantine Fault Tolerant
`Services, in Proceedings ofACM SOSP, Oct. 2003.
`A. AviZienis, The n-version approach to fault-tolerant software, IEEE
`Transactionson Software Engineering, ll (l2):l49l-l50l, 1985.
`S. Bhatkar, D. C. DuVarney, and R. Sekar, Address Obfuscation: an
`Efficient Approach to Combat a Broad Range of Memory Error
`Exploits, In Proceedings of the 12th Security Symposium, pp. 105
`120, Aug. 2003.
`S. Brilliant, J. C. Knight, and N. G. Leveson, Analysis ofFaults in an
`N-Version Software Experiment, IEEE Transactions on Software
`Engineering, 16(2), Feb. 1990.
`
`* cited by examiner
`
`4
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 1 of8
`
`US 8,074,115 B2
`
`SERVER
`
`110
`J
`
`106
`
`COMMUNICATIONS NETWORK
`(E.G., INTERNET, INTRANET,
`LAN, WAN, ETC.)
`
`102
`WORKSTATION J
`
`102
`WORKSTATION J
`
`102
`WORKSTATION 1
`
`FIG. 1
`
`5
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 2 618
`
`US 8,074,115 B2
`
`COMMUNICATIONS
`NETWORK
`
`1104
`
`106
`
`108
`
`WORKSTATION
`
`SERVER
`
`202
`f
`
`204
`r
`
`220
`f
`
`222
`/
`
`PROCESSOR
`
`DISPLAY
`
`PROCESSOR
`
`DISPLAY
`
`206
`f
`INPUT
`DEVICE
`
`208
`f
`
`MEMORY
`
`224
`f
`INPUT
`DEVICE
`
`226
`/
`
`MEMORY
`
`FIG. 2
`
`6
`
`SYMC 1001
`
`

`

`US Patent
`
`Dec. 6, 2011
`
`Sheet 3 0f 8
`
`US 8,074,115 B2
`
`300
`
`MONITORING AN APPLICATION FOR VARIOUS TYPES
`OF FAILURES USING ONE OR MORE SENSORS
`
`I
`
`PREDICTING THAT A FAULT MAY OCCUR OR
`DETECTING A FAULT THAT OCCURRED IN AT LEAST
`A PORTION OF THE APPLICATION’S CODE (E.G.,
`DETERMINING WHICH PORTIONS OF THE
`APPLICATION ARE VULNERABLE TO FAULTS
`AND/ OR ATTACKS)
`
`I
`
`UPON PREDICTING THAT A FAULT MAY OCCUR OR
`DETECTING THAT A FAULT OCCURRED, ISOLATING
`THE PORTION OF THE APPLICATION’S CODE HAVING
`THE FAULTY INSTRUCTION
`
`I
`
`GENERATING AN INSTRUMENTED VERSION OF THE
`PORTION OF THE APPLICATION’S CODE OR
`WRAPPING THAT PORTION OF THE APPLICATION’S
`CODE
`
`CONSTRUCTING AN EMULATOR-BASED VACCINE
`
`I
`I
`
`310
`
`/
`
`320
`
`330
`
`340
`
`350
`
`EMULATING SEGMENTS OF AN APPLICATION’S
`CODE WHERE THE FAULT OCCURRED USING THE
`EMULATOR-BASED VACCINE (E.G., TESTING WITH
`THE INPUTS SEENS BEFORE THE FAULT OCCURRED)
`
`360
`
`I
`
`IF THE FAULT OCCURS AGAIN, CAUSING THAT
`PORTION OF THE APPLICATION CODE TO RETURN
`WITH AN ERROR CODE, THEREBY SIMULATING A
`PROGRAMMED FAILURE
`
`370
`
`FIG. 3
`
`7
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 4 of8
`
`US 8,074,115 B2
`
`400
`
`DETECTING THAT A FAULT HAS OCCURRED (E.G.,
`ILLEGAL MEMORY DEREFERENCES, ETC.) THAT /
`CAUSES THE APPLICATION TO ABORT
`
`l
`
`420
`
`GENERATING A CORE DUMP AND GATHERING
`OTHER INFORMATION IN RESPONSE TO DETECTING j
`THAT THE FAULT HAS OCCURRED (E.G., TYPE OF
`FAILURE, STACK TRACE, ETC.)
`
`1
`
`ISOLATING A PORTION OF THE APPLICATION’S CODE j
`BASED AT LEAST IN PART ON THE CORE DUMP AND
`THE OTHER GATHERED INFORMATION, WHERE
`THAT PORTION OF THE APPLICATION CODE WILL BE
`EXECUTED UNDER EMULATION TO DETECT AND
`RECOVER FROM FUTURE INSTANCES OF THE FAULT
`
`FIG. 4
`
`8
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 5 of8
`
`US 8,074,115 B2
`
`500
`
`{
`"emici 5:31:11 E]
`int 51. = 1,;
`5*
`E-mtilatE-_init { f1‘
`emulatewbegin [jp_a:g5 ji
`a+~+gt
`emulatemerzdlj];
`emulate_:erm[]g
`prinzfi?a = ?arlzlkn“, E113
`
`,;
`
`FIG. 5
`
`9
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 6 of8
`
`US 8,074,115 B2
`
`600
`
`DIVIDING AN APPLICATION’S CODE INTO PORTIONS OF CODE
`
`l
`
`MONITORING THE PORTION OF CODE USING ONE OF THE
`PLURALITY OF DEVICES FOR VARIOUS TYPES OF FAILURES
`
`610
`
`620
`
`l
`
`PREDICTING THAT A FAULT
`630
`MAY OCCUR IN THE
`MONITORED PORTION OF CODE /
`(E.G., VULNERABLE TO FAULTS
`AND/OR ATTACKS)
`
`I
`
`640
`
`DETECTTNO THAT A
`FAULT HAS OCCURRED
`THAT CAUsEs THE
`APPLICATION TO
`ABORT OR OTHERWISE
`FAIL
`
`i
`
`l
`
`NOTIFYING THE OTHER DEVICES (E.G.,
`WORKSTATIONS, SERVERS, ETC.) OF THE FAULT;
`ALL DEVICES USE MONITOR AND RECOVERY ON
`THE IDENTIFIED-AS—VULNERABLE PORTION OF THE
`CODE, IN ALL INSTANCES OF THE APPLICATION
`
`650
`
`/
`
`i
`
`FIG. 6
`
`10
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 7 of8
`
`US 8,074,115 B2
`
`\‘
`
`fl.
`
`xi
`
`a()
`
`100
`
`b0
`
`200
`
`c()
`
`300
`
`rt.
`
`1
`
`2
`
`3
`
`vi
`
`(11
`
`(12
`
`(13
`
`T
`
`CW‘) rf‘vi
`
`600
`
`16
`
`(11
`
`600
`
`33
`
`2112
`
`600
`
`50
`
`3&3
`
`FIG. 7
`
`11
`
`SYMC 1001
`
`

`

`US. Patent
`
`Dec. 6, 2011
`
`Sheet 8 of8
`
`US 8,074,115 B2
`
`800
`
`802K
`
`Detect function
`call being made
`
`804 \ Comparc function
`call to model
`
`i
`
`806
`
`Identify function
`call as anomalous
`
`FIG. 8
`
`12
`
`SYMC 1001
`
`

`

`US 8,074,115 B2
`
`1
`METHODS, MEDIA AND SYSTEMS FOR
`DETECTING ANOMALOUS PROGRAM
`EXECUTIONS
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a US. National Phase Application
`Under 35 U.S.C. §37l of International PatentApplication No.
`PCT/US2006/04l59l, ?led Oct. 25, 2006, Which claims the
`bene?t under 35 U.S.C. §l 19(e) of United States Provisional
`Patent Application No. 60/730,289, ?led Oct. 25, 2005, each
`of Which is hereby incorporated by reference herein in its
`entirety.
`
`TECHNOLOGY AREA
`
`The disclosed subject matter relates to methods, media,
`and systems for detecting anomalous program executions.
`
`BACKGROUND
`
`Applications may terminate due to any number of threats,
`program errors, software faults, attacks, or any other suitable
`softWare failure. Computer viruses, Worms, trojans, hackers,
`key recovery attacks, malicious executables, probes, etc. are a
`constant menace to users of computers connected to public
`computer netWorks (such as the Internet) and/ or private net
`Works (such as corporate computer netWorks). In response to
`these threats, many computers are protected by antivirus soft
`Ware and ?reWalls. HoWever, these preventative measures are
`not alWays adequate. For example, many services must main
`tain a high availability When faced by remote attacks, high
`volume events (such as fast-spreading Worms like Slammer
`and Blaster), or simple application-level denial of service
`(DoS) attacks.
`Aside from these threats, applications generally contain
`errors during operation, Which typically result from program
`mer error. Regardless of Whether an application is attacked by
`one of the above-mentioned threats or contains errors during
`operation, these softWare faults and failures result in illegal
`memory access errors, division by Zero errors, buffer over
`?oWs attacks, etc. These errors cause an application to termi
`nate its execution or “crash.”
`
`SUMMARY
`
`Methods, media, and systems for detecting anomalous pro
`gram executions are provided. In some embodiments, meth
`ods for detecting anomalous program executions are pro
`vided, comprising: executing at least a part of a program in an
`emulator; comparing a function call made in the emulator to
`a model of function calls for the at least a part of the program;
`and identifying the function call as anomalous based on the
`comparison.
`In some embodiments, computer-readable media contain
`ing computer-executable instructions that, When executed by
`a processor, cause the processor to perform a method for
`detecting anomalous program executions are provide, the
`method comprising: executing at least a part of a program in
`an emulator; comparing a function call made in the emulator
`to a model of function calls for the at least a part of the
`program; and identifying the function call as anomalous
`based on the comparison.
`In some embodiments, systems for detecting anomalous
`program executions are provided, comprising: a digital pro
`cessing device that: executes at least a part of a program in an
`
`2
`emulator; compares a function call made in the emulator to a
`model of function calls for the at least a part of the program;
`and identi?es the function call as anomalous based on the
`comparison.
`In some embodiments, methods for detecting anomalous
`program executions are provided, comprising: modifying a
`program to include indicators of program-level function calls
`being made during execution of the program; comparing at
`least one of the indicators of program-level function calls
`made in the emulator to a model of function calls for the at
`least a part of the program; and identifying a function call
`corresponding to the at least one of the indicators as anoma
`lous based on the comparison.
`In some embodiments, computer-readable media contain
`ing computer-executable instructions that, When executed by
`a processor, cause the processor to perform a method for
`detecting anomalous program executions are provide, the
`method comprising: modifying a program to include indica
`tors of program-level function calls being made during execu
`tion of the program; comparing at least one of the indicators
`of program-level function calls made in the emulator to a
`model of function calls for the at least a part of the program;
`and identifying a function call corresponding to the at least
`one of the indicators as anomalous based on the comparison.
`In some embodiments, systems for detecting anomalous
`program executions are provided, comprising: a digital pro
`cessing device that: modi?es a program to include indicators
`of program-level function calls being made during execution
`of the program; compares at least one of the indicators of
`program-level function calls made in the emulator to a model
`of function c