2019 Vol. 56 No. 11
2019, 56(11): 2299-2314.
DOI: 10.7544/issn1000-1239.2019.20190341
Abstract：
Vulnerabilities are the core elements of system security and attack-defense confrontation. The automatic discovery, analysis and exploit of vulnerabilities has been a hot and difficult issue for a long time. The related researches mainly focus on fuzzing, propagate taint analysis and symbolic execution. On one hand, current solutions focus on different aspects of vulnerability discovery, analysis and exploit, which lack systematic researches and implementations. On the other hand, current solutions ignore the feasibility of limited resources under the realistic environment. Inside, the fuzzing is mainly based on large-scale server cluster system implementation, and the methods of propagate taint analysis and symbolic execution have high time and space complexity, which are prone to state explosion. Counter the problem of vulnerability automatic discovery and exploit under the limited resources, a program dynamic runtime Weak-Tainted model is established, then a complete solution for automatic vulnerability discovery, analysis and exploit is presented. The paper optimizes and enhances the ability of propagate taint analysis, and proposes a method for input solving based on output feature feedback, and any other analysis solutions under the limited resources to improve the ability and efficiency of vulnerability discovery, analysis and exploit. The paper designs and implements the vulnerability discovery and exploit automatic prototype system, which can concurrent 25 tasks for fuzzing, and propagate taint analysis and input solving with one server. The paper tests experiments on the samples of the 2018 BCTF competition, and the results show that the method of input solving in this paper is superior to ANGR for solving the atoi, hex and base64 encoding. The efficiency of vulnerability discovery is improved 45.7% higher than AFL, and 24 of the 50 samples can generate exploits automatically successfully. The advantages of Weak-Tainted vulnerability description model for vulnerability discovery and exploit are verified.
Vulnerabilities are the core elements of system security and attack-defense confrontation. The automatic discovery, analysis and exploit of vulnerabilities has been a hot and difficult issue for a long time. The related researches mainly focus on fuzzing, propagate taint analysis and symbolic execution. On one hand, current solutions focus on different aspects of vulnerability discovery, analysis and exploit, which lack systematic researches and implementations. On the other hand, current solutions ignore the feasibility of limited resources under the realistic environment. Inside, the fuzzing is mainly based on large-scale server cluster system implementation, and the methods of propagate taint analysis and symbolic execution have high time and space complexity, which are prone to state explosion. Counter the problem of vulnerability automatic discovery and exploit under the limited resources, a program dynamic runtime Weak-Tainted model is established, then a complete solution for automatic vulnerability discovery, analysis and exploit is presented. The paper optimizes and enhances the ability of propagate taint analysis, and proposes a method for input solving based on output feature feedback, and any other analysis solutions under the limited resources to improve the ability and efficiency of vulnerability discovery, analysis and exploit. The paper designs and implements the vulnerability discovery and exploit automatic prototype system, which can concurrent 25 tasks for fuzzing, and propagate taint analysis and input solving with one server. The paper tests experiments on the samples of the 2018 BCTF competition, and the results show that the method of input solving in this paper is superior to ANGR for solving the atoi, hex and base64 encoding. The efficiency of vulnerability discovery is improved 45.7% higher than AFL, and 24 of the 50 samples can generate exploits automatically successfully. The advantages of Weak-Tainted vulnerability description model for vulnerability discovery and exploit are verified.
Abstract：
Many security vulnerabilities are caused by the unsafe use of library programming interfaces. To protect applications from security attacks, library designers provide security tips to help developers use security-sensitive APIs correctly. However, developers often fail to follow security tips, which can introduce vulnerabilities to their programs. To evaluate the scale and impact of this problem, we conduct the first systematic, large-scale study on security tips and their violations in Android apps. Our study shows that existing security tips are less effective, due to their imprecise descriptions, misleading sample code, incorrect default settings, fragmentation (scattered across different sources), and lack of compliance check. As a result, the significant portion of Android apps we analyze are found to be vulnerable. To help the security guidance better followed by app developers, we propose TipTracer, a framework for verifying Android security tips automatically and efficiently. TipTracer contains a security property language that formally describes constraints expressed in security tips and a static code analyzer that checks whether applications satisfy security tips. We demonstrate the effectiveness, efficiency and usability of TipTracer using a large set of real-world apps.
Many security vulnerabilities are caused by the unsafe use of library programming interfaces. To protect applications from security attacks, library designers provide security tips to help developers use security-sensitive APIs correctly. However, developers often fail to follow security tips, which can introduce vulnerabilities to their programs. To evaluate the scale and impact of this problem, we conduct the first systematic, large-scale study on security tips and their violations in Android apps. Our study shows that existing security tips are less effective, due to their imprecise descriptions, misleading sample code, incorrect default settings, fragmentation (scattered across different sources), and lack of compliance check. As a result, the significant portion of Android apps we analyze are found to be vulnerable. To help the security guidance better followed by app developers, we propose TipTracer, a framework for verifying Android security tips automatically and efficiently. TipTracer contains a security property language that formally describes constraints expressed in security tips and a static code analyzer that checks whether applications satisfy security tips. We demonstrate the effectiveness, efficiency and usability of TipTracer using a large set of real-world apps.
Abstract：
Intrusion detection aims to effectively detect abnormal attacks in the network, which is critical for cyber security. Considering the problem that traditional intrusion detection methods are difficult to extract effective data features from industrial control system communication data, a intrusion detection model based on correlation information entropy and CNN-BiLSTM is proposed. It combines feature selection based on correlation information entropy with fused deep learning algorithms, and thus it can effectively remove noise redundancy, reduce computation and improve detection accuracy. Firstly, the corresponding pre-processing is carried out for the imbalanced samples, and the algorithm based on correlation information entropy is implied to select the features of the samples to achieve the purposes of removing noise data and redundant features. Then, convolutional neural network (CNN) and bidirectional long short-term memory (BiLSTM) network are applied respectively to extract data features from time and space dimensions, and realize feature fusion through multi-head attention mechanism to obtain the final test results. Finally, the optimal model is obtained by the single variable principle and cross-validation method. Compared with other traditional intrusion detection methods, the model has higher accuracy (99.21%) and lower false negative rate (0.77%).
Intrusion detection aims to effectively detect abnormal attacks in the network, which is critical for cyber security. Considering the problem that traditional intrusion detection methods are difficult to extract effective data features from industrial control system communication data, a intrusion detection model based on correlation information entropy and CNN-BiLSTM is proposed. It combines feature selection based on correlation information entropy with fused deep learning algorithms, and thus it can effectively remove noise redundancy, reduce computation and improve detection accuracy. Firstly, the corresponding pre-processing is carried out for the imbalanced samples, and the algorithm based on correlation information entropy is implied to select the features of the samples to achieve the purposes of removing noise data and redundant features. Then, convolutional neural network (CNN) and bidirectional long short-term memory (BiLSTM) network are applied respectively to extract data features from time and space dimensions, and realize feature fusion through multi-head attention mechanism to obtain the final test results. Finally, the optimal model is obtained by the single variable principle and cross-validation method. Compared with other traditional intrusion detection methods, the model has higher accuracy (99.21%) and lower false negative rate (0.77%).
2019, 56(11): 2339-2348.
DOI: 10.7544/issn1000-1239.2019.20190393
Abstract：
In the current complex network environment, malicious codes have been spread quickly in various ways, which illegally occupy user terminal equipment or network equipment and illegally steal privacy data. Malware poses a serious security threat to network and Internet users. Traditional methods can’t detect unknown malicious codes which is challenged by the diversity and large number of malicious code variants. We propose an unsupervised malware identification approach that generates a standardization rule of assembly instructions by analyzing the content of the decompiled PE files. By introducing latent Dirichlet allocation (LDA), our method extracts the latent “document-topic” and “topic-word” probability allocation from samples. The topic probability distributions are extracted as features of samples, which is a new way for malware feature presentation. Then, we propose a new malware detecting framework to train model and test malware. What’s more, our method solves the problem that the topic number in LDA model needs to be specified beforehand using the perplexity and different steps, which evaluates the best numbers of “topics” quickly and automatically. Finally, it analyzes the semantics of “document-topic” and “topic-word” aggregating results in assembly instructions, which explains the latent semantics of features obtained by our method. Experimental results show that our method is more discriminative, which has better classification results than other methods, while providing accurate discrimination of the new novel malware variants.
In the current complex network environment, malicious codes have been spread quickly in various ways, which illegally occupy user terminal equipment or network equipment and illegally steal privacy data. Malware poses a serious security threat to network and Internet users. Traditional methods can’t detect unknown malicious codes which is challenged by the diversity and large number of malicious code variants. We propose an unsupervised malware identification approach that generates a standardization rule of assembly instructions by analyzing the content of the decompiled PE files. By introducing latent Dirichlet allocation (LDA), our method extracts the latent “document-topic” and “topic-word” probability allocation from samples. The topic probability distributions are extracted as features of samples, which is a new way for malware feature presentation. Then, we propose a new malware detecting framework to train model and test malware. What’s more, our method solves the problem that the topic number in LDA model needs to be specified beforehand using the perplexity and different steps, which evaluates the best numbers of “topics” quickly and automatically. Finally, it analyzes the semantics of “document-topic” and “topic-word” aggregating results in assembly instructions, which explains the latent semantics of features obtained by our method. Experimental results show that our method is more discriminative, which has better classification results than other methods, while providing accurate discrimination of the new novel malware variants.
2019, 56(11): 2349-2364.
DOI: 10.7544/issn1000-1239.2019.20190412
Abstract：
As a typical application of Internet of things (IoT) technology, smart home platform is gradually entering thousands of households. However, the security issues of smart home platforms have hindered their further market expanding. The research on the security of smart home platforms is still at early stages, but many security threats have been proposed by researchers recently. In this paper, we review the typical the architectures of current popular smart home platforms, and analyze their attack interfaces on all components. In the area of information interface security, this paper analyzes the data steganography problems existing in the smart camera’s image interface, as well as the adversarial examples aiming at the voice control interface. In the aspect of cloud backend security, this paper analyses the security rulers’ breaches and the data leakage when running the smart applications. For these security problems, this paper reviews some existing solutions and their limitations. Furthermore, for smart home platform, this paper proposes a third-party malicious application detection system using wireless traffic analysis without any modification on the current platform. This paper introduces the design details of the proposed system, and demonstrates its effectiveness on the Samsung SmartThings platform, and proposes a privacy protection mechanism for this system.
As a typical application of Internet of things (IoT) technology, smart home platform is gradually entering thousands of households. However, the security issues of smart home platforms have hindered their further market expanding. The research on the security of smart home platforms is still at early stages, but many security threats have been proposed by researchers recently. In this paper, we review the typical the architectures of current popular smart home platforms, and analyze their attack interfaces on all components. In the area of information interface security, this paper analyzes the data steganography problems existing in the smart camera’s image interface, as well as the adversarial examples aiming at the voice control interface. In the aspect of cloud backend security, this paper analyses the security rulers’ breaches and the data leakage when running the smart applications. For these security problems, this paper reviews some existing solutions and their limitations. Furthermore, for smart home platform, this paper proposes a third-party malicious application detection system using wireless traffic analysis without any modification on the current platform. This paper introduces the design details of the proposed system, and demonstrates its effectiveness on the Samsung SmartThings platform, and proposes a privacy protection mechanism for this system.
2019, 56(11): 2365-2374.
DOI: 10.7544/issn1000-1239.2019.20190365
Abstract：
The intelligent environment built by machine learning, artificial intelligence, Internet of things is changing the way people live, work and think. The way of data storage and processing in intelligent environment is changing constantly, where security and efficiency are two important factors. In terms of security, privacy must be guaranteed during the sharing and analysis of data. In addition, many devices with limited resources exist in the intelligent environment, whose feasibility is directly influenced by how to design suitable algorithms or protocols. Based on the above two requirements, this paper studies the problem of secure pattern matching for intelligent environment. In the traditional secure pattern matching protocol, the pattern holder needs to compute lots of public-key operations，which is unsuitable for a resource-limited device such as a mobile phone. In this paper, we formalize the functionality of the secure pattern matching protocol under the two-cloud-assisted secure two-party computation model for the first time, and construct an efficient protocol via oblivious transfer (OT). The protocol is secure in semi-honest adversary model, assuming that no collusion exists between the cloud servers and the participants. The protocol requires 4 rounds, and the pattern holder performs only a small number of XOR operations, and the complex OT protocols are mainly executed between the database and the cloud servers. Furthermore, the OT extension technology can reduce the number of all OT protocols from O(nm) to O(k), where n and m are the input lengths of the two participants, and k is the number of base OT in OT extension protocol, which is much smaller than nm.
The intelligent environment built by machine learning, artificial intelligence, Internet of things is changing the way people live, work and think. The way of data storage and processing in intelligent environment is changing constantly, where security and efficiency are two important factors. In terms of security, privacy must be guaranteed during the sharing and analysis of data. In addition, many devices with limited resources exist in the intelligent environment, whose feasibility is directly influenced by how to design suitable algorithms or protocols. Based on the above two requirements, this paper studies the problem of secure pattern matching for intelligent environment. In the traditional secure pattern matching protocol, the pattern holder needs to compute lots of public-key operations，which is unsuitable for a resource-limited device such as a mobile phone. In this paper, we formalize the functionality of the secure pattern matching protocol under the two-cloud-assisted secure two-party computation model for the first time, and construct an efficient protocol via oblivious transfer (OT). The protocol is secure in semi-honest adversary model, assuming that no collusion exists between the cloud servers and the participants. The protocol requires 4 rounds, and the pattern holder performs only a small number of XOR operations, and the complex OT protocols are mainly executed between the database and the cloud servers. Furthermore, the OT extension technology can reduce the number of all OT protocols from O(nm) to O(k), where n and m are the input lengths of the two participants, and k is the number of base OT in OT extension protocol, which is much smaller than nm.
2019, 56(11): 2375-2383.
DOI: 10.7544/issn1000-1239.2019.20190293
Abstract：
The distributed biometric authentication system achieves high reliability, security and convenience without relying on weak passwords or hardware identifiers, but also faces more security threats due to the risk of permanent failure and privacy leakage of biometrics. The biometric authentication scheme based on homomorphic encryption technology allows feature vectors to be matched in the ciphertext domain to protect feature vector security and user privacy, but have to perform expensive multiplication operations in the ciphertext domain and it may also be compromised by improper vector encapsulation. In this paper, a secure vector matching method is proposed based on the BGV homomorphic encryption scheme, and a password-assisted biometric authentication protocol is designed based on this method. The protocol does not require hardware identifiers such as USB key, and registration only needs to store the auxiliary vector and the ciphertext of the sum of the biometric template vector and the auxiliary vector, authentication server using auxiliary vector matching method to evaluate the similarity of the template vector and the request vector can achieve user identity authentication. Based on Dolev-Yao attacker model and the multiple attacking methods of distributed biometric authentication system, the security analysis of the protocol is achieved, and the new protocol is proved to be more advantageous in privacy protection and vector matching efficiency by comparing and analyzing two other well-known RLWE-based biometric authentication protocols.
The distributed biometric authentication system achieves high reliability, security and convenience without relying on weak passwords or hardware identifiers, but also faces more security threats due to the risk of permanent failure and privacy leakage of biometrics. The biometric authentication scheme based on homomorphic encryption technology allows feature vectors to be matched in the ciphertext domain to protect feature vector security and user privacy, but have to perform expensive multiplication operations in the ciphertext domain and it may also be compromised by improper vector encapsulation. In this paper, a secure vector matching method is proposed based on the BGV homomorphic encryption scheme, and a password-assisted biometric authentication protocol is designed based on this method. The protocol does not require hardware identifiers such as USB key, and registration only needs to store the auxiliary vector and the ciphertext of the sum of the biometric template vector and the auxiliary vector, authentication server using auxiliary vector matching method to evaluate the similarity of the template vector and the request vector can achieve user identity authentication. Based on Dolev-Yao attacker model and the multiple attacking methods of distributed biometric authentication system, the security analysis of the protocol is achieved, and the new protocol is proved to be more advantageous in privacy protection and vector matching efficiency by comparing and analyzing two other well-known RLWE-based biometric authentication protocols.
2019, 56(11): 2384-2395.
DOI: 10.7544/issn1000-1239.2019.20180823
Abstract：
Aspect-based sentiment analysis has become one of the hottest research issues in the field of natural language processing. It identifies the aspect sentiment polarity of texts by learning from context information, which can effectively help people understand the sentiment expression on different aspects. Currently, the most models with combining attention mechanism and neural network only consider a single level of attention information. When solving aspect-based sentiment analysis tasks, theses models have a lot of limitations. The convolutional neural network cannot capture the global structural information. For the recurrent neural network, the training time-consuming is too long, and the degree of dependence between words gradually decreases as the distance increases. To solve the above problems, we propose the dual-attention networks for aspect-level sentiment analysis (DANSA) model. Firstly, by introducing the multi-head attention mechanism, the model performs multiple linear transformation on the input to obtain more comprehensive attention information, which can realize parallel computing and enhance the training speed. Secondly, the self-attention mechanism is introduced to obtain global structural information by calculating the attention scores between each word and all other words in the input, and the degree of dependence between words is not affected by time and sentence length. Finally, the model makes a prediction of aspects sentiment polarity by combining the context self-attention information and the aspect of the word attention information. The extensive experiments on the SemEval2014 datasets and the Twitter datasets show that the DANSA achieves better classification performance, which further demonstrates the validity of DANSA.
Aspect-based sentiment analysis has become one of the hottest research issues in the field of natural language processing. It identifies the aspect sentiment polarity of texts by learning from context information, which can effectively help people understand the sentiment expression on different aspects. Currently, the most models with combining attention mechanism and neural network only consider a single level of attention information. When solving aspect-based sentiment analysis tasks, theses models have a lot of limitations. The convolutional neural network cannot capture the global structural information. For the recurrent neural network, the training time-consuming is too long, and the degree of dependence between words gradually decreases as the distance increases. To solve the above problems, we propose the dual-attention networks for aspect-level sentiment analysis (DANSA) model. Firstly, by introducing the multi-head attention mechanism, the model performs multiple linear transformation on the input to obtain more comprehensive attention information, which can realize parallel computing and enhance the training speed. Secondly, the self-attention mechanism is introduced to obtain global structural information by calculating the attention scores between each word and all other words in the input, and the degree of dependence between words is not affected by time and sentence length. Finally, the model makes a prediction of aspects sentiment polarity by combining the context self-attention information and the aspect of the word attention information. The extensive experiments on the SemEval2014 datasets and the Twitter datasets show that the DANSA achieves better classification performance, which further demonstrates the validity of DANSA.
2019, 56(11): 2396-2409.
DOI: 10.7544/issn1000-1239.2019.20180880
Abstract：
By increasing the depth of neural network and the size of datasets, the deep neural networks are currently widely used for many artificial intelligence applications including computer vision, speech recognition and natural language processing. It can deliver the state of the art accuracy on these tasks. However, these operations will increase the overhead of training process in deep neural network algorithm. Stochastic gradient descent (SGD) has been used for accelerating the training of deep neural networks in a distributed computing environment. Nevertheless, parallel SGD can easily generate the problem of stale gradient, which affects the overall convergence. Most of the existing solutions are suit for high performance computing (HPC) environment where the performance of each node is similar. Few studies have researched cluster environment where the performance of each node is quite different. This paper proposes a variant of ASGD (asynchronous SGD) algorithm in which the batch size is modulated according to the runtime performance of each node. Experimental verification is performed on commonly-used image classification benchmarks: Mnist and cifar10 to demonstrate the effectiveness of the approach. Compared with ASGD and n-soft, the loss function of Mnist is reduced by 60% and the accuracy of the cifar10 is increased about 10% without reducing the speed-up.
By increasing the depth of neural network and the size of datasets, the deep neural networks are currently widely used for many artificial intelligence applications including computer vision, speech recognition and natural language processing. It can deliver the state of the art accuracy on these tasks. However, these operations will increase the overhead of training process in deep neural network algorithm. Stochastic gradient descent (SGD) has been used for accelerating the training of deep neural networks in a distributed computing environment. Nevertheless, parallel SGD can easily generate the problem of stale gradient, which affects the overall convergence. Most of the existing solutions are suit for high performance computing (HPC) environment where the performance of each node is similar. Few studies have researched cluster environment where the performance of each node is quite different. This paper proposes a variant of ASGD (asynchronous SGD) algorithm in which the batch size is modulated according to the runtime performance of each node. Experimental verification is performed on commonly-used image classification benchmarks: Mnist and cifar10 to demonstrate the effectiveness of the approach. Compared with ASGD and n-soft, the loss function of Mnist is reduced by 60% and the accuracy of the cifar10 is increased about 10% without reducing the speed-up.
2019, 56(11): 2410-2423.
DOI: 10.7544/issn1000-1239.2019.20180793
Abstract：
Spam filtering is an important issue in the information age. And, if an important email is wrongly classified, it would lead to an immeasurable cost. Thus, in the field of spam filtering, the ways to improve the accuracy and recall of the filters is the key issue. At present, the binary classification model in machine learning is usually used to deal with spam filtering. However, compared with the three-way decisions, the binary classification model usually leads to a higher cost of misclassification. And, as an important branch of three-way decisions, the three-way decisions with decision-theoretic rough sets can effectively reduce the misclassification cost and further improve the performance of filters. And, it also conforms to human cognition. Nevertheless, few studies consider the effect on classification results induced by the differences among equivalence classes when constructing the loss functions. Therefore, under the framework of the three-way decisions with decision-theoretic rough sets, an adaptive three-way spam filter with similarity measure is proposed. The model calculates the weights of condition attributes according to set variance firstly. Then, a comprehensive evaluation function for describing difference information among equivalence classes based on similarity measure of set is established. Finally, an adaptive model for calculating threshold pairs based on Bayesian decision rules is constructed. Experimental results show that the proposed model performs well in the field of spam filtering.
Spam filtering is an important issue in the information age. And, if an important email is wrongly classified, it would lead to an immeasurable cost. Thus, in the field of spam filtering, the ways to improve the accuracy and recall of the filters is the key issue. At present, the binary classification model in machine learning is usually used to deal with spam filtering. However, compared with the three-way decisions, the binary classification model usually leads to a higher cost of misclassification. And, as an important branch of three-way decisions, the three-way decisions with decision-theoretic rough sets can effectively reduce the misclassification cost and further improve the performance of filters. And, it also conforms to human cognition. Nevertheless, few studies consider the effect on classification results induced by the differences among equivalence classes when constructing the loss functions. Therefore, under the framework of the three-way decisions with decision-theoretic rough sets, an adaptive three-way spam filter with similarity measure is proposed. The model calculates the weights of condition attributes according to set variance firstly. Then, a comprehensive evaluation function for describing difference information among equivalence classes based on similarity measure of set is established. Finally, an adaptive model for calculating threshold pairs based on Bayesian decision rules is constructed. Experimental results show that the proposed model performs well in the field of spam filtering.
2019, 56(11): 2424-2437.
DOI: 10.7544/issn1000-1239.2019.20180740
Abstract：
The task of person re-identification is to associate individuals who have been observed over disjoint camera views.Due to its value in applications of video surveillance, person re-identification has drawn great attention from computer vision and machine learning communities.To address this problem, current literature mainly focuses on extracting discriminative features or learning distance metrics from pedestrian images.However, the representation power of learned features or metrics might be limited, because a person’s appearance usually undergoes large variations in different camera views, and many passers-by may take similar visual appearances in public spaces.In order to overcome these challenges and improve the person re-identification accuracies, we propose an effective re-identification method called cross-view discriminative dictionary learning with metric embedding.Different from traditional dictionary learning or metric learning approaches, the cross-view dictionary and distance metric are jointly learned in our model, thus their strengths can be combined. The proposed model not only captures the intrinsic relationships of representation coefficients, but also explores the distance constraints in different camera views. As a result, the re-identification can be performed with much more powerful representations in a discriminative subspace.To address the bias brought by unbalanced training samples in the metric learning phase, an automatic weighting strategy of training pairs is introduced.We devise an efficient optimization algorithm to solve the proposed model, in which the representation coefficients, dictionary, and metric are optimized alternately. Experimental results on three public benchmark datasets including VIPeR, GRID, and 3DPeS, show that the proposed method achieves remarkable performance compared with existing approaches as well as published results.
The task of person re-identification is to associate individuals who have been observed over disjoint camera views.Due to its value in applications of video surveillance, person re-identification has drawn great attention from computer vision and machine learning communities.To address this problem, current literature mainly focuses on extracting discriminative features or learning distance metrics from pedestrian images.However, the representation power of learned features or metrics might be limited, because a person’s appearance usually undergoes large variations in different camera views, and many passers-by may take similar visual appearances in public spaces.In order to overcome these challenges and improve the person re-identification accuracies, we propose an effective re-identification method called cross-view discriminative dictionary learning with metric embedding.Different from traditional dictionary learning or metric learning approaches, the cross-view dictionary and distance metric are jointly learned in our model, thus their strengths can be combined. The proposed model not only captures the intrinsic relationships of representation coefficients, but also explores the distance constraints in different camera views. As a result, the re-identification can be performed with much more powerful representations in a discriminative subspace.To address the bias brought by unbalanced training samples in the metric learning phase, an automatic weighting strategy of training pairs is introduced.We devise an efficient optimization algorithm to solve the proposed model, in which the representation coefficients, dictionary, and metric are optimized alternately. Experimental results on three public benchmark datasets including VIPeR, GRID, and 3DPeS, show that the proposed method achieves remarkable performance compared with existing approaches as well as published results.
Abstract：
Interval-valued hesitant fuzzy sets are generalizations of interval numbers and hesitant fuzzy sets, which are usually used to depict the incompleteness and hesitancy in uncertain information. In recent years, interval-valued hesitant fuzzy multi-attribute decision making problems have received extensive attentions of scholars. In allusion to interval-valued hesitant fuzzy multi-attribute decision making problems that are possessed with correlations and prioritization relationships between attributes at the same time, by taking advantages of fuzzy graphs could represent the correlations between attributes through edges between vertices, this paper studies multi-attribute decision making approaches based on interval-valued hesitant fuzzy graphs. Firstly, the related notion of interval-valued hesitant fuzzy graphs is established from the aspect of definitions, operation rules and mapping relationships. Based on the constructed notion, an approach to interval-valued hesitant fuzzy graphs in multi-attribute decision making with correlations and prioritization relationships is proposed. At last, a case study along with a comparative analysis is given to illustrate the feasibility and efficiency of the proposed multi-attribute decision making approach. Compared with classical interval-valued hesitant fuzzy multi-attribute decision making approaches, the results show that the proposed approach could reasonably solve interval-valued hesitant fuzzy multi-attribute decision making problems that are characterized by correlations and prioritization relationships between attributes at the same time.
Interval-valued hesitant fuzzy sets are generalizations of interval numbers and hesitant fuzzy sets, which are usually used to depict the incompleteness and hesitancy in uncertain information. In recent years, interval-valued hesitant fuzzy multi-attribute decision making problems have received extensive attentions of scholars. In allusion to interval-valued hesitant fuzzy multi-attribute decision making problems that are possessed with correlations and prioritization relationships between attributes at the same time, by taking advantages of fuzzy graphs could represent the correlations between attributes through edges between vertices, this paper studies multi-attribute decision making approaches based on interval-valued hesitant fuzzy graphs. Firstly, the related notion of interval-valued hesitant fuzzy graphs is established from the aspect of definitions, operation rules and mapping relationships. Based on the constructed notion, an approach to interval-valued hesitant fuzzy graphs in multi-attribute decision making with correlations and prioritization relationships is proposed. At last, a case study along with a comparative analysis is given to illustrate the feasibility and efficiency of the proposed multi-attribute decision making approach. Compared with classical interval-valued hesitant fuzzy multi-attribute decision making approaches, the results show that the proposed approach could reasonably solve interval-valued hesitant fuzzy multi-attribute decision making problems that are characterized by correlations and prioritization relationships between attributes at the same time.
2019, 56(11): 2448-2457.
DOI: 10.7544/issn1000-1239.2019.20180754
Abstract：
The purpose of automatic test pattern generation (ATPG) is to determine a high-quality set of test patterns for a particular fault model. Automatic test pattern generation is a very important part in chip testing. Through using the test set, generated by the automatic test pattern generation process, we can detect most of the faults in the circuit so that the fault coverage of the chip (design) can reach the desired value. Nowadays, there are many commercial tools available to generate the set of test patterns. Among these tools, TetraMAX ATPG 2018 is the most powerful and easy-to-use automatic test pattern generation tool. It can generate the highest quality test pattern set with the highest fault coverage in the shortest amount of time. In this paper, a method for computing minimal complete test pattern set based on the minimal hitting set method is proposed. By re-modeling the test pattern set reduction problem, the test set generated by TetraMAX ATPG 2018 is reduced with the method of computing minimal hitting set. This method can effectively reduce the scale of the test pattern set and ensure that the fault coverage of the test set does not change. It has important practical significance to reduce the test cost of the chip. In the experimental part of the paper, we use stuck-at fault as the fault model. The experimental results show that the proposed method can effectively reduce the size of the test set. At the same time, the method we proposed can guarantee that the obtained test pattern set does not contain redundant test pattern.
The purpose of automatic test pattern generation (ATPG) is to determine a high-quality set of test patterns for a particular fault model. Automatic test pattern generation is a very important part in chip testing. Through using the test set, generated by the automatic test pattern generation process, we can detect most of the faults in the circuit so that the fault coverage of the chip (design) can reach the desired value. Nowadays, there are many commercial tools available to generate the set of test patterns. Among these tools, TetraMAX ATPG 2018 is the most powerful and easy-to-use automatic test pattern generation tool. It can generate the highest quality test pattern set with the highest fault coverage in the shortest amount of time. In this paper, a method for computing minimal complete test pattern set based on the minimal hitting set method is proposed. By re-modeling the test pattern set reduction problem, the test set generated by TetraMAX ATPG 2018 is reduced with the method of computing minimal hitting set. This method can effectively reduce the scale of the test pattern set and ensure that the fault coverage of the test set does not change. It has important practical significance to reduce the test cost of the chip. In the experimental part of the paper, we use stuck-at fault as the fault model. The experimental results show that the proposed method can effectively reduce the size of the test set. At the same time, the method we proposed can guarantee that the obtained test pattern set does not contain redundant test pattern.
2019, 56(11): 2458-2468.
DOI: 10.7544/issn1000-1239.2019.20180617
Abstract：
The existing Gaussian-impulse mixed noise removal algorithms usually restore the noisy images via regularization technique by solving an optimal objective function iteratively, which results in low executive efficiency and limits their practical applications. To this end, in this paper we propose an image quality-aware fast blind denoising algorithm (IQA-FBDA), which takes convolutional neural network (CNN) as the core technique for the removal of Gaussian-impulse mixed noise. In the training phase, a shallow CNN-based image quality estimation model is first exploited to estimate the image quality of the image to be denoised. Then, according to the statistical distribution of the image qualities of a large number of noisy images, we construct a mixed noise pattern classification dictionary (MNPCD). Based on the MNPCD, the training noisy images are classified into 16 sub-classes, and then deep CNN-based denoisers for each class are trained. In the denoising phase, the image quality estimation model is first used to estimate the quality value of a given noisy image. After querying the quality value in the MNPCD, the corresponding pre-trained denoiser is exploited to achieve efficient blind image denoising. Experiments show that, compared with the state-of-the-art Gaussian-impulse mixed noise removal algorithms, the proposed one achieves comparable noise reduction effect with great improvement in terms of the execution efficiency, which makes it more practical.
The existing Gaussian-impulse mixed noise removal algorithms usually restore the noisy images via regularization technique by solving an optimal objective function iteratively, which results in low executive efficiency and limits their practical applications. To this end, in this paper we propose an image quality-aware fast blind denoising algorithm (IQA-FBDA), which takes convolutional neural network (CNN) as the core technique for the removal of Gaussian-impulse mixed noise. In the training phase, a shallow CNN-based image quality estimation model is first exploited to estimate the image quality of the image to be denoised. Then, according to the statistical distribution of the image qualities of a large number of noisy images, we construct a mixed noise pattern classification dictionary (MNPCD). Based on the MNPCD, the training noisy images are classified into 16 sub-classes, and then deep CNN-based denoisers for each class are trained. In the denoising phase, the image quality estimation model is first used to estimate the quality value of a given noisy image. After querying the quality value in the MNPCD, the corresponding pre-trained denoiser is exploited to achieve efficient blind image denoising. Experiments show that, compared with the state-of-the-art Gaussian-impulse mixed noise removal algorithms, the proposed one achieves comparable noise reduction effect with great improvement in terms of the execution efficiency, which makes it more practical.
2019, 56(11): 2469-2484.
DOI: 10.7544/issn1000-1239.2019.20180699
Abstract：
To reduce the computational complexity of traditional elastic motion estimation, this paper proposes a novel elastic motion estimation algorithm using two-bit-depth pixels. First, the Prewitt operator is employed to calculate the gradient of each video frame. The mean and standard deviation of the gradient norm is utilized to down-sample each pixels depth from 8 b into 2 b. Second, the bitwise operation-based matrix multiplication and the comparison based partial derivative computation are introduced. We subsequently describe an elastic motion model using two-bit-depth pixels, as well as a simplified Gaussian-Newton method which avoids the repetitive computation of the Hessian matrix and its inverse matrix. Meanwhile, we establish the functional relationship of the damping step size versus motion vector increment and motion-compensated errors by the first-order linear approximation, obtaining a method for approximately calculating the initial step size. Furthermore, we address a fast method for solving the elastic motion model with two-bit-depth pixels, using the diamond search algorithm as initial search. Experimental results illustrate that our algorithm obviously outperforms the full search with eight-bit-depth pixels, the full search with two-bit-depth pixels, as well as the conventional elastic motion estimation with eight-bit-depth pixels in terms of the peak signal-to-noise ratio (PSNR) and computational efficiency.
To reduce the computational complexity of traditional elastic motion estimation, this paper proposes a novel elastic motion estimation algorithm using two-bit-depth pixels. First, the Prewitt operator is employed to calculate the gradient of each video frame. The mean and standard deviation of the gradient norm is utilized to down-sample each pixels depth from 8 b into 2 b. Second, the bitwise operation-based matrix multiplication and the comparison based partial derivative computation are introduced. We subsequently describe an elastic motion model using two-bit-depth pixels, as well as a simplified Gaussian-Newton method which avoids the repetitive computation of the Hessian matrix and its inverse matrix. Meanwhile, we establish the functional relationship of the damping step size versus motion vector increment and motion-compensated errors by the first-order linear approximation, obtaining a method for approximately calculating the initial step size. Furthermore, we address a fast method for solving the elastic motion model with two-bit-depth pixels, using the diamond search algorithm as initial search. Experimental results illustrate that our algorithm obviously outperforms the full search with eight-bit-depth pixels, the full search with two-bit-depth pixels, as well as the conventional elastic motion estimation with eight-bit-depth pixels in terms of the peak signal-to-noise ratio (PSNR) and computational efficiency.
2019, 56(11): 2485-2493.
DOI: 10.7544/issn1000-1239.2019.20180656
Abstract：
Recent researches in neural network models have shown great potential in image inpainting task, which focuses on understanding image semantic information and reconstructs missing image content. These researches can generate visually reasonable image structures and textures, however, they usually produce distorted structures or blurry textures that are inconsistent with the surrounding areas, especially for the face inpainting task. The face inpainting task is often necessary to gene the advantages of fully connected convolution and U-net network, and the model proposes locally attributes discriminator to make the inpainted contents more innovative and is able to keep the global and local semantic consistency. The model not only improves the perception of the overall semantic information of the face image, but also restores the key parts of the face based on the local attributes. Experiments on the CelebA dataset have shown that our model can effectively deal with face image repair problems and generate novel results.
Recent researches in neural network models have shown great potential in image inpainting task, which focuses on understanding image semantic information and reconstructs missing image content. These researches can generate visually reasonable image structures and textures, however, they usually produce distorted structures or blurry textures that are inconsistent with the surrounding areas, especially for the face inpainting task. The face inpainting task is often necessary to gene the advantages of fully connected convolution and U-net network, and the model proposes locally attributes discriminator to make the inpainted contents more innovative and is able to keep the global and local semantic consistency. The model not only improves the perception of the overall semantic information of the face image, but also restores the key parts of the face based on the local attributes. Experiments on the CelebA dataset have shown that our model can effectively deal with face image repair problems and generate novel results.
2019, 56(11): 2494-2505.
DOI: 10.7544/issn1000-1239.2019.20180750
Abstract：
Opportunistic mobile social networks (OMSNs) are the network where mobile users utilize opportunistic contacts to transmit data by wireless peer-to-peer interaction. The growing share of using smart mobile devices offers the opportunity to build a ubiquitous infrastructure for data disseminations, so it is significant to study data transmissions in OMSNs. In order to improve the data dissemination performance of OMSNs, a data dissemination mechanism based on group structure (DDMGS) is proposed in this paper. Firstly, the relationship measurement model is designed based on the user’s behavior attributes that include the user’s movement trajectories, interests and communication behaviors. In addition, the group construction algorithm is designed for network topology composed of different behavior attribute relations. The topological structure based on location relationship has periodic stability. The topological structure based on interest relationship has long-term stability. The topological structure based on communication relationship has dynamicity. In order to improve the data dissemination performance and the overall network performance, a buffer management scheme is designed, and a cooperative game theory is introduced to strengthen the cooperation between nodes, to avoid the selfish behavior of the node. Simulation results show that, compared with the performance of direct delivery routing, prophetic routing, Simbet routing and Epidex routing, DDMGS has better performance in success rate of message transmission and the average hop count. It demonstrates that DDMGS is feasible and effective.
Opportunistic mobile social networks (OMSNs) are the network where mobile users utilize opportunistic contacts to transmit data by wireless peer-to-peer interaction. The growing share of using smart mobile devices offers the opportunity to build a ubiquitous infrastructure for data disseminations, so it is significant to study data transmissions in OMSNs. In order to improve the data dissemination performance of OMSNs, a data dissemination mechanism based on group structure (DDMGS) is proposed in this paper. Firstly, the relationship measurement model is designed based on the user’s behavior attributes that include the user’s movement trajectories, interests and communication behaviors. In addition, the group construction algorithm is designed for network topology composed of different behavior attribute relations. The topological structure based on location relationship has periodic stability. The topological structure based on interest relationship has long-term stability. The topological structure based on communication relationship has dynamicity. In order to improve the data dissemination performance and the overall network performance, a buffer management scheme is designed, and a cooperative game theory is introduced to strengthen the cooperation between nodes, to avoid the selfish behavior of the node. Simulation results show that, compared with the performance of direct delivery routing, prophetic routing, Simbet routing and Epidex routing, DDMGS has better performance in success rate of message transmission and the average hop count. It demonstrates that DDMGS is feasible and effective.
Abstract：
In recent years, community discovery in heterogeneous networks has gradually become a research hotspot. However, most of the existing methods for discovering non-overlapping or overlapping communities only take one single type of information network into account, and cannot be applied to heterogeneous networks containing multi-mode entities and their multi-dimensional relationships. Presently as a new emerging heterogeneous network, location based social network (LBSN) is attracting more and more attention from social network field. How to effectively discover the hidden complex community structures with multi-dimensional relationships in LBSN, is a very challenging problem for current researchers. Therefore, a community discovery method called multi-relational nonnegative matrix factorization (MRNMF) is proposed that integrates both user and location entities and fuse their multidimensional relationships in LBSN. This method establishes a joint clustering objective function based on nonnegative matrix factorization (NMF), and considers the effect of multi-dimensional factors such as user social relations, user-location check-ins and features of points of interests (POIs). The merits are that not only obtaining accurate user fuzzy communities, but also getting closely related clusters of POIs, which can effectively alleviate data sparse problem in recommendations. The experimental results on two real LBSN datasets show that the proposed method MRNMF has better recommendation performance than other traditional methods in the dual recommendations for POIs and users.
In recent years, community discovery in heterogeneous networks has gradually become a research hotspot. However, most of the existing methods for discovering non-overlapping or overlapping communities only take one single type of information network into account, and cannot be applied to heterogeneous networks containing multi-mode entities and their multi-dimensional relationships. Presently as a new emerging heterogeneous network, location based social network (LBSN) is attracting more and more attention from social network field. How to effectively discover the hidden complex community structures with multi-dimensional relationships in LBSN, is a very challenging problem for current researchers. Therefore, a community discovery method called multi-relational nonnegative matrix factorization (MRNMF) is proposed that integrates both user and location entities and fuse their multidimensional relationships in LBSN. This method establishes a joint clustering objective function based on nonnegative matrix factorization (NMF), and considers the effect of multi-dimensional factors such as user social relations, user-location check-ins and features of points of interests (POIs). The merits are that not only obtaining accurate user fuzzy communities, but also getting closely related clusters of POIs, which can effectively alleviate data sparse problem in recommendations. The experimental results on two real LBSN datasets show that the proposed method MRNMF has better recommendation performance than other traditional methods in the dual recommendations for POIs and users.
