Volume 27,Issue 12,2016 Table of Contents

  • Display Type:
  • Text List
  • Abstract List
  • 1  Satisfiability Threshold of the Regular Random (k,r)-SAT Problem
    ZHOU Jin-Cheng XU Dao-Yun LU You-Jun
    2016, 27(12):2985-2993. DOI: 10.13328/j.cnki.jos.005129
    [Abstract](3037) [HTML](1041) [PDF 1.14 M](5086)
    Abstract:
    This article studies the strictly regular (k,r)-SAT problem by restricting the k-SAT problem instances, where each variables occurs precisely r=2s times and each of the positive and negative literals occurs precisely s times. By constructing a special independent random experiment, the study derives an upper bound on the satisfiability threshold of the strictly regular random (k,r)-SAT problem via the first moment method. Based on the fact that the satisfiability threshold of the strictly regular and the regular random (k,r)-SAT problems are approximately equal, a new upper bound on the threshold of the regular random (k,r)-SAT problem is obtained. This new upper bound is not only below the current best known upper bounds on the satisfiability threshold of the regular random (k,r)-SAT problem, but also below the satisfiability threshold of the uniform random k-SAT problem. Thus, it is theoretically explained that in general the regular random (k,r)-SAT instances are harder to satisfy at their phase transition points than the uniform random k-SAT problem at the corresponding phase transition points with same scales. Finally, numerical results verify the validity of our new upper bound.
    2  Exogenous Quantum Markov Chains and Reachability Analysis
    LIN Yun-Guo LI Yong-Ming
    2016, 27(12):2994-3002. DOI: 10.13328/j.cnki.jos.004916
    [Abstract](2652) [HTML](1213) [PDF 1.10 M](5074)
    Abstract:
    In order to describe quantum properties of open quantum system, it is necessary to extend the existing quantum Markov chains. In this paper, Exogenous quantum Markov chains is introduced through building Exogenous quantum operator logic. For this new type of quantum Markov chain, the paper focuses on four reachability formulas, gives the solution of their satisfiability problems, and analyzes their decidability problems. As an application, an example is provided to show that the termination of the generalized quantum loop program corresponds to the future reachability of Exogenous quantum Markov chains, and therefore can be decided by checking satisfaction of quantum formulas.
    3  Sufficient Conditions for Convergence of the Warning Propagation Algorithm
    WANG Xiao-Feng XU Dao-Yun
    2016, 27(12):3003-3013. DOI: 10.13328/j.cnki.jos.004940
    [Abstract](2898) [HTML](1232) [PDF 1.36 M](4815)
    Abstract:
    Message propagation algorithms are very effective in finding satisfying assignments for SAT instances, and hard region become narrower. However, message propagation algorithms do not always converge for graphs with cycles. Unfortunately, rigorous theory proof of this phenomenon is still lacking. Warning propagation (WP) algorithm is the most basic message propagation algorithm, we have derived the sufficient conditions for convergence of the warning propagation algorithm. Lastly, experimental results show that such conditions for convergence of WP are very effective in different group data from random satisfiable 3-SAT instances.
    4  Improving the Performance of Defect Prediction Based on Evolution Data
    WANG Dan-Dan WANG Qing
    2016, 27(12):3014-3029. DOI: 10.13328/j.cnki.jos.004869
    [Abstract](2237) [HTML](1582) [PDF 1.79 M](4672)
    Abstract:
    It is an undisputed fact that software continues to evolve. Software evolution is caused by requirement changes which often result in injection of defects. Existing defect prediction techniques mainly focus on utilizing the attributes of software work products, such as documents, source codes and test cases, to predict defects. Consider an evolving software as a species and its development process as a natural species' evolutionary process, the injection of defects may have the characters of a species and will be impacted by its evolution. A great many of researchers have studied the process of software evolution and proposed some evolution related metrics. In this study, a set of new metrics is first proposed based on evolutionary history to characterize software evolution process, and then a case study on building defect prediction models is presented. Experiments on six well-known open source projects achieved good performance, demonstrating the effectiveness of the proposed metrics.
    5  Research on Multi-Scale Data Mining Method
    LIU Meng-Meng ZHAO Shu-Liang HAN Yu-Hui SU Dong-Hai LI Xiao-Chao CHEN Min
    2016, 27(12):3030-3050. DOI: 10.13328/j.cnki.jos.004924
    [Abstract](3696) [HTML](1234) [PDF 3.17 M](6212)
    Abstract:
    Many researches of data mining have paid close attention to multi-scale theory. However the study of multi-scale data mining still comes short on universal theories and approaches. To overcome this limitation, this paper conducts a study of universal multi-scale data mining on theoretical and methodological aspect. First, the paper lays out the definition of data-scale-partition and data-scale based on concept hierarchy, and characterizes the relationship of upper-layer and lower-layer datasets between multi-scale datasets. Next, it illustrates the definition and essence of multi-scale data mining, and presents the classification of multi-scale data mining methods. Finally, it introduces the algorithm framework and its theoretical basis of multi-scale data mining, and proposes an algorithm named MSARMA (multi-scale association rules mining algorithm) to realize the transition of knowledge in multi-scale data expressions. Experiments are carried out to test MSARMA with the help of IBM T10I4D100K dataset and demographic dataset from H province, and the results indicate that MSARMA is effective and feasible with better coverage rate, better accuracy and lower average support error.
    6  Optimizing Top-k Similarity Join Algorithm
    WANG Hong-Ya YANG Li-Hong LIU Xiao-Qiang
    2016, 27(12):3051-3066. DOI: 10.13328/j.cnki.jos.005012
    [Abstract](2653) [HTML](1455) [PDF 1.77 M](4811)
    Abstract:
    Similarity join is widely used in data cleaning, data integration and the detection of near duplicate Web pages. Existing similarity join algorithms fall into two categories:Threshold-based similarity join and Top-k similarity join. Top-k similarity join is suitable for applications in which the threshold is unknown in advance. The most efficient Top-k similarity join algorithm is Top-k-join, which is proposed by Xiao et al. In order to resolve the performance problemsof Topk-join, a novel Top-k similarity join algorithm Opt-join is proposed in this paper. By integrating the token batch processing technique into the existing event-driven framework, Opt-join reduces the cost of processing the prefix events. In addition, Opt-joinreduces the cost in hash lookup by switching the positions of the hash lookup and filtering operations. The correctness of the new algorithm is proved. Experimental results show that 1.28x-3.09xspeed-up is achieved by Opt-join compared with Topk-join. More importantly, with the increase of the record length or the k value, Opt-join surpasses Topk-join by a larger margin.
    7  Technique Based on Shared Execution Strategy for Optimizing Interval Query
    ZHOU Xin ZHANG Xiao XUE Zhong-Bin WANG Shan
    2016, 27(12):3067-3084. DOI: 10.13328/j.cnki.jos.005013
    [Abstract](1699) [HTML](961) [PDF 2.27 M](3720)
    Abstract:
    As an important query type, interval query is widely used in social networks, information retrieval and database domain. Many kinds of optimization techniques have sprung up to support effective interval query. Although existing methods are efficient to handle single query, they all suffer from performance problem when the concurrent query loads exceed the processing capacity of the server such that more than 70% queries couldn't receive the results in the expected time. To solve this problem, this paper presents a method named SESIQ (shared execution strategy for interval queries). SESIQ batches interval queries, analyzes common operations among a group of interval queries and reduces duplicate data access to lower the cost of disk I/O and network transmission. The paper theoretically studies and analyzes SESIQ, and demonstrates the feasibility by large number of experiments based on two types of real datasets. Results show that SESIQ improves the performance of interval query by several ten folds.
    8  Real-Time and Passive Wormhole Detection for Wireless Sensor Networks
    LU Li Muhammad Jawad HUSSAIN ZHU Jin-Qi
    2016, 27(12):3085-3103. DOI: 10.13328/j.cnki.jos.004938
    [Abstract](2906) [HTML](1293) [PDF 2.24 M](4846)
    Abstract:
    Wormhole attack is one of the severe threats to wireless sensor and ad hoc networks. Most of the existing countermeasures either demand high network overheads or require specialized hardware to capture the specific symptoms induced by the wormholes, which in result, limits their applicability. This paper exploits an inevitable symptoms of wormhole attack and proposes Pworm, a real-time and passive wormhole detection and localization scheme based on the key observation that a large amount of network traffic are attracted by the wormholes. The proposed scheme can silently observe the variations in network topology to infer the existence of wormholes. Besides the scheme solely depends on network routing information and does not demand any specialized hardware. System performance of the scheme is evaluated through extensive simulations of 100 to 500 nodes for various network scales and the results show that Pworm is well suited for false alarms with good scalability and low time delay.
    9  Software Defined Security Networking Mechanism Against DDoS Attacks
    WANG Xiu-Lei CHEN Ming XING Chang-You SUN Zhi WU Quan-Feng
    2016, 27(12):3104-3119. DOI: 10.13328/j.cnki.jos.004942
    [Abstract](3510) [HTML](1522) [PDF 2.50 M](5678)
    Abstract:
    The emerging software defined networking (SDN) offers a new way to rethink the defense of DDoS attacks. In this paper the DDoS attacks are first modeled and analyzed from the perspective of network architecture, and the necessary conditions of DDoS attacks such as connectivity, concealment and aggressivity are presented. Then for breaking or limiting these necessary conditions, a software defined security networking mechanism (SDSNM) against DDoS attacks is proposed. The security mechanism is implemented in the edge SDN networks while inheriting the core infrastructure of IP network. Cloud computing and Chord technology are also employed to solve the expansibility and consistency problems. The experiments demonstrate that SDSNM is feasible and incrementally deployable.
    10  Coverage Prediction Model and Number Estimation for Directional Sensor Networks
    LIU Zhi-Min JIA Wei-Jia WANG Guo-Jun
    2016, 27(12):3120-3130. DOI: 10.13328/j.cnki.jos.004949
    [Abstract](2069) [HTML](1150) [PDF 1.32 M](4007)
    Abstract:
    Recently, directional sensor networks (DSN) have received a great deal of attention due to their wide range of applications. Unlike conventional omni-directional sensors that always have an omni-angle of sensing range, a DSN is composed of many directional sensors which have a limited angle of sensing range due to technical constraints or cost considerations. This paper studies coverage prediction and number estimation model for directional sensor networks. Aiming at better guiding initial deployment of DSN, a novel probability-based networks coverage prediction model with the boundary effects named PCPMB is proposed. Simulation results show that the proposed model outperforms the previous published model without boundary effect.
    11  Shape Recognition Using Unordered Point-Set Description and Matching of Object Contour
    WANG Bin
    2016, 27(12):3131-3142. DOI: 10.13328/j.cnki.jos.005101
    [Abstract](2515) [HTML](1480) [PDF 2.08 M](4387)
    Abstract:
    Treating the shape contour as an unordered point set and extracting shape features from it for fast and effective shape recognition is a challenge task of shape analysis. To address this issue, a complex-network based shape description and recognition method is proposed in this paper. In this method, a self-organized dynamic network-evolution model is built for providing a hierarchical description framework. In each moment of the dynamic evolution of the complex network, local and global measurements are performed against the network shut that both weighted and un-weighted features are extracted from the network. At the shape matching stage, the local matching (based on Hausdorff distance) and global matching (based on L1 distance) are conducted using the obtained local descriptor and global descriptor respectively. The dissimilar value between two shapes is determined by combining the two distance measures. Several standard test sets are used to evaluate the performance of the proposed method, and the experimental results show that the proposed method can provide robust and fast shape recognition in high accuracy.
    12  Method of Formal Design and Verification of OS on Assembly Layer
    QIAN Zhen-Jiang HUANG Hao SONG Fang-Min
    2016, 27(12):3143-3157. DOI: 10.13328/j.cnki.jos.004851
    [Abstract](2740) [HTML](1304) [PDF 1.77 M](5206)
    Abstract:
    The correctness of design and implementation of operating system is difficult to be described and verified with the traditional methods, due to the huge size of the system. In this paper, a model is build for the functionality semantics of the system modules on the assembly layer. A system state model is proposed as the link of the design and verification on the assembly layer. Through defining the legal states and state transition functions, the universe of discourse of the system state model and the assembly layer are constructed. The correctness of functionality modules is verified to ensure the correctness of design and functionality implementation. Within the Isabelle/HOL theorem prover, the system state model is described, and the correctness of functionality semantics of the system modules is verified. Meanwhile, the self-implemented secure trusted operating system (verified secure operating system, VSOS) is used as the example to illustrate the proposed formal method for design and verification, and to show the feasibility of the method.
    13  Fault Tolerant Global Scheduling with Non-Preemptive Backups
    PENG Hao LU Yang SUN Feng HAN Jiang-Hong
    2016, 27(12):3158-3171. DOI: 10.13328/j.cnki.jos.004917
    [Abstract](1909) [HTML](1278) [PDF 1.59 M](3609)
    Abstract:
    Fault tolerance is a critical capability of hard real-time systems. Even with faults, fault tolerant scheduling algorithms are able to guarantee the real time property of tasks. In primary-backup based fault tolerant scheduling algorithms, only a small time window is left for the backup when the primary faults occur, therefore the backup will likely miss its deadline. This paper proposes a fault tolerant global scheduling with non-preemptive backups (FTGS-NPB). By assigning the highest priority to all backups, the backup can attain processor immediately in case of primary faults, and keep executing until finishing its job. In this way the backup can achieve the shortest response time. The schedulability tests are set up based on deadline analysis and response time analysis. The compatibility of priority assignment algorithms and schedulability tests is discussed. The simulation results show that FTGS-NPB can reduce the amount of additional processors for achieving fault tolerant capability.
    14  Data Characteristics-Based Kernel Malware Detection
    CHEN Zhi-Feng LI Qing-Bao ZHANG Ping DING Wen-Bo
    2016, 27(12):3172-3191. DOI: 10.13328/j.cnki.jos.004927
    [Abstract](3247) [HTML](1684) [PDF 2.23 M](5406)
    Abstract:
    Kernel malwares are serious threat to the security of operating system. Existing kernel malware detection methods are mainly code view-based, which cannot detect the code reuse and code obfuscation attacks; and a small number of available detection methods for data attacks have limit detection capability due to the limited data invariants. To solve these problems, a kernel malware detection technique based on data characteristics is proposed. First, a kernel data object access model is built by analyzing the kernel object access process during the kernel running. Then, data characteristics building process is discussed based on the model. The process uses dynamic monitoring and static analysis methods to identify the kernel data objects, and employs EPT to monitor the memory access operations to build data characteristics. Finally, the kernel malware detection algorithm based on data characteristics is realized. With this groundwork, a kernel malware detection prototype system MDS-DCB is designed and implemented based on Bitvisor, and the effectiveness and performance overhead of MDS-DCB are evaluated by comprehensive experiments. The results show that MDS-DCB can effectively detect kernel malwares, and the performance penalty induced by MDS-DCB is acceptable.
    15  Load Balancing Framework for Metadata Service of Distributed File Systems
    SUN Yao LIU Jie YE Dan ZHONG Hua
    2016, 27(12):3192-3207. DOI: 10.13328/j.cnki.jos.004930
    [Abstract](3049) [HTML](1280) [PDF 1.91 M](5825)
    Abstract:
    Request load balancing is the core issue in distributed file system metadata management. To maximize the throughput of the metadata service, an adaptive request load balancing framework is critical. This paper presents a distributed cache framework above the distributed metadata management schemes to manage hotspots rather than managing all metadata to achieve request load balancing. Compared with the existing distributed metadata load balancing framework, it has a higher degree of flexibility of the two-tier load balancing structure, and is stronger on the perception of the overall load. It also avoids hot spots redistribution and namespace structure destruction caused by metadata migration. Compared with data, metadata has its own distinct characteristics, such as small size and large quantity. The cost of non-use metadata prefetching is much less than data prefetching. Based on this study, a time period-based prefetching strategy and a perfecting-based adaptive replacement cache algorithm are devised to improve the performance of the distributed caching layer to adapt constantly changing workloads. Finally, the presented approach is evaluated with a Hadoop distributed file system cluster.
    16  Approach of Measuring and Predicting Software System State Based on Hidden Markov Model
    WU Jia ZENG Wei-Ru CHEN Han-Lin TANG Xue-Fei
    2016, 27(12):3208-3222. DOI: 10.13328/j.cnki.jos.005014
    [Abstract](1973) [HTML](1347) [PDF 1.96 M](5795)
    Abstract:
    With increased improvement on the capability and performance of software systems, enterprises have improved the management efficiency and enhanced the business model. Meanwhile, as software systems become more and more complex, severe challenges for the management of software systems are encountered. This paper presents a method for measuring and predicting software system state based on hidden Markov model. It establishes the linkage between the exterior state (the observation state) and the interior state (the hidden state) of the software system. K-means method is applied to construct the observation state of system. Triple order exponential smoothing is used to predict the future state of the system exterior state which changes cyclically. The experimental analysis on B/S information management system shows that the proposed method has high accuracy for measuring and predicting the software system state.

    Current Issue


    Volume , No.

    Table of Contents

    Archive

    Volume

    Issue

    联系方式
    • 《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.

    Beijing Public Network Security No. 11040202500063