11institutetext:  Drexel University, Philadelphia, PA, USA
11email<EMAIL_ADDRESS>22institutetext: University Of Moratuwa, Moratuwa,
Sri Lanka
22email<EMAIL_ADDRESS>33institutetext: Abdullah Gul University,
Kayseri, Turkey
33email<EMAIL_ADDRESS>44institutetext: Prairie View A&M University,
Prairie View, TX, USA
44email<EMAIL_ADDRESS>55institutetext: Temsa R&D Center, Adana,
Turkey
55email<EMAIL_ADDRESS>
# NEUROSEC: FPGA-Based Neuromorphic Audio Security

Murat Isik 11 Hiruna Vishwamith 22 Yusuf Sur 33 Kayode Inadagbo 44 I. Can
Dikmen 55

###### Abstract

Neuromorphic systems, inspired by the complexity and functionality of the
human brain, have gained interest in academic and industrial attention due to
their unparalleled potential across a wide range of applications. While their
capabilities herald innovation, it is imperative to underscore that these
computational paradigms, analogous to their traditional counterparts, are not
impervious to security threats. Although the exploration of neuromorphic
methodologies for image and video processing has been rigorously pursued, the
realm of neuromorphic audio processing remains in its early stages. Our
results highlight the robustness and precision of our FPGA-based neuromorphic
system. Specifically, our system showcases a commendable balance between
desired signal and background noise, efficient spike rate encoding, and
unparalleled resilience against adversarial attacks such as FGSM and PGD. A
standout feature of our framework is its detection rate of 94%, which, when
compared to other methodologies, underscores its greater capability in
identifying and mitigating threats within 5.39 dB, a commendable SNR ratio.
Furthermore, neuromorphic computing and hardware security serve many sensor
domains in mission-critical and privacy-preserving applications.

###### Keywords:

neuromorphic computing, FPGA, hardware security, audio processing

##  1 Introduction

Computer hardware that emulates the intricate functions of the human brain has
been termed neuromorphic hardware. Drawing inspiration from biological neural
systems, neuromorphic hardware aims to replicate the way these systems process
information, bridging the gap between biological cognition and artificial
computation. Neuromorphic computing represents a paradigm shift from
traditional computing methodologies. At its core, it seeks to emulate the
brain’s neural structures and functionalities, offering a more natural and
efficient way to process information. The significance of neuromorphic
computing lies in its potential to revolutionize various domains, from
artificial intelligence to robotics, by providing systems that can learn,
adapt, and evolve in real-time [6, 16, 7]. Field-Programmable Gate Arrays
(FPGAs) have emerged as a pivotal component in the neuromorphic computing
landscape. Their inherent reconfigurability and parallel processing
capabilities align seamlessly with the demands of neuromorphic systems. FPGAs
offer the flexibility to design and customize neuromorphic architectures,
enabling researchers and engineers to experiment with and optimize neural
network designs, thereby pushing the boundaries of what neuromorphic systems
can achieve. As with any computing system, security remains paramount in
neuromorphic systems. Given their potential applications in sensitive areas
such as defense, healthcare, and finance, ensuring the integrity,
confidentiality, and availability of data processed by neuromorphic systems is
crucial. Furthermore, the unique architecture and operation of neuromorphic
systems present both challenges and opportunities in the realm of security,
requiring specialized approaches to safeguard them against threats [20, 17, 2,
15, 9, 10]. Neuromorphic hardware, inspired by the intricate functions of the
human brain, seeks to bridge the gap between biological cognition and
artificial computation. This approach represents a paradigm shift, offering a
more natural and efficient way to process information. FPGAs, with their
inherent reconfigurability and parallel processing capabilities, have emerged
as a pivotal component in this landscape, enabling the design and
customization of neuromorphic architectures. Given the potential applications
of neuromorphic systems in sensitive areas such as defense and healthcare,
ensuring their security is paramount. The unique architecture of these systems
presents both challenges and opportunities in the realm of security.

In this paper, we present the following contributions:

  * •

We explore SNN-based neuromorphic audio processing, a niche compared to
image/video processing.

  * •

We analyze security threats in neuromorphic audio, emphasizing adversarial
attacks like FGSM and PGD that introduce audio artifacts.

  * •

Our FPGA-integrated system boasts a 94% detection rate, efficient spike
encoding, and a balanced signal-to-noise ratio.

  * •

We compare our framework with existing methods, highlighting its superior
threat detection and mitigation within a favorable SNR.

##  2 Neuromorphic Hardware: Evolution, Applications, and Security

Neuromorphic hardware has transitioned from basic silicon neurons to
sophisticated neuromorphic chips, offering benefits, especially in security.
FPGAs enhance these systems with their flexibility in design and parallel
processing capabilities. Several studies have explored the integration of
neuromorphic systems with FPGAs, touching upon design methodologies,
applications, and security implications. The journey of neuromorphic computing
began with the vision of replicating the brain’s neural structures in silicon.
Early endeavors focused on creating silicon neurons, aiming to capture the
parallel processing capabilities of the brain. Over time, advancements in
technology and research led to the development of advanced neuromorphic chips,
which are now at the forefront of many cutting-edge applications. FPGAs offer
flexibility in design, allowing for the customization of neuromorphic
architectures. Their reconfigurability and parallel processing capabilities
align well with the inherent characteristics of neuromorphic systems. Several
studies and research endeavors have delved into the integration of
neuromorphic systems with FPGAs. These works have explored various aspects,
from design methodologies to applications, and have also touched upon the
security implications of such integrations. Neuromorphic hardware offers a
range of benefits, especially in the context of security. Neuromorphic
hardware, with its unique architecture and capabilities, holds immense promise
in the realm of security. Its integration with FPGAs further amplifies its
potential, paving the way for adaptive security solutions [18, 5, 26, 8].
Researchers explored the use of temporal dependency in audio data to mitigate
the impact of adversarial examples, particularly in automatic speech
recognition (ASR) systems. The study shows that input transformations, often
used in image adversarial defense, provide limited robustness improvement in
audio data and are susceptible to advanced attacks. Conversely, exploiting
temporal dependencies in audio can effectively discriminate against
adversarial examples and resist adaptive attacks on Recurrent Neural Network
(RNN) [25]. It was showed the vulnerability of Deep Neural Networks (DNNs) to
adversarial examples, particularly in the audio field. Adversarial examples
are crafted by adding subtle noise to original samples, which can deceive
machines while remaining imperceptible to humans. The paper proposes a defense
method that introduces low-level distortion via audio modification to detect
these adversarial examples. The idea is that while the classification of the
original sample remains stable under this distortion, the adversarial
example’s classification changes significantly. This method was tested using
the Mozilla Common Voice dataset and the DeepSpeech model, showing a
significant drop in the accuracy of adversarial examples, thereby effectively
detecting them [12]. U-Net based attention model were introduced for enhancing
adversarial speech signals. The proposed self-attention speech U-Net is
designed to improve the robustness against adversarial examples in speech
recognition systems. The model uses attention mechanisms in its upsampling
blocks to better process adversarial noise in speech signals. The study
demonstrates that while traditional methods of speech enhancement can increase
signal-to-noise ratio (SNR) scores, they often fail to improve other key
metrics such as PESQ, STI, and STOI. The authors also found that adversarial
training can further enhance the performance of the Convolutional Neural
Network (CNN), making it more robust against adversarial attacks in speech
recognition [24].

Table 1: Features of Neuromorphic Systems. Feature | Description
---|---
Speed | Emulates brain for fast parallel processing.
Power Efficiency | Energy-efficient chips for continuous monitoring.
Adaptive Learning | Evolves algorithms for new threats.
Anomaly Detection | Flags deviations as threats.
Hardware Security | Robust protection via FPGA integration.
Parallel Processing | Processes multiple data streams.
Scalability | Supports expansion for security needs.
Resilience | Resists conventional system attacks.
Real-time Response | Instant threat response.
Integration | FPGA versatility offers comprehensive security.

###  2.1 Spiking Neural Networks (SNNs)

SNNs are designed to computationally emulate the behavior of biological
neurons. As the intricacies of these networks grow, so do the computational
demands associated with SNN inference. This growth has intensified the trade-
off between hardware resources, power consumption, and acceleration
performance, making it a focal point of contemporary research. Consequently,
there’s a burgeoning need for specialized hardware accelerators that can
optimize computing-to-power efficiency ratios, especially in embedded and
lightweight applications. One of the salient features of SNNs, from a hardware
implementation perspective, is their communication mechanism. Neurons in SNNs
communicate using spikes, which, in terms of logic resources, can be equated
to a single bit, thereby reducing logic occupation. Recent studies have
highlighted the potential of SNNs in enhancing security. For instance,
researchers have shown that noise filters for Dynamic Vision Sensors (DVS) can
act as defense mechanisms against adversarial attacks. They conducted
experiments with various attacks, specifically in the setting of two different
noise filters tailored for DVS cameras [16]. In another notable study, a novel
attack method tailored for rate coding SNNs was introduced, named the Rate
Gradient Approximation Attack (RGA). This method was employed to detect
abnormal traffic patterns, indicative of attacks, in Networks-on-Chip data
using SNNs [1, 14]. Fig. 1 illustrates a generic framework for implementing
hardware security in neuromorphic audio systems.

Figure 1: Hardware Security Framework for Neuromorphic Audio Systems.

###  2.2 Event-based Applications in Audio Processing

Event-based audio processing is an emerging paradigm that draws inspiration
from the asynchronous nature of the human auditory system which is depicted
schematic representation of the audio processing workflow in Fig. 2. Unlike
traditional audio processing techniques that operate on uniformly sampled
data, event-based methods focus on capturing and processing significant audio
events as they occur. Researchers provide a comprehensive review of event-
based sensing and signal processing across various sensory domains, including
the auditory system [23]. Their work explains the advantages of event-based
approaches, especially in mimicking biological sensory systems, and offers
insights into the potential applications and challenges of this paradigm. The
authors delve into the post-processing of audio event detectors, employing
reinforcement learning to enhance their performance [4]. Their approach
underscores the potential of combining advanced machine-learning techniques
with event-based audio processing to achieve superior detection accuracy and
efficiency. Furthermore, the significance of neuromorphic auditory computing
in the context of robotics is highlighted in [3]. The author emphasizes the
potential of a digital, event-based implementation of the hearing sense,
paving the way for more responsive and adaptive robotic systems that can
interact seamlessly with their environment.

Figure 2: Audio Processing Diagram.

###  2.3 Security Challenges

Neuromorphic systems have garnered significant attention due to their
potential in various applications, from robotics to artificial intelligence.
However, like all computing systems, they are not immune to security threats.
This section delves into the unique security challenges posed by FPGA-based
neuromorphic systems, drawing from existing literature and current research
findings. The integration of neuromorphic computing with FPGA technology
presents a novel set of vulnerabilities. FPGA platforms, while offering
flexibility and performance advantages, have been shown to be susceptible to a
range of security threats. FPGA provides the capability to process vast
amounts of data in parallel, mimicking the human brain’s neural networks. On
the other hand, this complexity can introduce multiple points of
vulnerability. These vulnerabilities can be exploited by adversaries to
compromise the integrity, confidentiality, or availability of the system.
Specific attacks on FPGA-based neuromorphic systems include:

  * •

Side-channel attacks: These attacks exploit information leaked during the
physical operation of the system, such as power consumption or electromagnetic
radiation. Given the unique architecture of neuromorphic systems, they may
exhibit distinct side-channel signatures that can be exploited by attackers.

  * •

Hardware Trojans: Malicious alterations to the hardware can be introduced
during the design or manufacturing process. These Trojans can lie dormant
until triggered, leading to unexpected and potentially harmful behaviors.

  * •

Model Vulnerability Analysis: The security of neuromorphic systems depends on
identifying and counteracting vulnerabilities in neural network models, a key
step in preventing adversarial attacks. These attacks, often imperceptible to
human observers, manipulate model inputs to provoke incorrect responses or
reveal confidential information. Therefore, a comprehensive vulnerability
analysis is vital to develop effective defenses, ensuring the integrity and
dependability of these advanced systems in adversarial scenarios which are
focused on this work.

Addressing the security challenges of FPGA-based neuromorphic systems requires
a multi-faceted approach. The solutions must be tailored to the unique
architecture and operation of these systems. Dedicated hardware modules can be
integrated into the FPGA to monitor and detect malicious activities. For
instance, hardware performance counters can be used to detect anomalies in
system operation, indicative of an ongoing attack. To safeguard data integrity
and confidentiality, advanced encryption techniques can be employed.
Homomorphic encryption, for instance, allows for computations on encrypted
data, making it particularly suitable for neuromorphic systems where data
privacy is paramount. Additionally, the design and implementation of FPGA-
based neuromorphic systems should adhere to secure coding practices. This
includes regular code reviews, vulnerability assessments, and the use of
trusted libraries and tools. Ensuring that the software aspect of the system
is secure can mitigate potential exploitation of hardware vulnerabilities [22,
1, 21, 13].

##  3 Proposed Design Methodology

We describe a specific neuromorphic hardware system, detailing its
architecture and relevant features. In response to these identified threats,
we put forth a suite of tailored security measures and methodologies, all
grounded in a well-articulated theoretical framework. A salient challenge that
emerges in this domain is the susceptibility of audio-denoising systems to
adversarial attacks. The core intent behind these attacks is to induce the
denoising system to yield inaccurate or suboptimal outputs. Two primary
modalities of these attacks can be discerned: Gradient-based Attacks, PGD
(Projected Gradient Descent) and FGSM (Fast Gradient Sign Method), which
exploit a comprehensive understanding of the model’s architecture and its
gradient information, and Black-box Attacks, which function in the absence of
intimate knowledge of the model’s internals, instead relying on surrogate
models or alternative methodologies. The effects of such adversarial endeavors
are significant. For instance, within a security paradigm that leverages
surveillance audio, an adversary employing adversarial samples might
manipulate the system to exclude or modify critical audio data. Analogously,
within the consumer electronics sector, such attacks present the risk of
degrading user experience or spreading false information. The strategic
emphasis on audio input-based adversarial attacks, particularly in
computational tasks extending beyond mere classification, underscores the
inherent vulnerabilities extant in contemporary deep learning paradigms. This
focus reiterates the pressing imperative for supported robustness across the
spectrum of machine learning endeavors, extending beyond the purview of
classification alone.

Figure 3: Overview of the steps involved in this work.

The proposed algorithm highlights the key aspects of the security protocol for
a neuromorphic system, emphasizing the detection and mitigation of potential
threats. As illustrated in Fig. 3, the algorithm begins with the
initialization phase, where the dataset and the attack model are loaded,
ensuring all necessary data is available for processing and potential attack
simulation. Subsequently, the model is integrated into the attack mechanism,
setting the stage for potential threat simulations and evaluations. To
optimize computational efficiency, the system processes the dataset in
batches, handling 32 batches at a time. Each audio batch, which comprises both
noisy and clean data, undergoes a splitting process where it’s divided into
its absolute value and argument components using the Short-Time Fourier
Transform (STFT). To simulate real-world processing latencies, the absolute
values and arguments of both the noisy and clean audio are delayed, with the
clean audio undergoing a similar delay. The core of the algorithm lies in the
attack generation phase. Here, an attack is synthesized by comparing the
absolute values of the noisy and clean audio. If an attack is to be simulated,
it targets the noisy audio’s absolute value. This synthesized attack, when
combined with the argument of the noisy audio using the SFT mixer, produces a
composite signal. The Signal-to-Noise Ratio (SNR) of this composite signal is
then computed. A significant deviation of the SNR from a predefined threshold
indicates the detection of an attack. In response to a detected threat, the
Advanced Encryption Standard (AES) is employed to encrypt the data, ensuring
its confidentiality. If required, the encrypted data can be decrypted to
restore its original form. However, in the absence of any detected threats,
the model outputs the denoised absolute value. This denoised value, when
combined with the noisy audio’s argument using the SFT mixer, represents the
output under standard operation. The algorithm concludes its operation,
marking the end of the processing cycle. This comprehensive framework ensures
the security of neuromorphic systems, addressing potential threats through a
combination of proactive and reactive measures.

###  3.1 CPU/GPU Implementation

We utilized Python to execute implementations on the CPU and GPU. The study
leveraged the computational prowess of NVIDIA’s GeForce RTX 3060 GPU and
Intel’s Core i9 12900H CPU, both of which are optimized for different tasks,
ensuring an efficient execution of our implementations.

###  3.2 FPGA Implementation

The presented implementation delineates the operational flow and
interconnections of a neuromorphic system integrated with an FPGA. The
schematic representation captures the core components and their interactions,
providing a comprehensive overview of the system’s architecture and
functionality. Fig. 4 showcases the implementation of the framework within the
FPGA architecture.

Figure 4: Implementation of the Neuromorphic Audio Processing Framework on
FPGA Architecture.

The following elucidates the individual components and their roles:

  1. 1.

Memory (Weights, Patterns): Essential data, such as synaptic weights, neural
patterns, and bias values, are stored in this module. These are crucial for
neuromorphic processing. We utilized DDR4 SDRAM for reading the audio dataset
and writing feedback from the design. The data, initialized in the MIF file
type, is stored in RAM and is fed into the neuromorphic processor for further
processing.

  2. 2.

STFT (Short-Time Fourier Transform): This section processes the audio input,
converting it into the frequency domain, making it suitable for neuromorphic
processing and aiding in the detection of adversarial attacks with Xilinx FFT
core.

  3. 3.

Security Attack Module:This module plays a pivotal role in identifying and
mitigating security threats, specifically targeting FGSM and PGD adversarial
attacks on incoming audio inputs. It operates under a defined attacker model,
where such attacks are anticipated during the inference phase, necessitating
robust pre-processing security measures, including encrypted data handling. To
address concerns of potential security breaches, the system is designed to
process encrypted data, maintaining security integrity while effectively
detecting adversarial manipulations.

  4. 4.

Neuromorphic Processor: This module performs advanced neuromorphic
computations, leveraging the distinct capabilities of the SNN detector. While
it receives the processed data and checks for potential FGSM and PGD attacks
using the Perturbation Detector, the SNN detector plays a complementary role.
It is instrumental in initial attack identification and feature extraction,
providing a secondary layer of analysis that works in tandem with SNR
computations. The system processes the input through its layers to produce the
output, and if an attack is detected, it enters a hard reset state with error
flags for FGSM and PGD set. The layers and neurons in this processor are
designed parametrically, allowing for easy configurability across various
application areas and enhancing the system’s capability to identify and
respond to complex security threats. Upon detection of an attack, the module
signals the neuromorphic processor to initiate a hard reset and set
appropriate error flags, thereby preserving the system’s integrity and
responsiveness in the face of sophisticated cyber threats.

  5. 5.

Security Module: Given the sensitivity of neuromorphic computations and the
potential threats they face, a dedicated security module is integrated. This
module encrypts the data using AES encryption before it’s processed, ensuring
data confidentiality.

  6. 6.

Anomaly Detection: Operating in tandem with the security module, the anomaly
detection unit continuously monitors the system’s operations. It identifies
and reports any detected threats or anomalies to the security module, ensuring
the system’s integrity. Our rigorous testing regime, which includes a variety
of attack scenarios, ensures a high threat detection accuracy, mitigating
risks of overfitting.

Our threat model, specifically targeting Gradient-based, PGD, FGSM, and Black-
box Attacks in audio denoising, addresses the nuanced vulnerabilities inherent
in neuromorphic systems. We chose AES encryption for its proven robustness and
security, ensuring data integrity against sophisticated cyber threats, a
priority given the sensitivity of audio data in our application. The
positioning of the anomaly detection module post-encryption strategically
aligns with our security protocol, enabling efficient threat detection without
compromising encrypted data integrity, a critical factor in maintaining
system-wide security and operational efficiency. Our FPGA architecture
underscores the importance of a holistic approach, integrating advanced
neuromorphic processing with robust security measures. By ensuring seamless
interactions between the modules and prioritizing data integrity and security,
the system is poised to deliver efficient and secure neuromorphic
computations.

##  4 Evaluation

Table 2: Our Framework characteristics. Metric | Value
---|---
Sampling Rate | 16000kHz
Resolution | 16 bits
Frequency Response | 8000Hz
Signal-to-Noise Ratio (SNR) | 5.395dB
Total Harmonic Distortion (THD) | 39.50%
Spike Rate | 7994.8spikes/s
Neural Network Topology | SNN
Detection Rate | 94%
False Positive Rate | 6%
Type of Attacks Tested | FGSM, PGD
Encryption Standards | AES

Table 2 delineates the salient features and metrics of proposed framework
underscoring its robustness and precision in neuromorphic audio processing.
Operating at a high sampling rate of 16000kHz and a resolution of 16 bits, the
framework ensures fine-grained audio capture and processing. Its frequency
response, capped at 8000Hz, is aptly tailored for human auditory perception. A
noteworthy metric is the SNR of 5.395dB, indicating a commendable balance
between the desired signal and background noise. While the Total Harmonic
Distortion (THD) at 39.50% suggests the presence of harmonics, the spike rate
of 7994.8 spikes/s accentuates the framework’s efficiency in encoding
information. The adoption of SNNs as the neural network topology further
emphasizes the biological fidelity and energy efficiency of the system. With a
detection rate of 94% and a 6% false positive rate, the framework’s
reliability in adversarial scenarios, especially against FGSM and PGD attacks,
is evident. Moreover, the incorporation of the AES encryption standard
signifies a commitment to data security and integrity, ensuring the secure
transmission and storage of audio data. While AES encryption itself does not
directly counteract adversarial signals affecting the audio-processing neural
network, it plays a crucial role in safeguarding the data against unauthorized
access or tampering. Once securely transmitted and decrypted, our neuromorphic
system, equipped with its robust detection capabilities, efficiently handles
the adversarial attacks, thus providing a comprehensive security solution.

Table 3: Evaluation results on CPU, GPU, and our processor. | i9 12900H (CPU) | RTX 3060 (GPU) | VU37P (FPGA)
---|---|---|---
Technology [nm] | 10 | 8 | 16
Frequency [MHz] | 3700 | 1320 | 100
# of MAC [GOP] | 4.306 | 4.306 | 4.306
Latency [ms] | 395.91 | 16.99 | 72.81
Throughput [GOP/s] | 11.01 | 256.622 | 59.16
Power [Watt] | 20.03 | 69 | 14.53
Power Efficiency [GOP/s/W] | 0.54 | 3.71 | 4.07

Table 3 provides a comprehensive evaluation of three distinct computing
platforms: an i9 12900H CPU, an RTX 3060 GPU, and a VU37P FPGA. The table
encompasses several pivotal metrics, ranging from manufacturing technology and
operating frequency to performance indicators such as latency, throughput, and
power efficiency. GPU stands out with a remarkable 256.622 GOP/s, dwarfing the
CPU’s 11.01 GOP/s and the FPGA’s 59.16 GOP/s. This underscores the GPU’s
prowess in parallel processing capabilities, making it well-suited for tasks
that can exploit such parallelism. The GPU, with its high throughput, consumes
a substantial 69 Watts, whereas the CPU and FPGA consume 20.03 Watts and 14.53
Watts, respectively. However, when evaluating power efficiency, which measures
the performance per unit of power, the FPGA emerges as the most efficient with
4.07 GOP/s/W, slightly surpassing the GPU’s 3.71 GOP/s/W and significantly
outperforming the CPU’s 0.54 GOP/s/W, underlining the suitability of FPGA
devices for tasks where power efficiency is critical. This comparison reveals
the distinctive characteristics and advantages of each technology, and their
appropriateness would largely depend on the specifics of the application at
hand.

Table 4: Comparison of neuromorphic hardware security for audio processing. | [25] | [12] | [24] | Our Framework
---|---|---|---|---
Neural Network Type | RNN | DNN | CNN | SNN
Task | Detecting | Defense | Detecting | Defense
Adversarial Example | FGSM | Carlini and Wagner Attacks | FGSM | FGSM, PGD
SNR (dB) | 12 | 12 | 5.40 | 5.39
Latency [ms] | - | - | - | 72.81
Detection Rate (%) | 93.7 | 93.79 | 93 | 94

Table 4 shows a detailed comparative analysis of neuromorphic hardware
methodologies for audio processing, focusing on their resilience to
adversarial attacks. Different neural network architectures, from RNNs, DNNs,
and CNNs, have been explored, but our introduction of SNNs marks a significant
advancement, given their biological inspiration and energy efficiency. While
various methodologies aim at either detecting or defending against adversarial
inputs, our framework emphasizes a proactive defense, showcasing robustness
against both FGSM and PGD attacks. This robustness is further highlighted by
the SNR values, indicating maintained signal quality amidst adversarial noise.
Additionally, the latency metric in our framework underscores its suitability
for real-time applications. Overall, our methodology, with its integration of
SNNs and comprehensive defense mechanisms, sets a benchmark for adversarial
robustness in neuromorphic audio processing.

##  5 Conclusions

We offer a comprehensive overview of the salient points discussed,
underscoring the paramount importance of security within FPGA-based
neuromorphic systems and delineating potential mitigation strategies. The
integration of SNNs in our framework marks a significant advancement in
neuromorphic audio processing. With its biological inspiration, energy
efficiency, and flawless detection rate, our system sets a benchmark in
adversarial robustness. The inclusion of the AES encryption standard further
emphasizes our commitment to ensuring data security and integrity. Event-
driven audio processing, as discussed, emerges as a promising paradigm,
offering both enhanced security and efficiency. We envision architecting
solutions that ensure efficiency and security by leveraging the advantages of
event-centric systems and neuromorphic architectures. It has been shown that
the VCK190 board employed offers a robust implementation of AI-Engine (AIE)
cores, capable of achieving notable throughput [11, 19]. As a next step of
this research, we intend to further explore and evaluate the proposed
framework within a real-time environment, specifically leveraging the
capabilities of the AIE cores. We anticipate validating these outcomes in an
industrial setting, in collaboration with our funding partners and affiliated
enterprises.

##  6 Acknowledgment

We acknowledge the Temsa Research R&D Center for their generous financial
support and the reviewers for their invaluable insights and suggestions that
significantly contributed to the enhancement of our paper.

## References

  * [1] Bu, T., Ding, J., Hao, Z., Yu, Z.: Rate gradient approximation attack threats deep spiking neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7896–7906 (2023)
  * [2] Chen, X., Li, S., Huang, H.: Adversarial attack and defense on deep neural network-based voice processing systems: An overview. Applied Sciences 11(18), 8450 (2021)
  * [3] Galán, D.G.: Neuromorphic auditory computing: towards a digital, event-based implementation of the hearing sense for robotics. Ph.D. thesis, Universidad de Sevilla (2022)
  * [4] Giannakopoulos, P., Pikrakis, A., Cotronis, Y.: Improving post-processing of audio event detectors using reinforcement learning. IEEE Access 10, 84398–84404 (2022)
  * [5] Gongye, C., Luo, Y., Xu, X., Fei, Y.: Hammerdodger: A lightweight defense framework against rowhammer attack on dnns. In: 2023 60th ACM/IEEE Design Automation Conference (DAC). pp. 1–6. IEEE (2023)
  * [6] Huynh, P.K., Varshika, M.L., Paul, A., Isik, M., Balaji, A., Das, A.: Implementing spiking neural networks on neuromorphic architectures: A review. arXiv preprint arXiv:2202.08897 (2022)
  * [7] Inadagbo, K., Arig, B., Alici, N., Isik, M.: Exploiting fpga capabilities for accelerated biomedical computing. In: 2023 Signal Processing: Algorithms, Architectures, Arrangements, and Applications (SPA). pp. 48–53. IEEE (2023)
  * [8] Isik, M.: A survey of spiking neural network accelerator on fpga. arXiv preprint arXiv:2307.03910 (2023)
  * [9] Isik, M., Inadagbo, K.: Astrocyte-integrated dynamic function exchange in spiking neural networks. In: International Conference on Engineering of Computer-Based Systems. pp. 263–273. Springer (2023)
  * [10] Isik, M., Paul, A., Varshika, M.L., Das, A.: A design methodology for fault-tolerant computing using astrocyte neural networks. In: Proceedings of the 19th ACM International Conference on Computing Frontiers. pp. 169–172 (2022)
  * [11] Jia, X., Zhang, Y., Liu, G., Yang, X., Zhang, T., Zheng, J., Xu, D., Wang, H., Zheng, R., Pareek, S., et al.: Xvdpu: A high performance cnn accelerator on the versal platform powered by the ai engine. In: 2022 32nd International Conference on Field-Programmable Logic and Applications (FPL). pp. 01–09. IEEE (2022)
  * [12] Kwon, H., Yoon, H., Park, K.W.: Poster: Detecting audio adversarial example through audio modification. In: Proceedings of the 2019 ACM SIGSAC conference on computer and communications security. pp. 2521–2523 (2019)
  * [13] Liu, B., Yang, C., Li, H., Chen, Y., Wu, Q., Barnell, M.: Security of neuromorphic systems: Challenges and solutions. In: 2016 IEEE International Symposium on Circuits and Systems (ISCAS). pp. 1326–1329. IEEE (2016)
  * [14] Madden, K., Harkin, J., McDaid, L., Nugent, C.: Adding security to networks-on-chip using neural networks. In: 2018 IEEE Symposium Series on Computational Intelligence (SSCI). pp. 1299–1306. IEEE (2018)
  * [15] Maji, S., Lee, K., Gongye, C., Fei, Y., Chandrakasan, A.P.: An energy-efficient neural network accelerator with improved protections against fault-attacks. In: ESSCIRC 2023- IEEE 49th European Solid State Circuits Conference (ESSCIRC). pp. 233–236 (2023). https://doi.org/10.1109/ESSCIRC59616.2023.10268746
  * [16] Marchisio, A., Pira, G., Martina, M., Masera, G., Shafique, M.: Dvs-attacks: Adversarial attacks on dynamic vision sensors for spiking neural networks. In: 2021 International Joint Conference on Neural Networks (IJCNN). pp. 1–9. IEEE (2021)
  * [17] Merchant, F.: Security as an important ingredient in neuromorphic engineering. In: 2022 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). pp. 314–319. IEEE (2022)
  * [18] Peng, H., Zhou, S., Luo, Y., Xu, N., Duan, S., Ran, R., Zhao, J., Wang, C., Geng, T., Wen, W., et al.: Pasnet: Polynomial architecture search framework for two-party computation-based secure neural network deployment. In: 2023 60th ACM/IEEE Design Automation Conference (DAC). pp. 1–6. IEEE (2023)
  * [19] Perryman, N., Wilson, C., George, A.: Evaluation of xilinx versal architecture for next-gen edge computing in space. In: 2023 IEEE Aerospace Conference. pp. 1–11. IEEE (2023)
  * [20] Salehi, S., Sheaves, T., Gubbi, K.I., Beheshti, S.A., PD, S.M., Rafatirad, S., Sasan, A., Mohsenin, T., Homayoun, H.: Neuromorphic-enabled security for iot. In: 2022 20th IEEE Interregional NEWCAS Conference (NEWCAS). pp. 153–157. IEEE (2022)
  * [21] Sepulveda, J., Reinbrecht, C., Diguet, J.P.: Security aspects of neuromorphic mpsocs. In: 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). pp. 1–6. IEEE (2018)
  * [22] Staudigl, F., Fetz, T., Pelke, R., Sisejkovic, D., Joseph, J.M., Pöhls, L.B., Leupers, R.: Fault injection in native logic-in-memory computation on neuromorphic hardware. arXiv preprint arXiv:2302.07655 (2023)
  * [23] Tayarani-Najaran, M.H., Schmuker, M.: Event-based sensing and signal processing in the visual, auditory, and olfactory domain: A review. Frontiers in Neural Circuits 15, 610446 (2021)
  * [24] Yang, C.H., Qi, J., Chen, P.Y., Ma, X., Lee, C.H.: Characterizing speech adversarial examples using self-attention u-net enhancement. In: ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 3107–3111. IEEE (2020)
  * [25] Yang, Z., Li, B., Chen, P.Y., Song, D.: Characterizing audio adversarial examples using temporal dependency. arXiv preprint arXiv:1809.10875 (2018)
  * [26] Zhou, T., Luo, Y., Ren, S., Xu, X.: Nnsplitter: An active defense solution to dnn model via automated weight obfuscation. arXiv preprint arXiv:2305.00097 (2023)


# On Coding for an Abstracted Nanopore Channel for DNA Storage

Reyna Hulett, Shubham Chandak, and Mary Wootters  Computer Science Department,
Stanford University<EMAIL_ADDRESS>RH’s research supported in part by
a NSF Graduate Research Fellowship under grant DGE-1656518. Electrical
Engineering Department, Stanford University<EMAIL_ADDRESS>Computer
Science and Electrical Engineering Departments, Stanford University.
<EMAIL_ADDRESS>RH and MW’s research supported in part by NSF grants
CCF-1844628 and SemiSynBio-1807371.

(January 2021)

###### Abstract

In the emerging field of DNA storage, data is encoded as DNA sequences and
stored. The data is read out again by sequencing the stored DNA. Nanopore
sequencing is a new sequencing technology that has many advantages over other
methods; in particular, it is cheap, portable, and can support longer reads.
While several practical coding schemes have been developed for DNA storage
with nanopore sequencing, the theory is not well understood. Towards that end,
we study a highly abstracted (deterministic) version of the nanopore
sequencer, which highlights key features that make its analysis difficult. We
develop methods and theory to understand the capacity of our abstracted model,
and we propose efficient coding schemes and algorithms.

##  1 Introduction

In the emerging field of DNA storage, data is encoded as DNA sequences and
stored; the data can be read back by sequencing the stored DNA. This
technology promises high storage density and stability, as well as efficient
duplication of data and random access using PCR-based technologies; we refer
the reader to [4] and the references therein for an excellent overview.

Both the synthesis and sequencing processes are noisy, and as a result the
data must be encoded before the synthesis stage to ensure accurate data
recovery. Prior work has studied methods for encoding data in order to protect
it against (aspects of) the noise introduced by these processes, for example
[10, 3, 7, 22, 17, 14, 15, 5].

In this work, we focus on one particular stage of this noisy process, the
nanopore sequencer. Nanopore sequencing—and in particular the MinION sequencer
developed by Oxford Nanopore Technologies [12]—is an emerging sequencing
technology. While initial works in DNA storage used Illumina sequencing,
nanopore sequencing has been attracting interest due to its portability, low
cost, and ability to support significantly longer reads than Illumina.

At a high level, the nanopore sequencer works as follows. A single strand of
DNA is passed through a pore, leading to variations in a current readout. The
pore can hold $k$ nucleotides (for our purposes, a nucleotide is just a value
in $\\{A,C,G,T\\}$) at a time; in practice $k$ is about six. The value of the
current readout depends on which nucleotides are in the pore. For example, if
the strand of DNA is AGCTAAT, and the pore sees the sub-strand AGCT, it will
output one current reading. As the strand is passed through the pore, the
contents of the pore will shift, say from AGCT to GCTA, then to CTAA, then to
TAAT, and so on. This will result in a change in the current reading,
according to some function $f$ that maps $k$-mers to current levels. The
process is depicted in Figure 1. Given the current readout, the goal is to
recover the original DNA sequence.

$k$ bases in the pore at a time $T$$G$$A$$C$$C$$G$$T$$A$timecurrent Figure 1:
High-level view of the nanopore sequencer.

This channel is difficult to analyze, for several reasons. First, the output
at any given time depends on $k>1$ bases, and so there is inter-symbol
interference. Second, there may be collisions in the output: two different
pore contents may lead to similar current readouts. Third, the current readout
can be noisy. Fourth, the amount of time that each $k$-mer spends in the pore
can vary, and sometimes never occur at all, leading to synchronization errors
in the output.

Due to this complexity, typical basecallers (that is, methods for recovering
the original sequence from the current readouts) rely on machine learning
techniques [21, 9, 20]. This is effective in practice, but difficult to get a
theoretical handle on. While there are several practical approaches to error
correction for nanopore sequencing in DNA storage [22, 17, 14, 15, 5], the
theoretical limits of this channel are not well understood. The work [16],
discussed more below, proposed a probabilistic model of the nanopore sequencer
and developed bounds on the capacity of the resulting channel. However, this
problem is quite difficult; in particular, taking into account the possibility
of synchronization errors places this problem as more difficult than
determining the capacity of the deletion channel, a notorious open problem.

In this work, we take a different approach to developing a theoretical
understanding of the nanopore sequencer. We develop a highly abstracted,
deterministic model, which is meant to highlight the first two sources of
noise mentioned above: the inter-symbol interference, and the prospect of
collisions when multiple $k$-mers lead to similar current outputs. We develop
methods and theory to understand the capacity of our abstracted channel, and
we propose efficient coding schemes and algorithms.

Our goal in this work is to open up a research direction towards a theoretical
understanding of the nanopore sequencer. We fully acknowledge that our work is
not yet practical; in particular our abstracted channel does not include noise
in the current readings or synchronization errors that can arise from variable
pore dwelling times. It is our hope that a solid understanding of our
abstracted channel can then be combined with (much more well-studied) theories
of coding for substitution and synchronization errors, in order to make
progress on a more realistic channel model.

Contributions. Our contributions are as follows.

  1. 1.

We propose a novel abstraction of the nanopore sequencer, which highlights the
inter-symbol interference and the prospect of collisions. This abstraction is
simple enough that it is tractable, yet complex enough that it (a) captures
some fundamental properties of the nanopore sequencer, and (b) already gives
rise to extremely interesting problems from a theoretical perspective. We hope
that our abstraction will lead to future work in this area.

  2. 2.

In Section 3, we develop an algorithm to determine the capacity of this
channel. The algorithm is inefficient as pore size $k$ grows, but we can use
it to determine the capacity for small $k$.

  3. 3.

In Section 4, we develop simple bounds on the “best” and “worst” capacity for
an arbitrary pore size $k$ (where “best” and “worst” refers to the choice of
the map from $k$-mers to current readouts). We use our algorithms mentioned
above to compare these bounds to the exact values for $k=2$. These preliminary
results suggest there may be some intriguing “bumpiness” in the worst-case
capacity as the number of distinct current levels increases, but that the
average-case is closer to best- than worst-case.

  4. 4.

In Section 5, we develop efficient coding schemes for our abstracted channel.
In particular, we develop a scheme that achieves rate $C_{f}-\epsilon$, where
$C_{f}$ is the capacity, that requires preprocessing time
$O\left(\frac{1}{\epsilon}\cdot 4^{1/\epsilon}\right)$, and has
encoding/decoding time $O(n)$, where the $O(\cdot)$ notation hides a constant
that depends on $f$. We also present an efficient coding scheme that improves
over the “naive” one with high probability, where the probability is over a
random map from $k$-mers to current readouts.

###  1.1 Related Work

DNA storage has been around as an idea since the 1960’s, and there has been
renewed interest in it in the past decade, starting with the works [6, 10]. We
refer the reader to [4] for an excellent survey on DNA storage. Most works on
DNA storage have focused on other sequencing technologies like Illumina, but
starting with the work of [22], there have been several works which developed
practical DNA storage systems for nanopore sequencers, including [22, 17, 14,
15, 5]. All of these works developed practical coding schemes for DNA storage
with a nanopore sequencer, but did not explicitly model the sequencer or
analyze the theoretical limits.

Perhaps the work most related to ours is that of [16], who also developed a
model of the nanopore sequencer and studied the capacity of their model. In
particular, they give a multi-letter capacity formula for their channel, and
derive computable bounds for the capacity, in terms of a Markov transition
matrix $P$ that captures the probability of transitioning from one $k$-mer to
the next in the pore. Our work complements that work by focusing on different
aspects of the problem. In more detail, that work differs from ours in several
ways. First, the model in [16] is stochastic, while ours is deterministic. As
a result, they take an information-theoretic approach, while our approach is
more combinatorial in nature. Second, their model includes the possibility
that $k$-mers might get dropped; in particular, the binary deletion channel
appears as one part of their model. Since understanding the capacity of the
binary deletion channel is a difficult open problem, this makes their problem
extremely difficult. In contrast, we ignore this aspect in order to more
cleanly focus in on the effects of the inter-symbol interaction and the
potential confusability between the $k$-mers. Third, that work focuses on the
nanopore sequencer for general applications (not necessarily for DNA storage),
and in particular does not consider efficient coding schemes for their model.
Finally, that work derives bounds on the channel capacity for a particular
choice of (a stochastic analog of) the map $f$ from $k$-mers to current
levels, derived from experimental data. In contrast, we are interested in
results for any $f$, and in particular for the best and worst such functions
$f$. While the former direction is obviously of immediate interest for
existing technology, it is our hope that understanding how the capacity of the
channel changes with $f$ could perhaps guide how nanopore technology is
developed in the future. We note that this is still an emerging area and the
technology is evolving; see [11] for an overview of recent advances.

##  2 Abstract Model of Nanopore Sequencer

In this section we formalize our model. As mentioned above, our goal is to
focus on the challenges of (1) inter-symbol interference, and (2) the
possibility of different $k$-mers producing similar current readouts. With
that in mind, we propose a very simple model for the nanopore sequencer. As
input, we take an encoded string $s_{0}s_{1}\cdots
s_{n-1}\in\\{A,C,G,T\\}^{n}$. This is transformed into a sequence of $k$-mers
according to a sliding window, to obtain $(s_{0}\cdots s_{k-1}),(s_{1}\cdots
s_{k}),(s_{2}\cdots s_{k+1}),\ldots,(s_{n-k}\cdots s_{n-1})$. Finally, each of
these $k$-mers is mapped to one of $b$ distinct current levels, according to a
mapping $f:\\{A,C,G,T\\}^{k}\to\\{0,1,\ldots,b-1\\}$. This mapping $f$ defines
the channel.

######  Definition 1 (Abstract Nanopore Channel).

Given a mapping $f:\\{A,C,G,T\\}^{k}\to\\{0,1,\dots,b-1\\}$ from $k$-mers to
current levels, let $f^{*}:\\{A,C,G,T\\}^{*}\to\\{0,1,\dots,b-1\\}^{*}$
represent the mapping from DNA strands to their full current readout, i.e.,

$f^{*}(s_{0}s_{1}\cdots s_{n-1})=f(s_{0}\cdots s_{k-1})\circ f(s_{1}\cdots
s_{k})\circ\cdots\circ f(s_{n-k}\cdots s_{n-1}).$

We call $f^{*}$ the abstract nanopore channel given by $f$.

Given a mapping $f$, we are interested in the capacity $C_{f}$ (in bits-per-
base), which we define as follows.

######  Definition 2.

Let $f:\\{A,C,G,T\\}^{k}\to\\{0,1,\ldots,b-1\\}$. The capacity $C_{f}$ of the
abstract nanopore channel determined by $f$ is defined as

$C_{f}=\lim_{n\to\infty}\frac{\log{|\\{c\in\\{0,1,\dots,b-1\\}^{n-k+1}\mid\exists
s\in\\{A,C,G,T\\}^{n}\text{ s.t. }f^{*}(s)=c\\}|}}{n}.$ (1)

Observe that if $\mathcal{S}$ is a collection of strings
$s\in\\{A,C,G,T\\}^{n}$ so that $f^{*}(s)$ are all distinct for
$s\in\mathcal{S}$, then by assigning a different message to each
$s\in\mathcal{S}$, we can communicate perfectly (if not necessarily
efficiently) across the abstract nanopore channel.

We will focus on balanced mappings $f$. These are mappings so that
$|f^{-1}(i)|$ is the same for all $i\in\\{0,1,\ldots,b-1\\}$.

##  3 Computing the Capacity

Our first contribution is an algorithm (Algorithm 1 below) that computes
$C_{f}$, given $f$. The basic idea is to consider a finite automaton on the
alphabet $\\{0,1,\dots,b-1\\}$ that accepts exactly those current readouts
that can be generated by some DNA strand; then we use the transfer matrix
method [2, 8] for counting accepting paths in that finite automaton.

Formally, an Nondeterministic Finite Automaton (NFA) is a tuple
$(Q,\Sigma,\Delta,Q_{0},F)$ where $Q$ is the set of states, $\Sigma$ is the
alphabet, $\Delta:Q\times\Sigma\to 2^{Q}$ is the transition function,
$Q_{0}\subseteq Q$ is the set of initial states, and $F\subseteq Q$ is the set
of accepting states. Likewise, a Deterministic Finite Automaton (DFA) is a
tuple $(Q,\Sigma,\delta,q_{0},F)$, defined analogously except that
$\delta:Q\times\Sigma\to Q$ is the transition function and there is only a
single initial state $q_{0}$.

We consider the NFA $M$ and the DFA $M^{\prime}$ described in Algorithm 1. The
NFA $M$ has states indexed by strings in $\\{A,C,G,T\\}^{k-1}$ and alphabet
$\Sigma=\\{0,1,\ldots,b-1\\}$, the current levels. Given a state $(s_{0}\cdots
s_{k-2})$ and an input current level $i\in\Sigma$, the NFA $M$ can transition
to any other state of the form $(s_{1}\cdots s_{k-1})$ so that
$f(s_{0}s_{1}\cdots s_{k-1})=i$. All states are accepting states. By
construction, a sequence of current readings $c\in\Sigma^{n-k+1}$ can be an
output $f^{*}(s_{0}s_{1}\cdots s_{n-1})$ of the nanopore sequencer if and only
if $c$ is accepted by $M$. The DFA $M^{\prime}$ accepts exactly the same
strings as $M$, and is obtained using the classic subset construction [18],
such that each state of the DFA corresponds to a subset of the states of the
NFA.

The transfer matrix method is a method for obtaining a generating function
$g_{f}(z)$ for the number of states accepted by a given DFA. In more detail,
given the transfer matrix $T$ for the automaton (so that $T_{i,j}$ is the
number of transitions from state $i$ to state $j$), the transfer matrix method
gives an expression for a function $g_{f}(z)$ (in terms of the matrix $T$), so
that

$g_{f}(z)=\sum_{m=0}^{\infty}N_{m}z^{m},$

so that $N_{m}$ is the number of strings of length $m$ accepted by the finite
automaton. We will use the notation $[z^{m}]g_{f}(z)$ to denote the
coefficient $N_{m}$ on $z^{m}$.

######  Lemma 1 (Transfer Matrix Method [2]).

Given a DFA $D=(Q,\Sigma,\delta,q_{0},F)$, let $D^{\prime}=(Q\cup
q_{F},\Sigma\cup\lambda,\delta^{\prime},q_{0},\\{q_{F}\\})$ be obtained from
the DFA $D$ by adding a new state $q_{F}$ and new symbol $\lambda$, along with
$\lambda$-transitions from each of the accepting states of $D$ to $q_{F}$. Let
$T$ be the transfer matrix of $D^{\prime}$, where $T_{ij}$ is the number of
transitions from state $i$ to state $j$, with $q_{0}$ being state $0$ and
$q_{F}$ being state $|Q|$. Then the generating function for $D^{\prime}$ is

$g_{f}(z)=(-1)^{|Q|}\times\frac{\det(I-zT:|Q|,0)}{z\det(I-zT)}$

where $(I-zT:|Q|,0)$ is the minor of index $|Q|,0$, i.e., the matrix $I-zT$
with the $|Q|^{th}$ row and $0^{th}$ column deleted.

In our case, the number of strings of length $m$ accepted by our finite
automaton will be the number of current readouts of length $m=n-k+1$ that can
be generated by some DNA strand of length $n$.

From $g_{f}(z)$, we can derive the asymptotic behavior of the number of
possible current readouts required to determine $C_{f}$. As shown in the proof
below, it is related to the smallest positive singularity of $g_{f}(z)$.

$Q\leftarrow\\{A,C,G,T\\}^{k-1}$

$\Sigma\leftarrow\\{0,1,\dots,b-1\\}$

NFA $M\leftarrow(Q,\Sigma,\Delta,Q,Q)$ where $\Delta(s_{0}\cdots
s_{k-2},i)=\\{s_{1}\cdots s_{k-1}\mid f(s_{0}s_{1}\cdots s_{k-1})=i\\}$

DFA $M^{\prime}\leftarrow(2^{Q},\Sigma,\delta,q_{0},F)$ obtained from the
subset construction on $M$

$M^{\prime}\leftarrow(2^{Q}\cup\\{q_{F}\\},\Sigma\cup\\{\lambda\\},\delta^{\prime},q_{0},\\{q_{F}\\})$
where  $\delta^{\prime}(q,\sigma)=\begin{cases}\delta(q,\sigma)&q\in
2^{Q}\text{ and }\sigma\neq\lambda\\\ q_{F}&q\in F\text{ and
}\sigma=\lambda\\\ \emptyset&\text{otherwise}\end{cases}$

$T\leftarrow$ transfer matrix of $M^{\prime}$, i.e., $T_{i,j}=$ number of
transitions from state $i$ to state $j$

$g_{f}(z)\leftarrow(-1)^{2^{|Q|}}\times\frac{\det(I-zT:2^{|Q|},0)}{z\det(I-zT)}$
where $(I-zT:2^{|Q|},0)$ is the minor of index $2^{|Q|},0$

$r\leftarrow$ smallest positive real root of the denominator of $g_{f}(z)$
(simplified)

return $\log\frac{1}{r}$

Algorithm 1 Calculate $C_{f}$

######  Theorem 2.

Given a mapping $f:\\{A,C,G,T\\}^{k}\to\\{0,1,\dots,b-1\\}$, Algorithm 1
computes $C_{f}$.

###### Proof.

First, observe that the NFA $M$ accepts exactly those current readouts that
can be generated by some DNA strand under the mapping $f$. For any current
readout accepted by $M$, consider an accepting path $P=s_{0}\cdots
s_{k-2},s_{1}\cdots s_{k-1},\dots,s_{m}\cdots s_{m+k-2}$. Then by
construction, the DNA strand $s_{0}\cdots s_{m+k-2}$ generates that current
readout. In the other direction, for any DNA strand $s_{0}\cdots s_{m+k-2}$,
the path $P$ is an accepting path for $f^{*}(s_{0}\cdots s_{m+k-2})$.

The DFA obtained from the subset construction accepts the same current
readouts as $M$ [18]. Then we apply the transfer matrix method described in
Lemma 1 to obtain the generating function $g_{f}(z)$, which counts the number
of current readouts accepted by $M$.

Finally, we need to extract the asymptotic behavior of $[z^{m}]g_{f}(z)$.
Since $g_{f}(z)$ is a generating function with non-negative coefficients, the
Exponential Growth Formula [8] tells us that
$\limsup_{m\to\infty}\left([z^{m}]g_{f}(z)\right)^{1/m}=1/r$ where $r$ is the
smallest positive singularity of $g_{f}(z)$. Note that the number of possible
current readouts is monotonically non-decreasing in $m$, so the lim sup is
equal to the limit. Therefore, based on equation (1), and the fact that the
length of the current readouts for DNA strands of length $n$ is $m=n-k+1$,

$\displaystyle C_{f}$
$\displaystyle=\lim_{n\to\infty}\frac{\log\left([z^{n-k+1}]g_{f}(z)\right)}{n}$
$\displaystyle=\lim_{n\to\infty}\frac{n-k+1}{n}\log\left([z^{n-k+1}]g_{f}(z)\right)^{1/(n-k+1)}$
$\displaystyle=\log\frac{1}{r}$

∎

###  3.1 Complexity of Algorithm 1

Unfortunately, the DFA obtained from the subset construction has $2^{4^{k-1}}$
states, so the runtime of Algorithm 1 is exponential in the problem size
(i.e., the description length of $f$).

It is possible that calculating $C_{f}$ may be hard, because computing such a
statistic for NFAs _in general_ is PSPACE-complete [19]. Specifically, even
determining whether $C_{f}=\log b$ for $b=2$ or 4 ($C_{f}=\log b$ is the
highest possible capacity over all mapping functions $f$; see Lemma 5) is
equivalent to determining whether the corresponding NFA is universal (i.e.,
accepts every string in the alphabet). We make this precise in the following
lemma.

######  Lemma 3.

For $b=2$ or $4$ and any $f$, $C_{f}$ is equal to $\log b$ if and only if
every current readout in $\\{0,1,\dots,b-1\\}^{*}$ can be generated by some
DNA strand.

###### Proof.

First we verify the “if” direction. Indeed, if every current readout can be
generated, then $C_{f}=\lim_{n\to\infty}\frac{\log b^{n-k+1}}{n}=\log b$.

To show the “only if” direction we show the contrapositive. Suppose there is
some current readout $c$ of length $\ell$ which cannot be generated by any DNA
strand. Observe that any current readout which contains $c$ as a contiguous
substring can also not be generated by any DNA strand (otherwise we could
generate $c$ by truncation). Thus, consider any current readout of length
$n-k+1$ which _can_ be generated by some DNA strand. If we divide it up into
sections of length $\ell$, obviously none of those sections can be equal to
$c$. So we see that

$\displaystyle C_{f}$
$\displaystyle\leq\lim_{n\to\infty}\frac{\log\left((b^{\ell}-1)^{\lfloor\frac{n-k+1}{\ell}\rfloor}\
b^{(n-k+1)\bmod\ell}\right)}{n}$
$\displaystyle=\lim_{n\to\infty}\frac{\lfloor\frac{n-k+1}{\ell}\rfloor\log(b^{\ell}-1)}{n}$
$\displaystyle=\frac{1}{\ell}\log(b^{\ell}-1)<\log b.$

∎

Since universality is PSPACE-complete for general NFAs, an efficient algorithm
would have to in some way leverage the highly structured nature of the NFAs
corresponding to some mapping $f$.

######  Remark 4.

Although we currently don’t know how to calculate (or approximate) $C_{f}$
efficiently, it is possible to approximate the capacity for strands of fixed
length $\ell$, $C_{f}(\ell)$. Specifically, there are existing randomized
approximation algorithms for counting the number of strings of a given length
accepted by an NFA, in time polynomial in $\ell$ and the size of the NFA [13,
1].

##  4 Bounding the Capacity

The above approach for computing $C_{f}$ exactly given a mapping $f$ is only
practical for small window sizes $k$. However, we can derive some general
bounds that apply to any mapping $f$. In particular, we are interested in the
worst-case mapping $f$ (e.g., the one that attains $\min_{f}C_{f}$), as well
as the best-case mapping $f$ (e.g., the one that attains $\max_{f}C_{f}$). We
prove the following lemma.

######  Lemma 5.

For a given window size $k$ and with $b$ distinct current levels, we have the
following bounds on $C_{f}$:

  1. 1.

$\max_{f}C_{f}=\min(\log(b),2)$

  2. 2.

$\min_{f}C_{f}\geq\frac{\log(b)}{k}$

  3. 3.

$\min_{f}C_{f}\leq 1$ when $b\leq 2^{k}$

###### Proof.

We prove each bound independently:

  1. 1.

Observe that the the size of the set in the numerator of equation (1) is
bounded above both by the number of possible current readouts ($b^{n-k+1}$)
and the number of DNA strands ($4^{n}$). Therefore
$\max_{f}C_{f}\leq\min(\log(b),2)$.

Furthermore, this rate is achievable. For $b=2$, it is achieved by, for
instance,

$f(s_{0}\cdots s_{k-1})=\begin{cases}0&\text{if $s_{0}\in\\{A,C\\}$}\\\
1&\text{otherwise}\end{cases}$

since then all possible current readouts are achievable: given
$c\in\\{0,1,\dots,b-1\\}^{n-k+1}$, simply replace all the 0’s with $A$’s and
the 1’s with $G$’s, and add any $k-1$ bases to the end.

For $b\geq 4$, the optimal rate is achieved by any mapping where
$f(s_{0}\cdots s_{k-1})=f(t_{0}\cdots t_{k-1})$ implies $s_{0}=t_{0}$, since
then every DNA strand ending with $k-1$ A’s gives rise to a unique current
readout.

  2. 2.

Regardless of the mapping $f$, we can always generate at least $b^{\lfloor
n/k\rfloor}$ distinct current readouts: any choice of desired $0^{th}$,
$k^{th}$, $2k^{th}$, etc. current readings can be obtained because they
correspond to non-overlapping length-$k$ windows. Thus
$\min_{f}C_{f}\geq\lim_{n\to\infty}\frac{\log b^{\lfloor
n/k\rfloor}}{n}=\frac{\log(b)}{k}$.

  3. 3.

When $b\leq 2^{k}$, we can effectively make the bases $A$ and $C$
indistinguishable from each other, and likewise the bases $G$ and $T$
indistinguishable from each other. Consider any balanced mapping
$f^{\prime}:\\{A,G\\}^{k}\to\\{0,1,\dots,b-1\\}$ — in this case, balanced
means that for each $i$,

$\left\lvert\\{s_{0}\cdots s_{k-1}\in\\{A,G\\}^{k}\mid f^{\prime}(s_{0}\cdots
s_{k-1})=i\\}\right\rvert=2^{k}/b.$

Then define $f(s)=f^{\prime}(s^{\prime})$ where $s^{\prime}$ is obtain from
$s$ by replacing all $C$’s with $A$’s and all $T$’s with $G$’s. Observe that
$f$ is a balanced mapping, and also the size of the set in the numerator of
equation (1) is now at most $2^{n}$. Thus
$\min_{f}C_{f}\leq\lim_{n\to\infty}\frac{\log(2^{n})}{n}=1$.

∎

Combining these bounds, we obtain the plot in Figure 3. One might wonder how
tight the bounds shown in Figure 3 are, and also about where $C_{f}$ lies for
a “typical” mapping function $f$. Using Algorithm 1, we are able to exactly
calculate the maximum, minimum, and average $C_{f}$ for $k=2$, restricted to
balanced mappings. These empirical results are shown in Figure 3.

$1$$2$$0$$1$$2$…$2^{k}$$2^{k+1}$…$4^{k}$bbits-per-base Figure 2: Bounds on the
value of $C_{f}$. The dashed blue line is equal to $\max_{f}C_{f}$. The value
of $\min_{f}C_{f}$ must lie somewhere in the red shaded area.

$1$$2$$4$$8$$16$$0$$1$$2$bbits-per-base Figure 3: For $k=2$, the true
$\max_{f}C_{f}$ (dashed blue), $\min_{f}C_{f}$ (solid red), and
$\mathbb{E}_{f}C_{f}$ (dotted green), superimposed over our bounds from Figure
3.

The lower bound is on $\min_{f}C_{f}$ curious. Our theoretical bounds on
$\min_{f}C_{f}$ are not tight, but the $k=2$ results suggest there may be some
“bumpiness” in the true bound. Also based on the $k=2$ results, it appears
that random (balanced) mappings are closer to the best-case scenario than the
worst-case. Section 5.2 illustrates one coding scheme that takes advantage of
a property shared by most random mappings for $b=2$, and we may hope there
exist more general coding schemes that perform well for random mappings.

##  5 Coding Schemes

In the proof of Lemma 5, we observed that given a mapping $f$ with window size
$k$ and $b$ distinct current levels, we can achieve a rate of
$\frac{\log(b)}{k}$ by coding only on the $0^{th},k^{th},2k^{th},$ etc.
current readings. Here, we propose two generalizations of this trivial scheme
to improve the rate with additional preprocessing based on the mapping $f$.

###  5.1 “Block” Encoding

Instead of coding on non-overlapping windows of length $k$, each of which maps
to one of $b$ current readings, we may instead choose a block length $\ell\geq
k$ and code on non-overlapping blocks of length $\ell$. This requires
precomputing an alphabet $\Sigma(\ell)\subseteq\\{A,C,G,T\\}^{\ell}$ such that
$f^{*}\restriction_{\Sigma(\ell)}$ is an injective function with the same
range as $f^{*}\restriction_{\\{A,C,G,T\\}^{\ell}}$. That is, each DNA strand
in $\Sigma(\ell)$ generates a unique current readout, and together they
generate every possible current readout of length $\ell-k+1$ given the mapping
$f$. Provided our desired strand length $n$ is divisible by $\ell$ or tends to
infinity, this coding scheme obtains the rate

$C_{f}(\ell)=\frac{\log{|\\{c\in\\{0,1,\dots,b-1\\}^{\ell-k+1}\mid\exists
s\in\\{A,C,G,T\\}^{\ell}\text{ s.t.
}f^{*}(s)=c\\}|}}{\ell}=\frac{\log|\Sigma(\ell)|}{\ell}$

Since $\lim_{\ell\to\infty}C_{f}(\ell)=C_{f}$, it is possible to get
arbitrarily close to the optimal rate by picking a sufficiently large $\ell$.

######  Theorem 6.

Given a mapping $f$, for all $\epsilon>0$, there is a coding scheme achieving
rate $C_{f}-\epsilon$ with linear time encoding and decoding that requires
preprocessing time $O(\frac{1}{\epsilon}\cdot 4^{1/\epsilon})$, where the
$O(\cdot)$ notation hides constants that may depend on the mapping $f$.

###### Proof.

We will exhibit such a scheme by choosing an appropriate block length $\ell$.
Let $|\Sigma(\ell)|$ be the number of distinct current readouts that can be
generated from DNA strands of length $\ell$. Equivalently,
$|\Sigma(\ell)|=[z^{\ell-k+1}]g_{f}(z)$ is the number of current readouts of
length $\ell-k+1$ accepted by the NFA $M$ constructed by Algorithm 1. Because
$g_{f}(z)$ is a counting function for a regular language, and because
$[z^{\ell-k+1}]g_{f}(z)$ is non-decreasing in $\ell$, the asymptotic behavior
of $[z^{\ell-k+1}]g_{f}(z)$ has a simple form ([8], Theorem V.3):

$|\Sigma(\ell)|=[z^{\ell-k+1}]g_{f}(z)=\Theta(\Pi(\ell-k+1)(2^{C_{f}})^{\ell-k+1})$

where $\Pi(x)$ is a polynomial.

Thus, there must exist some $\ell_{0}$ and some constant $C$ depending only on
the mapping $f$, such that for all $\ell\geq\ell_{0}$, $|\Sigma(\ell)|\geq
C(2^{C_{f}})^{\ell-k+1}$. Therefore, if we choose
$\ell\geq\max\left(\ell_{0},\frac{C_{f}\cdot(k-1)-\log C}{\epsilon}\right)$,
we see that

$\displaystyle C_{f}(\ell)$ $\displaystyle=\frac{\log|\Sigma(\ell)|}{\ell}$
$\displaystyle\geq\frac{\log\left(C(2^{C_{f}})^{\ell-k+1}\right)}{\ell}$
$\displaystyle=\frac{\log C+C_{f}\cdot(\ell-k+1)}{\ell}$
$\displaystyle=C_{f}-\frac{C_{f}\cdot(k-1)-\log C}{\ell}$ $\displaystyle\geq
C_{f}-\epsilon.$

Therefore, to achieve rate $C_{f}-\epsilon$, we should choose $\ell$
proportional to $1/\epsilon$, with the constants depending only on the mapping
$f$.

Given the block length $\ell$, we now describe how to compute the alphabet
$\Sigma(\ell)$. We will construct an array $E$ containing the alphabet
$\Sigma(\ell)$ and a hash table $D$ mapping current readouts of length
$\ell-k+1$ to the index in $E$ of the DNA strand that generates that readout.

For each DNA strand $s$ of length $\ell$, compute $f^{*}(s)$. If $f^{*}(s)$
has not yet been added to the hash table $D$, append $s$ to the end of array
$E$ and map $f^{*}(s)$ to the appropriate index. This preprocessing takes
$O(\ell)$ time for each of $4^{\ell}$ DNA strands, for a total of $O(\ell\cdot
4^{\ell})=O(\frac{1}{\epsilon}\cdot 4^{1/\epsilon})$.

Encoding and decoding are then quite straightforward: Convert the message to
base $|\Sigma(\ell)|$ and use lookup table $E$ to map each digit to a block of
length $\ell$. Similarly, decode each block of $\ell-k+1$ current readings
using the hash table $D$ (skipping the $k-1$ readings that straddle each pair
of adjacent blocks). ∎

As an example, consider the case when $b=2$ or $4$ and $f$ is any mapping with
the highest-possible capacity $C_{f}=\log b$. Per Lemma 3, this implies that
every current readout can be generated by some DNA strand, so
$|\Sigma(\ell)|=b^{\ell-k+1}$ and
$C_{f}(\ell)=\frac{(\ell-k+1)\log(b)}{\ell}$. In this case, we can calculate
the dependence of $\ell$ on $\epsilon$ exactly:

$\displaystyle C_{f}-\epsilon$ $\displaystyle=\frac{(\ell-k+1)\log(b)}{\ell}$
$\displaystyle-\epsilon$ $\displaystyle=\frac{(-k+1)\log(b)}{\ell}$
$\displaystyle\ell$ $\displaystyle=\frac{(k-1)\log(b)}{\epsilon}.$

For instance, when $k=2,b=2,$ and $\epsilon=0.1$, we would require $\ell=10$.

###  5.2 “Greedy” Encoding

Alternatively, instead of changing the lengths of the blocks used in the
trivial scheme, we may relax the “non-overlapping” requirement.

This may not always be possible, depending on the mapping $f$. Indeed, in the
worst case, it is possible that once you have fixed the first $k$ bases, the
next $k-1$ current readings may also be fixed—for instance, if the first $k$
bases are all $A$, and all windows starting with $A$ map to the same current
level. However, this pessimal case shouldn’t happen for most mappings.

Consider the case of $b=2$ current levels, and suppose that for some length
$1\leq\ell<k$, for every “prefix” $p\in\\{A,C,G,T\\}^{\ell}$, at least one
window in $f^{-1}(0)$ _and_ at least one window in $f^{-1}(1)$ starts with
that prefix. Then it is possible to have every $(k-\ell)^{th}$ current reading
code for one binary symbol independently. This would give us a rate of
$\frac{1}{k-\ell}$ rather than $\frac{1}{k}$. Such an event is not too
unlikely with a random mapping $f$.

######  Lemma 7.

Given a random mapping $f$ with $b=2$ distinct current levels and a length
$1\leq\ell<k$, $f$ admits the coding scheme described above with rate
$\frac{1}{k-\ell}$ with probability at least

$1-4^{\ell}\cdot 2\cdot\left(\frac{1}{2}\right)^{4^{k-\ell}}.$

Furthermore,

  1. 1.

we can determine whether such a scheme exists for a given $f$ and $\ell$ in
$O(4^{k})$.

  2. 2.

we can find the maximum $\ell$ for which such a scheme exists for a given $f$
in $O(k4^{k})$.

  3. 3.

we can implement such a scheme with $O(k4^{k})$ preprocessing and linear
encoding and decoding.

###### Proof.

Let $f$ be a uniformly random mapping from $\\{A,C,G,T\\}^{k}\to\\{0,1\\}$
(not necessarily balanced). For a given prefix $p$ of length $\ell$ and
current level $\beta$, the probability that all $4^{k-\ell}$ windows beginning
with that prefix belong to $f^{-1}(\beta)$ is
$\left(\frac{1}{2}\right)^{4^{k-\ell}}$. Thus by the union bound, the
probability of being able to execute this scheme for a given length $\ell$ is
at least

$1-4^{\ell}\cdot 2\cdot\left(\frac{1}{2}\right)^{4^{k-\ell}}.$

This probability would only be higher if we restrict $f$ to be a random
balanced mapping.

Given a specific mapping $f$ and desired length $\ell$, we can trivially check
whether this property is satisfied by checking, for each prefix of length
$\ell$, the current level corresponding to each of the $4^{k-\ell}$ windows
beginning with that prefix, in time $O(4^{k})$.

Naturally, we could determine the maximum $\ell$ that works for a given
mapping $f$ in $O(k4^{k})$ by repeating the above procedure for each
$\ell\in\\{1,2,\dots,k-1\\}$.

Furthermore, such a scheme could be straightforwardly implemented for a given
$f$. For instance, we could construct tries — trie 0 corresponding to
$f^{-1}(0)$ and trie 1 corresponding to $f^{-1}(1)$ — in $O(k4^{k})$. For ease
of encoding, we will also equip each leaf node $s_{0}s_{1}\cdots s_{k-1}$ of
the tries with two pointers, pointing to the internal nodes
$s_{k-\ell}s_{k-\ell+1}\cdots s_{k-1}$ in both trie 0 and trie 1. To encode
from binary to a DNA strand, we then start with any length-$k$ window in the
trie corresponding to the first bit. For each subsequent bit, follow the
pointer from our current leaf to the internal node of the trie corresponding
to that bit, then append an arbitrary path from that prefix to a leaf in the
appropriate trie. Decoding is simply a matter of extracting every
$(k-\ell)^{th}$ current reading. Thus both encoding and decoding are linear in
the length of the DNA strand. ∎

For example, with $k=6,\ell=4$, we see that we can obtain a rate of $1/2$
(compared to the trivial $1/6$) with probability at least $1-\frac{1}{128}$.

##  6 Conclusion

We have initiated a theoretical study of coding for a highly abstracted
version of the nanopore sequencer for DNA storage. We have provided algorithms
and bounds for understanding the capacity, and we have given efficient coding
schemes. However, we view our work as the tip of an iceberg. First, even for
this abstracted model, much remains open. Can one derive better bounds on the
capacity, or compute it efficiently for, say, $k=6$? Second, we hope that our
insights will generalize to more practical models, including with substitution
and synchronization errors.

## References

  * [1] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram and Cristian Riveros “Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation” In _Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , 2019
  * [2] Abdulbaki Aydin, Lucas Bang and Tevfik Bultan “Automata-Based Model Counting for String Constraints” In _Computer Aided Verification_ Cham: Springer International Publishing, 2015, pp. 255–272
  * [3] Meinolf Blawat et al. “Forward error correction for DNA data storage” In _Procedia Computer Science_ 80 Elsevier, 2016, pp. 1011–1022
  * [4] Luis Ceze, Jeff Nivala and Karin Strauss “Molecular digital data storage using DNA” In _Nature Reviews Genetics_ 20.8 Nature Publishing Group, 2019, pp. 456–466
  * [5] Shubham Chandak et al. “Overcoming high nanopore basecaller error rates for DNA storage via basecaller-decoder integration and convolutional codes” In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 8822–8826 IEEE
  * [6] George M Church, Yuan Gao and Sriram Kosuri “Next-generation digital information storage in DNA” In _Science_ 337.6102 American Association for the Advancement of Science, 2012, pp. 1628–1628
  * [7] Yaniv Erlich and Dina Zielinski “DNA Fountain enables a robust and efficient storage architecture” In _Science_ 355.6328 American Association for the Advancement of Science, 2017, pp. 950–954
  * [8] Philippe Flajolet and Robert Sedgewick “Analytic Combinatorics” Cambridge University Press, 2009
  * [9] “Flappie: Flip-flop basecaller for Oxford Nanopore reads” Last accessed: January 2021, https://github.com/nanoporetech/flappie
  * [10] Nick Goldman et al. “Towards practical, high-capacity, low-maintenance information storage in synthesized DNA” In _Nature_ 494.7435 Nature Publishing Group, 2013, pp. 77–80
  * [11] Yusuke Goto, Rena Akahori, Itaru Yanagi and Ken-ichi Takeda “Solid-state nanopores towards single-molecule DNA sequencing” In _Journal of human genetics_ 65.1 Nature Publishing Group, 2020, pp. 69–77
  * [12] Miten Jain, Hugh E Olsen, Benedict Paten and Mark Akeson “The Oxford Nanopore MinION: delivery of nanopore sequencing to the genomics community” In _Genome biology_ 17.1 Springer, 2016, pp. 1–11
  * [13] Sampath Kannan, Z. Sweedyk and Steve Mahaney “Counting and Random Generation of Strings in Regular Languages” In _Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’95 San Francisco, California, USA: Society for IndustrialApplied Mathematics, 1995, pp. 551–557
  * [14] Henry H Lee et al. “Terminator-free template-independent enzymatic DNA synthesis for digital information storage” In _Nature communications_ 10.1 Nature Publishing Group, 2019, pp. 1–12
  * [15] Randolph Lopez et al. “DNA assembly for nanopore data storage readout” In _Nature communications_ 10.1 Nature Publishing Group, 2019, pp. 1–9
  * [16] Wei Mao, Suhas N Diggavi and Sreeram Kannan “Models and information-theoretic bounds for nanopore sequencing” In _IEEE Transactions on Information Theory_ 64.4 IEEE, 2018, pp. 3216–3236
  * [17] Lee Organick et al. “Random access in large-scale DNA data storage” In _Nature biotechnology_ 36.3 Nature Publishing Group, 2018, pp. 242
  * [18] M. O. Rabin and D. Scott “Finite Automata and Their Decision Problems” In _IBM Journal of Research and Development_ 3.2, 1959, pp. 114–125 DOI: 10.1147/rd.32.0114
  * [19] Narad Rampersad, Jeffrey Shallit and Zhi Xu “The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages” In _CoRR_ abs/0907.0159, 2009 arXiv: http://arxiv.org/abs/0907.0159
  * [20] “Scrappie: a technology demonstrator for the Oxford Nanopore Research Algorithms group” Last accessed: January 2021, https://github.com/nanoporetech/scrappie
  * [21] Ryan R Wick, Louise M Judd and Kathryn E Holt “Performance of neural network basecalling tools for Oxford Nanopore sequencing” In _Genome biology_ 20.1 Springer, 2019, pp. 1–10
  * [22] SM Hossein Tabatabaei Yazdi, Ryan Gabrys and Olgica Milenkovic “Portable and error-free DNA-based data storage” In _Scientific reports_ 7.1 Nature Publishing Group, 2017, pp. 1–6