Effective Anomaly Detection with Scarce Training DataWilliam Robertson∗[email protected] BerkeleyFederico Maggi∗[email protected] di MilanoChristopher Kruegel Giovanni Vigna{chris,vigna}@cs.ucsb.eduComputer Security GroupUC Santa BarbaraAbstractLearning-based anomaly detection has proven to bean effective black-box technique for detecting unknownattacks. However, the effectiveness of this techniquecrucially depends upon both the quality and the com-pleteness of the training data. Unfortunately, in mostcases, the traffic to the system (e.g., a web applica-tion or daemon process) protected by an anomaly de-tector is not uniformly distributed. Therefore, somecomponents (e.g., authentication, payments, or contentpublishing) might not be exercised enough to train ananomaly detection system in a reasonable time frame.This is of particular importance in real-world settings,where anomaly detection systems are deployed with lit-tle or no manual configuration, and they are expected toautomatically learn the normal behavior of a system todetect or block attacks.In this work, we first demonstrate that the featuresutilized to train a learning-based detector can be se-mantically grouped, and that features of the same grouptend to induce similar models. Therefore, we proposeaddressing local training data deficiencies by exploitingclustering techniques to construct a knowledge base ofwell-trained models that can be utilized in case of un-dertraining. Our approach, which is independent of theparticular type of anomaly detector employed, is vali-dated using the realistic case of a learning-based systemprotecting a pool of web servers running several webapplications such as blogs, forums, or Web services. Werun our experiments on a real-world data set containingover 58 million HTTP requests to more than 36,000 dis-tinct web application components. The results show thatby using the proposed solution, it is possible to achieveeffective attack detection even with scarce training data.Keywords: Anomaly detection, training data, web appli-cation.1 IntroductionThe Internet has evolved from its humble beginningsat CERN in 1991 into a massive network of ubiquitousservices that spans the globe and reaches an estimated1.4 billion people [27]. The World Wide Web containsmore than 100 million sites [46] and around 1 trillionunique URLs as indexed by Google [1]. Due to its per-vasive nature, the Internet – and in particular the Web– has become a predominant medium for disseminat-ing and collecting information. In fact, web applicationshave enjoyed immense popularity as an efficient meansfor providing services to users. For instance, Face-book has more than 250 million active users, upload-ing more than 1 billion photos each month, and Twit-ter distributed more than 3 million messages per day inMarch 2008 [34].Unfortunately, applications have been found to con-tain many security vulnerabilities, due to a combina-tion of unsafe development tools and a historical lackof security awareness among developers. In addition,the risks are magnified when vulnerable software is de-ployed in the context of the Web, since applications aretypically widely accessible and often have access to sen-sitive information. These factors have naturally resultedin web-related vulnerabilities receiving substantial at-tention from the criminal underground [40]. As a con-sequence, the incidence of data breaches, online fraud,and other crimes resulting from the exploitation of webapplication vulnerabilities continues to rise [29,33], and,therefore, it is essential to protect applications and sys-tems connected to the Internet against such attacks.Anomaly detection has received much attention fromthe research community as an approach to detecting andpreventing unknown attacks by monitoring a network’straffic [20,25,26,32,43,44,47] or a host’s operating sys-tem [3,14,21,24,28,31,38,42]. Recently, anomaly-basedtechniques have also been shown to be effective againstweb-based threats [5, 15, 19, 30]. Effective anomaly de-tection systems are attractive because they consider theprotected system as a black box. As a result, they canbe deployed in live environments without any a prioriknowledge about the application.Anomaly detection systems contain specifications, ormodels, of the normal behavior of the protected system,and consider deviations from the specifications to be ev-idence of malicious behavior. In contrast to signature-based systems, anomaly detectors have the desirableproperty that previously unknown attacks can be iden-tified automatically. Though anomaly detection modelscan be manually specified by domain experts, this is atedious, labor-intensive, and error-prone process. There-fore, most research has instead focused on applying ma-chine learning techniques to automatically derive mod-els of normal behavior from unlabeled training data. Theterm normal behavior generally refers to a set of charac-teristics (e.g., the distribution of the symbols of strings,or the mean and standard deviation of the values of nu-merical variables) extracted from data observed duringa system’s normal operation. For instance, such datacould be the payloads of network packets, or HTTP re-quests and responses exchanged between a web serverand clients. Those characteristics are used to build mod-els of normal behavior. Learning-based anomaly detec-tors obviate the tedious and error-prone task of creat-ing specifications, and, additionally, are able to adapt tothe particular characteristics of the local environment.Therefore, anomaly detectors typically require only amodest initial configuration effort to provide effectiveattack detection.In an ideal case, a learning-based anomaly detectionsystem is deployed in front of a system and, in a com-pletely automated fashion, learns the normal interactionbetween the system and its users. Once enough trainingdata has been analyzed and the profiles for the moni-tored systems have been established, the anomaly detec-tor switches to detection mode; it is then able to detectattacks that represent anomalies with respect to normalusage. These types of anomaly detection systems areextremely attractive to security officers and site admin-istrators, who have neither the resources nor the skills tomanually analyze applications composed of hundreds ofcomponents. Because of this, several commercial webapplication firewalls implement some form of machinelearning to support anomaly detection [4,