ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 May 2014, Volume 51 Issue 5
Research on Space Internetworking Service Based on DTN
Lin Chuang, Dong Yangwei, and Shan Zhiguang
2014, 51(5):  931-943. 
Asbtract ( 678 )   HTML ( 1)   PDF (2743KB) ( 717 )  
Related Articles | Metrics
The increasing demand on space communication stimulates the internetworking and space-ground integration for space communication systems. Space networks are featured in heterogonous subnets, dynamic topology, large transmission delay, and high link errors. TCP/IP protocol suite requires stable connectivity and short transmission delay, which cannot be satisfied in space networks. As a result, existing protocols for the current Internet cannot be directly applied to space networks. Delay/disruption tolerant network (DTN) is a general message-oriented overlay network architecture that can be adapted to space networks. This makes DTN a very promising approach for interconnecting space communication systems. This paper first demonstrates the system architecture which applies DTN in space internetworking service (SIS), and then analyzes the key components and working patterns including protocol stack, message forwarding mechanism, naming and addressing, licklider transmission protocol (LTP), etc. Then we give a real scenario of Mars exploration. By surveying some key technologies and research trends, we analyze some technical problems to be solved and propose some future research directions including routing, security, and QoS control. And then, we introduce related development efforts, practice, and aircraft verification projects. Finally, we analyze the prospects for the research and application of DTN and SIS technologies in China.
Data and Protocol Optimization Techniques in Wide Area Networks
Dong Pingping, Wang Lezhi, Sun Jun, and Wang Jianxin
2014, 51(5):  944-958. 
Asbtract ( 556 )   HTML ( 0)   PDF (2833KB) ( 623 )  
Related Articles | Metrics
In recent years, with the rapid development of computer networks, people increasingly rely on computer networks to obtain information. However, ubiquitous applications are deployed over the wide area networks (WANs), which have shown low transport efficiency due to the natural characteristics of WANs such as high latency and high packet loss rate. WANs optimization, also known as WANs acceleration, which aims to accelerate a broad range of applications and protocols over WANs, has become a hot topic in both academia and industry. Based on the in-depth study of the current WANs optimization techniques from different aspects that cause the WANs performance degradation, a survey is presented on the state of the art of WANs optimization or WANs acceleration techniques from the networking point of view including data optimization and protocol optimization. Data optimization also includes data compression, data caching, data pre-fetching and data de-duplication, while protocol optimization is depicted with transport layer optimization and application-layer protocol optimization. Meanwhile, how these acceleration techniques can improve application performance, mitigate the impact of latency and loss, and minimize bandwidth consumption is also illustrated. In addition, widely deployed WANs acceleration products incorporating major WANs optimization techniques are discussed. Finally, a conclusion and some perspectives are given.
EasiSHA: A Reconfigurable Node Architecture for IoT Based on Joint Design of Software and Hardware
Shi Hailong, Li Dong, Qiu Jiefan, and Cui Li
2014, 51(5):  959-973. 
Asbtract ( 483 )   HTML ( 0)   PDF (3361KB) ( 430 )  
Related Articles | Metrics
More and more IoT (Internet of Things) systems have been deployed in a wide variety of applications, and they are influencing many aspects of our life. However, IoT applications are characterized by their strong domain specificity. This characteristic of IoT has brought new design requirements of the node. Firstly, IoT nodes must have strong versatility, and be able to adapt to a variety of applications. Secondly, IoT nodes need to have strong professional characteristic, and can be customized to fit well a specific application. To meet these requirements, we propose a reconfigurable node architecture for IoT based on the joint design of software and hardware, named EasiSHA. Specifically, we present a task scheduling mechanism, which can change dynamically the implementation of tasks based on the performance requirements. Thus, it can reduce redundancy of hardware and software, and also minimize overall power consumption. Furthermore, we propose a shield layer between applications and tasks to improve the reusability of software, and reduce the correlation of applications and tasks. Therefore, the development speed of applications is improved and system development costs are reduced. Based on EasiSHA, we have designed a node prototype and applied it to a number of actual applications. The verified results show that it can accelerate the speed of deployment of the IoT applications, and reduce R&D costs effectively.
RBSA: Repeatedly-Woken Based Scanning Algorithm for Road Network Surveillance
Chen Liangyin, Li Zhanghua, Wang Chaolong, Zhang Jingyu, Yan Bingshu, Liu Yan, Yin Feng, and Chen Pengpeng5
2014, 51(5):  974-983. 
Asbtract ( 512 )   HTML ( 0)   PDF (3023KB) ( 463 )  
Related Articles | Metrics
This paper proposes a repeatedly-woken based scanning algorithm (RBSA), which is tailored and optimized for the road network surveillance within low duty-cycle WSNs. Our design is mainly based on the facts that the movement of targets (e.g., vehicles) is always confined in roadways with limited speed and the road network maps are normally easy to obtain from the map services provider or from the Internet. The main idea is that each sensor node along the roadway successively wakes up and sleeps for k times in one round or sleeps with sufficient use of the overlapped sense area between two adjacent nodes, while the detection of moving targets is guaranteed before they reach specific protection points such as temporary base camps. The duty cycle of each node is consequently minimized, resulting in obvious extension of the network lifetime. We provide complete theoretical analysis on the performance of RBSA in terms of network lifetime and average detection delay. Extensive simulation shows that RBSA extends network lifetime by 80% in typical configuration parameters compared with the original classic scanning algorithm, while only small average detection delay is extended.
A Low-Power FIS Mechanism and Energy Analysis for Green Router
Yuan Bo, Dai Yi, and Wang Binqiang
2014, 51(5):  984-996. 
Asbtract ( 404 )   HTML ( 0)   PDF (4071KB) ( 489 )  
Related Articles | Metrics
With the development of the next generation Internet, the existing router architecture faces many problems, such as performance,complexity and power consumption. With the increasing of network size, how to implement a low-power forwarding is a challenge in green and high-performance router design. In this paper, we consider building a FIS mechanism based on forwarding in switching idea. The memory requiring and accessing are reduced by blurredly forwarding and piping switching. The multilevel line framework in FIS is made by many slow processing units. It can obtain higher performance and lookup speed through cosmically running. Simultaneously, it can reduce the complexity of hardware implementation. Energy model of FIS and FBS is established. We propose different modeling methodologies for node switches, internal buffers and interconnect wires inside switch fabric architectures. In this paper four switch fabric architectures are analyzed under different traffic throughput and different numbers of ingress/egress ports. Experiments using real-life routing tables demonstrate that our FIS solution can reduce the power of routing lookup by 12.5% than FBS clearly. This framework and analysis can be applied to the architectural exploration for low power high performance network router designs.
An Efficient Fault-Tolerant Event and Event Boundary Detection Algorithm for Wireless Sensor Networks
Xu Xiaolong, Geng Weijian, Yang Geng, Li Lingjuan, and Yang Zhen
2014, 51(5):  997-1008. 
Asbtract ( 345 )   HTML ( 0)   PDF (2835KB) ( 438 )  
Related Articles | Metrics
The event and event boundary detection is one of the most important applications of wireless sensor networks(WSNs) . The accurate node fault detection is the premise of improving the efficiency of the event and event boundary detection. However, current approaches consider fewer fault types of sensor nodes, which are very possible to mistake the event boundary nodes for the fault nodes; and current approaches also need nodes to communicate with each other frequently. Thus current approaches usually lead to low level of the fault-tolerant ability of WSNs systems, bad availability of nodes and high energy consumption. Therefore, in order to increase the accuracy of detection rate and the efficiency of energy consumption, a new fault-tolerant event and event boundary detection algorithm for wireless sensor networks is proposed. The algorithm adopts the temporal correlated information to detect event, and adopts the spatial correlated information to detect fault and event boundary. The node reliability level restore mechanism is also proposed, enabling nodes to act according to the change of network environments, and adjust their reliability level automatically. Experimental results show that the fault-tolerant event and event boundary detection algorithm proposed in this paper has good performance even in the conditions of high fault probabilities.
DCent: A High Extensible Data Center Networking Structure Using Dual-port Servers
Zhu Guiming, Xie Xianghui, Guo Deke, Lu Feifei, and Tao Zhirong
2014, 51(5):  1009-1017. 
Asbtract ( 557 )   HTML ( 0)   PDF (3578KB) ( 446 )  
Related Articles | Metrics
A fundamental goal of data-center networking is to efficiently interconnect a large number of servers with low equipment cost while keeping high network bandwidth. The traditional tree-based networking schemes were born with the performance bottleneck and extensibility problems. To tackle the problems, some server-centric data center networking structures have been proposed. However, they are not truly expandable and suffer a low degree of regularity and symmetry. Since servers generally have two network interface card ports, how to design a high extensible and cost-effective data center networking structure with high performance based on servers’ two network interface card ports and without expensive high-end switches is a challenging problem. This paper proposes a high extensible modular server-centric data center networking structure called DCent, which requires that servers have two network interface card ports and only use commodity off-the-shelf mini-switches. We also develop low-overhead and robust routing schemes for DCent. Mathematical analysis shows that DCent has excellent topology properties. Although the server degree is only 2, DCent can be expanded very easily to encompass hundreds of thousands servers with the low diameter and high bisection width. DCent also has fine modularity where servers interconnect by switches which avoids direct connection between servers.
ECG Signal Recovery Problem Based on Compressed Sensing Theory
Zhang Yingchao, Mao Dan, and Hu Kai,
2014, 51(5):  1018-1027. 
Asbtract ( 372 )   HTML ( 0)   PDF (4493KB) ( 708 )  
Related Articles | Metrics
Body sensor network (BSN) is a new network which can monitor the patient’s physiological characteristics in real time, thus the network is widely utilized to improve the level of healthcare for people through the computer techniques, such as intelligent information processing, new network services and so on. Compressed sensing (CS) is a new theory of signal acquisition and decoding, which not only breaks through the bottleneck of the law of traditional sampling, but also makes the signal sampling and compression done at the same time. So, CS is extensively used in medicine, astronomy, pattern recognition and so on. For now, CS is paid more and more attention to by many researchers. This paper faces the recovery problem of electrocardiogram (ECG) signals through compressed sensing theory. According to the various performance of all kinds of wavelet basis conducted as sparse basis, we hope to find an optimal wavelet basis that makes the ECG signal restored precisely and stably through a lot of experiments. The experimental results demonstrate that there exists a set of wavelet basis which can make a variety of ECG signals recuperated with high accuracy and strong robustness. The result can provide ideas for discussing the recovery problem of ECG signals furthermore.
A Behavior-Based System Resources Access Control Scheme for Android
Lei Lingguang, Jing Jiwu, Wang Yuewu, and Zhang Zhongwen,
2014, 51(5):  1028-1038. 
Asbtract ( 595 )   HTML ( 0)   PDF (2275KB) ( 693 )  
Related Articles | Metrics
As a coarse-grained access control mechanism, Android permission model cannot effectively prevent the applications from abusing system resources to launch attacks. In this paper, a behavior-based system resources access control scheme is proposed, to regulate the applications’ behavior in their system resources accessing and prevent the resources from being abused by applications. Firstly, we define a secure behavior pattern for each security-related critical system resource access operation using temporal logic of causal knowledge (TLCK) logic, and dynamically monitor the behavior of the applications. Then, the access control to these system resources is implemented through comparing the applications’ dynamic behavior with the resources’ secure behavior patterns. Compared with the malicious code detection schemes based on malicious behavior signatures, secure behavior patterns are easier to be defined and can be used to detect unknown attacks. Finally, we achieve a behavior-based resources access control system for short message service (SMS) attacks, the most preferred attacks for Android. And the experimental results demonstrate that this scheme has good performance in terms of effectiveness and efficiency.
A Real-time Network Threat Recognition and Assessment Method Based on Association Analysis of Time and Space
Lü Huiying, Peng Wu, Wang Ruimei, and Wang Jie
2014, 51(5):  1039-1049. 
Asbtract ( 421 )   HTML ( 2)   PDF (2685KB) ( 590 )  
Related Articles | Metrics
How to identify successful threat activities and current security state, is the prerequisite and key to network real-time threat assessment. To do this, all the detected threats need to be associated and studied in many ways and multiple directions. Aiming at this issue, a network real-time threat identification and quantitative assessment approach is proposed based on the association analysis from two dimensions of time and space. This approach fully considers spatial complexity and temporal dynamic under network attack-defense confrontation environment. Firstly threat state transition graph is constructed to simulate intruding process and model threat scenarios. Based on the graph, by associating threat spreading paths in temporal dimension and correlating with threat state features in spatial dimension, valid threats can be filtered out and current threat state can be recognized. Then a multi-granularity hierarchical assessment method is put forward to evaluate network threat. This method takes entity value, threat weight and threat success probability as evaluation indexes in order to quantitatively analyze threat indexes of single state, path and the whole network respectively. Therefore, the results report network real-time risk situation in different levels. Finally simulation experiment verifies the effectiveness and advantage of the approach, and the approach can reveal threat situation more thoroughly and provide valuable guide for intrusion response decision-making and dynamic defense strategy adjusting.
A Sensitivity Measurement for Sensitive Information Processing
Sha Letian, Fu Jianming, Chen Jing, and Huang Shiyong
2014, 51(5):  1050-1060. 
Asbtract ( 347 )   HTML ( 1)   PDF (1968KB) ( 527 )  
Related Articles | Metrics
Application software needs to use sensitive information to build up the authentication between client and server, so how to measure the security or sensitivity of sensitive information during processing is an open issue. According to the procedure of sensitive information processing and context of its occurrence, inherent property, variable property and inferenced property have been defined, the mapping rules from these properties to data operations have been designed, and a method of sensitivity calculation based on AHP (analytic hierarchy process) and TOPSIS (technique for order preference by similarity to an ideal solution) has been proposed. This method can demonstrate dynamic changes of sensitivities among sensitive information processing to support security prevention against information leakage and attacks, and can be applied to security analysis and trust measure of trustworthy software on sensitive information. Finally, experimental results demonstrate that this method can describe sensitivity changes among sensitive information processing, and discover the potentially dangerous points in this processing, so its effectivity has been verified.
Fine-Grained Parallel Regular Expression Matching for Deep Packet Inspection
Liu Xingkui, Shao Zongyou,, Liu Xinchun, and Sun Ninghui
2014, 51(5):  1061-1070. 
Asbtract ( 651 )   HTML ( 0)   PDF (3133KB) ( 520 )  
Related Articles | Metrics
Regular expression matching plays an important role in many critical network applications. Deterministic finite automata (DFA) is an effective way to implement regular expression matching, however, DFAs’ inherent sequential state transition makes them impractical for high-speed backbone networks. In this paper, a novel fine-grained parallel DFA, called LBDFA (Loopback DFA), is proposed to improve the matching performance of DFAs. The method is based on the observation that most transitions occur among a small number of states while other states are rarely accessed. Furthermore, the frequently traversed states, called Loopback states in this paper, usually remain unchanged for a large number of consecutive input characters in the process of state transitions. Therefore a remarkable improvement can be achieved by parallelizing the consecutive state transitions on Loopback states. A Bloom filter is employed to eliminate the temporary deviation in transitions in order to further improve the parallelism of LBDFAs. Experimental results on rule sets from L7-filter and Snort show that the LBDFA can meet the demand of regular expression matching for backbone networks with bandwidth of more than 10Gbps.
Spampot: A Spam Capture System Based on Distributed Honeypot
Guo Junquan, Zhuge Jianwei, Sun Donghong, and Duan Haixin
2014, 51(5):  1071-1080. 
Asbtract ( 774 )   HTML ( 0)   PDF (2336KB) ( 539 )  
Related Articles | Metrics
Spampot is a spam capturing system based on distributed low-interaction honeypot. Based on the previous research on SMTP, HTTP proxy and SOCKS protocols, we designed a spam honeypot system integrated with open relay and open proxy services and built the repositories of spammers’ attack behaviors, new spam samples, spammers’ IP and their geographic locations, the URLs blacklist from spam. We also discussed some of our considerations when designing the system, including improving the attractiveness for spammers, avoiding being blacklisted by anti-spam organization, and reducing the impact of the honeypot system on the real network. Our experimental deployment in CERNET for 6 months showed that Spampot could attract spammers effectively without being blacklisted by well-known anti-spam organization in the Internet. During the 6 months period, Spampot captured bulks of spam samples and spammers’ attack traffic. Our analysis show that these spammers are mainly from Taiwan, China and Brazil while their main targets are Taiwan (such as yahoo.com.tw and hinet.com). We have also discovered some new spammer behaviors and some new technologies that the spammer used to escape the filtering of anti-spam system. What’s more, through cluster analysis on the spam samples, we have identified some cases in which botnets are used for large-scale spam campaign.
Strong Key-Insulated Signature Scheme Supporting Multi-Helpers in the Standard Model
Ge Lirong, Yu Jia, Cheng Xiangguo, Hao Rong, Zhao Huiyan, and Li Meng
2014, 51(5):  1081-1088. 
Asbtract ( 314 )   HTML ( 0)   PDF (889KB) ( 460 )  
Related Articles | Metrics
Key-insulated signature is an important technique for protecting the signing secret keys. In key-insulated signature schemes, the security of the rest of the periods are unaffected even if a signing key of a time period is exposed. Parallel key-insulated signature schemes normally allow two helpers to help the signer update temporary private keys to strengthen the security. When two helper keys and any temporary private key are exposed simultaneously, the adversary can forge the correct signature of any time. In order to enhance the security of signature scheme, a new strong key-insulated signature scheme supporting n(n>2) helper devices is proposed. In the proposed scheme, if the user changes the frequency of updating temporary private keys to n times, the chance of exposing helper key still keeps the same as the original key-insulated system. As a result, it will not increase the chance of exposing the helper keys to insecure environment and will decrease the damage caused by key exposure. Finally, the scheme is proved secure based on the computation Diffie-Hellman assumption in the standard model.
An Efficient Rainbow Table Structure and Faster Cryptanalytic Time-Memory Trad-off Attack
Gu Chunxiang, Zhu Yuefei, Zheng Yonghui, and Li Zheng
2014, 51(5):  1089-1094. 
Asbtract ( 589 )   HTML ( 2)   PDF (836KB) ( 479 )  
Related Articles | Metrics
The time-memory trade-off algorithm is a method for quickly inverting a one-way function using pre-computed tables. Since its first introduction by Hellman, many variants and their analysis results have appeared. Oechslin suggested the so-called rainbow tables which made the method efficient and effective for cryptanalytic attacks. The Checkpoints method is a technique that reduces the number of table lookups performed by the algorithm. In this paper, we propose a new method using a novel design of pre-computed table structure. Compared with the rainbow method, the new design achieves distinct reduction in term of the storage requirement. We apply the method on the example of 8-character possible password composed from a character set of 95 different typeable characters. The number of records stored in the storage can increase with about 70% in our example compared with the rainbow method, which also leads to the increase of 7.8% to 15.6% (for different chain lengths) in terms of the success rate of attack if the storage requirement and the computational complexity remain the same. What’s more, our method can further use Checkpoints technique to reduce the complexity of on line computation with 15% to 20% by setting a checkpoint in the middle position of the chain.
Load Balancing Degree First Algorithm on Phase Space for Cloud Computing Cluster
Wang Peng, Huang Yan, Li Kun, and Guo Youming,
2014, 51(5):  1095-1107. 
Asbtract ( 624 )   HTML ( 3)   PDF (4615KB) ( 632 )  
Related Articles | Metrics
A load balancing degree first algorithm on phase space for cloud computing cluster is proposed. Cloud computing cluster is of tremendous nodes and is highly coupled. The cloud computing cluster server’s parameters are casted to the phase space, and the alteration of server’s status is converted into the movements of nodes on the phase space. Load balancing degree on phase space proposed in this paper is the key parameter to evaluate cloud computing cluster’s load balancing and scheduling algorithm’s performance. So the problem of task scheduling strategy can be converted into finding the way to make the least load balancing degree on phase space. This algorithm makes the cluster’s projection on phase space gather well. Load balancing degree on phase space, board sense temperature, board sense entropy are used in the simulation experiments. These broad sense thermodynamic parameters reflect the status of the cloud computing cluster. Four kinds of experiments are designed to verify the LBFA’s dynamic and static performance. The results show that this algorithm is superior to the least load first algorithm on most performance indexes, and the load balancing degree on phase space is more stable when cluster’s scale becomes larger.
User-Aware Resource Provision Policy for Cloud Computing
Zhou Jingcai, Zhang Huyin, Zha Wenliang, and Chen Yibo
2014, 51(5):  1108-1119. 
Asbtract ( 733 )   HTML ( 2)  
Related Articles | Metrics
Cloud computing has become a hot topic, and researchers have proposed various resource sharing techniques and resource provision techniques. However, few literatures pay attentions to the influence of behavior habits of user for resource provision policy. This paper proposes a behavior-based resource provision policy for cloud computing, and designs an algorithm BBTSA to analyze the user behavior data. Then, we can utilize probably theory to forecast the set of submitted task and expectation completing time of task at next time segment from the statistic results. After creating the policy table, system can dynamically adjust the resource provision policy according to the policy table and get the max VOC of unit resource. In order to evaluate the effect, we have done four-series experiments on HUTAF which is a cloud testing platform and developed by Huawei. The results indicate that the proposed resource provision policy is effective for improving the VOC and without increasing investment. The algorithm BBTSA is good for IaaS service companies to reduce investment.
Random Task-Oriented User Utility Optimization Model in the Cloud Environment
Tang Zhuo, Zhu Min, Yang Li, Tang Xiaoyong, and Li Kenli
2014, 51(5):  1120-1128. 
Asbtract ( 460 )   HTML ( 0)   PDF (2197KB) ( 515 )  
Related Articles | Metrics
Resource allocation methods and technology have always been a hot issue in the field of cloud computing. The existing solutions for resource allocation have not considered the actual requirement of the users so far. Through introducing the concept: utility, this paper proposes a description model for the user’s utility in the cloud environment, which quantifies the user’ satisfaction about the time and cost of the task in the cloud environment. Considering the randomness of the arrival time and the type of the tasks, this paper proposes an optimization model of task scheduling based on the theory of linear programming, using the basic concepts of user utility. This model takes the total utility value of the tasks completion as a goal, and takes the user tasks’ expected time, cost and parallel speed-up ratio as the constraint condition. It can describe the randomness of the user’s tasks, and choose the fittest resources which maximize the needs of every user while keeping the interests of other users. Finally, the simulation results verify the user utility optimization model of this paper.
A Splitting-Based Cloud Storage Mechanism for Digital Images
Lü Xiaobo, Guo Yao, and Chen Xiangqun
2014, 51(5):  1129-1135. 
Asbtract ( 494 )   HTML ( 0)   PDF (1822KB) ( 513 )  
Related Articles | Metrics
Due to the development of cloud computing and datacenters, the task of data processing and storage has migrated to the cloud platforms gradually. As a special kind of data, digital images contain a lot of private information, and require a huge amount of storage resources with frequent addition and deletion. Although storing digital images on cloud servers could solve some of these challenges, the quality of service provided by some of these servers is not reliable enough, especially when privacy issues are concerned. This paper proposes a splitting-based cloud storage mechanism for digital images. After splitting images into several blocks or layers and storing them into different cloud storage platforms, the privacy and reliability of these images can be enhanced. Two image splitting algorithms are proposed: block-based splitting and layer-based splitting. An image storage tool for privacy protection is implemented to demonstrate the mechanism. Experimental results show that the proposed techniques are able to provide privacy protection, at the same time enhancing the reliability and performance when storing digital images to the cloud. Performance under different cloud storage services, different splitting algorithms and different splitting granularities are also provided and analyzed. Finally, privacy-related issues and challenges are discussed.
A Fast Processing Algorithm on Section Disjoint Query of Data Stream
Wang Shaopeng, Wen Yingyou, Li Zhi, and Zhao Hong
2014, 51(5):  1136-1148. 
Asbtract ( 454 )   HTML ( 1)   PDF (2282KB) ( 368 )  
Related Articles | Metrics
Disjoint query has played a very important role in the research about similarity match over subsequence of data stream, such as sensor network, data mining and so on. But the existing research did not focus on the disjoint query which is executed for elements of data stream in the fixed-length section. Running Spring algorithm for all the elements in every section directly is the NAIVE algorithm. But this algorithm does not have the characteristic of incremental computation, so it has redundant operation. The boundary path technology is proposed in this paper to deal with this redundant operation. The NAIVE algorithm can get the disjoint query results of current section based on the ones of previous section and need not performing for every element in current section by using this technology, so it has the characteristic of incremental computation. The FSDQ algorithm, which has the characteristic of incremental computation, is proposed by improving NAIVE algorithm with the boundary path technology. Extensive experiments on real and synthetic data sets show that the FSDQ algorithm is an effective way to solve the problem of section disjoint query over data stream, and it can reduce redundant operations the NAIVE algorithm has and meet the requirements of practical application.
A Cyclic Memory Race Recording Algorithm Implemented with Hardware Signatures
Zhu Suxia, Ji Zhenzhou, Li Dong, and Zhang Hao
2014, 51(5):  1149-1157. 
Asbtract ( 436 )   HTML ( 0)   PDF (2261KB) ( 368 )  
Related Articles | Metrics
Shared-memory multithreaded programs running on chip multiprocessors tend to be nondeterministic. Two-phase deterministic record-replay is an effective approach to resolve this problem. Memory race recording is the key technology to replay multithreaded programs deterministically. It is significant to develop an efficient memory race recording scheme with both low log growth rate and rapid replay speed. A cyclic memory race recording algorithm based on point-to-point logging approach, named CyclicMR, is proposed. CyclicMR presents each memory race by using a new current dependency, uses hardware signatures with small size to detect memory races instead of cache memory, reduces the continuous memory races with same direction by a conflict direction detecting mechanism, and records an innovative cyclic dependency which can achieve much more transitivity. In this algorithm, all memory races recorded between two threads are loop-shaped, significantly reducing the redundancy of memory races. At the same time, cyclic dependency is further optimized by an incremental instruction counter, and the size of memory race is reduced a lot. Using an 8-core chip multiprocessor system, an exact comparison with earlier mainstream approaches is performed. The analysis results show that CyclicMR achieves small log growth rate, low hardware overhead and low bandwidth overhead. And it also has good scalability in memory race log.