Abstract:Computing symbolic complexity bounds of loops can prove program’s termination. Based on the solving techniques of recurrence equations and optimization problems, this paper presents a practical approach for computing complexity bounds of loops called P*-solvable loops. Two algorithms are given for loops with assignments only and loops with conditional branches respectively. Compared with some other works, this approach can attain more complexity bounds of loops. The experimental results demonstrate the practicality of this approach.

Abstract:A unified algebraic model is used to represent optimization problems, which uses a transformational approach that starts from an initial problem specification and reduces it into sub-problems with less complexity. The model then constructs the problem reduction graph (PRG) describing the recurrence relations between the problem, and derives an algorithm with its correctness proof hand-in-hand. A prototype system that implements the formal algorithm development process mechanically is also designed. This approach significantly improves the automation of algorithmic program design and helps to understand inherent characteristics of the algorithms.

Abstract:Based on the analysis of exist ant colony optimization (ACO) algorithms and the studies in visual perception and cognitive psychology, this paper proposes a new optimization strategy, the visual feedback and behavioral memory based Max-Min ant colony optimization algorithm (VM-MMACO). The main idea is to enhance the ant’s search ability by establishing the learning mechanism of visual feedback and behavioral memory. With artificial visual memory and learning abilities, the ant can not only see the targets around, using visual perception to optimize the heuristic information produced by pheromone in order to improve the search quality, but can also exploit the historical solutions, finding local best segments (called experience) to narrow the searching space smoothly, so that it can accelerate the convergence process. Comparisons of VM-MMACO and existing optimization strategies within a given iteration number are performed on the publicly available TSP instances from TSPLIB. The results demonstrates that VM-MMACO significantly outperforms other optimization strategies. Finally, according to the accumulative learning theory, the learning mechanism could be studied further to make a much more intelligent algorithm.

Abstract:This paper first investigates two main kinds of features of Web service description language (WSDL) documents: the structure features and the reference features. Next, a novel multi-vector model for Web services is introduced, which is distinguished from the general text representation model by the explicit features of Web services. The structure features are represented by multiple vector spaces and the term weighting in the sub-vector is determined by the reference features. A method to compute the similarity between two Web services is proposed and a Web service discovery prototype system based on this new model is implemented. Finally, a Web service discovery test collection is constructed, which has 1576 WSDL documents together with incomplete relevance judgments. The experimental results on this collection show that Web service discovery based on the proposed model is more effective than based on simple vector space model of text with the confidence of 95%.

Abstract:There are limitations with most of the current role models. For example, the issues of role creation and attachment have to be handled explicitly in the source code: the navigation between role objects and source objects is unidirectional, and messages cannot be transferred bi-directionally, etc. Such limitations always result in the core business becoming tangled with the control logic for role objects. A dynamic role model, named DR, can provide the automatic creating and destroying mechanisms of role objects and can also provide the bi-directional navigation between role objects and source objects. These functionalities make up the core of the use of the role model, and the control logic for role objects is also transparent to users. The implementation of DR is centered around prepositve objects and delegation mechanisms not only resolves the complex hierarchy of roles problem, but the dynamic role model also solves the compatibility problem with traditional object-oriented systems.

Abstract:In this paper, based on a flow and context-sensitive SSA (static single assignment) information-flow analysis, a fine-grained and scalable approach is proposed for taint propagation analysis, which can not only track tainted data and its propagation path with control and data-flow properties, but also detect the vulnerabilities such as buffer overflow and format string bugs successfully. During the analysis, pieces of code considered vulnerable are instrumented with dynamic verification routines, so that runtime security is guaranteed in the absence of user intervention. The analysis system is implemented as an extension of GCC compiler, and the experiments have proven that this approach is efficient, holding both optimized accuracy and time-space cost.

Abstract:This paper presents a dynamic hieratical task decomposition algorithm which applies for a management module of complex IT application based on multi-agent collaboration. The algorithm considers the capacity restriction of multi-agent and the dynamicity of management task caused by the variation of management strategy, IT infrastructure and service logic. Meanwhile, it also considers the balance issue of sub tasks after decomposition, which is the load balance issue of the corresponding multi-agent. The algorithm effectively improves the task executing efficiency and stability of multi-agent. Simulation and analysis results show that the algorithm in this paper is more efficient and has steadier load distribution than that of other compared algorithms.

Abstract:This paper proposes an incremental extremely random forest (IERF) algorithm, dealing with online learning classification with streaming data, especially with small streaming data. In this method, newly arrived examples are stored at the leaf nodes and used to determine when to split the leaf nodes combined with Gini index, so the trees can be expanded efficiently and fast with a few examples. The proposed online IERF algorithm gives more competitive or even better performance, than the offline extremely random forest (ERF) method, based on the UCI data experiment. On the moderate training datasets, the IERF algorithm beats the decision tree reconstruction algorithm and other incremental learning algorithms on the performance. Finally, the IERF algorithm is used to solve online video object tracking (multi-object tracking also included) problems, and the results on the challenging video sequences demonstrate its effectiveness and robustness.

Abstract:An approach of semantic-based focused crawling is proposed in order to use semantic resource efficiently. In this paper, a domain-ontology is used to describe the topic of Web crawling. Lexicon of the keywords list are mapped to ontology, and semantic of words are obtained through mapping. Inference services about assertion set expanding and domain-range relation are defined. The semantic relation among keywords can be inferred by inference services. At the same time, the definition of concept about Web page is given. A semantic computational model is proposed by combining inference services mentioned above. In the end, the order of URLs corresponding to their Web page is decided according to the subsumption of topic concepts. The result show that this approach is advanced in harvest-rate and crawling efficiency and is better than some classical algorithms.

Abstract:This paper focuses on the energy efficient construction of a k-barrier coverage in mobile sensor networks. First, this paper formulates 1-BCMS (1-barrier coverage min-sum of moving distance) problem for constructing 1-barrier coverage energy efficiently, reduces the 1-BCMS problem to 1-GBMS (1-grid barrier min-sum of moving distance) problem based on grid model, and present the reduced problem’s Linear Programming Model and prove it to be NP-hard. Secondly, this paper presents a CBGB (constructing baseline grid barrier) algorithm to construct 1-barrier coverage energy efficiently. CBGB is an approximation algorithm for 1-GBMS problem and the solution of CBGB is close to the optimal solution. Finally, a Divide-and-Conquer algorithm is proposed to construct k-barrier coverage. This algorithm significantly reduces communication overhead and computation cost compared to other algorithms. Simulation demonstrates the effectiveness of the proposed algorithm in constructing k-barrier coverage.

Abstract:Some statistical characteristic will emerge in unstructured P2P networks because of its large scale. Using above phenomena, an unstructured P2P overlay called Multi-Level Local Overlay, or ML²O is presented in this paper. The mathematical control on the links can generate a topology with locality in multiple scale. Theoretical analyses show that the diameter of network and the average degree of peers are all O(logn) where n is the size of peers. Based on the multi-level locality, a recursive indexing mechanism is devised in this paper, in which the index for larger locality is build from the indexes of smaller localities Finally, an unstructured P2P search algorithm called Local Pervasion and Directed Search, or LPDS is presented in this paper. LPDS will collect information from local scope by executing local pervasion. Moreover, a part of the index tree can be achieved from the collected information. LPDS can find the next hop approaching the destination in the partial index tree. Theoretical analyses show that the expectation of average search hops and communication loads produced by LPDS are all O(logn). Experimental results illustrate the scalability of LPDS on ML²O is close to structured P2P search and its robustness is close to unstructured P2P search.

Abstract:In recent years, eMule network, a kind of peer-to-peer (P2P) file-sharing network has become more and more popular. Along with its popularity, the demand to accurately determine the peer in eMule has also increased for two reasons: it is a critical step to accurately locate sources of files in P2P file-sharing networks, and the wanton spread of vulgar content makes it necessary to censor eMule. This demand allows everyone to put forward the problem of optimal peer identifier in eMule network. However, since Kad ID (the widely-used identifier in eMule network) can be freely changed by users of eMule, there exists Kad ID aliasing, a single peer may correspond to multiple Kad IDs; reversely, There also exists Kad ID repetition, which are multiple peers corresponding with a single Kad ID. Therefore, it is difficult to accurately determine the peer by using Kad ID. This paper attempts to solve this problem. First, the stability factor (SF) of peer identifier is defined to evaluate candidate identifiers. Then, a crawler named Rainbow is designed and implemented to collect peer information from multiple candidate identifiers’ relationship in real eMule network. Note that Rainbow has been proved to be convergent and has low time and space complexity. Experimental results show that {userID} is the optimal peer identifier in peer identifier set 2^{{Kad ID,userID,IP}-{Φ}} as {userID} has the largest SF value. Later on, in order to quantify the extent of Kad ID aliasing, the relationship between {userID} and {Kad ID} is discussed. Lastly, the effectiveness of the application of the optimal peer identifier is analyzed. Results show that peers are more accurately determined when using {userID} as the identifier of peers. All in all, the identification of optimal peer identifier provides a basis for future research of eMule network, and Rainbow serves as a useful tool for measuring real eMule network.

Abstract:By using the theory of minimum connected dominating set, the issue of topology optimization for heterogeneous wireless sensor networks is studied. Considering the heterogeneous feature of sensor nodes’ communication capabilities, a function named area energy consumption rate has been built by integrating the quality of communication links, the transmission range and the remaining energy of nodes. This function has been used to estimate the energy consumption rate of communication areas and determine the selection of dominating nodes. Thus, a distributed topology control algorithm which is minimum connected, has been proposed. The experimental results show that network topology constructed by this algorithm has reliable communication links and high efficiency of energy utilization. It has the potential to significantly prolong the lifecycle of heterogeneous wireless sensor networks.

Abstract:Wireless sensor networks usually have limited energy and transmission capacity. A critical and practical demand is to online compress sensor data streams continuously. This paper makes the following contributions. First, using the built-in buffer of sensor node, a piecewise constant approximation based data compression algorithm with infinite norm error bound is presented, which is named PCADC-sensor and is a near online algorithm. Second, with infinite norm and square norm error bound respectively, this study proposes two online piecewise linear approximation based data compression algorithms in sensor node, named PLADC-sensor. A necessary and sufficient condition of PLA uniform approximation is given. Third, a piecewise linear representations based data compression algorithm in cluster head or sink, named PLRDC-cluster is presented. It does not need raw sensory data and can be applied to calculate aggregate functions. Last, the experiments on real-world sensor dataset show that the proposed algorithms match the sensor data stream model and can achieve significant data reduction.

Abstract:In this paper, based on the subnet abstraction mechanism, a fluid-based large-scale bandwidth-limited worm simulation model is proposed. In this model, the fluid simulation paradigm is leveraged to take away the huge volume of scanning traffic to reduce the requirements of computational capability and memory usage. Through extensive comparisons with the packet-level worm simulation and the measurement datasets, experiments demonstrate that the proposed simulation model is capable of high fidelity and low resource consumption, and thus, can fulfill the needs of the analysis of bandwidth-limited worm propagation characteristics and the verification of worm defense strategies.

Abstract:A resilient stochastic fair blue (RSFB) algorithm is proposed to preserve the existing normal network throughput under DDoS attacks. RSFB algorithm identifies benign flows according to their marking probability, which is derived from the stochastic fair blue algorithm. All the identified benign flows are then recorded in a benign flow queue (BFQ). Finally, the RSFB algorithm ensures the transportation of the packets from benign flows to the BFQ. A series of simulations are carried out to evaluate the anti-attack performance of RSFB and a serial of well known AQM algorithms. The results show that the RSFB algorithm i) is highly robust, ii) can well preserve the TCP throughput in the presence of DDoS attacks, iii) and obviously over performs the existing AQM algorithms when facing DDoS attacks.

Abstract:This paper proposes a resource on-demand approach for Web applications, which can efficiently online reconfigure clusters in response to time-varying resource requirements. It can also dynamically decide the number of running nodes and virtual machines deployed on them. It first predicts the future workloads of the applications with Brown’s quadratic exponential smoothing method to make reconfiguration catch up with demands. Next, it adopts a genetic algorithm to parallel find the optimal reconfiguration policy. Experimental results demonstrate the approach can online adapt the cluster resource according to the change of requirement, increase the cluster resource utilization and greatly reduce power consumption.

Abstract:In this paper, the performance evaluation and modeling of parallel file system based on Lustre file system is studied. After performing a survey on performance factors, a series of performance evaluations via experimental approaches and propose a performance relational model (PRModel). In the experimental and PRModel analysis, it is found that different performance factors have closed performance correlations. In order to mime the relational information, a novel relative performance predictive model (RPPModel) is proposed. This model can be used to predict the overhead over different performance factors. The model is validated through a series of experiments over a variety of performance factors. The experimental results show that the average relative errors results can be controlled within 17%~28%. This model is easy to use and can obtain better prediction accuracy.

Abstract:Based on the OpenMP-like parallel program, a loop scheduling and dynamic voltage scaling technology is coordinated to optimize system power consumption under the given performance constraint. First, the basic model for power-aware loop scheduling on the heterogeneous system is presented. After that, through theoretical analysis, it has been concluded that the lower bound of energy consumption for parallel loop scheduling on heterogeneous systems, can be used as a baseline to evaluate the efficiency of optimization technology. Furthermore, this paper induces the scheduling problem as a typical integer programming problem and proposes inner-processor loop re-scheduling method to further reduce power consumption. Finally, 10 typical kernel programs on a CPU-GPU heterogeneous system are created. The experimental results demonstrate that the proposed method can effectively reduce the total energy consumption of the whole system and improve the system energy efficiency.

Abstract:This paper presents expanded hypothesis based OpenMP static scheduling energy optimization algorithm—Improved Energy-Optimal OpenMP Static Scheduling, IEOSS. Based on EOSS algorithm, IEOSS algorithm exploits the impact of memory access latency on performance and energy of parallel loop. Due to cache miss, the optimal chunk S^* scales down processors’ voltage/frequency and obtains the minimal energy consumption. Five programs from NPB3.2-OMP for further evaluation. Take 480 processors, 64-byte cache line as an example: with 5% performance loss, IEOSS algorithm improves the energy savings of EP, IS, FT, CG, MG by 10.15%, 4.49%, 81.66%, 2.32%, 10.11% compared with energy consumption of OpenMP chunk scheduling. This shows that IEOSS can effectively improve energy optimization by combining DVS with choosing optimal chunk size.

Abstract:This paper addresses the issue of fault tolerance in transactional memory, and proposes a new method of fault recovery based on transaction rollback (FRTR). The method achieves an efficient fault recovery in transactional memory by utilizing the data-versioning mechanism of transactional memory to avoid the extra overhead of saving the checkpoint data. This paper provides the correctness of this method by proving the isolation of the fault tolerant transactional memory. Finally, this paper presents the design of the FRTRs for 5 test programs, including 4 SPLASH-2 benchmarks. The experimental results show compared with the checkpointing mechanism, the FRTR avoids the extra overhead of saving the checkpoint data and has a low overhead of the fault recovery.