With aggressive device scaling, timing failures have become more prevalent due to manufacturing defects and process variations. When timing failure occurs, it is important to take corrective actions immediately. Therefore, an efficient and fast diagnosis method is essential. In this paper, we propose a new diagnostic method using timing information. Our method approximately estimates all the segment delays of measured paths in a design, using inequality-constrained least squares methods. Then, the proposed method ranks the possible locations of delay defects based on the difference between estimated segment delays and the expected values of segment delays. The method works well for multiple delay defects as well as single delay defects. Experiment results show that our method yields good diagnostic resolution. With the proposed method, the average first hit rank (FHR), was within 7 for single delay defect and within 8 for multiple delay defects.

A practical model-checking (MC) approach for fault analysis, that is one of the most cost-effective tasks in software development, is proposed. The proposed approach is based on a technique, named “Program-oriented Modeling” (POM) for extracting a model from source code. The framework of model extraction by POM provides configurable abstraction based on user-defined transformation rules, and it supports trial-and-error model extraction. An environment for MC called POM/MC was also built. POM/MC analyzes C source code to extract Promela models used for the SPIN model checker. It was applied to an industrial software system to evaluate the efficiency of the configurable model extraction by POM for fault analysis. Moreover, it was shown that the proposed MC approach can reduce the effort involved in analyzing software faults by MC.

Fault localization is essential for conducting effective program repair. However, preliminary studies have shown that existing fault localization approaches do not take the requirements of automatic repair into account, and therefore restrict the repair performance. To address this issue, this paper presents the first study on designing fault localization approaches for automatic program repair, that is, we propose a fault localization approach using failure-related contexts in order to improve automatic program repair. The proposed approach first utilizes program slicing technique to construct a failure-related context, then evaluates the suspiciousness of each element in this context, and finally transfers the result of evaluation to automatic program repair techniques for performing repair on faulty programs. The experimental results demonstrate that the proposed approach is effective to improve automatic repair performance.

This paper presents a novel architecture for a fault-tolerant and dual modular redundancy (DMR) system using a checkpoint recovery approach. The architecture features exploitation of SRAM with simultaneous copy and instantaneous compare function. It can perform low-latency data copying between dual cores. Therefore, it can carry out fast backup and rollback. Furthermore, it can reduce the power consumption during data comparison process compared to the cyclic redundancy check (CRC). Evaluation results show that, compared with the conventional checkpoint/restart DMR, the proposed architecture reduces the cycle overhead by 97.8% and achieves a 3.28% low-latency execution cycle even if a one-time fault occurs when executing the task. The proposed architecture provides high reliability for systems with a real-time requirement.

In this paper, we propose fault-tolerant field-programmable gate array (FPGA) architectures and their design framework for intellectual property (IP) cores in system-on-chip (SoC). Unlike discrete FPGAs, in which the integration scale can be made relatively large, programmable IP cores must correspond to arrays of various sizes. The key features of our architectures are a regular tile structure, spare modules and bypass wires for fault avoidance, and a configuration mechanism for single-cycle reconfiguration. In addition, we utilize routing tools, namely EasyRouter for proposed architecture. This tool can handle various array sizes corresponding to developed programmable IP cores. In this evaluation, we compared the performances of conventional FPGAs and the proposed fault-tolerant FPGA architectures. On average, our architectures have less than 1.82 times the area and 1.11 times the delay compared with traditional island-style FPGAs. At the same time, our FPGA shows a higher fault tolerant performance.

This paper presents an efficient method for differential fault analysis (DFA) on substitution-permutation network (SPN)-based block ciphers. A combination of a permutation cancellation and an algebraic key filtering technique makes it possible to reduce the computational cost of key filtering significantly and therefore perform DFAs with new fault models injected at an earlier round, which defeats conventional countermeasures duplicating or recalculating the rounds of interest. In this paper, we apply the proposed DFA to the LED block cipher. Whereas existing DFAs employ fault models injected at the 30th round, the proposed DFA first employs a fault model injected at the 29th round. We demonstrate that the proposed DFA can obtain the key candidates with only one pair of correct and faulty ciphertexts in about 2.1h even from the 29th round fault model and the resulting key space is reduced to 24.04

This paper proposes a multiple-fault injection attack based on adaptive control of fault injection timing in embedded microcontrollers. The proposed method can be conducted under the black-box condition that the detailed cryptographic software running on the target device is not known to attackers. In addition, the proposed method is non-invasive, without the depackaging required in previous works, since such adaptive fault injection is performed by precisely generating a clock glitch. We first describe the proposed method which injects two kinds of faults to obtain a faulty output available for differential fault analysis while avoiding a conditional branch in a typical recalculation-based countermeasure. We then show that the faulty output can be obtained by the proposed method without using information from the detailed instruction sequence. In particular, the validity of the proposed method is demonstrated through experiments on Advanced Encryption Standard (AES) software with a recalculation-based countermeasure on 8-bit and 32-bit microcontrollers. We also present a countermeasure resistant to the proposed method.

A method of round addition attack on substitution-permutation network (SPN) block ciphers using differential fault analysis (DFA) is presented. For the 128-bit advanced encryption standard (AES), we show that secret keys can be extracted using one correct ciphertext and two faulty ciphertexts. Furthermore, we evaluate the success rate of a round addition DFA attack, experimentally. The proposed method can also be applied to lightweight SPN block cipher such as KLEIN and LED.

With IC design entering the nanometer scale integration, the reliability of VLSI has declined due to small-delay defects, which are hard to detect by traditional delay fault testing. To detect small-delay defects, on-chip delay measurement, which measures the delay time of paths in the circuit under test (CUT), was proposed. However, our pre-simulation results show that when using on-chip delay measurement method to detect small-delay defects, test generation under the single-path sensitization is required. This constraint makes the fault coverage very low. To improve fault coverage, this paper introduces techniques which use segmented scan and test point insertion (TPI). Evaluation results indicate that we can get an acceptable fault coverage, by combining these techniques for launch off shift (LOS) testing under the single-path sensitization condition. Specifically, fault coverage is improved 27.02∼47.74% with 6.33∼12.35% of hardware overhead.

The applicability of at-speed scan-based logic built-in self-test (BIST) is being severely challenged by excessive capture power that may cause erroneous test responses even for good circuits. Different from conventional low-power BIST, this paper is the first to explicitly focus on achieving capture power safety with a novel and practical scheme, called capture-power-safe logic BIST (CPS-LBIST). The basic idea is to identify all possibly-erroneous test responses caused by excessive capture power and use the well-known approach of masking (bit-masking, slice-masking,vector-masking) to block them from reaching the multiple-input signature register(MISR). Experiments with large benchmark circuits and a large industrial circuit demonstrate that CPS-LBIST can achieve capture power safety with negligible impact on test quality and circuit overhead.

An efficient subcarrier allocation scheme of a supporting cell is proposed to recover the communication of faulty cell users in an OFDM-based wireless system. With the proposed subcarrier allocation scheme, the number of subcarriers allocated to faulty cell users is maximized while the average throughput of supporting cell users is maintained at a desired level. To find the maximum number of subcarriers allocated to faulty cell users, the average throughput of the subcarrier with the k-th smallest channel gain in a subcarrier group is derived by an inductive method. It is shown by simulation that the proposed subcarrier allocation scheme can provide more subcarriers to faulty cell users than the random selection subcarrier allocation scheme.

Runtime analysis is to enhance the safety of critical systems by monitoring the change of corresponding external environments. In this paper, a modified FTA approach, making full utilization of the existing safety analysis result, is put forward to achieve runtime safety analysis. The procedures of the approach are given in detail. This approach could be widely used in safety engineering of critical systems.

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.

Fault tolerant methods using dynamically reconfigurable devices have been studied to overcome wear-out failures. However, quantitative comparisons have not been sufficiently assessed on device lifetime enhancement with these methods, whereas they have mainly been evaluated individually from various viewpoints such as additional hardware overheads, performance, and downtime for fault recovery. This paper presents quantitative lifetime evaluations performed by simulating the fault-avoidance procedures of five representative methods under the same conditions in wear-out scenarios, applications, and device architecture. The simulation results indicated that improvements of up to 70% mean-time-to-failure (MTTF) in comparison with ideal fault avoidance could be achieved by using methods of fault avoidance with ‘row direction shift’ and ‘dynamic partial reconfiguration’. ‘Column shift’, on the other hand, attained a high degree of stability with moderate improvements in MTTF. The experimental results also revealed that spare basic elements (BEs) should be prevented from aging so that improvements in MTTF would not be adversely affected. Moreover, we found that the selection of initial mappings guided by wire utilization could increase the lifetimes of partial reconfiguration based fault avoidance.

An n-dimensional folded hypercube, denoted by FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 2n-3 for n ≥ 5.

At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.

Existing fault localization approaches usually do not provide a context for developers to understand the problem. Thus, this paper proposes a novel approach using the dynamic backward slicing technique to enrich contexts for existing approaches. Our empirical results show that our approach significantly outperforms five state-of-the-art fault localization techniques.

Recently, the wavelet-based estimation method has gradually been becoming popular as a new tool for software reliability assessment. The wavelet transform possesses both spatial and temporal resolution which makes the wavelet-based estimation method powerful in extracting necessary information from observed software fault data, in global and local points of view at the same time. This enables us to estimate the software reliability measures in higher accuracy. However, in the existing works, only the point estimation of the wavelet-based approach was focused, where the underlying stochastic process to describe the software-fault detection phenomena was modeled by a non-homogeneous Poisson process. In this paper, we propose an interval estimation method for the wavelet-based approach, aiming at taking account of uncertainty which was left out of consideration in point estimation. More specifically, we employ the simulation-based bootstrap method, and derive the confidence intervals of software reliability measures such as the software intensity function and the expected cumulative number of software faults. To this end, we extend the well-known thinning algorithm for the purpose of generating multiple sample data from one set of software-fault count data. The results of numerical analysis with real software fault data make it clear that, our proposal is a decision support method which enables the practitioners to do flexible decision making in software development project management.

We propose a lightweight scheme for fault diagnosis in time-triggered (TT) systems. An existing scheme is preferable in its capability but incurs computation time that can be prohibitively large for some real-time systems, such as automotive control systems. Our proposed scheme, which we call voting sharing, can substantially reduce the computation time by sharing the diagnosis result obtained by each node with all nodes in the system. We clarify the properties of the voting sharing scheme with respect to fault tolerance and show some experimental results.

We propose a fast and resource-efficient agreement protocol on a request set, which is used to realize Byzantine fault tolerant server replication. Although most existing randomized protocols for Byzantine agreement exploit a modular approach, that is, a combination of agreement on a bit value and a reduction of request set values to the bit values, our protocol directly solves the multi-valued agreement problem for request sets. We introduce a novel coin tossing scheme to select a candidate of an agreed request set randomly. This coin toss allows our protocol to reduce resource consumption and to attain faster response time than the existing representative protocols.