Since the seminal work from F. Cohen in the eighties, abstract virology has seen the apparition of successive viral models, all based on Turing-equivalent formalisms. But considering recent malware such as rootkits or k-ary codes, these viral models only partially cover these evolved threats. The problem is that Turing-equivalent models do not support interactive computations. New models have thus appeared, offering support for these evolved malware, but loosing the unified approach in the way. This article provides a basis for a unified malware model founded on process algebras and in particular the Join-Calculus. In terms of expressiveness, the new model supports the fundamental definitions based on self-replication and adds support for interactions, concurrency and non-termination allows the definition of more complex behaviors. Evolved malware such as rootkits can now be thoroughly modeled. In terms of detection and prevention, the fundamental results of undecidability and isolation still hold. However the process-based model has permitted to establish new results: identification of fragments from the Join-Calculus where malware detection becomes decidable, formal definition of the non-infection property, approximate solutions to restrict malware propagation.
Considering malware, a recent article underlines the fact that interactions with the execution environment, concurrency and also non-termination prove to be important computation functionalities @cite_21 . In effect, malware, being resilient and adaptive by nature, intensively use these functionalities to survive and infect new systems. Looking at the theoretical models existing in abstract virology, they mainly focus on the self-replication capacity which is defined in a purely functional way @cite_0 , [Chpt.2-3] FI05 , @cite_7 . Unfortunately, these models rely on Turing-equivalent formalisms which can hardly support interactive computations. With the apparition of interaction-based viral techniques, new models have thus been introduced to cope with this drawback, but loosing the unified approach in the way. The apparition of k-ary malware is an obvious example. In effect, these malware heavily rely on concurrency by a distribution of the malicious code over several executing parts. A new model based on Boolean functions has been provided to model their evolving interdependence over time @cite_26 . A second relevant example is the apparition of reactive non-terminating techniques such as stealth currently deployed in rootkits. Different models have been provided to cover stealth based either on steganography @cite_29 or graph theory @cite_19 .
@cite_26 @cite_7 @cite_29 @cite_21 @cite_0 @cite_19
2964159373 2008324060 2124900567 1757513105
Malware is constantly adapting in order to avoid detection. Model-based malware detectors, such as SVM and neural networks, are vulnerable to so-called adversarial examples which are modest changes to detectable malware that allows the resulting malware to evade detection. Continuous-valued methods that are robust to adversarial examples of images have been developed using saddle-point optimization formulations. We are inspired by them to develop similar methods for the discrete, e.g. binary, domain which characterizes the features of malware. A specific extra challenge of malware is that the adversarial examples must be generated in a way that preserves their malicious functionality. We introduce methods capable of generating functionally preserved adversarial malware examples in the binary domain. Using the saddle-point formulation, we incorporate the adversarial examples into the training of models that are robust to them. We evaluate the effectiveness of the methods and others in the literature on a set of Portable Execution (PE) files. Comparison prompts our introduction of an online measure computed during training to assess general expectation of robustness. As organizations become ever more dependent on networked operations, they are increasingly vulnerable to attack by a variety of attackers, including criminals, terrorists and nation states using cyber attacks. New malware attacks, including viruses, Trojans, and worms, are constantly and rapidly emerging threats. However, attackers often reuse code and techniques from previous attacks. Both by recognizing the reused elements from previous attacks and by detecting patterns in the types of modification and reuse observed, we can more rapidly develop defenses, make hypotheses about the source of the malware, and predict and prepare to defend against future attacks. We achieve these objectives in Malware Analysis and Attribution using Genetic Information (MAAGI) by adapting and extending concepts from biology and linguistics. First, analyzing the “genetics” of malware (i.e., reverse engineered representations of the original program) provides critical information about the program that is not available by looking only at the executable program. Second, the evolutionary process of malware (i.e., the transformation from one species of malware to another) can provide insights into the ancestry of malware, characteristics of the attacker, and where future attacks might come from and what they might look like. Third, functional linguistics is the study of the intent behind communicative acts; its application to malware characterization can support the study of the intent behind malware behaviors. To this point in the program, we developed a system that uses a range of reverse engineering techniques, including static, dynamic, behavioral, and functional analysis that clusters malware into families. We are also able to determine the malware lineage in some situations. Using behavioral and functional analysis, we are also able to identify a number of functions and purposes of malware. A novel approach to malware detection by recognizing known inter-process and intra-process malicious functionalities in software behavior is proposed. It encompasses two essential tasks: the specification of a functionality that may involve a joint activity of several apparently independent processes, and efficient recognition of the specified functionality in the process behavior. The robustness of the proposed technology is achieved by the generalization of the specification domain that is separated from the detection domain. The functionalities of interest are defined in the abstract system domain through activity diagrams, thus resulting in formal specifications that are rather generic and less prone to false negatives. To facilitate the detection, we developed a procedure that automatically generates a Colored Petri Net recognizing the specified functionality in the system call domain. The separation of specification and recognition domains results in signature expressiveness and recognition efficiency. The approach is illustrated by the analysis, specification and consequent recognition of several common malicious functionalities including self-replication engines and popular payloads. A prototype IDS implementing the proposed approach has been developed and successfully tested on a set of real malware. This paper is motivated by two applications, namely i) generalizations of cuckoo hashing, a computationally simple approach to assigning keys to objects, and ii) load balancing in content distribution networks, where one is interested in determining the impact of content replication on performance. These two problems admit a common abstraction: in both scenarios, performance is characterized by the maximum weight of a generalization of a matching in a bipartite graph, featuring node and edge capacities. Our main result is a law of large numbers characterizing the asymptotic maximum weight matching in the limit of large bipartite random graphs, when the graphs admit a local weak limit that is a tree. This result specializes to the two application scenarios, yielding new results in both contexts. In contrast with previous results, the key novelty is the ability to handle edge capacities with arbitrary integer values. An analysis of belief propagation algorithms (BP) with multivariate belief vectors underlies the proof. In particular, we show convergence of the corresponding BP by exploiting monotonicity of the belief vectors with respect to the so-called upshifted likelihood ratio stochastic order. This auxiliary result can be of independent interest, providing a new set of structural conditions which ensure convergence of BP.