Volume 16,Issue 7,2005 Table of Contents
2005, 16(7):1197-1204.
Abstract:
Description of the pairs of rough sets is an important aspect in the research of rough set theory by algebraic method. By defining some basic operators on the approximation pairs, rough algebras can be constructed. Then some general algebras can be selected to describe the pairs of rough sets. The most famous rough algebras are Rough Double Stone Algebra, Rough Nelson Algebra and Approximation Space Algebra, and their corresponding general algebra structures are regular double Stone algebra, semi-simple Nelson algebra and pre-rough algebra respectively. This paper establishes the relations between the operators of these rough algebras and proves that: (a) approximation space algebra can be made into semi-simple Nelson algebra or regular double Stone algebra; (b) rough Nelson algebra can be made into pre-rough algebra or regular double Stone algebra; (c) rough double Stone algebra can be made into pre-rough algebra or semi-simple Nelson algebra. Thus, a uniform structure for the famous works from three different aspects is built and the relations among them are established.
Description of the pairs
2005, 16(7):1205-1209.
Abstract:
The following three conclusions are found: (1) By regular order-sorted theory morphism being deduced to many-sorted theory morphism, both model functors ( )·and ( )# being commutative with φ have been proved; (2) Lawvere theorem in Institution of regular order-sorted equational logic is presented; (3) The correspondence among initial (terminal) semantics of glued theories and factor theories in Institution of regular order-sorted equational logic is clarified.
The following three conclusions are found: (1) By regular order-sorted theory morphism being deduced to many-sorted theory morphism, both model functors ( )·and ( )# being commutative with φ have been proved; (2) Lawvere theorem in Institution of regular order-sorted equational logic is presented; (3) The correspondence among initial (terminal) semantics of glued theories and factor theories in Institution of regular order-sorted equational logic is clarified.
2005, 16(7):1210-1220.
Abstract:
This paper presents an integrated metamorphic testing environment MTest and reports an experimental analysis of the effectiveness of metamorphic testing, which is carried out using MTest with a real program of sparse matrix multiplication. Quantitative evaluation and comparison of special case testing, metamorphic testing with special and random test cases are illustrated with two measurements: mutation score and fault detection ratio. The case study shows that metamorphic testing and special case testing are complementary to each other, and with respect to source test case for metamorphic testing, random test cases are preferred to special test cases.
This paper presents an integrated metamorphic testing environment MTest and reports an experimental analysis of the effectiveness of metamorphic testing, which is carried out using MTest with a real program of sparse matrix multiplication. Quantitative evaluation and comparison of special case testing, metamorphic testing with special and random test cases are illustrated with two measurements: mutation score and fault detection ratio. The case study shows that metamorphic testing and special case testing are complementary to each other, and with respect to source test case for metamorphic testing, random test cases are preferred to special test cases.
2005, 16(7):1221-1231.
Abstract:
Analyzing and handling the inconsistency in requirements is critical to the development of complex software systems. How to solve this problem directly influences the quality of requirements specification, as well as the final software production. Based on a common-recognized management framework of requirements inconsistency, this paper summarizes representative researches on this topic. The main aim is to get a comprehensive understanding of the current techniques and methods of inconsistency management. Finally, the paper also identifies some issues which are still open to further research.
Analyzing and handling the inconsistency in requirements is critical to the development of complex software systems. How to solve this problem directly influences the quality of requirements specification, as well as the final software production. Based on a common-recognized management framework of requirements inconsistency, this paper summarizes representative researches on this topic. The main aim is to get a comprehensive understanding of the current techniques and methods of inconsistency management. Finally, the paper also identifies some issues which are still open to further research.
2005, 16(7):1232-1241.
Abstract:
Features denote the extensions of the basic function set of the communication software, while Feature Interactions (FIs) mean the unexpected interference between the features. The paper studies the FIs in the next generation communication software mainly on the aspect of the distributed implementation and deployment of the features. Based on the Communication Finite State Machine (CFSM) model, the authors design an FI detection method using the system verification technique. For the state explosion problem during verification, an optimization scheme is presented to reduce the complexity. Its validity is proved in theory and illustrated by examples.
Features denote the extensions of the basic function set of the communication software, while Feature Interactions (FIs) mean the unexpected interference between the features. The paper studies the FIs in the next generation communication software mainly on the aspect of the distributed implementation and deployment of the features. Based on the Communication Finite State Machine (CFSM) model, the authors design an FI detection method using the system verification technique. For the state explosion problem during verification, an optimization scheme is presented to reduce the complexity. Its validity is proved in theory and illustrated by examples.
2005, 16(7):1242-1251.
Abstract:
Verification is meaningful for ensuring the correctness of workflow process definition. This paper focuses on semantic verification method, solving the problem of conflict checking under the combination of control flow, data flow and resource dimensions of workflow processes. Firstly, a formal model for process description— 3DWFN is defined responding to the requirement of semantic verification, and then reduction rules accomplishing semantic verification are stated in details based on 3DWFN nets. Finally, their advantages on semantic verification layer are compared with the existing reduction rules in the literatures.
Verification is meaningful for ensuring the correctness of workflow process definition. This paper focuses on semantic verification method, solving the problem of conflict checking under the combination of control flow, data flow and resource dimensions of workflow processes. Firstly, a formal model for process description— 3DWFN is defined responding to the requirement of semantic verification, and then reduction rules accomplishing semantic verification are stated in details based on 3DWFN nets. Finally, their advantages on semantic verification layer are compared with the existing reduction rules in the literatures.
2005, 16(7):1252-1261.
Abstract:
It is very important in a lot of applications to forecast future trend of data streams. For example, using predictive queries to a sensor network for monitoring environment, observers can forecast future average temperature and humidity in the area covered by the network to determine abnormal events. Recent works on query processing over data streams mainly focused on approximate queries over newly arriving data. To the best of the knowledge, there is nothing to date in the literature on predictive query processing over data streams. Adopting multivariable linear regression, a predictive mathematical model for forecasting the aggregate value over data streams is first proposed. Then, based on the model, a predictive aggregate query processing method over data streams is proposed in the paper. When the frequency of forecast failing is greater than a predefined threshold, an adaptive strategy for the predictive mathematical model is proposed. A mathematical model that characterizes the affects of the updating cycle of sliding window and data stream rate on predictive accuracy is also presented.Analytical and experimental results show that the proposed method is very effective, and the proposed algorithms have higher performance and provide better prediction of aggregate values over data streams to users. In experiments the TPC-H data and ocean air temperature data measured by TAO (tropical atmosphere ocean) are used to construct data streams.
It is very important in a lot of applications to forecast future trend of data streams. For example, using predictive queries to a sensor network for monitoring environment, observers can forecast future average temperature and humidity in the area covered by the network to determine abnormal events. Recent works on query processing over data streams mainly focused on approximate queries over newly arriving data. To the best of the knowledge, there is nothing to date in the literature on predictive query processing over data streams. Adopting multivariable linear regression, a predictive mathematical model for forecasting the aggregate value over data streams is first proposed. Then, based on the model, a predictive aggregate query processing method over data streams is proposed in the paper. When the frequency of forecast failing is greater than a predefined threshold, an adaptive strategy for the predictive mathematical model is proposed. A mathematical model that characterizes the affects of the updating cycle of sliding window and data stream rate on predictive accuracy is also presented.Analytical and experimental results show that the proposed method is very effective, and the proposed algorithms have higher performance and provide better prediction of aggregate values over data streams to users. In experiments the TPC-H data and ocean air temperature data measured by TAO (tropical atmosphere ocean) are used to construct data streams.
2005, 16(7):1262-1269.
Abstract:
Algorithm FDMSP (fast distributed mining of sequential patterns) is proposed in order to deal with mining sequential patterns in distributed environment and its properties are analyzed. The algorithm utilizes prefix-projected technique to divide the pattern searching space, utilizes polling site associated with prefix to get a global support, and utilizes local pruning, poll pruning and count pruning to decrease candidate sequences. It is divided into three sub-procedures which run asynchronously. As a result, the algorithm has lower I/O cost, memory cost and communication cost, and global sequential patterns are generated with higher efficiency. The experiments show that it outperforms the algorithm GSP after centralizing data by 68.5% to 99.5% and scaleable over LAN with huge amount of data.
Algorithm FDMSP (fast distributed mining of sequential patterns) is proposed in order to deal with mining sequential patterns in distributed environment and its properties are analyzed. The algorithm utilizes prefix-projected technique to divide the pattern searching space, utilizes polling site associated with prefix to get a global support, and utilizes local pruning, poll pruning and count pruning to decrease candidate sequences. It is divided into three sub-procedures which run asynchronously. As a result, the algorithm has lower I/O cost, memory cost and communication cost, and global sequential patterns are generated with higher efficiency. The experiments show that it outperforms the algorithm GSP after centralizing data by 68.5% to 99.5% and scaleable over LAN with huge amount of data.
2005, 16(7):1270-1281.
Abstract:
Traditionally, SQL is the main interface to access data from relational databases. However, it is difficult for inexperienced end users to learn the complicated syntax of SQL. Enabling keyword-based information retrieval over relational databases will allow users to acquire information from databases without any knowledge of SQL and the underlying database schema, just like the way of common search engines. This paper describes the design and implementation of SEEKER, a system supporting keyword-based information retrieval over relational databases. While there have been some existing systems that support searching text attributes in relational databases, SEEKER can also search database metadata and numeric attributes. Moreover, SEEKER employs an improved ranking function and supports Top-k queries. Experimental results show that SEEKER can achieve good retrieval performance.
Traditionally, SQL is the main interface to access data from relational databases. However, it is difficult for inexperienced end users to learn the complicated syntax of SQL. Enabling keyword-based information retrieval over relational databases will allow users to acquire information from databases without any knowledge of SQL and the underlying database schema, just like the way of common search engines. This paper describes the design and implementation of SEEKER, a system supporting keyword-based information retrieval over relational databases. While there have been some existing systems that support searching text attributes in relational databases, SEEKER can also search database metadata and numeric attributes. Moreover, SEEKER employs an improved ranking function and supports Top-k queries. Experimental results show that SEEKER can achieve good retrieval performance.
2005, 16(7):1282-1288.
Abstract:
Slice is one of the major operations in on-line analysis processing, which has played an important role in the application of decision support. In this paper, a method of mining exceptional slices is presented for extracting the distribution feature of the slice data based on the technique of the singular value decomposition, and the exceptional slices can be found by utilizing the distance-based outlier detection technique on the singular value feature. The effectiveness of the approach is experimentally demonstrated on the artificial data and the real slices data.
Slice is one of the major operations in on-line analysis processing, which has played an important role in the application of decision support. In this paper, a method of mining exceptional slices is presented for extracting the distribution feature of the slice data based on the technique of the singular value decomposition, and the exceptional slices can be found by utilizing the distance-based outlier detection technique on the singular value feature. The effectiveness of the approach is experimentally demonstrated on the artificial data and the real slices data.
2005, 16(7):1289-1295.
Abstract:
Feng Deng-Guo suggested a problem so called “threshold group-signature scheme with privilege subsets”. This paper analyzes the security of such schemes at present and propose new schemes. Based on theory of finite fields, the authors firstly show there are some insufficiencies and potential hazard in the scheme proposed by Shi, et al. Secondly, using the idea of constructing group-signature scheme by individual signature scheme, a group of the ones with four variants of type of ElGamal are put fordward, which have some attractive properties, such as message recovery, shorter length of signature, etc. Finally, the security of the schemes is proved under the assumption that the respective individual signature schemes are secure.
Feng Deng-Guo suggested a problem so called “threshold group-signature scheme with privilege subsets”. This paper analyzes the security of such schemes at present and propose new schemes. Based on theory of finite fields, the authors firstly show there are some insufficiencies and potential hazard in the scheme proposed by Shi, et al. Secondly, using the idea of constructing group-signature scheme by individual signature scheme, a group of the ones with four variants of type of ElGamal are put fordward, which have some attractive properties, such as message recovery, shorter length of signature, etc. Finally, the security of the schemes is proved under the assumption that the respective individual signature schemes are secure.
2005, 16(7):1296-1304.
Abstract:
In this paper, the performance of integrating real-time and non real-time traffic in the PCF (point coordination function) mode of IEEE 802.11 is studied, and a novel real-time traffic admission control algorithm is proposed. By changing the admission threshold dynamically according to the current load of non real-time traffic and polling the admitted real-time nodes according to their service index, the proposed algorithm can provide parameterized QoS (quality of service) for real-time traffic, while at the same time, keep the throughput of non real-time traffic at an acceptable level. The validity of the admission control algorithm is verified by simulation.
In this paper, the performance of integrating real-time and non real-time traffic in the PCF (point coordination function) mode of IEEE 802.11 is studied, and a novel real-time traffic admission control algorithm is proposed. By changing the admission threshold dynamically according to the current load of non real-time traffic and polling the admitted real-time nodes according to their service index, the proposed algorithm can provide parameterized QoS (quality of service) for real-time traffic, while at the same time, keep the throughput of non real-time traffic at an acceptable level. The validity of the admission control algorithm is verified by simulation.
2005, 16(7):1305-1313.
Abstract:
Mobile IP is a simple and scalable global mobility solution. This paper numerically analyzes the characterization of handoff for Mobile IP: the probability distribution about packet loss and packet disorder. By using the result, the radius of overlap region is optimized. The illustrations show that the model precisely reflects the handoff behavior. The probability is very helpful to evaluate the handoff performance.
Mobile IP is a simple and scalable global mobility solution. This paper numerically analyzes the characterization of handoff for Mobile IP: the probability distribution about packet loss and packet disorder. By using the result, the radius of overlap region is optimized. The illustrations show that the model precisely reflects the handoff behavior. The probability is very helpful to evaluate the handoff performance.
2005, 16(7):1314-1322.
Abstract:
A distributed dynamic micro-mobility management scheme is proposed to make up the deficiency of not supporting well for highly Mobile Host (MH) in Mobile IP. The scheme places a few of Regional Mobility Agents (RMA) to distributedly manage hosts’ mobility in region. An algorithm is presented for MH to decide its RMA and regional size in terms of its mobility characteristics and some informed network parameters, which results in minimum signaling cost and packet delivery cost, but does not impose any restrictions on network’s topology and RMAs’ locations. Analysis shows when MH’s average packet arrival rate increases, the regional size decreases while the total cost increases; when MH’s average residence time in Access Router increases, both the regional size and total cost decrease. Finally, a performance comparison demonstrates that the total costs produced in Hierarchical Mobile IPv6 with several distinct regional sizes are all higher than the possible highest total cost produced in the scheme.
A distributed dynamic micro-mobility management scheme is proposed to make up the deficiency of not supporting well for highly Mobile Host (MH) in Mobile IP. The scheme places a few of Regional Mobility Agents (RMA) to distributedly manage hosts’ mobility in region. An algorithm is presented for MH to decide its RMA and regional size in terms of its mobility characteristics and some informed network parameters, which results in minimum signaling cost and packet delivery cost, but does not impose any restrictions on network’s topology and RMAs’ locations. Analysis shows when MH’s average packet arrival rate increases, the regional size decreases while the total cost increases; when MH’s average residence time in Access Router increases, both the regional size and total cost decrease. Finally, a performance comparison demonstrates that the total costs produced in Hierarchical Mobile IPv6 with several distinct regional sizes are all higher than the possible highest total cost produced in the scheme.
2005, 16(7):1323-1332.
Abstract:
Robustness is an important issue in the development of multi-bits watermarking algorithm. A new algorithm for robust multi-bits image watermarking based on Hidden Markov Model (HMM) in wavelet domain is proposed. The algorithm is characterized as follows: (1) the proposed blind detector based on vector HMM, which is employed to describe the statistics of wavelet coefficients, achieves significant improvements in performance compared to the conventional correlation detector; (2) an adaptive watermark embedding scheme is applied to achieve the low distortion according to the human visual system; (3) an optimal multi-bit watermark embedding strategy and a maximum-likelihood detection for tree structure of vector HMM are proposed through system robustness analysis. Simulation results show that relatively high capacity for watermark embedding in low frequency subbands of wavelet domain is achieved with the proposed algorithm, and high robust results are observed against Stirmark attacks, such as JPEG compress, adding noise, median cut and filter.
Robustness is an important issue in the development of multi-bits watermarking algorithm. A new algorithm for robust multi-bits image watermarking based on Hidden Markov Model (HMM) in wavelet domain is proposed. The algorithm is characterized as follows: (1) the proposed blind detector based on vector HMM, which is employed to describe the statistics of wavelet coefficients, achieves significant improvements in performance compared to the conventional correlation detector; (2) an adaptive watermark embedding scheme is applied to achieve the low distortion according to the human visual system; (3) an optimal multi-bit watermark embedding strategy and a maximum-likelihood detection for tree structure of vector HMM are proposed through system robustness analysis. Simulation results show that relatively high capacity for watermark embedding in low frequency subbands of wavelet domain is achieved with the proposed algorithm, and high robust results are observed against Stirmark attacks, such as JPEG compress, adding noise, median cut and filter.
2005, 16(7):1333-1343.
Abstract:
A broadcast encryption allows the sender to securely distribute content to a dynamically changing group of users over a broadcast channel. A public key tracing and revocation scheme can combine the public key encryption with the traitor tracing algorithm. This paper proposes a fully public key tracing and revocation scheme. The salient feature of the scheme is that the secret keys of the users are chosen by the users themselves, while in the previous public key broadcast encryption schemes, the broadcaster publishes the encryption key and distributes the individual secret keys to the users. The scheme deals with the setting of stateless receivers. When the traitors are found, the sender can revoke them without involvement of the remaindering receivers. The encryption algorithm in the scheme is semantically secure against adaptive chosen cipher-text attacks based on the DDH assumption.
A broadcast encryption allows the sender to securely distribute content to a dynamically changing group of users over a broadcast channel. A public key tracing and revocation scheme can combine the public key encryption with the traitor tracing algorithm. This paper proposes a fully public key tracing and revocation scheme. The salient feature of the scheme is that the secret keys of the users are chosen by the users themselves, while in the previous public key broadcast encryption schemes, the broadcaster publishes the encryption key and distributes the individual secret keys to the users. The scheme deals with the setting of stateless receivers. When the traitors are found, the sender can revoke them without involvement of the remaindering receivers. The encryption algorithm in the scheme is semantically secure against adaptive chosen cipher-text attacks based on the DDH assumption.
2005, 16(7):1344-1351.
Abstract:
In this paper three newly proposed stream ciphers S1, S2 and S3 are analyzed. These stream ciphers are designed with respect to different levels of GSM security. The results show that both S1 and S2 are vulnerable to the known plaintext attacks and S3 can not decrypt correctly. With negligible amount of computation and few known keystream bytes, S1 and S2 can be broken completely. Furthermore, simulation results show that S3 cannot work correctly. The conclusion is that these stream ciphers are either extremely weak or poorly designed so that they cannot play the role as the designers hope in GSM network security.
In this paper three newly proposed stream ciphers S1, S2 and S3 are analyzed. These stream ciphers are designed with respect to different levels of GSM security. The results show that both S1 and S2 are vulnerable to the known plaintext attacks and S3 can not decrypt correctly. With negligible amount of computation and few known keystream bytes, S1 and S2 can be broken completely. Furthermore, simulation results show that S3 cannot work correctly. The conclusion is that these stream ciphers are either extremely weak or poorly designed so that they cannot play the role as the designers hope in GSM network security.
2005, 16(7):1352-1358.
Abstract:
This paper integrates traffic engineering (TE) in network planning (network improvement) to build high performance networks, which achieve traffic’s multi-constrained quality of service (QoS). It is a NP complete problem that cannot be efficiently solved by traditional network improvement with extending equipments’ capability. A new network improvement algorithm based on TE is proposed. A heuristic algorithm of graph’s connectivity augmentation is presented to satisfy the topological constraint, a static routing algorithm based on multi-QoS requirements is adopted to satisfy TE constraints, and a genetic algorithm is used to globally search the network with minimum improvement cost and with its capacity of rational allocation. With the simulation analysis, while achieving network’s multi-constraint, rebuilding networks by the new network improvement algorithm is only a traffic balancing, but not a local blocking of the existing high performance networks.
This paper integrates traffic engineering (TE) in network planning (network improvement) to build high performance networks, which achieve traffic’s multi-constrained quality of service (QoS). It is a NP complete problem that cannot be efficiently solved by traditional network improvement with extending equipments’ capability. A new network improvement algorithm based on TE is proposed. A heuristic algorithm of graph’s connectivity augmentation is presented to satisfy the topological constraint, a static routing algorithm based on multi-QoS requirements is adopted to satisfy TE constraints, and a genetic algorithm is used to globally search the network with minimum improvement cost and with its capacity of rational allocation. With the simulation analysis, while achieving network’s multi-constraint, rebuilding networks by the new network improvement algorithm is only a traffic balancing, but not a local blocking of the existing high performance networks.
联系方式
- 《Journal of Software 》
- 主办单位：Institute of Software, CAS, China
- 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
