Differential testing uses similar programs as cross-referencing oracles to find semantic bugs that do not exhibit explicit erroneous behaviors like crashes or assertion failures. Unfortunately, existing differential testing tools are domain-specific and inefficient, requiring large numbers of test inputs to find a single bug. In this paper, we address these issues by designing and implementing NEZHA, an efficient input-format-agnostic differential testing framework. The key insight behind NEZHA's design is that current tools generate inputs by simply borrowing techniques designed for finding crash or memory corruption bugs in individual programs (e.g., maximizing code coverage). By contrast, NEZHA exploits the behavioral asymmetries between multiple test programs to focus on inputs that are more likely to trigger semantic bugs. We introduce the notion of δ-diversity, which summarizes the observed asymmetries between the behaviors of multiple test applications. Based on δ-diversity, we design two efficient domain-independent input generation mechanisms for differential testing, one gray-box and one black-box. We demonstrate that both of these input generation schemes are significantly more efficient than existing tools at finding semantic bugs in real-world, complex software. NEZHA's average rate of finding differences is 52 times and 27 times higher than that of Frankencerts and Mucerts, two popular domain-specific differential testing tools that check SSL/TLS certificate validation implementations, respectively. Moreover, performing differential testing with NEZHA results in 6 times more semantic bugs per tested input, compared to adapting state-of-the-art general-purpose fuzzers like American Fuzzy Lop (AFL) to differential testing by running them on individual test programs for input generation. NEZHA discovered 778 unique, previously unknown discrepancies across a wide variety of applications (ELF and XZ parsers, PDF viewers and SSL/TLS libraries), many of which constitute previously unknown critical security vulnerabilities. In particular, we found two critical evasion attacks against ClamAV, allowing arbitrary malicious ELF/XZ files to evade detection. The discrepancies NEZHA found in the X.509 certificate validation implementations of the tested SSL/TLS libraries range from mishandling certain types of KeyUsage extensions, to incorrect acceptance of specially crafted expired certificates, enabling man-in-the-middle attacks. All of our reported vulnerabilities have been confirmed and fixed within a week from the date of reporting.

Vulnerabilities that disclose executable memory pages enable a new class of powerful code reuse attacks that build the attack payload at runtime. In this work, we present Heisenbyte, a system to protect against memory disclosure attacks. Central to Heisenbyte is the concept of destructive code reads -- code is garbled right after it is read. Garbling the code after reading it takes away from the attacker her ability to leverage memory disclosure bugs in both static code and dynamically generated just-in-time code. By leveraging existing virtualization support, Heisenbyte's novel use of destructive code reads sidesteps the problem of incomplete binary disassembly in binaries, and extends protection to close-sourced COTS binaries, which are two major limitations of prior solutions against memory disclosure vulnerabilities. Our experiments demonstrate that Heisenbyte can tolerate some degree of imperfect static analysis in disassembled binaries, while effectively thwarting dynamic code reuse exploits in both static and JIT code, at a modest 1.8% average runtime overhead due to virtualization and 16.5% average overhead due to the destructive code reads.

Machine to Machine (M2M) systems are actively spreading, with mobile networks rapidly evolving to provide connectivity beyond smartphones and tablets. With billions of embedded devices expected to join cellular networks over the next few years, novel applications are emerging and contributing to the Internet of Things (IoT) paradigm. The new generation of mobile networks, the Long Term Evolution (LTE), has been designed to provide enhanced capacity for a large number of mobile devices and is expected to be the main enabler of the emergence of the IoT. In this context, there is growing interest in the industry and standardization bodies on understanding the potential impact of the scalability of M2M systems on LTE networks. The highly heterogeneous traffic patterns of most M2M systems, very different from those of smartphones and other mobile devices, and the surge of M2M connected devices over the next few years, present a great challenge for the network. This paper presents the first insights and answers on the scalability of the IoT on LTE networks, determining to what extent mobile networks could be overwhelmed by the large amount of devices attempting to communicate. Based on a detailed analysis with a custom-built, standards-compliant, large-scale LTE simulation testbed, we determine the main potential congestion points and bottlenecks, and determine which types of M2M traffic present a larger challenge. To do so, the simulation testbed implements realistic statistical M2M traffic models derived from fully anonymized real LTE traces of six popular M2M systems from one of the main tier-1 operators in the United States.

The proliferation of computers in any domain is followed by the proliferation of malware in that domain. Systems, including the latest mobile platforms, are laden with viruses, rootkits, spyware, adware and other classes of malware. Despite the existence of anti-virus software, malware threats persist and are growing as there exist a myriad of ways to subvert anti-virus (AV) software. In fact, attackers today exploit bugs in the AV software to break into systems.

Purpose IOS firmware diversity, the unintended consequence of a complex firmware compilation process, has historically made reliable exploitation of Cisco routers difficult. With approximately 300,000 unique IOS images in existence, a new class of version‐agnostic shellcode is needed in order to make the large‐scale exploitation of Cisco IOS possible. The purpose of this paper is to show that such attacks are now feasible by demonstrating two different reliable shellcodes that will operate correctly over many Cisco hardware platforms and all known IOS versions. Design/methodology/approach The paper examines prior work in the area of Cisco IOS rootkits and constructs a novel IOS version‐agnostic rootkit called the interrupt‐hijack rootkit. Findings As the experimental results show, the techniques proposed in this paper can reliably inject command and control capabilities into arbitrary IOS images in a version‐agnostic manner. Originality/value The authors believe that the technique presented in this paper overcomes an important hurdle in the large‐scale, reliable rootkit execution within Cisco IOS. Thus, effective host‐based defence for such routers is imperative for maintaining the integrity of our global communication infrastructures.

Decoy technology and the use of deception are useful in securing critical computing systems by confounding and confusing adversaries with fake information. Deception leverages uncertainty forcing adversaries to expend considerable effort to differentiate realistic useful information from purposely planted false information. In this paper, we propose software-based decoy system that aims to deceive insiders, to detect the exfiltration of proprietary source code. The proposed system generates believable Java source code that appear to an adversary to be entirely valuable proprietary software. Bogus software is generated iteratively using code obfuscation techniques to transform original software using various transformation methods. Beacons are also injected into bogus software to detect the exfiltration and to make an alert if the decoy software is touched, compiled or executed. Based on similarity measurement, the experimental results demonstrate that the generated bogus software is different from the original software while maintaining similar complexity to confuse an adversary as to which is real and which is not.

We propose a novel trap-based architecture for detecting passive, “silent”, attackers who are eavesdropping on enterprise networks. Motivated by the increasing number of incidents where attackers sniff the local network for interesting information, such as credit card numbers, account credentials, and passwords, we introduce a methodology for building a trap-based network that is designed to maximize the realism of bait-laced traffic. Our proposal relies on a “record, modify, replay” paradigm that can be easily adapted to different networked environments. The primary contributions of our architecture are the ease of automatically injecting large amounts of believable bait, and the integration of different detection mechanisms in the back-end. We demonstrate our methodology in a prototype platform that uses our decoy injection API to dynamically create and dispense network traps on a subset of our campus wireless network. Our network traps consist of several types of monitored passwords, authentication cookies, credit cards and documents containing beacons to alarm when opened. The efficacy of our decoys against a model attack program is also discussed, along with results obtained from experiments in the field. In addition, we present a user study that demonstrates the believability of our decoy traffic, and finally, we provide experimental results to show that our solution causes only negligible interference to ordinary users.

ABSTRACT A masquerade attack is a consequence of identity theft. In such attacks, the impostor impersonates a legitimate insider while performing illegitimate activities. These attacks are very hard to detect and can cause considerable damage to an organization. Prior work has focused on user command modeling to identify abnormal behavior indicative of impersonation. In this paper, we investigate the performance of two one‐class user behavior profiling techniques: one‐class Support Vector Machines (ocSVMs) and a Hellinger distance‐based user behavior profiling technique. Both techniques modelbags of wordsor commands and do not modelsequencesof commands. We use both techniques for masquerade detection and compare the experimental results. The objective is to evaluate which modeling technique is most suitable for use in an operational monitoring system, hence our focus is on accuracy and operational performance characteristics. We show that one‐class SVMs are most practical for deployment in sensors developed for masquerade detection in the general case. We also show that for specific users whose profile fits the average user profile, one‐class SVMs may not be the best modeling approach. Such users pose a more serious threat since they may be easier to mimic. Copyright © 2011 John Wiley & Sons, Ltd.

Our global communication infrastructures are powered by large numbers of legacy embedded devices. Recent advances in offensive technologies targeting embedded systems have shown that the stealthy exploitation of high-value embedded devices such as router and firewalls is indeed feasible. However, little to no host-based defensive technology is available to monitor and protect these devices, leaving large numbers of critical devices defenseless against exploitation. We devised a method of augmenting legacy embedded devices, like Cisco routers, with host-based defenses in order to create a stealthy, embedded sensor-grid capable of monitoring and capturing real-world attacks against the devices which constitute the bulk of the Internet substrate. Using a software mechanism which we call the Symbiote, a white-list based code modification detector is automatically injected in situ into Cisco IOS, producing a fully functional router firmware capable of detecting and capturing successful attacks against itself for analysis. Using the Symbiote-protected router as the main component, we designed a sensor system which requires no modification to existing hardware, fully preserves the functionality of the original firmware, and detects unauthorized modification of memory within 450 ms. We believe that it is feasible to use the techniques described in this paper to inject monitoring and defensive capability into existing routers to create an early attack warning system to protect the Internet substrate.

We present a quantitative lower bound on the number of vulnerable embedded device on a global scale. Over the past year, we have systematically scanned large portions of the internet to monitor the presence of trivially vulnerable embedded devices. At the time of writing, we have identified over 540,000 publicly accessible embedded devices configured with factory default root passwords. This constitutes over 13% of all discovered embedded devices. These devices range from enterprise equipment such as firewalls and routers to consumer appliances such as VoIP adapters, cable and IPTV boxes to office equipment such as network printers and video conferencing units. Vulnerable devices were detected in 144 countries, across 17,427 unique private enterprise, ISP, government, educational, satellite provider as well as residential network environments. Preliminary results from our longitudinal study tracking over 102,000 vulnerable devices revealed that over 96% of such accessible devices remain vulnerable after a 4-month period. We believe the data presented in this paper provides a conservative lower bound on the actual population of vulnerable devices in the wild. By combining the observed vulnerability distributions and its potential root causes, we propose a set of mitigation strategies and hypothesize about its quantitative impact on reducing the global vulnerable embedded device population. Employing our strategy, we have partnered with Team Cymru to engage key organizations capable of significantly reducing the number of trivially vulnerable embedded devices currently on the internet. As an ongoing longitudinal study, we plan to gather data continuously over the next year in order to quantify the effectiveness of community's cumulative effort to mitigate this pervasive threat.

We propose a novel trap-based architecture for enterprise networks that detects "silent" attackers who are eavesdropping network traffic. The primary contributions of our work are the ease of injecting, automatically, large amounts of believable bait, and the integration of various detection mechanisms in the back-end. We demonstrate our methodology in a prototype platform that uses our decoy injection API to dynamically create and dispense network traps on a subset of our campus wireless network. Finally, we present results of a user study that demonstrates the believability of our automatically generated decoy traffic.

Current network access control (NAC) technologies manage the access of new devices into a network to prevent rogue devices from attacking network hosts or services. Typically, new devices are checked against a set of manually defined policies (rules) before being granted access by the NAC enforcer. The main difficulty with this approach lies in the generation and update of new policies manually as time elapses and all devices have to reestablish their access rights. The BB-NAC mechanism was the first to introduce a novel behavior-based network access control architecture based on behavior profiles and not rules, where behavior-based access control policies were automatically generated. As originally presented, BB-NAC relied on manually pre-determined clusters of behavior which required human intervention and prevented the fully automation of the mechanism. In this paper, we present an enhanced BB-NAC mechanism that fully automatizes the creation of clusters of behavior. The access control is enhanced with the incorporation of automatic behavior clustering, which improves the intrusion detection capabilities by allowing for a more fine-grained definition of normal behavior. Apart from the lack of automatic clustering, the original BB-NAC overlooked the evolution of the mechanism as new behavior profiles were computed over time. As part of our enhancements, we also present an incremental-learning algorithm that automatically updates the behavior-based access control policies. We show that the algorithm is resilient to compromised or fabricated profiles trying to manipulate the policies. We provide extensive experiments with real user profiles computed with their network flows processed from Cisco NetFlow logs captured at our host institution. Our results show that behavior-based access control policies enhance conventional NAC technologies. Specifically, we achieve true rejection rates of 95% for anomalous user profiles separated by one standard deviation from the normal user network behavior. In addition, we also show that the enhanced mechanism can differentiate between normal changes in the behavior profiles (concept drift) and attacks.

Anomaly detection (AD) sensors compute behavior profiles to recognize malicious or anomalous activities. The behavior of a host is checked continuously by the AD sensor and an alert is raised when the behavior deviates from its behavior profile. Unfortunately, the majority of AD sensors suffer from high volumes of false alerts either maliciously crafted by the host or originating from insufficient training of the sensor. We present a cluster-based AD sensor that relies on clusters of behavior profiles to identify anomalous behavior. The behavior of a host raises an alert only when a group of host profiles with similar behavior (cluster of behavior profiles) detect the anomaly, rather than just relying on the host's own behavior profile to raise the alert (single-profile AD sensor). A cluster-based AD sensor significantly decreases the volume of false alerts by providing a more robust model of normal behavior based on clusters of behavior profiles. Additionally, we introduce an architecture designed for the deployment of cluster-based AD sensors. The behavior profile of each network host is computed by its closest switch that is also responsible for performing the anomaly detection for each of the hosts in its subnet. By placing the AD sensors at the switch, we eliminate the possibility of hosts crafting malicious alerts. Our experimental results based on wireless behavior profiles from users in the CRAWDAD dataset show that the volume of false alerts generated by cluster-based AD sensors is reduced by at least 50% compared to single-profile AD sensors.

The efficacy of anomaly detection (AD) sensors depends heavily on the quality of the data used to train them. Artificial or contrived training data may not provide a realistic view of the deployment environment. Most realistic data sets are dirty; that is, they contain a number of attacks or anomalous events. The size of these high-quality training data sets makes manual removal or labeling of attack data infeasible. As a result, sensors trained on this data can miss attacks and their variations. We propose extending the training phase of AD sensors (in a manner agnostic to the underlying AD algorithm) to include a sanitization phase. This phase generates multiple models conditioned on small slices of the training data. We use these "micro- models" to produce provisional labels for each training input, and we combine the micro-models in a voting scheme to determine which parts of the training data may represent attacks. Our results suggest that this phase automatically and significantly improves the quality of unlabeled training data by making it as "attack-free" and "regular" as possible in the absence of absolute ground truth. We also show how a collaborative approach that combines models from different networks or domains can further refine the sanitization process to thwart targeted training or mimicry attacks against a single site.

Polymorphic malcode remains a troubling threat. The ability formal code to automatically transform into semantically equivalent variants frustrates attempts to rapidly construct a single, simple, easily verifiable representation. We present a quantitative analysis of the strengths and limitations of shellcode polymorphism and consider its impact on current intrusion detection practice.

Mobile Ad-hoc NETworks (MANETs) pose unique security requirements and challenges due to their reliance on open, peer-to-peer models that often don't require authentication between nodes. Additionally, the limited processing power and battery life of the devices used in a MANET also prevent the adoption of heavy-duty cryptographic techniques. While traditional misuse-based Intrusion Detection Systems (IDSes) may work in a MANET, watching for packet dropouts or unknown outsiders is difficult as both occur frequently in both malicious and non-malicious traffic. Anomaly detection approaches hold out more promise, as they utilize learning techniques to adapt to the wireless environment and flag malicious data. The anomaly detection model can also create device behavior profiles, which peers can utilize to help determine its trustworthiness. However, computing the anomaly model itself is a time-consuming and processor-heavy task. To avoid this, we propose the use of model exchange as a device moves between different networks as a means to minimize computation and traffic utilization. Any node should be able to obtain peers' model(s) and evaluate it against its own model of "normal" behavior. We present this model, discuss scenarios in which it may be used, and provide preliminary results and a framework for future implementation.

The content of a webpage is usually contained within a small body of text and images, or perhaps several articles on the same page; however, the content may be lost in the clutter, particularly hurting users browsing on small cell phone and PDA screens and visually impaired users relying on speed rendering of web pages. Using the genre of a web page, we have created a solution, Crunch that automatically identifies clutter and removes it, thus leaving a clean content-full page. In order to evaluate the improvement in the applications for this technology, we identified a number of experiments. In this paper, we have those experiments, the associated results and their evaluation.

The Email Mining Toolkit (EMT) is a data mining system that computes behavior profiles or models of user email accounts. These models may be used for a multitude of tasks including forensic analyses and detection tasks of value to law enforcement and intelligence agencies, as well for as other typical tasks such as virus and spam detection. To demonstrate the power of the methods, we focus on the application of these models to detect the early onset of a viral propagation without “content-base ” (or signature-based) analysis in common use in virus scanners. We present several experiments using real email from 15 users with injected simulated viral emails and describe how the combination of different behavior models improves overall detection rates. The performance results vary depending upon parameter settings, approaching 99 % true positive (TP) (percentage of viral emails caught) in general cases and with 0.38 % false positive (FP) (percentage of emails with attachments that are mislabeled as viral). The models used for this study are based upon volume and velocity statistics of a user's email rate and an analysis of the user's (social) cliques revealed in the person's email behavior. We show by way of simulation that virus propagations are detectable since viruses may emit emails at rates different than human behavior suggests is normal, and email is directed to groups of recipients in ways that violate the users' typical communications with their social groups.

Machine learning and data mining can be effectively used to model, classify and discover interesting information for a wide variety of data including email. The Email Mining Toolkit, EMT, has been designed to provide a wide range of analyses for arbitrary email sources. Depending upon the task, one can usually achieve very high accuracy, but with some amount of false positive tradeoff. Generally false positives are prohibitively expensive in the real world. In the case of spam detection, for example, even if one email is misclassified, this may be unacceptable if it is a very important email. Much work has been done to improve specific algorithms for the task of detecting unwanted messages, but less work has been report on leveraging multiple algorithms and correlating models in this particular domain of email analysis.EMT has been updated with new correlation functions allowing the analyst to integrate a number of EMT's user behavior models available in the core technology. We present results of combining classifier outputs for improving both accuracy and reducing false positives for the problem of spam detection. We apply these methods to a very large email data set and show results of different combination methods on these corpora. We introduce a new method to compare multiple and combined classifiers, and show how it differs from past work. The method analyzes the relative gain and maximum possible accuracy that can be achieved for certain combinations of classifiers to automatically choose the best combination.

We present a component anomaly detector for a host-based intrusion detection system (IDS) for Microsoft Windows. The core of the detector is a learning-based anomaly detection algorithm that detects attacks on a host machine by looking for anomalous

The analysis of the vast storehouse of email content accumulated or produced by individual users has received relatively little attention other than for specific tasks such as spam and virus filtering. Current email analysis in standard client applications consists of keyword based matching techniques for filtering and expert driven manual exploration of email files.

We propose a fully distributed system (as compared to centralized and partially distributed systems) for cost-sensitive data mining. Experimental results have shown that this approach achieves higher accuracy than both the centralized and partially distributed learning methods, however, it incurs much less training time, neither communication nor computation overhead.

Presently, inductive learning is still performed in a frustrating batch process. The user has little interaction with the system and no control over the final accuracy and training time. If the accuracy of the produced model is too low, all the computing resources are misspent. In this paper we propose a progressive modeling framework. In progressive modeling, the learning algorithm estimates online both the accuracy of the final model and remaining training time. If the estimated accuracy is far below expectation, the user can terminate training prior to completion without wasting further resources. If the user chooses to complete the learning process, progressive modeling will compute a model with expected accuracy in expected time. We describe one implementation of progressive modeling using ensemble of classifiers.

Intrusion detection is an essential component of computer security mechanisms. Intrusion detection systems (IDSs) need to efficiently and accurately adapt to incorporate new knowledge of previously unseen classes of attacks (different from incremental learning) that are constantly invented to prevent any further damage as early as possible. Learning a completely new detection model from both known attacks and new unknown attacks is usually very slow due to the complexity of the problem and large size of the dataset. There isn't much previous research to address this issue. In this paper, we propose an “ensemble-based” method to efficiently learn a light weight model from audit data of new attack patterns that is then “attached” to an existing previously learned model by a decision rule system. Our method solves the problem of fast training and efficient model deployment that prevents the damage of new types of intrusions at its earliest stage. Several configurations varying in the form of the underlying model and decision rules are explored. The training cost of this method is significantly less than re-training a monolithic model from both new and old training data. Empirical studies show the ensemble-based method has comparable accuracy as the monolithic detector, but the model generation time is 150 times faster. This quick learning time provides an opportunity to deploy new models rapidly to thwart damage of both new and old classes of attacks, which can be replaced later with an updated and better monolithic model as time and resources permit.

We present a general framework for scalable cost-sensitive learning based on ensembles of classifiers. To compute ensembles for scalable learning, base models are computed from data subsets and their predictions are combined. Previous research mainly focus on combining class labels for cost-insensitive problems. In our study, we concentrate on how to combine the probability and benefit outputs (such as charity donation amount) for scalable cost-sensitive learning. We identify a few properties of both averaging and cost-sensitive optimal decision-making. Due to these properties, averaging has great potential for higher benefit as well as its obvious advantage of scalability. Experiments have shown that the averaging methods achieve a benefit level as good as or even better than the respective single classifier trained from the same dataset as a whole. However, the averaging methods exhibit linear speedup and scaled speedup that are independent of learning algorithms. Besides the averaging methods, we have experimented with tree-structured methods using variations of meta-learning and regression. Nonetheless, these approaches do not lead to higher benefits but consume higher overhead, hence are less scalable. Compared with tree-structured methods, the averaging methods are more efficient to classify examples, and easer to implement and verify.

Intrusion detection systems (IDSs) must maximize the realization of security goals while minimizing costs. In this paper, we study the problem of building cost-sensitive intrusion detection models. We examine the major cost factors associated with an IDS, which include development cost, operational cost, damage cost due to successful intrusions, and the cost of manual and automated response to intrusions. These cost factors can be qualified according to a defined attack taxonomy and site-specific security policies and priorities. We define cost models to formulate the total expected cost of an IDS, and present cost-sensitive machine learning techniques that can produce detection models that are optimized for user-defined cost metrics. Empirical experiments show that our cost-sensitive modeling and deployment techniques are effective in reducing the overall cost of intrusion detection.

Intrusion detection systems (IDSs) must be capable of detecting new and unknown attacks, or anomalies. We study the problem of building detection models for both pure anomaly detection and combined misuse and anomaly detection (i.e., detection of both known and unknown intrusions). We propose an algorithm to generate artificial anomalies to coerce the inductive learner into discovering an accurate boundary between known classes (normal connections and known intrusions) and anomalies. Empirical studies show that our pure anomaly detection model trained using normal and artificial anomalies is capable of detecting more than 77% of all unknown intrusion classes with more than. 50% accuracy per intrusion class. The combined misuse and anomaly detection models are as accurate as a pure misuse detection model in detecting known intrusions and are capable of detecting at least 50% of unknown intrusion classes with accuracy measurements between 75% and 100% per class.

A serious security threat today is malicious executables, especially new, unseen malicious executables often arriving as email attachments. These new malicious executables are created at the rate of thousands every year and pose a serious security threat. Current anti-virus systems attempt to detect these new malicious programs with heuristics generated by hand. This approach is costly and oftentimes ineffective. We present a data mining framework that detects new, previously unseen malicious executables accurately and automatically. The data mining framework automatically found patterns in our data set and used these patterns to detect a set of new malicious binaries. Comparing our detection methods with a traditional signature-based method, our method more than doubles the current detection rates for new malicious executables.

Intrusion detection (ID) is an important component of infrastructure protection mechanisms. Intrusion detection systems (IDSs) need to be accurate, adaptive, and extensible. Given these requirements and the complexities of today's network environments, we need a more systematic and automated IDS development process rather that the pure knowledge encoding and engineering approaches. This article describes a novel framework, MADAM ID, for Mining Audit Data for Automated Models for Instrusion Detection. This framework uses data mining algorithms to compute activity patterns from system audit data and extracts predictive features from the patterns. It then applies machine learning algorithms to the audit records taht are processed according to the feature definitions to generate intrusion detection rules. Results from the 1998 DARPA Intrusion Detection Evaluation showed that our ID model was one of the best performing of all the participating systems. We also briefly discuss our experience in converting the detection models produced by off-line data mining programs to real-time modules of existing IDSs.

1 Introduction Learning from very large and distributed databases imposes major performance challenges for data mining. Many databases have grown too large to fit into main memory. Learning a monolithic classifier will be very slow since it requires all data be held in main memory. Some databases are inherently distributed and cannot be brought into a single site for a variety of reasons. It is very hard to learn a single classifier under these constraints. One such application is to learn a fraud detection model from different participating credit card companies whose datasets are huge and strictly distributed. Yet there are some databases that have large amounts of new data available periodically or in real time. To re-learn a new model of the whole data set each time an increment is provided is both expensive and inefficient.

We discuss the KDD process in "data-flow" environments, where unstructured and time dependent data can be processed into various levels of structured and semanticallyrich forms for analysis tasks.Using network intrusion detection as a concrete application example, we describe how to construct models that are both acczLrate in describing the underlying concepts, and efficient when used to analyze data in real-time.We present procedures for analyzing frequent patterns from lower level data and constructing appropriate features to formulate higher level data.The features generated from various levels of data have different computational costs (in time and space).We show that in order to minimize the time required in using the classification models in a real-time environment, we can exploit the "necessary conditions" associated with the lowcost features to determine whether some high-cost features need to be computed and the corresponding classification rules need to be checked.We have applied our tools to the problem of building network intrusion detection models.We report our experiments using the network data provided as part of the 1998 DARPA Intrusion Detection Evaluation program.We also discuss our experience in using the mined models in NFR, a real-time network intrusion detection system.

There is often the need to update an installed intrusion detection system (IDS) due to new attack methods or upgraded computing environments. Since many current IDSs are constructed by manual encoding of expert knowledge, changes to IDSs are expensive and slow. We describe a data mining framework for adaptively building Intrusion Detection (ID) models. The central idea is to utilize auditing programs to extract an extensive set of features that describe each network connection or host session, and apply data mining programs to learn rules that accurately capture the behavior of intrusions and normal activities. These rules can then be used for misuse detection and anomaly detection. New detection models are incorporated into an existing IDS through a meta-learning (or co-operative learning) process, which produces a meta detection model that combines evidence from multiple models. We discuss the strengths of our data mining programs, namely, classification, meta-learning, association rules, and frequent episodes. We report on the results of applying these programs to the extensively gathered network audit data for the 1998 DARPA Intrusion Detection Evaluation Program.

Many commercial organizations routinely gather large numbers of databases for various marketing and business analysis functions. The task is to correlate information from different databases by identifying distinct individuals that appear in a number of different databases typically in an inconsistent and often incorrect fashion. The problem we study here is the task of merging data from multiple sources in as efficient manner as possible, while maximizing the accuracy of the result. We call this the merge/purge problem. In this paper we detail the sorted neighborhood method that is used by some to solve merge/purge and present experimental results that demonstrates this approach may work well in practice but at great expense. An alternative method based upon clustering is also presented with a comparative evaluation to the sorted neighborhood method. We show a means of improving the accuracy of the results based upon a multi-pass approach that succeeds by computing the Transitive Closure over the results of independent runs considering alternative primary key attributes in each pass.

Expert Databases are environments that support the processing of rule programs against a disk resident database. They occupy a position intermediate between active and deductive databases, with respect to the level of abstraction of the underlying rule language. The operational semantics of the rule language influences the problem solving strategy, while the architecture of the processing environment determines efficiency and scalability.

Much prior work in AI on various attempts to speed up rule-based systems by parallel processing has been reported. Unfortunately, many of these results indicate that there is limited parallelism to be found when rules are applied to relatively small amounts of data. Thus, one can predict that much greater parallelism can be extracted when rules are applied to large amounts of data. However, traditional compile-time parallelization strategies as developed for main-memory based systems do not scale to large databases. We propose a scalable strategy for the efficient parallel implementation of rule-based systems operating upon large databases. We concentrate on load balancing techniques in a synchronous model of rule execution, where the variance in runtime of the distributed sites is minimized per cycle of rule processing, thus increasing utilization and speedup. We demonstrate that static load balancing techniques are insufficient, and thus low overhead dynamic load balancing is the key to successful scaling. We present a form of dynamic load balancing that is based upon predicting future system loads, rather than conventional demand-driven approaches that monitor current system state. We analyze a number of possible predictive dynamic load balancing protocols by isoefficiency analysis to guide the design of a parallel database rule processing system.

In this paper, we propose meta-leaming as a general technique to combine the results of multiple learning algorithms, Mets-learner Met: ID3 96.6+

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

A panel session in which issues relating to the effects of advances in faster and more parallel hardware, production system match (PSM) algorithms, and application domains for match on PSM as a research area is presented. It is argued that there is no such thing as the optimal matching algorithm, even for the well-defined task of production-system match and that broadening the scope of the matching task beyond forward-chaining production system presents a new set of problems to the artificial intelligence community. Also, even with all the speedups, large production system runs take hours to complete, and a major portion of this time is attributable to PSM. Match technology remains a large and centralized component of system performance. To that extent, providing sufficient speedups in the match in these systems may still be useful. Performance issues of production system execution are discussed, and a common set of benchmarks and test cases is called for. It is argued that parallel algorithms for match, resolve, and fire are all interesting and difficult problems to solve, and should be the focus of research by the PSM community.>

Rule interpreters usually start with an initial database and perform the inference procedure in cycles, ending with a final database. In a real time environment it is possible to receive updates to the initial database after the inference procedure has started or even after it has ended. We present an algorithm for incremental maintenance of the deductive database in the presence of such updates. Interestingly, the same algorithm is useful for parallel and distributed rule processing in the following sense. \\'hen the processors evaluating a program operate asynchronously. then they may have different views of the database. The incremental maintenance procedure we present can be used to synchronize these views.

Although the problem of increasing the speed of rule-based programs has been studied for a long while, so far the level of parallelism achieved under various parallel processing schemes fails to meet expectations of high performance gains. Most of the work has focused on manipulating existing rule programs to accommodate parallel architectures. However, without changing the inherently sequential algorithms encoded in rule form and without using intrinsic parallel rule languages to exploit parallelism, speedup is severely limited. In this paper we demonstrate that to maximize parallelism, manipulations must take place at the algorithmic level in addition to the program level. However, traditional rule languages are not equipped to easily express parallel algorithms. Thus, an inherently parallel rule language must be devised to enable maximum parallelism. We present our initial specification of such a language, named PARULEL. Preliminary performance results are detailed for one test case program. PARULEL is one part of a larger research effort that considers four key approaches to parallel rule processing: inherently parallel execution semantics; the use of redaction meta-rules to allow programmer control of the set of parallel instantiations; an incremental evaluation algorithm that incorporates, in an efficient manner, updates to the initial set of assumptions; and an algorithm that maps a program to a parallel architecture.

DADO is a parallel, tree-structured machine designed to provide significant performance improvements in the execution of large expert systems implemented in production system form. A full-scale version of the DADO machine would comprise a large set of processing elements (PEs) (on the order of thousands), each containing its own processor, a small amount (20K bytes, in the current prototype design) of local random access memory, and a specialized I/O switch. The PEs are interconnected to form a complete binary tree. This paper describes the application domain of the DADO machine and the rationale for its design. Parallel algorithms for production system execution are briefly described. We then focus on the machine architecture and detail the hardware design of a moderately large prototype comprising 1023 microprocessors currently operational at Columbia University. We conclude with very encouraging performance statistics recently calculated from an analysis of simulations of the system.