Abstract:Statically typed XML processing languages show new ways of processing XML data. However, current languages are not efficient enough. This paper studies the decision problem of subtyping relation which is an important issue of the languages, and optimizes XDuce’s subtyping algorithm with a pruning strategy. Experimental data show the efficiency of the algorithm increased 20% averagely. This optimization strategy can be applied to other languages which use similar subtyping algorithm.

Abstract:SAT-Based bounded model checking (BMC) has high complexity in dealing with real-time systems. Satisfiability modulo theories (SMT) solvers can generalize SAT solving by adding the ability to handle arithmetic and other decidable theories. This paper uses SMT in BMC for real-time systems instead of SAT. The clocks can be represented as integer or real variables directly and clock constraints can be represented as linear arithmetic expressions. These make the checking procedure more efficient. TCTL (timed computation tree logic) is used to specify the properties of real-time systems and improvement of the encodings has been done.

Abstract:It was assumed that the pattern and text characters are independent and uniformly distributed over a finite alphabet in classical string matching algorithms, and this assumption differs from real applications and causes many problems. Considering the probability distributions, the contexts of the characters, and the convenience of applications, this paper gives a concept hit rate and four extended concepts about it. Then it gives the theory analysis and detailed experiments with hit rate on the four classical algorithms. The map of the relationships is obtained between the hit rate and the algorithms’ performance, and at the same time some valuable conclusions are made through above work. As a character variable, hit rate describes the relativity of patterns and text and can serve as guidelines in the algorithms design, analysis and some other extended research fields of the string matching.

Abstract:The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set. This problem is NP-hard. Based on the deep analysis of its structural characteristics, employing the strategy of set partition and the improved results of another related problem, this paper proposes a parameterized algorithm of running time O* for the problem, in which l denotes the number of terminal pairs and k denotes the number of removed vertices. This algorithm significantly improves the previous one of running time O*.

Abstract:Data caching has emerged as an effective way to reduce network traffic, alleviate server load and accelerate information access. Deploying a group of distributed caching nodes to cooperate with each other in serving client requests will further improve the system performance. One of the important issues in distributed caching system is coordinating cache placement to achieve access cost minimization. In this paper, a theoretical model is introduced to analyze the access cost of placing a set of data objects in distributed caching systems. In this model, the cache placement problem is formulated as an optimization problem. A graph-based algorithm is proposed to solve the problem. The algorithm applies a modified Dijkstra’s algorithm to look for the shortest path in the access cost graph, which corresponds to an optimal cache deployment for the system. The correctness of the graph-based algorithm is proved theoretically and its performance is evaluated by simulations. Experimental results show that the graph-based algorithm outperforms most existing distributed caching schemes.

Abstract:The specification-based testing can be used to test software functions without knowing program code. Decisions are the main form of the pre- and post-conditions in formal specifications. This work analyzes logic coverage testing criteria for specification-based testing. It proposes and analyzes in detail masking logic coverage testing criteria, to solve the problems that the existent determinant logic coverage testing criteria can not solve. A feasible test case generation algorithm based on the masking logic coverage testing criteria is presented. The test cases satisfying the masking logic coverage testing criteria can detect those errors caused by the masking property of conditions. It also analyzes the constraints among conditions, how to decompose and compose a complicated decision, and the relationship among decisions. These can respectively clarify the coupling problem among conditions, the multiple occurrences of a condition in a decision, and the position problem of decisions in a program. Additionally, test criteria including full true decision coverage, full false decision coverage, all sub-decisions coverage, unique condition true coverage and unique condition false coverage are proposed. The test sets satisfying these criteria can detect respectively different types of errors. Finally, the subsumption relation graph among these testing criteria is presented and different applicable scenarios for different testing criteria are suggested.

Abstract:Skyband queries are very important for decision-making applications. To incorporate the Skyband operator into the database system, the problem of Skyband cardinality estimation must be solved, i.e., estimating the number of the Skyband elements returned by Skyband queries, which is very important for extending the query optimizer’s cost model to accommodate Skyband queries. This paper proposes a space and time efficient approach to estimate the Skyband cardinality, which is based on the generalized form of the Inclusion-Exclusion Principle. Experimental results show that the proposed approach can estimate the Skyband cardinality accurately.

Abstract:To cluster the retrieval results of Web image, a framework for the clustering is proposed in this paper. It explores the surrounding text to mine the correlations between words and images and therefore the correlations are used to improve clustering results. Two kinds of correlations, namely word to image and word to word correlations, are mainly considered. As a standard text process technique, tf-idf method cannot measure the correlation of word to image directly. Therefore, this paper proposes to combine tf-idf method with a feature of word, namely visibility, to infer the correlation of word to image. Through LDA model, it defines a topic relevance function to compute the weights of word to word correlations. Finally, complex graph clustering and spectral co-clustering algorithms are used to testify the effect of introducing visibility and topic relevance into image clustering. Encouraging experimental results are reported in this paper.

Abstract:The traditional TCP transport protocol has many drawbacks on Fast Long Distance Networks (FLDnet), and its transfer performance can not satisfy the requirement of increasing bulk data transfer applications. The UDP transport protocol has high transfer speed on FLDnet, but its reliability can not be guaranteed. This paper firstly analyzes the drawbacks of the traditional transport protocols on FLDnet, then, classifies and summarizes the main design principles of all kinds of enhanced transport protocols proposed in recently years and the research work on performance evaluation of transport protocols. Finally, some open issues and further research directions are proposed.

Abstract:Internet is becoming the infrastructure and starts to carry more critical mission traffic where even a short disruption can cause significant losses for certain applications. Nevertheless, traditional route protocols have the problem of long convergence delay, transient unreachability and loop upon the network topology changes due to links/nodes failure or various other reasons. Unfortunately, the transient routing failures are very common according to the experimental studies. Numerous routing protocols which can provide disruption-free forwarding and fast recovery have been proposed. This paper firstly studies the root cause of transient failures, and then presents classification standards for survivable routing protocols. Thereafter, it focuses on analyzing the fundamental mechanism of existing representative survivable routing protocols and comparing their characteristics, performance and overhead. Finally, the current research status and open research issues are concluded.

Abstract:The rapid development of Internet leads to an increase in system complexity and uncertainty. Traditional network management can not meet the requirement, and it shall evolve to fusion based Cyberspace Situational Awareness (CSA). Based on the analysis of function shortage and development requirement, this paper introduces CSA as well as its origin, conception, objective and characteristics. Firstly, a CSA research framework is proposed and the research history is investigated, based on which the main aspects and the existing issues of the research are analyzed. Meanwhile, assessment methods are divided into three categories: Mathematics model, knowledge reasoning and pattern recognition. Then, this paper discusses CSA from three aspects: Model, knowledge representation and assessment methods, and then goes into detail about main idea, assessment process, merits and shortcomings of novel methods. Many typical methods are compared. The current application research of CSA in the fields of security, transmission, survivable, system evaluation and so on is presented. Finally, this paper points the development directions of CSA and offers the conclusions from issue system, technical system and application system.

Abstract:As an application of mobile ad hoc networks (MANET) on Intelligent Transportation Information System, the most important goal of vehicular ad hoc networks (VANET) is to reduce the high number of accidents and fatal consequences dramatically. One of the most important factors that would contribute to the realization of this goal is the design of effective broadcast protocols. This paper introduces the characteristics and application fields of VANET briefly. Then, it discusses the characteristics, performance, and application areas with analysis and comparison of various categories of broadcast protocols in VANET. According to the characteristic of VANET and its application requirement, the paper proposes the ideas and breakthrough direction of information broadcast model design of inter-vehicle communication.

Abstract:With the rapid development of numerous applications and optical network, fast long distance optical network has emerged in the Internet field. Some novel studies indicated that, due to the exigent requirement of scientific applications and the rapid improvement of network bandwidth, the network transfer speed has outstripped the processing speed of the end systems. Therefore, the congestion has been pushed into the end nodes and the processing ability of the end system has become a bottleneck in such a network. Thus several novel end-system performance aware transport protocols have been proposed. The authors categorize and describe all these protocols, and emphatically analyze that congestion detection, rate adaption mechanisms, advantages and disadvantages of all kinds of schemes. Subsequently, the current existing open issues are summarized and some further interesting directions are pointed out.

Abstract:Wireless sensor networks (WSNs) consist of low-power and energy-constrained sensor nodes, and a fundamental challenge in the design of such networks is to maximize the network lifetime. In WSNs, data collected by adjacent sensor nodes usually have spatial-temporal correlations, and data aggregation technique is often used as an effective approach to remove data redundancy. Efficient usage of data aggregation technique can significantly reduce the amount of data delivery, lower the cost of overall power consumption of the network, hence increase the network lifetime. This paper studies the optimal data delivery in WSNs that takes advantage of data aggregation and nodal power control, and presents a novel routing algorithm that maximizes the network lifetime. The algorithm uses genetic algorithm (GA) to achieve an optimal selection of aggregation points, and gradient algorithm is also used to further optimize the result. The algorithm balances the power consumption of sensor nodes, and maximizes the network lifetime. Numerical results show that the proposed approach has substantially improved the network lifetime.

Abstract:By analyzing the property of the resource addressing, this paper proposes the general layered model of the resource addressing in the IOT by extending the model in Internet. It provides the theoretical basis for the particular addressing conflict problems in the Internet of Things (IOT) caused by multiple existing code standards. According to the model, this paper further puts forward the application architecture model of IOT. By realizing the main function, the validity and feasibility of the model can be verified.

Abstract:This paper identifies all factors impairing TCP performance based on network protocol hierarchy: Lossy wireless channel at the physical layer; excessive contention and unfair access at the MAC layer; frequent routing changes due to node mobility at the network layer; the fundamentally inappropriate mechanisms of TCP at the transport layer, including window-based congestion control, loss-based congestion detection, slow-start and AIMD (additive increase/multiplicative-decrease) of congestion window; reliance on ACK-clocked characteristics. Then, it designs a novel cross-layer optimal congestion control (CCOC) protocol tailored toward the characteristics of ad hoc networks. Cross-Layer design framework is applied in CCOC to improve fair access at MAC layer, to detect false link failure, to reduce the number of route failures, to quick-start during route changes, to transmit reliably based on SACK, and to implement the adaptive optimization strategy guided by the nonlinear optimization theory. Then, this paper outlines the protocol framework of CCOC. Finally, the extensive packet-level simulations is implemented in NS2 environment. The simulation results show that CCOC significantly outperforms TCP and ATCP in many important performances such as throughput and fairness, under a variety of scenario and mobility conditions.

Abstract:Key management is a critical issue for wireless sensor networks security. This paper proposes EEHS, a novel Energy Efficient and Highly Survivable dynamic key management scheme for large-scale clustered wireless sensor networks based on Exclusion Basis System (EBS). The major advantages of EEHS are strengthened network security, enhanced energy efficiency, high dynamic performance and good support for network expansion. In EEHS, a novel polynomial-based key—the common polynomial key, is designed and employed as the administration key in the EBS, which can enhance the network survivability under attack. All system keys can be refreshed and revoked according to the compromise of sensor nodes. The function of key assignment and key generation are dispatched to different functional nodes in one cluster and sensor nodes also rotate to act as functional nodes in order to improve the energy efficiency and the network robustness. Simulation and analysis results show that compared with related works, EEHS supports the networks with more energy efficiency, longer lifespan and stronger resilience to node compromise.

Abstract:An adaptively imperceptible video watermarking algorithm using entropy model is proposed. This algorithm works by first combining the Human Visual System (HVS) with block-matching techniques to obtain motion-related information. It then uses entropy model to statistically analyze the obtained information, and eventually establish a set of non-linear formulas based on HVS and motion information. Based on the contents of video frames, this set of non-linear formulas can adaptively calculate the maximum strength of every block. Experimental results show that using entropy model and non-linear formulas can significantly improve watermarking imperceptibility, effectively resist common attacks for video watermarking, and consequently achieve higher robustness.

Abstract:The validation of source IP addresses becomes the key technique for devising a trustworthy network. However, inter-domain IP spoofing preventions based on source-destination labels and end-hosts IP authentications based on source labels both adopt end to end mode to solve the problem, which ignores the flooding of spoofing packets on middle networks. To address this problem, an enhancing mechanism for the inter-domain IP spoofing prevention service, ESP (enhanced spoofing prevention), is proposed. Via integrating path labels into source labels, ESP reduces the collision of source labels at destination networks and enables filtering IP spoofing packets toward other nodes in middle networks, thus prevents flooding attacks in advance and extends the protected domain of the spoofing prevention. Based on BGP (border gateway protocol) update ESP develops the validation of prefix security to restrict the scope of the propagation of labels, thus decreases the cost of computing and storing of labels. The abilities of IP spoofing prevention and filtering spoofing packets in advance are demonstrated in the topology, which is constructed based on RIB (routing information base) provided by Routeview.

Abstract:The multi-path routing scheme provides reliable guarantee for mobile ad hoc networks. This paper proposes a new method used to analyze the security of multi-path routing protocol within the framework of Universally Composable (UC) security. Based on the topological model that exist in adversarial nodes, the concept of plausible route is extended and the definition of plausible-route set is presented. Plausible-Route set is used to describe the multi-path routing for ad hoc networks, and a formal security definition based on UC-RP is given. A provably Security Multiple Node-Disjoint Paths source routing (SMNDP) is proposed and used to address secure fault issue of MNDP (multiple node-disjoint paths) in the active adversary model. The new approach shows that the security of SMNDP can be reduced to the security of the message authentication code and the digital signature. SMNDP implements the correctness of route discovery process, the authentication of nodes identifier and the integrality of route information.

Abstract:Routing table size and routing path length are two critical measures for evaluating a routing algorithm, and there exists a tradeoff problem between them. Compact routing refers to the design of routing algorithms obtaining relatively optimal tradeoffs between the above two measures. So far, researchers have proposed quite a few universal compact routing schemes, which have high optimized bounds on routing table size and path length for arbitrary network topologies. However, as real-world networks usually have specific topologies, the universal schemes are possibly sub-optimal on them for not exploiting the topological properties. Recent work discovered many real-world networks had scale-free topologies. By exploiting the power-law and strong clustering features, a compact routing scheme with additive stretch for this class of networks is presented in this paper. By separating a network into a backbone tree and shortcuts, this scheme ensures between any source node and destination node in a network, the routing path length is at most an additive factor of b longer than the shortest path between them, and the local routing table at each node is upper bounded by O(clog2n) bits, wherein b and c are parameters related to the network topology. Experimental results show that b and c have small values in scale-free networks, and the proposed scheme can achieve better average-case performance than known schemes.

Abstract:Finding two link-disjoint QoS paths (primary and backup) between source-destination pairs is one of the most significant schemes to provide reliable QoS routing. Current algorithms for seeking multi-constrained link-disjoint path pair (MCLPP) can not always make sure to find the feasible solutions in networks. To solve this problem, this paper analyzes the properties of the optimal solution of MCLPP problem, and then proposes a design principle for the exact algorithm. Based on the design principle, an exact algorithm called link-disjoint optimal multi-constrained paths algorithm (LIDOMPA) is presented, which is able to find multi-constrained shortest link-disjoint path pair for arbitrary networks. To reduce the complexity, this paper introduces three key concepts: The candidate optimal solution, the constricted constraint vector and the structure-aware non-dominance, which effectively reduce the search space of LIDOMPA without loss of exactness. Extensive experiments show that LIDOMPA outperforms the existing algorithms in terms of the ability of obtaining solutions and achieves acceptable running time overhead.

Abstract:This paper presents a construction of Boolean functions with the maximum algebraic immunity on even number of variables. It also gives a construction of balanced rotation symmetric Boolean functions with the maximum algebraic immunity on even number of variables. This paper uses some results of linear algebra and enumerative combinatorics in the constructions. These functions have strong resistance against algebraic attacks. The balanced rotation symmetric Boolean functions constructed can also be used in the construction of safer hashing functions.

Abstract:The Universal Mobile Telecommunication System (UMTS) adopts 3GPP authentication and key agreement (3GPP AKA) protocol as its security framework, and this protocol has made effective improvements on the hidden security problems of GSM (global system for mobile communications). This paper investigates into the security of the 3GPP authentication and key agreement protocol, and analyzes four types of attacks to which it is vulnerable. To solve the security problems mentioned above, it presents an efficient authentication and key agreement protocol, which is based on public key cryptography, under the circumstances of location updating and location immovability, adopts formal analysis to prove the security of two protocols proposed, and compares it with other protocols from the aspect of security. The results show that this proposed protocol can significantly enhance the security of 3GPP AKA protocol.