Patent Document

CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims the benefit of U.S. provisional application 60/915,253 filed May 1, 2007 hereby incorporated by reference. 
     
    
       [0002]    This invention was made with United States government support awarded by the following agencies:
   NAVY/ONR N00014-01-1-0708   ARMY/SMDC W911NF-05-C-0102   
 
         [0005]    The United States has certain rights in this invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0006]    The present invention relates to computer programs and, in particular, to a computer program for detecting malicious computer programs (malware) such as computer viruses and the like. 
         [0007]    As computers become more interconnected, malicious computer programs have become an increasing problem. Such malicious programs include “viruses”, “worms”, “Trojan horses”, “backdoors”, “spyware”, and the like. Viruses are generally programs attached to other programs or documents to activate themselves within a host computer to self-replicate and attach to other programs or documents for further dissemination. Worms are programs that self-replicate to transmit themselves across a network. Trojan horses are programs that masquerade as useful programs but contain portions to attack the host computer or leak data. Backdoors are programs that open a computer system to external entities by subverting local security measures intended to prevent remote access or control over a network. Spyware are programs that transmit private user data to an external entity. These and similar programs will henceforth be termed “malware”. 
         [0008]    A common technique for detecting malware is to scan suspected programs for sequences of instructions or data that match “signature” sequences extracted from known malware types. When a match is found, the user is signaled that a malware program has been detected so that the malware may be disabled or removed. 
         [0009]    Many signature detection systems may be defeated by relatively simple code obfuscation techniques that changed the signature of the malware without changing the essential function of the malware code. Such techniques may include changing the static ordering of the instructions by using jump instructions (code transposition), substituting instructions of the signature with different synonym instructions providing the same function (synonym insertion), and the introduction of nonfunctional code (“dead code”) that does not modify the functionality of the malware. 
         [0010]    Co-pending U.S. patent application entitled: “Method And Apparatus To Detect Malicious Software”, assigned to the same assignee as the present invention, and hereby incorporated by reference, describes a preprocessor that can reverse some types of malware obfuscation by converting the malware program instructions into a standard form. A search of the de-obfuscated malware for malware signatures is then used to detect malicious code. Such a system employs three processes: a control flow graph (CFG) builder that reorders the instructions according to their control flow, a synonym dictionary that replaces functionally identical sets of instructions with standard equivalents and a dead code remover that removes irrelevant instructions (e.g. “nop” instructions). Irrelevant jump instructions, being unconditional jump instructions that simply jump to the next instruction in the control flow, may also be eliminated. 
         [0011]    Malware may be encrypted or compressed (packed), and may execute a decryption or unpacking program once the malware arrives in a host, to unpack or decrypt critical elements of the malware. The encryption or compression serves to hide features of the malware that might be detected by a malware signature detector, until the malware is being executed. A common and normally benign compression program may be used so that signature detection of the unpacking program of decryption program is impractically prone to false positive alerts. 
         [0012]    One approach for detecting packed or encrypted programs is to run the signature checker continuously to attempt to find the unpacked program in memory in an unpacked state. This can be impractical for systems where many programs must be monitored. 
       SUMMARY OF THE INVENTION 
       [0013]    The present invention provides a malware normalizer that may be part of a malware detection system that permits practical detection of encrypted and/or compressed malware programs. The detection of compressed or encrypted malware relies on an insight that a packed or encrypted program can be inferred by detection of a suspect program&#39;s execution of data previously written by the suspect program. 
         [0014]    The invention also provides for improved de-obfuscation of code reordering and dead code insertion. Improved code reordering is obtained by examining the control flow graph for nodes which have: (1) at least one preceding edge which is an unconditional jump and (2) no “fall-through” edge, as will be defined below. Improved removal of dead code eliminates or supplements a standard “synonym dictionary” with a piecewise analysis of code “hammocks” that produce no net change of external variables. 
         [0015]    Specifically then, the present invention may provide a malware normalization program that monitors memory locations written to during execution of a suspect program. Execution by the suspect program of the “written to” memory locations is used to trigger an analysis of the suspect program against malware signatures based on an assumption that any encrypted or compressed code is not decrypted or uncompressed. 
         [0016]    Thus it is one feature of at least one embodiment of the invention to provide a reliable and automatic method of signature detection for encrypted or compressed malware. 
         [0017]    The signature analysis may be limited to memory locations written to by the suspect program and within a loaded image of the suspect program. 
         [0018]    It is another feature of at least one embodiment to simplify the task of signature matching by minimizing the code that must be examined. 
         [0019]    The execution of the suspect program may be performed by a computer emulator limiting access by the suspect program to computer resources. 
         [0020]    It is another feature of at least one embodiment of the invention to prevent suspect programs from affecting the host computer prior to their analysis. 
         [0021]    The monitoring of execution of previously “written to” data may be repeated iteratively. 
         [0022]    It is another feature of at least one embodiment of the invention to provide a system that may automatically work with nested levels of packing or encryption. 
         [0023]    The invention may include a step of prescreening suspect programs according to an “entropy” of the loaded image suspect program, low entropy generally suggesting compression of a program. 
         [0024]    It is therefore a feature of at least one embodiment of the invention to provide a method of reducing the need for full analysis of all suspect programs. 
         [0025]    Alternatively or in addition, the invention may include the step of prescreening suspect programs through a static execution of the suspect program detecting an execution of previously “written to” addresses. 
         [0026]    It is thus a feature of at least one embodiment of the invention to allow the invention to be used to prescreen programs for possible self-generation. 
         [0027]    The invention may further provide a deobfuscation of the decrypted or uncompressed program to correct for instruction reordering before analyzing the program for malware signatures. 
         [0028]    It is thus another feature of at least one embodiment of the invention to provide a system that may work with deobfuscation techniques that address code reordering. 
         [0029]    The deobfuscation of code reordering may examine the execution order of the instructions and, when a given instruction has no fall-through edge and at least one preceding instruction that is an effective unconditional jump, replace the one effective unconditional jump with the given instruction. 
         [0030]    It is thus another feature of at least one embodiment of the invention to provide an improved method of correcting for code reordering obfuscation that may work with complex control flow graphs where multiple branches lead to a single instruction. 
         [0031]    The invention may further remove non-functional instructions before checking for malware signatures. In a preferred embodiment, the nonfunctional instructions are identified by finding “hammocks” of instructions within the execution order of the instructions, monitoring data written to during execution of the hammocks; and removing the instructions of the hammock as non-functional instructions when execution of the hammock does not change external data. 
         [0032]    It is another feature of at least one embodiment of the invention to provide a method of semantic “dead code” removal that unlike synonym techniques may work with novel obfuscation patterns that may not be in a synonym dictionary. 
         [0033]    These particular features and advantages may apply to only some embodiments falling within the claims and thus do not define the scope of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0034]      FIG. 1  is a block diagram of a malware normalization/detection system that may employ the present invention; 
           [0035]      FIG. 2  is a detailed block diagram of a normalizer of  FIG. 1  showing the steps of unpacking/decryption, reordering, and dead code removal; 
           [0036]      FIG. 3  is a representation of the loaded image of a suspect program showing its control flow and data flow; 
           [0037]      FIG. 4  is a flow chart of the principal steps used in the present invention in the unpacking/decryption block of  FIG. 2 ; 
           [0038]      FIG. 5  is a simplified flow chart of a suspect program showing standard instructions and control flow instructions; 
           [0039]      FIGS. 6   a  and  6   b  are examples of control flow graphs of the program of  FIG. 5  showing the steps of code reordering of  FIG. 2  per the present invention; 
           [0040]      FIG. 7  is a flow chart showing the principal steps used in the present invention in the code-reordering block of  FIG. 2  applied to the program of  FIG. 6 ; 
           [0041]      FIG. 8  is a control flow graph showing a hammock that may be analyzed per the present invention for dead code removal per  FIG. 2 ; and 
           [0042]      FIG. 9  is a flow chart of the principal steps used in the present invention in the dead code removal process block of  FIG. 2  applied to the program of  FIG. 8 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0043]    Referring now to  FIG. 1 , a computer system  10 , which may be, for example, a general purpose computer or a network intrusion detection system (an IDS), may receive executable files  12  from a network  14 , such as the Internet, or from a storage device  16  such as a hard drive of the computer system  10 . The executable files  12  may be programs directly executable under the operating system of the computer system  10  (e.g., “exe” or “bin”) files or may be “scripts” or so-called “application macros” executed by another application program. 
         [0044]    The received executable files  12  may be received by a scanner program  18  incorporating a malware normalizer  20  of the present invention which normalizes the code of the executable files  12  and then provides it to a signature detector program  22  that compares the normalized executable files  12  to a set of standard, previously prepared, malware signatures  24 . 
         [0045]    Referring now to  FIG. 2  the malware normalizer  20  of the present invention may provide for a prescreening block  26  which makes an optional predetermination of whether the executable file  12  is likely to be malware or not. This pre-screening is accepting of a significant number of false positives and is intended only to provide improved throughput to the malware normalizer  20  and the signature detector program  22  by eliminating the need to analyze programs that are unlikely to be malicious. 
         [0046]    Depending on the determination by the prescreening block  26  the executable file may be passed along to an unpacking program  28  or bypassed, as indicated by bypass path  30 , without unpacking to the reordering program  31 . 
         [0047]    At the unpacking program  28 , as will be described further below, executable file  12  is allowed to unpack (decompress) or decrypt itself (if the executable file  12  is packed or encrypted). As used henceforth the terms “pack” and “unpacking” shall be considered to refer also to “encrypt” and “decrypt” and similar functions performed by self-generating code, for example, including optimization, that generally alter the signature of the executable file  12 . The unpacking process of unpacking program  28  may be repeated iteratively, as indicated by path  32 , so as to unpack executable files  12  that have been packed multiple times. The unpacking program  28  may produce a detection signal  33  when the detection of self-generating code is desired (as opposed to the detection of malware). 
         [0048]    At the moment the unpacking or decryption is complete, the unpacked executable file  12  is forwarded to a reordering program  31 . If the executable file  12  does not have packing it is passed directly to the reordering program  31  without modification. 
         [0049]    The reordering program  31  reorders the instructions of the executable file  12 , as received from the unpacking program  28  into a standard form, as will be described, and then passes the reordered executable file  12  to the dead code remover program  34 . The dead code remover program  34  removes “semantic nops” being nonfunctional code (not necessarily limited to nop instructions) to provide as an output a normalized executable file  12  that is passed to the signature detector program  22  for comparison to normalized malware signatures  24 . 
         [0050]    Referring still to  FIG. 2 , the prescreening block  26  is intended to provide a rough determination of whether the executable file  12  has been packed or encrypted. To the extent that packing programs look for repeating patterns that may be abstracted and expressed more simply (for example long runs of zeros) a compressed program will have a greater entropy or randomness. Thus the prescreening block  26  in one embodiment may compare the entropy of the executable file  12  against a threshold for the determination of likelihood that the executable file  12  is compressed. The threshold is set high enough that nearly all compressed executable files  12  are passed to the unpacking program  28  even at the risk of including some uncompressed executable files  12 . Other methods of prescreening can also be employed including those that consider the source of the file or that look for signatures of common unpacking programs and the like. 
         [0051]    Referring now to  FIGS. 2 ,  3  and  4 , the unpacking program  28  receives the executable files  12  suspected of being packed and loads the file into memory  40  to be controllably executed, for example, by an emulator or in a “sandbox” environment as indicated by process block  36 . The emulator or sandbox allows the monitoring “reads” and “writes” to memory by the executable file  12  with the ability to block the writing of data outside of the sandbox and the ability to freeze the execution of the executable file during the monitoring process based on memory reads and writes. 
         [0052]    As shown in  FIG. 3 , a loaded image  42  of the executable file  12 , including program instructions and data, will be bounded by a logical starting address  44  and an ending address  45  and will begin execution at a start instruction  46  moving throughout the instructions of the executable file  12  as indicated by control flow  48 . During execution, data writes  50  may occur both to external data locations  52  for example to “external” memory addresses outside of the loaded image, for example the “heap” or the stack of the computer system  10 , or to “internal” memory addresses within the loaded image  42 . These internal memory addresses will be tracked per process block  58  of the unpacking program  28  to determine an unpack area  56 . 
         [0053]    At some point in the execution of the executable file  12 , if the executable file  12  is packed, an unpacker program  54  in the executable file  12  will be invoked performing writes  50  to internal memory addresses of code that is being unpacked. These memory addresses are also tracked per process block  58  of the unpacking program  28  to further define the unpack area  56  which will grow, logically bounded by a first instruction  60  and a last instructions  62  although unpack area  56  need not be absolutely continuous within that range. 
         [0054]    At decision block  64  of the unpacking program  28 , occurring during the execution of each instruction of the executable file  12 , the unpacking program  28  checks to see if there has been a jump in the control flow  48  to the unpack area  56  indicating that previously written data is now being executed as instructed. This jump is assumed to signal the conclusion of the unpacking process and the beginning of execution of the malware. At this time, a signal  33  is produced indicating that compression was detected. 
         [0055]    At iteration block  66 , the unpacking program  28  checks to see if the executable file  12  has concluded execution such as may be detected by movement of the control flow  48  out of the loaded image  42  or by a steady state looping such as may be detected, for example, by analyzing a fixed number of executed instructions. So long as the executable file  12  appears to be continuing execution, the iteration block  64  repeats process blocks  36 ,  58 , and  64  creating a new unpack area  56  within the loaded image and monitoring the control flow  48  for a jump into the new unpack area  56 . This process is continued to accommodate possible multiple packing operations. 
         [0056]    At the conclusion all the iteration, as indicated by process block  68  of the unpacking program  28 , the unpacked code, being for example the unpack area  56  of the final iteration or the union of all unpack areas  56  of all iterations, is sent to the reordering program  31 . 
         [0057]    Referring now to  FIGS. 5 ,  6   a,    6   b,  and  7 , the reordering program  31  builds a control flow graph of the executable file  12  (as possibly unpacked) using for example a disassembler (to recover the source code from the object code of the executable file  12 ) combined with a control flow graph builder. Disassemblers for this purpose are well known in the art and may, for example, include the IDAPro™ interactive disassembler commercially available from DataRescue of Liege, Belgium (www.datarescue.com). The execution ordered control flow graph may be produced using CodeSurfer™ by GrammaTech, Inc. of Ithaca, N.Y. (www.grammatech.com). 
         [0058]    Referring specifically to  FIG. 5 , an executable file  12  received from the unpacking program  28  may, for example, include an instruction  70  (A) followed by a conditional branch instruction  72  (B) followed by an arbitrary instruction  74  (C) followed by an unconditional jump instruction  75  (D) and an arbitrary instruction  76  (E). Instruction  72  and  75  are a control flow instructions, that is, they direct the control flow of the executable file  12 , while the remaining instructions are non-control flow instructions. 
         [0059]    As shown in  FIG. 6   a  each of these instructions  70 - 76  may represent a node in a control flow graph with control flow paths between them representing edges in a control flow graph. The edge  78  connecting instructions  70  and  72  will be termed a “fall-through edge” being any edge linking a non-control flow instruction with its unique control flow successor. The edge  80  connecting instructions  72  and  74  will also be termed a “fall-through edge” because it represents the false path of the conditional control flow instruction. 
         [0060]    The edge  82  connecting instructions  72  and  76  is a conditional jump instruction and the edge  84  connecting instructions  72  and  76  is an unconditional jump instruction. 
         [0061]    Per  FIG. 7 , and as shown by process block  90 , the reordering program  31  of  FIG. 2  tests each node of the control flow graph of  FIG. 6   a  to see that each node with at least one unconditional jump edge also has exactly one fall-through edge per decision block  92 . In this example, node  76  receives an unconditional jump edge  84  and when the test is applied to node  76  it is apparent that node  76  does not have a fall-through edge. 
         [0062]    In this case, and as shown by process block  94 , the executable file  12  is edited by the reordering program  31  to remove the unconditional jump instruction  75  and replace it with its target  76  as shown in  FIG. 6   b.    
         [0063]    When there is more than one unconditional jump predecessor for a given node (and that node has no fall-through edges) an arbitrary unconditional jump instruction may be eliminated. In a preferred embodiment, the unconditional jump instruction that is eliminated is the last unconditional jump predecessor in the order of the control flow graph. In a more sophisticated embodiment, conditional jump instructions that always jump are detected and treated as unconditional jump instructions. 
         [0064]    Referring now to  FIGS. 2 ,  8  and  9 , after code reordering per the reordering program  31 , the program is received by a dead code remover program  34 . Unlike conventional dead code removal tools that collect lists of non-functional code, for example, strings all of nop instructions, or successive incrementing and decrementing of a variable, and their functional synonyms in a predefined table, the present invention employs a semantic analysis approach that may detect nonfunctional code that has not previously been observed and catalogued. 
         [0065]    Referring to  FIG. 9 , at a first step of this process indicated by process block  96 , the dead code remover program  34  searches for “hammocks” in the executable files  12 . Hammocks are sections of the control flow graph having a single entry node and a single exit node, that is, there are no nodes between the entry and exit node that are connected by edges to nodes outside the hammock. For example, as shown in  FIG. 8 , hammock  98  may be identified by its single entry node  100  and single exit node  102 . 
         [0066]    Generally hammocks will occur with structured “if”, “while”, and “repeat” statements but may also occur in other contexts. 
         [0067]    Per process block  104  of the dead code remover program  34 , the execution of the instructions within the hammock  98  (for example using the emulator or sandbox described above) is monitored keeping track of each write  106  performed by an instruction in the hammock  98 , for example, by enrolling those written values and their addresses in a buffer table  108  to be refreshed at each hammock  98 . If a given address receives a multiple write, the last written value is the one held in the table  108 . The table  108  also preserves the original values  112  for each of the written values  110 . 
         [0068]    This population of the table  108  may also be performed by a static analysis of the instructions of the hammock  98 . 
         [0069]    At the conclusion of the execution of the hammock  98 , that is when the hammock  98  is exited from at node  102 , per process block  107 , the original values  112  and written values  110  are compared. If they are identical, then the hammock represents nonfunctional or dead code insofar as there has been no net change in any variable. 
         [0070]    Referring again to  FIG. 2  upon completion of the operation of the dead code remover program  34 , the resulting processed and normalized executable file  12  is forwarded to the signature detector program  22  as seen in  FIG. 1 . In this case it is important that the signatures  24  also be of normalized malware executable files. 
         [0071]    It is specifically intended that the present invention not be limited to the embodiments and illustrations contained herein, but include modified forms of those embodiments including portions of the embodiments and combinations of elements of different embodiments as come within the scope of the following claims.

Technology Category: g