Routing is one of the major challenges of FPGA compilation. PathFinder is a ubiquitous FPGA routing algorithm used in industry and academia due to its ability to adapt to arbitrary routing architectures and user circuits. However, to this day, we do not fully understand why PathFinder works so well and what its limitations are. When a circuit fails to route, it is difficult to pinpoint the problem: architecture or algorithm. Usually, in such cases, either Pathfinder is fine-tuned or routing resources are added to the architecture to improve routability, thereby ignoring the inherent inefficiencies that may exist in Pathfinder, which further prevents us from designing silicon-efficient architectures. In this work, to pinpoint the problem, we construct constrained routing problems where nets have access to limited but specific routing resources that guarantee a legal routing solution. Yet, even with a state-of-the-art implementation, PathFinder fails to find the guaranteed routing solution or any other solution, highlighting issues specific to PathFinder. The reduced search space makes the underlying behavior more accessible for analysis and reasoning, allowing us to identify inefficiencies in the current PathFinder paradigm and propose a solution to address them. We uncovered that PathFinder's greedy approach of routing individual connections yields an inefficient route tree, in terms of the total number of nodes. We then transfer this insight-through a simple yet effective algorithm-from the constrained to the standard setting, where the search space is not reduced. By constructing more efficient route trees, the routed wirelength and the number of routed connections were reduced by 6.4% and 3.6%, respectively, on average.

Reconfigurable computing fabrics include FPGAs and CGRAs. FPGAs offer flexible bit-level reconfigurability and can map almost any program via high-level synthesis (HLS) compilers, but they incur high area and speed overheads compared to ASICs. CGRAs, in contrast, provide ASIC-like performance but limited flexibility, typically supporting only feedforward programs with unambiguous memory accesses, far from the capabilities of HLS compilers. This work introduces a new class of reconfigurable arrays inspired by modern dynamically scheduled HLS (DHLS) tools. Unlike traditional HLS, DHLS compilers no longer produce explicit state machines, eliminating the need for look-up tables. Instead, they delegate scheduling decisions to a set of coarse-grained primitives. Our arrays leverage these primitives as processing elements and combine FPGA-style interconnect topology for high routing flexibility with CGRA-like bus-based interconnect. We present a framework to explore these arrays and evaluate a preliminary architecture using DHLS benchmarks. The results show an average of ~2× speed improvement, but unfortunately only a ~20% area reduction compared to an FPGA implemented on the same technology node.

In recent years, there has been a trend towards reconfigurable fabrics at the intersection between field-programmable gate arrays (FPGAs) and coarse-grained reconfigurable arrays (CGRAs): using FPGA-like interconnect but word-based and built around coarse-grained primitives. These architectures often employ complex clusters with far more heterogeneous resources than FPGAs or typical CGRAs— sometimes over a hundred primitives, most of which are bypassable. As a result, clustering, the problem of covering the application netlist with architecture clusters, is a key challenge for design tools targeting these fabrics. Clustering is analogous to the instruction selection problem in CISC architectures, albeit with orders of magnitude more complex "instructions". In this work, we propose a two-phase, architecture-agnostic clustering algorithm that scales to highly complex architecture clusters. The first phase enumerates potential cluster matches in the application netlist using a strategy based on an abstract decision tree. The second phase selects a cover from the enumerated matches. We show that our algorithm effectively prunes the search space for complex clusters, scales well to circuits composed of many clusters, and achieves better clustering quality than CLUMAP, a state-of-the-art CGRA clustering algorithm, for the simple cases that CLUMAP can handle.

To answer the growing demand for hardware acceleration, Amazon, Microsoft, and many other major cloud service providers have included field-programmable gate arrays (FPGAs) in their datacenters. However, researchers have shown that cloud FPGAs, when shared between multiple tenants, face the threat of remote power side-channel analysis (SCA) attacks. FPGA time-to-digital converter (TDC) sensors enable adversaries to sense voltage fluctuations and, in turn, break cryptographic implementations or extract confidential information with the help of machine learning (ML). The operating temperature of the TDC sensor affects the traces it acquires, but its impact on the success of remote power SCA attacks has largely been ignored in literature. This paper attempts to fill in this gap. We focus on two attack scenarios: correlation power analysis (CPA) and ML-based profiling attacks. We show that the temperature impacts the success of the remote power SCA attacks: with the ambient temperature increasing, the success rate of the CPA attack decreases. In-depth analysis reveals that TDC sensor measurements suffer from temperature-dependent effects, which, if ignored, can lead to misleading and overly optimistic results of ML-based profiling attacks. We evaluate and stress the importance of following power side-channel trace acquisition guidelines for minimizing the temperature effects and, consequently, obtaining a more realistic measure of success for remote ML-based profiling attacks.

When spatially shared among multiple tenants, field-programmable gate arrays (FPGAs) are vulnerable to remote power side-channel analysis attacks. Using carefully crafted on-chip voltage sensors, adversaries can extract secrets (e.g., encryption keys or the architectural parameters of neural network accelerators) from collocated tenants. A common countermeasure against power side-channel attacks is hiding; in hiding, the goal is to introduce noise and worsen the signal-to-noise ratio visible to the attacker. In a multitenant FPGA setting, hiding countermeasures can be implemented with an active fence placed between tenants. Previous work demonstrated the effectiveness of active fences built using NAND-based ROs. We enhance the state-of-the-art active fence implementation with novel wire-based power wasters, at no increase in resource overhead. Compared to an RO-based fence, our active wire fence makes the side-channel attack considerably more difficult. When using the RO fence to protect an AES-128 cryptographic module, we recovered all the bytes of the secret key with one million sensor traces, on average. In comparison, when using our novel wire fence, more than six million traces (an improvement of at least 6×) were required to recover all the bits of the secret key.

We identified that in modern commercial FPGAs, routing signals from the general interconnect to the inputs of the CLB primitives through a very sparse input interconnect block (IIB) represents a significant runtime bottleneck. This is despite academic research often neglecting the runtime of last-mile routing through the IIB. We propose a two-step routing approach that allows resolving this bottleneck by leveraging massive parallelism of today's compute infrastructure. The main premise that enables massive parallelization is that once the signals are legally routed in the general interconnect-only reaching the inputs of the IIB, but not the final targets-the remaining last-mile routing through the IIB can be completed independently for each FPGA tile.

A graph$H$is a minor of a second graph$G$if$G$can be transformed into$H$by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem, where$H$is the application's dataflow graph and$G$is the CGRA's device-model graph. A heuristic algorithm to find graph minors has proven to be practical for sparse graphs with hundreds of vertices in a quantum computing application. In this work, we adapt the heuristic to CGRA application mapping, where the graphs have directed edges, and the vertices have unique types (e.g., representing ALUs or interconnect). Additionally, we alter the original cost function, taking inspiration from PathFinder, an iterative negotiated-congestion routing algorithm. In an experimental study comparing with a CGRA mapper based on integer linear programming, we demonstrate a higher rate of successful mappings and from 80× to up to orders of magnitude lower runtime.

We identified that in modern commercial FPGAs, routing signals from the general interconnect to the configurable logic blocks (CLBs) through a very sparse input interconnect block (IIB) represents a significant runtime bottleneck. This is despite academic research usually altogether neglecting the runtime of last-mile routing through the IIB. To alleviate this bottleneck, we combine computer-aided design (CAD) and FPGA architecture enhancements. We propose a multi-stage FPGA routing approach, based on the premise that once the signals are legally routed in general interconnect-only reaching the inputs of the IIB, but not the final targets-the remaining last-mile routing through the IIB can be completed efficiently and independently for each FPGA tile. Then, the final routing solution can simply be built by joining the previously obtained partial solutions. However, we observe that some properties of modern IIB architectures limit the success rate of the intra-CLB routing, creating the need for revisiting the routing in the general interconnect and inevitably impairing the multi-stage routing runtime gains. We show that an enhanced IIB architecture mitigates the issue at a minimal cost. With ISPD16 benchmarks and an FPGA architecture model closely resembling AMD UltraScale FPGAs, we demonstrate the dominant contribution of last-mile routing to the router's runtime. After applying our multi-stage routing approach and the proposed enhancements, we show that the observed bottleneck can be mitigated, resulting in 4.94× faster routing on average.

Field-programmable gate arrays (FPGAs) have become critical components in many cloud computing platforms. These devices possess the fine-grained parallelism and specialization needed to accelerate applications ranging from machine learning to networking and signal processing, among many others. Unfortunately, fine-grained programmability also makes FPGAs a security risk. Here, we review the current scope of attacks on cloud FPGAs and their remediation. Many of the FPGA security limitations are enabled by the shared power distribution network in FPGA devices. The simultaneous sharing of FPGAs is a particular concern. Other attacks on the memory, host microprocessor, and input/output channels are also possible. After examining current attacks, we describe trends in cloud architecture and how they are likely to impact possible future attacks. FPGA integration into cloud hypervisors and system software will provide extensive computing opportunities but invite new avenues of attack. We identify a series of system, software, and FPGA architectural changes that will facilitate improved security for cloud FPGAs and the overall systems in which they are located.

Side-channel CPU disassembly is a side-channel attack that allows an adversary to recover instructions executed by a processor. Not only does such an attack compromise code confidentiality, it can also reveal critical information on the system's internals. Being easily accessible to a vast number of end users, modern embedded devices are highly vulnerable against disassembly attacks. To protect them, designers deploy countermeasures and verify their efficiency in security laboratories. Clearly, any vulnerability discovered at that point, after the integrated circuit has been manufactured, represents an important setback. In this paper, we address the above issues in two steps: Firstly, we design a framework that takes a design netlist and outputs simulated power side-channel traces, with the goal of assessing the vulnerability of the device at design time. Secondly, we propose a novel side-channel disassembler, based on multilayer perceptron and sparse dictionary learning for feature engineering. Experimental results on simulated and measured side-channel traces of two commercial RISC-V devices, both working on operating frequencies of at least 100 MHz, demonstrate that our disassembler can recognize CPU instructions with success rates of 96.01% and 93.16%, respectively.

FPGAs are proving useful and attractive for many applications, thanks to their hardware reconfigurability, low power, and high-degree of parallelism. As a result, modern embedded systems are often based on systems-on-chip (SoCs), where CPUs and FPGAs share the same die. In this paper, we demonstrate the first undervolting attack in which the FPGA acts as an aggressor while the CPU, residing on the same SoC, is the victim. We show that an adversary can use the FPGA fabric to create a significant supply voltage drop which, in turn, faults the software computation performed by the CPU. Additionally, we show that an attacker can, with an even higher success rate, execute a denial-of-service attack, without any modification of the underlying hardware or the power distribution network. Our work exposes a new electrical-level attack surface, created by tight integration of CPUs and FPGAs in modern SoCs, and incites future research on countermeasures.

In this paper, we survey recently proposed methods for protecting against side-channel and fault attacks in shared FPGAs. These methods are quite versatile, targeting FPGA compilation flow, real-time timing-fault detection, on-chip active fences, automated bitstream verification, etc. Despite their versatility, they are mostly designed to counteract a specific class of attacks. To understand how to address the problem of security in shared FPGAs in a comprehensive way, we discuss their individual strengths and weaknesses, in an attempt to identify research directions necessitating further investigation.

Novel applications have triggered significant changes at the system level of FPGA architecture design, such as the introduction of embedded VLIW processor arrays and hardened NoCs. However, the routing architecture of the soft logic fabric has largely remained unchanged in recent years. Since hunger for acceleration of ever more varied tasks with various power budgets---as well as complications related to technology scaling---is likely to remain significant, it is foreseeable that the routing architecture too will have to evolve. In this work, we do not try to suggest how routing architectures of tomorrow should look like. Instead, we analyze an existing architecture from a popular commercial FPGA family, discussing the possible origins of various design decisions and pointing out aspects that may merit future research. Moreover, we present an open-source tool that greatly eases such analyses, relying only on data readily available from the vendor CAD tools. Our hope is that this work will help the academic research community in catching up with the current developments in industry and accelerate its contributions to FPGA architectures of the future.

Recent works have demonstrated the possibility of extracting secrets from a cryptographic core running on an FPGA by means of remote power analysis attacks. To mount these attacks, an adversary implements a voltage fluctuation sensor in the FPGA logic, records the power consumption of the target cryptographic core, and recovers the secret key by running a power analysis attack on the recorded traces. Despite showing that the power analysis could also be performed without physical access to the cryptographic core, these works were mostly carried out on dedicated FPGA boards in a controlled environment, leaving open the question about the possibility to successfully mount these attacks on a real system deployed in the cloud. In this paper, we demonstrate, for the first time, a successful key recovery attack on an AES cryptographic accelerator running on an Amazon EC2 F1 instance. We collect the power traces using a delay-line based voltage drop sensor, adapted to the Xilinx Virtex Ultrascale+ architecture used on Amazon EC2 F1, where CARRY8 blocks do not have a monotonic delay increase at their outputs. Our results demonstrate that security concerns raised by multitenant FPGAs are indeed valid and that countermeasures should be put in place to mitigate them.

Embedded and cyber-physical systems are pervading all aspects of our lives, including sensitive and critical ones. As a result, they are an alluring target for cyber attacks. These systems, whose implementation is often based on reconfigurable hardware, are typically deployed in places accessible to attackers. Therefore, they require protection against tampering and side-channel attacks. However, a side-channel resistant implementation of a security primitive is not sufficient, as it can be weakened by an adversary, aging, or environmental factors. To detect this, legitimate users should be able to evaluate the side-channel resistance of their systems not only when deploying them for the first time, but also during their entire service life. The most widespread and de facto standard methodology for measuring power side-channel leakage uses Welch's t-test. In practice, collecting the data for the t-test requires physical access to the device, a device-specific test setup, and the equipment for measuring the power consumption during device operation. Consequently, only a small number of cyber-physical systems deployed in the field can be tested this way and the tests to reevaluate the device resistance to side-channel attacks cannot be easily repeated. To address these issues, we present a design and an FPGA implementation of a built-in test for self-evaluation of the resistance to first-order power side-channel attacks. Once our test is triggered, the FPGA measures its own internal power-supply voltage and computes the t-test statistic in real time. Experimental results on two different implementations of the AES-128 algorithm demonstrate that the self-evaluation test is very reliable. We believe that this work is an important step towards the development of security sensors for the next generation of safe and robust cyber-physical systems.

Recently, FPGA-accelerated cloud has emerged as a new computing environment. The inclusion of FPGAs in the cloud has created new security risks, some of which are due to circuits exercising excessive switching activity. These power-wasting tenants can cause timing faults in the collocated circuits or a denial-of-service attack by resetting the host FPGA. In this work, we present the idea of populating the FPGA with voltage sensors based on ring oscillators, to continuously monitor the core voltage fluctuations across the entire FPGA. To implement the sensors, we do not lock any FPGA resources; instead, we infiltrate the sensors undercover, by taking advantage of the logic and the routing resources unused by the tenants. Additionally, we infiltrate the sensors into the FPGA circuits after their implementation, but before their deployment on the cloud; the tenants are thus neither aware nor affected by our voltage monitoring system. Finally, we devise a novel metric that takes the sensor measurements to quantify the power wasting activity in the FPGA clock regions where the sensors are infiltrated. We use VTR benchmarks and a Xilinx Virtex-7 FPGA to test the feasibility of our approach. Experimental results demonstrate that, using the undercover voltage sensors and our novel metric, one can accurately locate the source of the malicious power-wasting activity.

This paper presents an extension to PathFinder FPGA routing algorithm, which enables it to deliver FPGA designs free from risks of crosstalk attacks. Crosstalk side-channel attacks are a real threat in large designs assembled from various IPs, where some IPs are provided by trusted and some by untrusted sources. It suffices that a ring-oscillator based sensor is conveniently routed next to a signal that carries secret information (for instance, a cryptographic key), for this information to possibly get leaked. To address this security concern, we apply several different strategies and evaluate them on benchmark circuits from Verilog-to-Routing tool suite. Our experiments show that, for a quite conservative scenario where 10-20% of all design nets are carrying sensitive information, the crosstalk-attack-aware router ensures that no information leaks at a very small penalty: 1.58-7.69% increase in minimum routing channel width and 0.12-1.18% increase in critical path delay, on average. In comparison, in an AES-128 cryptographic core, less than 5% of nets carry the key or the intermediate state values of interest to an attacker, making it highly likely that the overhead for obtaining a secure design is, in practice, even smaller.

Albeit very appealing, FPGA multitenancy in the cloud computing environment is currently on hold due to a number of recently discovered vulnerabilities to side-channel attacks and covert communication. In this work, we successfully demonstrate a new attack scenario on shared FPGAs: we show that an FPGA tenant can activate a dormant hardware Trojan without any physical or logical connection to the private Trojan-infected FPGA circuit. Our victim contains a so-called satisfiability don't-care Trojan, activated by a pair of don't-care signals, which never reach the combined trigger condition under normal operation. However, once a malicious FPGA user starts to induce considerable fluctuations in the on-chip signal delays—and, consequently, the timing faults-these harmless don't-care signals take unexpected values which trigger the Trojan. Our attack model eliminates the assumption on physical access to or manipulation of the victim design. Contrary to existing fault and side-channel attacks that target unprotected cryptographic circuits, our new attack is shown effective even against provably well-protected cryptographic circuits. Besides demonstrating the attack by successfully leaking the entire cryptographic key from one unprotected and one masked AES S-box implementation, we present an efficient and lightweight countermeasure.

FPGAs have made their way into the cloud, allowing users to gain remote access to the state-of-the-art reconfigurable fabric and implement their custom accelerators. Since FPGAs are large enough to accommodate multiple independent designs, the multi-tenant user scenario may soon be prevalent in cloud computing environments. However, shared use of an FPGA raises security concerns. Recently discovered hardware Trojans for use in multi-tenant FPGA settings target denial-of-service attacks, power side-channel attacks, and crosstalk side-channel attacks. In this work, we present an attack method for causing timing-constraints violation in the multi-tenant FPGA setting. This type of attack is very dangerous as the consequences of timing faults are temporary errors, which are often impossible to notice. We demonstrate the attack on a set of self-timed true random number generators (STRNGs), frequently used in cryptographic applications. When the attack is launched, the STRNG outputs become biased and fail randomness tests. However, after the attack, STRNGs recover and continue generating random bits.

FPGA routing is one the longest steps in FPGA compilation, often preventing fast edit-compile-test cycles in prototyping and development. There have been attempts to accelerate FPGA routing using algorithmic improvements, multi-core or multi-CPU platforms. Instead, we propose porting FPGA routing to a CPU+FPGA platform. Motivated by the approaches in FPGA-accelerated graph processing, we propose and implement three acceleration strategies: (1) reducing the number of expensive random memory accesses, (2) parallel and pipelined computation, and (3) efficient hardware priority queues. To reduce irregular memory accesses we first allow wire-to-pin wavefront expansion only when a net is reaching one of its destination pins and, second, we group in sets all the wires starting at the same (x, y) coordinate of the FPGA grid and going in the same direction. Consequently, it becomes possible to design an FPGA accelerator that performs streaming memory accesses and parallel wavefront expansion on all wires in two connected sets. To test and evaluate our FPGA-accelerated PathFinder-based router, we implement it on DE1-SoC, Intel's ARM+FPGA platform and run a set of benchmarks from the VTR suite. The results show that our implementation produces deterministic and good quality output. It is also successful in accelerating a purely software version on the same CPU+FPGA platform, but not against VPR running on a powerful Intel Core-i5 CPU, due to the limitations of the chosen mid-end DE1-SoC platform. Yet, our performance prediction model suggests that higher memory bandwidth and faster FP units would render our router superior to the software alternative.

Field-programmable gate arrays (FPGAs) are, like CPUs, susceptible to side-channel information leakage and covert communication. The malleability of FPGAs enables users to create and control physical effects, and sense and measure the consequences. With FPGAs becoming integrated into the cloud, a range of hardware-and software-based attacks may be waiting to be discovered. In this survey, we focus on physical channels used for side-channel attacks or covert communication. Physical channels are those that exist due to the physical properties of FPGAs, for example: power consumption, temperature, or electromagnetic emission. We include the most recent demonstrations of malicious or unintended use of physical channels in remote and/or shared FPGAs, propose taxonomies, compare the efficiency and feasibility of the attacks, and discuss challenges in preventing them.

This paper describes a deterministic and parallel implementation of the VPR routability-driven router for FPGAs. We considered two parallelization strategies: (1) routing multiple nets in parallel; and (2) routing one net at a time, while parallelizing the Maze Expansion step. Using eight threads running on eight cores, the two methods achieved speedups of 1.84× and 3.67×, respectively, compared to VPR's single-threaded routability-driven router. Removing the determinism requirement increased these respective speedups to 2.67× and 5.46×, while sacrificing the quarantee of reproducible results.

As transistor scaling is slowing down [1], other opportunities for ensuring continuous performance increase have to be explored. Field programmable gate arrays (FPGAs) are in the spotlight these days: not only due to their malleability and energy efficiency, but also because FPGAs have recently been integrated into the cloud [2]. The latter makes them available to everyone in need of the immense computing power and data throughput they can offer. However, one important issue needs to be resolved first - the time to compile an industrial-scale design for an FPGA must be drastically reduced. Researchers have been looking for ways to accelerate FPGA routing through parallelism, since routing is one of the most time-consuming compilation steps. However, the ideal solution has not been found yet. This paper provides a survey of parallel FPGA routers, with the aim to identify their strengths and weaknesses, thus suggesting directions to take in further efforts for acceleration.

Historically, hardware acceleration technologies have either been application-specific, therefore lacking in flexibility, or fully programmable, thereby suffering from notable inefficiencies on an application-by-application basis. To address the growing need for domain-specific acceleration technologies, this paper describes a design methodology (i) to automatically generate a domain-specific coarse-grained array from a set of representative applications and (ii) to introduce limited forms of architectural generality to increase the likelihood that additional applications can be successfully mapped onto it. In particular, coarse-grained arrays generated using our approach are intended to be integrated into customizable processors that use application-specific instruction set extensions to accelerate performance and reduce energy; rather than implementing these extensions using application-specific integrated circuit (ASIC) logic, which lacks flexibility, they can be synthesized onto our reconfigurable array instead, allowing the processor to be used for a variety of applications in related domains. Results show that our array is around 2× slower and 15× larger than an ultimately efficient ASIC implementation, and thus far more efficient than fieldprogrammable gate arrays (FPGAs), which are known to be 3-4× slower and 20-40× larger. Additionally, we estimate that our array is usually around 2× larger and 2× slower than an accelerator synthesized using traditional datapath merging, which has, if any, very limited flexibility beyond the design set of DFGs.

Hardware specialization is often the key to efficiency for programmable embedded systems, but comes at the expense of flexibility. This paper combines flexibility and efficiency in the design and synthesis of domain-specific datapaths. We merge all individual paths from the Data Flow Graphs (DFGs) of the target applications, leading to a minimal set of required resources; this set is organized into a column of physical operators and cloned, thus generating a domain-specific rectangular lattice. A bus-based FPGA-style interconnection network is then generated and dimensioned to meet the needs of the applications. Our results demonstrate that the lattice has good flexibility: DFGs that were not used as part of the datapath creation phase can be mapped onto it with high probability. Compared to an ASIC design of a single DFG, the speed of our domain-specific coarse-grained reconfigurable datapath is degraded by a factor up to 2×, compared to 3-4× for an FPGA; similarly, our lattice is up to 10× larger than an ASIC, compared to 20-40× for an FPGA. We estimate that our array is up to 6× larger than an ASIC accelerator, which is synthesized using datapath merging and has limited or null generality.