Abstract:Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. This paper presents a new fast ant heuristic for the QAP, the approximatebackbone guided fast ant colony algorithm (ABFANT). The main idea is to fix the approximatebackbone which is the intersection of several local optimal permutations to the QAP. After fixing it, the authors can smooth the search space of the QAP instance without losing the search capability, and then solve the instance using the known fast ant colony algorithm (FANT) which is one of the best heuristics to the QAP in the much smoother search space. Comparisons of ABFANT and FANT within a given iteration number are performed on the publicly available QAP instances from QAPLIB. The result demonstrates that ABFANT significantly outperforms FANT.Furthermore, this idea is general and applicable to other heuristics of the QAP.

Abstract:Haplotypes, rather than genotypes are required in some disease susceptibilities and drug response tests.However, it is both time-consuming and expensive to obtain haplotypes experimentally. Therefore usually genotype data are collected in the laboratory at first, then, haplotype data are inferred from them resorting to some computational approaches. Different from Clark's well-known haplotype inference method, Gusfield and Wang et al.proposed a new model according to the maximum parsimony principle. It tries to find a minimum set of haplotypes that can explain the genotype samples. This parsimony model overcomes some weaknesses of Clark's method. For the parsimony this paper presents model a polynomial time greedy algorithm and a compound algorithm that combines the greedy policy with the branch-and-bound strategy in a uniform framework. Compared with the original complete algorithm proposed by Wang et al., the greedy approximation algorithm runs much faster, and in the meanwhile, produces relatively higher accurate results. The compound algorithm is also a complete algorithm.Simulation results show that it is much more efficient and can be applied to instances of much larger scales than the original complete algorithm.

Abstract:Synchronization operations make a huge expense for concurrent Java programs. This paper proposes an effective and precise static analysis algorithm for the redundant synchronization removal. The algorithm consists of two phases-basic analysis and inter-thread temporal analysis. Both phases take the effect of control flow relation and thread control relation into count. This paper also constructs a Java compiler-JTool and implements the algorithm on it. To deterministic single-threaded programs, the removal ratio reaches 100% and to multi-threaded programs, the removal ratio is higher than the existing analysis tools.

Abstract:Distributed cognition theory plays a role of instructor in Human-Computer Interaction research by coordinating interaction between human and computer and combining advantages of them. Though Resources Model based on distributed cognition theory has been successfully employed for analyzing human computer interaction, the model, to some extent, leads to confusion in the representative forms because of the absence of support to complex user tasks and correct definitions of elements. Therefore, an extended resources model (ERM) is constructed by using distributed cognition theory to connect actions with representations in Human-Computer Interaction and to guide the design and realization of interfaces. The Extended Resources Model supports actions with static constructions and interactive strategies so as to decrease human cognitive burdens of interaction. This work will be beneficial to designing interfaces according to human’s cognitive characteristics.

Abstract:Dynamic voltage scaling is an effective low-power technique. Using the technique, compiler-directed dynamic voltage scaling can reduce computer’s energy consumption effectively. Based on programming language’s syntax tree, a real-time dynamic voltage scaling algorithm for low power is presented, and the algorithm assisted with static timing analysis could make intra-task dynamic voltage scaling by automatically inserting dynamic voltage scaling source code. The algorithm has been realized in the real-time low-power system RTLPower, and obtained energy reduction of up to 50 percent over no power management in some real-time embedded benchmarks.

Abstract:Software process is a human-centered system, with special characteristics in dynamic and continuous evolvement. The physical execution of a defined process will normally deviate from its process model. This paper uses E-CSPE (extended constraints on succeeding and proceeding events) constraints to carry out process validation and deviation measurement. The event constraints are defined based on the process model. The execution of a process instance is recorded down as an event sequence. The event sequence is analyzed to determine how much each event constraint defined is covered or violated. The result can be used to compute the EPD (event constraint based process difference metric) and EAD (event constraint based activity deviation metric) metrics. The EPD metric can reflect the difference between the process execution and its process model, while the EAD metric can provide some evidence for process evolvement.

Abstract:This paper presents a survey on the theory of provable security and its applications to the design and analysis of security protocols. It clarifies what the provable security is, explains some basic notions involved in the theory of provable security and illustrates the basic idea of random oracle model. It also reviews the development and advances of provably secure public-key encryption and digital signature schemes, in the random oracle model or the standard model, as well as the applications of provable security to the design and analysis of session-key distribution protocols and their advances.

Abstract:A formal method which can be used to analyze security properties such as accountability and fairness in electronic commerce protocols is presented. Compared with the previous work, the main contributions are the following. Firstly, a formal definition is given to the possession set of each protocol participant, and the initial possession set depends only on the environment. Secondly, the set of initial state assumptions is divided into three categories: basic assumptions, trust assumptions, and protocol comprehension assumptions, in order to avoid analysis errors caused by informal initial state assumptions. Thirdly, the set of trust assumptions is articulated by formal specification at a lower level of granularity, exposing the essence of the protocol. Fourthly, establishing an axiom system makes the new approach more rigorous and expressive.

Abstract:Real time transmission, which is delay sensitive, is an important aspect of application-layer multicast. It is crucial to build an efficient multicast tree to guarantee the lower delay. This research is focused on the algorithms of the minimum-delay spanning tree for the application-layer multicast. Firstly, it is stated that the total delay is affected by communication delay, processing delay and the degree of nodes. Then the network is modeled into the node-and-edge-weighted directed graph with the limited degree of nodes. In this model the problem is shown to be NP-hard. Therefore, two kinds of heuristic algorithms are proposed, which are based on the maximum degree and the maximal length path respectively. Finally, the simulation demonstrates that the proposed algorithms are valid.

Abstract:This paper proposes a generic audit policy model on multilevel secure DBMS. The model is powerful expressively which not only expresses audit policy based on periodical time constraints, but also implements audit policy deduction based on rules. Furthermore, fine-grained audit policies are possible in this model with the introduction of object attribute predicate. The decidability of the model is proven and a decidability algorithm is presented.

Abstract:Current strand spaces model can not analyze some complex security protocols on account of their poor cryptographic primitives’ abstract. So it is very necessary to extend original theory of strand spaces so that it can be applied to analyze real world protocols. The penetrator’s strands are extended through adding signature, signature verification and HMAC (keyed-hashing for message authentication code) traces to them. A new notion of ideal is defined and the relevant propositions or theorems are therefore modified and proved. The extended honest ideals model not only inherits its original characters, but also is adaptive to the analysis of protocols with more cryptographic primitives such as JFK or IKE2.

Abstract:This paper proposes a cooperative secure reliable storage system depending on pure P2P and supporting self-repair. Participant nodes of this system form an overlay by Paramecium protocol, which maintains the organization of system and provides routing service, or other compatible distributed hash table (DHT) protocols. The PKI authentication mechanism is introduced to ensure security in an open environment. Binding user data with replica identifiers supports secure auto-repair. The introduction of replica types provides secure sharing-write. Preliminary analysis and experiments demonstrate that it maintains a high reliability and read/write performance in real settings while keeping the cost of maintenance bandwidth low.

Abstract:Watermark detection plays a crucial role in digital watermarking. It has traditionally been tackled using correlation-based techniques. However, correlation-based detection is not the optimum choice either when the host media doesn't follow a Gaussian distribution or when the watermark is not embedded in the host media in an additive way. This paper addresses the problem of DCT (discrete cosine transform) domain multiplicative watermark detection for digital images. First, generalized Gaussian distributions are applied to statistically model the AC (alternative current) DCT coefficients of the original image. Then, the imperceptibility constraint of watermarking is exploited, and watermark detection is formulated as the problem of weak signal detection in non-Gaussian noise. A binary hypothesis test concerning whether or not an image is watermarked is established, and an optimum detection structure for blind watermark detection is derived. Experimental results indicate the superiority of the new detector in the case that the embedding strengths are unknown to the detector. Therefore, the proposed detector can be used for the copyright protection of the digital multimedia data.

Abstract:A dynamic multi-secrets sharing threshold scheme is presented to apply to a large scale electronic voting system with many talliers (tallying authorities). Even if there exist adaptive adversaries, this scheme can guard the ballot’s producing, encrypting, transmitting, decrypting and final tallying in spite of the adversaries’s attack, so the scheme guarantees robustness. In this paper, the verifiability of the voters’ qualification and talliers’ identification will be solved by a dynamic multi-secret sharing scheme without invoking more zero knowledge proof to maintain privacy, universal verifiablitlity, and anonymity of ballots. It holds more communication efficiency and more security than the proposed schemes in early time.

Abstract:In order to find a way of fast confirmation for the real time clearance of online financial trading, this paper analyzes the typical online trading process and the security characteristics. Based on the principle of elliptic curves signing, a kind of clear confirmation scheme is proposed, which can confirm the trading result step by step, and finish it once a time at the final clear. This scheme can avoid the complicated PKI system and the one by one confirm process, realize the non-reputation efficiently, keep the proof of signing easily, and make straight through process and online clear and possible.

Abstract:This paper proposes an anonymous fingerprinting scheme based on the additively homomorphic public key cryptosystems. The proposed fingerprinting scheme enables the merchant to identify the illegal distributors without the help of a trusted third party when he/she finds an illegally redistributed fingerprinted copy. Furthermore, it allows two-party trials, i.e. there is no need for the accused (and possibly innocent) buyer to take part in the dispute resolution protocol and reveal his/her secrets. In addition, the problem of how to construct the anonymous public key and private key pairs is also addressed in the scheme. The security analysis shows that the proposed scheme is secure for both seller and buyer, and has the properties of anonymity and unlinkability for the buyer.

Abstract:Software pipelining is a loop scheduling technique that extracts instruction level parallelism by overlapping the execution of several consecutive iterations. One of its drawbacks is the high register requirements, which may lead to software pipelining failure due to insufficient static general registers in Itanium. This paper evaluates the register requirements of software-pipelined loops and presents three new methods for software pipelining loops that require more static general registers than those available in Itanium processor. They reduce register pressure by either reducing instructions in the loop body or allocating stacked non-rotating registers or rotating register in register stack to serve as static registers. These methods are better than the existing techniques in that they further improve performance gain from software pipelining by increasing software-pipelined loops. These methods have been implemented in open research compiler (ORC) targeted for Itanium processor, and they perform well on loops of the programs in NAS Benchmarks. For some benchmarks, the performance is improved by more than 21%.

Abstract:Software pipelining tries to improve the performance of a loop by overlapping the execution of several successive iterations. As processor gets much higher speed, the memory access latency becomes a bottleneck that restricts higher performance. Software pipelining has been combined with several memory optimization technologies for higher performance by hiding memory access latency. This paper presents a foresighted latency modulo scheduling (FLMS) algorithm which determines the latency of load instructions according to the feature of the loop. Experimental results show that FLMS decreases the stall time and improves the performance of programs.

Abstract:Software pipelining can speedup the loop execution. Modulo scheduling is a widely used heuristic for software pipelining. Cache hierarchies can improve memory systems, but probably all processor implementations introduce additional delays (cache penalty). This paper demonstrates possible cache penalty due to modulo scheduling, and presents an algorithm named Prevent Cache Penalty in Modulo Scheduling (PCPMS), which can prevent cache penalty due to modulo scheduling. Experimental results show that PCPMS can prevent cache penalty and improve the performance of programs.

Abstract:In this paper, summarization of results of program funded by NSFC in the field of natural language processing in recent years is given, including summarization of Chinese information processing technology, natural language processing application technology, minority language information processing technology.