Distributed Computing and Internet Technology

Distributed Sensor networks have a wide range of real-time applications in aerospace, automation, defense, medical imaging, robotics, and weather prediction. Over the past several years, scientists, engineers, and researchers in a multitude of disciplines have been clamoring for more detailed information without much success. This new evolving technology can provide solutions to a variety of these technology related problems. Professor Iyengar in this talk will give an overview of these impact areas based on his experience in working with various industries like Oak ridge National Lab, Jet Propulsion Lab, and Naval Research Lab. His talk is also based on his experiences of working with scientists from Raytheon, Boeing during the last few years.

The Distributed Computing track of ICDCIT 2005 received 181 papers. Based on the review by the members of the Program Committee, 16 full and 9 short papers were selected for inclusion in the proceedings of the conference. The accepted papers cover a wide range of topics in Distributed Computing. Design of MAC protocol, network architecture and routing protocol for Wireless Ad-Hoc Networks seem to attract the attention of many researchers. 5 of the 16 accepted full papers fall in this area. The other popular areas include, Network Security, Sensor Networks, Fault Detection and Recovery and Grid Computing. Each of these areas will have at least 3 papers in the proceedings. The Distributed Computing track will also have papers in the areas of Cellular Networks, Peer-to-Peer Networks, Optical Networks, Information Retrieval, QoS and Mobile IP. We have put together a program that covers many important areas of Distributed Computing. We hope you will find the papers in this track informative, interesting and useful.

Mobile IP represents a global solution, providing mobility management for a wide variety of radio technologies, devices and applications. Significant research results relating to extensions for MIPv6 have been reported over the last several years. However practical and common issues exist within the technology, in particular, the specification of Binding Update Lifetime has a substantial impact on the system performance. In this paper, binding lifetime determination schemes are devised to obtain high energy-efficiency mobile nodes in HMIPv6. Some people may stay within some area for a long time and thus the related information can be very useful in decreasing the frequency of binding update messages. That is, if each user maintains a profile locally based on moving history; this can be very useful in fixing the lifetime in terms of current location. In addition, the resident time is occasionally affected by the daily arrival time as well as the subnet. Thus, we expand the scheme to consider the time region of arrival time per each subnet. We study the performance improvement of our schemes through extensive simulations.

Defending against distributed denial-of-service (DDoS) attack is one of the hardest security problems on the internet today. In this paper, we investigate a fast search algorithm for IP trace back, which is similar to the Viterbi algorithm and it has simple implementation. The approach is capable of tracking back attacks as quickly as possible. Our research can feature low network and router overhead, and support incremental deployment.

Token-based MAC(Medium Access Control) Protocols are proposed for WDM Burst-Switched Ring Network which consists of nodes using TT-TR(Tunable Transmitter-Tunable Receiver). The node architectures with TT-TR may make an efficient use of network resources, even though traffic pattern such as IP traffic with high self-similarity are dynamically changed, and can also support good expandability. However, MAC protocols suitable for TT-TR node architecture must be designed with consideration for various factors in order to use the limited resources of network efficiently. A variety of Token-based MAC protocols are suggested to increase the performance while reducing the processing overhead at each node. The performance of the MAC protocols are evaluated and compared in terms of average packet delay, channel utilization and burst loss rate through OPNET simulation. Finally, we provide insight into the design of MAC protocols by investigating the effect of various parameters.

Application of sensor networks in different fields is an interesting area to work with and has already drawn widespread attention. Since sensors have limited supply of on-board energy, efficient management of network is a compulsion in extending life of the sensor. At the same time, frequent damage to sensors and link failure occur because of the adverse environment in which they are deployed. A sensor network has to tolerate and recover from these failures themselves with no external help. In this respect, we have designed a self-stabilizing energy-aware routing protocol in a sensor network. Our protocol ensures the sensor network, starting from an arbitrary state, eventually set up reliable communication in network with minimum energy consumption and in a finite number of steps.

This paper presents a gradient routing algorithm a modified approach of DIR (compass routing) method to suit for mobile ad hoc network. It is a direction based localized algorithm where each node makes forwarding decisions solely based on the position of itself, its neighbors and destination. Source node selects a neighbor node to forward a message which is closest (having minimum gradient i.e. angle) towards the direction of destination. This algorithm makes use of the position information of nodes to improve the performance of routing protocols in mobile ad hoc network. The performance of gradient algorithms is compared with other directional routing algorithms LAR and DREAM in mobile environment using proactive approach. The experimental results show that gradient algorithm have higher success rate and lower flooding rate compared to LAR and DREAM

An important objective in designing a protocol is to save scarce resources like energy and bandwidth, and avoid the broadcast storm problem [1]. One way of addressing these problems is by forming a small virtual backbone. In this paper, we present a distributed clustering algorithm for forming a small backbone in ad-hoc network, based on connected dominating set. The time and message complexity of the algorithm is in

O

(

n

).

Clustering is a widely used approach to ease implementation of various problems such as routing and resource management in mobile ad hoc networks (MANET)s. We first look at minimum spanning tree(MST) based algorithms and then propose a new algorithm for clustering in MANETs. The algorithm we propose merges clusters to form higher level clusters by increasing their levels. We show the operation of the algorithm and analyze its time and message complexities.

Reducing power consumption and increasing battery life of nodes in an ad hoc network requires an integrated power control and routing strategy. To maximize the lifetime of mobile networks, the power consumption rate of each node must be evenly distributed. This objective alone cannot be satisfied by the use of routing algorithms proposed in previous work. In this paper a new route selection mechanism for MANET routing protocol, called as Self Organizing Routing (SOR). Self Organized Routing (SOR) algorithm is devised to enable high-energy nodes to participate in routing of data packets using a virtual backbone. Hence the lifetime and stability of the network is increased as nodes having high energy are involved in routing of packets. Based on the simulation results obtained using GloMoSim (simulator), it is observed that SOR algorithm increase the lifetime of mobile ad hoc networks and validate the environment suitable for the various techniques.

An algorithm for time division multiple access (TDMA) is found to be applicable in converting existing distributed algorithms into a model that is consistent with sensor networks. Such a TDMA service needs to be self-stabilizing so that in the event of corruption of assigned slots and clock drift, it recovers to states from where TDMA slots are consistent. Previous self-stabilizing solutions for TDMA are either randomized or assume that the topology is known upfront and cannot change. Thus, the question of feasibility of self-stabilizing deterministic TDMA algorithm where topology is unknown remains open.

In this paper, we present a self-stabilizing, deterministic algorithm for TDMA in networks where a sensor is aware of only its neighbors. This is the first such algorithm that achieves these properties. Moreover, this is the first algorithm that demonstrates the feasibility of stabilization-preserving, deterministic transformation of a shared memory distributed program on an arbitrary topology into a program that is consistent with the sensor network model.

In this paper, we investigate the communication performance of one-dimensional cellular networks from the viewpoint of the mobile node’s speed with the simulation method assuming various types of speed distributions. Simulation results are measured as blocking probabilities of both new and handoff calls and call completion probability. We can observe the phenomenon that blocking probabilities of both new and handoff calls are not related to the mobile node’s speed distribution, but the call completion probability concerns with that under overloaded situation when the blocking probabilities are not small.

In this paper, a distributed technique is proposed to assign time slots to the nodes of an ad hoc network for Spatial Time Division Media Access (STDMA) to facilitate collision-free communication. An upper bound is established on the length of the time cycle assuming a constant bound on the degree of each node. The proposed algorithm is augmented to adapt with incremental changes in the topology.

Let

P

be a polygonal region which is forbidden in order to place a base station in the context of mobile communication. Our objective is to place one base station at any point on the boundary of

P

or two base stations at some specified edge and assign a range such that every point in the region is covered by those base stations and the maximum range assigned to these base stations is minimum among all such possible choice of base stations. Here we consider the forbidden region

P

as convex and base station can be placed on the boundary of the region. We present optimum linear time algorithms for these problems.

The growth of the internet provides opportunities for cooperative computation, it also requires development of protocols that can accomplish this task among mutually untrusting parties. The aim is to develop methods which ensure both the correct evaluation of the function and privacy of individual inputs. Multiparty Computation protocols help to achieve the aim without using a trusted third party.

In this paper we consider the problem of context-free language recognition in a two-party setting. Alice has the description of a context-free language

L

while Bob has a secret string whose membership in

L

is to be checked. Neither Alice nor Bob is ready to disclose his/her input to the other. Here we propose a protocol which accomplishes secure two party context-free language recognition. The novelty of this paper lies in the use of formal languages based approach for multiparty computations.

Because all vulnerabilities of a network cannot be realized, and penetration of the system cannot always be prevented, intrusion detection systems have become necessary to ensure the security of a network. The intrusion detection systems need to be accurate, adaptive, and extensible. Given these requirements and the complexities of today’s network environments, the design of an intrusion detection system has become a very challenging task. A great deal of research has been conducted on intrusion detection in a distributed environment to circumvent the problems of centralized approaches. However, distributed intrusion detection systems suffer from a number of drawbacks e.g., high rates of false positives, low efficiency etc. In this paper, we propose the architecture of a fully distributed intrusion detection system that uses a set of autonomous but cooperating agents. The system has also the capability of isolating compromised nodes from intrusion detection activity thereby ensuring fault-tolerance in computation.

In this paper, we consider a contaminated network with an intruder. The task for the mobile agents is to decontaminate all hosts while preventing a recontamination and to do so as efficiently as possible. We study under what conditions and what cost a team of mobile agents can do this in synchronous arbitrary regular graphs using the breadth-first-search strategy. Due to the nature of the experiment we use a genetic algorithm to find the minimum number of agents required to decontaminate a given network. The results show that there is a relation between the degree, the size of the graph, and the number of starting locations of the mobile agents. in particular, this relation demonstrates the possibility of improvements in reducing the number of mobile agents used depending on the number of starting location in arbitrary regular graphs.

Keywords:

Mobile Agents, Intruder Capture, Graph Search, Mesh.

In mobile distributed systems data broadcasting is widely used as a data dissemination solution, where we need an indexing scheme in order to energy-efficiently access the wireless data. In conventional indexing schemes, they use key attribute values and construct tree-structured index. Therefore, the conventional indexing schemes do not support content-based retrieval queries such as partial-match queries, range-queries, and so on. In this paper we propose an index method which supports content-based retrieval queries on wireless broadcast data stream. For this purpose, we construct a tree-structured index which is composed of bit-vectors, where the bit-vectors are generated from data records through multi-attribute hashing.

In this paper, we present a tool, called

Autoprofiler

, that automates the discovery of resource consumption by transactions on distributed systems. Such information is required as input to performance analysis tools, which may be used for capacity planning, for re-architecting a distributed system, or to identify potential bottlenecks. Deriving this information using existing tools is a tedious and error prone process. In contrast, our tool requires minimal human intervention, and brings down the time required to profile complex distributed systems to a few minutes. It does this by co-ordinating the process of load generation and server resource profiling. Our tool also works with a Java profiler, called

LiteJava Profiler

, which we have built, to fully automate the process of resource consumption discovery for J2EE servers.

To continuously log messages in the limited volatile memories of their sending processes, existing SBML protocols force the processes to periodically flush the message log into the stable storage or messages in the log to be useless for future failures and then removes them. But, these garbage collection algorithms may result in a large number of stable storage accesses or high communication and checkpointing overheads as inter-process communication rate increases. To address this problem, we propose an efficient algorithm to autonomously remove useless log information in its volatile storage by piggybacking only some additional information. It requires no extra message and forced checkpoint. Additionally, the algorithm efficiently supports fast commit of all output to the outside world. Simulation results show that our algorithm considerably outperforms the traditional algorithm with respect to the average elapsed time required until the memory buffer for message logging of a process is full.

We revisit the work of Chandra and Toueg on achieving

consensus

using

unreliable failure detectors

in an asynchronous system with crash stop failures. Following a brief review of their approach, we provide a probabilistic analysis of their consensus algorithm, which shows that the number of messages is exponentially proportional to the number of participating processes

n

. Based on our analysis, we study how their solution may be improved when we have

a priori

knowledge of the maximum number of process failures that may occur. Accordingly, we propose

multi-level consensus

as a generalization of the Chandra-Toueg algorithm, and give a probabilistic analysis of our algorithm. For

n

large relative to the bound on the number of failures

k

, this approach yields an improvement (in the expected case) in the message complexity.

In this paper, we consider the problem of multiple hypothesis testing by a bandwidth and power constrained sensor network with a fusion center. We propose a scheme, where each sensor is restricted to send a 1-bit message to fusion center and the fusion center collates the bits sent by all the sensors and makes a decision about the hypothesis. We analyze the performance of our scheme and illustrate it with an example.

The purpose of distributed system-level diagnosis is to have each fault-free nodes determine the state of all nodes of system. The paper presents a Multi-level distributed system-level diagnosis, which considers the problem of achieving scalability and performance tuning for distributed diagnosis. Existing work is aimed to reduce either diagnosis latency or network utilization but scales poorly. A diagnosis algorithm, called Multi-level DSD, is presented to provide scalability, which controls both latency and network utilization in fully connected networks. The algorithm is scalable in the sense that it is possible to diagnose system with large number of processing elements (nodes) by tuning diagnosis parameters. The diagnosis algorithm allows tuning of diagnosis performance to lever latency message cost trade-off. Multi-level DSD divides system in clusters of nodes, where each cluster is either a single node or a group of clusters. Cluster diagnoses itself by running a cluster diagnosis algorithm between its sub clusters. Clusters at each level runs same cluster diagnosis algorithm.

The problem of global state observation is fundamental to distributed systems. All interactions in distributed systems can be analyzed in terms of the building block formed by the pairwise interactions of intervals between two processes. Considering causality-based pairwise interactions by which two intervals at different processes may interact with each other, there are 40 possible orthogonal interactions. This paper examines the problem: “If a global state of interest to an application is specified in terms of the pairwise interaction types between each pair of processes, how can such a global state be detected?” A solution identifies a global state in which the relation specified for each process pair is satisfied. This paper formulates the specific conditions on the exact communication structures to determine which of the intervals being examined at any time may never satisfy the stipulated relation for that pair of processes, and therefore that interval must be deleted.

In this paper, we propose a packet-level parallel data transfer and a Two-Phase Scheduling(TPS) algorithm for collective communication primitives in MPICH-G2. The algorithms are characterized by two unique features: 1) a concurrent data transfer of packets from a source node to multiple destination nodes and 2) a scheduling of enhancing the performance of collective communications by early identification of bottleneck incurring nodes. The proposed technique is implemented and the performance improvement is measured. According to the performance evaluation, the proposed method has achieved about 20% performance improvement against conventional block data transfer methods when a binomial tree is used for the communication in LAN. In TPS algorithm, the distribution of messages to bottleneck incurring nodes is delayed to minimize the affection of the node to the total performance. Using TPS algorithm on WAN, significant performance improvement has also been achieved for various data sizes and number of nodes.

The essence of grid computing lies in the efficient utilization of a wide range of heterogeneous, loosely coupled resources in an organization. In a computational grid environment, regular monitoring of the execution of applications and taking actions for improving their performance in real time can achieve this. This paper presents the design of a multiagent framework for performance monitoring and tuning of an application executing in a Grid environment.

Keywords:

Grid Monitoring, Application Performance Tuning, Multi-agent framework.

Existing grid models target purely data parallel applications without inter-task communication. This paper proposes a transparent programming model to support communicating parallel tasks in a wide area grid. The proposed grid model with Distributed Pipes (DP) abstraction named as, GDP, enables location independent intertask communication among processes on machines spread over a wide area distributed system. This approach enables anonymous migration of communicating parallel tasks adjusting to grid dynamics. The proposed model supports sequential load to coexist with parallel load. A prototype of the proposed model has been implemented over clusters of nodes spread across the Internet. A steady state equilibrium engineering problem was studied over the model. Performance studies show linear to super linear speed up for the application.

Internet Technology Track received around 60 papers and the papers were reviewed by the International program committee and finally 9 papers have been selected for presentation (6 full and 3 short papers). As the track chair, I would like to thank all the authors who submitted their papers in this track and all the PC members who reviewed the papers in timely fashion. The paper presentation in this track is organized into three sessions, (1) Internet Search and Query, (2) E-commerce, (3) Web Browsing. I hope you enjoyed your presence in these sessions.

We study the problem of answering queries through a target RDF-based ontology, given a set of view-based mappings between one or more source relational schemas and this target ontology. Particularly, we consider a set of RDFS semantic constraints such as rdfs:subClassof, rdfs:subPropertyof, rdfs:domain, and rdfs:range, which are present in RDF model but neither XML nor relational models. We formally define the query semantics in such an integration scenario, and design a novel query rewriting algorithm to implement the semantics.

An efficient searching system is needed to offer the exact result of diverse web information to the user. Due to this reason, it is important to extract and analyze the user requirements in the distributed information environment. The searching method proposed in this paper uses the keyword as well as its context information for effective searching. Moreover, the proposed searching method is extracted keywords by using the new keyword extraction method also proposed in this paper, and it is executed web searching based on keyword mining profile generated by the extracted keywords. Unlike the conventional searching method, which searched for information by representative words, the proposed searching method is more efficient and exact. This is because data are searched by the example-based query including the content information as well as the representative words. Moreover, this searching method makes a domain keyword list for a quick search. The domain keyword is the representative word of a special domain. The performance of the proposed algorithm is analyzed in a series of experiments to identify its various characteristics.

We define an agent to be any node in the network that is prepared to provide some services to other parties when requested. Such services may be required for various purposes and then, searching and establishing communication with the agent will be necessary. The agent search may be oriented along a particular direction to reduce network load and optimize overall performance. Such oriented algorithms already exist. In this paper we have given a communications protocol that may use such oriented algorithm, defined its request and response packet formats and shown the simulation results for overhead incurred in such communication.

Depending on the type of the product, different kinds of personalized recommender systems can be built to guide the consumers in a large product feature space. In the approach, we present a fuzzy-based recommender system for those products that a general consumer does not buy very often, especially for consumer electronic products. For those consumer electronic products, it is difficult and not necessary to reason a customer’s previous preferences because there may not be enough information about the customer’s past purchases and the customer may have his specific requirements in each single purchase. Hence the system has specific domain knowledge and capability to interact with the consumer. Experimental results show the promise of our systems.

Organizations are seeking for a special kind of browser for exchanging structured information across business entities. In this paper, we present a generic solution called as XML Schema Definition (XSD) [6] to GUI translator. This translator processes data model defined in XML schema document and then generates user interface dynamically. This translator generates user interfaces in different rendering languages such as Java swings, HTML and WML.

Keywords:

XML, XSD, WML.

Micro-payment systems have the potential to provide non-intrusive, high-volume and low-cost pay-as-you-use services for a wide variety of web-based applications. We propose an extension, P2P-NetPay, a micro-payment protocol characterized by off-line processing, suitable for peer-to-peer network services sharing. Our approach provides high performance and security using one-way hashing functions for e-coin encryption. In our P2P-NetPay protocol, each peer’s transaction does not involve any broker and double spending is detected during the redeeming transaction. We describe the motivation for P2P-NetPay and describe three transactions of the P2P-NetPay protocol in detail to illustrate the approach. We then discuss future research on this protocol.

The existing search engines sometimes give unsatisfactory search result for lack of any categorization. If there is some means to know the preference of user about the search result and rank pages accordingly, the result will be more useful and accurate to the user. In the present paper a web page ranking algorithm is proposed based onsyntactic classification of web pages. The proposed approach mainly consists of three steps: select some properties of web pages based on user’s demand, measure them, and give different weightage to each property during ranking for different types of pages. The existence of syntactic classification is supported by running fuzzy c-means algorithm and neural network classifier on a set of web pages. It has been demonstrated that, for different types of pages, the same query string has produced different page ranking.

In this paper, we report some experiments and observations to make browsing of images more adaptable using small devices. We highlight the usability of such an alternative in mobile e-commerce and bandwidthconstrained systems.

Document clustering is classifying a data set of documents into groups of closely related documents, so that its resulting clusters can be used in browsing and searching the documents of a specific topic. In most cases of such as application, a set of new documents are incrementally added to the data set and there can be a large variation in the number of words in each document. This paper proposes an incremental document clustering method for an incrementally increasing data set of documents. The normalized inverse document frequency of a word in the data set is introduced to cope with the variation of the number of words in each document. Furthermore, an average link method for document clustering instead of using one similarity measure used in two similarity measures: a cluster cohesion rate and a cluster participation rate. Furthermore, a category tree for a set of identified clusters is introduced to assist the incremental document clustering of newly added documents. In this paper, the performance of the proposed method is analyzed by a series of experiments to identify their various characteristics.

The objectives of the System Security track of the 2nd International Conference on Distributed Computing and Internet Technology were to discuss in depth the current state of the research and practice in computer security with emphasis on network and distributed systems security, enable participants to benefit from personal contact with other researchers and expand their knowledge and disseminate the research results. This volume contains the 10 papers that were presented at the System Security track of the conference. These papers which had been selected from 77 submissions were rigorously reviewed by members of the Program Committee comprising of internationally recognized researchers in the area of computer security. The topics covered include a broad range of sub-areas - from emerging areas such as security issues in mobile and ad-hoc networks, security policy integration and code fingerprinting, to more traditional areas such as digital watermarking, intrusion detection and defense against virus and worms. These papers, the program committee believes, address some of the most pressing needs of the day for computer security. We would like to thank all the authors for submitting reports of their leading edge research to this conference and making it a success. A special thank you goes to the members of the System Security track program committee and other external reviewers who helped with the review process in spite of their busy schedule.

Many random key predistribution schemes have been proposed for pairwise key establishment in sensor networks recently. A general model of security under which these key predistribution techniques can be formally analyzed for correctness is required. In this paper, we have made such an attempt. We use the well known computational model of probabilistic turn based

$2\frac{1}{2}$

-player games to model the key predistribution schemes and have shown how this model can be translated in formally specifying a property that these schemes should have. To the best of our knowledge this is the first work where we show the significance of probabilistic turn based

$2\frac{1}{2}$

-player games in modelling security requirement of key predistribution schemes.

With the appearance of a number of e-mail worms in recent years, we urgently need a solution to detect unknown e-mail worms rather than using the traditional solution: signature-based scanning which does not deal with the new e-mail worms well. Our collected data shows that the quantitative trend of e-mail worms is really exploding. In this paper, we propose an e-mail worm Detection System that is based on analysis on human and worm behavior for detecting unknown e-mail worms. Message data such as e-mail or short messages are the result of human behavior. The proposed system detects unknown worms by assessment of behavior in communication because human behavior and worm behavior have different projection on data.

Verifiably encrypted signature is a useful mechanism for fair exchange especially, for online contract signing. In this paper, we propose a verifiably encrypted signature scheme using bilinear pairings. The scheme is secure against existential forgery under chosen message attack and extraction, without random oracles.

Keywords:

Fair Exchange, Verifiably Encrypted Signature, Bilinear Pairings, Random Oracles.

In this paper, we propose a Distributed Intrusion Detection System to protect Mobile Adhoc Networks from intruder-induced attacks. The highly dynamic, decentralized nature of these networks and a lack of infrastructure means that these networks are exposed to various kinds of security threats like spoofing, DOS attacks etc. We propose a new procedure to circumvent the intruder node and a technique to detect the intruder node in a co-operative manner based on the history of the failed paths due to intrusion. The experimental setup and the obtained results are presented discussing the various performance and security issues in the proposed protocol.

We focus on the problem of user revocation in secure adhoc networks. The current approach to achieve security in adhoc networks is to use a secret instantiation protocol in which, each user is given a subset of secrets from a common secret pool. To communicate securely, a pair of users use the secrets that are common to both of them. However, when users are compromised, some of these secrets are also compromised. Hence, to revoke the compromised users, the secrets known to these users need to be updated. Many group key management solutions exist for revocation of users from a group. However, due to the limitations in adhoc networks, i.e., lack of efficient broadcast mechanisms and lossy links, revocation of users is a challenging problem. In this paper, we propose a revocation algorithm that combines the secret instantiation protocols with group key management protocols. Depending on the combination of protocols used, our revocation algorithm provides deterministic or probabilistic guarantees for revocation. We illustrate our revocation algorithm by combining the square grid protocol and the logical key hierarchy protocol.

Keywords:

Secure Adhoc Networks, User Revocation, Secret Instantiation Protocols, Group Key Management Protocols.

IDS use different sources of observation data and a variety of techniques to differentiate between benign and malicious behaviors. In the current work, Hidden Markov Models (HMM) are used in a manner analogous to their use in text categorization. The proposed approach performs host-based intrusion detection by using HMM along with STIDE methodology (enumeration of subsequences) in a hybrid fashion. The proposed method differs from STIDE in that only one profile is created for the normal behavior of all applications using short sequences of system calls issued by the normal runs of the programs. Subsequent to this, HMM with simple states along with STIDE is used to categorize an unknown program’s sequence of system calls to be either normal or an intrusion. The results on 1998 DARPA data show that the hybrid method results in low false positive rate with high detection rate.

Network intrusion detection systems often rely on matching patterns that are learned from known attacks. While this method is reliable and rarely produces false alarms, it has the disadvantage that it cannot detect novel attacks. An alternative approach is to learn a model of normal traffic and report deviations, but these anomaly models are typically restricted to modeling IP addresses and ports. We describe an anomaly detection system which models all the fields of network, transport layer and payload of a packet at the byte level, by giving more weight to the most anomalous attributes. We investigated all the attributes and assigned weights to the attributes based on their anomalous behavior. We detect 144 of 185 attacks in the DARPA off-line intrusion detection evaluation data set [1] at 10 false alarms per day (total 100 false alarms), after training on one week of attack-free traffic. We investigate the performance of the system when attack free training data is not available.

Fingerprinting schemes use digital watermarks to determine originators of unauthorized/pirated copies. Multiple users may collude and collectively escape identification by creating an average or median of their individually watermarked copies. We present a collusion-resilient code, which improves anti-collusion fingerprinting (AND-ACC) scheme using statistically secure matrix. Our approach improves the robustness for non-linear attacks, and can be scalable for large number of users. We experiment our approach using HVS based watermarking scheme, for standard test images, and the results show better collusion detection performance over average and median collusion attacks.

Video watermarking hides information (e.g. ownership, recipient information, etc) into video contents. Video watermarking research is classified into (1) extension of still image watermarking, (2) use of the temporal domain features, and (3) use of video compression formats. In this paper, we propose a watermarking scheme to resist geometric attack (rotation, scaling, translation, and mixed) for H.264 (MPEG-4 Part 10 Advanced Video Coding) compressed video contents. We analyzed our perceptual model for video watermark in maximal capacity aspects, and experimented with the standard image and video sequences. Simulation results show that our video watermarking scheme is robust against H.264 video compression (average PSNR = 31 dB) and geometric attacks (rotation with 0-90 degree, scaling with 75-200%, and 50%~75% cropping).

Organizations typically have multiple security policies operating together in the same system. The integration of multiple policies might be needed to achieve the desired security requirements. Validating this integrated policy is a non-trivial process. This paper addresses the problem of composing, modeling and validating the security policies. We show how the various approaches for composing security policies can be modeled and verified using Alloy, a lightweight modeling system with automatic semantic analysis capability.

Theories of concurrency can be distinguished by the set of processes that they model, and by their choice of pre-ordering relation used to compare processes to prove their correctness. A link between two theories is a function L, which maps the processes of the source theory onto those of the target theory. Its image defines exactly the set of processes of the target theory. The ordering relation of the target theory is obtained by applying the link L to one or both operands of the source theory ordering. We will use the normal transition rules of a structured operational semantics to define a series of linking functions: W for weak simulation, R for refusals, T for traces refinement, D for divergences, etc. We then show that each function is a retraction, in the sense that it is monotonic, decreasing and idempotent. Finally we show their composition is a retraction.

The Software Engineering track received 63 papers from which 7 papers were selected after an intensive reviewing and selection process. Many good papers could not be selected due to lack of space in the program. The selected papers cover a diverse range of topics within software engineering: from software reliability prediction to middle-ware for component management to runtime validation and code generation. The paper by Roychoudhury, Negi and Mitra analyzes programs loops for estimating program execution time. They use constraint propagation techniques to detect infeasible paths followed by timing analysis that employ memoization techniques. The paper by Sengupta and Cleaveland presents the operational semantics of timed message sequence charts to help detect errors and inconsistencies in specifications. Tripathi and Mall present a method for making predictions about reliability of software during the software development process itself when the failure data from the field cannot be available. The paper by Wang presents a logic programming framework for integrating architecture description languages (ADLs) which allows tools developed for one ADL to be used even though the architectural specification is written in another ADL. In a similar vain, the paper by Stevenson, Fu and Dong presents a framework for automated and validated realization of software architecture designs. The paper by Bhattarcharjee and Shyamsundar presents a method for validated code generation for activity diagrams which are useful in model driven design of software. Finally, the paper by Mousavi et al presents techniques that exploit symmetry for tackling the state-space explosion problem that arises in model checking.

Numerous architectural description languages(ADLs) have been developed in the last decade. However, none of the ADLs and their toolsets are expressive enough to cover all the requirements that may be specified while developing a software system. An ADL based approach will be more useful and powerful if ADLs can share architectural descriptions and if their analysis tools can be integrated. In this paper, we propose a semantics-based approach to integrating ADLs. A general, abstract executable form is developed for representing architectural information. A uniform query language is also defined that can be used to retrieve architectural information from this abstract form. There are at least three benefits of our framework. First, software designer and analysis tools can use a uniform query language to retrieve architectural information from architectural descriptions written in different ADLs. Second, interpreters and toolsets for ADLs can be developed extremely quickly. Thus, as an ADL rapidly evolves, its implementation infrastructure can be developed at the same pace. Third, an architecture description written in one ADL can be readily translated into another ADL.

The benefits of architecture description languages (ADLs) cannot be fully captured without a automated and validated realization of software architecture designs. In addition to the automated realization of software architecture designs, we validate the realization process by exploring the runtime verification technique and aspect-oriented programming. More specifically, system properties are not only verified against design models, but also verified during execution of the generated implementation of software architecture designs. All these can be done in an automated way. In this paper, we show that our methodology of automated realization of software architecture designs and validation of the implementation is viable through a case study.

Statically estimating the worst case execution time of a program is important for real-time embedded software. This is difficult even in the programming language level due to the inherent difficulty in detecting infeasible paths in a program’s control flow graph. In this paper, we study the problem of accurately bounding the execution time of a program loop. This involves infeasible path detection followed by timing analysis. We employ constraint propagation methods to detect infeasible paths spanning across loop iterations. Our timing analysis is exact modulo the infeasible path information provided. Moreover, the analysis is efficient since it relies on memoization techniques to avoid exhaustive enumeration of all paths through a loop. The precision of our timing analysis is demonstrated on different benchmark programs.

In early developmental stages of software, failure data is not available to determine the reliability of software. But developers need reliability prediction for quality assessment and resource planning. We propose a model based on Reliability Block Diagram (RBD) for representing real-world problems and an algorithm for analysis of these models in early phase of software development. We have named this technique Early Reliability Analysis Technique (ERAT). We have performed several simulations on randomly generated software models to compute reliabilities and sensitivity. The simulation result shows that reliabilities are good quality indicator and sensitivity of system reliability to functions reliability can be determined.

Triggered Message Sequence Charts (TMSCs) are a scenario-based visual formalism for early stage requirements specifications of distributed systems. In this paper, we present a formal operational semantics for TMSCs that allow the simulation of TMSC system descriptions, so that errors and inconsistencies in specification may be detected early on. The semantics is defined in terms of Structured Operational Semantics (SOS) rules that guide the step-wise execution of TMSC specifications. We also consider the equivalence of this semantics and the TMSC denotational semantics that has been presented in previous work.

Symmetry reduction is a promising technique for combatting state space explosion in model checking. The problem of finding the equivalence classes, i.e., the so-called

orbits

, of states under symmetry is a difficult problem known to be as hard as graph isomorphism. In this paper, we show how we can automatically find the orbits in an actor-based model, called Rebeca, without enforcing any restriction on the modeler. The proposed algorithm solves the orbit problem for Rebeca models in polynomial time. As a result, the simple actor-based Rebeca language can be utilized efficiently for modeling and verification of systems, without involving the modeler with the details of the verification technique implemented.

Activity Diagram

is an important component of the set of diagrams used in UML. The OMG document on UML 2.0 proposes a Petri net based semantics for Activity Diagrams. While Petri net based approach is useful and interesting, it does not exploit the underlying inherent synchronous concepts of activity diagrams. The latter can be effectively utilized for validated code generation and verification. In this paper, we shall capture activity diagrams in synchronous language framework to arrive at executional models which will be useful in model based design of software. This also enables validated code generation using code generation mechanisms of synchronous language environments such as Esterel and its programming environments. Further, the framework leads to scalable verification methods.

The unprecedented growth of electronic data and ever increasing user dependence on electronic data in today’s world suggests that data should be regarded as one of the most important assets of the users. Within the last few years Data Mining and Knowledge Discovery technology has established itself as a key technology for enterprises that wish to improve the quality of the results obtained from data analysis, decision support, and the automatic extraction of knowledge from data. The Data Mining Track focuses on the logical and physical design of knowledge discovery systems, particularly, on data classification and clustering, association rules, data mining techniques, data analysis and discovery, and data mining applications.

This paper presents an efficient clustering technique which can identify any embedded and nested cluster over any variable density space. The proposed algorithm is basically an enhanced version of DBSCAN [4] and OPTICS [7]. Experimental results are reported to establish that the proposed clustering technique outperforms both DBSCAN and OPTICS in terms of complex cluster detection.

Keywords:

Variable density, embedded cluster, core-distance, cluster, core neighborhood, unsupervised.

With the enormous growth of data, which exhibit sequentiality, it has become important to investigate the impact of embedded sequential information within the data. Sequential data are growing enormously, hence an efficient classification of sequential data is needed. k-Nearest Neighbor (kNN) has been used and proved to be an efficient classification technique for two-class problems. This paper uses sliding window approach to extract sub-sequences of various lengths and classification using kNN. We conducted experiments on DARPA 98 IDS dataset using various distance/similarity measures such as Jaccard similarity, Cosine similarity, Euclidian distance and Binary Weighted Cosine (BWC) measure. Our results demonstrate that sub-sequence information enhances kNN classification accuracy for sequential data, irrespective of the distance/similarity metric used.

Automatically finding

interesting

,

novel

or

surprising

patterns in time series data is useful in several applications, such as fault diagnosis and fraud detection. In this paper, we extend the notion of distance-based outliers to time series data and propose two algorithms to detect both global and local outliers in time series data. We illustrate these algorithms on some real datasets.

Keywords:

Novelty detection, Outlier detection, Time series, Sequence mining.

With the proliferation of the Web, capture of market intelligence data has become more difficult in reality from the system’s point of view, as data sources on the web are voluminous, heterogeneous in terms of structures and semantics, and some part of it may be irrelevant to a specific organizations’ marketing decision making context, which is the primary premises of market intelligence (MI) systems. To address these requirements of MI, we are proposing a method for creating an MI network using customer feedback messages and e-mails as inputs. We have proposed the use of knowledge map (KM) method for representing textual and unstructured resources as a network using KMs and clustering and then incrementally enhance itself as the new customer e-mails keep coming. At last, we have proposed a self-enhancing network using Bolzmann Machines concept where the new messages are treated as new hypotheses, and they get absorbed into the MI network based on their similarity values.

In many applications numeric as well as categorical features describe the data objects. A variety of algorithms have been proposed for clustering if fuzzy partitions and descriptive cluster prototypes are desired. However, most of these methods are designed for data sets with variables measured in the same scale type (only categorical, or only numeric). We have developed probabilistic distance measure to compute significance of attributes for numeric data, and distance between two categorical values. We used this distance measure with the cluster center definition proposed by Yasser El-Sonbaty and M. A. Ismail [26] to propose Fuzzy-c mean type clustering algorithm for mixed attributes data. The results of the application of the new algorithm show that new technique is quite encouraging.

The multidimensional modeling of data is steadily gaining popularity, finding adoption not only for business but for scientific applications as well. Data Warehousing is the most prominent example of multidimensional data usage. In parallel, wireless networks, with their rapid growth, already play a fundamental role in facilitating time critical decision-making. Nevertheless, their inherent shortcomings, but also those of the mobile devices operating within their proximity, introduce additional complexity. Access time and energy consumption become, among others, factors that should be taken into consideration. This paper deals with the efficient dissemination of multidimensional data into wireless networks. In this context, a new family of scheduling algorithms, which simultaneously exploits various characteristics both of OLAP data and wireless networks, is introduced. These algorithms clearly outperform existing proposals, on all counts: average access time, energy consumption and network utilization.

Knowledge about multi-dimensional frequent patterns is interesting and useful. The classic frequent pattern mining algorithms based on a uniform minimum support, such as Apriori and FP-growth, either miss interesting patterns of low support or suffer from the bottleneck of itemset generation. Other frequent pattern mining algorithms, such as Adaptive Apriori, though taking various supports, focus mining at a single abstraction level. Furthermore, as an Apriori-based algorithm, the efficiency of Adaptive Apriori suffers from the multiple database scans. In this paper, we extend FP-growth to attack the problem of multidimensional frequent pattern mining. The algorithm Ada-FP, which stands for Adaptive FP-growth. The efficiency of the Ada-FP is guaranteed by the high scalability of FP-growth. To increase the effectiveness, the Ada-FP pushes various support constraints into the mining process. We show that the Ada-FP is more flexible at capturing desired knowledge than previous Algorithm.

Phylogenetic networks are the generalization of the tree models used to represent evolutionary relationship between the species. Tree models of evolutionary process are not adequate to represent the evolutionary events such as, hybridization, lateral/ horizontal gene transfer and genetic recombination. A well-formulated problem in phylogenetic networks, due to recombination, is to derive a set of input sequences on a network with minimum number of recombinations. No efficient algorithm exists for this problem as it is known to be NP-hard. Efficient solutions exist for the constrained recombination networks, where the nodes on each recombination cycles are disjoint. These solutions are based on the assumption that the ancestral sequence is known in advance. On the other hand, the more biologically realistic case is that where the ancestor sequence is not known in advance. In this paper we propose an efficient classification based method for deriving a phylogenetic network under constrained recombination without knowing the ancestral sequence.

In the original version for this paper, the name of the first author was not correct. It should read as Pradeep Kumar.

In the original version for this paper, the name of the first author was not correct. It should read as Pradeep Kumar.