Arbiter-based Physically Unclonable Functions (APUFs) utilize the variability in manufacturing to create distinct digital identifiers for integrated circuits (ICs). Essentially, the input-output functions / truth-tables / full set of "responses" to "challenges", serve as potential hardware security primitives. To fulfill this role, every APUF batch from the same design should exhibit specific features; two of the most important are the response bias and uniqueness. A faulty APUF batch with a μ-fault from the design phase fails to achieve desired uniqueness levels and sometimes exhibits undesired response bias as well, hence is unqualified for security purposes. Instead of discarding such faulty APUFs and re-designing, we present a novel method to salvage a faulty APUF batch with the presence of multiple μ-faults, so that the desired uniqueness and bias are restored. This is done by carefully selecting challenges that can mitigate the impact of the faults. Such a salvaging strategy via challenge selection is intrinsically difficult, due to the enormous size of the challenge set, the black-box nature of APUFs, and the need to perform such tasks efficiently. To overcome these problems, we propose a simple yet effective way to estimate the intensity of the multiple faults and use them to guide the challenge selection process. The proposed method can efficiently find large challenge sets that achieve the desired response bias and uniqueness, thus salvaging a faulty APUF batch in the post-production phase.

Arbiter Physically Unclonable Functions (APUFs) are low-cost hardware security primitives that may serve as unique digital fingerprints for ICs. To fulfill this role, it is critical for manufacturers to ensure that a batch of PUFs coming off the same design and production line have different truth tables, and uniqueness / inter-PUF-distance metrics have been defined to measure this. This paper points out that a widely-used uniqueness metric fails to capture some special cases, which we remedy by proposing a modified uniqueness metric. We then look at two fundamental APUF-native production line fault models that severely affect uniqueness: the$\mu$(abnormal mean of a delay difference element) and (abnormal variance of a delay difference element) faults. We propose test and diagnosis methods aimed at these two APUF production line faults, and show that these low-cost techniques can efficiently and effectively detect such faults, and pinpoint the element of abnormality, without the (costly) need to directly measure the uniqueness metric of a PUF batch.

Modeling attacks, in which an adversary uses machine learning techniques to model a hardware-based Physically Unclonable Function (PUF) pose a great threat to the viability of these hardware security primitives. In most modeling attacks, a random subset of challenge-response-pairs (CRPs) are used as the labeled data for the machine learning algorithm. Here, for the arbiter-PUF, a delay based PUF which may be viewed as a linear threshold function with random weights (due to manufacturing imperfections), we investigate the role of active learning in Support Vector Machine (SVM) learning. We focus on challenge selection to help SVM algorithm learn “fast” and learn “slow”. Our methods construct challenges rather than relying on a sample pool of challenges as in prior work. Using active learning to learn “fast” (less CRPs revealed, higher accuracies) may help manufacturers learn the manufactured PUFs more efficiently, or may form a more powerful attack when the attacker may query the PUF for CRPs at will. Using active learning to select challenges from which learning is “slow” (low accuracy despite a large number of revealed CRPs) may provide a basis for slowing down attackers who are limited to overhearing CRPs.

Arbiter Physically Unclonable Functions (APUFs) are hardware security primitives that exploit manufacturing random-ness to generate unique digital fingerprints for ICs. This paper theoretically and numerically examines the impact of faults native to APUFs - mask parameter faults from the design phase, or process variation (PV) during the manufacturing phase. We model them statistically, and explain quantitatively how these faults affect the resulting APUF bias and uniqueness. On a single APUF instance, these faults manifest as some outlier delta elements in magnitude, thus we focus on such abnormal delta elements when addressing APUF faults. To detect such bad APUF instances and diagnose the abnormal delta elements, we propose a testing methodology which partitions a random set of challenges so that a specific delta element can be targeted, forming a perceivable bias in the responses over these sets. This low-cost approach is highly effective in detecting and diagnosing bad APUFs with abnormal delta element(s).

This paper presents a reconfigurable Many-processor Array utilizing a layer of Routers with localized interconnects to provide fault tolerance for Processing Elements (PEs). In such a system, each PE is assigned to a Router in the neighborhood. The required interconnect topology among the PE's is implemented via a fixed Backbone Network connecting all the Routers. A localized Auxiliary Network is used to provide assignment flexibilities between each Router and its peripheral PE's. Faulty PE's are repaired via spare PE's in the array, and to extend the reach of spares, repair is done via Replacement Chains: a faulty PE's Router will be assigned to another functional PE within its neighborhood; the Router of the replacement PE will then be reassigned to another PE, until eventually a spare PE is reached. In this paper, we propose a Many-processor Array on the basis of this principle, and show that this architecture is able to deliver high level of fault tolerance properties while being scalable in hardware and interconnect overheads.

Globalization of the semiconductor industry has raised serious concerns about trustworthy hardware. Particularly, an untrusted manufacturer can steal the information of a design (Reverse Engineering), and/or produce extra chips illegally (IC Piracy). Among many candidates that address these attacks, Design Withholding techniques work by replacing a part of the design with a reconfigurable block on chip, so that none of the manufactured chips will function properly until they are activated in a trusted facility, where the withheld function is restored back into the reconfigurable block on chip. However, most existing approaches are ad-hoc based, and are facing two major challenges: 1) susceptibility to a category of algorithmic attacks, from attackers in a strong position, such as a manufacturer; and 2) scaling up the defense level is checkmated by the explosion of hardware cost that has to be paid at the designer's side. In this paper, we propose a novel protection scheme, called Entanglement, which can substantially strengthen the Design Withholding framework: 1) the algorithmic attacks are prevented by forcing the attacker to solve a huge number of problems of high computational complexity; 2) the attack cost (in terms of computational complexity) is quantitatively controllable at the designer's end, with low hardware overhead: while the cost of attack can be increased exponentially, the hardware overhead imposed on the designer's side grows only linearly. The proposed work distinguishes itself from the previous works by not relying on the difficulty of finding the solution for some NP-Complete/NP-Hard problems, but rather, on the exponentially boosted number of such problems that an attacker has to solve, while carefully maintaining the growth of the hardware overhead to be scalable via Entanglement.

This paper presents the necessary and sufficient conditions for a system with n functioning Processing Elements (PE's), k spare PE's, to be k-fault tolerant (k-FT). A repair is carried out by a "replacement chain" of PE's, starting with a spare, each taking over the task of the next one, to eventually reaching a faulty PE. In this paper, a Task-PE relationship model is proposed, based on which a "replacement chain algebra" can be formulated. This makes it possible to calculate precisely how a repair will affect all the other potential repairs in the future, and to determine whether the system remains repairable for subsequent faults. In the end, two equivalent conditions (both necessary and suficient) are presented and proven in this paper to make a system guaranteed k-FT, supporting on-the-fly repair after every fault occurrence.

Nanoelectronics are inherently defect prone, and defect-tolerant logic implementation has emerged as a new foundation to form reliable systems. Crossbar-based architectures have been shown to be promising in future nanoelectronic systems, with most of the existing defect tolerance approaches based on logic mapping. Essentially, mapping-based schemes exploit the freedom of choosing which variables/products (in a logic function) to map to which of the vertical/horizontal wires (in a crossbar). In this paper, we expand the realm of defecting tolerant logic implementation by introducing two approaches orthogonal to mapping-based schemes, namely, logic morphing and fine-grained fine-tuned logic hardening. Logic morphing exploits the various equivalent forms of a logic function to tolerate defects, while calculated logic hardening adds redundancies to make the hardened logic function inherently defect tolerable. A new integrated framework is proposed to utilize the two new schemes while not sacrificing existing mapping-based techniques. The algorithms in the framework can efficiently search for a successful logic implementation in the combined solution space. Simulation results show that the proposed integrated framework boost defect tolerance capability significantly with 2-10 yield improvement, while adding no runtime overhead on top of the basic mapping algorithm.

Crossbar-based architectures are promising for the future nanoelectronic systems. However, due to the inherent unreliability of nanoscale devices, the implementation of any logic functions relies on aggressive defect-tolerant schemes applied at the post-manufacturing stage. Most of such defect-tolerant approaches explore mapping choices between logic variables/products and crossbar vertical/horizontal wires. In this paper, we develop a new approach, namely fine-grained logic hardening, based on the idea of adding redundancies into a logic function so as to boost the success rate of logic implementation. We propose an analytical framework to evaluate and fine-tune the amount and location of redundancy to be added for a given logic function. Furthermore, we devise a method to optimally harden the logic function so as to maximize the defect tolerance capability. Simulation results show that the proposed logic hardening scheme boosts defect tolerance capability significantly in yield improvement, compared to mapping-only schemes with the same amount of hardware cost.

The transition to Nano-scale devices is expected to open the way for highly complex parallel systems. However, decreased reliability and strict interconnect limitations are two important challenges that the devices need to overcome. To do so, such systems have to adapt to the changing workload and faults, employing decentralized protocols to coordinate among the many components. In this paper, we investigate algorithms for evenly distributing resources among locally connected components, so that the system can dynamically self-balance as the availability of resources changes. We propose two efficient Decentralized Protocols that achieve near-optimal resource distributions. The protocols are scalable and guarantee the desired fair distribution regardless of the interconnect topology.

Crossbar-based architectures are promising for the future nanoelectronic systems. However, due to the inherent unreliability, defect tolerance schemes are necessary to guarantee the successful implementations of any logic functions. Most of the existing approaches have been based on logic mapping, which exploits the freedom of choosing which variables/products (in a logic function) to map to which of the vertical/horizontal wires (in a crossbar). In this paper, we propose a new defect tolerance approach, namely logic morphing, by exploiting the various equivalent forms of a logic function. This approach explores a new dimension of freedom in achieving defect tolerance, and is compatible with the existing mapping-based approaches. We propose an integrated algorithmic framework, which employs both mapping and morphing simultaneously, and efficiently searches for a successful logic implementation in the combined solution space. Simulation results show that the proposed scheme boosts defect tolerance capability significantly with many-fold yield improvement, while having no extra runtime over the existing approach of performing mapping alone.

Crossbar-based architectures are promising for the future nanoelectronic systems. Due to the inherent unreliability of nanotechnology, logic mapping onto highly defective crossbars needs to be performed on every chip. This posts significant challenge as the mapping problem is NP-complete. The complexity of the defect-tolerant logic mapping problems makes it hard to analyze runtime and model yield. This paper presents a new metric for evaluating the quality of the defect-tolerant logic mapping by tagging each mapping trial with a “score”, namely the mismatch number. Specifically, we look into the mismatch number distribution over: 1) crossbars having the same defect rate, 2) crossbars having the same defect number, and 3) a single crossbar with a given defect pattern. We show that the number of mismatches can be well modeled in probabilistic approaches, and the mismatch number distribution follows Normal/Poisson and Hypergeometric distribution, respectively. This new metric serves as the basis of performing runtime and yield analysis, which are difficult to estimate for logic mapping onto nanocrossbars. More importantly, the quantitative score for each underlying mapping trial serves as the basis in building the reliable nanocrossbar systems.

Future nanoelectronics based arithmetic components will enjoy abundant hardware, yet at the same time confront severe unreliability challenges. We focus on the fault tolerance of high performance parallel prefix adders (PPA), and exploit the inherent redundancy in PPAs to develop efficient fault tolerance approaches. We show that the internal invariant inherent in the parallel prefix adders provides support for online fault detection and fault masking. Furthermore, based on the particular regular structure of PPAs, an online diagnosis scheme can be developed, thus enabling the application of reconfigurability of nanoelectronics for the highly flexible online repair approaches. In contrast to traditional fault tolerance techniques that rely solely on significant external overhead, the proposed approach opens up a new genre of efficient fault tolerance techniques for arithmetic components in the nanoelectronic environment.

A regular structure and capability to implement arbitrary logic functions in a two-level logic form have placed crossbar-based programmable logic arrays (PLAs) as promising implementation architectures in the emerging nanoelectronics environment. Yet reliability constitutes an important concern in the nanoelectronics environment, necessitating a thorough investigation and its effective augmentation for crossbar-based PLAs. We investigate in this paper fault masking for crossbar-based nanoelectronics PLAs. Missing nanoelectronics devices at the crosspoints have been observed as a major source of faults in nanoelectronics crossbars. Based on this observation, we present a class of fault masking approaches exploiting logic tautology in two-level PLAs. The proposed approaches enhance the reliability of nanoelectronics PLAs significantly at low hardware cost

Programmable logic arrays (PLA), which can implement arbitrary logic functions in a two-level logic form, are promising as platforms for nanoelectronic logic due to their highly regular structure compatible with the nano crossbar architectures. Reliability is an important challenge as far as nanoelectronic devices are concerned. Consequently, it is necessary to focus on the fault tolerance aspects of nanoelectronic PLAs to ensure their viability as a foundation for nanoelectronic systems. In this paper, we investigate two types of fault tolerance techniques for nanoelectronic device based PLAs, focusing at the online faults occurring at the cross-points of nano devices. We develop a scheme to precisely locate the faults online, as this is a crucial step for efficient online reconfiguration based fault tolerance schemes. We also propose a tautology based fault masking scheme. We demonstrate that these two types of fault tolerance schemes developed for nano PLAs significantly improve at low hardware cost the reliability of the high fault occurrence nanoelectronic environment.

Highly regular, nanodevice based architectures have been proposed to replace pure CMOS based architectures in the emerging post CMOS era. Since bottom-up self-assembly is used to build these architectures, regular nanowire crossbars are emerging as a promising candidate. While these regular structures resemble CMOS programmable logic arrays (PLAs), PLA logic synthesis methodologies fail to solve the associated problems since the length and connectivity constraints imposed by individual nanowires in these crossbars translate into challenges hitherto not considered. These strict topological constraints should be considered while mapping Boolean functions onto nanowire crossbars during logic synthesis. We develop a mathematical model for this problem, an algorithm to solve it and three heuristics to improve the algorithm runtime.

Online repair through reconfiguration is a particularly advantageous approach in the nanoelectronic environment since reconfigurability is naturally supported by the devices. However, precise identification of faulty locations is of critical importance for fine-grain repairs. A CLA is mainly composed of: (1) carry generation blocks and (2) g,p signal generation blocks. In this paper we propose two schemes for fault identification in these two parts correspondingly. For carry generation blocks, an inherently redundant computation path is exploited to identify the faulty block with high precision. As a time redundancy approach, recomputation with rotated operands (RERO) has been utilized in online fault detection for CLA’s [13]. For g,p generation blocks, we exploit the RERO scheme to achieve precise fault identification. A comprehensive analysis is provided for the aliasing in the proposed fault identification approach. It is shown that both the amount of repair hardware overhead and the fault coverage loss for the proposed scheme are very low. Overall, the proposed scheme can perform fast and precise identification of faults in the CLA components with low area overhead, thus facilitating the development of powerful and efficient fault tolerance schemes through online repair for nanoelectronic systems

Emerging nanoelectronics are expected to have very high manufacture-time defect rates and operation-time fault rates. Traditional N-modular redundancy (NMR) exploits the large device densities offered by these nanoelectronics to tolerate these high fault rates by allocating redundant resources according to the worst case fault rates. However, this approach is inflexible when the fault rates are time varying. In this paper, we propose a dynamically adaptive NMR approach by developing: (i) a genre of nanofabric topologies that supports sharing of redundancies in the NMR approach so as to adapt to the time varying fault rates and (ii) reconfiguration algorithms for these topologies to deal with fault tolerance loss caused by manufacturing defects and operation-time online faults, respectively. Simulation results verify that the ability to construct reliable systems, possibly the paramount consideration in constructing working applications in nanoelectronics, is significantly improved with the proposed flexible NMR architecture and the reconfiguration algorithms.

In this paper we propose a fault-tolerant processor architecture and an associated fault-tolerant computation model capable of fault tolerance in the nanoelectronic environment that is characterized by high and time varying fault rates. The proposed fault tolerant processor architecture not only guarantees the correctness of computation but also is flexible in that it dynamically trades-off computation resources and performance. The core of the architecture is a decentralized instruction control unit called the voter that achieves both fault tolerance and the maximum parallel execution of instructions by exploiting the abundant computational resources provided by nanotechnologies. Although the result of each instruction needs to be confirmed by executing it on multiple computation units, multiple unconfirmed instructions can proceed as speculative branches. The voter implements a hardware-frugal computation unit allocation algorithm to organize the redundant computations and to dynamically control the growth of speculative branches.

Nanoelectronic devices are expected to have extremely high and variable fault rates; thus future processor architectures based on these unreliable devices need to be built with fault tolerance embedded so as to satisfy the fundamental requirement of computational correctness. In this paper an architectural-level computation model is proposed for fault tolerant computations in nanoelectronic processors. The proposed scheme is capable of guaranteeing the correctness of each instruction through exploitation of both hardware and time redundancy, even under high and variable fault rates. Each instruction is confirmed by multiple computation instances. Through a speculative execution based on unconfirmed results, the proposed scheme eliminates the severe performance deterioration typically caused by time redundancy approaches on data dependent instructions. To avoid the exponential growth of resource allocation introduced by the hardware redundancy approaches on the speculations, a hardware allocation framework is developed in the proposed scheme to control the growth of hardware resources while preserving the low latency achieved through the speculative executions. We set up an experimental framework to validate the effectiveness of the proposed scheme as well as to investigate multiple tradeoff points within the proposed approach. Experimental data further confirm that the proposed approach achieves the goal of providing fault tolerance in the pipelined nanoelectronic processors, while at the same time providing high system performance and efficient utilization of hardware resources.

In This work we investigate an effective approach to construct a linear decompression network in the multiple scan chain architecture. A minimal pin architecture, complemented by negligible hardware overhead, is constructed by mathematically analysing test data relationships, delivering in turn drastic test reductions. The proposed network drives a large number of internal scan chains with a short input vector, thus allowing significant reductions in both test time and test volume. The proposed method constructs an inverter-interconnect based network by exploring the pairwise linear dependencies of the internal scan chain vectors, resulting in a very low cost network that is nonetheless capable of outperforming much costlier compression schemes. We propose an iterative algorithm to construct the network from an initial set of test cubes. The experimental data shows significant reductions in test time and test volume with no loss of fault coverage.

Several emerging nanotechnologies have been displaying the negative differential resistance (NDR) characteristic, which makes them naturally support multi-valued logic with a large number of logic states. Such multi-valued logic with a large number of logic states can support a native digit-level redundant number system and hence a native digit-level carry save arithmetic. We present a new approach to linear block code based fault-tolerant arithmetic in NDR nanotechnologies. Specifically, we show how linear block codes can be used for error checking and error correction in carry save arithmetic operations. The proposed approach significantly improves timing and fault-tolerance of arithmetic operations in the highly unreliable nanoelectronic environment. Since digit-level information redundancy via linear block codes is widely used for fault tolerant communications and storage systems, the proposed scheme also unifies the fault tolerance approaches across arithmetic, interconnection and storage subsystems.

We propose in this paper an extension on the Scan Chain Concealment technique to further reduce test time and volume requirement. The proposed methodology stems from the architecture of the existing SCC scheme, while it attempts to overlap consecutive test vector seeds, thus providing increased flexibility in exploiting effectively the large volume of don't-care bits in test vectors. We also introduce modified ATPG algorithms upon the previous SCC scheme and explore various implementation strategies. Experimental data exhibit significant reductions on test time and volume over all current test compression techniques.