On Evolving Buffer Overflow Attacks Using Genetic ProgrammingHilmi Güneş Kayacık Dalhousie University Faculty of Computer Science 6050 University Avenue Halifax, Nova Scotia, Canada [email protected] Malcolm Heywood Dalhousie University Faculty of Computer Science 6050 University Avenue Halifax, Nova Scotia, Canada [email protected] Nur Zincir-Heywood Dalhousie University Faculty of Computer Science 6050 University Avenue Halifax, Nova Scotia, Canada [email protected] ABSTRACT In this work, we employed genetic programming to evolve a “white hat” attacker; that is to say, we evolve variants of an attack with the objective of providing better detectors. Assuming a generic buffer overflow exploit, we evolve variants of the generic attack, with the objective of evading detection by signature-based methods. To do so, we pay particular attention to the formulation of an appropriate fitness function and partnering instruction set. Moreover, by making use of the intron behavior inherent in the genetic programming paradigm, we are able to explicitly obfuscate the true intent of the code. All the resulting attacks defeat the widely used 'Snort' Intrusion Detection System. Categories and Subject Descriptors K.6.5 [Security and Protection]: Unauthorized access; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search; I.2.2 [Automatic Programming]; General Terms: Algorithms, Design, Security. Keywords: Linear Genetic Programming, Mimicry Attacks, Intrusion Detection Systems. 1. INTRODUCTION All users of virus checkers, firewalls and more generally signature-based intrusion detection systems are familiar with the need to continuously receive updates to the original base detection system. The basic nature of the intrusion detection problem is that new attacks are continuously under development. As a consequence patches to your personal firewall, virus checker or intrusion detection system are also required in order to plug the current favorite attack instance. The bottom line however, is that an omnipresent third party is required. Such a third party is responsible for recognizing unseen attacks from the log files once the system is attacked and then developing the necessary signature patch. Thus, your detector is only as good as the most recent attacks such a third party is able to correctly label. Anomaly detection (as opposed to signature-based detection) on the other hand concentrates on modeling what constitutes "normal behavior". Any deviation from the normal behavior is then flagged as an attack. This naturally results in a system able to identify novel attacks, but at the expense of false positives. That is to say, what constitutes normal behavior is not straightforward to establish, and is invariably specific to a user-application-network mix, making it impossible to carry models of normal behavior between different customers, limiting the product base for such systems. In this work we are interested in building detection systems using a genetic programming (GP) methodology, with the aim of discovering rules suitably generic for describing a wide range of anomalous behaviors. However, there are at least two pragmatic limitations constraining the applicability of GP based detectors. Firstly, the datasets used to characterize intrusion detection problems typically consist of millions of exemplars, which implies an overhead in training time. Secondly, once trained, the model is only as good as the data available at training, a third party is again required to provide appropriate labels for new attack instances. Solutions to the first problem have been demonstrated by way of active learning algorithms [1], [2], [3]. In this work we propose to address the second problem by evolving a "white hat" attacker i.e., the purpose of this attacker is to generate the attack data for which a detector will be built. Within this context the principal objective of the attacker is to camouflage a 'core' attack in such a way that the signatures at the detector are unable to discover the true nature of the code. In doing so, we are interested in making use of the code bloat property from GP where, within this context, it provides a mechanism for hiding the real intent of the code. Finally, we focus on the case of buffer overflow attacks, where such attacks represent one of the most widely utilized models of attack. From the detection perspective, this then means that we are building a modular detection platform, with different detectors associated with specific forms of attack. 2. EVOLVING BUFFER OVERFLOW ATTACKS The core behavior of an overflow attack lies in the simple observation that just because an address space of a variable declared in a program might be allocated of a specific size, this does not stop the same program from attempting to access memory outside of the allocated space. In order to make use of such a weakness, the attacker requires three components: (1) A Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. GECCO’06, July 8–12, 2006, Seattle, Washington, USA. Copyright 2006 ACM 1-59593-186-4/06/0007…$5.00. 1667program used by the target system that possesses an inherent overflow vulnerability; (2) Knowledge of the size of memory reference necessary to cause the overflow; and (3) The correct placement of a suitable exploit to make use of the overflow when it occurs. The skill in crafting such an attack lies in how an exploit is hidden and ensuring that the memory referenced outside of the allocated space corresponds to the code defining the desired malicious behavior. The generic buffer overflow attack consists of three components: the payload, the "NOP" (No operation) sled, and the "return address". The payload represents the shell code used to perform the malicious activity once operation of the buffer has been compromised. Although the specific content of any payload will vary (e.g. for different operating systems or exploit goals), encryption of the payload has in effect rendered detection of the payload itself impossible [4]. The buffer overflow is actually caught through the use of the