AN AGENT BASED INTRUSION DETECTION, RESPONSE AND BLOCKING USING SIGNATURE METHOD IN ACTIVE NETWORKS
As attackers use automated methods to inflict widespread damage on vulnerable systems connected to the network, it has become painfully clear that traditional manual methods of protection do not suffice. This paper discusses an intrusion prevention approach, intrusion detection, response based on active networks that helps to provide rapid response to vulnerability advisories.
A intrusion detection and intrusion blocker that can provide interim protection against a limited and changing set of high-likelihood or high-priority threats. It is expected that this mechanism would be easily and adaptively configured and deployed to keep pace with the ever-evolving threats on the network, intrusion detection and response based on agent system, digital signature used to provide a security.
Active networks are an exciting development in networking services in which the infrastructure provides customizable network services to packets. The custom network services can be deployed by the user inside the packets themselves. In this paper we propose the use of agent based intrusion detection and response. Agents are integrated with the collaborative IDS in order to provide them with a wider array of information to use their response activities.Keywords: intrusion detection, blocking, response, agents, digital signature.
A NEAR-OPTIMAL MULTICAST SCHEME FOR MOBILE AD HOC NETWORKS USING A HYBRID GENETIC ALGORITHM
Multicast routing is an effective way to communicate among multiple hosts in a network. It outperforms the basic broadcast strategy by sharing resources along general links, while sending information to a set of predefined multiple destinations concurrently. However, it is vulnerable to component failure in ad hoc network due to the lack of redundancy, multiple paths and multicast tree structure. Tree graph optimization problems (GOP) are usually difficult and time consuming NP- hard or NP-complete problems. Genetic algorithms (GA) have been proven to be an efficient technique for solving the GOP, in which well-designed chromosomes and appropriate operators are key factors that determine the performance of the GAs. Limited link, path constraints, and mobility of network hosts make the multicast routing protocol design particularly challenging in wireless ad hoc networks. Encoding trees is a critical scheme in GAs for solving these problems because each code should represent a tree. Prufer number is the most representative method of vertex encoding, which is a string of n-2 integers and can be transformed to an n-node tree. However, genetic algorithm based on Prufer encoding (GAP) does not preserve locality, while changing one element of its vector causes dramatically change in its corresponding tree topology. In this paper, we propose a novel GA based on sequence and topology encoding (GAST) for multicast protocol is introduced for multicast routing in wireless ad hoc networks and generalizes the GOP of tree-based multicast protocol as well as three associated operators. It has revealed an efficient method of the reconstruction of multicast tree topology and the experimental results demonstrated the effectiveness of GAST compare to GAP technique.
A NOVEL SECURE COMMUNICATION PROTOCOL FOR AD HOC NETWORKS [SCP]
An ad hoc network is a self organized entity with a number of mobile nodes without any centralized access point and also there is a topology control problem which leads to high power consumption and no security, while routing the packets between mobile hosts. Authentication is one of the important security requirements of a communication network. The common authentication schemes are not applicable in Ad hoc networks.
In this paper, we propose a secure communication protocol for communication between two nodes in ad hoc networks. This is achieved by using clustering techniques. We present a novel secure communication framework for ad hoc networks (SCP); which describes authentication and confidentiality when packets are distributed between hosts with in the cluster and between the clusters. These cluster head nodes execute administrative functions and network key used for certification. The cluster head nodes (CHs) perform the major operations to achieve our SCP framework with help of Kerberos authentication application and symmetric key cryptography technique, which will be secure, reliable, transparent and scalable and will have less overhead.
Security, Authentication, Confidentiality, Clustering.
IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 5, NO. 1, JANUARY-MARCH 2008
CONTROLLING IP SPOOFING THROUGH INTERDOMAIN PACKET FILTERS
The Distributed Denial-of-Service (DDoS) attack is a serious threat to the legitimate use of the Internet. Prevention mechanisms are thwarted by the ability of attackers to forge or spoof the source addresses in IP packets. By employing IP spoofing, attackers can evade detection and put a substantial burden on the destination network for policing attack packets.
In this paper, we propose an interdomain packet filter (IDPF) architecture that can mitigate the level of IP spoofing on the Internet. A key feature of our scheme is that it does not require global routing information. IDPFs are constructed from the information implicit in Border Gateway Protocol (BGP) route updates and are deployed in network border routers.
We establish the conditions under which the IDPF framework correctly works in that it does not discard packets with valid source addresses. Based on extensive simulation studies, we show that, even with partial deployment on the Internet, IDPFs can proactively limit the spoofing capability of attackers.
In addition, they can help localize the origin of an attack packet to a small number of candidate networks.
IP spoofing, DDoS, BGP, network-level security and protection, routing protocols
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 38, NO. 3, MAY 2008
A NEW MODEL FOR SECURE DISSEMINATION OF XML CONTENT
The paper proposes an approach to content dissemination that exploits the structural properties of an Extensible Markup Language (XML) document object model in order to provide an efficient dissemination and at the same time assuring content integrity and confidentiality. Our approach is based on the notion of encrypted postorder numbers that support the integrity and confidentiality requirements of XML content as well as facilitate efficient identification, extraction, and distribution of selected content portions. By using such notion, we develop a structurebased routing scheme that prevents information leaks in the XML data dissemination, and assures that content is delivered to users according to the access control policies, that is, policies specifying which users can receive which portions of the contents. Our proposed dissemination approach further enhances such structure based, policy-based routing by combining it with multicast in order to achieve high efficiency in terms of bandwidth usage and speed of data delivery, thereby enhancing scalability. Our dissemination approach thus represents an efficient and secure mechanism for use in applications such as publish–subscribe systems for XML Documents. The publish–subscribe model restricts the consumer and document source information to the routers to which they register with. Our framework facilitates dissemination of contents with varying degrees of confidentiality and integrity requirements in a mix of trusted and untrusted networks, which is prevalent in current settings across enterprise networks and the web. Also, it does not require the routers to be aware of any security policy in the sense that the routers do not need to implement any policy related to access control.
Encryption, Extensible Markup Language (XML), postorder traversal, preorder traversal, publish–subscribe, security, structure-based routing, trees
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. -, NO. 2, FEBRUARY 2008
BANDWIDTH EFFICIENT VIDEO MULTICASTING IN MULTIRADIO MULTICELLULAR WIRELESS NETWORKS
In this paper, we propose a new mechanism to select the cells and the wireless technologies for layer-encoded video multicasting in the heterogeneous wireless networks. Different from the previous mechanisms, each mobile host in our mechanism can select a different cell with a different wireless technology to subscribe each layer of a video stream, and each cell can deliver only a subset of layers of the video stream to reduce the bandwidth consumption. We formulate the Cell and Technology Selection Problem (CTSP) to multicast each layer of a video stream as an optimization problem. We use Integer Linear Programming to model the problem and show that the problem is NP-hard. To solve the problem, we propose a distributed algorithm based on Lagrangean relaxation and a protocol based on the proposed algorithm. Our mechanism requires no change of the current video multicasting mechanisms and the current wireless network infrastructures. Our algorithm is adaptive not only to the change of the subscribers at each layer, but also the change of the locations of each mobile host.
Multicast, layer-encoded video, heterogeneous wireless networks
DISTRIBUTED CACHE UPDATING FOR THE DYNAMIC SOURCE ROUTING PROTOCOL
On-demand routing protocols use route caches to make routing decisions. Due to mobility, cached routes easily become stale. To address the cache staleness issue, prior work in DSR used heuristics with ad hoc parameters to predict the lifetime of a link or a route. However, heuristics cannot accurately estimate timeouts because topology changes are unpredictable. In this paper, we propose proactively disseminating the broken link information to the nodes that have that link in their caches. We define a new cache structure called a cache table and present a distributed cache update algorithm. Each node maintains in its cache table the information necessary for cache updates. When a link failure is detected, the algorithm notifies all reachable nodes that have cached the link in a distributed manner. The algorithm does not use any ad hoc parameters, thus making route caches fully adaptive to topology changes. We show that the algorithm outperforms DSR with path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches. We conclude that proactive cache updating is key to the adaptation of on-demand routing protocols to mobility.
Mobile ad hoc networks, On-demand routing protocols, Mobility,Distributed cache updating
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 6, NO. 5, MAY 200-
AN ACKNOWLEDGMENT-BASED APPROACH FOR THE DETECTION OF ROUTING MISBEHAVIOR IN MANETS
We study routing misbehavior in MANETs (Mobile Ad Hoc Networks) in this paper. In general, routing protocols for MANETs are designed based on the assumption that all participating nodes are fully cooperative. However, due to the open structure and scarcely available battery- based energy, node misbehaviors may exist. One such routing misbehavior is that some selfish nodes will participate in the route discovery and maintenance processes but refuse to forward data packets. In this paper, we propose the 2ACK scheme that serves as an add-on technique for routing schemes to detect routing misbehavior and to mitigate their adverse effect. The main idea of the 2ACK scheme is to send two-hop acknowledgment packets in the opposite direction of the routing path. In order to reduce additional routing overhead, only a fraction of the received data packets are acknowledged in the 2ACK scheme. Analytical and simulation results are presented to evaluate the performance of the proposed scheme.
Mobile Ad Hoc Networks (MANETs), routing misbehavior, node misbehavior, network security, Dynamic Source Routing (DSR).
IMAGE TRANSFORMATION USING GRID
The objective of this paper is to design and implement an algorithm to transform an available 2D image into a 3D image. Since the available algorithms are time consuming enhance the efficiency, Grid computing has been used to implement the same. Grid computing phenomenon can be defined as “A paradigm/infrastructure that enabling the sharing, selection, & aggregation of geographically distributed resources”. Images captured by devices such as digital camera are generally of two dimensional in nature. But to analyze the images that too in engineering applications the same two-dimensional image if transformed into a three-dimensional image without appreciable data loss will be very useful and effective for analysis. Conventionally there are some software packages available for converting a 2D image to 3D image. In java graphics API (jdk 1.5) a package for 2D to 3D is there with defined methods for generating algorithms. But when such an algorithm is being designed and developed it was found that it consumed much time for execution.So a new approach is used here for running such an algorithm over the concept of grid. To illustrate the phenomenon we have developed software which transforms a two dimensional objects to three dimensional objects. In this module, Grid computing has been employed as a platform since it is a rapidly developing field. Grid computing will be very useful in projects where complexity and time factors are essential. It can also be used effectively to improve the overall system efficiency.
Grid service, Event, Object, Heterogeneity, Data sets, patterns, concept hierarchies, Load distribution
IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 4, NO. 1, JANUARY-MARCH 2007
HYBRID INTRUSION DETECTION WITH WEIGHTED SIGNATURE GENERATION OVER ANOMALOUS INTERNET EPISODES
This paper reports the design principles and evaluation results of a new experimental hybrid intrusion detection system (HIDS). This hybrid system combines the advantages of low false-positive rate of signature-based intrusion detection system (IDS) and the ability of anomaly detection system (ADS) to detect novel unknown attacks. By mining anomalous traffic episodes from Internet connections, we build an ADS that detects anomalies beyond the capabilities of signature-based SNORT or Bro systems. A weighted signature generation scheme is developed to integrate ADS with SNORT by extracting signatures from anomalies detected. HIDS extracts signatures from the output of ADS and adds them into the SNORT signature database for fast and accurate intrusion detection. By testing our HIDS scheme over real-life Internet trace data mixed with 10 days of Massachusetts Institute of Technology/ Lincoln Laboratory (MIT/LL) attack data set, our experimental results show a 60 percent detection rate of the HIDS, compared with 30 percent and 22 percent in using the SNORT and Bro systems, respectively. This sharp increase in detection rate is obtained with less than 3 percent false alarms. The signatures generated by ADS upgrade the SNORT performance by 33 percent. The HIDS approach proves the vitality of detecting intrusions and anomalies, simultaneously, by automated data mining and signature generation over Internet connection episodes.
Network security, intrusion detection systems, anomaly detection, signature generation, SNORT and Bro systems, false alarms, Internet episodes, traffic data mining.
SCALABLE MULTICASTING IN MOBILE AD HOC NETWORKS
Chao Gui and Prasant Mohapatra, Department of Computer Science, University of California, Davis
Many potential applications of Mobile Ad hoc Networks (MANETs) involve group communications among the nodes. Multicasting is an useful operation that facilitates group communications. Efficient and scalable multicast routing in MANETs is a difficult issue. In addition to the conventional multicast routing algorithms, recent protocols have adopted the following new approaches: overlays, backbone-based, and stateless. In this paper, we study these approaches from the protocol state management point of view, and compare their scalability behaviors. To enhance performance and enable scalability, we have proposed a framework for hierarchical multicasting in MANET environments. Two classes of hierarchical multicasting approaches, termed as domain-based and overlay-based, are proposed. We have considered a variety of approaches that are suitable for different mobility patterns and multicast group sizes. Results obtained through simulations demonstrate enhanced performance and scalability of the proposed techniques.
Hierarchical multicasting, Mobile Ad hoc networks, Domain-based multicasting, Overlay multicasting, Stateless multicasting, Scalability
APPLICATION OF BPCS STEGANOGRAPHY TO WAVELET COMPRESSED VIDEO
This paper presents a steganography method using lossy compressed video which provides a natural way to send a large amount of secret data. The proposed method is based on wavelet compression for video data and bit-plane complexity segmentation (BPCS) steganography. In waveletbased video compression methods such as 3-D set partitioning in hierarchical trees (SPIHT) algorithm and Motion- JPEG2000, wavelet coefficients in discrete wavelet transformed video are quantized into a bit-plane structure and therefore BPCS steganography can be applied in the wavelet domain. 3-D SPIHT-BPCS steganography and Motion- JPEG2000-BPCS steganography are presented and tested, which are the integration of 3-D SPIHT video coding and BPCS steganography, and that of Motion-JPEG2000 and BPCS, respectively. Experimental results show that 3-D SPIHT-BPCS is superiorto Motion-JPEG2000-BPCS performance. with regard to embedding
ODAM: AN OPTIMIZED DISTRIBUTED ASSOCIATION RULE MINING ALGORITHM
Association rule mining is an active data mining research area. However, most ARM algorithms cater to a centralized environment. In contrast to previous ARM algorithms, ODAM is a distributed algorithm for geographically distributed data sets that reduces communication costs. Modern organizations are geographically distributed. Typically, each site locally stores its ever increasing amount of day-to-day data. Using centralized data mining to discover useful patterns in such organizations’ data isn’t always feasible because merging data sets from different sites into a centralized site incurs huge network communication costs. Data from these organizations are not only distributed over various locations but also vertically fragmented, making it difficult if not impossible to combine them in a central location. Distributed data mining has thus emerged as an active subarea of data mining research. A significant area of data mining research is association rule mining. Unfortunately, most ARM algorithms 1-9 focus on a sequential or centralized environment where no external communication is required. Distributed ARM algorithms, on the other hand, aim to generate rules from different data sets spread over various geographical sites; hence, they require external communications throughout the entire process. DARM algorithms must reduce communication costs so that generating global association rules costs less than combining the participating sites’ data sets into a centralized site. However, most DARM algorithms don’t have an efficient message optimization technique, so they exchange numerous messages during the mining process. We have developed a distributed algorithm, called Optimized Distributed Association Mining, for geographically distributed data sets. ODAM generates support counts of candidate itemsets quicker than other DARM algorithms and reduces the size of average transactions, data sets, and message exchanges.
INCREMENTAL SERVICE DEPLOYMENT USING THE HOP BY HOP MULTICAST ROUTING PROTOCOL
IP Multicast is facing a slow take-off although it is a hotly debated topic since more than a decade. Many reasons are responsible for this status. Hence, the Internet is likely to be organized with both unicast and multicast enabled networks. Thus, it is of utmost importance to design protocols that allow the progressive deployment of the multicast service by supporting unicast clouds. This paper presents HBH (Hop-By- Hop multicast routing protocol). HBH adopts the source-specific channel abstraction to simplify address allocation and implements data distribution using recursive unicast trees, which allow the transparent support of unicast-only routers. An important original feature of HBH is its tree construction algorithm that takes into account the unicast routing asymmetries. Since most multicast routing protocols rely on the unicast infrastructure, the unicast asymmetries impact the structure of the multicast trees. We show through simulation that HBH outperforms other multicast routing protocols in terms of the delay experienced by the receivers and the bandwidth consumption of the multicast trees. Additionally, we show that HBH can be incrementally deployed and that with a small fraction of HBH-enabled routers in the network HBH outperforms application-layer multicast.
Multicast, routing, service deployment
IEEE/ACM TRANSACTIONS ON NETWORKING VOL. 12, NO. 1, FEBRUARY 2004
A DISTRIBUTED DATABASE ARCHITECTURE FOR GLOBAL ROAMING IN NEXT- GENERATION MOBILE NETWORKS
The next-generation mobile network will support terminal mobility, personal mobility, and service provider portability, making global roaming seamless. A location-independent personal telecommunication number (PTN) scheme is conducive to implementing such a global mobile system. However, the nongeographic PTNs coupled with the anticipated large number of mobile users in future mobile networks may introduce very large centralized databases. This necessitates research into the design and performance of high-throughput database technologies used in mobile systems to ensure that future systems will be able to carry efficiently the anticipated loads. This paper proposes a scalable, robust, efficient location database architecture based on the location- independent PTNs. The proposed multitree database architecture consists of a number of database subsystems, each of which is a three-level tree structure and is connected to the others only through its root. By exploiting the localized nature of calling and mobility patterns, the proposed architecture effectively reduces the database loads as well as the signaling traffic incurred by the location registration and call delivery procedures. In addition, two memory-resident database indices, memory- resident direct file and T-tree, are proposed for the location databases to further improve their throughput. Analysis model and numerical results are presented to evaluate the efficiency of the proposed database architecture. Results have revealed that the proposed database architecture for location management can effectively support the anticipated high user density in the future mobile networks.
Database architecture, location management, location tracking, mobile networks.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE – VOL. 27, NO. 3, MARCH 2005
FACE RECOGNITION USING LAPLACIANFACES
We propose an appearance-based face recognition method called the Laplacianface approach. By using Locality Preserving Projections (LPP), the face images are mapped into a face subspace for analysis. Different from Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) which effectively see only the Euclidean structure of face space, LPP finds an embedding that preserves local information, and obtains a face subspace that best detects the essential face manifold structure. The Laplacianfaces are the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the face manifold. In this way, the unwanted variations resulting from changes in lighting, facial expression, and pose may be eliminated or reduced.
Theoretical analysis shows that PCA, LDA, and LPP can be obtained from different graph models. We compare the proposed Laplacianface approach with Eigenface and Fisherface methods on three different face data sets. Experimental results suggest that the proposed Laplacianface approach provides a better representation and achieves lower error rates in face recognition.
Face recognition, principal component analysis, linear discriminant analysis, locality preserving projections, face manifold, subspace learning.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 1, JANUARY 2004
ONLINE HANDWRITTEN SCRIPT RECOGNITION
Automatic identification of handwritten script facilitates many important applications such as automatic transcription of multilingual documents and search for documents on the Web containing a particular script. The increase in usage of handheld devices which accept handwritten input has created a growing demand for algorithms that can efficiently analyze and retrieve handwritten data. This paper proposes a method to classify words and lines in an online handwritten document into one of the six major scripts: Arabic, Cyrillic, Devnagari, Han, Hebrew, or Roman. The classification is based on 11 different spatial and temporal features extracted from the strokes of the words. The proposed system attains an overall classification accuracy of 8-.1 percent at the word level with 5-fold cross validation on a data set containing 13,379 words. The classification accuracy improves to 95 percent as the number of words in the test sample is increased to five, and to 95.5 percent for complete text lines consisting of an average of seven words.
Document understanding, handwritten script identification, online document, evidence accumulation, feature design.
LOCATION-AIDED ROUTING (LAR) IN MOBILE AD HOC NETWORKS
A mobile ad hoc network consists of wireless hosts that may move often. Movement of hosts results in a change in routes, requiring some mechanism for determining new routes. Several routing protocols have already been proposed for ad hoc networks. This paper suggests an approach to utilize location information (for instance, obtained using the global positioning system) to improve performance of routing protocols for ad hoc networks. By using location information, the proposed Location-Aided Routing (LAR) protocols limit the search for a new route to a smaller “request zone” of the ad hoc network. This results in a significant reduction in the number of routing messages. We present two algorithms to determine the request zone, and also suggest potential optimizations to our algorithms
IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 11, NO. 4, AUGUST 2003
NOISE REDUCTION BY FUZZY IMAGE FILTERING
A new fuzzy filter is presented for the noise reduction of images corrupted with additive noise. The filter consists of two stages. The first stage computes a fuzzy derivative for eight different directions. The second stage uses these fuzzy derivatives to perform fuzzy smoothing by weighting the contributions of neighboring pixel values. Both stages are based on fuzzy rules which make use of membership functions. The filter can be applied iteratively to effectively reduce heavy noise. In particular, the shape of the membership functions is adapted according to the remaining noise level after each iteration, making use of the distribution of the homogeneity in the image. Astatistical model for the noise distribution can be incorporated to relate the homogeneity to the adaptation scheme of the membership functions. Experimental results are obtained to show the feasibility of the proposed approach. These results are also compared to other filters by numerical measures and visual inspection.
Additive noise, edge preserving filtering, fuzzy image filtering, noise reduction.
ITP: AN IMAGE TRANSPORT PROTOCOL FOR THE INTERNET
Images account for a significant and growing fraction of Web downloads. The traditional approach to transporting images uses TCP, which provides a generic reliable in-order bytestream abstraction, but which is overly restrictive for image data. We analyze the progression of image quality at the receiver with time, and show that the in-order delivery abstraction provided by a TCP- based approach prevents the receiver application from processing and rendering portions of an image when they actually arrive. The end result is that an image is rendered in bursts interspersed with long idle times rather than smoothly. This paper describes the design, implementation, and evaluation of the image transport protocol (ITP) for image transmission over loss-prone congested or wireless networks. ITP improves user-perceived latency using application-level framing (ALF) and out-of order application data unit (ADU) delivery, achieving significantly better interactive performance as measured by the evolution of peak signal-to-noise ratio (PSNR) with time at the receiver. ITP runs over UDP, incorporates receiver-driven selective reliability, uses the congestion manager (CM) to adapt to network congestion, and is customizable for specific image formats (e.g., JPEG and JPEG2000). ITP enables a variety of new receiver post-processing algorithms such as error concealment that further improve the interactivity and responsiveness of reconstructed images. Performance experiments using our implementation across a variety of loss conditions demonstrate the benefits of ITP in improving the interactivity of image downloads at the receiver.
Computer networks, congestion control, Internetworking, network adaptation, selective reliability, transport protocols.
IEEE/ACM TRANSACTIONS ON NETWORKING VOL. 16, NO. 1, FEBRUARY 2008
EFFICIENT ROUTING IN INTERMITTENTLY CONNECTED MOBILE NETWORKS: THE MULTIPLE-COPY CASE
Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from the source to the destination. There are many real networks that follow this model, for example, wildlife tracking sensor networks, military networks, vehicular ad hoc networks, etc. In this context, conventional routing schemes fail, because they try to establish complete end-to-end paths, before any data is sent. To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention which can significantly degrade their performance. Furthermore, proposed efforts to reduce the overhead of flooding-based schemes have often been plagued by large delays. With this in mind, we introduce a new family of routing schemes that “spray” a few message copies into the network, and then route each copy independently towards the destination. We show that, if carefully designed, spray routing not only performs significantly fewer transmissions per message, but also has lower average delivery delays than existing schemes; furthermore, it is highly scalable and retains good performance under a large range of scenarios. Finally, we use our theoretical framework proposed in our 2004 paper to analyze the performance of spray routing.We also use this theory to show how to choose the number of copies to be sprayed and how to optimally distribute these copies to relays.
Ad hoc networks, delay tolerant networks, intermittent connectivity, routing
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 18, NO. 4, APRIL 2007
A FULLY DISTRIBUTED PROACTIVELY SECURE THRESHOLD-MULTISIGNATURE SCHEME
Threshold-multisignature schemes combine the properties of threshold group-oriented signature schemes and multisignature schemes to yield a signature scheme that allows a threshold or more group members to collaboratively sign an arbitrary message. In contrast to threshold group signatures, the individual signers do not remain anonymous, but are publicly identifiable from the information contained in the valid threshold-multisignature. The main objective of this paper is to propose such a secure and efficient threshold-multisignature scheme. The paper uniquely defines the fundamental properties of threshold multisignature schemes and shows that the proposed scheme satisfies these properties and eliminates the latest attacks to which other similar schemes are subject. The efficiency of the proposed scheme is analyzed and shown to be superior to its counterparts. The paper also proposes a discrete logarithm based distributed-key management infrastructure (DKMI), which consists of a round optimal, publicly verifiable, distributed-key generation (DKG) protocol and a one round, publicly verifiable, distributed-key redistribution/updating (DKRU) protocol. The round optimal DKRU protocol solves a major problem with existing secret redistribution/updating schemes by giving group members a mechanism to identify malicious or faulty share holders in the first round, thus avoiding multiple protocol executions.
Security and protection, distributed systems, group-oriented cryptography, threshold-multisignature, secret sharing, distributed-key management infrastructure, publicly verifiable distributed-key generation, publicly verifiable distributed-key update, publicly verifiable distributed-key redistribution
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 18, NO. 3, MARCH 2007
A NEW OPERATIONAL TRANSFORMATION FRAMEWORK FOR REAL-TIME GROUP EDITORS
Group editors allow a group of distributed human users to edit a shared multimedia document at the same time over a computer network. Consistency control in this environment must not only guarantee convergence of replicated data, but also attempt to preserve intentions of operations. Operational transformation (OT) is a well-established method for optimistic consistency control in this context and has drawn continuing research attention since 1989. However, counterexamples to previous works have often been identified despite the significant progress made on this topic over the past 15 years. This paper analyzes the root of correctness problems in OT and establishes a novel operational transformation framework for developing OT algorithms and proving their correctness.
Consistency control, group editors, groupware, operational transformation
ADAPTED ONE-VERSUS-ALL DECISION TREES FOR DATA STREAM CLASSIFICATION
Hashemi, S. Ying Yang Mirzamomen, Z. Kangavari, M., Monash Univ., Clayton, VIC
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 624-637, ISSN: 1041-4347, INSPEC Accession Number: 10520351,Digital Object Identifier: 10.1109/TKDE.2008.181, First Published: 2008-08-29
Current Version Published: 2009-03-24
One versus all (OVA) decision trees learn k individual binary classifiers, each one to distinguish the instances of a single class from the instances of all other classes. Thus OVA is different from existing data stream classification schemes whose majority use multiclass classifiers, each one to discriminate among all the classes. This paper advocates some outstanding advantages of OVA for data stream classification. First, there is low error correlation and hence high diversity among OVA’s component classifiers, which leads to high classification accuracy. Second, OVA is adept at accommodating new class labels that often appear in data streams. However, there also remain many challenges to deploy traditional OVA for classifying data streams. First, as every instance is fed to all component classifiers, OVA is known as an inefficient model. Second, OVA’s classification accuracy is adversely affected by the imbalanced class distribution in data streams. This paper addresses those key challenges and consequently proposes a new OVA scheme that is adapted for data stream classification. Theoretical analysis and empirical evidence reveal that the adapted OVA can offer faster training, faster updating and higher classification accuracy than many existing popular data stream classification algorithms.
BAYES VECTOR QUANTIZER FOR CLASS-IMBALANCE PROBLEM
Diamantini, C. Potena, D., Dipt. di Ing. Inf., Gestionale e dell’Autom., Universitd Politec. delle Marche, Ancona
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 638-651, ISSN: 1041-4347,
INSPEC Accession Number: 10520352, Current Version Published: 2009-03-24,
Digital Object Identifier: 10.1109/TKDE.2008.187, First Published: 2008-09-12
The class-imbalance problem is the problem of learning a classification rule from data that are skewed in favor of one class. On these datasets traditional learning techniques tend to overlook the less numerous class, at the advantage of the majority class. However, the minority class is often the most interesting one for the task at hand. For this reason, the class-imbalance problem has received increasing attention in the last few years. In the present paper we point the attention of the reader to a learning algorithm for the minimization of the average misclassification risk. In contrast to some popular class-imbalance learning methods, this method has its roots in statistical decision theory. A particular interesting characteristic is that when class distributions are unknown, the method can work by resorting to stochastic gradient algorithm. We study the behavior of this algorithm on imbalanced datasets, demonstrating that this principled approach allows obtaining better classification performances compared to the principal methods proposed in the literature.
CATCHING THE TREND: A FRAMEWORK FOR CLUSTERING CONCEPT-DRIFTING CATEGORICAL DATA
Hung-Leng Chen Ming-Syan Chen Su-Chen Lin, Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 652-665,
ISSN: 1041-4347, INSPEC Accession Number: 10520353, Current Version Published: 2009-03-24,
Digital Object Identifier: 10.1109/TKDE.2008.192, First Published: 2008-09-19
Sampling has been recognized as an important technique to improve the efficiency of clustering. However, with sampling applied, those points that are not sampled will not have their labels after the normal process. Although there is a straightforward approach in the numerical domain, the problem of how to allocate those unlabeled data points into proper clusters remains as a challenging issue in the categorical domain. In this paper, a mechanism named MAximal Resemblance Data Labeling (abbreviated as MARDL) is proposed to allocate each unlabeled data point into the corresponding appropriate cluster based on the novel categorical clustering representative, namely, N-Nodeset Importance Representative (abbreviated as NNIR), which represents clusters by the importance of the combinations of attribute values. MARDL has two advantages: (1) MARDL exhibits high execution efficiency, and (2) MARDL can achieve high intracluster similarity and low intercluster similarity, which are regarded as the most important properties of clusters, thus benefiting the analysis of cluster behaviors. MARDL is empirically validated on real and synthetic data sets and is shown to be significantly more efficient than prior works while attaining results of high quality.
GRIDVIDEO: A PRACTICAL EXAMPLE OF NONSCIENTIFIC APPLICATION ON THE GRID
Bruneo, D. Iellamo, G. Minutoli, G. Puliafito, A., Dept. of Math., Univ. of Messina, Messina
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 666-680, ISSN: 1041-4347, INSPEC Accession Number: 10520354, Current Version Published: 2009-03-24,
Digital Object Identifier: 10.1109/TKDE.2008.191, First Published: 2008-09-19.
Starting from 1990s and until now, Grid computing has been mainly used in scientific laboratories. Only in the last few years, it is evolving into a business-innovating technology that is driving commercial adoption. In this paper, we describe GridVideo, a Grid-based multimedia application for the distributed tailoring and streaming of media files. The objective is to show, starting from a real experience, how Grid technologies can be used for the development of nonscientific applications. Relevant performance aspects are analyzed, regarding both user-oriented (in terms of responsiveness) and provider-oriented (in terms of system efficiency) requirements. Different multimedia data dissemination strategies have been analyzed and an innovative technique, based on the Fibonacci series, is proposed. To respond to the stringent quality-of-service (QoS) requirements, typical of soft real-time applications, a reservation-based architecture is presented. Such architecture is able to manage the Grid resource allocation, thus enabling the provisioning of advanced services with different QoS levels. Technical and practical problems encountered during the development are discussed, and a thorough performance evaluation of the developed prototype is presented.
HIERARCHICALLY DISTRIBUTED PEER-TO-PEER DOCUMENT CLUSTERING AND CLUSTER SUMMARIZATION
Hammouda, K.M. Kamel, M.S., Desire2Learn Inc., Kitchener, ON
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 681-698, ISSN: 1041-4347,
INSPEC Accession Number: 10520355, Digital Object Identifier: 10.1109/TKDE.2008.189,
First Published: 2008-09-19, Current Version Published: 2009-03-24
In distributed data mining, adopting a flat node distribution model can affect scalability. To address the problem of modularity, flexibility and scalability, we propose a Hierarchically-distributed Peer-to-Peer (HP2PC) architecture and clustering algorithm. The architecture is based on a multi-layer overlay network of peer neighborhoods. Supernodes, which act as representatives of neighborhoods, are recursively grouped to form higher level neighborhoods. Within a certain level of the hierarchy, peers cooperate within their respective neighborhoods to perform P2P clustering. Using this model, we can partition the clustering problem in a modular way across neighborhoods, solve each part individually using a distributed K-means variant, then successively combine clusterings up the hierarchy where increasingly more global solutions are computed. In addition, for document clustering applications, we summarize the distributed document clusters using a distributed keyphrase extraction algorithm, thus providing interpretation of the clusters. Results show decent speedup, reaching 165 times faster than centralized clustering for a 250-node simulated network, with comparable clustering quality to the centralized approach. We also provide comparisontotheP2PK-meansalgorithmandthat HP2PC accuracy is better for typical hierarchy heights. Results for distributed cluster summarization match those of their centralized counterparts with up to 88% accuracy.
EXACT KNOWLEDGE HIDING THROUGH DATABASE EXTENSION
Gkoulalas-Divanis, A. Verykios, V.S., Dept. of Comput. & Commun. Eng., Univ. of Thessaly, Volos;
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 699-713, ISSN: 1041-4347,
INSPEC Accession Number: 10520356, Digital Object Identifier: 10.1109/TKDE.2008.199,
First Published: 2008-09-26, Current Version Published: 2009-03-24
In this paper, we propose a novel, exact border-based approach that provides an optimal solution for the hiding of sensitive frequent itemsets by
(i) minimally extending the original database by a synthetically generated database part – the database extension,
(ii) formulating the creation of the database extension as a constraint satisfaction problem,
(iii) mapping the constraint satisfaction problem to an equivalent binary integer programming problem,
(iv) exploiting underutilized synthetic transactions to proportionally increase the support of non-sensitive itemsets,
(v) minimally relaxing the constraint satisfaction problem to provide an approximate solution close to the optimal one when an ideal solution does not exist, and (vi) by using a partitioning in the universe of the items to increase the efficiency of the proposed hiding algorithm.
Extending the original database for sensitive itemset hiding is proved to provide optimal solutions to an
extended set of hiding problems compared to previous approaches and to provide solutions of higher quality. Moreover, the application of binary integer programming enables the simultaneous hiding of the sensitive itemsets and thus allows for the identification of globally optimal solutions.
GLIP: A CONCURRENCY CONTROL PROTOCOL FOR CLIPPING INDEXING
Chang-Tien Lu Jing Dai Ying Jin Mathuria, J., Dept. of Comput. Sci., Virginia Tech., Falls Church, VA
This paper appears in: Knowledge and Data Engineering, IEEE Transactions on Publication Date: May 2009, Volume: 21, Issue: 5, On page(s): 714-728, ISSN: 1041-4347,
INSPEC Accession Number: 10520357, Digital Object Identifier: 10.1109/TKDE.2008.183,
First Published: 2008-09-12, Current Version Published: 2009-03-24
Multidimensional databases are beginning to be used in a wide range of applications. To meet this fast-growing demand, the R-tree family is being applied to support fast access to multidimensional data, for which the R+-tree exhibits outstanding search performance. In order to support efficient concurrent access in multiuser environments, concurrency control mechanisms for multidimensional indexing have been proposed. However, these mechanisms cannot be directly applied to the R+-tree because an object in the R+-tree may be indexed in multiple leaves. This paper proposes a concurrency control protocol for R-tree variants with object clipping, namely, Granular Locking for clipping indexing (GLIP). GLIP is the first concurrency control approach specifically designed for the R+- tree and its variants, and it supports efficient concurrent operations with serializable isolation, consistency, and deadlock-free. Experimental tests on both real and synthetic data sets validated the effectiveness and efficiency of the proposed concurrent access framework.