290333
A cooperative intrusion detection system for ad hoc networks
Mobile ad hoc networking (MANET) has become an exciting and important technology in recent years because of the rapid proliferation of wireless devices. MANETs are highly vulnerable to attacks due to the open medium, dynamically changing network topology, cooperative algorithms, lack of centralized monitoring and management point, and lack of a clear line of defense. In this paper, we report our progress in developing intrusion detection (ID) capabilities for MANET. Building on our prior work on anomaly detection, we investigate how to improve the anomaly detection approach to provide more details on attack types and sources. For several well-known attacks, we can apply a simple rule to identify the attack type when an anomaly is reported. In some cases, these rules can also help identify the attackers. We address the run-time resource constraint problem using a cluster-based detection scheme where periodically a node is elected as the ID agent for a cluster. Compared with the scheme where each node is its own ID agent, this scheme is much more efficient while maintaining the same level of effectiveness. We have conducted extensive experiments using the ns-2 and MobiEmu environments to validate our research.
8008073
Worm detection, early warning and response based on local victim information
Worm detection systems have traditionally focused on global strategies. In the absence of a global worm detection system, we examine the effectiveness of local worm detection and response strategies. This paper makes three contributions: (1) we propose a simple two-phase local worm victim detection algorithm, DSC (Destination-Source Correlation), based on worm behavior in terms of both infection pattern and scanning pattern. DSC can detect zero-day scanning worms with a high detection rate and very low false positive rate. (2) We demonstrate the effectiveness of early worm warning based on local victim information. For example, warning occurs with 0.19% infection of all vulnerable hosts on Internet when using a /12 monitored network. (3) Based on local victim information, we investigate and evaluate the effectiveness of an automatic real-time local response in terms of slowing down the global Internet worms propagation. (2) and (3) are general results, not specific to certain detection algorithm like DSC. We demonstrate (2) and (3) with both analytical models and packet-level network simulator experiments.
15031377
Anomaly detection using call stack information
The call stack of a program execution can be a very good information source for intrusion detection. There is no prior work on dynamically extracting information from the call stack and effectively using it to detect exploits. In this paper we propose a new method to do anomaly detection using call stack information. The basic idea is to extract return addresses from the call stack, and generate an abstract execution path between two program execution points. Experiments show that our method can detect some attacks that cannot be detected by other approaches, while its convergence and false positive performance is comparable to or better than the other approaches. We compare our method with other approaches by analyzing their underlying principles and thus achieve a better characterization of their performance, in particular on what and why attacks will be missed by the various approaches.
15927015
Using Labeling to Prevent Cross-Service Attacks Against Smart Phones
Wireless devices that integrate the functionality of PDAs and cell phones are becoming commonplace, making different types of network services available to mobile applications. However, the integration of different services allows an attacker to cross service boundaries. For example, an attack carried out through the wireless network interface may eventually provide access to the phone functionality. This type of attacks can cause considerable damage because some of the services (e.g., the GSM-based services) charge the user based on the traffic or time of use. In this paper, we demonstrate the feasibility of these attacks by developing a proof-of-concept exploit that crosses service boundaries. To address these security issues, we developed a solution based on resource labeling. We modified the kernel of an integrated wireless device so that processes and files are marked in a way that allows one to regulate the access to different system resources. Labels are set when certain network services are accessed. The labeling is then transferred between processes and system resources as a result of either access or execution. We also defined a language for creating labeling rules, and demonstrated how the system can be used to prevent attacks that attempt to cross service boundaries. Experimental evaluation shows that the implementation introduces little overhead. Our security solution is orthogonal to other protection schemes and provides a critical defense for the growing problem of cell phone viruses and worms
4680884
Statistical Causality Analysis of INFOSEC Alert Data
With the increasingly widespread deployment of security mechanisms, such as firewalls, intrusion detection systems (IDSs), antiviras software and authentication services, the problem of alert analysis has become very important. The large amount of alerts can overwhelm security administrators and prevent them from adequately understanding and analyzing the security state of the network, and initiating appropriate response in a timely fashion. Recently, several approaches for alert correlation and attack scenario analysis have been proposed. However, these approaches all have limited capabilities in detecting new attack scenarios. In this paper, we study the problem of security alert correlation with an emphasis on attack scenario analysis. In our framework, we use clustering techniques to process low-level alert data into high-level aggregated alerts, and conduct causal analysis based on statistical tests to discover new relationships among attacks. Our statistical causality approach complements other approaches that use hard-coded prior knowledge for pattern matching. We perform a series of experiments to validate our method using DARPA’s Grand Challenge Problem (GCP) datasets, the 2000 DARPA Intrusion Detection Scenario datasets, and the DEF CON 9 datasets. The results show that our approach can discover new patterns of attack relationships when the alerts of attacks are statistically correlated.
2157536
A framework for constructing features and models for intrusion detection systems
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.
14599729
Combining Indexing Technique with Path Dictionary for Nested Object Queries
A path dictionary encodes the connections among objects in the aggregation hierarchy. It has been shown to be an efficient mechanism for supporting nested object queries [6]. In this paper, we present a new method, called the path dictionary index method, which combines indexing techniques with the path dictionary method. We describe the operations of the new mechanism and develop cost modeis for its storage overhead and query and update costs. Finally, we compare the new mechanism to the path index method 131. The result shows that the path dictionary index method is significantly better than the path index method over a wide range of parameters.
1981600
Distributed caching of multi-dimensional data in mobile environments
Caching has been an important technique for saving network traffic and reducing response time, especially in mobile environments where bandwidth is often a scarce resource. In this paper, we propose a novel approach for caching multidimensional data in a cluster of mobile devices. In particular, we focus on the most common types of multi-dimensional queries, namely range and k-nearest neighbor queries, by computing a cacheable region for every query, caching the result at the client, and indexing it in an R*-tree at the cluster gateway. Subsequent queries are first issued to the R*-tree and only remainder queries or queries that cannot be guaranteed exact answers are sent to the remote data server. To the best of our knowledge, our work is the first to study caching results from complex multi-dimensional queries (e.g., kNN query) and propose to build an R*-tree on previously fetched query results in a cluster of mobile devices. Rigorous experiments show that our approach significantly reduces network traffic and response time.
2559830
Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm
As a sub-procedure our algorithm executes the Berlekamp/Massey algorithm on a sequence of large integers or polynomials. We give a fraction-free version of the Berlekamp/Massey algorithm, which does not require rational numbers or functions and GCD operations on the arising numerators and denominators. The relationship between the solution of Toeplitz systems, Padé approximations, and the Euclidean algorithm is classical. Fraction-free versions [3] can be obtained from the subresultant PRS algorithm [2]. Dornstetter [6] gives an interpretation of the Berlekamp/Massey algorithm as a partial extended Euclidean algorithm. We map the subresultant PRS algorithm onto Dornstetter's formulation. We note that the Berlekamp/Massey algorithm is more efficient than the classical extended Euclidean algorithm.
14432130
An effective hardware architecture for bump mapping using angular operation
In this paper, we propose an effective bump mapping algorithm that utilizes the reference space with the polar coordinate system and also propose a new hardware architecture associated with the proposed bump mapping algorithm. The proposed architecture reduces the computations to transform the vectors from the object space into the reference space by using a new vector rotation method. It also reduces the computations for the illumination calculation by using the law of cosine. Compared with the previous approaches, the proposed architecture reduces multiplication operations up to 78%.
14613627
Spatial Index on Air
With the advent of wireless networking and personal digital devices, the population of mobile users will increase significantly. Broadcasting is particularly suitable for environments having a large number of clients. In this paper, we study the query processing of some typical location-dependent queries, such as window queries and kNN queries, in a broadcast system. To reduce clients' power consumption and provide efficient services, a transformation of the objects is applied based on Hilbert curve. Furthermore, a linear index structure is constructed and several algorithms are devised to answer spatial queries. Experiments are conducted to evaluate the performance of the proposed transformation and related algorithms. Results show that the proposed schemes outperform existing algorithms significantly.