US 8,549,647 B1Grant

Classifying portable executable files as malware or whiteware

Issue Date:2013-10-01

•24 Claims

•8 Drawing Sheets

Abstract

An improved approach for classifying portable executable files as malicious (malware) or benign (whiteware) is disclosed. The invention classifies portable executable files as malware or whiteware after using Bayes Theorem to evaluate each observable feature of each file with respect to other observable features of the same portable executable file with reference to statistical information gathered from repositories of known whiteware and malware files.

Metadata

Assignee

The United States of America as represented by the Secretary of the Air Force

Inventors

Mark Mason
Ming-Shih Wong
Jeff Rhines
Josh Mitchell

Application Information

Application Number:US 13/007,265

Filing Date:2011-01-14

Priority Date:2011-01-14

Art Unit:2432

Classifications

IPC:

G06F21/00

Patent Drawings (8 sheets)

Description

Rights of the Government

[0001] The invention described herein may be manufactured and used by or for the Government of the United States for all governmental purposes without the payment of any royalty.

Background of the Invention

[0002] The present invention relates to categorizing portable executable files as malicious (malware) or benign (whiteware), and more particularly to the use of Bayesian statistical methods to classify such portable executable files.

[0003] In response to the demand for convenient communication and data exchange, the number of personal computers and the frequency of internet usage have increased steadily. Unfortunately, this growth has also increased the surface area exposed to sponsored and unsponsored hackers seeking to exploit vulnerabilities known to exist in applications and operating systems.

[0004] Normally, the motivation for exploitation is persistent access to—and control of—a personal computer by implanting and hiding malicious software, known as malware. Once this is accomplished, the malware is typically programmed to propagate throughout the sub-network which connects the initially infected computer to others. At any stage in this process, the malware almost always performs malicious actions such as accepting commands, instructing computers to carry out various tasks such as returning lists to enumerate processes, files, services, registry keys, etc. Other tasks include modifying, deleting, and sending files to the controller at the remote address. There are many such functions performed by malware. A typical modern malware sample is replete with enough functionality to accomplish almost any task normally associated with the job duties of a professional network administrator.

[0005] The networks of government organizations and large companies are vast. Such networks are comprised of an extremely large number of computers, running thousands of software packages. As time goes on and needs evolve, more and more software is introduced across hosts in the network. The surface area of exposure in the collective network increases in a controlled and easily measurable way in proportion to the number of servers added that host services and web sites accessible to users in numerous sub-nets. However, the surface area grows unpredictably in proportion to the number of individual computer users on the network, given their tendencies to respond to suspicious emails, their ill-advised use of the internet, and their decisions to download or install files and software from unscreened, questionable websites. Regardless of whether it is a planned, calculated risk or through the wide variance in human activity, the surface area of exposure to cyber threats is an increasing value, making it a harsh fact of life that malware finds its way onto even the most carefully protected networks.

[0006] Despite the pervasiveness of malware, vast controlled networks are also useful as they collectively constitute a very well controlled and precisely defined baseline. Taken together, the files across operating systems form a “whiteware” repository, providing enough files to generate very strong statistics for hundreds of properties associated with files of interest. These properties are called observables. Equally strong statistics may be computed from readily accessible malware repositories existing in both the public and the private domains.

[0007] The portable executable format is a file format for executables, object code and Dynamic Link Libraries (DLLs), used in both 32- and 64-bit versions of Windows operating systems. The portable executable format is a data structure encapsulating the information necessary for a Windows OS loader to manage the wrapped executable code. The Windows loader looks up the information in the portable executable file and then decides how the file is to be mapped into memory. The mapping is consistent in such a way that higher offsets in a file correspond to higher memory addresses when mapped into memory. The offset of an item in the disk file may differ from its offset once loaded into memory. However, all the information is present for translation from disk offset to memory offset.

[0008] Because the majority of computers are Windows based, most malware targets Windows Operating Systems. Although malware must adhere somewhat to the portable executable format, malware samples in the wild are frequently found to contain anomalies in fields and code/data buffers. These portable executable aberrations can be used to classify portable executable files as malware or whiteware.

[0009] Traditionally, a primary method which aims to identify malware is signature based malware scanners. Signature based scanners rely on the “signatures” (unique features or data strings) of known malware so that future examples of the same malware can be correctly classified. However, such detectors face a scaling problem in the form of signature proliferation, given the millions of malware variants. Consequently, signature-based detectors necessarily operate with high-maintenance databases requiring updates on a regular basis. These databases are normally extremely bloated, even when signatures are aged out. Moreover, signature-based detectors miss almost all malware files which are not already included in the signature base. This means that almost all malware will evade a signature based scanner on the day they are released.

[0010] As just described, a very serious problem with signature-based detectors is that they are inherently almost always out-of-date for new malware threats, and always out-of-date for so-called zero day malware threats. This is generally not a serious problem for individuals and commercial enterprises, as it usually takes time for new malware threats to propagate throughout the Internet. Many organizations, however, such as the military, are often specifically targeted and subject to zero day attacks. They require identifying malware before a specific malware threat has been identified, a signature determined, the signature added to a malware signature database and the new database propagated to computers across the Internet.

[0011] Accordingly, there exists a need for an approach devoid of signatures. One prior art method which aims to identify malware is anomaly detectors. Anomaly detectors are built from statistics based on observables belonging only to a repository of whiteware portable executable files. Anomaly detectors use the statistics from whiteware files in an attempt to identify malware by differences between the malware observables and whiteware statistics. However, when statistics are generated from a repository of uncontaminated whiteware, without any reference to malware, the approach has a high failure rate because there is too much overlap between properties and behaviors of whiteware and malware files.

[0012] As such, there exists a need for an approach that uses whiteware statistics like an anomaly detector, but factors in malware statistics as well. Unfortunately, prior art attempts have fallen short in quickly and accurately classifying files using statistical methods. Most prior art is limited by the tradeoff between speed of evaluation and accuracy of results. Some methods sacrifice accuracy for the sake of speed by evaluating only a few portable executable observables, thus having high false positive or negative rates. Other methods sacrifice speed for the sake of accuracy by evaluating many portable executable observables, but causing the evaluation of each file to take a substantial amount of time.

[0013] Additionally, while prior art has employed statistical methods based on Bayes Theorem, prior art employs only simple Naïve Bayes calculations or Multi-Naïve Bayes calculations. These calculations employed by prior art consider each portable executable observable separately from each other portable executable observable and assume that each observable is independent of all other observables. The Naïve Bayes implementation results in the loss of data which could be used if the true dependent relationship between observables and the full power of Bayes Theorem were harnessed. Accordingly, the Naïve Bayes and Multi-Naïve Bayes approach result in less accurate results.

[0014] Accordingly, there exists a need for a portable executable file classification method and apparatus based on a fully-functional Bayesian Inference Engine which employs statistics based on both malware and whiteware observables and does not use signatures as a method of classifying files.

Summary of the Invention

[0015] The present invention solves these problems by, unlike prior art naïve Bayesian approaches that assume every feature is independent from every other feature, taking advantage of that each iteration of a Bayesian analysis on a PE file observable feature provides an improved initial probability assumption for the next sequential iteration so that, among other advantages, the probability of a PE file being either malware or whiteware can converge to a threshold value, usually quickly, providing much faster determinations with less computational overhead, particularly when scanning a large number of files.

[0016] The present invention also adds a significant improvement to this approach by selecting each next observable to be processed by which possible next observable is most closely correlated with the change in probability of the preceding step, providing even faster convergence and less computation overhead.

[0017] The present invention considers a large number of observable features of portable executable files without the necessity of executing any of the instructions within the portable executable files.

[0018] The invention disclosed applies a static, statistical approach combining both whiteware and malware statistics to form a baseline composed of conditional probability tables. When the invention runs live in detection mode, it loads a portable executable file into memory and computes values for observable features of the file, a sequence of observations. Each observable value is used to look-up counterparts in the malware and whiteware conditional probability tables. The conditional probabilities for a given observable along with the current value which represents the belief about the true nature of the file is then passed to a Bayesian Inference Engine. The engine, in turn, internally invokes Bayes Theorem to update the belief about the true nature of the file and pass that value back to the program. After this process is complete for all observables or the probability regarding the files true nature converges on 0 or 1, adjudication is complete and the file is classified as malware or whiteware dependent on the probability value reached after all iterations of the Bayesian Inference Engine.

[0019] According to one example embodiment, an iterative approach is used where Bayes Theorem is invoked once for each observable. In each iteration, the belief the file is malware, P(M), is updated with the result of Bayes Theorem with respect to the instant observable, P(M|O), such that P(M) is set to equal P(M|O) after each iteration. In this way, the result of each iteration is dependent on the results of all prior iterations.

[0020] In another example embodiment, the invention evaluates numerous observables. Some observables are skewed toward malware properties (anomalies), while others are skewed toward whiteware properties (standard forms). In one embodiment, the observables are divided into three types and assigned discrete numeric values. Boolean types are assigned a value of 0 or 1, integer types are assigned an integer value, and range types are assigned a numeric value within a given range.

[0021] In yet another example embodiment, the observables are processed in a predetermined set order with observables likely to have the largest determinative effect processed first and less determinative observables processed later.

[0022] In a further example embodiment, the observables are processed according to a correlation table where each subsequent observable is determined by reference to the change in the probability value assigned to the file as a result of the previous observable. This method addresses the dependence of Bayesian final belief or probability on the order in which observables are processed. The single end effect of the technique is to generate observable orderings that simultaneously minimize false negative and false positive rates, thereby maximizing accuracy.

Brief Description of the Drawings

[0023] FIG. 1 is a flowchart detailing the method for evaluating and classifying portable executable files.

[0024] FIG. 2 illustrates sample instructions for iterative use of Bayes Theorem to evaluate and classify portable executable files.

[0025] FIG. 3 is a process plot which illustrates how the Bayesian Inference Engine iterates to a final belief for a malware sample.

[0026] FIG. 4 is an actual screenshot of the present invention's graphical user interface before any files have been evaluated.

[0027] FIG. 5 is an actual screenshot of the present invention's graphical user interface after all selected files have been evaluated.

[0028] FIG. 6 is a flowchart detailing the method for determining which observable to process after an increase in malware belief.

[0029] FIG. 7 is a flowchart detailing the method for determining which observable to process after malware belief does not increase.

Detailed Description

[0030] The invention classifies portable executable files as malware or whiteware after using Bayes Theorem to evaluate each observable feature of each portable executable file with respect to other observable features of the same portable executable file with reference to statistical information gathered from repositories of known whiteware and malware files.

[0031] The invention utilizes Bayesian inference to classify portable executable files. Bayesian Inference is an effect-to-cause method of reasoning over statistics. The base variable is a statistical quantity termed the observable. In the Bayesian context, the observable is a physically measured effect, E. Once in hand, it is then used to update and refine beliefs in one or more possible causes for it. This is stated in the mathematical relation below as Bayes Theorem wherein C is a possible cause for the effect, E; P(C) is the prior probability of cause, C being the cause for the effect, E; P(E|C) is the probability of measuring effect, E conditioned on cause, C being true; P(E) is the marginal probability of effect, E; and P(C|E) is the posterior probability of cause, C after the effect, E is measured.

[0032]

P (C ❘ E) = \frac{P (E | C) P (C)}{P (E)}

[0033] In the application of Bayes Theorem utilized by the invention, the effect, E, maps into the portable executable observable, O: E→O. Additionally, the enumeration for the possible cause, C is: Cε{M,W}, where M≡Malware and W≡Whiteware. With these assignments, Bayes Theorem is recast in colloquial terms:

[0034]

P (M | O) = \frac{P (O | M) P (M)}{P (O)}

[0035] Because a file is either whiteware or malware, but never both, the probability that file is whiteware, P(W) can be expressed as P(W)=1−P(M).

[0036] To assure that malware and whiteware conditional probabilities are treated equally and the complementary relationship 1=P(M|O)+P(W|O) is maintained, the special form of Bayes Theorem is used such that

[0037]

P (M | O) = \frac{1}{1 + \frac{P (O | W)}{P (O | M)} \frac{(1 - P (M))}{P (M)}}

[0038] The flowchart shown in FIG. 1 illustrates the process for evaluating each portable executable file. In this example embodiment, the first action is to initialize the malware probability, P(M), to a value of 0.5 10. Since belief equates with probability, this is equivalent to expressing complete neutrality concerning the true disposition of the file before the first iteration begins.

[0039] After initialization, the first observable is accessed 20. Those skilled in the art will recognize that observables can be accessed one at a time as needed or all at the same time. Many different tools are available to access observables in portable executable files such as the Python module, pefile, which provides access to fields and data or code buffers within a portable executable file through the member classes and structures it initializes.

[0040] In this example embodiment of the invention, a numeric value is computed for the first observable 30. The numeric value can be computed in a variety of ways depending on the observable type. In one example embodiment, three observable types are used: Boolean, count and interval.

[0041] Boolean type observables are returned as a value of 1 or 0 depending on whether the observable is present or not present respectively. For example, one observable may be whether or not a portable executable file has a valid security certificate. Files where the certificate is present and valid would be assigned a value of 1 for the observable and those where it was not present or not valid would be assigned a value of 0.

[0042] Count type observables are assigned an integer value depending on the specific number of specified features observed. For example, one observable may be how many sections are contained within the portable executable file. The invention would access the observable, compute the number of sections and return an integer value for the observable.

[0043] Interval type observables are assigned any real number in a predetermined interval. A practitioner skilled in the art could compute an interval type observable by evaluating several sub-observables using an equation. Interval type observables could also be features such as the size of the portable executable file.

[0044] After a value is computed for the observable, the process obtains the malware conditional probability 40 by querying a database of probabilities for the various observables in known malware files 50 which returns the value for the malware conditional probability with respect to the instant observable, P(O|M) 60. In some embodiments, calculations are performed after querying the database of probabilities to compute values for observables which are dependent on values of other observables.

[0045] The process next obtains the whiteware conditional probability 70 by querying a database of probabilities for the various observables in known whiteware files 80 which returns the value for the whiteware conditional probability with respect to the instant observable, P(O|W) 90. In some embodiments, calculations are performed after querying the database of probabilities to compute values for observables which are dependent on values of other observables.

[0046] Those skilled in the art will recognize that the database of probabilities as well as information on observable types can be configured to receive external updates. Accordingly, the disclosed process could maintain accuracy over time despite the changing nature of malware and whiteware files by receiving updated statistical information and observables from a remote source where new statistical data and observables were determined.

[0047] After the malware 40 and whiteware 70 conditional probabilities are obtained, the process invokes Bayes Theorem to update the malware belief 100. To do this, the process passes the values for malware probability, P(M), malware conditional probability, P(O|M), and whiteware conditional probability, P(O|W) 110 to a function 120 which utilizes the special form of Bayes Theorem disclosed above to return an updated value for malware probability given the instant observable, P(M|O) 130.

[0048] In this example embodiment, the updated value for the malware probability is evaluated with regard to a convergence value, ε, after each observable is processed 140 and 150. Generally ε has a very small value such as 0.01. Where P(M|O) is less than ε 140, the process sets P(M)_Finalequal to the value for P(M|O) 190 and reports the value for P(M)_Finaland that the file is whiteware 210. Where P(M|O) is greater than 1−ε 150, the process sets P(M)_Finalequal to the value for P(M|O) 190 and reports the value for P(M)_Finaland that the file is malware 220. If P(M|O) is not less than ε 140 or greater than 1−ε 150, the process determines whether there are additional observables remaining to evaluate 160. If there are additional observables, the malware probability, P(M), is reset to the value returned by Bayes theorem with respect to the prior observable such that P(M)=P(M|O) 170. Thereafter, the next observable is accessed 180 and the process begins again at step 30.

[0049] The above described process repeats until either the malware probability converges with respect to the convergence value, E, at step 140 or step 150 or the last observable is processed 160. If all observables have been processed and the malware probability has not converged with respect to the convergence value, ε, then the process sets P(M)_Finalequal to the last value for P(M|O) 190 and final malware probability, P(M)_Final, is evaluated with respect to a threshold value, T 200. In one example embodiment, the threshold value is set to 0.7. If the final malware probability, P(M)_Final, is less than T, the process reports the value for P(M)_Finaland that the file is whiteware 210. Otherwise, the program reports the value for P(M)_Finaland that the file is malware 220.

[0050] FIG. 2 illustrates sample instructions for the described process. Starting with the first instruction, the prior malware belief is initialized: P(M)=0.5 230. After initialization, the algorithm executes the main loop 240. For each observable, the main loop cycles through the steps of solving Bayes Theorem 250 and resetting the prior belief 260. Each pass through the loop constitutes a single iteration. After each iteration, the value is tested against the convergence criteria with regard to the convergence value, ε 270. The main loop iterates until either convergence is reached in step 270 or the last observable is processed. Once the main loop has finished all iterations, the value for P(M)_Finalis set to the malware belief, P(M), reached during the final iteration of the main loop 280. P(M)_Finalis the probability that is assigned to the portable executable file and is used to determine the files ultimate classification as either malware or whiteware.

[0051] FIG. 3 is a process plot which illustrates how the Bayesian Inference Engine iterates to a final belief for a malware sample. The vertical axis of the plot 290 represents the malware belief, P(M), as it fluctuates within its range of 0 to 1 based on the analysis of the various observables. The horizontal axis of the plot 300 represents the observables analyzed by the invention. The first circle on the left of the plot 310 is set over the initialized malware belief of 0.5. The additional circles 320 indicate selected observables. For this plot, there were 32 observables in all and the main loop in the algorithm was executed 32 times. In FIG. 3, the final malware belief, P(M)_Final, is approximately equal to 0.98. The horizontal line crossing the plot at P(M)=0.7 is the threshold, T 330, such that any portable executable file satisfying the relation, P(M)_Final≧T is considered malware.

[0052] FIGS. 4 and 5 illustrate a graphical user interface (GUI) included in one example embodiment. The GUI includes buttons which allow a user to “Browse” 340 the computer file system to select a target directory of files to be evaluated which is displayed in a text box on the GUI once selected 350. Once the directory is chosen, the user can initiate execution of the process by clicking on the “Start Screening” button 360. As explained above, the final belief, P(M)_Finalis compared pared to a threshold, T, which determines the range of probabilities in which a file will be classified as malware or whiteware. The GUI allows a user to adjust the threshold to any value between 0 and 1 370.

[0053] As the invention runs, basic statistics for the collection of files are updated in the “Summary” pane 380. After all files have been processed, checkboxes and buttons associated with the “Export” pane 390 become functional. At this point, the user may select a subsequent action to perform on specified file types. The user may choose one or more lists to export. The list choices are all files 400, likely black files 410, likely white files 420, and failed files 430. “All files” 400 indicates all of the files which were part of the user-selected target directory for analysis. “Likely black files” 410 indicates the files which the invention classified as malware. “Likely white files” 420 indicates the files which the invention classified as whiteware. “Failed files” 430 indicates the files which the invention was not able to evaluate, whether because they were of the wrong type, were corrupt, or any other reason. Once a user selects a list or lists of files, the user may elect among three options. One option “Submit to UCATS” 440 allows the user to submit the selected lists of files to the external UCATS triage system for further testing. Another option, “Export as ZIP,” 450 allows the user to create a zip file of the files to save for further analysis. Finally, the user may select “Show Files,” 460 to display the files in the selected group or groups. The user may also elect to clear the results by clicking the “Clear” button 470, close the window by clicking the “Close” button 480, update the results by clicking the “Update” button 490, or access the programs help menu by clicking the “Help” button 500.

[0054] In one example embodiment of the invention, a correlation method is used to determine the order in which observables are processed. The effect of this method is to generate observable orderings that minimize false negative and false positive rates. The method navigates the disclosed Bayseian process through a given set of observables, processing them in an order that optimizes detection.

[0055] The observables most likely to identify a file as either malware or whiteware vary from file-to-file. This variance exists in both malware and whiteware samples. However, the observables likely to identify any given file as malware or whiteware are not generally independent. Some observables appear frequently with other specific observables and are positively correlated with those observables. Others observables are unlikely to appear together or mutually exclusive and are negatively correlated. Correlation coefficients can verify and quantify these relationships.

[0056] By using correlation to determine the order in which to process observables, the invention may sometimes classify a portable executable file after evaluating only a few observables because the observables associated with its distinguishing properties are evaluated first. Using correlation, the next observable to process may be determined according to the magnitude and sign of the correlation coefficients linking observables together. Thus, by using the change in malware probability after any given observable is processed to determine which observable to next process, the invention is further optimized.

[0057] The method to determine the order of observables based on correlation can be included as part of the process during each iteration before step 180 when the next observable is accessed.

[0058] To implement correlation information, the invention utilizes two basic variables. The first variable is the ratio of conditional probabilities between malware and whiteware for a given observable:
R(O_i)=P(O_i|M)÷P(O_i|W)

- [0059] O_i≡i^thObservable where i=1, 2, 3, . . . , N_O
- [0060] N_O≡Total Number of Observables

[0061] The second variable is the inter-observable correlation coefficient. There are two subtypes. The first subtype is the malware correlation coefficient between two observables, Oi and Oj:

[0062]

C^{M} (i, j) = \frac{1}{σ_{i} σ_{j}} \frac{1}{N_{F}^{M} - 1} \sum_{k = 1}^{N_{F}^{M}} (O_{i}^{M} (k) - {\overline{O}}_{i}^{M}) (O_{j}^{M} (k) - {\overline{O}}_{j}^{M})

[0063] Supporting variables appearing in the expression above include the malware average value for the ith Observable, Oi:

[0064]

{\overline{O}}_{i}^{M} = \frac{1}{N_{F}^{M}} \sum_{k = 1}^{N_{F}^{M}} O_{i}^{M} (k)

N_{F}^{M} \equiv Numbered of Malware Files

O_{i}^{M} (k) \equiv Value for Observable O_{i} Measured

in k^{th} Malware File

[0065] Also appearing in the expression is the malware standard deviation for the ith Observable, Oi:

[0066]

σ_{i}^{M} = \sqrt{\frac{1}{N_{F}^{M} - 1} \sum_{k = 1}^{N_{F}^{M}} {(O_{i}^{M} (k) - {\overline{O}}_{i}^{M})}^{2}}

[0067] The second subtype is the whiteware correlation coefficient between two observables, Oi and Oj:

[0068]

C^{W} (i, j) = \frac{1}{σ_{i} σ_{j}} \frac{1}{N_{F}^{W} - 1} \sum_{k = 1}^{N_{F}^{W}} (O_{i}^{W} (k) - {\overline{O}}_{i}^{W}) (O_{j}^{W} (k) - {\overline{O}}_{j}^{W})

[0069] Supporting variables appearing in the expression above include the whiteware average value for the ith Observable, Oi:

[0070]

{\overline{O}}_{i}^{W} = \frac{1}{N_{F}^{W}} \sum_{k = 1}^{N_{F}^{W}} O_{i}^{W} (k)

N_{F}^{W} \equiv Number of Whiteware Files

O_{i}^{W} (k) \equiv Value for Observable, O_{i} Measured

in k^{th} Whiteware Files

[0071] Also appearing in the expression is the whiteware standard deviation for the ith Observable, Oi:

[0072]

σ_{i}^{W} = \sqrt{\frac{1}{N_{F}^{W} - 1} \sum_{k = 1}^{N_{F}^{W}} {(O_{i}^{W} (k) - {\overline{O}}_{i}^{W})}^{2}}

[0073] Depending on the difference in belief measured after processing an observable, Oi, through Bayesian Inference Engine, one of two processes is executed. If the difference is positive, indicating an increase in malware belief, the branch in FIG. 6 is executed. Otherwise, the branch in FIG. 7 is executed.

[0074] FIG. 6 is a flowchart showing the method followed to determine which observable to process after an observable which has increased the malware probability P(M). In one example embodiment, the first action is to evaluate the ratio of conditional probabilities, P(Oi|M)÷P(Oi|W) for observable, Oi 600.

[0075] When the ratio generated in step 600 is greater than 1, the next observable to be evaluated is decided by comparing two observables determined by steps 610 and 620. The first observable, Op, is the observable which satisfies two conditions 610. The first condition demands its malware correlation coefficient, C^M(i,p), linking Oi to Op be the maximum. The second condition is that the ratio of conditional probabilities between malware and whiteware, P(Op|M)÷P(Op|W), exceeds 1.

[0076] The second observable, Oq, is the observable which satisfies two different conditions 620. The first condition demands its malware correlation coefficient, C^M(i,q), linking Oi to Oq be the minimum. The second condition is that the ratio of conditional probabilities between whiteware and malware, P(Oq|W)÷P(Oq|M), be at least 1.

[0077] The next step compares the absolute values of the correlation coefficients for the observables Op and Oq 630. If the absolute value of CM(i,p) is greater, then Op is selected as the next observable to process 640. Otherwise, Oq is selected as the next observable to process 650.

[0078] When the ratio generated in step 600 is not greater than 1, the next observable to be evaluated is decided by comparing two observables determined in steps 660 and 670. The first observable, Or, is found satisfying two conditions 660. The first condition demands its malware correlation coefficient, C^M(i,r), linking Oi to Or be the minimum. The second condition is that the ratio of conditional probabilities between malware and whiteware, P(Or|M)÷P(Or|W), exceeds 1.

[0079] The second observable, Os, is found which satisfies two different conditions 670. The first condition demands its malware correlation coefficient, C^M(i,s), linking Oi to Os be the maximum. The second condition demands its ratio of conditional probabilities between whiteware and malware, P(Os|W)÷P(Os|M), be at least 1.

[0080] The next step compares the absolute values of the correlation coefficients for the observables Or and Os 680. If the absolute value of CM(i,s) is greater, then Os is selected as the next observable to process 690. Otherwise, Or is selected as the next observable to process 700.

[0081] FIG. 7 is a flowchart indicating the method followed to determine which observable to process after an observable which has not increased the malware probability P(M). In one example embodiment, the first action is to evaluate the ratio of conditional probabilities, P(Oi|M)÷P(Oi|W) for observable, Oi 800.

[0082] When the ratio generated in step 800 is greater than 1, the next observable to be evaluated is decided by comparing two observables determined by steps 810 and 820. The first observable, Op, is the observable which satisfies two conditions 810. The first condition demands its whiteware correlation coefficient, C^W(i,p), linking Oi to Op be the maximum. The second condition demands its ratio of conditional probabilities between malware and whiteware, P(Op|M)÷P(Op|W), exceeds 1.

[0083] The second observable, Oq, is the observable which satisfies two different conditions 820. The first condition demands its whiteware correlation coefficient, CW(i,q), linking Oi to Oq be the minimum. The second condition is that the ratio of conditional probabilities between whiteware and malware, P(Oq|W)÷P(Oq|M), be at least 1.

[0084] The next step compares the absolute values of the correlation coefficients for the observables Op and Oq 830. If the absolute value of C^W(i,p) is greater, then Op is selected as the next observable to process 840. Otherwise, Oq is selected as the next observable to process 850.

[0085] When the ratio generated in step 800 is not greater than 1, the next observable to be evaluated is decided by comparing two observables determined in steps 860 and 870. The first observable, Or, is found satisfying two conditions 860. The first condition demands its whiteware correlation coefficient, C^W(i,s), linking Oi to Os be the maximum. The second condition is that the ratio of conditional probabilities between whiteware and malware, P(Os|W)÷P(Os|M), be at least 1.

[0086] The correlation coefficient, CW(i,s) is then compared against the absolute value of the correlation coefficient, CW(i,r) 880. If CW(i,s) is greater, then Os is selected as the next observable to process 890. Otherwise, Or is selected as the next observable to process 900.

[0087] The terminology used in this description is only for the purpose of describing particular embodiments. Unless the context clearly demonstrates otherwise, it is not intended to be limiting. In this specification and in the claims, the singular forms “a,” “an” and “the” include plural references unless the context clearly dictates otherwise. Conversely, the claims may be drafted to exclude any optional element or be further limited using exclusive terminology as “solely” “only” and the like in connection with the recitation of claim elements or by use of a “negative” limitation. Any optional feature of the inventive variations described herein may be set forth and claimed independently, or in combination with anyone or more of the described features.

[0088] Although the foregoing specific details describe various embodiments of the invention, persons reasonably skilled in the art will recognize that various changes may be made in the details of the apparatus of this invention without departing from the spirit and scope of the invention as defined in the appended claims. Therefore, unless otherwise specified, this invention is not limited to the specific details shown and described.

Claims

We claim:

1. A computer-implemented method for classifying a portable executable file, comprising:

(a) initializing a malware belief (P(M)) to a predetermined value;

(b) accessing, using one or more processors, an observable feature from the portable executable file;

(c) obtaining a malware conditional probability for the accessed observable feature from a database of predetermined probabilities for malware;

(d) obtaining a whiteware conditional probability for the accessed observable feature from a database of predetermined probabilities for whiteware;

(e) applying Bayes theorem to calculate a probability that the portable executable file is malware given the malware and whiteware conditional probabilities of the accessed observable feature;

(f) updating the malware belief (P(M)) with a result of Bayes theorem calculated with respect to the accessed observable feature;

(g) iterating steps (c) through (f) for any additional accessible observable features, whereby a final malware belief (P(M)Final) is returned;

(h) evaluating the final malware belief (P(M)Final) to classify the portable executable file as malware if the final malware belief (P(M)Final) is greater than or equal to a predetermined threshold value, or as whiteware if the final malware belief (P(M)Final) is less than the same predetermined threshold value; and

(i) where the malware belief (P(M)) is evaluated after each iteration and the process returns a value for the final malware belief (P(M)Final) and the portable executable file is classified as whiteware after any iteration where the malware belief (P(M)) is less than a predetermined convergence value and the process returns a value for the final malware belief (P(M)Final) and the portable executable file is classified as malware if the malware belief (P(M)) is greater than one minus the same predetermined convergence value and the final malware belief (P(M)Final) is evaluated with regard to the distinct predetermined threshold value only after all accessed observable features have been evaluated and the predetermined convergence value is never reached.

2. The method according to claim 1, where the initial malware belief (P(M)) is set to 0.5 in step (a).

3. The method according to claim 1, where the predetermined threshold value in step (h) is 0.7.

4. The method according to claim 1, where a change in malware belief (P(M)) is determined as the difference between a current and the immediately previous malware belief (P(M)), and where a next observable feature of the portable executable file to be evaluated is dependent on the change in malware belief (P(M)) as the result of evaluation of the previous observable feature.

5. The method according to claim 1, where a step for determining the next observable feature to be processed is included after step (f).

6. The method according to claim 5, where the next observable feature to be processed is determined by evaluating the change in malware belief (change in P(M)) as a result of the last observable feature processed and finding which of the remaining observable features to be processed are most closely correlated with the change in malware belief.

7. The method according to claim 1, where multiple portable executable files can be processed and all evaluated portable executable files can be listed by classification type.

8. The method according to claim 1, where the final malware belief (P(M)Final) is returned after all accessed observable features have been evaluated.

9. A computer-implemented method for classifying a portable executable file, comprising:

(a) initializing a malware belief (P(M)) to a predetermined value;

(b) accessing, using one or more processors, at least one observable features from the portable executable file;

(c) obtaining a malware conditional probability of a first observable feature from a database of predetermined probabilities for malware;

(d) obtaining a whiteware conditional probability for the first observable feature from a database of predetermined probabilities for whiteware;

(e) applying Bayes theorem to calculate a probability that the portable executable file is malware given the malware and whiteware conditional probabilities of the first observable feature;

(f) updating the malware belief (P(M)) with a result of Bayes theorem calculated with respect to the first observable feature;

(g) iterating steps (c) through (f) for additional observable features until a final malware belief (P(M)Final) is returned;

10. The method according to claim 9, where the predetermined convergence value is 0.01.

11. The method according to claim 9, where the predetermined threshold value is 0.7.

12. A computer-implemented method for classifying a portable executable file, comprising:

(a) initializing a malware belief (P(M)) to a predetermined value;

(b) accessing, using one or more processors, an observable feature from the portable executable file;

(c) performing calculations with respect to the accessed observable feature such that the accessed observable feature is assigned a discrete numeric value;

(d) obtaining the malware conditional probability of the discrete numeric value for the accessed observable feature from a database of predetermined probabilities for malware;

(e) obtaining the whiteware conditional probability of the discrete numeric value for the same accessed observable feature from a database of predetermined probabilities for whiteware;

(f) invoking Bayes theorem to calculate the probability that the portable executable file is malware given the malware and whiteware conditional probabilities for the discrete numeric value of the first observable;

(g) updating the malware belief (P(M)) to reflect a result of Bayes theorem calculated with respect to the first observable feature;

(h) iterating steps (b) through (g) for any additional accessible observable features, whereby a final malware belief (P(M)Final) is returned;

(i) evaluating the final malware belief (P(M)Final) to classify the portable executable file as malware if the final malware belief (P(M)Final) is greater than or equal to a predetermined threshold value, or as whiteware if the final malware belief (P(M)Final) is less than the same predetermined threshold value; and

13. The method according to claim 12, where the observable feature types include Boolean, integer, and range such that a Boolean observable feature is assigned a value of 0 or 1, an integer observable feature is assigned an integer value, and a range observable feature is assigned a value within a bounded range.

14. The method according to claim 12, where a value for an observable feature is computed by performing calculations with respect to the values of other observable features.

15. The method according to claim 12, where the initial malware belief (P(M)) is set to 0.5 in step (a).

16. The method according to claim 12, where the predetermined threshold value in step (i) is 0.7.

17. The method according to claim 12, where a change in malware belief (P(M)) is determined as the difference between a current and the immediately previous malware belief (P(M)), and where the next observable feature of the portable executable file to be evaluated is dependent on the change in the malware belief (P(M)) as the result of evaluation of the previous observable feature.

18. The method according to claim 12, where a step for determining the next observable feature to be processed is included after step (g).

19. The method according to claim 18, where the next observable feature to be processed is determined by evaluating the change in malware belief (change in P(M)) as a result of the last observable feature processed and finding which of the remaining observable features to be processed are most closely correlated with the change in malware belief.

20. The method according to claim 12, where multiple portable executable files can be processed and all evaluated portable executable files can be listed by classification type.

21. The method according to claim 12, where the final malware belief (P(M)Final) is returned after all available observable features have been evaluated.

22. A computer-implemented method for classifying a portable executable file, comprising:

(a) initializing a malware belief (P(M)) to a predetermined value;

(b) accessing, using one or more processors, a first observable feature from the portable executable file;

(c) performing calculations with respect to the first observable feature such that the first observable feature is assigned a discrete numeric value;

(d) obtaining the malware conditional probability of the discrete numeric value for the first observable feature from a database of predetermined probabilities;

(e) obtaining the whiteware conditional probability of the discrete numeric value for the same first observable feature from a database of predetermined probabilities;

(g) updating the malware belief (P(M)) to reflect a result of Bayes theorem calculated with respect to the first observable feature;

(h) iterating steps (b) through (g) for additional observable features until a final malware belief (P(M)Final) is returned;

(j) where the malware belief (P(M)) is evaluated after each iteration and the process returns a value for the final malware belief (P(M)Final) and the portable executable file is classified as whiteware after any iteration where the malware belief (P(M)) is less than a predetermined convergence value and the process returns a value for the final malware belief (P(M)Final) and the portable executable file is classified as malware if the malware belief (P(M)) is greater than one minus the same predetermined convergence value and the final malware belief (P(M)Final) is evaluated with regard to the distinct predetermined threshold value only after all accessed observable features have been evaluated and the predetermined convergence value is never reached.

23. The method according to claim 22, where the predetermined convergence value is 0.01.

24. The method according to claim 22, where the predetermined threshold value is 0.7.

Patent Citations (7)

Patent	Date	Inventor	Cited By
US6161130(A)	2000-12-01	Horvitz et al.	Applicant
US6907430(B2)	2005-06-01	Chong et al.	Examiner
US7487544(B2)	2009-02-01	Schultz et al.	Applicant
US7577993(B2)	2009-08-01	Roychowdhary et al.	Examiner
US8161548(B1)	2012-04-01	Wan	Examiner
US2003/0065926(A1)	2003-04-01	Schultz et al.	Examiner
US2009/0013405(A1)	2009-01-01	Schipka	Examiner

Non-Patent Literature (16)

Schultz, M. G. et al, “Data Mining Methods for Detection of New Malicious Executables,” IEEE Symposium on Security and Privacy (S&P), pp. 38-49, 2001.Applicant
Hnatiw, Nick et al “Pimp My PE: Parsing Malicious and Malformed Executables,” Virus Bulletin Conference, Sep. 19, 2007.Applicant
Shafiq, M. Zubair et al, “PE-Miner: Mining Structural Information to Detect Malicious Executables in Realtime,” Recent Advances in Intrusion Detection, vol. 5758, pp. 121-141, 2009.Applicant
Tevis, Jay-Evan J. et al., “Static Analysis of Anomalies and Security Vulnerabilities in Executable Files,” ACM SE'06, Mar. 10-12, 2006.Applicant
Perdisci, R. et al., “McBoost: Boosting Scalability in Malware Collection and Analysis Using Statistical Classification of Executables,” Annual Computer Security Applications Conference (ACSAC), IEEE Press, pp. 301-310, 2008.Applicant
Kolter, M.A. et al., “Learning to Detect Malicious Executables in the Wild,” International Conference on Knowledge Discovery and Data Mining (KDD), pp. 470-478, 2004.Applicant
Tabish, S. Momina et al., “Malware Detection Using Statistical Analysis of Byte-Level File Content,” International Conference on Knowledge Discovery and Data Mining Proceedings of the ACM SIGKDD Workshop on CyberSecurity and Intelligence Infomatics, pp. 23-31, 2009.Applicant
Choi, Yang-Seo et al., “Encoded Executable File Detection Technique via Executable File Header Analysis,” International Journal of Hybrid Information Technology, vol. 2, No. 2, Apr. 2009.Applicant
Li, Wei-Jen et al., “Information Assurance Workshop, 2005. IAW '05,” Proceedings from the Sixth Annual IEEC SMC, pp. 64-71, 15-17 Jun. 2005.Applicant
Reddy, D. K. S. et al., “N-Gram Analysis for Computer Virus Detection,” Journal in Computer Virology, 2(3), 2006.Applicant
Wikipedia, “Bayesian Inference,” http://en.wikipedia.org/wiki/Bayesian—inference, 2011.Applicant
Wikipedia, “Naive Bayes Classifier,” http://en.wikipedia.org/wiki/Naive—Bayes—classifier, 2011.Applicant
Ero Carrera, “pefile Documentation, version 1.2.6,” http://dkbza.org/pefile/pefile.html, 2005.Applicant
Pietrek, Matt, “An In-Depth Look into the Win32 Portable Executable File Format, Part 2,” MSDN Magazine, Mar. 2002.Applicant
Pietrek, Matt, “An In-Depth Look into the Win32 Portable Executable File Format, Part 1,” MSDN Magazine, Feb. 2002.Applicant
A-V Comparatives E.V., “Anti-Virus Comparative Proactive/Retrospective Test,” Jun. 2010.Applicant

Abstract

Description

Rights of the Government

[0001] The invention described herein may be manufactured and used by or for the Government of the United States for all governmental purposes without the payment of any royalty.

Background of the Invention

Summary of the Invention

Brief Description of the Drawings

[0023] FIG. 1 is a flowchart detailing the method for evaluating and classifying portable executable files.

[0024] FIG. 2 illustrates sample instructions for iterative use of Bayes Theorem to evaluate and classify portable executable files.

[0025] FIG. 3 is a process plot which illustrates how the Bayesian Inference Engine iterates to a final belief for a malware sample.

[0026] FIG. 4 is an actual screenshot of the present invention's graphical user interface before any files have been evaluated.

[0027] FIG. 5 is an actual screenshot of the present invention's graphical user interface after all selected files have been evaluated.

[0028] FIG. 6 is a flowchart detailing the method for determining which observable to process after an increase in malware belief.

[0029] FIG. 7 is a flowchart detailing the method for determining which observable to process after malware belief does not increase.

Detailed Description

[0032]

P (C ❘ E) = \frac{P (E | C) P (C)}{P (E)}

[0034]

P (M | O) = \frac{P (O | M) P (M)}{P (O)}

[0035] Because a file is either whiteware or malware, but never both, the probability that file is whiteware, P(W) can be expressed as P(W)=1−P(M).

[0037]

P (M | O) = \frac{1}{1 + \frac{P (O | W)}{P (O | M)} \frac{(1 - P (M))}{P (M)}}

[0057] The method to determine the order of observables based on correlation can be included as part of the process during each iteration before step 180 when the next observable is accessed.

- [0059] O_i≡i^thObservable where i=1, 2, 3, . . . , N_O
- [0060] N_O≡Total Number of Observables

[0061] The second variable is the inter-observable correlation coefficient. There are two subtypes. The first subtype is the malware correlation coefficient between two observables, Oi and Oj:

[0062]

C^{M} (i, j) = \frac{1}{σ_{i} σ_{j}} \frac{1}{N_{F}^{M} - 1} \sum_{k = 1}^{N_{F}^{M}} (O_{i}^{M} (k) - {\overline{O}}_{i}^{M}) (O_{j}^{M} (k) - {\overline{O}}_{j}^{M})

[0063] Supporting variables appearing in the expression above include the malware average value for the ith Observable, Oi:

[0064]

{\overline{O}}_{i}^{M} = \frac{1}{N_{F}^{M}} \sum_{k = 1}^{N_{F}^{M}} O_{i}^{M} (k)

N_{F}^{M} \equiv Numbered of Malware Files

O_{i}^{M} (k) \equiv Value for Observable O_{i} Measured

in k^{th} Malware File

[0065] Also appearing in the expression is the malware standard deviation for the ith Observable, Oi:

[0066]

σ_{i}^{M} = \sqrt{\frac{1}{N_{F}^{M} - 1} \sum_{k = 1}^{N_{F}^{M}} {(O_{i}^{M} (k) - {\overline{O}}_{i}^{M})}^{2}}

[0067] The second subtype is the whiteware correlation coefficient between two observables, Oi and Oj:

[0068]

C^{W} (i, j) = \frac{1}{σ_{i} σ_{j}} \frac{1}{N_{F}^{W} - 1} \sum_{k = 1}^{N_{F}^{W}} (O_{i}^{W} (k) - {\overline{O}}_{i}^{W}) (O_{j}^{W} (k) - {\overline{O}}_{j}^{W})

[0069] Supporting variables appearing in the expression above include the whiteware average value for the ith Observable, Oi:

[0070]

{\overline{O}}_{i}^{W} = \frac{1}{N_{F}^{W}} \sum_{k = 1}^{N_{F}^{W}} O_{i}^{W} (k)

N_{F}^{W} \equiv Number of Whiteware Files

O_{i}^{W} (k) \equiv Value for Observable, O_{i} Measured

in k^{th} Whiteware Files

[0071] Also appearing in the expression is the whiteware standard deviation for the ith Observable, Oi:

[0072]

σ_{i}^{W} = \sqrt{\frac{1}{N_{F}^{W} - 1} \sum_{k = 1}^{N_{F}^{W}} {(O_{i}^{W} (k) - {\overline{O}}_{i}^{W})}^{2}}