Out-of-order superscalar processors rename register numbers to remove false dependencies between instructions. A renaming logic for register renaming is a high-cost module in a superscalar processor, and it consumes considerable energy. A renamed trace cache (RTC) was proposed for reducing the energy consumption of a renaming logic. An RTC caches and reuses renamed operands, and thus, register renaming can be omitted on RTC hits. However, conventional RTCs suffer from several performance, energy consumption, and hardware overhead problems. We propose a semi-global renamed trace cache (SGRTC) that caches only renamed operands that are short distance from producers outside traces, and solves the problems of conventional RTCs. Evaluation results show that SGRTC achieves 64% lower energy consumption for renaming with a 0.2% performance overhead as compared to a conventional processor.

Traceability links between requirements and source code are helpful in software reuse and maintenance tasks. However, manually recovering links in a large group of products requires significant costs and some links may be overlooked. Here, we propose a semi-automatic method to recover traceability links between requirements and source code in the same series of large software products. In order to support differences in representation between requirements and source code, we recover links by using the configuration management log as an intermediary. We refine the links by classifying requirements and code elements in terms of whether they are common to multiple products or specific to one. As a result of applying our method to real products that have 60KLOC, we have recovered valid traceability links within a reasonable amount of time. Automatic parts have taken 13 minutes 36 seconds, and non-automatic parts have taken about 3 hours, with a recall of 76.2% and a precision of 94.1%. Moreover, we recovered some links that were unknown to engineers. By recovering traceability links, software reusability and maintainability will be improved.

In this letter, we give a trace representation of binary Jacobi sequences with period pq over an extension field of the odd prime field Fr. Our method is based on the use of a pqth root of unity over the extension field, and the representation of the Jacobi sequences by corresponding indicator functions and quadratic characters of two primes p and q.

Concurrency bugs do significantly affect system reliability. Although many efforts have been made to address this problem, there are still many bugs that cannot be detected because of the complexity of concurrent programs. Compared with atomicity violations, order violations are always neglected. Efficient and effective approaches to detecting order violations are therefore in urgent need. This paper presents a bidirectional predictive trace analysis approach, BIPED, which can detect order violations in parallel based on a recorded program execution. BIPED collects an expected-order execution trace into a layered bidirectional prediction model, which intensively represents two types of expected-order data flows in the bottom layer and combines the lock sets and the bidirectionally order constraints in the upper layer. BIPED then recognizes two types of candidate violation intervals driven by the bottom-layer model and then checks these recognized intervals bidirectionally based on the upper-layer constraint model. Consequently, concrete schedules can be generated to expose order violation bugs. Our experimental results show that BIPED can effectively detect real order violation bugs and the analysis speed is 2.3x-10.9x and 1.24x-1.8x relative to the state-of-the-art predictive dynamic analysis approaches and hybrid model based static prediction analysis approaches in terms of order violation bugs.

This paper proposes an automatic error correction method for melanosome tracking. Melanosomes in intracellular images are currently tracked manually when investigating diseases, and an automatic tracking method is desirable. We detect all melanosome candidates by SIFT with 2 different parameters. Of course, the SIFT also detects non-melanosomes. Therefore, we use the 4-valued difference image (4-VDimage) to eliminate non-melanosome candidates. After tracking melanosome, we re-track the melanosome with low confidence again from t+1 to t. If the results from t to t+1 and from t+1 to t are different, we judge that initial tracking result is a failure, the melanosome is eliminated as a candidate and re-tracking is carried out. Experiments demonstrate that our method can correct the error and improves the accuracy.

Let p be an odd characteristic and m be the degree of a primitive polynomial f(x) over the prime field Fp. Let ω be its zero, that is a primitive element in F*pm, the sequence S={si}, si=Tr(ωi) for i=0,1,2,… becomes a non-binary maximum length sequence, where Tr(·) is the trace function over Fp. On this fact, this paper proposes to binarize the sequence by using Legendre symbol. It will be a class of geometric sequences but its properties such as the period, autocorrelation, and linear complexity have not been discussed. Then, this paper shows that the generated binary sequence (geometric sequence by Legendre symbol) has the period n=2(pm-1)/(p-1) and a typical periodic autocorrelation. Moreover, it is experimentally observed that its linear complexity becomes the maximum, that is the period n. Among such experimental observations, especially in the case of m=2, it is shown that the maximum linear complexity is theoretically proven. After that, this paper also demonstrates these properties with a small example.

Fault localization is a necessary process of locating faults in buggy programs. This paper proposes a novel approach using dynamic slicing and association analysis to improve the effectiveness of fault localization. Our approach utilizes dynamic slicing to generate a reduced candidate set to narrow the range of faults, and introduces association analysis to mine the relationship between the statements in the execution traces and the test results. In addition, we develop a prototype tool DSFL to implement our approach. Furthermore, we perform a set of empirical studies with 12 Java programs to evaluate the effectiveness of the proposed approach. The experimental results show that our approach is more effective than the compared approaches.

Aspect-oriented software development (AOSD) helps to solve the problem of low scalability and high maintenance costs of legacy systems caused by code scattering and tangling by extracting cross-cutting concerns and inserting them into aspects. Identifying the cross-cutting concerns of legacy systems is the key to reconstructing such systems using the approach of AOSD. However, current dynamic approaches to the identification of cross-cutting concerns simply check the methods' execution sequence, but do not consider their calling context, which may cause low precision. In this paper, we propose an improved comprehensive approach to the identification of candidate cross-cutting concerns of legacy systems based on the combination of the analysis of recurring execution relations and fan-ins. We first analyse the execution trace with a given test case and identify four types of execution relations for neighbouring methods: exit-entry, entry-exit, entry-entry and exit-exit. Afterwards, we measure the methods' left cross-cutting degrees and right cross-cutting degrees. The former ensures that the candidate recurs in a similar running context, whereas the latter indicates how many times the candidate cross-cuts different methods. The final candidates are then obtained from those high fan-in methods, which not only cross-cut others more times than a predefined threshold, but are always entered or left under the same running context. The experiment conducted on three open source systems shows that our approach improves the precision of identifying cross-cutting concerns compared with tradition ones.

In this paper, we present an average-case efficient algorithm to resolve the problem of determining whether two Boolean functions in trace representation are identical. Firstly, we introduce a necessary and sufficient condition for null Boolean functions in trace representation, which can be viewed as a generalization of the well-known additive Hilbert-90 theorem. Based on this condition, we propose an algorithmic method with preprocessing to address the original problem. The worst-case complexity of the algorithm is still exponential; its average-case performance, however, can be improved. We prove that the expected complexity of the refined procedure is O(n), if the coefficients of input functions are chosen i.i.d. according to the uniform distribution over F2n; therefore, it performs well in practice.

We propose a 2 × 2 space-time block code based on a trace criterion for 64-quadrature amplitude modulation (QAM). We introduce a method to easily calculate the trace norm of a space-time code for 64-QAM, and propose a new space-time code searched by this method. The error rate performance of the proposed code is compared with that of the Alamouti code. By comparison of the theoretical upper bounds, the proposed space-time code is better than the Alamouti code, when the number of receiving antennas is more than one. Moreover, bit error rate performance of the proposed code is compared with maximum likelihood decoding on perfect channel state information Rayleigh fading channels by computer simulations. These results show the proposed code almost outperforms the Alamouti code when the number of receive antennas is more than one, and the increased number of receiving antennas with our code is a decided advantage.

Single-packet attack can be tracked with logging-based IP traceback approaches, whereas DDoS attack can be tracked with marking-based approaches. However, both approaches have their limits. Logging-based approaches incur heavy overhead for packet-digest storage as well as time overhead for both path recording and recovery. Marking-based approaches incur little traceback overhead but are unable to track single packets. Simply deploying both approaches in the same network to deal with single-packet and DDoS attacks is not an efficient solution due to the heavy traceback overhead. Recent studies suggest that hybrid approaches are more efficient as they consume less router memory to store packet digests and require fewer attack packets to recover attack paths. Thus, the hybrid single packet traceback approach is more promising in efficiently tracking both single-packet and DDoS attacks. The major challenge lies in reducing storage and time overhead while maintaining single-packet traceback capability. We present in this paper a new hybrid approach to efficiently track single-packet attacks by designing a novel path fragment encoding scheme using the orthogonality of Walsh matrix and the degree distribution characteristic of router-level topologies. Compared to HIT (Hybrid IP Traceback), which, to the best of our knowledge, is the most efficient hybrid approach for single-packet traceback, our approach has three advantages. First, it reduces the overhead by 2/3 in both storage and time for recording packet paths. Second, the time overhead for recovering packet paths is also reduced by a calculatable amount. Finally, our approach generates no more than 2/3 of the false-positive paths generated by HIT.

Probabilistic Packet Marking (PPM) is a scheme for IP traceback where each packet is marked randomly with an IP address of one router on the attack path in order for the victim to trace the source of attacks. In previous work, a network coding approach to PPM (PPM+NC) where each packet is marked with a random linear combination of router IP addresses was introduced to reduce number of packets required to infer the attack path. However, the previous work lacks a formal proof for benefit of network coding to PPM and its proposed scheme is restricted. In this paper, we propose a novel method to prove a strong theorem for benefit of network coding to PPM in the general case, which compares different perspectives (interests of collecting) at the collector in PPM+NC scheme. Then we propose Core PPM+NC schemes based on our core network coding approach to PPM. From experiments, we show that our Core PPM+NC schemes actually require less number of packets than previous schemes to infer the attack path. In addition, based on the relationship between Coupon Collector's Problem (CCP) and PPM, we prove that there exists numerous designs that CCP still benefits from network coding.

In this letter, we present a general construction of sequence sets with low correlation zone, which is based on finite fields and the balance property of some functions. The construction is more flexible as far as the partition of parameters is concerned. A simple example is also given to interpret the construction.

Tin (Sn) contacts are widely applied to connector contacts. Surfaces of plated tin layer are covered with an oxide film that results in high contact resistance. However, it is possible to obtain low contact resistance by using high contact load. Current downsizing trends often make it difficult to obtain high contact loads. Therefore, it is important to conduct basic studies of the contacts resistance characteristics under low contact load conditions. In this study, relationships between contact resistance and the changes of contact traces were examined. When a platinum (Pt) hemisphere contacted to tin plated flat coupon, it was found that the hemisphere surface sank into the softer tin plated flat surface during loading resulting in a piling up tin crystal grains along the periphery of the contact trace. During this process, sudden decrease in contact resistance was observed. To clarify the phenomenon, morphology changes of contact traces were observed by AFM, SEM and EBSD. FEM analysis was also used to analyze the mechanical stress distribution in the tin plated layer. Due to the peculiar distribution of stress, the crystal grains are separated and push out the contact area. This phenomenon is very different from commonly observed decrease in contact resistance due to elastic and plastic deformation inducing mechanical fracture of the surface oxide film.

To improve the observability during the post-silicon validation, it is the key to select the limited trace signals effectively for the data acquisition. This paper proposes an automated trace signal selection algorithm, which uses the pruning-based strategy to reduce the exploration space. First, the restoration range is covered for each candidate signals. Second, the constraints are generated based on the conjunctive normal form (CNF) to avoid the conflict. Finally the candidates are selected through pruning-based enumeration. The experimental results indicate that the proposed algorithm can bring higher restoration ratios and is more effective compared to existing methods.

In this work we propose a novel smart card based privacy-protecting authentication scheme for roaming services. Our proposal achieves so-called Class 2 privacy protection, i.e., no information identifying a roaming user and also linking the user's behaviors is not revealed in a visited network. It can be used to overcome the inherent structural flaws of smart card based anonymous authentication schemes issued recently. As shown in our analysis, our scheme is computationally efficient for a mobile user.

The Viterbi algorithm is widely used for decoding of the convolutional codes. The trace-back method is preferable to the register exchange method because of lower power consumption especially for convolutional codes with many states. A drawback of the conventional trace-back is that it generally requires long latency to obtain the decoded data. In this paper, a method of the trace-back with source states instead of decision bits is proposed which reduces the number of memory accesses. The dedicated memory is also presented which supports the proposed trace-back method. The reduced memory accesses result in smaller power consumption and a shorer decode latency than the conventional method.

Feature location is to identify source code that implements a given feature. It is essential for software maintenance and evolution. A large amount of research, including static analysis, dynamic analysis and the hybrid approaches, has been done on the feature location problems. The existing approaches either need plenty of scenarios or rely on domain experts heavily. This paper proposes a new approach to locate functional feature in source code by combining the change impact analysis and information retrieval. In this approach, the source code is instrumented and executed using a single scenario to obtain the execution trace. The execution trace is extended according to the control flow to cover all the potentially relevant classes. The classes are ranked by trace-based impact analysis and information retrieval. The ranking analysis takes advantages of the semantics and structural characteristics of source code. The identified results are of higher precision than the individual approaches. Finally, two open source cases have been studied and the efficiency of the proposed approach is verified.

Traceable ring signatures, proposed at PKC'07, are a variant of ring signatures, which allow a signer to anonymously sign a message with a tag behind a ring, i.e., a group of users chosen by the signer, unless he signs two messages with the same tag. However, if a signer signs twice on the same tag, the two signatures will be linked and the identity of the signer will be revealed when the two signed messages are different. Traceable ring signatures can be applied to anonymous write-in voting without any special voting authority and electronic coupon services. The previous traceable ring signature scheme relies on random oracles at its security and the signature size is linear in the number of ring members. This paper proposes the first secure traceable ring signature schemes without random oracles in the common reference string model. In addition, the proposed schemes have a signature size of O(), where N is the number of users in the ring.

Current trends in modern out-of-order processors involve implementing deeper pipelines and a large instruction window to achieve high performance, which lead to the penalty of the branch misprediction recovery being a critical factor in overall processor performance. Multi path execution is proposed to reduce this penalty by executing both paths following a branch, simultaneously. However, there are some drawbacks in this mechanism, such as design complexity caused by processing both paths after a branch and performance degradation due to hardware resource competition between two paths. In this paper, we propose a new recovery mechanism, called Recovery Critical Misprediction (RCM), to reduce the penalty of branch misprediction recovery. The mechanism uses a small trace cache to save the decoded instructions from the alternative path following a branch. Then, during the subsequent predictions, the trace cache is accessed. If there is a hit, the processor forks the second path of this branch at the renamed stage so that the design complexity in the fetch stage and decode stage is alleviated. The most contribution of this paper is that our proposed mechanism employs critical path prediction to identify the branches that will be most harmful if mispredicted. Only the critical branch can save its alternative path into the trace cache, which not only increases the usefulness of a limited size of trace cache but also avoids the performance degradation caused by the forked non-critical branch. Experimental results employing SPECint 2000 benchmark show that a processor with our proposed RCM improves IPC value by 10.05% compared with a conventional processor.