# A Survey on Computing Schematic Network Maps:
The Challenge to Interactivity

Hsiang-Yun Wu  TU Wien, Austria
<EMAIL_ADDRESS>Benjamin Niedermann  University of Bonn, Germany
<EMAIL_ADDRESS>Shigeo Takahashi  University of Aizu, Japan
<EMAIL_ADDRESS>Martin Nöllenburg  TU Wien, Austria
<EMAIL_ADDRESS>
###### Abstract

Schematic maps are in daily use to show the connectivity of subway systems and
to facilitate travellers to plan their journeys effectively. This study
surveys up-to-date algorithmic approaches in order to give an overview of the
state of the art in schematic network mapping. The study investigates the
hypothesis that the choice of algorithmic approach is often guided by the
requirements of the mapping application. For example, an algorithm that
computes globally optimal solutions for schematic maps is capable of producing
results for printing, while it is not suitable for computing instant layouts
due to its long running time. Our analysis and discussion, therefore, focus on
the computational complexity of the problem formulation and the running times
of the schematic map algorithms, including algorithmic network layout
techniques and station labeling techniques. The correlation between problem
complexity and running time is then visually depicted using scatter plot
diagrams. Moreover, since metro maps are common metaphors for data
visualization, we also investigate online tools and application domains using
metro map representations for analytics purposes, and finally summarize the
potential future opportunities for schematic maps.

###### Index Terms:

Metro Maps, Graph Drawing, Metaphors

##  I Introduction

A metro map is a schematic visual representation of an underlying transit
network that depicts the connectivity between metro stations and lines of a
public transportation system [30]. With well-designed metro maps, travellers
can effectively identify their locations and find their way or perform routing
planning on a complex transportation system in a big city, such as London,
Paris, or Tokyo. These maps are especially helpful since travellers often look
for a quick solution for the shortest or cheapest path from station $A$ to
$B$, how to transfer from $A$ to $B$, and how many stations left to $B$ [33].
To support these tasks, Henry Beck introduced the so-called Tube Map of London
Underground, and has proposed several drawing criteria to achieve this [14],
and many extended versions have been evaluated [34][35].

Nonetheless, the need for automatic drawing algorithms is still increasing due
to the high cost and limited adaptability of hand-drawn maps. This has been
considered as a difficult problem because several subproblems, including
layout schematization, line crossing minimisation, and map label placement
have been studied and proved as complex problems [26]. Two state-of-the-art
reports from 2007 and 2014 have surveyed similar approaches before [50][26].
Hence we focus on relatively new approaches from the last 5 years after
Nöllenburg’s report [26] and discuss the correlation in terms of computational
complexity and interactivity, as well as the potential techniques that can be
used in different research domains.

###  I-A Problem Definition

The initial idea for a metro map lies on simplifying the layout geometry to
facilitate users’ comprehensive understanding of connectivity between metro
stations. This allows us to formulate the drawing problem as network
visualization problems, which are often studied to untangle visual clutter of
the layout to improve its readability [51].

#### Metro Map Problem

Let us formulate the metro map problem by introducing an undirected graph
$G=(V,E)$ embedded in a plane $\mathbb{R}^{2}$. Each vertex $v\in V$
represents a metro station and an edge $e=(v_{i},v_{j})\in E$ indicates the
physical connection between two metro stations. In addition, a line $l\in L$
is a metro line containing a set of metro stations and edges that are defined
from the corresponding metro system. Note that $l$ is a set cover, which
implies each edge $e$ belongs to at least one $l\in L$. We call $MG=(G,L)$
here a _Metro Graph_ as previously defined by Nöllenburg [26]. The input of
the proposed problem is the connectivity of a Metro Graph $MG$ together with
its geographically accurate embedding, and the solution aims to find a
schematic layout of $MG$ that maximally satisfies several user-defined
aesthetic drawing criteria.

###  I-B Our Taxonomy Design

In this study, we investigate the trade-off between computation times and
layout quality as well as application requirements. This is motivated by our
observation that a user who is trying to create a map would accept longer
computation times for an exact solution if the generated map is expected to be
printed, while the user will not be patient if the application is expected to
be an interactive application. To investigate our assumption systematically,
we analyze several factors in this survey (see Tables I and III) that
influence the computational complexity and optimality requirements of a
problem together with the corresponding running time of the algorithmic
approach (Table III). Our two primary topics cover algorithmic network layout
techniques and station labeling techniques. The correlation between problem
complexity and time complexity is then given using a scatter plot diagram
visually.

This is done by categorizing publications along two primary coordinates,
problem complexity and running time. These include (1) the range from local to
global optimality in terms of the incorporated aesthetic criteria and
objective functions, and (2) the range of suitability from static to
interactive visualizations based on the computation speed. The values on the
first coordinate are computed using the scoring Tables I and III. For
simplicity, we assume that the degree of interactivity, running time in other
words, of a schematic map algorithm is potentially linearly-correlated to the
degree of criteria selected by the proposed approach. In other words, we
expect the developed techniques would find a good balance between the
efficiency of the algorithms and the quality of the schematic maps generated
by those approaches. For better instructing readers along this assumption, we
will focus our discussion on these two aspects in the following sections.

###  I-C Tasks and Design Rules

It is known that drawing criteria are often designed based on users’
effectiveness to accomplish tasks on a map. These tasks are similar to tasks
on graphs, such as _Topology-Based Tasks_ , _Attribute-Based Tasks_ , and
_Browsing Tasks_ since finding shortest or cheapest paths, identifying a
station of a line, and navigating along a specific route are mostly performed
by the travellers. We revisit Nöllenburg’s list [26] of design principles and
investigate which of these serve as dominant constraints, for generating a
globally optimal map, in the coming sections. In this survey, we primarily
focus on two directions in this field, including network layout techniques (N)
and labeling techniques (L) as summarized in Table I and Table III,
respectively. Note that the selected criteria are ordered in the sense that
the criterion with higher scores influences global structures of the layout,
while the one with lower scores affects the layout in a local fashion. This
scoring scheme will then be used as an indicator for guiding readers to
navigate the diagrams created in the coming sections. Based on the
aforementioned scoring scheme, we derive our novel taxonomy of metro map
techniques in this survey paper.

The remainder of this paper is structured as follows. In Section II, we
summarize relevant schematic network layout algorithms, and in Section III,
research approaches integrating map features, mainly on text and image labels.
In Section IV, we then introduce several tools that are accessible online and
demonstrate the usability of the collected techniques in different research
domains. Finally in Section VI, we conclude this paper and list several future
directions to this topic.

##  II Algorithmic Network Layout Techniques

|
LocalGlobalSlowFast[42][28][49][52][43][29][46][8][9][45][18][39][27][12][48]paper
$\geq 2014$paper $<2014$
---|---
(a) | (b)
Figure 1: Network map visualization, including an example of (1) Vienna metro map [27], and (b) layout techniques with respect to their globality and potential for interactiveness. TABLE I: The point system for evaluating the criterion effectiveness. ID | S | Description (x-coordinate in Figs. 1\- 3)
---|---|---
(N1) |  | Combinatorial property
(N1.1) | 4 | Overall combinatorial optimization.
(N1.2) | 3 | Combinatorial criteria for sets of vertices or edges.
(N1.3) | 2 | Combinatorial criteria for pairs of vertices or edges.
(N1.4) | 1 | Combinatorial criteria for single vertices or edges.
(N2) |  | Geometry property
(N2.1) | 4 | Uniform geometric optimization.
(N2.2) | 3 | Geometric criteria for sets of vertices or edges.
(N2.3) | 2 | Geometric criteria for pairs of vertices or edges.
(N2.4) | 1 | Geometric criteria for single vertices or edges.
(N3) |  | Approach optimality
(N3.1) | 4 | Global optimality and exact global optimization.
(N3.2) | 3 | Global optimality, but local optimization.
(N3.3) | 2 | Local optimality, but global optimality for sub-problems.
(N3.4) | 1 | Local optimality, and local optimization.
TABLE II: The point system for evaluating the time effectiveness. ID | S | Time complexity (y-coordinate in Figs. 1\- 3)
---|---|---
T1 | 4 | The layout is computed less than a second.
T2 | 3 | The layout is computed in a few seconds.
T3 | 2 | The layout is computed within a few minutes .
T4 | 1 | The layout is computed in several hours or more.

In this section we classify the different network layout algorithms proposed
in the literature over the past 15 years along three criteria that determine
the degree of globality of the algorithmic techniques. These criteria comprise
combinatorial properties (N1) of the underlying graph structure (e.g.,
topology preservation), geometric properties (N2) of the input network and the
schematic layout (e.g., directional deviations and line straightness), and the
degree of optimality (N3) of the computed solutions, i.e., whether an global
optimum is computed or just a local optimum. Table I lists the three criteria,
which are ranked by scores ranging from 1 (high locality) to 4 (high
globality). Additionally, we assess each technique by the required
computational resources and resulting degree of suitability for interactive
applications (summarized in Table II).

Each of the papers discussed in the following paragraphs thus receives two
scores that we use as coordinates in the two-dimensional scatter plot of
Figure 1.

We start with four classic papers that serve as representatives of the main
algorithmic techniques that were already discussed in the 2014 survey of
Nöllenburg [26]. Since our focus is on new results from 2014 onward, we refer
to the 2014 survey for a comprehensive discussion of the earlier literature.
The force-based algorithm of Hong et al. [18] considers combinatorial and
geometric parameters of individual and pairs of edges and vertices in their
objective function, e.g., the slope of edges, or the preservation of the local
network topology at each vertex. The objective function considers the sum of
several forces acting upon each vertex to push it toward a state of locally
minimal energy. Layouts are computed within a few seconds.

Stott et al. [39] define an explicit global objective function for metro maps,
which takes smaller values for maps with higher layout quality. This quality
function measures, e.g., angles at each vertex or between neighboring edges,
local edge length differences, or the octilinearity of edges, which
corresponds to a score of 2 in these criteria. The optimization itself is by a
hill climbing algorithm that moves vertices to the best position in a local
neighborhood, but evaluates the global map quality. The reported computation
times range between a few minutes and a few hours.

The mixed-integer linear programming (MIP) approach of Nöllenburg and Wolff
[27] defines combinatorial and geometric constraints among pairs of edges and
vertices to guarantee, e.g., the correct network topology, octilinear edges,
or a bounded amount of angular distortion, as well as the minimization of
bends along lines and subpaths or the total network length. Their solution
model, however, guarantees a globally optimal solution. To achieve this
highest degree of optimality, one needs to invest computation times ranging
from several minutes for simple network maps to several hours for more complex
instances.

Finally, Wang and Chi [48] define an energy function to represent the layout
quality, with the goal of minimizing this energy function. As in the previous
methods, this comprises aspects defined on pairs of vertices and edges such as
edge lengths, angles, or octilinearity. Their optimization aims for global
optimality, but using an iterative conjugate gradient method for least squares
minimization to converge to a global minimum. Their algorithms typically run
in less than a second.

Among the more recent papers, we mostly find approaches that improve and
extend one of the classic techniques like MIP, local optimization heuristics,
force-based iterative methods, or stroke-based incremental algorithms. Chivers
and Rodgers [8] present a hybrid force-based method that defines both a set of
classic spring embedder forces [13] as well as a magnetic force field that
models octilinearity [41]. Their hybrid idea is to first let the spring forces
find a well distributed layout and then let the magnetic forces become
dominant to achieve octilinear edges. By the nature of their method they aim
for locally optimal stable layouts, but the convergence is quite fast and
typical metro maps can be computed in less than a second. A second and very
fast approach with similar properties is given by van Dijk and Lutz [45]. They
propose a method based on linearized least-squares minimization as an
approximation of a non-linear model for computing linear cartograms, which are
network drawings with prescribed edge lengths. This idea is then applied to
metro map layout as one problem instance, where the length and slope of edges
are soft constraints to be optimized. While several typical constraints of
metro maps are not considered in their algorithm, it is an extremely fast
technique with running times in the range of a few milliseconds. Wang and Peng
[49] provide another system using a global energy function whose minima
correspond to locally optimal metro layouts in their model. The optimization
technique is least-squares minimization. It comprises both octilinear and
curvilinear layouts and is designed for interactive editing by a user who can
modify the positions of a few _handle_ vertices. It is very fast and only
requires a few milliseconds to compute medium-sized metro maps.

Three papers take the idea of decomposing the network into paths (also called
_strokes_), computing schematic representations of the strokes and then
composing them into a single network again, see e.g. [20]. Ti and Li [42] and
Ti et al. [43] both propose an approach that first detects and enlarges areas
in the geographically accurate representation of the metro network that have
high vertex or edge density and then apply multifocal fisheye transformations
to get a more uniform spatial distribution of the underlying network. In a
second step, strokes are identified and locally schematized in an octilinear
fashion. While no running times are reported in the papers, these methods are
typically quite fast and run within at most a few seconds. On the other hand,
the schematization only minimizes local distances to the input geometry and no
explicit global objective function is optimized. The algorithm by van Dijk et
al. [46] proposes schematic maps using strokes that are represented as
circular arcs, and not as octilinear paths. They first simplify sequences of
edges of the same metro line into longer paths, even across junctions, to
reduce overall complexity of the layout and then find locally optimal
representations of these paths/strokes by circular arcs guided by the Fréchet
distance between paths and circular arcs.

Chivers and Rodgers [9] extend the search space of the hill climbing local
search technique [39] by parameterizing grid spacing, local neighborhood size
for node movements, and the number of iterations. The constraints and
objectives are the same as those by Stott et al. [39]. With their improvements
they gain a speed-up factor between 5 and 8 compared to the earlier multi-
criteria hill climbing technique [39] and obtain the final (labeled) layouts
within 5 to 60 minutes.

Finally, the MIP model has been improved and accelerated by several authors.
Oke and Siddiqui [28] relax some of the integrality constraints of Nöllenburg
and Wolff [27] and drop one term in the objective function. Their model
improves the running time by up to one order of magnitude to computation times
of few minutes. Onda et al. [29] also modify the existing MIP model [27]. They
split the computation into two phases in order to speed up computation of
large instances such as the Tokyo metro map. In the first phase they generate
a rough layout that satisfies all hard constraints in an incremental face-by-
face manner. The second phase optimizes the directions of short subpaths while
keeping the directions of the remaining layout fixed. A layout of the Tokyo
network was computed within 5 hours. Certain topological structures can be
highlighted by Wu et al., who allow for straightening a user-specified path
[55], or deforming a cyclic path into a circle [52] in order to emphasize
meaningful structures. This has been achieved by introducing additional
constraints to the standard MIP model, which increases the time for finding
the corresponding solutions by a small amount. Fink et al. [12] use the MIP
technique to model layout of concentric metro maps, where the network consists
of polylines composed of radial or circular segments. The optimization
considers among others bend minimization, minimization of distinct radial
slopes, or uniformity of edge lengths. The reported running times are in the
range of several minutes for small input maps like Vienna and Montreal.

##  III Labeling Techniques

| LocalGlobalSlowFast[56][25][52][53][55][48][27][7][39][18][54][49]paper
$\geq 2014$paper $<2014$
---|---
(a) | (b)
Figure 2: Labeled network maps, including an example of (1) Vienna metro map with image labels [53], and (b) labeling techniques with respect to their globality and interactiveness. TABLE III: The point system for evaluating the criterion effectiveness. ID | S | Description (x-coordinate in Fig. 2)
---|---|---
(L1) |  | Adjustment of metro maps
(L1.1) | 4 | The layout and label placement is done simultaneously.
(L1.2) | 3 | The layout is uniformly scaled to fit in labels.
(L1.3) | 2 | The directions of the edges are preserved.
(L1.4) | 1 | The layout is not changed when labeling is created.
(L2) |  | Placement of labels
(L2.1) | 4 | Uniform placement.
(L2.2) | 3 | Criteria for sets of labels.
(L2.3) | 2 | Criteria for pairs labels.
(L2.4) | 1 | Criteria for single labels only.
(L2) |  | Optimality
(L3.1) | 4 | Global optimality and exact global optimization.
(L3.2) | 3 | Global optimality, but local optimization.
(L3.3) | 2 | Local optimality, but global optimality for sub-problems.
(L3.4) | 1 | Local optimality, and local optimization.

In this section we discuss the current state on algorithmic labeling
techniques for metro maps. Similarly to Section II, we classify the approaches
with respect to their degree of globality and interactivity; see also Figure
2. We used the following three criteria to decide on the locality of a
labeling approach, including adjustment of metro map (L1), placement of labels
(L2), and optimality (L3) (see also Table III).

For each criterion and each labeling approach we determined the highest score
that suits the approach. The overall degree of globality of a labeling
approach is then the average over its three assigned scores. In order to
decide on the degree of interactivity for each labeling approach, we applied a
similar approach as we did in Section II using Table II. We assigned each
approach to the lowest category that suits the approach best. Altogether, we
obtain a measure for both the degree of globality and interactivity of a
labeling approach, which we depict in Figure 2. In the following we discuss
the single results in increasing order with respect to their degree of
interactivity.

Nöllenburg and Wolff [27] present an approach that creates the layout of the
metro map and the label placement simultaneously. To that end, they present a
mixed integer linear programming formulation that optimally creates a metro
map with respect to a global cost-function. They particularly require that
labels in between two crossings lie on the same side of the metro line.
However, their approach comes with a high running time, e.g., for the metro
system of Sydney they report a running time up to $12$ hours. Stott et al.
[39] present an iterative approach that creates the layout and label placement
in an integrated way using hill climbing based on a global multi-criteria
function. Among other criteria they prefer labels on the same side of the
metro line. They report running times between 2 and 120 minutes.

In contrast, Wu et al. [53] assume when placing labels that the layout is
given. Still, they scale the map to increase free spaces, which they use for
label placement based on a MIP approach. By considering the layout and
labeling step independently, they achieve running times up to minutes. Yoshida
et al. [56] scale single edges of the map while preserving the directions of
the edges. The main idea is to create free spaces in dense parts of the map,
while leaving other parts of the maps unchanged. Similarly to Wu et al. [53],
Niedermann and Haunert [25] systematically scale the map layout to fit in the
labeling. For the labeling procedure they propose a dynamic programming
approach that labels a single metro line optimally. They use this method as a
subroutine of their heuristic, which labels the map within few minutes.

Wu et al. [55] label the stations with photos instead of text labels. They
place the photos alongside two boundaries of the rectangular map and associate
them with their stations via connecting curves, also called _leaders_. They
aim at crossing-free solutions that minimize the length of the leaders. Wu et
al. [52] generalize this approach to all four sides of the map. Wu et al. [54]
separate the labels from the metro map less clearly. They present a genetic
algorithm that places overlap-free text labels and photos within the free
spaces of the metro map connecting the labels with their stations using
straight-line leaders. At the core of the genetic algorithm, which
systematically explores different orders of placing labels, the actual
placement is done by a simple and fast greedy procedure.

Hong et al. [18] separate the placement of the labels from the computation of
the layout. They describe the labeling problem as a conflict graph based on
label candidates and their occlusions. The label placement corresponds to an
independent set of vertices within the graph, which they determine using
simulated annealing. Although they maximize the number of labels, they cannot
guarantee that each station gets a label.

Wang and Chi [48] also separate the placement of labels from the computation
of the metro map layout. They describe the labeling problem as a multi-
criteria energy function, which they locally optimize. Their approach
particularly avoids occlusions between labels and prefers labels on the same
side of the metro line. They report running times below one second, which
makes their approach applicable for interactive real-time scenarios. Wang and
Peng [49] use the same labeling approach for their interactive editing system.

Chivers and Rodgers [7] present an approach that after fixing the metro map
layout selects for each station a label out of eight candidates using a simple
greedy approach. They penalize label occlusions and prefer similarly placed
labels of adjacent stations.

Altogether, we observe that with increasing degree of interactivity the
globality of the approaches decreases. In particular, those approaches that
are applicable for interactive real-world scenarios, typically assume a fixed
metro map layout. While this provides the possibility of computing the label
placement much faster than approaches integrating the process of creating the
layout, the given metro map layout may not host all labels. This is either
resolved by allowing occlusions [48][49] or by labeling only a (possibly
large) subset of stations [18]. Hence, those approaches are far away from
achieving the same quality with respect to the labeling as approaches with a
smaller degree of interactivity. We therefore deem the development of labeling
algorithms with the potential for a high degree of interactivity as a still
open and important research problem.

##  IV Applications and On-line Tools

Schematic network maps have widely been employed for representing abstract
relationships between subjects. In such cases, the schematic maps serve as
visual metaphors that effectively systematize the underlying structures hidden
behind the target information space. In this section, we first focus on
techniques for visualizing abstract information space using schematic map
metaphors and then raise representative on-line tools for designing such maps.

| LocalGlobalSlowFast[40][6][37][36][38][47][28][24][15]paper $\geq
2014$paper $<2014$
---|---
(a) | (b)
Figure 3: Visualization using schematic maps as metaphors, including (1) an
example of fruit maps, and (b) Applications with respect to their globality
and interactiveness.

###  IV-A Metro Maps as Visual Metaphors

Effects of using schematic maps as visual metaphors have been investigated,
though several case studies are at an early stage. Nesbitt [23] conducted
preliminary studies to evaluate the capabilities of metro map metaphors in
understanding abstract data and showed that they can provide a better mental
model of the target data as a first impression. Pontikakis and Twaroch [32]
also examined the potential use of metro maps to represent the topological
connections between points of interest especially when the underlying
topographic maps are unavailable.

Metro map metaphors have often been employed to explore the underlying
structure of an information space. In this case, each line corresponds to a
chain of subjects such as events, topics, plans, articles, etc. Stott et al.
[40] visualized the time-lines of project plans and their dependency as a
metro map by employing the early version of their hill-climbing algorithm
[39]. Aguiregoitia et al. [6] applied such an idea to software project
visualization where a different set of tasks is aligned with each metro line
according to the software development process.

A set of documents is another target for which we can effectively employ a
schematic map as a visual metaphor. Shahaf et al. [37] proposed an algorithm
for constructing a metro map of documents in such a way that the topology of a
document network reflects the desired sparseness inherent in ordinary railway
networks. This technique has been devised to visualize chains of scientific
papers to clarify the evolution of research fields [36], and then further
extended to the scalable scheme that enables the the level of detail control
in metro map metaphors [38].

As an application of schematic network metaphors to scientific data, Wahabzada
et al. [47] successfully visualized plant disease dynamics by tracking
spatiotemporal disease patterns with imaging techniques and composed metro map
metaphors by taking advantage of [27]. Cancer pathways [16] were also
visualized as schematic metro maps in the context of multiobjective
optimization [28].

Schematic network metaphors also allows us to visualize the structure of low-
dimensional space obtained through dimensionality reduction techniques.
Neumayer et al. [24] employed a metro map metaphor to describe the
configuration of segmented characteristic regions over the 2-dimensional plane
obtained through self-organizing maps. Gorban et al. [15] applied this idea in
the context of dimensionality reduction based on elastic energy minimization
to schematize the distribution of data samples with a metro map metaphor.

Several manually designed metaphors of metro maps are available on-line.
Example includes a Galaxy map that details relationships among planets [11], a
science map composed of scientists and their fields of sciences [31], a human
anatomy diagram consisting of organ systems as metro lines [17], a logistic
map of supply chains [1], a map of leading names and domains on the Internet
[5], and a map of digital workspace and marketing technology vendors [2]. The
most timely example is the Brexit tube maps [10], which model Brexit issues
and sectors as stations and lines, respectively, to elucidate how they relate
to one another.

###  IV-B Accessible On-line Tools

On-line tools often allows us to customize travel routes within the
precomputed schematic network maps or even to manually design such schematic
maps themselves. Mapway [4] and ExploreMetro [3] are mobile apps for finding a
route to the destination on metro maps in major cities. Metro Map Maker [44]
provides a web-based tool for designing schematic network maps, in which it is
possible to manually place stations and draw metro lines by referring to a
regular grid on a screen canvas. Several software libraries for designing
interactive schematic maps are also available, including Unfolding Map Library
[22] for Processing and Java, a library for interactive SVG metro maps with
JointJS [21], and a jQuery plug-in for subway map visualization [19].

##  V Discussion and Guidance for Followers

Our hypothesis about the correlation between problem complexity and running
time has been visually supported since our scatter plots approximately show a
top-left to bottom-right diagonal distribution of algorithmic approaches. This
strongly suggests that researchers are looking for a compromise between the
selected constraints for their problem formulation and the techniques to be
used, in order to find the balance between the global scope of the solution as
opposed to the running time of the algorithm. Doubtlessly, the final goal of
schematic mapping algorithms is to develop an ultimate technique that
pinpoints us in the top-right corner of the plots, representing high-quality
maps computed instantaneously. As shown in Figure 1, the blue markers
represent approaches investigated before 2014, and red markers depict the
techniques developed after 2014. A tendency from left to right and from bottom
to top can be observed indicating that researchers are heading towards the
desired goal. While some techniques [29][28] tend to accelerate the
conventional approach by Nöllenburg and Wolff [27], which has been considered
as the most global optimization method in this paper, the running times are
still not very suitable for interactive applications. This also confirms that
the schematic map problem is still a fundamentally difficult one, so that a
certain quality loss needs to be tolerated in order to achieve fast
performance [48]. More sophisticated algorithms are expected to be developed
to open further opportunities. As summarized in Section IV, several
researchers are beginning to use the maps generated by schematization
techniques to visualize their research results, especially when the data is
associated with entity connectivity and spatial relationship between entities.
The previous plots can also serve as a visual guidance to instruct those
researchers to select an appropriate technique for their research purposes.

##  VI Future Research Direction

In this study, we have compiled the state of the art on schematic network
visualization and have given a comprehensive overview of automatic network
layout algorithms and map labeling algorithms, as well as tools and
applications for use in multidisciplinary domains. Our taxonomy demonstrates
that most methods carefully design their solutions in compliance with the
problem space in order to provide effective approaches with reasonable
quality. Nonetheless until now, no benchmark is provided to enable standard
testing on schematic map production, although the Sydney metro map has been
studied by most of the conventional map layout algorithms. Developing such a
repository would help promoting the usage of algorithms not only in
cartography but also in other scientific domains. Another challenge for future
work in this field is to target advanced methodology to smartly handle global
constraints to improve the scalability of the algorithms. This can be
integrated with the interaction techniques together with appropriate user
scenarios. For this purpose, we plan to further investigate visual
representations and interaction schemes in accordance with the task taxonomy
for map users.

## Acknowledgment

The project leading to this submission has received funding from the EU
Horizon 2020 research and innovation programme under the Marie Sklodowska-
Curie grant No. 747985.

## References

  * [1] 3pl subway map.  https://www.supplychainmedia.eu/print/visuals/subway-maps/3pl-subway-map/.
  * [2] Digital workplace & marketing technology vendor map.  https://www.realstorygroup.com/vendormap/.
  * [3] Exploremetro.  https://www.exploremetro.com/.
  * [4] Mapway.  https://www.mapway.com/.
  * [5] Web trend map 4: Coolest gift for geeks.  https://ia.net/topics/wtm4.
  * [6] A. Aguirregoitia, J. J. D. Cosín, and C. Presedo.  Software project visualization using task oriented metaphors.  Journal of Software Engineering and Applications, 3(11):1015–1026, 2010.
  * [7] D. Chivers and P. Rodgers.  Gesture-based input for drawing schematics on a mobile device.  In Information Visualisation (IV’11), pages 127–134, 2011.
  * [8] D. Chivers and P. Rodgers.  Octilinear force-directed layout with mental map preservation for schematic diagrams.  In T. Dwyer, H. Purchase, and A. Delaney, editors, Diagrammatic Representation and Inference (Diagrams’14), pages 1–8. Springer Berlin Heidelberg, 2014.
  * [9] D. Chivers and P. Rodgers.  Improving search-based schematic layout by parameter manipulation.  Int. J. Software Engineering and Knowledge Engineering, 25(6):961–991, 2015.
  * [10] S. de Groot and M. J. Roberts.  Brexit mapping.  http://www.brexitmapping.com.
  * [11] J. Diaz.  We are just a tiny station in the milky way subway map.  https://gizmodo.com/we-are-just-a-tiny-station-in-the-milky-way-subway-map-5454587.
  * [12] M. Fink, M. Lechner, and A. Wolff.  Concentric metro maps.  In Proceedings of the Schematic Mapping Workshop (SMW’14), 2014\.  Poster.
  * [13] T. M. J. Fruchterman and E. M. Reingold.  Graph drawing by force-directed placement.  Software: Practice and experience, 21(11):1129–1164, 1991.
  * [14] K. Garland.  Mr. Beck’s Underground Map.  Capital Transport Publishing, 1994.
  * [15] A. N. Gorban, N. R. Sumner, and A. Y. Zinovyev.  Beyond the concept of manifolds: Principal trees, metro maps, and elastic cubic complexes.  In Principal Manifolds for Data Visualization and Dimension Reduction, pages 219–237. Springer, 2008.
  * [16] W. C. Hahn and R. A. Weinburg.  A subway map of cancer pathways, 2002.  https://www.nature.com/nrc/poster/subpathways/index.html [Subway map designed by C. Bentley.].
  * [17] B. P. C. Ho.  A doctor created a human anatomy diagram in the style of a subway map and it’s friggin’ gorgeous.  http://digg.com/2018/human-anatomy-subway-map.
  * [18] S.-H. Hong, D. Merrick, and H. A. D. do Nascimento.  Automatic visualisation of metro maps.  Journal of Visual Languages and Computing, 17(3):203–224, 2006\.
  * [19] N. Kalyani.  Subway map visualization jquery plugin.  https://github.com/techbubble/subwayMap.
  * [20] Z. Li and W. Dong.  A stroke-based method for automated generation of schematic network maps.  Int. J. Geographical Information Science, 24(11):1631–1647, 2010\.
  * [21] P. Maszczynski.  Creating an interactive svg metro map with jointjs.  https://www.netvlies.nl/tips-updates/applicaties/cases/creating-an-interactive-svg-metro-map-with-jointjs/.
  * [22] T. Nagel.  Unfolding map library.  http://unfoldingmaps.org/.
  * [23] K. V. Nesbitt.  Getting to more abstract places using the metro map metaphor.  In Information Visualisation, IV ’04, pages 488–493, 2004.
  * [24] R. Neumayer, R. Mayer, G. Polzlbauer, and A. Rauber.  The metro visualisation of component planes for self-organising maps.  In Int. Joint Conference on Neural Networks, pages 2788–2793, 2007\.
  * [25] B. Niedermann and J. Haunert.  An algorithmic framework for labeling network maps.  Algorithmica, 80(5):1493–1533, 2018.
  * [26] M. Nöllenburg.  A survey on automated metro map layout methods.  In Schematic Mapping Workshop, Essex, UK, 2014.  https://i11www.iti.kit.edu/extra/publications/n-asamm-14.pdf.
  * [27] M. Nöllenburg and A. Wolff.  Drawing and labeling high-quality metro maps by mixed-integer programming.  IEEE Transactions Visualization and Computer Graphics, 17(5):626–641, 2011.
  * [28] O. Oke and S. Siddiqui.  Efficient automated schematic map drawing using multiobjective mixed integer programming.  Computers & Operations Research, 61:1–17, 2015.
  * [29] M. Onda, M. Moriguchi, and K. Imai.  Automatic drawing for tokyo metro map.  In European Workshop on Computational Geometry (EuroCG’18), pages 62:1–62:6, 2018.
  * [30] M. Ovenden.  Metro Maps of the World.  Capital Transport Publishing, 2003.
  * [31] P. Plait.  Metrocontextual science map.  http://blogs.discovermagazine.com/badastronomy/2010/08/31/metrocontextual-science-map/\\#.XFEYW88zbfB.
  * [32] E. Pontikakis and F. Twaroch.  Schematic maps as an alternative to point coverages when topographic maps are not available.  In Information Visualisation, IV ’06, pages 297–303, 2006.
  * [33] M. J. Roberts.  Underground Maps Unravelled: Explorations in Information Design.  Self-published, 2012.
  * [34] M. J. Roberts, H. Gray, and J. Lesnik.  Preference versus performance: Investigating the dissociation between objective measures and subjective ratings of usability for schematic metro maps and intuitive theories of design.  International Journal of Human-Computer Studies, 98:109 – 128, 2017\.
  * [35] M. J. Roberts, E. J. Newton, F. D. Lagattolla, S. Hughes, and M. C. Hasler.  Objective versus subjective measures of paris metro map usability: Investigating traditional octolinear versus all-curves schematics.  International Journal of Human-Computer Studies, 71(3):363 – 386, 2013.
  * [36] D. Shahaf, C. Guestrin, and E. Horvitz.  Metro maps of science.  In Knowledge Discovery and Data Mining, KDD ’12, pages 1122–1130, 2012.
  * [37] D. Shahaf, C. Guestrin, and E. Horvitz.  Trains of thought: Generating information maps.  In World Wide Web, WWW ’12, pages 899–908, 2012.
  * [38] D. Shahaf, J. Yang, C. Suen, J. Jacobs, H. Wang, and J. Leskovec.  Information cartography: Creating zoomable, large-scale maps of information.  In Knowledge Discovery and Data Mining, KDD ’13, pages 1097–1105, 2013.
  * [39] J. Stott, P. Rodgers, J. C. Martínez-Ovando, and S. G. Walker.  Automatic metro map layout using multicriteria optimization.  17(1):101–114, 2011.
  * [40] J. M. Stott, P. Rodgers, R. A. Burkhard, M. Meier, and M. T. J. Smis.  Automatic layout of project plans using a metro map metaphor.  In Information Visualisation, IV ’05, pages 203–206, 2005.
  * [41] K. Sugiyama and K. Misue.  Graph drawing by the magnetic spring model.  Journal of Visual Languages & Computing, 6(3):217–231, 1995.
  * [42] P. Ti and Z. Li.  Generation of schematic network maps with automated detection and enlargement of congested areas.  International Journal of Geographical Information Science, 28(3):521–540, 2014.
  * [43] P. Ti, Z. Li, and Z. Xu.  Automated generation of schematic network maps adaptive to display sizes.  The Cartographic Journal, 52(2):168–176, 2015.
  * [44] S. Turner.  Metro map maker.  https://metromapmaker.com/.
  * [45] T. C. van Dijk and D. Lutz.  Realtime linear cartograms and metro maps.  In Advances in Geographic Information Systems (SIGSPATIAL’18), pages 488–491. ACM, 2018.
  * [46] T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann.  Map schematization with circular arcs.  In M. Duckham, E. Pebesma, K. Stewart, and A. U. Frank, editors, Geographic Information Science (GIScience’14), pages 1–17. Springer International Publishing, 2014.
  * [47] M. Wahabzada, A.-K. Mahlein, C. Bauckhage, U. Steiner, E.-C. Oerke, and K. Kersting.  Metro maps of plant disease dynamics-automated mining of differences using hyperspectral images.  PLOS ONE, 10(1):1–20, 2015.
  * [48] Y.-S. Wang and M.-T. Chi.  Focus+context metro maps.  IEEE Transactions Visualization and Computer Graphics, 17(12):2528–2535, 2011.
  * [49] Y.-S. Wang and W.-Y. Peng.  Interactive metro map editing.  IEEE Transactions on Visualization and Computer Graphics, 22(2):1115–1126, 2016.
  * [50] A. Wolff.  Drawing subway maps: A survey.  Informatik – Forschung und Entwicklung, 22(1):23–44, 2007.
  * [51] A. Wolff.  Graph drawing and cartography.  In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 23, pages 697–736. CRC Press, 2013.
  * [52] H.-Y. Wu, S.-H. Poon, S. Takahashi, M. Arikawa, C.-C. Lin, and H.-C. Yen.  Designing and annotating metro maps with loop lines.  In Information Visualization, IV ’15, pages 9–14. IEEE, 2015.
  * [53] H.-Y. Wu, S. Takahashi, D. Hirono, M. Arikawa, C.-C. Lin, and H.-C. Yen.  Spatially efficient design of annotated metro maps.  Computer Graphics Forum, 32(3):261–270, 2013.
  * [54] H.-Y. Wu, S. Takahashi, C.-C. Lin, and H.-C. Yen.  A zone-based approach for placing annotation labels on metro maps.  In Smart Graphics (SG’11), volume 6815 of LNCS, pages 91–102. Springer-Verlag, 2011.
  * [55] H.-Y. Wu, S. Takahashi, C.-C. Lin, and H.-C. Yen.  Travel-route-centered metro map layout and annotation.  Computer Graphics Forum, 31(3):925–934, 2012.
  * [56] Y. Yoshida, K. Maruyama, T. Kawagoe, H.-Y. Wu, M. Arikawa, and S. Takahashi.  Progressive annotation of schematic railway maps.  In Information Visualisation, IV ’18, pages 373–378. IEEE, 2018\.


# SystemC Model of Power Side-Channel Attacks Against AI Accelerators:
Superstition or not? ††thanks: This work has been funded by the German
Ministry of Education and Research (BMBF) via the project VE-Jupiter
(16ME0234).

Andrija Nešković1, Saleh Mulhem1, Alexander Treff2, Rainer Buchty1, Thomas
Eisenbarth2, and Mladen Berekovic1 1Institute of Computer Engineering and
2Institute for IT Security
University of Lübeck
Lübeck, Germany
{andrija.neskovic, saleh.mulhem, a.treff, rainer.buchty, thomas.eisenbarth,
<EMAIL_ADDRESS>
###### Abstract

As training artificial intelligence (AI) models is a lengthy and hence costly
process, leakage of such a model’s internal parameters is highly undesirable.
In the case of AI accelerators, side-channel information leakage opens up the
threat scenario of extracting the internal secrets of pre-trained models.
Therefore, sufficiently elaborate methods for design verification as well as
fault and security evaluation at the electronic system level are in demand.

In this paper, we propose estimating information leakage from the early design
steps of AI accelerators to aid in a more robust architectural design. We
first introduce the threat scenario before diving into SystemC as a standard
method for early design evaluation and how this can be applied to threat
modeling. We present two successful side-channel attack methods executed via
SystemC-based power modeling: correlation power analysis and template attack,
both leading to total information leakage. The presented models are verified
against an industry-standard netlist-level power estimation to prove general
feasibility and determine accuracy. Consequently, we explore the impact of
additive noise in our simulation to establish indicators for early threat
evaluation. The presented approach is again validated via a model-vs-netlist
comparison, showing high accuracy of the achieved results. This work hence is
a solid step towards fast attack deployment and, subsequently, the design of
attack-resilient AI accelerators.

###### Index Terms:

Artificial Intelligence, Accelerators, Side-channel Attacks, SystemC, Power
Modeling.

##  I Introduction

The use of Artificial Intelligence (AI) is rapidly growing across all emerging
technologies. One of the most important aspects is accelerating the AI
inference process and building according hardware accelerators. An accelerator
design’s fault-tolerance mechanisms and other safety features are usually
evaluated in the pre-silicon phase, whereas evaluation of the accelerator’s
physical security is performed in the post-silicon phase. Side channel
attacks, especially power attacks, are considered a serious security threat
leading to a vulnerable AI hardware component. Recently, studies in the domain
of AI accelerator design show that side-channel leakages of AI accelerators
can be exploited to reveal industrial secrets such as the AI model
architecture and its parameters [1, 2, 3]. For instance, power attacks are
deployed successfully to reverse engineer the AI model [1, 4]. Power attacks
lead to copying the AI model and then distributing it as counterfeit
intellectual property (IP). Therefore, a huge need exists for evaluating an AI
accelerator’s side-channel attack resistance in the early design steps (EDS)
of integrated circuit (IC) design, such as security evaluation at register-
transfer level (RTL), using gate-level netlists, or even earlier. Evaluation
and investigation of security issues in EDS provide insight into the
robustness of the later fabricated IC. Thus, design decisions made at high
abstraction levels have significant impact on the whole design process.

Figure 1: AI Accelerator IC Design Process (Adapted from [5]).

Tools and platforms considering security evaluation in EDS were developed
mainly to detect hardware Trojan circuitry [6] or to check the security rule
in ICs [7]. Recent work confirms the importance of security evaluation in the
EDS by demonstrating static and dynamic information flow analysis using
Virtual Prototypes (VPs) [8, 9]. Simulators targeting side-channel evaluation
have been studied in [10]. However, the reviewed tools consider only the
software implementation of cryptographic algorithms executed on general
purpose hardware (i.e. microcontrollers). The evaluation of side-channel
attacks (SCA) and its impact on ICs are still an open issue in EDS: To the
best of our knowledge, no simulator exists targeting SCA evaluation of
dedicated AI hardware accelerators. The missing SCA evaluation in EDS of IC is
required to ensure the IC’s dependability, together with existing reliability
and safety tests [11].

Our work demonstrates previously shown power SCA by utilizing a dedicated
power estimation model with the goal to evaluate the worst-case resilience of
an AI accelerator’s design at electronic system level (ESL). This approach was
positively verified by a comparison of the SystemC model’s behavior with a
technology-synthesized gate-level netlist.

###  I-A Why a SystemC Model?

SystemC is a solid candidate [12] for performing security evaluation in EDS,
as it is one of the industry standards for hardware/software modelling at high
abstraction levels. Particularly, SystemC is C++-based and was originally
conceived for hardware/software co-design, simulation, and functional
verification [13]. Over time, new design aspects such as fault evaluation [14]
and power modeling [15, 16] were also addressed using SystemC. The security
assessment of IC design has recently received more attention [7], especially
by SystemC in EDS [12]. With proper power estimation models, SystemC can be
utilized to simulate power attacks against ICs even at the ESL.

In order to clarify how to deploy SystemC in EDS, Fig. 1 shows the top-down
hardware design process of AI accelerators (a modified version of the Double
roof model described in [5, 17]). Starting from ESL, the requirements towards
AI accelerators are specified and synthesized into a system model (most likely
represented by a VP [18]). The requirements for lower abstraction levels are
derived based on this specification and implementation. At every abstraction
level, the specification is transformed into an implementation with a
synthesis step. This work presents a SystemC model of an AI accelerator at
ESL.

###  I-B Paper Contribution

In this paper, we show how to evaluate power attacks against AI accelerators
in EDS. For this, we build a SystemC model of a systolic-array-based AI
accelerator hardware at ESL. Using SystemC, the activation count of components
can be annotated with a power-consumption model to generate power traces
covering the hardware of AI accelerators. We demonstrate a correlation power
analysis (CPA) and template attacks (TA) based on our SystemC model in ideal
conditions and explore the limits of these attacks in a noisy environment.
Finally, we show the comparison of our model-based traces against power traces
from a state of the art netlist level simulation to demonstrate the
feasibility of the proposed model.

##  II Related Work

The target of this work is to evaluate the benefits of using SystemC models to
analyze side-channel information leakage at ESL in EDS. Therefore, power side-
channel attacks against AI accelerators are briefly discussed in this section,
as well as modeling approaches utilizing SystemC in different areas.

###  II-A Power Attacks vs. AI Hardware Accelerator

Several power attack scenarios against AI hardware accelerators have been
proposed [19, 4]. Power attacks exploit power consumption leakage from an
accelerator executing a pre-trained AI model (simply AI model) to reveal its
internal secrets. In particular, an attacker uses an evaluation board attached
to a targeted device [20], i.e., the AI Hardware accelerator, and captures
power consumption traces of some data input. The attacker applies statistical
analysis, e.g., Simple Power Analysis (SPA), Differential Power Analysis
(DPA), or Correlation Power Analysis (CPA), on the data input and the power
traces to recover the internal secrets of the AI model. For instance, DPA was
deployed to extract the AI’s secret parameters in [19]. In [4], CPA was
applied against the systolic-array-based hardware accelerator of Deep Neural
Networks (DNNs).

###  II-B Power Consumption Modeling Challenges

The power consumption of any CMOS computing platform includes two types:
static (leakage) power consumption $P_{static}$ and dynamic (switching) power
consumption $P_{dynamic}$ [21]. The total power for a computing platform can
be modeled by:

$P_{total}=P_{dynamic}+P_{static}$ (1)

$P_{static}$ is the product of leakage current and the supply voltage [22],
and $P_{dynamic}$ indicates and quantifies transistor switching. Thus,
$P_{dynamic}$ provides a distinctive current profile. Therefore, power attacks
mainly rely on $P_{dynamic}$, which is considered the Achilles heel of any
CMOS computing platforms [23].

SystemC can be utilized for the activation count of hardware components at
different abstraction levels. It plays a crucial role in simulating power
attacks in EDS. Using SystemC to estimate a computing platform’s power
consumption poses several challenges: SystemC was used in [24] to estimate the
power consumption of different processor configurations based on pre-computed
power values of its components, such as memories, register files, function
units, etc. The proposed power model exhibited a 15% prediction error. In
[15], a black-box power model was introduced for digital signal processors
(DSPs) in SystemC. The proposed power model does not require detailed insight
into the individual components of the probed computing platform. The black-box
power model exhibited a prediction error of less than 4%. This prediction
error is caused by the lack of information about power dissipation
$P_{static}$ of the targeted manufacturing technology. Therefore, the power
consumption of a computing platform is rather difficult to model in SystemC.
However, our work introduces a SystemC model that considers only dynamic power
consumption $P_{dynamic}$ to enable simulating power attacks.

###  II-C SystemC for Security Evaluation

Utilizing a SystemC VP to evaluate security-critical systems on chips has
already been demonstrated in [16]. Beyond that, SystemC was proven successful
for power-attack evaluation of cryptographic applications in [12], such as
RSA-based public-key cryptosystems and elliptic-curve cryptography. This
approach in [12] solely relies on a dedicated dynamic power consumption model,
the so-called input-dependent model. This model covers the arithmetic
operations by assuming that there is no difference between simulated hardware
or C++ operators. The input-dependent model covers bit-shifts and comparisons
as well, but lacks power modeling of registers, multiplexers, and other
hardware components. In order to extend SystemC power attacks analysis beyond
cryptographic applications, this paper introduces power estimation models to
cover systolic arrays. By utilizing these power models, CPA and power-template
attacks (TA) against AI accelerators are simulated.

In the following sections, we first build a system model of a systolic-array-
based AI accelerator and extend and modify power-consumption models proposed
in [12, 16] to also cover additional components present in an AI hardware
accelerator. Then, we perform the proposed attacks. Finally, we verify our
power estimation model and the validity of the attacked performed hereon
against a state-of-the-art netlist-level power estimation tool.

##  III AI Accelerator ESL Model

Figure 2: Block diagram of TPU including the threat model.

To perform a security evaluation in EDS, an ESL model of an AI accelerator is
required. For our approach, we use SystemC as the modelling language and start
with a loosely-timed SystemC model of a systolic array for simulating the
behaviour. By annotating this model with input-dependent power estimation
capabilities, all components for SCA simulation can be provided.

###  III-A Systolic Array for Acceleration

The inference process of AI applications requires frequent data access. Such
data-read operations from memory are very costly and time-consuming and
therefore should be avoided on edge accelerators in order to minimize power
consumption and maximize performance. This can be addressed by using so-called
systolic array architectures, featuring a number of benefits [25]. Instead of
accessing memory after every arithmetic operation, the systolic design
approach utilizes multiple processing elements (_PEs_) to avoid frequent
memory access. Each _PE_ performs a multiply-accumulate operation (MAC) as
shown in Fig. 2. The partial result of an _PE_ is directly passed to another
_PE_ without memory access. The realization of an array of _PEs_ in hardware
can accelerate matrix multiplication, which is essential for accelerating the
desired AI algorithm.

The matrix multiplication of $A=(a_{ij})_{3\times 3}$ and $B=(b_{ij})_{3\times
3}$ results in a matrix $C=(c_{ij})_{3\times 3}$. A systolic array accelerates
such a matrix multiplication, where, a resulting element ($c_{11}$) is, for
instance, calculated sequentially over $3$ clock-cycles by performing 3 MACs
in 3 different _PEs_ as follows [4]:

$\begin{array}[]{rlr}Reg_{11}&=a_{11}\times b_{11}+0&(t=1)\\\
Reg_{21}&=a_{12}\times b_{21}+Reg_{11}&\\\ &=a_{12}\times b_{21}+a_{11}\times
b_{11}&(t=2)\\\ Reg_{31}&=a_{13}\times b_{31}+Reg_{21}&\\\ &=a_{13}\times
b_{31}+a_{12}\times b_{21}+a_{11}\times b_{11}&(t=3)\end{array}$ (2)

Where $Reg_{ij}$ is a partial sum register of $\emph{PE}_{ij}$ as shown in
Fig. 2. In our model, the weights and inputs are represented as 8 bit
integers, and the partial-sum results as 18 bit integers.

###  III-B SystemC Model of the Accelerator

For our approach, we focus on a loosely-timed SystemC model. Here, the
behaviour of the AI accelerator is represented by a SystemC _module_ to
perform accelerated calculations and mimic the timing and power
characteristics of a real hardware accelerator. Fig. 2 shows the architecture
of the modelled system. The SystemC model easily realizes the individual
multiply-accumulate and register operations required during inference, by
using dedicated data types. The matrix multiplication is performed over
several cycles depending on the dimension of the matrix by utilizing all _PEs_
in parallel. The result is therefore available in several parts across
multiple cycles as described in Eq. 2. Furthermore, the proposed adversary is
implemented as another SystemC _module_ which is able to send input and
receive output from the AI accelerator. Lastly, all activity during inference
is tracked by a dedicated resource handler shown in Fig. 3, which implements a
power-estimation model described in the following section.

Figure 3: SystemC Implementation Overview.

##  IV Dynamic Power Consumption Model

As the dynamic power consumption ($P_{Dynamic}$) is the required power
consumption during logical transitions [22], the dynamic power-estimation
model of a systolic array can be built based on the operations performed by
every _PE_. Here, the SystemC model should implement a dedicated resource
handler to generate power traces while the calculation is performed [12]. From
ESL perspective, every single operation performed in hardware consumes a
certain amount of power measured by the so-called power expense, which depends
on the hardware architecture, the type of operations, and the inputs of the
operation. In the following, we utilize the input-dependent power model
proposed in [12] and we extend this model to include hardware components such
as registers and MAC components.

###  IV-A Power Model of a Single Processing Element

The extended version of the input-dependent model relies on the input of the
hardware components and its computational/storage efforts $CE$. If the inputs
of a hardware component are zero, we consider its contribution to the dynamic
power consumption as negligible and its computational/storage effort $CE$ is
zero. Otherwise, its contribution is not negligible, and its
computational/storage effort $CE$ relies on the number of ones in the input.
The $CE$ reflects the switching activity of the component and can be described
by utilizing a bit-flipping power model. Several cases of single-bit flipping
have to be considered, and a power expense for every case is assigned as
follows: The transition $0\rightarrow 0$ and $1\rightarrow 1$ require zero
power expense, $0\rightarrow 1$ requires one power expense, and $1\rightarrow
0$ requires 0 power expense as flipping one bit from $0$ to $1$ consumes much
more power than from $1$ to $0$ [12]. The proposed dynamic power consumption
model of a single _PE_ estimates the power expense of the MAC component by
breaking it down into arithmetic operations. Additionally, the expense of
accessing the register is considered.

MAC Component Power Model: The computational expenses of the MAC component can
be broken down into the switching activity of binary arithmetic operations
performed during the calculation, namely multiplication and addition. Counting
the flipping of single bits during the calculation provides an estimation of
the power expense of the performed MAC operation. Binary arithmetic
multiplication can be considered as a series of adders; therefore, the power
model of the multiplication is based on the power expenses of a binary adder
shown in Table I.

TABLE I: Power Expenses of Binary Adder

Input Bits | Output Bits | $state$ | $CE$ | $PM_{BA}$
---|---|---|---|---
$(a,b,c)$ | $(c,s)$ | $expense$
(0,0,0) | (0,0) | 0 | 0 | 0
(1,0,0) | (0,1) | 0 | 1 | 1
(0,1,0) | (0,1) | 0 | 1 | 1
(1,1,0) | (1,0) | 1 | 2 | 3
(0,0,1) | (0,1) | 1 | 0 | 1
(1,0,1) | (1,0) | 0 | 1 | 1
(0,1,1) | (1,0) | 0 | 1 | 1
(1,1,1) | (1,1) | 0 | 2 | 2

Register Power Model: $P\\!M_{Reg}$ denotes the power expenses of the register
access power model, which can be modeled based on the bit-switching activity
inside the register every time a new value is written. Therefore, the old and
new states of the register ($Reg_{old}$ and $Reg_{new}$) are compared, and the
number of switches is counted by using the Hamming Distance (HD):

$P\\!M_{Reg}=H\\!D(Reg_{old}\oplus Reg_{new}).$ (3)

The power consumption model of one PE: The total power consumption of a _PE_
($P\\!M_{\emph{PE}}$) is the sum of the $P\\!M_{MAC}$ and the $P\\!M_{Reg}$,
i.e.,

$P\\!M_{\emph{PE}}=P\\!M_{MAC}+P\\!M_{Reg}.$ (4)

###  IV-B Resource Handler

In the SystemC implementation, the power estimation is performed by the
resource handler. The proposed resource handler relies on the total dynamic
power consumption of all _PEs_ , where the _PEs_ consume power depending on
the performed MAC operation and the register write operation. These operations
are modeled separately and combined to produce a power trace of the whole
calculation. We modify and add our _PE_ power model and utilize the resource
handler proposed in [12] to fit the AI accelerator model. Fig. 3 illustrates
how the resource handler generates power traces of the AI accelerator during
inference.

In the following sections, we will show how the power traces generated by the
resource handler can be used by an adversary to perform power SCA.

##  V Threat Model

The proposed threat model is equivalent to a practical one in which the
adversary has physical access to an AI edge device [4]. Regarding the system
model, we assume that the adversary has the following capabilities during the
attack:

  * •

The adversary has knowledge about the targeted platform or device.

  * •

The adversary has knowledge about the internal structure of the AI
accelerator.

  * •

The adversary cannot directly access to or read the secret information
(weights).

  * •

The adversary can input any data into the AI accelerator.

  * •

The adversary can observe the device’s inference results and obtain power
traces of the performed operations.

This scenario can be classified as a grey-box approach [26], where the target
of the adversary is to reveal the _PEs_ ’ parameters. These parameters are
highly valuable, since they represent the weights of a trained NN.

Fig. 2 shows an overview of the threat model. The weight parameters are pre-
loaded to the systolic array for inference. The information leak is caused by
the power trace of the inference calculations, thus the adversary can attack
the weights via SCA.

##  VI SCA Simulation using SystemC

The described model of an AI accelerator extended with power estimation
capabilities enables the modelling of SCA. Having defined the threat model, we
can simulate side-channel attacks targeting the secret parameters of a trained
neural network at the ESL. In order to simulate realistic scenarios, the CPA
approach is considered as this approach has been proven successful on real
hardware [4]. In addition, we revisit Template attacks, which are considered
the most objective method to assess the leakage of a device under test [27,
28].

###  VI-A Adversary Simulation in SystemC

The power estimation model of every _PE_ is a combination of the power
estimation models of the single operations performed by the _PE_. Since static
power consumption of the device is of no interest for the above mentioned
SCAs, the focus lies on dynamic power consumption. The adversary has access to
the modeled power trace and thus can perform the attacks as if the hardware
was real.

###  VI-B Correlation Power Analysis

CPA-based attacks have been proven successful against hardware cryptographic
functions [29]. Compared to less complex power analysis attacks, like SPA or
DPA, CPA shows a more robust behavior. To perform a CPA, a leakage model needs
to be defined. The most common approach is to calculate the correlation
coefficient between power trace and Hamming Distance (HD) or Hamming Weight
(HW) estimation of a certain calculation performed by the observed system.

Figure 4: CPA provides multiple weight candidates for $b_{11}$.

Every $\emph{PE}_{ij}$ of the systolic performs a multiply-accumulate
operation and stores the result of the operation into a register. An adversary
assumes a correlation between the power traces and the HD model of _PEs_
registers. To reveal a secret parameter, the adversary calculates the HD
estimation ($\hat{H}_{n,b_{k}}$) for all possible transitions of the
$Reg_{ij}$ register by

$\hat{H}_{n,b_{k}}=H\\!D\left(Reg_{ij}^{t},Reg_{ij}^{t+1}\right).$ (5)

The correlation coefficient ($\rho\left(b_{k}\right)$) of all estimations and
the recorded power traces is calculated as follows:

$\rho\left(b_{k}\right)=\frac{\sum_{n=0}^{N-1}\left(P_{n}-\bar{P}\right)\left(\hat{H}_{n,b_{k}}-\bar{H}_{b_{k}}\right)}{\sqrt{\sum_{n=0}^{N-1}\left(P_{n}-\bar{P}\right)^{2}}\sqrt{\Sigma_{n=0}^{N-1}\left(\hat{H}_{n,b_{k}}-\bar{H}_{n,b_{k}}\right)^{2}}},$
(6)

where $P_{n}$ and $\bar{P}$ are the power trace and its average value and
$\hat{H}_{n,b_{k}}$ and $\bar{H}_{b_{k}}$ are the HD estimation and its
average value. The true value of the parameter produces the highest
correlation; thus the adversary can reveal it by comparing all of the
correlation coefficients as follows:

$\hat{b}=\arg\max_{b_{k}}\left(\left|\rho\left(b_{k}\right)\right|\right).$
(7)

Since the HD model is not unique for all possible transitions, multiple
candidates can provide a similar correlation coefficient (values with bit-
shift difference from the true value, e.g. 23, 46, 92, etc.). This causes
certain constraints when revealing the parameters since the attack produces
multiple candidates as shown in Fig. 4. Nevertheless, the attack can reduce
the search space drastically.

###  VI-C Template Attack

Template attacks are a very powerful type of side-channel analysis [30]. As a
subset of profiling attacks, template attacks are composed of two phases:
profiling and attack phase. In the profiling phase, the adversary profiles
data-dependent power consumption and noise behavior of a target device
handling sensitive data. Then, the adversary performs the attack in the
attacking phase to reveal the sensitive data based on the prior knowledge of
the device profile.

In the profiling phase of a template attack, the adversary has full control
over a target device and can, e.g., arbitrarily set the weights. This scenario
can be easily simulated with our implemented SystemC model.

Having created the templates for individual _PEs_ , the adversary can launch
the attack by iterating over individual _PEs_. In this attack a small number
(10-20) of traces with unknown, but fixed weights leads to a successful
recovery.

As the parameters for building the template differ from _PE_ to _PE_ , the
adversary cannot re-use the same template to reveal all of the parameters.
Nevertheless, the additional effort to reveal all of the parameters is only
linked to building the template for each of the _PEs_. The acquired traces can
be re-used, thus the adversary doesn’t require additional power traces
(neither for the profiling, nor for the attack).

##  VII Attack Results and Impact of Additive Noise

Figure 5: Correlation coefficient against additive noise.

Since the model does not consider any measurement noise, the attacker is able
to reveal all hidden parameters of the systolic array with the CPA. Fig. 4
shows the simulation results of the attack against the first parameter. The
multiple peaks observed are caused by bit-shifted true values. Since the HD of
bit-shifted values is the same, these weight candidates cause very similar
correlation levels. The CPA of a real computing platform is most certainly
influenced by measurement noise, therefore, this results should be considered
as the best-case scenario (from the attacker’s perspective).

The template attack successfully recovers all nine weights from the processing
elements with a very low number of attack traces (less than 15 attack traces).
Since we assume an adversary in a chosen-plaintext scenario, the attacker can
freely decide which inputs are sent to the systolic array. By setting entire
input columns to zero, the impact of most processing elements which store the
pre-loaded weights is eliminated. This allows the attacker to selectively
enable only a small subset (i.e. single columns) of processing elements. Just
like with the CPA, the bit-shifted values of the correct weight produce a high
score. Therefore, it is possible to have multiple candidates as a result of
the attack in the leftmost column. After recovering the weights from the
leftmost columns, the attack can build templates including the recovered
weights. This reduces the uncertainty when attacking the middle or rightmost
_PEs_ , thus bit-shifted values of the correct weights do not produce a false
positive.

TABLE II: Impact of additive noise on attacks

Revealed Parameters | Template Attack | Correlation Power Attack
---|---|---
SNR | # Attack Traces | SNR | Correlation Coefficient
9/9 |  $\geq$2.0 | 15 | >4.0 | 0.561 - 0.775
8/9 | - | - | 3.5 - 4.0 | 0.444 - 0.561
0/9 | <2.0 | - | <3.5 | <0.444

###  VII-A Impact of Additive Noise on CPA

In applied cryptography, analysing the impact of additive noise on power
attacks is essential [31, 32]. The backbone of such an analysis is Signal-to-
noise ratio (SNR) of the leaked information [20]. Here, additive noise is
used. The measurement noise is modelled by adding random values $R_{n}$ with
an average $\bar{R}=0$ to the power trace $P_{n}$ at each estimation point as
$P_{n}+R_{n}$. It can be gradually increased to have a bigger impact on the
power estimation value. Here, we can set a fixed SNR to produce noisy power
traces.

With this model, a threshold evaluation of the CPA’s success is possible.
Multiple experiments with additive noise are performed to investigate the
influence of noise on correlation coefficients. A comparison of the
correlation with different amounts of additive noise is shown in Table II and
illustrated in Fig. 5. The results show how an increasing noise level impacts
the correlation coefficient, ultimately making the correct candidate
indistinguishable from other candidates. For too low SNRs, the CPA cannot
successfully reveal the weights from the AI accelerator. Increasing the number
of traces an attacker acquires, increases the chance of a successful attack.
This can give an indication to how many traces an attacker would require in a
post-silicone attack.

###  VII-B Impact of Additive Noise on Template Attacks

Several experiments have been conducted to study the impact of additive noise
on template attacks, where both the profiling and attack traces are affected.
SNR is also used to describe the magnitude of the noise. The experiments show
that recovering the weights remains as easy as without noise. By increasing
the impact of noise, i.e., decreasing the SNR to as low as 2.0, the template
attacks proves to be successful with as little as 15 attack traces per
targeted parameter.

Consequently, template attacks are applicable with lower SNR values, i.e., the
template attacks are much less affected by noise if the same noise level is
present during the profiling phase, as well as the attack phase. Template
attacks therefore, pose a serious threat to implementations, even in a noisy
environment. By taking advantage of input tuning (as a chosen plaintext
attack), an adversary could theoretically attack systolic arrays of any size
and reveal secret parameters. Here, a more noisy environment requires the
attacker to use a larger number of traces when building the template.

##  VIII Model Verification

Figure 6: Systolic Array Implemented for Verification.

It was previously shown [33], that a time-based power estimation with a gate-
level netlist comes quite close to post-silicon measurements. To achieve
industry-grade results, we also use the Synopsys tool suite for our
experiments.

The verification starts with a Verilog implementation of a single PE, as well
as the whole $(3\times 3)$ systolic array, as shown in 6. The design is
synthesized using Synopsys DesignCompiler [34] to generate a gate-level
netlist. A pre-defined test bench is used to stimulate the netlist and gather
a value-change dump (VCD) using Synopsys VCS [35]. Lastly, Synopsys PrimePower
[33] creates a power trace based on the VCD in a time-based power analysis.
These power traces are considered to be noise-free reference traces of the
real hardware. We use these traces to verify the input-dependent power model
utilized in our SystemC simulation of a systolic array. Consequently, a
statistical comparison between the reference power traces and the power traces
collected at the SystemC level is performed. The comparison is divided into
four main experiments as follows:

Figure 7: Pearson’s Correlation Coefficient between Trace Sets.

###  VIII-A First Experiment

For a single PE with the same random inputs, we generate two sets of power
traces (20 000 traces) collected at SystemC level and gate-level netlist.
Then, we use Pearson’s correlation coefficient (PCC) to interpret if there is
a linear correlation between them. PCC lies between $[-1,+1]$, with $PCC=0$
indicating no linear correlation. The results show that there is a positive
correlation between the traces, as seen in Fig. 7a. A value of PCC up to 0.65
confirms that the proposed SystemC model is linearly associated with the power
consumption tendency of a real hardware implementation.

###  VIII-B Second Experiment

For a single PE with two distinct sets of random inputs, we generate two sets
of power traces (20 000 traces) collected at SystemC level and gate-level
netlist. The goal of this experiment is to exclude a false-positive
correlation for a single PE. Here, we observe a correlation coefficient close
to 0, as shown in Fig. 7b. This confirms there is no false positive
correlation between the power traces.

###  VIII-C Third Experiment

The design of the whole systolic array is more complex. A test bench with full
coverage of all possible input/weight combinations for all PEs would produce
an enormous amount of traces. Therefore, we fixed the weights in the PEs and
stimulated the systolic array by 20 000 random input samples. An equivalent
test bench is implemented in SystemC to produce comparable traces. As we
expected, the two trace sets will be linearly correlated the most when
modeling smaller pieces of hardware. Naturally, modelling bigger hardware at a
high abstraction level will bring a drop in accuracy, and PCC will be lower,
as shown in the in Fig. 7c. Therefore, Spearman’s correlation coefficient
(SCC) is used in this experiment to interpret the direction of the association
between them. The sign of the SCC value indicates if the same trends are
expected between the two trace sets. When evaluating SCC between the two sets,
we observe a positive SCC coefficient of $+0.27$. This indicates a moderate
monotonic (linear or non-linear) relationship between them. In other words,
SCC shows that power traces collected at SystemC level tend to increase when
reference power traces increase.

###  VIII-D Fourth Experiment

Similar to the second experiment, we aim to exclude a false-positive
correlation result between the traces of the whole systolic array. With two
distinct sets of random inputs, we observe both PCC and SCC close to 0, as
shown in Fig. 7d. This indicates there is no false positive in the power
traces collected at SystemC level.

In conclusion, it can be said with high confidence that the proposed power
estimation model follows the same trends as a state-of-the-art netlist-level
power estimation.

##  IX Conclusion

This paper presents power side-channel attacks against AI accelerator
architectures at the electronic system level. Our approach features AI
accelerator models with a corresponding dynamic power-consumption model to
simulate the behaviour of systolic-array-based AI accelerators using SystemC.
Our findings show that SystemC-based power attacks are possible and
sufficiently resemble real-world threat scenarios. Our experiments
successfully simulate SystemC-based power side-channel attacks against AI
accelerators leading to full secret extraction: While correlation power
analysis shows certain limitations in noisy conditions, template attacks pose
a significant risk of being able to adapt to noise.

To verify the SystemC-power estimation model, several experiments were
performed to compare power traces computed from synthesized netlists with the
proposed model. The results show that the proposed model follows the same
trends as a gate-level netlist power estimation. Our set goal of earliest-
possible threat analysis and subsequent design suggestions was thus
successfully achieved and demonstrated.

This work hence is one essential – and with regard to the presented methods
and procedures to the best of our knowledge first – step in design-space
exploration for security from a design/hardware perspective. In a future step
and raising complexity, we would like to extend this approach from a systolic
array to a full system model.

## References

  * [1] L. Batina, S. Bhasin, D. Jap, and S. Picek, “CSI NN: Reverse Engineering of Neural Network Architectures through Electromagnetic Side Channel,” in _Proceedings of the 28th USENIX Conference on Security Symposium_ , ser. SEC’19. USA: USENIX Association, 2019, pp. 515–532.
  * [2] H. Chabanne, J.-L. Danger, L. Guiga, and U. Kühne, “Side channel attacks for architecture extraction of neural networks,” _CAAI Transactions on Intelligence Technology_ , vol. 6, no. 1, pp. 3–16, 2021.
  * [3] Y.-S. Won, S. Chatterjee, D. Jap, A. Basu, and S. Bhasin, “WaC: First Results on Practical Side-Channel Attacks on Commercial Machine Learning Accelerator,” in _Proceedings of the 5th Workshop on Attacks and Solutions in Hardware Security_ , ser. ASHES ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 111–114. [Online]. Available: https://doi.org/10.1145/3474376.3487284
  * [4] K. Yoshida, M. Shiozaki, S. Okura, T. Kubota, and T. Fujino, “Model Reverse-Engineering Attack against Systolic-Array-Based DNN Accelerator Using Correlation Power Analysis,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. E104.A, no. 1, pp. 152–161, 2021.
  * [5] A. Gerstlauer, C. Haubelt, A. D. Pimentel, T. P. Stefanov, D. D. Gajski, and J. Teich, “Electronic system-level synthesis methodologies,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 28, no. 10, pp. 1517–1530, 2009.
  * [6] H. Salmani and M. Tehranipoor, “Analyzing circuit vulnerability to hardware trojan insertion at the behavioral level,” in _2013 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFTS)_ , 2013, pp. 190–195.
  * [7] K. Xiao, A. Nahiyan, and M. Tehranipoor, “Security rule checking in ic design,” _Computer_ , vol. 49, no. 8, pp. 54–61, 2016.
  * [8] M. Hassan, V. Herdt, H. M. Le, D. Große, and R. Drechsler, “Early soc security validation by vp-based static information flow analysis,” in _2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_ , 2017, pp. 400–407.
  * [9] M. Goli, M. Hassan, D. Große, and R. Drechsler, “Security validation of vp-based socs using dynamic information flow tracking,” _it - Information Technology_ , vol. 61, no. 1, pp. 45–58, 2019. [Online]. Available: https://doi.org/10.1515/itit-2018-0027
  * [10] N. Veshchikov and S. Guilley, “Use of simulators for side-channel analysis,” in _2017 IEEE European Symposium on Security and Privacy Workshops (EuroS &PW)_, 2017, pp. 104–112.
  * [11] B. Bauer, M. Ayache, S. Mulhem, M. Nitzan, J. Athavale, R. Buchty, and M. Berekovic, “On the dependability lifecycle of electrical/electronic product development: The dual-cone v-model,” _Computer_ , vol. 55, no. 09, pp. 99–106, sep 2022.
  * [12] J. Treus and P. Herber, “Early analysis of security threats by modeling and simulating power attacks in systemc,” in _2020 IEEE 91st Vehicular Technology Conference (VTC2020-Spring)_ , 2020, pp. 1–5.
  * [13] R. Drechsler, “Advanced formal verification,” 01 2004.
  * [14] B.-A. Tabacaru, M. Chaari, W. Ecker, T. Kruse, and C. Novello, “Fault-effect analysis on system-level hardware modeling using virtual prototypes,” in _2016 Forum on Specification and Design Languages (FDL)_ , 2016, pp. 1–7.
  * [15] G. Onnebrink, S. Schürmans, F. Walbroel, R. Leupers, G. Ascheid, X. Chen, and Y. Harn, “Black box power estimation for digital signal processors using virtual platforms,” in _Proceedings of the 2016 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools_ , ser. RAPIDO ’16. New York, NY, USA: Association for Computing Machinery, 2016. [Online]. Available: https://doi.org/10.1145/2852339.2852345
  * [16] F. Menichelli, R. Menicocci, M. Olivieri, and A. Trifiletti, “High-level side-channel attack modeling and simulation for security-critical systems on chips,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 5, no. 3, pp. 164–176, 2008.
  * [17] J. Teich, “Embedded System Synthesis and Optimization,” 2000.
  * [18] R. Leupers, G. Martin, R. Plyaskin, A. Herkersdorf, F. Schirrmeister, T. Kogel, and M. Vaupel, “Virtual platforms: Breaking new grounds,” in _2012 Design, Automation Test in Europe Conference Exhibition (DATE)_ , 2012, pp. 685–690.
  * [19] A. Dubey, R. Cammarota, and A. Aysu, “MaskedNet: The First Hardware Inference Engine Aiming Power Side-Channel Protection,” in _2020 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_. Los Alamitos, CA, USA: IEEE Computer Society, dec 2020, pp. 197–208. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/HOST45689.2020.9300276
  * [20] A. Biryukov, D. Dinu, and J. Großschädl, “Correlation Power Analysis of Lightweight Block Ciphers: From Theory to Practice,” in _Applied Cryptography and Network Security_ , M. Manulis, A.-R. Sadeghi, and S. Schneider, Eds. Cham: Springer International Publishing, 2016, pp. 537–557.
  * [21] D. Harris and S. Harris, _Digital design and computer architecture_. Morgan Kaufmann, 2010.
  * [22] B. Jacob, S. W. Ng, and D. T. Wang, “Chapter 29 - power and leakage,” in _Memory Systems_ , B. Jacob, S. W. Ng, and D. T. Wang, Eds. San Francisco: Morgan Kaufmann, 2008, pp. 847–864. [Online]. Available: https://www.sciencedirect.com/science/article/pii/B978012379751350031X
  * [23] R. Soares, V. Lima, R. Lellis, P. Finkenauer Jr, and V. Camargo, “Hardware countermeasures against power analysis attacks: a survey from past to present,” _Journal of Integrated Circuits and Systems_ , vol. 16, no. 2, pp. 1–12, 2021.
  * [24] S. A. A. Shah, J. Wagner, T. Schuster, and M. Berekovic, “A lightweight-system-level power and area estimation methodology for application specific instruction set processors,” in _2014 24th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS)_ , 2014, pp. 1–5.
  * [25] Kung, “Why systolic architectures?” _Computer_ , vol. 15, no. 1, pp. 37–46, 1982.
  * [26] Y. Xiang, Y. Xu, Y. Li, W. Ma, Q. Xuan, and Y. Liu, “Side-Channel Gray-Box Attack for DNNs,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 68, no. 1, pp. 501–505, 2021.
  * [27] F. Durvaux, F. Standaert, and N. Veyrat-Charvillon, “How to certify the leakage of a chip?” in _Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings_ , ser. Lecture Notes in Computer Science, P. Q. Nguyen and E. Oswald, Eds., vol. 8441. Springer, 2014, pp. 459–476. [Online]. Available: https://doi.org/10.1007/978-3-642-55220-5_26
  * [28] O. Bronchain, J. M. Hendrickx, C. Massart, A. Olshevsky, and F. Standaert, “Leakage certification revisited: Bounding model errors in side-channel security evaluations,” in _Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I_ , ser. Lecture Notes in Computer Science, A. Boldyreva and D. Micciancio, Eds., vol. 11692. Springer, 2019, pp. 713–737. [Online]. Available: https://doi.org/10.1007/978-3-030-26948-7_25
  * [29] E. Brier, C. Clavier, and F. Olivier, “Correlation Power Analysis with a Leakage Model,” in _Cryptographic Hardware and Embedded Systems - CHES 2004_ , M. Joye and J.-J. Quisquater, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 16–29.
  * [30] S. Chari, J. R. Rao, and P. Rohatgi, “Template attacks,” in _Cryptographic Hardware and Embedded Systems - CHES 2002_ , B. S. Kaliski, ç. K. Koç, and C. Paar, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 13–28.
  * [31] L. Lerman, N. Veshchikov, S. Picek, and O. Markowitch, “On the construction of side-channel attack resilient s-boxes,” in _International Workshop on Constructive Side-Channel Analysis and Secure Design_. Springer, 2017, pp. 102–119.
  * [32] F.-X. Standaert, T. G. Malkin, and M. Yung, “A unified framework for the analysis of side-channel key recovery attacks,” in _Annual international conference on the theory and applications of cryptographic techniques_. Springer, 2009, pp. 443–461.
  * [33] “Synopsys PrimePower,” https://www.synopsys.com/implementation-and-signoff/signoff/primepower.html, accessed: 2023-05-17.
  * [34] “Synopsys DesignCompiler,” https://www.synopsys.com/implementation-and-signoff/rtl-synthesis-test/dc-ultra.html, accessed: 2023-05-17.
  * [35] “Synopsys VCS,” https://www.synopsys.com/verification/simulation/vcs.html, accessed: 2023-05-17.