In this paper, we demonstrate the first successful extraction of the encryption key from the hardware AES accelerator in the nRF52832 Bluetooth Low Energy system-on-chip operating in Counter with CBC-MAC (CCM) mode using side-channel information recovered from RF signals. This attack marks a significant milestone, as previous attempts to break this accelerator were unsuccessful. Our results provide a critical insight into the proprietary hardware AES-CCM accelerator in the nRF52832, paving the way for future enhancements to its resistance to side-channel attacks. All the related data are made available to the research community to promote further analysis.

At present, the state-of-the-art cloud FPGA deployment process does not allow the cloud provider to perform design checks for malicious circuits unless the clients' designs are available in an unprotected form. In this paper, we introduce the circuit disguise method that allows the design checks to be performed without disclosing the clients' Intellectual Property (IP). The method is based on a lossy circuit transformation that generates a compressed version of the netlist specifying the client's design. While the design checks can still be performed on the compressed version of the netlist, reversing the transformation to recover the original design is not possible. The circuit disguise method can be used in combination with bitstream encryption. This enables the clients to protect not only the designs but also the bitstreams. Furthermore, with circuit disguise, new design checks can be performed on designs that are already compiled into a protected bitstream. We present an implementation of the circuit disguise method and demonstrate its effectiveness with various benign and malicious benchmark designs. The implementation is publicly available.

Module Lattice Digital Signature Algorithm (MLDSA) is a post-quantum digital signature algorithm currently being standardised by the NIST. Devices making use of MLDSA are expected to soon become generally available in various environments. It is thus important to assess the resistance of ML-DSA implementations to physical attacks. This paper presents a fault injection attack on hedged ML-DSA in ARM Cortex-M4. First, voltage glitching is performed to skip computation of a seed during the generation of the signature. We identified settings that allowed us to consistently skip the necessary function without crashing the device. After the fault injection, the secret key vector $s_{1}$ is derived directly from the resulting faulty signature. The attack succeeds in recovering s1from a single trace with a probability of around $53 \%$. We also propose countermeasures against the presented attack.

CRYSTALS-Kyber has been recently selected by the NIST as a new public-key encryption and key-establishment algorithm to be standardized. This makes it important to assess how well CRYSTALS-Kyber implementations withstand side-channel attacks. Software implementations of CRYSTALS-Kyber have already been analyzed and the discovered vulnerabilities were patched in the subsequently released versions. In this paper, we present a profiling side-channel attack on a hardware implementation of CRYSTALS-Kyber. Since hardware implementations carry out computations in parallel, they are typically more difficult to break than their software counterparts. We demonstrate a successful message (session key) recovery attack on a Xilinx Artix-7 FPGA implementation of CRYSTALS-Kyber by deep learning-based power analysis. Our results indicate that currently available hardware implementations of CRYSTALS-Kyber need better protection against side-channel attacks.

Deep learning transformed side-channel analysis and made many conventional countermeasures obsolete. This brings the need for more effective, deep learning-resistant defense mechanisms. We propose a method for protecting hardware implementations of cryptographic algorithms that combines clock randomization with duplication. The presented method ensures that the duplicated block generates algorithmic noise that is dependent on the input of the primary block and has a similar power profile. In addition, the duplicated block does not create any secret key-related leakage. We evaluate the presented method on the example of the Advanced Encryption Standard (AES) algorithm implemented in FPGA. Our experimental results show that the protected AES implementation is resistant to deep learning-based power analysis.

In this paper, we present the first near-field electro-magnetic (EM) sensor that is entirely implemented in the FPGA configurable fabric, without the use of any peripherals such as analog-to-digital converters, external antennas, or resistor-capacitor circuits. The sensor detects changes in path delays caused by external EM radiation using an antenna (composed of the interconnect) and a time-to-digital converter. A cloud-based FPGA remotely configured with such a sensor may act as a receiving end of a wireless covert channel, e.g., to another FPGA in the neighborhood that does not share any common resources with the receiving FPGA. Thus, our results show the plausibility of an exploitable attack vector for cloud-based FPGA that is not limited to the multi-tenancy scenario.

In the ongoing last round of NIST's post-quantum cryptography standardization competition, side-channel analysis of finalists is a main focus of attention. While their resistance to timing, power and near field electromagnetic (EM) side-channels has been thoroughly investigated, amplitude-modulated EM emanations has not been considered so far. The attacks based on amplitude-modulated EM emanations are more stealthy because they exploit side-channels intertwined into the signal transmitted by the on-board antenna. Thus, they can be mounted on a distance from the device under attack. In this paper, we present the first results of an amplitude-modulated EM side-channel analysis of one of the NIST PQ finalists, Saber key encapsulation mechanism (KEM), implemented on the nRF52832 (ARM Cortex-M4) system-on-chip supporting Bluetooth 5. By capturing amplitude-modulated EM emanations during decapsulation, we can recover each bit of the session key with 0.91 probability on average.

We present an algorithm capable of defeating SRAM FPGA design obfuscation methods based on hardware opaque predicates. This is achieved by ensuring the full controllability of each instantiated look-up table input via iterative bitstream modifications. Unlike many previous deobfuscation approaches, the presented method does not require the possession of a netlist. It is applied directly to the FPGA bitstream. The feasibility of our approach is verified on the example of an obfuscated SNOW 3G design implemented in a Xilinx Artix-7 FPGA.

The hardware random number generator (RNG) integrated in STM32 MCUs is intended to ensure that the numbers it generates cannot be guessed with a probability higher than a random guess. The RNG is based on several ring oscillators whose outputs are combined and post-processed to produce a 32-bit random number per round of computation. In this paper, we show that it is possible to train a neural network capable of recovering the Hamming weight of these random numbers from power traces with a higher than 60% probability. This is a 4-fold improvement over the 14% probability of the most likely Hamming weight.

Today’s power/EM side-channel analysis is limited by the complexity of the target hardware. We investigate the feasibility of power/EM side-channel analysis of general-purpose computers. This paper makes a step towards this goal by analyzing memory operations of Raspberry Pi 3 Model B, a widely used general-purpose IoT device that is capable of running an operating system, and shows that it is possible to extract information about the data field of memory operations from near-field EM measurements.

SNOW 3G is one of the core algorithms for confidentiality and integrity in several 3GPP wireless communication standards, including the new Next Generation (NG) 5G. It is believed to be resistant to classical cryptanalysis. In this paper, we show that SNOW 3G can be broken by a fault attack based on bitstream modification. By changing the content of some look-up tables in the bitstream, we reduce the non-linear state updating function of SNOW 3G to a linear one. As a result, it becomes possible to recover the key from a known plaintext-ciphertext pair. To our best knowledge, this is the first successful bitstream modification attack on SNOW 3G.

In this paper, we present a bitstream modification attack on the Trivium stream cipher, an international standard under ISO/IEC 29192-3. By changing the content of three LUTs in the bitstream, we reduce the non-linear state updating function of Trivium to a linear one. This makes it possible to recover the key from 288 keystream bits using at most 219.41operations. We also propose a countermeasure against bitstream modification attacks which obfuscates the bitstream using dummy and camouflaged LUTs which look legitimate to the attacker. We present an algorithm for injecting dummy LUTs directly into the bitstream without causing any performance or power penalty.

Assuring the security of the Internet of Things (IoT) is much more challenging than assuring the security of centralized environments, like the cloud. A reason for this is that IoT devices are often deployed in domains that are remotely managed and monitored. Thus, they cannot be protected from physical attacks as reliably as data centers. Up till now, implementations of many established, standardized algorithms including AES and SNOW 3G have been broken by physical attacks. In this paper, we show that even the most recently designed algorithms are also vulnerable. We attack an SRAM-based FPGA implementation of ACORN v3 stream cipher, a finalist of CAESAR cryptographic competition for authenticated encryption. By modifying the content of several look-up tables directly in the bitstream, we inject faults which reduce the nonlinear feedback function of ACORN to a linear one. As a result, it becomes possible to extract the full key from 215.34bits of faulty keystream by an algebraic attack using 235.46operations. Our results, once again confirm the necessity to rethink the way cryptographic algorithms are implemented in FPGAs.

Message Authentication Codes (MACs) used in today's wireless communication standards may not be able to satisfy resource limitations of simpler 5G radio types and use cases such as machine type communications. As a possible solution, we present a lightweight message authentication scheme based on the cyclic redundancy check (CRC). It has been previously shown that a CRC with an irreducible generator polynomial as the key is an ϵ-almost XOR-universal (AXU) hash function with ϵ = (m + n)/2n-1, where m is the message size and n is the CRC size. While the computation of n-bit CRCs can be efficiently implemented in hardware using linear feedback shift registers, generating random degree-n irreducible polynomials is computationally expensive for large n. We propose using a product of k irreducible polynomials whose degrees sum up to n as a generator polynomial for an n-bit CRC and show that the resulting hash functions are ϵ-AXU with ϵ = (m + n)k/2n-k. The presented message authentication scheme can be seen as providing a trade-off between security and implementation efficiency.

Side-channel attacks are currently one of the most powerful attacks against implementations of cryptographic algorithms. They exploit the correlation between the physical measurements (power consumption, electromagnetic emissions, timing) taken at different points during the computation and the secret key. Some of the existing countermeasures offer a protection against one specific type of side channel only. We show that it can be a bad practice which can make exploitation of other side-channels easier. First, we perform a power analysis attack on an FPGA implementation of the Advanced Encryption Standard (AES) which is not protected against side-channel attacks and estimate the number of power traces required to extract its secret key. Then, we repeat the attack on AES implementations which are protected against fault injections by hardware redundancy and show that they can be broken with three times less power traces than the unprotected AES. We also demonstrate that the problem cannot be solved by complementing the duplicated module, as previously proposed. Our results show that there is a need for increasing knowledge about side-channel attacks and designing stronger countermeasures.

Physical unclonable functions (PUFs) are promising hardware security primitives suitable for low-cost cryptographic applications. Ring oscillator (RO) PUF is a well-received silicon PUF solution due to its ease of implementation and entropy evaluation. However, the responses of RO-PUFs are susceptible to environmental changes, in particular, to temperature variations. Additionally, a conventional RO-PUF implementation is usually more power-hungry than other PUF alternatives. This paper explores circuit-level techniques to design low-power RO-PUFs with enhanced thermal stability. We introduce a power-efficient approach based on a phase/frequency detector (PFD) to perform pairwise comparisons of ROs. We also propose a temperature compensated bulk-controlled oscillator (BCO) and investigate its feasibility and usage in PFD-based RO-PUFs. Evaluation results demonstrate that the proposed techniques can effectively reduce the thermally induced errors in PUF responses while imposing a low power overhead. The PFD-based BCO-PUF is one of the best among existing RO-PUFs in terms of power efficiency.

Binary Machines (BMs) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a nonlinear function of the previous state. It is known how to construct a BM generating a given completely specified binary sequence. In this paper, we present an algorithm which can efficiently handle the case of incompletely specified sequences. Our experimental results show that it significantly outperforms the approaches based on all-0 or random fill in both area and power dissipation. On average, it reduces dynamic power dissipation twice compared to all-0 fill approach and 6 times compared to random fill approach. The presented algorithm can potentially be useful for many applications, including Logic Built-In Self Test (LBIST).

Cryptographic methods are used to protect confidential information against unauthorised modification or disclo-sure. Cryptographic algorithms providing high assurance exist, e.g. AES. However, many open problems related to assuring security of a hardware implementation of a cryptographic algorithm remain. Security of a hardware implementation can be compromised by a random fault or a deliberate attack. The traditional testing methods are good at detecting random faults, but they do not provide adequate protection against malicious alterations of a circuit known as hardware Trojans. For example, a recent attack on Intel's Ivy Bridge processor demonstrated that the traditional Logic Built-In Self-Test (LBIST) may fail even the simple case of stuck-at fault type of Trojans. In this paper, we present a novel LBIST method for Feedback Shift Register (FSR)-based cryptographic systems which can detect such Trojans. The specific properties of FSR-based cryptographic systems allow us to reach 100% single stuck-at fault coverage with a small set of deterministic tests. The test execution time of the proposed method is at least two orders of magnitude shorter than the one of the pseudo-random pattern-based LBIST. Our results enable an efficient protection of FSR-based cryptographic systems from random and malicious stuck-at faults.

LFSR-based filter generators are used as a basic building block in many stream ciphers. Filter generators are popular because their well-defined mathematical description enables a detailed formal security analysis. In this paper, we show how to modify a filter generator into a nonlinear feedback shift register which is faster, but slightly larger, than the original filter generator. For example, the propagation delay can be reduced 1.54 times at the expense of 1.27% extra area. The presented method might be important for applications which require very high data rates, e.g. 4G mobile communication technology.

We introduce a power optimization technique for suppression countermeasures against Power Analysis attacks that can potentially be applied to any type of crypto-system implemented as a synchronous digital system. Since the power consumption of systems protected by suppression countermeasures is proportional to current peaks, we propose a simple transformation to move some of the switching activity of the crypto-system from the rising edge to the falling edge of the clock, so that current peaks are reduced. The transformation is easy to apply, requires only standard cell logic gates, has a low area overhead but can reduce the maximal working frequency of a system by at most a factor 2. We prove our method on an ASIC implementation of the Grain-80 stream cipher using SPICE-level simulation, obtaining 50% power savings compared to the non-optimized suppression countermeasure.

On-chip storage of binary sequences normally require the use of Read-Only Memories (ROMs). However, ROMs do not exploit of the fact that the stored information is accessed sequentially. This paper presents an area-efficient sequence storage technique based on state machines. Experimental results show that the presented method significantly outperforms previous approaches. The resulting state machines are on average 54% smaller than ROMs storing the same sequence.

A method for constructingn-stage Galois NLFSRs with period 2n-1 fromn-stage maximum length LFSRs is presented. Nonlinearity is introduced into state cycles by adding a nonlinear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. The effect of nonlinearity is cancelled and state cycles are joined back by adding a copy of the same function to a later stage of the register. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for largen.

In this paper we introduce a new type of Ring Oscillator PUF (RO-PUF) in which the inverters composing the ring oscillators can be supplied by independent voltages. This new RO-PUF can improve the reliability of the PUF in case of temperature variations.

Feedback Shift Register (FSR) based stream ciphers are one of the most promising new groups of cryptographic algorithms, which target applications characterized by strong power, area and cost constraints. Due to high sensibility against power analysis attacks, there is a strong need for countermeasures which increase the immunity of this class of ciphers without introducing large power and area overheads. In this paper we study analog multi-level countermeasures which can protect FSR-based stream ciphers against Differential Power Analysis (DPA) attacks, with lower power overhead compared to alternative solutions that can be found in literature. We highlight a trade-off between power consumption and security, and propose an approach which ensures at the same time low power overhead and high security against power analysis attacks.

Conventional logic synthesis flows are composed of three separate phases: technology independent optimization, technology mapping, and technology dependent optimization. A fundamental problem with such a three-phased approach is that the global logic structure is decided during the first phase without any knowledge of the actual technology parameters considered during later phases. Although technology dependent optimization algorithms perform some limited logic restructuring, they cannot recover from fundamental mistakes made during the first phase, which often results in non-satisfiable solutions. In this paper, we present a method for integrating the three synthesis phases using an annealing algorithm as optimization framework. The annealing-based search is driven by a complex objective function, combining both technology independent as well as technology dependent optimization criteria. Our experimental results shown that, on average, the presented approach can improve the area and delay of circuits optimized with script rugged of SIS by 11.2% and 32.5% respectively.

In this paper we analyze the power characteristics of Feedback Shift Registers (FSRs) and their e ect on FSR-based stream ciphers. We introduce a technique to isolate the switching activity of a stream cipher by equalizing the current drawn from the cipher with lower power overhead compared to previously introduced countermeasures. By re-implementing the Grain-80 and the Grain-128 ciphers with the presented approach, we lower their power consumption respectively by 20% and 25% compared to previously proposed countermeasures.

Binary machines are a generalization of Feedback Shift Registers (FSRs) in which both, feedback and feedforward, connections are allowed and no chain connection between the register stages is required. In this paper, we present an algorithm for synthesis of binary machines with the minimum number of stages for a given degree of parallelization. Our experimental results show that for sequences with high linear complexity such as complementary, Legendre, or truly random, parallel binary machines are an order of magnitude smaller than parallel FSRs generating the same sequence. The presented approach can potentially be of advantage for many applications including wireless communication, cryptography, and testing.

Rewriting is a common approach to logic optimization based on local transformations. Most commercially available logic synthesis tools include a rewriting engine that may be used multiple times on the same netlist during optimization. This paper presents an And-Inverter graph (AIG) based rewriting algorithm using 5-input cuts. The best circuits are pre-computed for a subset of NPN classes of 5-variable functions. Cut enumeration and Boolean matching are used to identify replacement candidates. The presented approach is expected to complement existing rewriting approaches which are usually based on 4-input cuts. The experimental results show that, by adding the new rewriting algorithm to ABC synthesis tool, we can further reduce the area of heavily optimized large circuits by 5.57% on average.

This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

The problem of constructing a binary machine with the minimum number of stages generating a given binary sequence is addressed. Binary machines are a generalization of nonlinear feedback shift registers (NLFSRs) in which both connections, feedback and feedforward, are allowed and no chain connection between the register stages is required. An algorithm for constructing a shortest binary machine generating a given periodic binary sequence is presented.

A common approach to protect confidential information is to use a stream cipher which combines plain text bits with a pseudo-random bit sequence. Among the existing stream ciphers, Non-Linear Feedback Shift Register (NLFSR)-based ones provide the best trade-off between cryptographic security and hardware efficiency. In this paper, we show how to further improve the hardware efficiency of the Grain stream cipher. By transforming the NLFSR of Grain from its original Fibonacci configuration to the Galois configuration and by introducing new hardware solutions, we double the throughput of the 80 and 128-bit key 1 bit/cycle architectures of Grain with no area and power penalty.

In this paper, we address the problem of low-overhead implementation of Feedback Shift Registers (FSRs). We present a dynamic pulse latch which is based on transistors with two different channel lengths. The channel lengths are selected to make the latch suitable for replacing flip-flops in FSRs. The presented latch is 1.92 times smaller and 3.94 times less power consuming compared to the smallest standard flip-flop in the same technology. By re-implementing FSRs of Grain-80 stream cipher with the presented latch, we achieve 32.24% reduction in area, 36.77% reduction in total power, and 10.81% increase in the maximum clock frequency compared to the original, flip-flop based version of Grain-80. If, in addition, the static time borrowing technique is applied, we achieve an additional 25.5% increase in the maximum clock frequency at the expense of 4.68% smaller gain in area and 2.67% smaller gain in total power.

The Fibonacci and the Galois configurations of nonlinear feedback shift registers (NLFSRs) are considered. In the former, the feedback is applied to the input bit of the shift register only. In the latter, the feedback can potentially be applied to every bit. The sufficient conditions for equivalence of NLFSRs in the Fibonacci and the Galois configurations have been formulated previously. The equivalent NLFSRs in different configurations normally have to be initialized to different states to generate the same output sequences. The mapping between the initial states of two equivalent NLFSRs in the Fibonacci and the Galois configurations is derived in this paper.

Non-linear feedback shift registers (NLFSRs) have been proposed as an alternative to linear feedback shift registers (LFSRs) for generating pseudo-random sequences for stream ciphers. Conventional NLFSRs use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

Conventional nonlinear feedback shift registers (NLFSRs) use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

Non-linear feedback shift registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. In this paper, we introduce (n,k)-NLFSRs which can be considered a generalization of the Galois type of LFSR. In an (n,fc)-NLFSR, the feedback can be taken from any of the n bits, and the next state functions can be any Boolean function of up to k variables. Our motivation for considering this type NLFSRs is that their Galois configuration makes it possible to compute each next state function in parallel, thus increasing the speed of output sequence generation. Thus, for stream cipher application where the encryption speed is important, (n,k)-NLFSRs may be a better alternative than the traditional Fibonacci ones. We derive a number of properties of (n,k)- NLFSRs. First, we demonstrate that they are capable of generating output sequences with good statistical properties which cannot be generated by the Fibonacci type of NLFSRs. Second, we show that the period of the output sequence of an (n,k)-NLFSR is not necessarily equal to the length of the largest cycle of its states. Third, we compute the period of an (n,k)-NLFSR constructed from several parallel NLFSRs whose outputs are XOR-ed and show how to maximize this period. We also present an algorithm for estimating the length of cycles of states of (n,k)-NLFSRs which uses binary decision diagrams for representing the set of states and the transition relation on this set.

In this paper we describe a new logic synthesis approach based on rule-based randomized search using simulated annealing. Our work is motivated by two observations: (1) Traditional logic synthesis applies literal count as the primary quality metric during the technology independent optimization phase. This simplistic metric often leads to poor circuit structures as it cannot foresee the impact of early choices on the final area, delay, power consumption, etc. (2) Although powerful, global Boolean optimization is not robust and corresponding algorithms cannot be used in practice without artificially restricting the application window. Other techniques, such as algebraic methods scale well but provide weaker optimization power. To address both problems, we use randomized search that is based on a simple circuit graph representation and a complete set of local transformations that include algebraic and Boolean optimization steps. The objective of the search process can be tuned to complex cost functions, combining area, timing, routability, and power. Our experimental results on benchmark functions demonstrate the significant potential of the presented approach.

In this paper we present a fast algorithm for computing common multiple-vertex dominators in circuit graphs. Dominators are widely used in CAD applications such as satisfiability checking, equivalence checking, ATPG, technology mapping, decomposition of Boolean functions and power optimization. State of the art algorithms compute single-vertex dominators in linear time. However, the rare appearance of single-vertex dominators in circuit graphs requires the investigation of a broader type of dominators and the development of algorithms to compute them. We show that our new technique is faster and computes more common multiple-vertex dominators than existing techniques.

The growing complexity of today's system designs requires fast and robust verification methods. Existing BDD, SAT or ATPG-based techniques do not provide sufficient solutions for many verification instances. Boolean function hashing is a probabilistic verification approach which can complement existing formal methods in a number of applications such as equivalence checking, biased random simulation, power analysis and power optimization. The proposed hashing technique is based on the arithmetic transform, which maps a Boolean function onto a probabilistic hash value for a given input assignment. The presented algorithm uses multiple-vertex dominators in circuit graphs to progressively simplify intermediate hashing steps. The experimental results on benchmark circuits demonstrate the robustness of our approach.

Structural testing techniques, such as statement and branch coverage, play an important role in improving the dependability of software systems. However, finding a set of tests which guarantees high coverage is a time-consuming task. We present a technique for structural testing based on kernel computation. A kernel satisfies the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the program's flowgraph. We present a linear-time algorithm for computing minimum kernels based on pre- and post-dominator relations of a flowgraph.

This paper addresses two problems related to disjoint-support decomposition of Boolean functions. First, we present a heuristic for finding a subset of variables, X, which results in the disjoint-support decomposition f(X, Y)=h(g(X), Y) with a good area/delay trade-off. Second, we present a technique for re-synthesis of the original circuit, implementing f(X, Y) into a circuit implementing the decomposed representation h(g(X), Y). Preliminary experimental results indicate that the proposed approach has significant potential.

Graph dominators provide a general mechanism for identifying re-converging paths in circuits. This is useful in a number of CAD applications, including computation of signal probabilities for test generation, switching activities for power and noise analysis, statistical timing analysis, cut point selection in equivalence checking, etc. Single-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. The paper addresses the problem of finding double-vertex dominators, which occur more frequently. First, we introduce a data structure, called dominator chain, which allows the representation of all possible O(n/sup 2/) double-vertex dominators of a given vertex in O(n) space, where n is the number of vertices of the circuit graph. Dominator chains can be efficiently manipulated, e.g., it takes constant time to look-up whether a given pair of vertices is a double-vertex dominator. Second, we present an efficient algorithm for finding double-vertex dominators. The experimental results show that the presented algorithm is an order of magnitude faster than existing algorithms for finding double-vertex dominators. Thus, it is suitable for running in an incremental manner during logic synthesis.

A Kauffman network is an abstract model of gene regulatory networks. Each gene is represented by a vertex. An edge from one vertex to another implies that the former gene regulates the latter. Statistical features of Kauffman networks match the characteristics of living cells. The number of cycles in the network's state space, called attractors, corresponds to the number of different cell types. The attractor's length corresponds to the cell cycle time. The sensitivity of attractors to different kinds of disturbances, modeled by changing a network connection, the state of a vertex, or the associated function, reflects the stability of the cell to damage, mutations and virus attacks. In order to evaluate attractors, their number and lengths have to be computed. This problem is the major open problem related to Kauffman networks. Available algorithms can only handle networks with less than a hundred vertices. The number of genes in a cell is often larger. In this paper, we present a set of efficient algorithms for computing attractors in large Kauffman networks. The resulting software package is hoped to be of assistance in understanding the principles of gene interactions and discovering a computing scheme operating on these principles.

This paper reports a result concerning the relation between the best variable orderings of an ROBDD G/sub f/ and the decomposition structure of the Boolean function f represented by G/sub f/. It was stated in [S.-W. Jeong (1992)] that, if f has a decomposition of type f(X)-g(h/sub 1/(Y/sub 1/),h/sub 2/(Y/sub 2/),...h/sub k/(Y/sub k/)), where {Y/sub 1/}, i/spl isin/{1,2,...,k}, is a partition of X, then one of the orderings which keeps the variables within the sets {Y/sub 1/} adjacent is a best ordering for G/sub f/. Using a counterexample, we show that this statement is incorrect.

This work presents Hermes, a depth-optimal LUT based FPGA mapping algorithm. The presented algorithm is based on a new strategy for finding LUTs allowing to find a good LUT in a significantly shorter time compared to the previous methods. The quality of results is improved by enabling LUT re-implementation and by introducing a cost function which encourages input sharing among LUTs. The experimental results show that, on average, the presented algorithm computes 15.5% and 3.5% smaller LUT mappings compared to the ones obtained by FlowMap and CutMap, respectively, using two orders of magnitude less CPU time. The speed of Hermes makes it suitable for running in an incremental manner during logic synthesis.

This paper presents a heuristic algorithm for disjoint decomposition of a Boolean function based on its ROBDD representation. Two distinct features make the algorithm feasible for large functions. First, for an n-variable function, it checks only O(n2) candidates for decomposition out of O(2n) possible ones. A special strategy for selecting candidates makes it likely that all other decompositions are encoded in the selected ones. Second, the decompositions for the approved candidates are computed using a novel IntervalCut algorithm. This algorithm does not require re-ordering of ROBDD. The combination of both techniques allows us to decompose the functions of size beyond that possible with the exact algorithms. The experimental results on 582 benchmark functions show that the presented heuristic finds 95% of all decompositions on average. For 526 of those functions, it finds 100% of the decompositions.

We present a new algorithm for decomposition of type f=g/spl middot/h+r. The algorithm searches for Boolean products g/spl middot/h of a special type, called cyclic chains. The number of cubes in a cyclic chain is no greater than the number of cubes in the part of the on-set of f covered by this chain. The number of literals is always smaller. Cyclic chains are extracted recursively until no more can be found. The presented algorithm is of particular interest in applications, which require circuit representations of a limited depth. Experimental results on benchmark circuits demonstrate the efficiency of our approach.

Summary form only given. The algorithms for static reordering of Reduced Ordered Binary Decision Diagrams (ROBDDs) rely on dependable properties for grouping of variables. Two such properties have been studied so far: keeping symmetric variables adjacent and minimizing the ROBDD width. However, counterexamples have been found for the both cases. In this paper, we introduce a new condition for grouping of variables, suggesting to keep adjacent the variables from all bound sets of the function which are explicitly given by its composition tree.

Summary form only given. Presents an heuristic algorithm TOP (Three-level Optimization of PLDs), targeting a three-level logic expression of type g/sub 1/ o g/sub 2/, where g/sub 1/ and g/sub 2/ are sum-of-products and "o" is a binary operation. Such an expression can be implemented by a three-level Programmable Logic Device (PLD) consisting of PLA 1 and PLA2, implementing the first two levels of logic, and a set of two-input logic expanders, implementing the third level. Each logic expander can be programmed to realize any function of two variables. PLDs of this type seem to give a good trade-off between the speed of a flat PLA and density of a multi-level network of PLAs. TOP chooses the functionality of the logic expanders so that the area of the PLAs is minimized.

S.M. Reddy (1972) showed that the binary circuits realizing Reed-Muller canonical form are easily testable. In this paper, we extend Reddy's result to multiple-valued logic circuits, employing more than two discrete levels of signal. The electronic fabrication of such circuits became feasible due to the recent advances in integrated circuit technology. We show that, in the multiple-valued case, several new phenomena occur which allow us to asymptotically reduce the upper bound on the number of tests required for fault detection, but make the generation of tests harder.

In this paper, a slight error in the paper of Bryant (ibid., vol.35, no.8, p.677-691, Aug. 1986 is corrected: It was stated that, under a certain ordering restriction, composition of two Reduced Ordered Binary Decision Diagrams (ROBDDs) results in a reduced OBDD. We show a counterexample and explore under which conditions this statement is incorrect.