Current Issue

• 2014, No. 11　Published:25 November 2014 Last issue    Next issue
  Columns in this issue: 论文

• 论文

  A data race detection and witness generation
  method for multithreaded programs

  ZHANG Xiaodong1，ZHENG Qinghua1，LIU Ting1，YU Lechen1，LIU Pei1，YANG Zijiang2

  2014, 36(11): 2047-2053. doi:

  Abstract ( 174 )   PDF (437KB) ( 285 )   　　

  Data race is a common problem in multithreaded programs. Due to the state explosion of thread interleaving, it is difficult to accurately detect bugs triggered by data races. Moreover, it is hard to replay and triage such bugs because of the facts that thread scheduling is difficult to control and the number of interleaving is astronomically large. A data race detection and witness generation method for multithreaded programs is proposed. A semantic model is designed to encode the execution path and the condition of data races as firstorder logic formula. The satisfiability of the formula, solvable by constraint solvers, indicates the existence of data races under multiple thread interleavings without requiring repeated executions. The solutions produced by an SMT solver serve as witnesses to localize and verify data races. In the experiments, we compare existing tools threadsanitizer and helgrind with ours to detect the data races for 10 multithreaded programs. It is shown that our method can detect 287.5% and 264.7% more bugs respectively without false alarm, while the false alarm positive rate of threadsanitizer and helgrind are 10.5% and 9.8%.

  An energy-saving algorithm for
  MapReduce-based virtual cluster       

  DENG Danting1,TENG Fei1,2,LI Tianrui1,YANG Hao1

  2014, 36(11): 2054-2060. doi:

  Abstract ( 122 )   PDF (517KB) ( 253 )   　　

  In the global energy crisis, many researchers begin to pay close attention to the problem of data centers’ energy consumption. On the premise of meeting the users’ demand, reducing the active nodes of adata center can effectively reduce the whole energy consumption. Virtual machine migration is a traditional way to reduce active nodes, but causes huge system cost. An energysaving algorithm for MapReducebased virtual cluster, named Online Time Balance Algorithm (OTBA), is proposed. The proposed algorithm can reduce the number of active physical nodes, reduce the energy consumption effectively, and avoid migrating the virtual machines. The objective function and the variable factors are determined by building the energy consumption model, the queue model and the MapReduce performance model. Since OTBA is based on virtual cloud environment and online MapReduce, it can make a  tradeoff between the runtime of virtual machines and the resource utilization so as to minimize the number of the activated physical servers in the data center and the energy consumption. At last, the algorithm is validated through experiments in simulation environment and on Hadoop platform.

  QoS-aware cloud service composition based on time series             

  XIAO Wenjuan，DUAN Yucong

  2014, 36(11): 2061-2066. doi:

  Abstract ( 141 )   PDF (518KB) ( 228 )   　　

  In this paper, we study QoS-aware cloud service composition based on time series, taking the sustaining change process of service QoS preference into research scope of cloud service composition,and transform the composition of cloud services into similarity comparison problems between time series.Euclidean distance and the extend Frobenius norm distance are used to measure similarity between two-dimensional time series respectively. In the next,the extend Frobenius norm distance or Euclidean distance based on principal component analysis and BruteForce method are adopted to measure the similarity between multidimensional time series. Experiments show that the extend Frobenius norm distance has better performance on similarity measurement in time and accuracy.

  EGovCloud: A cloud-service based e-government framework   

  YANG Dongju1,WANG Jing1,JIANG Guihuang2

  2014, 36(11): 2067-2073. doi:

  Abstract ( 162 )   PDF (1159KB) ( 273 )   　　

  In order to facilitate on demand resource sharing and cross-organizational collaboration in E-Government systems,the paper proposes a cloud-service based framework(EGovCloud),which utilizes the virtual resource repository to realize resource physically distributed storage and logically centralized management.E-Government metadata specifications are constructed as a unified semantic infrastructure and therefore support cross-organizational heterogeneous resource sharing and management.We explore the architecture of EGovCloud and the key technologies involved,and demonstrate the applications in constructing E-Government systems.

  A system for automatically tailoring
  Android applications’permissions

  BAI Xiaolong

  2014, 36(11): 2074-2086. doi:

  Abstract ( 138 )   PDF (1120KB) ( 277 )   　　

  Android uses the permission system to control application access.In the permission system,applications have to declare relevant permissions before they access some system resources.To be secure and trusted,applications should follow the principle of least privilege.However,in reality,many applications do not follow this principle,which may bring security threats.To solve this problem, we design and implement a novel system for automatically tailoring Android applications’permissions,called PTailor. PTailor analyzes and modifies the Android application installation file (APK file) so as to make it follow the principle of least privilege.Firstly,PTailor extracts the system API calls from the APK file and gets the API’s corresponding required permissions from a predefined APItopermissions map.In this way,PTailor can get the shortest permission list that this application really requires.PTailor uses this permission list to match the application’s permission declaration file and removes those unused permissions.At last,the modified permission declaration file and the original code file are zipped to a new APK file that follows the principle of least privilege without changing its structure and semantics.PTailor is used to process 1246 Android applications in order to evaluate its performance.The experimental results show that APK files can be processed in a short time and PTailor has little influence on most tailored applications.

  Energy efficient routing for linear wireless sensor
  networks based on fixed node location           

  WANG Nan，MENG Qingfeng

  2014, 36(11): 2087-2093. doi:

  Abstract ( 125 )   PDF (778KB) ( 239 )   　　

  The energy of Wireless Sensor Networks (WSNs) is very limited because battery is used for power supply in nodes normally.Therefore, the key issue that needs to be solved,is to improve the energy efficiency and prolong the lifetime of networks.In some practical applications of linear WSNs,due to the particularity of the monitoring environment and objects,the location of the monitoring points that is not in random distribution is fixed in advance, and this results in the limitation of applicability for the existing linear routing and the nodal arranging scheme with variable distances. Therefore, a grouped multihop routing algorithm based on equal distance, named GMRED, is proposed.The energy consumption mathematical model of the networks is constructed, and the network average energy is determined by the network length,the number of nodes and the groups. How to solve the problem of the group numbers when the network has minimum average energy is discussed. Finally, the Matlab software is used for simulation and analysis.The results show that,compared with the singlehop routing algorithm,the multihop routing algorithm,and the clustering multihop routing algorithm,the GMRED has the minimum average energy consumption and the maximum network lifetime because it has no cluster head.   

  An efficient forwarding strategy based on
  XOR operation in opportunistic network          

  LIU Hui1,2，CHEN Zhigang1,2，WU Jia1,2，WANG Dan1,2，ZENG Jianfeng1

  2014, 36(11): 2094-2099. doi:

  Abstract ( 141 )   PDF (541KB) ( 225 )   　　

  Through studying the ways of forwarding information in opportunistic networks,the communication nodes in the neighbourbood can be traversed and the two nodes can be compared.Through the form of the intersection,the neighbor node with the largest XOR is chosen as the next hop to transfer the information so that a communication path with maximum effectiveness is formed. Based on this analysis process, an efficient forwarding strategy based on XOR operation in opportunistic networks (FSXO) is proposed.The proposal is compared with classical algorithms in opportunistic networks,and the simulation results show that the proposed FSXO strategy can reduce the presence of invalid copy data at high transmission rates,thus effectively reduce the routing overhead and resource consumption.     

  A noval P2P streaming protocol and its traffic model          

  JI Yimu1,2,YUAN Yongge1,ZHANG Surui1

  2014, 36(11): 2100-2105. doi:

  Abstract ( 123 )   PDF (785KB) ( 239 )   　　

  The RTMFP protocol of FlashP2P technique is analyzed in detail and a FlashP2P traffic recognition algorithm based on RTMFP packet detection is proposed.The algorithm is used to effectively identify the FlashP2P streams of the domestic mainstream video sites. On this basis,the characteristics of FlashP2P flow are analyzed and their selfsimilarity is proved.Finally, based on the empirical mode decomposition of the ARIMA, we build a model to predict the selfsimilar network traffic. The simulation results show that the model not only reduces the complexity of the algorithm but also has high shortterm forecast accuracy.

  A dynamic network performance evaluation
  method based on multi-dimensional measurement          

  MAO Li1,2，QI Deyu1

  2014, 36(11): 2106-2113. doi:

  Abstract ( 119 )   PDF (844KB) ( 249 )   　　

  Aiming at overcoming the shortcomings of static and partiality in traditional network evaluation methods,based on multidimensional matterelement models, we propose a dynamic network performance evaluation method.This method is discussed from the aspects of multidimensional matterelement models of network evaluation,indicator system of network evaluation,and policies of fuzzy analytic hierarchy process.A campus network example shows that the evaluation method helps network managers track and monitor network operation dynamically and quantitatively,and improve the users’ability to observe and controll the network.

  Data distribution in vehicle Ad-hoc
  networks using bus assistance          

  YAO Hong,TENG Chao,CONG Lei,LIANG Qingzhong,HU Chengyu

  2014, 36(11): 2114-2118. doi:

  Abstract ( 104 )   PDF (616KB) ( 250 )   　　

  Intervehicle communications forms vehicle AdHoc networks,which have attracted extensive attention in academia.Due to vehicles’ dynamic nature and the intermittent connection of the signal coverage, the communication behaviors of such networks exhibit the characteristics of the delay tolerant network. Observing the characteristics of buses’ running tracks in urban blocks where there is high density of vehicles, and using the network coding technology and the carry forward method, we propose a data distribution algorithm based on bus assistance to achieve efficient and reliable content sharing.Experiments show that,under the premise of reducing network traffic overhead, the algorithm can effectively improve the delivery success rate of the content sharing data in urban blocks. 

  A novel heuristic edge ordering strategy
  and its performance analysis           

  PAN Zhusheng,MO Yuchang,ZHONG Farong,LIU Xuan,WU Huan

  2014, 36(11): 2119-2127. doi:

  Abstract ( 118 )   PDF (1364KB) ( 215 )   　　

  The computational complexity of the BDD (Binary Decision Diagram) based network reliability method is linear correlated to the size of BDD that heavily depends on the quality of edge ordering.Because it is still NP-hard to find the optimum edge ordering, heuristic ordering methods such as BFS (BreadthFirstSearch) or DFS (DepthFirstSearch) are commonly used in practice.For the edge ordering strategy, boundary set is first used to analyze the characteristics of constructing BDD,and then a high performance edge ordering strategy based on the boundary set is proposed.Several experiments show that the new strategy outperforms the classic methods such as DFS and BFS.The results extend new space for network reliability analysis method using BDD in largescale networks.

  A packet detection method based on Negative Pattern           

  TANG Xiangyan, CHENG Jieren, YIN Jianping, GONG Deliang

  2014, 36(11): 2128-2131. doi:

  Abstract ( 143 )   PDF (479KB) ( 204 )   PDF（mobile） (479KB) ( 6 )   　　

  To solve the problems in intrusion detection based on pattern matching, we present a packet detection method based on negative pattern,which uses the negative pattern matching strategy.Firstly,the method detects the NP pattern in the to-be-detected packets and divides the data into segments according to NP pattern.Secondly,the system detects the data segments by NP pattern.The experimental results show that the method can reduce the false alarm rate and improve the detection efficiency of the system.

  论文

  Research on tripartite key establishment
  protocol for wireless sensor networks           

  ZHENG Minghui,LIU Zhaozhao

  2014, 36(11): 2132-2136. doi:

  Abstract ( 112 )   PDF (395KB) ( 202 )   　　

  A provably secure authenticated multiple key establishment protocol for Wireless Sensor Networks (WSNs) is proposed.Security of the protocol is based on the computational infeasibility of solving elliptic curve discrete logarithm problem and computational DiffieHellman problem on bilinear pairing.The authentication among the nodes is one of the most challenging security requirements in WSNs.To achieve this security goal, it is required to establish a correct session key among the three adjacent nodes of WSNs. It is proved that the proposed protocol is secure against the attacks on data integrity and the known key security attacks on session key.It also provides perfect forward secrecy.

  An AHP-based browser vulnerability taxonomy              

  MENG Yongdang1,CAI Jun1,HE Jun1,JI Feng2

  2014, 36(11): 2137-2141. doi:

  Abstract ( 131 )   PDF (551KB) ( 243 )   　　

  Through analyzing the causes and effects of the browser vulnerabilities, we propose an AHPbased browser vulnerability taxonomy using the Analytic Hierarchy Process (AHP).According to the causes and attack effects of vulnerabilities,this taxonomy classifies the browser vulnerabilities,and compares the classification results with that of the CNNVD taxonomy.The results reveal that the applicability of the proposal is better.  

  An event query algorithm based on Hash function and energy balancing         

  ZHANG Caineng，GONG Deliang，LI Shengxin

  2014, 36(11): 2142-2147. doi:

  Abstract ( 118 )   PDF (748KB) ( 210 )   　　

  Unfixed location events and queries in wireless sensor networks is an important research topic.To achieve efficiency and maximizing the network life cycle, we propose an event query algorithm based on Hash function and energy balancing.In the algorithm,a sensor node only needs to care about the neighbor nodes within its communication range while not knowing the status of the entire network.The algorithm features less redundant data,less query energy consumption, a longer network life cycle, and ease of implementation.The simulation experiments in OMNET++ network simulator show that,compared with the classic routing algorithm, the proposed algorithm can query events quickly and effectively,while minimizing and balancing the energy consumption and prolonging the network life cycle.     

  An approximate data collection algorithm based
  on prediction model in sensor networks          

  WANG Min，WU Zhongbo，XU Degang,QU Junfeng,WU Zhao

  2014, 36(11): 2148-2152. doi:

  Abstract ( 122 )   PDF (541KB) ( 225 )   　　

  The modelbased data collection technology which can inhibit unnecessary data transportation and save energy effectively has been widely applied in sensor networks. We improve the traditional modelbased data collection technology and put forth an approximate data collection algorithm based on the Kalman filter,called ADCA, which can collect data effectively within a given range of error.In ADCA,sensor nodes are organized as clusters.Cluster header and cluster members build the Kalman filter respectively and save their mirror models.Cluster header can produce approximate data for cluster members,so some user queries can be answered by cluster header.Experiments show that ADCA has good performance.

  Analysis and improvement of two provable secure
  proxy signature schemes in the standard model      

  WU Shukun

  2014, 36(11): 2153-2158. doi:

  Abstract ( 102 )   PDF (383KB) ( 234 )   　　

  The security of two provable secure proxy signature schemes based on Waters in the standard mode, which are proposed by Ji et al. and Yu et al. recently,is analyzed,and the two drawbacks of the two schemes are pointed out: delegation forgeability exists so that anyone may disguise as the original signer to issue valid proxy delegation warrants to the proxy signer, and proxy signature forgeability exists so that anyone can forge the signature of the proxy signer without knowing the private key of the proxy signer.An improved proxy signature scheme that can overcome the drawbacks is proposed,and its correctness,efficiency and security are analyzed in detail. The analysis shows that the improved scheme has the same length of signature and almost the same execution efficiency in comparison to the two original schemes,but has higher security.

  Path-directed regression test suite augmentation         

  YIN Pengchuan，BEN Kerong

  2014, 36(11): 2159-2163. doi:

  Abstract ( 135 )   PDF (473KB) ( 225 )   　　

  To test the evolution software fully,new test cases need to be generated in regression testing typically.concolic testing is a hybrid software verification technique that performs symbolic execution along a concrete execution path,and can perform all the feasible paths of a program by generating test data.Concolic testing only focuses on the program under test with both existing test cases and software evolution information unexploited in regression testing, which  results in a large number of invalid test data generation,wasting resources and time.To address this problem,a pathdirected regression test suite augmentation approach is proposed. With the guidance of target paths,the approach selects the test cases conducive to cover target paths according to software evolution information,skips initial overlapping subpaths by using the existing test cases,takes the followup target subpath to guide concolic testing and generates test data covering the target paths.Case analysis demonstrates that the proposed approach can effectively reduce concolic testing paths in comparison to traditional concolic testing, and improves the efficiency of test data generation while covering feasible paths of the program.

  An ontology algorithm based on
  iterated Laplacian semi-supervised learning        

  PENG Bo,XU Tianwei,LI Zhen,GAO Wei

  2014, 36(11): 2164-2168. doi:

  Abstract ( 125 )   PDF (514KB) ( 237 )   　　

  Ontology similarity measure and ontology mapping are central contexts for knowledge representation and information processing.An ontology algorithm based on iterated Laplacian semisupervised learning is proposed.Using iterated Laplacian semisupervised learning method,all the vertices of the ontology graph are mapped into real numbers.Then,the ontology similarity measure algorithm and the ontology mapping strategy are obtained by comparing the differences of their corresponding values.Two experiments confirm that the new algorithm has high quality for special application fields.      

  Applying an improved particle swarm
  optimization algorithm in virtual network mapping         

  HU Ying,ZHUANG Lei

  2014, 36(11): 2169-2173. doi:

  Abstract ( 98 )   PDF (606KB) ( 218 )   　　

  Using the Particle Swarm Optimization (PSO) algorithm to solve the problem of virtual network embedding can reduce the consumption of network resource, but it also brings premature convergence.An improved PSO algorithm is proposed,which adds random factors,operates along the original direction, and changes the introduction  of history factors to the search process.The proposal not only keeps the instruction of history factors to the search process but also increases the search range,thus relieving, the premature convergence problems to a certain extent.The experimental results demonstrate that the improved PSO algorithm can be applied to virtual network mapping and effectively reduce resource consumption in comparison with the original PSO algorithm.