2009 Vol. 46 No. 3
2009, 46(3): 353-362.
Abstract：
Security situational awareness has become a hot topic in the area of network security research in recent years, which attracts the interest of more and more domestic and foreign researchers. The existing security situational awareness methods are analyzed and compared in detail. Considering the characteristics of multi-source information in network security research, a new network security situational awareness model based on information fusion is proposed. This model fuses multi-source information from a mass of logs by introducing the modified D-S evidence theory, gets the values of nodes security situational awareness by situational factors fusion using attacks threat and vulnerability information which network nodes have and successful attacks depend on, computes the value of network security situational awareness by nodes situation fusion using service information of the network nodes, and draws the security-situation-graph of network. Then, it analyzes the time series of the computing results by ARMA model to forecast the future threat in network security. Finally an example of actual network datasets is given to validate the network security situational awareness model and algorithm. The results show that this model and algorithm is more effective and accurate than the existing security situational awareness methods.
Security situational awareness has become a hot topic in the area of network security research in recent years, which attracts the interest of more and more domestic and foreign researchers. The existing security situational awareness methods are analyzed and compared in detail. Considering the characteristics of multi-source information in network security research, a new network security situational awareness model based on information fusion is proposed. This model fuses multi-source information from a mass of logs by introducing the modified D-S evidence theory, gets the values of nodes security situational awareness by situational factors fusion using attacks threat and vulnerability information which network nodes have and successful attacks depend on, computes the value of network security situational awareness by nodes situation fusion using service information of the network nodes, and draws the security-situation-graph of network. Then, it analyzes the time series of the computing results by ARMA model to forecast the future threat in network security. Finally an example of actual network datasets is given to validate the network security situational awareness model and algorithm. The results show that this model and algorithm is more effective and accurate than the existing security situational awareness methods.
2009, 46(3): 363-369.
Abstract：
Mobile agents (MA) are autonomous software entities that are able to migrate across heterogeneous network execution environments. Mobility and autonomy compensate the deficiencies of distributed technology pretty well. Thus, mobile agents have wide application prospects. But security is an important issue for the widespread deployment of mobile agents applications. Especially the protection of mobile agents from attacks of malicious hosts is a unique security problem of mobile agent systems. It is difficult to solve this problem because agent is completely exposed in remote host and it is easy to be isolated and attacked by the malicious host. A protection scheme of mobile agents based on obfuscated agent data variables and time checking technology is presented in this paper. A method of how to obtain related data in time checking is given also. The idea of the time checking is based on limiting the execution time of the MA on the destination hosts. The original host checks three inequalities for the security of the hosts on the itinerary during the execution of the MA. If any of them is not satisfied, the hosts on both sides are suspicious. Through this time checking scheme, all the malicious hosts can be detected. The protection scheme is tested in actual network management environment, which can effectively identify the malicious host. The MA protection ratio reaches over 95%.
Mobile agents (MA) are autonomous software entities that are able to migrate across heterogeneous network execution environments. Mobility and autonomy compensate the deficiencies of distributed technology pretty well. Thus, mobile agents have wide application prospects. But security is an important issue for the widespread deployment of mobile agents applications. Especially the protection of mobile agents from attacks of malicious hosts is a unique security problem of mobile agent systems. It is difficult to solve this problem because agent is completely exposed in remote host and it is easy to be isolated and attacked by the malicious host. A protection scheme of mobile agents based on obfuscated agent data variables and time checking technology is presented in this paper. A method of how to obtain related data in time checking is given also. The idea of the time checking is based on limiting the execution time of the MA on the destination hosts. The original host checks three inequalities for the security of the hosts on the itinerary during the execution of the MA. If any of them is not satisfied, the hosts on both sides are suspicious. Through this time checking scheme, all the malicious hosts can be detected. The protection scheme is tested in actual network management environment, which can effectively identify the malicious host. The MA protection ratio reaches over 95%.
2009, 46(3): 370-376.
Abstract：
Any circuit implementation of a cryptographic system might cause power leakages to reveal more information about the processed secret. A new way is proposed to enhance power analysis attacks on AES circuit implementations. The proposed method adopts Hamming difference of intermediate results as power model and arranges plaintext inputs to maximize the difference of power traces in order to retrieve the key value. Using UMC 0.25μm 1.8v technology library and Synopsys EDA tools, a simulation-based power acquisition environment is set up. On the simulation-based platform, various power attacks are conducted on AES circuit implementation. As the partitioning criterions of single-bit and multi-bit differential power analysis (DPA) are usually abstract and simple, these two DPA methods can not retrieve any useful information even with 6000 power measurements. Although the correlation power analysis (CPA) attack can extract the right subkey based on 4000 power measurements, its computational complexity sometimes exhibits a bottle-neck. Experimental results show that the proposed method improves the success rate effectively using acceptable power measurements. Furthermore, the proposed DPA traces can be built through simple summing and subtracting operations instead of complex statistic techniques. Therefore, compared with the original DPA and CPA attacks, the presented DPA approach excels them in both effectiveness and computation requirements.
Any circuit implementation of a cryptographic system might cause power leakages to reveal more information about the processed secret. A new way is proposed to enhance power analysis attacks on AES circuit implementations. The proposed method adopts Hamming difference of intermediate results as power model and arranges plaintext inputs to maximize the difference of power traces in order to retrieve the key value. Using UMC 0.25μm 1.8v technology library and Synopsys EDA tools, a simulation-based power acquisition environment is set up. On the simulation-based platform, various power attacks are conducted on AES circuit implementation. As the partitioning criterions of single-bit and multi-bit differential power analysis (DPA) are usually abstract and simple, these two DPA methods can not retrieve any useful information even with 6000 power measurements. Although the correlation power analysis (CPA) attack can extract the right subkey based on 4000 power measurements, its computational complexity sometimes exhibits a bottle-neck. Experimental results show that the proposed method improves the success rate effectively using acceptable power measurements. Furthermore, the proposed DPA traces can be built through simple summing and subtracting operations instead of complex statistic techniques. Therefore, compared with the original DPA and CPA attacks, the presented DPA approach excels them in both effectiveness and computation requirements.
2009, 46(3): 377-383.
Abstract：
Akkar proposed a transformed masking based implementation of AES (Advanced Encryption Standard) to prevent against power analysis attack. However, this countermeasure is not truly secure against first order differential power analysis. A thorough analysis of vulnerabilities for Akkar’s implementation is performed in this paper. Several possible first order and second order differential power analysis attacks to the countermeasure proposed by Akkar for AES are shown. Based on Akkar’s implementation, an improved countermeasure for AES is proposed. The key of the presented method is to make each intermediate result being masked by various random values to eliminate the vulnerabilities to power analysis attacks in the implementation of AES. When the random values are mutual independent and uniformly distributed, the presented method is proved to be secure against DPA (differential power analysis) and HO-DPA (high-order DPA). In this improved countermeasure, a large amount of uniformly distributed random values are required to mask all the intermediate results. So an efficient mechanism to generate the large amount of random values is also proposed. An AES coprocessor based on the presented countermeasure is implemented. And the experiment result shows that the proposed implementation achieves the provable security against power analysis attack with some extra cost of hardware complexity in comparison with other typical countermeasures.
Akkar proposed a transformed masking based implementation of AES (Advanced Encryption Standard) to prevent against power analysis attack. However, this countermeasure is not truly secure against first order differential power analysis. A thorough analysis of vulnerabilities for Akkar’s implementation is performed in this paper. Several possible first order and second order differential power analysis attacks to the countermeasure proposed by Akkar for AES are shown. Based on Akkar’s implementation, an improved countermeasure for AES is proposed. The key of the presented method is to make each intermediate result being masked by various random values to eliminate the vulnerabilities to power analysis attacks in the implementation of AES. When the random values are mutual independent and uniformly distributed, the presented method is proved to be secure against DPA (differential power analysis) and HO-DPA (high-order DPA). In this improved countermeasure, a large amount of uniformly distributed random values are required to mask all the intermediate results. So an efficient mechanism to generate the large amount of random values is also proposed. An AES coprocessor based on the presented countermeasure is implemented. And the experiment result shows that the proposed implementation achieves the provable security against power analysis attack with some extra cost of hardware complexity in comparison with other typical countermeasures.
2009, 46(3): 384-389.
Abstract：
Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers. By traitor tracing schemes, at least one authorized user will be found from those who collude and share their decryption keys to unauthorized users. Based on bilinear map a new public-key traitor tracing scheme is presented in this paper. The main contribution of this scheme is that it concurrently satisfies the following features: 1) Both the number of keys stored by a user and the length of broadcasted block data are independent of the number of users. 2) Full collusion resistance: no users can construct a different valid decryption key from themselves by coalition. 3) Full revoke: any selected users can be revoked without renewing the others’ decryption keys. 4) Full recoverability: any revoked users can be recovered without renewing their decryption keys. Most importantly, compared with the existing schemes that satisfy the above properties, the translation overhead and storage overhead in the new scheme are independent of the total number of users. Finally, in the scheme presented any sets of users can be treated as authorized users. The security of this scheme is based on the difficult problems of solving discrete logarithm problem and decision Diffie-Hellman problem (DDH).
Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers. By traitor tracing schemes, at least one authorized user will be found from those who collude and share their decryption keys to unauthorized users. Based on bilinear map a new public-key traitor tracing scheme is presented in this paper. The main contribution of this scheme is that it concurrently satisfies the following features: 1) Both the number of keys stored by a user and the length of broadcasted block data are independent of the number of users. 2) Full collusion resistance: no users can construct a different valid decryption key from themselves by coalition. 3) Full revoke: any selected users can be revoked without renewing the others’ decryption keys. 4) Full recoverability: any revoked users can be recovered without renewing their decryption keys. Most importantly, compared with the existing schemes that satisfy the above properties, the translation overhead and storage overhead in the new scheme are independent of the total number of users. Finally, in the scheme presented any sets of users can be treated as authorized users. The security of this scheme is based on the difficult problems of solving discrete logarithm problem and decision Diffie-Hellman problem (DDH).
2009, 46(3): 390-397.
Abstract：
Complex event processing aggregates and combines information from sources into higher-level information or knowledge at the appropriate point through analyzing relationships among instances of various event types. Although composite events have been a useful modelling tool in active database research and network monitoring, little progress has been made in complex event porcessing middleware. The time model including temporal ordering of events is a crucial aspect for complex event processing. The semantics of operators for complex events is not defined in a uniform manner in existing middleware and applications, leading to the inconsistent results from the desired semantics and the detected complex event instances, and there is need to trade off time model against event detection efficiency. To address these issues, a consistent time model is defined in this paper for complex event in the service-oriented computing platform InforSIB. It includes solutions for time model of complex event, unsynchronized timestamp and out-of-order event arrivals. Basic operators provide the potential of expressing the required semantics and are capable of restricting expressions by parameters. Interval-based semantics for event detection is introduced, and extended, defining precisely complex timing constraints among complex event instances. The corresponding efficient complex event detection algorithm is presented too. And experiment results prove its effectivity.
Complex event processing aggregates and combines information from sources into higher-level information or knowledge at the appropriate point through analyzing relationships among instances of various event types. Although composite events have been a useful modelling tool in active database research and network monitoring, little progress has been made in complex event porcessing middleware. The time model including temporal ordering of events is a crucial aspect for complex event processing. The semantics of operators for complex events is not defined in a uniform manner in existing middleware and applications, leading to the inconsistent results from the desired semantics and the detected complex event instances, and there is need to trade off time model against event detection efficiency. To address these issues, a consistent time model is defined in this paper for complex event in the service-oriented computing platform InforSIB. It includes solutions for time model of complex event, unsynchronized timestamp and out-of-order event arrivals. Basic operators provide the potential of expressing the required semantics and are capable of restricting expressions by parameters. Interval-based semantics for event detection is introduced, and extended, defining precisely complex timing constraints among complex event instances. The corresponding efficient complex event detection algorithm is presented too. And experiment results prove its effectivity.
2009, 46(3): 398-406.
Abstract：
Monitoring is an absolutely necessary means to maintain the execution reliability of business process in the research on inter-organizational workflow management. Though some work has been done in this field, neither the conventional methods nor the current study on fault tolerance and exception handling in mobile-agent-based systems can effectively solve the problem in the multi-agent cooperatively concurrent process. The migrating workflow system just represents that kind of process. A migrating workflow is performed by several migrating instances, which generally are mobile and possess hierarchical relationship. Hence it becomes difficult to monitor a business flow and recover it from exceptions or faults. To solve the problem of process monitoring and cooperative recovery, a novel hierarchical collaborative monitoring model is presented based on the migrating workflow framework. The migrating instance and some relations between two migrating instances are described. Some constraints are discussed when recovered from faults. The mechanism can supervise migrating instances of different hierarchies by dispatching monitors with corresponding levels. Moreover, the cooperation mechanism among monitors can confine the incidence when facing exceptions. As shown in the analysis and experiment results, the model can implement concurrent monitoring and hierarchical exception dealing. Additionally, it can avoid the inefficiency of single point bottleneck and enhance the reliability of workflow execution.
Monitoring is an absolutely necessary means to maintain the execution reliability of business process in the research on inter-organizational workflow management. Though some work has been done in this field, neither the conventional methods nor the current study on fault tolerance and exception handling in mobile-agent-based systems can effectively solve the problem in the multi-agent cooperatively concurrent process. The migrating workflow system just represents that kind of process. A migrating workflow is performed by several migrating instances, which generally are mobile and possess hierarchical relationship. Hence it becomes difficult to monitor a business flow and recover it from exceptions or faults. To solve the problem of process monitoring and cooperative recovery, a novel hierarchical collaborative monitoring model is presented based on the migrating workflow framework. The migrating instance and some relations between two migrating instances are described. Some constraints are discussed when recovered from faults. The mechanism can supervise migrating instances of different hierarchies by dispatching monitors with corresponding levels. Moreover, the cooperation mechanism among monitors can confine the incidence when facing exceptions. As shown in the analysis and experiment results, the model can implement concurrent monitoring and hierarchical exception dealing. Additionally, it can avoid the inefficiency of single point bottleneck and enhance the reliability of workflow execution.
2009, 46(3): 407-414.
Abstract：
Accurate traffic classification is the keystone of numerous network activities, so it has been a hot topic in network measurement for a long time. In recent years, Internet traffic classification using machine learning has been a new direction in this area. Nave Bayes and its improved methods have been widely used in this area, because they are simple and efficient. However, these methods depend on the probability distribution of sample space, so they have connatural instability. In order to handle this problem, a new method based on support vector machine (SVM) is proposed in this paper. This method converts the Internet traffic classification problem to a quadratic optimization problem using non-linear transformation and structural risk minimization, which performs good accuracy and stability. After the theoretical analysis, the comparison experiments with Nave Bayes and its improved methods on traffic sets are given. The experiment results validate that support vector machine method has three advantages in Internet traffic classification: Firstly, it is not necessary for flow attributes to satisfy the independence hypothesis, so feature selection is not required. Secondly, this method can work well with poor priori knowledge. Lastly, this method doesn’t use the probability distribution of sample space, so it can classify Internet traffic stably.
Accurate traffic classification is the keystone of numerous network activities, so it has been a hot topic in network measurement for a long time. In recent years, Internet traffic classification using machine learning has been a new direction in this area. Nave Bayes and its improved methods have been widely used in this area, because they are simple and efficient. However, these methods depend on the probability distribution of sample space, so they have connatural instability. In order to handle this problem, a new method based on support vector machine (SVM) is proposed in this paper. This method converts the Internet traffic classification problem to a quadratic optimization problem using non-linear transformation and structural risk minimization, which performs good accuracy and stability. After the theoretical analysis, the comparison experiments with Nave Bayes and its improved methods on traffic sets are given. The experiment results validate that support vector machine method has three advantages in Internet traffic classification: Firstly, it is not necessary for flow attributes to satisfy the independence hypothesis, so feature selection is not required. Secondly, this method can work well with poor priori knowledge. Lastly, this method doesn’t use the probability distribution of sample space, so it can classify Internet traffic stably.
2009, 46(3): 415-424.
Abstract：
It is commonly believed that extending structured peer to peer overlays to be capacity-aware will increase maintenance overhead, so it is significant to build a capacity aware protocol that is effective and has low maintenance overhead. Presented in this paper is an effective capacity-aware structured peer to peer protocol—HeteroChord. HeteroChord does not use the traditional method of nodes exchanging routing information to implement capacity awareness, it implements the capacity aware mechanism in a new node’s joining algorithm and updating algorithm. Compared with traditional capacity aware protocols, when a new node joins the system, HeteroChord can calculate the nodes whose routing table should be updated, so the capacity aware mechanism is efficient. The simulation results indicate that the maintenance overhead of HeteroChord is less than that of Chord under churn. Then a non-DHT structured file sharing model called NHFS is constructed based on HeteroChord. In NHFS, The supernodes are connected by super leaf sets, and the file indices are replicated to supernodes, so the queries can be processed simply in supernodes. Super leaf set makes it easy for the queries to traverse the supernodes in NHFS, and the maintenance overhead generated by unidirectional replication mechanism in NHFS is much lower than that generated by bidirectional replication mechanism in HeteroPastry. So the file sharing model NHFS is more reasonable than HeteroPastry.
It is commonly believed that extending structured peer to peer overlays to be capacity-aware will increase maintenance overhead, so it is significant to build a capacity aware protocol that is effective and has low maintenance overhead. Presented in this paper is an effective capacity-aware structured peer to peer protocol—HeteroChord. HeteroChord does not use the traditional method of nodes exchanging routing information to implement capacity awareness, it implements the capacity aware mechanism in a new node’s joining algorithm and updating algorithm. Compared with traditional capacity aware protocols, when a new node joins the system, HeteroChord can calculate the nodes whose routing table should be updated, so the capacity aware mechanism is efficient. The simulation results indicate that the maintenance overhead of HeteroChord is less than that of Chord under churn. Then a non-DHT structured file sharing model called NHFS is constructed based on HeteroChord. In NHFS, The supernodes are connected by super leaf sets, and the file indices are replicated to supernodes, so the queries can be processed simply in supernodes. Super leaf set makes it easy for the queries to traverse the supernodes in NHFS, and the maintenance overhead generated by unidirectional replication mechanism in NHFS is much lower than that generated by bidirectional replication mechanism in HeteroPastry. So the file sharing model NHFS is more reasonable than HeteroPastry.
2009, 46(3): 425-433.
Abstract：
Positioning is a fundamental issue for sensor network operation. Knowledge of accurate node location is essential in such network deployment. Many papers in this field focus on anchor-based solutions. The use of anchors introduces many limitations, since anchors require external equipments such as GPS, and that causes additional power consumption. Eliminating the requirement of anchors in this paper, a competent anchor-free algorithm is presented for distributed localization in sensor networks. Previous localization algorithms assume that there exist some anchor nodes, and then other nodes are estimated to create their coordinates. Once there are not anchors to be deployed, those localization techniques will be invalidated. The novel algorithm is proposed to create some virtual anchors and a virtual coordinate system, which is executed in a distributed fashion with a measured distance between two adjacent nodes. The neighbor information is adopted, and the intermediate estimations of nodes are measured for position mutation according to their reliability criterions. Thus the positioning optimization process of the whole network is avoided falling into a local optimal solution. Simulation results prove that the algorithm can reliably resolve the anchor-free localization problem. It is superior to previously proposed methods in terms of its ability to compute correct coordinates and the global-energy-ratio objective under a variety of conditions.
Positioning is a fundamental issue for sensor network operation. Knowledge of accurate node location is essential in such network deployment. Many papers in this field focus on anchor-based solutions. The use of anchors introduces many limitations, since anchors require external equipments such as GPS, and that causes additional power consumption. Eliminating the requirement of anchors in this paper, a competent anchor-free algorithm is presented for distributed localization in sensor networks. Previous localization algorithms assume that there exist some anchor nodes, and then other nodes are estimated to create their coordinates. Once there are not anchors to be deployed, those localization techniques will be invalidated. The novel algorithm is proposed to create some virtual anchors and a virtual coordinate system, which is executed in a distributed fashion with a measured distance between two adjacent nodes. The neighbor information is adopted, and the intermediate estimations of nodes are measured for position mutation according to their reliability criterions. Thus the positioning optimization process of the whole network is avoided falling into a local optimal solution. Simulation results prove that the algorithm can reliably resolve the anchor-free localization problem. It is superior to previously proposed methods in terms of its ability to compute correct coordinates and the global-energy-ratio objective under a variety of conditions.
2009, 46(3): 434.
Abstract：
Complexity and diversity of Internet traffic are constantly growing. Networking researchers become aware of the need to constantly monitor and reevaluate their assumptions in order to ensure that the conceptual models correctly represent reality. Internet traffic today is a complex nonlinear combination of the seasonal time series. The current network traffic measurement research is mainly concentrated on the flow forecasts and analysis based on network layer or transport layer. However, a single ARMA (n, n-1) model is used, which can only describe the overall network traffic trends, while different traffics based on the application layer aren’t always consistent with ARMA (n, n-1) model. Presented in this paper are traffic prediction models based on application layer, which use ARIMA seasonal multiple model (p, d, q)(P, D, Q)s for modeling and forecasting the seasonal time series from China’s exports of a metro area network link. Experimental results show that different application layer traffics perform different traffic behavior characteristics, and with the establishment of different application-layer flow prediction models, forecasting trends are very similar with the actual flow curves, and mean absolute percentage errors are around 10%. The authors firstly presents ARIMA seasonal multiple model as traffic prediction models based on application layer.
Complexity and diversity of Internet traffic are constantly growing. Networking researchers become aware of the need to constantly monitor and reevaluate their assumptions in order to ensure that the conceptual models correctly represent reality. Internet traffic today is a complex nonlinear combination of the seasonal time series. The current network traffic measurement research is mainly concentrated on the flow forecasts and analysis based on network layer or transport layer. However, a single ARMA (n, n-1) model is used, which can only describe the overall network traffic trends, while different traffics based on the application layer aren’t always consistent with ARMA (n, n-1) model. Presented in this paper are traffic prediction models based on application layer, which use ARIMA seasonal multiple model (p, d, q)(P, D, Q)s for modeling and forecasting the seasonal time series from China’s exports of a metro area network link. Experimental results show that different application layer traffics perform different traffic behavior characteristics, and with the establishment of different application-layer flow prediction models, forecasting trends are very similar with the actual flow curves, and mean absolute percentage errors are around 10%. The authors firstly presents ARIMA seasonal multiple model as traffic prediction models based on application layer.
2009, 46(3): 443-451.
Abstract：
Ontology realization poses as the major hindrance to the evolution of World Wide Web into semantic Web. The manual construction of ontology demands large amount of labor as well as lasts for long durations. Ontology learning technology makes it possible for the automatic building of ontology in texts and greatly accelerates the speed of construction; yet, the technology is constrained by its lack of generality and accuracy. Based on the object-oriented analytical methods, a formal spatial description on ontology learning data source is performed. The authors revise the classical descriptive method for texts, that is, the object-oriented single vector space model (VSM) and propose a double vector space model (D-VSM), specifically, verbal layer and noun layer. This model is characterized by the inclusion of diverse attributes and solid relations. To further cope with information redundancy associated with FCA method and to improve the accuracy of concept abstraction, the fuzzy formal concept analysis (FFCA) ontology learning technology is introduced, which can fully explore the distributed property of data in DVSM and specialize in solving issues like ontology continuity, ontology relations obtainment, etc. An ontology learning tool is created based on DV-FFCA methodology, which provides powerful support for automatic (semi-automatic) ontology construction.
Ontology realization poses as the major hindrance to the evolution of World Wide Web into semantic Web. The manual construction of ontology demands large amount of labor as well as lasts for long durations. Ontology learning technology makes it possible for the automatic building of ontology in texts and greatly accelerates the speed of construction; yet, the technology is constrained by its lack of generality and accuracy. Based on the object-oriented analytical methods, a formal spatial description on ontology learning data source is performed. The authors revise the classical descriptive method for texts, that is, the object-oriented single vector space model (VSM) and propose a double vector space model (D-VSM), specifically, verbal layer and noun layer. This model is characterized by the inclusion of diverse attributes and solid relations. To further cope with information redundancy associated with FCA method and to improve the accuracy of concept abstraction, the fuzzy formal concept analysis (FFCA) ontology learning technology is introduced, which can fully explore the distributed property of data in DVSM and specialize in solving issues like ontology continuity, ontology relations obtainment, etc. An ontology learning tool is created based on DV-FFCA methodology, which provides powerful support for automatic (semi-automatic) ontology construction.
2009, 46(3): 452-458.
Abstract：
Description logic is the logical foundation of the semantic Web. It is a tool for formally expressing domain knowledge. Description logic is the decidable fragment of the first order logic and suitable for modeling the concept terminology of domain knowledge. Because some application requirements and people can not describe all of the domain knowledge, there is lots of incomplete knowledge on the Web. Description logic is based on the open world assumption. It can only express the monotonic reasoning and can not solve the incomplete knowledge. By adding the epistemic operator “K” to the description logic, the epistemic description logic can be obtained. It has the advantage of dealing with the incomplete knowledge because of the non-monotonic features and the good computational complexity. The authors present a new epistemic description logic ALCKR\-+ based on the epistemic description logic ALCK, preserve the primary advantage of the description logic, add transitive roles for improving the expressivity, express the non-monotonic reasoning ability through the epistemic query, and design the syntax and semantic of ALCKR\-+. The corresponding tableau algorithm is also provided. The soundness and decidability of the tableau algorithm are proved. It is shown that the complexity of tableau algorithm is PSPACE-complete.
Description logic is the logical foundation of the semantic Web. It is a tool for formally expressing domain knowledge. Description logic is the decidable fragment of the first order logic and suitable for modeling the concept terminology of domain knowledge. Because some application requirements and people can not describe all of the domain knowledge, there is lots of incomplete knowledge on the Web. Description logic is based on the open world assumption. It can only express the monotonic reasoning and can not solve the incomplete knowledge. By adding the epistemic operator “K” to the description logic, the epistemic description logic can be obtained. It has the advantage of dealing with the incomplete knowledge because of the non-monotonic features and the good computational complexity. The authors present a new epistemic description logic ALCKR\-+ based on the epistemic description logic ALCK, preserve the primary advantage of the description logic, add transitive roles for improving the expressivity, express the non-monotonic reasoning ability through the epistemic query, and design the syntax and semantic of ALCKR\-+. The corresponding tableau algorithm is also provided. The soundness and decidability of the tableau algorithm are proved. It is shown that the complexity of tableau algorithm is PSPACE-complete.
2009, 46(3): 459-469.
Abstract：
Methods based on extension rule are new approaches for automated theorem proving and can efficiently solve problems with high complementary factor. In this paper, a new strategy to re-implement ER, which is an algorithm based on the propositional extension rule, is proposed. The new implementation of ER is superior to the original one. Based on this, the extension rule is applied in the following three areas: Firstly, there exist a set of analogous SAT problems being solved in real applications. In contrast with solving these SAT problems separately, an algorithm called nER that solves them as a whole is developed. The algorithm nER exploits the repetition property of ER and generally costs less time than the total time of using ER to solve every problem. Furthermore, based on ER, two new algorithms called #ER and #CDE are proposed, the latter being a combination of #ER and #DPLL. Experimental results show that #ER outperforms #DPLL on a wide range of problems and the #CDE integrates advantages of #ER and #DPLL. Finally, an ER based SAT solver is embedded into the conformant fast-forward to study the potential of ER based methods in artificial intelligence planning. Preliminary results show the efficiency of ER and future research topics.
Methods based on extension rule are new approaches for automated theorem proving and can efficiently solve problems with high complementary factor. In this paper, a new strategy to re-implement ER, which is an algorithm based on the propositional extension rule, is proposed. The new implementation of ER is superior to the original one. Based on this, the extension rule is applied in the following three areas: Firstly, there exist a set of analogous SAT problems being solved in real applications. In contrast with solving these SAT problems separately, an algorithm called nER that solves them as a whole is developed. The algorithm nER exploits the repetition property of ER and generally costs less time than the total time of using ER to solve every problem. Furthermore, based on ER, two new algorithms called #ER and #CDE are proposed, the latter being a combination of #ER and #DPLL. Experimental results show that #ER outperforms #DPLL on a wide range of problems and the #CDE integrates advantages of #ER and #DPLL. Finally, an ER based SAT solver is embedded into the conformant fast-forward to study the potential of ER based methods in artificial intelligence planning. Preliminary results show the efficiency of ER and future research topics.
2009, 46(3): 470-477.
Abstract：
Given a fuzzy information system, several important fuzzy attribute subsets can be found and each of them can have different contributions to decision-making. If only one of the fuzzy attribute subsets, which may be the most important one, is selected to induce decision rules, some useful information hidden in other important subsets for the decision-making will be lost unavoidably. To sufficiently make use of the information provided by every individual important fuzzy attribute subset in a fuzzy information system, a novel integration of multiple fuzzy decision trees is proposed. The method consists of three stages. First, several important fuzzy attribute subsets are found by fuzzy equivalent relation, and then a fuzzy decision tree for each important fuzzy attribute subset is generated using fuzzy ID3. The fuzzy integral is finally used as a fusion tool to integrate the generated decision trees, which combines together all outputs of the multiple fuzzy decision trees and forms the final decision result. An illustration is given to show the proposed fusion scheme. A numerical experiment on real data indicates that the proposed multiple tree induction is superior to the single tree induction based on the individual important fuzzy attribute subset.
Given a fuzzy information system, several important fuzzy attribute subsets can be found and each of them can have different contributions to decision-making. If only one of the fuzzy attribute subsets, which may be the most important one, is selected to induce decision rules, some useful information hidden in other important subsets for the decision-making will be lost unavoidably. To sufficiently make use of the information provided by every individual important fuzzy attribute subset in a fuzzy information system, a novel integration of multiple fuzzy decision trees is proposed. The method consists of three stages. First, several important fuzzy attribute subsets are found by fuzzy equivalent relation, and then a fuzzy decision tree for each important fuzzy attribute subset is generated using fuzzy ID3. The fuzzy integral is finally used as a fusion tool to integrate the generated decision trees, which combines together all outputs of the multiple fuzzy decision trees and forms the final decision result. An illustration is given to show the proposed fusion scheme. A numerical experiment on real data indicates that the proposed multiple tree induction is superior to the single tree induction based on the individual important fuzzy attribute subset.
2009, 46(3): 478-484.
Abstract：
To recognize images under various view-angle in noised background is one of the most important and challenging problems that need be resolved. An approach using affine invariant features in frequency domain for object recognition in low signal noise ratio (SNR) images is presented. The relationship of affine transforms between spatial domain and frequency domain is analyzed. That is, the effect of affine transformation on the spectrum is almost the same as the affine transform on the object in spatial domain except for two major differences: Firstly, the spectrum is inversely scaled and slanted; Secondly, shape translations parallel to the image plane do not affect the spectrum. In the preprocessing procedure, noise is reduced by convoluting the input image with a low-pass filter. Then the spectral signatures at low-to-median frequency are extracted using pseudo-log sampling, which is useful to reduce the influences of both view-point and illumination variation and to further suppress high frequency noises. A neural network is trained with these features to extract affine invariant features and to recognize objects at different poses. Comparing the proposed method with other two Gabor-based methods, experimental results show that more than 90% images can be recognized correctly even when SNR drops bellow -20dB and this approach is much better than the Gabor-based methods in low SNR images.
To recognize images under various view-angle in noised background is one of the most important and challenging problems that need be resolved. An approach using affine invariant features in frequency domain for object recognition in low signal noise ratio (SNR) images is presented. The relationship of affine transforms between spatial domain and frequency domain is analyzed. That is, the effect of affine transformation on the spectrum is almost the same as the affine transform on the object in spatial domain except for two major differences: Firstly, the spectrum is inversely scaled and slanted; Secondly, shape translations parallel to the image plane do not affect the spectrum. In the preprocessing procedure, noise is reduced by convoluting the input image with a low-pass filter. Then the spectral signatures at low-to-median frequency are extracted using pseudo-log sampling, which is useful to reduce the influences of both view-point and illumination variation and to further suppress high frequency noises. A neural network is trained with these features to extract affine invariant features and to recognize objects at different poses. Comparing the proposed method with other two Gabor-based methods, experimental results show that more than 90% images can be recognized correctly even when SNR drops bellow -20dB and this approach is much better than the Gabor-based methods in low SNR images.
2009, 46(3): 485-491.
Abstract：
Speculation is an important method to overcome control flow constraints during instruction scheduling. On the one hand, speculation can exploit more instruction-level parallelism and improve performance. However, on the other hand, it may also lengthen the live range of variables and increase the register pressure, which in turn results in spilling some variables to memory and deteriorating the performance. Previous work on register pressure sensitive instruction scheduling generally scheduled instructions conservatively when there were too many live variables in the scheduling region. But actually different variables have different spilling costs and different impacts on performance. Here a register pressure sensitive speculative instruction scheduling technology is presented, which not only considers the count of live variables, but also analyzes the benefits and the spilling costs brought by instructions’ speculative motions. The decrement of cycles in critical path is calculated as benefit, while the spilled variables are predicted and their spilling cost is used as cost. Only the speculative motion with benefit greater than the cost is permitted in our method. This algorithm has been implemented in Godson Compiler for MIPS architecture. Experiment result shows that the method in this paper can obtain 1.44％ speedup on average relative to its register pressure insensitive counterpart on SPEC CPU2000INT benchmarks.
Speculation is an important method to overcome control flow constraints during instruction scheduling. On the one hand, speculation can exploit more instruction-level parallelism and improve performance. However, on the other hand, it may also lengthen the live range of variables and increase the register pressure, which in turn results in spilling some variables to memory and deteriorating the performance. Previous work on register pressure sensitive instruction scheduling generally scheduled instructions conservatively when there were too many live variables in the scheduling region. But actually different variables have different spilling costs and different impacts on performance. Here a register pressure sensitive speculative instruction scheduling technology is presented, which not only considers the count of live variables, but also analyzes the benefits and the spilling costs brought by instructions’ speculative motions. The decrement of cycles in critical path is calculated as benefit, while the spilled variables are predicted and their spilling cost is used as cost. Only the speculative motion with benefit greater than the cost is permitted in our method. This algorithm has been implemented in Godson Compiler for MIPS architecture. Experiment result shows that the method in this paper can obtain 1.44％ speedup on average relative to its register pressure insensitive counterpart on SPEC CPU2000INT benchmarks.
2009, 46(3): 492-497.
Abstract：
Data mapping is a critical problem in large scale storage systems. Besides high performance and scalability, excellent data mapping algorithm should also provide minimum amount of data migration for keeping balance under dynamic storage environment. Proposed in this paper is a decentralized mapping algorithm for replicated data in large scale storage system. By adopting storage node weighting and consistent hash mechanism, this algorithm could distribute mass storage objects among tens or hundreds of thousands storage devices according to their serving abilities. When the number of storage devices changes, the amount of data migration for data rebalance nearly reaches theoretical lower band. By maintaining only little amount of information, front applications could calculate the location of every data object without consulting the conventional centralized data object mapping table, which greatly improves system scalability. At the same time, the complexity of the data mapping process is quite low. Testing results show that the deviation of the allocated data objects quantity for each storage device from the theoretical value is less than 5%. Testing results also show that the deviation of migrated data objects quantity needed for data rebalance from the theoretical lower band is less than 1%.
Data mapping is a critical problem in large scale storage systems. Besides high performance and scalability, excellent data mapping algorithm should also provide minimum amount of data migration for keeping balance under dynamic storage environment. Proposed in this paper is a decentralized mapping algorithm for replicated data in large scale storage system. By adopting storage node weighting and consistent hash mechanism, this algorithm could distribute mass storage objects among tens or hundreds of thousands storage devices according to their serving abilities. When the number of storage devices changes, the amount of data migration for data rebalance nearly reaches theoretical lower band. By maintaining only little amount of information, front applications could calculate the location of every data object without consulting the conventional centralized data object mapping table, which greatly improves system scalability. At the same time, the complexity of the data mapping process is quite low. Testing results show that the deviation of the allocated data objects quantity for each storage device from the theoretical value is less than 5%. Testing results also show that the deviation of migrated data objects quantity needed for data rebalance from the theoretical lower band is less than 1%.
2009, 46(3): 498-504.
Abstract：
Privacy preserving micro-data publishing is a hot issue in data privacy preserving research. Data perturbation is one of those methods to solve this problem, which does some revision to primitive data values at the cost of little mining accuracy loss. The key is the balance between privacy preserving and mining accuracy, which contradict each other to some extent. Concerning the problem of privacy preserving clustering, a novel privacy preserving data perturbation algorithm NETPA is proposed. The potential relation between data object and it’s neighborhood is analyzed. Referring the idea of entropy in information theory, the definitions of neighborhood entropy of attribute and neighboring main attribute are proposed. The primitive data set can be perturbed by changing each data object’s values of neighboring main attributes with corresponding attribute average value of those data objects in its k nearest neighborhood. Theoretical analysis testifies that this perturbation strategy can maintain the stability of k nearest neighboring relations in primitive data well, meanwhile it can avoid privacy leakage effectively. Experimental analysis is designed by adopting clustering algorithm DBCSAN and k-LDCHD on primitive datasets and perturbed ones by NETPA. Experimental results on both realistic and synthetic datasets prove that NETPA can preserve the privacy of primitive data effectively and maintain the clustering model of primitive data well.
Privacy preserving micro-data publishing is a hot issue in data privacy preserving research. Data perturbation is one of those methods to solve this problem, which does some revision to primitive data values at the cost of little mining accuracy loss. The key is the balance between privacy preserving and mining accuracy, which contradict each other to some extent. Concerning the problem of privacy preserving clustering, a novel privacy preserving data perturbation algorithm NETPA is proposed. The potential relation between data object and it’s neighborhood is analyzed. Referring the idea of entropy in information theory, the definitions of neighborhood entropy of attribute and neighboring main attribute are proposed. The primitive data set can be perturbed by changing each data object’s values of neighboring main attributes with corresponding attribute average value of those data objects in its k nearest neighborhood. Theoretical analysis testifies that this perturbation strategy can maintain the stability of k nearest neighboring relations in primitive data well, meanwhile it can avoid privacy leakage effectively. Experimental analysis is designed by adopting clustering algorithm DBCSAN and k-LDCHD on primitive datasets and perturbed ones by NETPA. Experimental results on both realistic and synthetic datasets prove that NETPA can preserve the privacy of primitive data effectively and maintain the clustering model of primitive data well.
2009, 46(3): 505-512.
Abstract：
Given a set of small rectangular pieces of different sizes and a rectangular container of fixed width and infinite length, the rectangular strip packing problem (RSPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the packing is minimized. RSPP belongs to NP-hard problem in theory and has many industrial applications such as the composition of news, the cutting of clothing and the cutting of metal, etc. To solve the rectangular strip packing problem, a hybrid algorithm, which combines a novel heuristic algorithm—dynamic-fit heuristic algorithm (DFHA), with the genetic algorithm, is adopted. The DFHA algorithm can dynamically select the better-fit rectangle for packing, according to the width-fit first (WFF) rule, the height-fit first (HFF) rule, the placeable first (PF) rule, and the biggest-rectangle first (BRF) rule, and the evolutionary capability of genetic algorithm is used to optimize the height of the packing which is calculated by DFHA. The hybrid algorithm is tested on two sets of benchmark problems taken from the previous literature. The first set includes 21 instances and the other one includes 13 instances. The computational results show that the hybrid algorithm is more effective than the existing algorithms from the previous literature.
Given a set of small rectangular pieces of different sizes and a rectangular container of fixed width and infinite length, the rectangular strip packing problem (RSPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the packing is minimized. RSPP belongs to NP-hard problem in theory and has many industrial applications such as the composition of news, the cutting of clothing and the cutting of metal, etc. To solve the rectangular strip packing problem, a hybrid algorithm, which combines a novel heuristic algorithm—dynamic-fit heuristic algorithm (DFHA), with the genetic algorithm, is adopted. The DFHA algorithm can dynamically select the better-fit rectangle for packing, according to the width-fit first (WFF) rule, the height-fit first (HFF) rule, the placeable first (PF) rule, and the biggest-rectangle first (BRF) rule, and the evolutionary capability of genetic algorithm is used to optimize the height of the packing which is calculated by DFHA. The hybrid algorithm is tested on two sets of benchmark problems taken from the previous literature. The first set includes 21 instances and the other one includes 13 instances. The computational results show that the hybrid algorithm is more effective than the existing algorithms from the previous literature.
2009, 46(3): 513-520.
Abstract：
As the size and functional complexity of IC designs increase, it has become important to address verification issues at early stages of the IC design flow. This means that IC designers require automated verification tools at higher levels of abstraction. Because of this, formal verification methods, such as equivalence verification, have become important for register transfer level or behavioral level verification. However, most of the existing techniques for equivalence verification are based on BDD or Boolean SAT, which are generally geared towards verification of designs implemented at lower levels of abstraction, such as gate level and circuitlayout level, and can hardly satisfy the high-level verification requirements. So in this paper, a new algorithm for the equivalence verification of high-level datapaths based on polynomial symbolic algebra is proposed. After researching further the method to describe behaviors of complex datapaths using polynomial expressions, the general form of the polynomial set representations for high-level datapaths is obtained. The functional equivalence of high-level datapaths is then defined from the perspective of common zeros of polynomial sets, and an efficient algebraic solution based on Grbner basis computation is presented. Experimental results on a variety of public benchmark suites show the efficiency of the proposed approach.
As the size and functional complexity of IC designs increase, it has become important to address verification issues at early stages of the IC design flow. This means that IC designers require automated verification tools at higher levels of abstraction. Because of this, formal verification methods, such as equivalence verification, have become important for register transfer level or behavioral level verification. However, most of the existing techniques for equivalence verification are based on BDD or Boolean SAT, which are generally geared towards verification of designs implemented at lower levels of abstraction, such as gate level and circuitlayout level, and can hardly satisfy the high-level verification requirements. So in this paper, a new algorithm for the equivalence verification of high-level datapaths based on polynomial symbolic algebra is proposed. After researching further the method to describe behaviors of complex datapaths using polynomial expressions, the general form of the polynomial set representations for high-level datapaths is obtained. The functional equivalence of high-level datapaths is then defined from the perspective of common zeros of polynomial sets, and an efficient algebraic solution based on Grbner basis computation is presented. Experimental results on a variety of public benchmark suites show the efficiency of the proposed approach.
Abstract：
It is always difficult to ascertain the number of clusters for image segmentation, while in this paper, the problem is solved well by using a method based on the measurement of difference of mutual information. The difference of mutual information describes the increase of mutual information in both original and segmented image when the number of segments is increasing. Being a measure of ascertaining the number of segments, it is considered getting the balance between the number of segments and the mutual information of segmented images. According to it, a rule of determining the number of segments is put forward. For the segmentation algorithm, Gauss-Markov random field model is often used, which takes advantage of both image intensity and spatial information imposed by Gibbs priori probability. The model can be used to effectively segment the noised images. However it is always difficult to confirm the Gibbs penalty factor β. As usual, it requires a tedious trial-and-error process. So to solve this problem, a class-adaptive penalty factor β is defined. It is automatically estimated from the posteriori probability and is anisotropic for each class. Furthermore, the model iteratively gets their parameters estimation in the EM-MAP algorithm. Finally, by the application of this algorithm in medical image segmentation, it is proved effective.
It is always difficult to ascertain the number of clusters for image segmentation, while in this paper, the problem is solved well by using a method based on the measurement of difference of mutual information. The difference of mutual information describes the increase of mutual information in both original and segmented image when the number of segments is increasing. Being a measure of ascertaining the number of segments, it is considered getting the balance between the number of segments and the mutual information of segmented images. According to it, a rule of determining the number of segments is put forward. For the segmentation algorithm, Gauss-Markov random field model is often used, which takes advantage of both image intensity and spatial information imposed by Gibbs priori probability. The model can be used to effectively segment the noised images. However it is always difficult to confirm the Gibbs penalty factor β. As usual, it requires a tedious trial-and-error process. So to solve this problem, a class-adaptive penalty factor β is defined. It is automatically estimated from the posteriori probability and is anisotropic for each class. Furthermore, the model iteratively gets their parameters estimation in the EM-MAP algorithm. Finally, by the application of this algorithm in medical image segmentation, it is proved effective.
