Loading...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Current Issue

    • Development analysis of China HPC 2017
      YUAN Guo-xing1,YAO Ji-feng2
      2017, 39(12): 2161-2166. doi:
      Abstract ( 117 )   PDF (872KB) ( 406 )     

      According to the latest China HPC  TOP100 rank list released by the specialty association of mathematical & scientific software in October 2017, discusses and analyzes the current development of domestic HPCs from the aspects of overall performance, manufacturers, application areas and deployment sites. Meanwhile, the future development of domestic HPCs is looked forward to.

      A load-centric core pipeline design in
      array many-core processors
       
      ZHANG Kun,ZHENG Fang,XIE Xiang-hui
      2017, 39(12): 2167-2175. doi:
      Abstract ( 93 )   PDF (1177KB) ( 160 )      Review attachment
      Traditional processor pipeline is a branch-instruction-centric design where a large number of chip resources are used to improve the prediction accuracy of branches. We present a load-centric core pipeline design in array many-core processors. In the load-centric pipeline, the load instruction has higher priority to be issued and executed. Besides, we also propose a prediction mechanism to generate the load instruction’s source address in advance. The load-centric design decreases the stall latency of load instructions and therefore improves the pipeline’s performance and energy efficiency. Experimental results show that equipped with a 4KB size prediction table, the load-centric design can improve the pipeline performance and energy efficiency by 8.6% and 7% respectively
       
      Impact of junction depth on SET pulse width
      in 65nm bulk CMOS transistor
      LIU Rong-rong,CHI Ya-qing,DOU Qiang
      2017, 39(12): 2176-2184. doi:
      Abstract ( 95 )   PDF (1356KB) ( 154 )      Review attachment
      We investigate the impact of N+-N,P+-P and PN junction depth on the single-event transient (SET) pulse width in nano technology through TCAD simulations. The variations of voltage or temperature are also considered. Simulation results indicate that N+-N junction plays the most important role in influencing the SET pulse width. Meanwhile, we also investigate the impact of voltage and temperature on junction depth. Simulation results indicate that the voltage can significantly affect N+-N and P+-P junction while the temperature can significantly affect PN junction.
       
      An abnormal behavior detection method in Hadoop cluster
      CAI Wu-yue1,WANG Ke2,HAO Yu-jie2,DUAN Xiao-ran2
      2017, 39(12): 2185-2191. doi:
      Abstract ( 93 )   PDF (598KB) ( 192 )      Review attachment

      With the development of distributed computing technology, Hadoop, as a typical representative in the field of massive data processing, is vulnerable to hidden security threats, such as data breaches, due to weak security mechanism and lack of user activity monitoring. By combining with the characteristics of the principal component analysis, we perform parallel process through MapReduce to overcome the disadvantage of principal component analysis and improve the training efficiency. We propose an abnormal behavior detection method in Hadoop cluster, namely we compare the current user behavior patterns with historical behavior patterns to see if they match, which is taken as a metric for anomaly behavior detection. Experimental results indicate that our method can detect users' anomaly behavior effectively.

      A cross-clock-domain data transmission
      method based on indicator signals
      WANG Liang,FANG Liang,CHI Ya-qing,WANG Zhi-yuan
      2017, 39(12): 2192-2197. doi:
      Abstract ( 111 )   PDF (721KB) ( 171 )      Review attachment

      With the development of the system on chip (SoC) technology, the communication among chip modules is frequent. Asynchronous systems are popular due to low power consumption, speed up potential and strong anti-jamming capability, however, the design is complex and the problem of cross-clock-domain data transmission needs to solve. At present the most popular way is the first input first output (FIFO). As the complexity of the SoC increases, there are hundreds of modules. So a system integration using the FIFO consumes disproportionate  resources and power. Through the analysis of the characteristics of asynchronous transmission, we propose a way to use indicator signals to achieve cross-clock-domain data transmission. Compared with the FIFO, the proposal can reduce power consumption and its design complexity without performance decrease. Simulations on the two chip modules (CPU and FPGA) using Verilogon and the Vivado hardware of Xilinx company verify its feasibility. Compared with the design of the FIFO method, the proposed method has better application value.
      A parallel kNN algorithm based on OpenCL
      YANG Peng-lin,FENG Bai-ming,ZHOU Zhi-yang,WEN Xiang-hui
      2017, 39(12): 2198-2202. doi:
      Abstract ( 143 )   PDF (508KB) ( 178 )      Review attachment
      The kNN algorithm is a classical algorithm often used in machine learning and data mining programs. With the increasing amount of data, the execution time of the kNN algorithm increases sharply. In order to effectively utilize GPU and other computing units of modern computers to reduce the computation time of the kNN algorithm, we present a parallel kNN algorithm based on OpenCL, which parallelizes the two segments of bottleneck code: distance calculation and sorting. The algorithm adopts the fine-grained parallelization strategy and the optimized memory model in the phase of distance calculation and uses bitonic sort that can optimize memory model in the phase of sorting. We use Letter, one of UCI datasets, as the test set and E8400 AND GTS450 to run the kNN algorithm for testing. The computing speed of the parallel kNN algorithm accelerated by GPU is 40.79 times faster than that of its CPU version.

       

       
      Model order reduction of two-sided  H2
      optimality  based on the cross Gramian
      WANG Wei-gang1,YANG Ping1,JIANG Yao-lin1,2
      2017, 39(12): 2203-2209. doi:
      Abstract ( 114 )   PDF (626KB) ( 172 )      Review attachment
      Aiming at the single input and single output (SISO) linear time-invariant system, we propose a two-sided H2 optimal model order reduction method based on the cross Gramian and Grassmann manifold. Firstly, the H2 norm of the error system is expressed by the cross Gramian, which is regarded as the cost function of transformation matrices. Secondly, by introducing the Grassmann manifold, the cost function is viewed as a nonnegative real function defined on the Grassmann manifold. Thirdly, we perform the linear-search method on the Grassmann manifold to seek a couple of transformation matrices, which makes the cost function as small as possible. We apply this method to an SISO linear time-invariant system and obtain a more accurate reduced order system. Numerical examples verify the effective approximation of the proposed method.
       
      Design and implementation of the interconnected
      architecture of SDN and traditional IP network
      TANG Yong,WANG Wei-zhen,WANG Wen-yong,XU Bin-wei
      2017, 39(12): 2210-2216. doi:
      Abstract ( 136 )   PDF (878KB) ( 240 )      Review attachment
      The interconnected architecture of software defined network (SDN) and traditional IP network we propose is based on the following core idea: taking the SDN as a traditional “route”. The network layer reachability information (NLRI) of the entire network becomes consistent after “route” communicates with IP network by exchanging NLRI through the border gateway protocol (BGP ). We design an interconnected architecture based on the above idea. Besides, we test the models’ functions, and verify the validity of interconnected architecture in the multi-SDN scene and the performance. Simulation results show that the interconnected architecture can make the SDN and traditional IP network interconnect and communicate normally. The proposed interconnected architecture makes little change to network devices, and the changes mainly focus on the SDN controller which is software programmable, and it is helpful for this technology to be deployed and implemented in the real network environment.
       
      A regret greedy algorithm for the interference
      minimization  problem in wireless sensor networks
      SUN Pei-xin
      2017, 39(12): 2217-2223. doi:
      Abstract ( 94 )   PDF (783KB) ( 237 )      Review attachment

      The wireless sensor network is one of the active research areas in current information field. However, wireless sensors carry limited energy, which limits its service life. One way of reducing the energy consumption of a node is to reduce the interference caused by the simultaneous transmission of the signals from its neighboring nodes. The topology control technology can adjust every node transmission radius to reduce interference while maintaining network connectivity. Under the receiver centric interference model, solving the interference minimization problem based on the topology control technique in wireless sensor networks is NP-hard. The existing greedy algorithms, which are based on some greedy criterions to determine the transmission radius of each node successively, are fast but their accuracy needs to be improved. We explore some strategies to enhance the accuracy of the best greedy algorithm available in the literature, which allows partial regret, that is, whenever the maximum interference of the current network increases in one greedy iteration step, through two regret strategies we attempt to re-adjust the transmission radii of some nodes in order to reduce the maximum interference in the current network. Experimental results show that the accuracy of the existing greedy algorithm is improved within a slightly increasing time for our randomly generated instances.

      Frameworks and methods of cybersecurity detection
      LIU Qiang,CAI Zhi-ping,YIN Jian-ping,DONG De-zun,TANG Yong,ZHANG Yi-ming
      2017, 39(12): 2224-2229. doi:
      Abstract ( 111 )   PDF (1376KB) ( 165 )      Review attachment
      Network and information systems are developed as the core of key infrastructures, economy and society. Once such systems are attacked by adversaries or severe security events, the security of national economy and the common value of the society can suffer from adverse impacts. Hence, how to detect network threats and how to ensure the security of network infrastructure are vital for protecting key technologies and constructing national cybersecurity assurance systems. We systematically review several studies on intrusion detection framework, automatic signature generation, security detection theories and methods, network topology monitoring and routing control. Furthermore, we summarize several scientific findings, such as cybersecurity detection algorithm and framework, wireless network security detection, network monitoring and security enhancement. Finally, we discuss several interesting future directions on cybersecurity detection and control.
       
      A semi-definite programming approach
      to RSS-based localization in WSNs
      DING Tao,YU Jie-xiao,LIU Kai-hua,ZHAO Yu
      2017, 39(12): 2230-2235. doi:
      Abstract ( 143 )   PDF (806KB) ( 148 )      Review attachment

      Received signal strength (RSS) based localization is one of the common methods used in wireless sensor networks (WSNs) localization. Due to the non-linearity and non-convexity of the objective function, the traditional maximum likelihood estimator (MLE) can converge to local optimum when applied to WSNs localization. To overcome this problem, we propose a semi-definite programming (SDP) based localization algorithm. Firstly, the Taylor-series approximation is employed to linearize the objective function. Secondly, auxiliary variables are introduced to transform the original problem into a constraint optimization problem. Finally, the semi-definite relaxation (SDR) is applied to transform this constraint optimization problem into a SDP convex optimization problem. Comparison of simulation results shows that the proposed algorithm has higher localization accuracy and is more robust than the existing algorithms.

      Security proof of wireless mesh network
      authentication protocol based on logic of events
      LI Ya-nan,XIAO Mei-hua,LI Wei,MEI Ying-tian,ZHONG Xiao-mei
      2017, 39(12): 2236-2244. doi:
      Abstract ( 112 )   PDF (610KB) ( 175 )      Review attachment
      Wireless mesh networks are a combination of wireless local area network (LAN) and mobile ad hoc network, and they are of a new multi-hop network structure. The openness of wireless networks and the limitation of resources make wireless networks vulnerable to replay attack, impersonation attack, and so on. Logic of events is a formal method to describe the protocol state transition and algorithm in concurrent and distributed systems, which can be used to prove the security of network protocols. Based on the logic of events, we propose a series of properties that include multiple combinations of information interaction, no stacking, event matching, dereplication and remove future. We utilize these rules to reduce the redundancy and complexity of the protocol validation process, and improve protocol analysis efficiency. We study the bidirectional authentication protocol of wireless Mesh network clients, and conclude that the protocol can resist man-in-the-middle replay attacks. The mesh protocol is proved secure. The logic of events can be applied to the formal analysis and verification of similar complex wireless network protocols.
       
      An extended Winnowing plagiarism detection algorithm
      DUAN Xu-liang,YANG Yang,WANG Man-tao,MU Jiong
      2017, 39(12): 2245-2251. doi:
      Abstract ( 122 )   PDF (726KB) ( 180 )      Review attachment
      Plagiarism is a common problem faced by both academic and education fields. Although commercial plagiarism detection systems are relatively mature in terms of technology, they are not adopted in routine, real-time and lightweight fields such as student assignments detection because of high cost in efficiency and economy. We propose an extending classic Winnowing plagiarism detection algorithm, which can record the location and length while calculating the hash value of a text block. The location and length information in fingerprints can be used to locate and mark plagiarism text block in original documents. We describe algorithms for detecting, locating and plagiarism fingerprints index merging using the extended Winnowing, and performe some functional and performance experiments to test the algorithms. Experiments and actual running results show that the extended  Winnowing affects performance slightly, but it can meet the needs of small to medium applications under general hardware configuration. The extended Winnowing algorithm keeps the original features such as high efficiency, reliability and flexibility, and meanwhile gets improved in functionality and enhances its practicability and adaptability.
       
      Security analysis of Nayak-T protocol
      based on time stamp and private key signature
      XIAO Mei-hua1,MEI Ying-tian1,2,LI Wei1,LI Ya-nan1,ZHONG Xiao-mei1,SONG Zi-fan1
      2017, 39(12): 2252-2259. doi:
      Abstract ( 81 )   PDF (661KB) ( 153 )      Review attachment
      With the rapid development of information networks, cloud services step into people’s vision and the problems of information security in the cloud environment become a focus. Nayak protocol is a password authentication scheme based on the bidirectional authentication and session key agreement in the cloud environment. Targeting at man-in-the-middle attacks existing in Nayak protocol, we put forward an improved Nayak-T protocol. Nayak-T protocol adds in time stamp and changes their encryption ways inside message options to ensure the security of two-way communication through double encryption. We use the four channels parallel modeling method to model Nayak-T protocol and adopt SPIN to verify the security of this protocol. Analysis of modeling optimization strategies proves that the model testing that adopts static analysis, type checking and syntax reordering are most efficient. This method can be applied to the formal analysis and verification of similar complicated protocols.

       

       
      Application of deep learning methods in software analysis
      ZHANG Xian,BEN Ke-rong
      2017, 39(12): 2260-2268. doi:
      Abstract ( 105 )   PDF (521KB) ( 197 )     
      In the big data era, the rapid rise of deep learning has made great progress in many fields, such as computer vision. In recent years, with the accumulation of software artifacts, deep learning has begun to play an important role in software engineering domain. We review recent advances of deep learning methods in software analysis, summarize major research interests and application features. A batch of important results has been published, and related research shows an upward trend. In the end, limitations and problems in the application of deep learning methods are discussed.

       

       

       
      A fault tree auto-modeling method based on
      avionics system architecture model
      #br#  
      XU Wen-hua,ZHANG Yu-ping
      2017, 39(12): 2269-2277. doi:
      Abstract ( 186 )   PDF (1555KB) ( 224 )      Review attachment

      It is very necessary to conduct safety analysis on the safety critical avionics system by fault tree. However, fault tree is traditionally modeled in a manual way, which mainly relies on how well the analyzers understand the system. Meanwhile, the consistency between failure modes and system architectures is hard to be guaranteed due to the differences  in the understanding between the safety analyzers of the system and the system designers. Aiming at the above problems, we propose a fault tree auto-modeling method based on avionics system architecture model. The safety analysis model is constructed through adding safety properties to the system design model and embedding assertion mechanism of the advanced formal language AltaRica to describe the fault transition process. The fault tree auto-modeling is then conducted by tracing the data signal path of the model. The results of the case study on one cockpit display system indicate that the proposed method is able to conduct fault tree auto-modeling efficiently based on the avionics system architecture model, ensuring the completeness of the fault tree analysis results.

      An ALL-Uses coverage guided regression
      test case generating method
       
      YU Jia-wei,BEN Ke-rong
      2017, 39(12): 2278-2289. doi:
      Abstract ( 120 )   PDF (1088KB) ( 142 )      Review attachment
      In the regression testing process based on extended finite state machine (EFSM), the influence domain of software modification should be analyzed according to dependence change. Because there is no consideration for multiple modifications to the software at the same time, the analysis method is used to expose the trigger conditions and behavior statement errors in the model, but its efficiency is not high. We propose an ALL-Uses coverage guided regression test case generating method. We introduce the concept of dependence factors, modify the production rules, and select and sort the test cases that can cover the sub path. Aiming at the sub paths which cannot be covered by test cases, we use the method of finding the critical path in the AOE activity diagram to supplement it into a complete migration execution sequence. Experiments on three different software show that this method can improve the coverage of ALL-Uses and implanted errors under the premise of reducing the size of the test suite, and enhance the efficiency of regression testing.
       
      Model checking for fuzzy alternating-time temporal logic
      YUAN Hong-juan1,2,MA Yan-fang3,PAN Hai-yu1,2
      2017, 39(12): 2290-2296. doi:
      Abstract ( 89 )   PDF (447KB) ( 150 )      Review attachment
      Alternating-time temporal logic has been widely used as the specification language of open systems, and its model checking is one of the most important verification methods for open systems. To describe and check the properties of the open systems with fuzzy uncertainty information, we propose fuzzy alternating-time temporal logic and discuss its model-checking problem. Firstly, we present two semantics, the path semantics and the fixed point semantics, which are equal in value. Based on the result, the model-checking algorithm is given and its time complexity is discussed.
       
      Automatic patent query expansion
      based on word embedding
      LIU Meng-lan1,2,LIU Bin1,2,PENG Zhi-yong1,2
      2017, 39(12): 2297-2305. doi:
      Abstract ( 93 )   PDF (678KB) ( 209 )      Review attachment
      Patent retrieval is very different from information retrieval. Patent texts include right statement, abstract and full text, so we cannot simply apply the retrieval algorithms for common texts to patent retrieval. Patent retrieval usually faces the problem of low recall rate. Firstly, due to the highly professional and complex expression and terms of patent texts, it is not easy to capture the search intent from users’ queries, eventually leading to unsatisfactory search results. Secondly, inventors consciously create some distinctive words when they write patent texts to avoid being retrieved. Many retrieval algorithms are designed to improve the recall rate, however, many problems remain to be solved and the effectiveness be improved. We propose an automatic patent query expansion model based on word embedding. On the basis of word embedding, a keyword network in patent domain is constructed, and then the dense subgraph discovery algorithm is used to find expansion terms, which can improve the effectiveness of expansion terms. Extensive experiments on the CLEF-IP 2012 dataset show that the proposed algorithm can guarantee the flexibility and effectiveness of expansion terms and improve the recall rate of patent retrieval.
       
      Marked complex sentence hierarchy analysis
      based on semantics and rules
       
      LI Yuan1,DIAO Sheng-quan1,HU Jin-zhu1,2,ZHAI Hong-sen1,YANG Meng-chuan1,HUANG Wen-can1
      2017, 39(12): 2306-2313. doi:
      Abstract ( 103 )   PDF (661KB) ( 167 )      Review attachment
      Chinese complex sentence hierarchy analysis is one of the challenging topics in the field of Chinese information processing. In order to solve the accuracy decline of automatic recognition caused by inadequate relationship marks, we analyze formal semantic knowledge that affects sentence association, based on which we construct a small sentence association recognition algorithm and apply it to the hierarchy decision rules of complex sentences to help analyze the hierarchical relationship. As for the analysis of the hierarchy of single and multiple marked complex sentences, we leverage the shift-reduce algorithm based on collocation rules. Finally, we propose a marked complex sentence hierarchy analysis model, which combines semantics and rules. Experimental results show that this method enhances the accuracy of automatic identification to a certain extent.