Massimo Equi
email: massimo.equi@helsinki.fi

Roberto Grossi
email: grossi@di.unipi.it

Veli Mäkinen
email: veli.makinen@helsinki.fi

On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree

Keywords: 2012 ACM Subject Classification Mathematics string matching, string search, strong exponential time hypothesis, variation graphs

Exact pattern matching in labeled graphs is the problem of searching paths of a graph G = (V, E) that spell the same string as the pattern P [1..m]. This basic problem can be found at the heart of more complex operations on variation graphs in computational biology, of query operations in graph databases, and of analysis operations in heterogeneous networks, where the nodes of some paths must match a sequence of labels or types. We describe a simple conditional lower bound that, for any constant > 0, an O(|E| 1-m)-time or an O(|E| m 1-)-time algorithm for exact pattern matching on graphs, with node labels and patterns drawn from a binary alphabet, cannot be achieved unless the Strong Exponential Time Hypothesis (seth) is false. The result holds even if restricted to undirected graphs of maximum degree three or directed acyclic graphs of maximum sum of indegree and outdegree three. Although a conditional lower bound of this kind can be somehow derived from previous results (Backurs and Indyk, FOCS'16), we give a direct reduction from seth for dissemination purposes, as the result might interest researchers from several areas, such as computational biology, graph database, and graph mining, as mentioned before. Indeed, as approximate pattern matching on graphs can be solved in O(|E| m) time, exact and approximate matching are thus equally hard (quadratic time) on graphs under the seth assumption. In comparison, the same problems restricted to strings have linear time vs quadratic time solutions, respectively, where the latter ones have a matching seth lower bound on computing the edit distance of two strings (Backurs and Indyk, STOC'15).

Introduction

Large-scale labeled graphs are becoming ubiquitous in several areas, such as computational biology, graph databases, and graph mining. Applications require sophisticated operations on these graphs, and often rely on primitives that locate paths whose nodes have labels or types matching a pattern given at query time.

In graph databases, query languages provide the user with the ability to select paths based on the labels of their nodes or edges, where the edge labels are called properties. In this way, graph databases explicitly lay out the dependencies between the nodes of data, whereas these dependencies are implicit in classical relational databases [START_REF] Angles | Survey of graph database models[END_REF]. Although a standard query language has not been yet universally adopted (as it occurred for SQL in relational databases), popular query languages such as Cypher [START_REF] Francis | Cypher: An evolving query language for property graphs[END_REF], Gremlin [START_REF] Rodriguez | The gremlin graph traversal machine and language (invited talk)[END_REF], and SPARQL [START_REF] Prud | SPARQL query language for RDF[END_REF] offer the possibility of specifying paths by matching the labels of their nodes.

In graph mining and machine learning for network analysis, heterogeneous networks specify the type of each node [START_REF] Shi | A survey of heterogeneous information network analysis[END_REF]. For example, in the DBLP network [START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF], the nodes for authors can be marked with letter 'A', and the nodes for papers can be marked with letter 'P', where edges connect authors to their papers. For example, coauthors can be identified by the pattern 'APA' when it matches two different nodes with 'A'. The strings generated by the labels on the paths have several applications in heterogeneous networks, such as graph kernels [START_REF] Hido | A linear-time graph kernel[END_REF] or node similarity [START_REF] Conte | Node similarity with q -grams for real-world labeled networks[END_REF], where a basic tool is retrieving the paths for a string.

In genome research, the very first step of many standard analysis pipelines of highthroughput sequencing data has been to align the sequenced fragments of DNA (called reads) on a reference genome of a species. Further analysis reveals a set of positions where the sequenced individual differs from the reference genome. After years of these kind of studies, there is now a growing dataset of frequently observed differences between individuals and the reference. A natural representation of this gained knowledge is a variation graph where the reference sequence is the backbone and variations are encoded as alternative paths [START_REF] Schneeberger | Simultaneous alignment of short reads against multiple genomes[END_REF]. Aligning reads (pattern matching) on this labeled graph gives the basis for the new paradigm called computational pan-genomics [9]. There are already tools that use such ideas, e.g. [START_REF] Garrison Erik | Variation graph toolkit improves read mapping by representing genetic variation in the reference[END_REF].

Although there is a growing need to perform pattern matching on graphs in several situations described above, the idea of extending the problem of string searching in sequences to pattern matching in graphs was studied over 25 years ago as a search problem in hypertext [START_REF] Manber | Approximate string matching with arbitrary costs for text and hypertext[END_REF]. The history of key contributions is given in Table 1, where the two best known results for exact and approximate pattern matching, both taking quadratic time in the worst case, are highlighted. Note that errors in the graphs makes the problem NP-hard [START_REF] Amir | Pattern matching in hypertext[END_REF], so we consider errors in the pattern only.

A common feature of the bounds reported in Table 1 is the appearance of the quadratic term m |E| (except for the special cases of trees and the general NP-hard approximate version). Here m is the length of the pattern string and E is the set of edges of the graph. The quadratic cost of the approximate matching on graphs by Rautiainen and Marschall [START_REF] Rautiainen | Aligning sequences to general graphs in O(V +mE) time[END_REF] are asymptotical optimal under the Strong Exponential Time Hypothesis [START_REF] Impagliazzo | On the complexity of k-sat[END_REF] (seth) as (i) they solve the approximate string matching as a special case, since a graph consisting of just one path of |E| + 1 nodes and |E| edges is a text string of length n = |E| + 1, and (ii) it has been recently proved that the edit distance of two strings of length n cannot be computed in O(n 2-) time, for any constant > 0, unless seth is false [START_REF] Backurs | Edit distance cannot be computed in strongly subquadratic time (unless seth is false)[END_REF]. Hence this conditional lower bound explains why the O(m|E|) barrier has been difficult to cross.

We can only explain the complexity on approximate pattern matching on graphs, but nothing is known on exact pattern matching on graphs. Indeed, the classical exact pattern matching with a pattern and a text string can be solved in linear time [START_REF] Knuth | Fast Pattern Matching in Strings[END_REF], so one could expect the corresponding problem on graphs to be easier than approximate pattern matching.

In this paper we end up with a slightly surprising observation that exact and approximate pattern matching are equally hard on graphs. Namely, we show the conditional lower bound that an O(|E| Amir et al. [START_REF] Amir | Pattern matching in hypertext[END_REF] general approximate (2) NP-Hard 1997 Amir et al. [START_REF] Amir | Pattern matching in hypertext[END_REF] general approximate (1) O(N m lg N + m|E|) 1998

Navarro [START_REF] Navarro | Improved approximate pattern matching on hypertext[END_REF] general approximate (1) O(N m + m|E|) 2017

Vadaddi et al. [START_REF] Vaddadi | Sequence alignment on directed graphs[END_REF] general approximate (1) O((|V | + 1)m|E|) 2017 Rautiainen, Marschall [START_REF] Rautiainen | Aligning sequences to general graphs in O(V +mE) time[END_REF] general approximate (1) O(N + m|E|) 2019 Jain et al. [START_REF] Jain | On the Complexity of Sequence to Graph Alignment[END_REF] general approximate (2) NP-Hard on binary alphabet to find indexing schemes for graphs with other than best case or average case guarantees for fast exact pattern matching [START_REF] Sirén | Indexing graphs for path queries with applications in genome research[END_REF][START_REF] Gagie | Wheeler graphs: A framework for bwtbased data structures[END_REF].

Before going on to give the overview and details of the reduction, let us now fix the problem definition and seth formulation. Definition 1. Given an alphabet Σ, a labeled graph G is a triplet (V, E, L) where (V, E) is a directed or undirected graph and L : V → Σ + is a function that defines which string over Σ is assigned to each node. Definition 2. Let u 1 , . . . , u j be a path in graph G and P be a pattern. Also, L(u)[l :] and L(u)[: l ] denote the suffix of L(u) starting at position l and the prefix of L(u) ending at position l , respectively. We say that u 1 , . . . , u j is a match for P in G with offset l if the concatenation of the strings L(u 1 )[l :] • L(u 2 ) • . . . • L(u j-1 ) • L(u j )[: l ] equals P , for some l .

The Pattern Matching in Labeled Graphs (pmlg) problem is then defined as: input: a labeled graph G = (V, E, L) and a pattern P over an alphabet Σ. output: all the matches for P in G.

For example, in Fig. 1 pattern cde has two occurrences but pattern bccce does not occur. For our purpose it would be enough to exploit a decision version of the problem, namely, to be able to determine whether or not there exists at least one match for P in G, without reporting all of them. Note that the matching path for P can go through the same nodes multiples times in G as otherwise pmlg is trying to solve the NP-hard Hamiltonian path problem.

We now recall what is seth, namely, the Strong Exponential Time Hypothesis [START_REF] Impagliazzo | On the complexity of k-sat[END_REF]. This is a conjecture which is commonly used as a basis of reductions in the scientific community, even though its weaker version eth is more widely accepted.

Definition 3 ([17]). Let q-sat be an instance of sat with at most q literals per clause. Given δ q = inf {α : there is an O(2 αn )-time algorithm for q-sat}, seth claims that lim q→∞ δ q = 1.

In other words, it is hard to find an O(2 αn )-time algorithm for general sat for a constant α < 1. We use seth in the the following result, given that the best known algorithm for pmlg, devised 20 years ago [START_REF] Amir | Pattern matching in hypertext[END_REF], has an O(|E| m) time complexity. We can further strengthen the statement of this theorem by proving the following corollaries.

Corollary 5. The conditional lower bound stated in Theorem 4 holds even if it is restricted to graphs with binary alphabet for the labels, where each node has degree at most three. Corollary 6. The conditional lower bound stated in Theorem 4 holds even if it is restricted to labeled directed acyclic graphs (DAGs) with binary alphabet for the labels, where each node has the sum of indegree and outdegree at most three.

In order to achieve these results we break down our reasoning process in some intermediate steps. Since this is a conditional lower bound we will reduce sat to pmlg. Then we will show that having a truly subquadratic algorithm for pmlg would cause to solve sat in O( 2 Our reduction shares some similarities with those for string problems in [START_REF] Backurs | Edit distance cannot be computed in strongly subquadratic time (unless seth is false)[END_REF][START_REF] Bringmann | Quadratic conditional lower bounds for string problems and dynamic time warping[END_REF][START_REF] Amir Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF][START_REF] Backurs | Which regular expression patterns are hard to match[END_REF][START_REF] Backurs | Improving viterbi is hard: Better runtimes imply faster clique algorithms[END_REF] as it uses seth. The closest connection is with [START_REF] Backurs | Which regular expression patterns are hard to match[END_REF], where regular expression matching is studied (graph G F in Section 2.2 is analogous to the NFA derived from the regular expression matching of type | • | in [START_REF] Backurs | Which regular expression patterns are hard to match[END_REF]). At presentation level, the difference to earlier work is that we reduce directly from seth, while the earlier work uses an intermediate problem, orthogonal vectors, as a tool; our reduction can also be presented via the orthogonal vectors problem, but we preferred to work with seth directly since sat is more familiar to researcher from various research areas. On a more conceptual level, the new reduction has some interesting features of independent interest. Given a sat formula, our reduction builds a pattern and a graph, using some special characters in the pattern to match bridges in the graph that can be traversed in one direction only (even if the graph is undirected). Also, obtaining the reduction for a binary alphabet requires a suitable variable-length encoding of the characters to avoid certain paths in the graph.

An earlier version of this reduction can be found in the Master's thesis of the first author [START_REF] Equi | Pattern matching in labeled graphs[END_REF] (supervised by the two last authors).

Conditional lower bound for PMLG on undirected graphs

Consider a sat formula F with variables v 1 , . . . , v n and set C of k clauses. 1 We show how to generate a corresponding instance of pmlg. We build a pattern P ∈ Σ m of suitable length

m = Õ(2 n 2
) and a labeled graph G = (V, E, L), where |E| = Õ(2 n 2 ) and L : V → Σ * is the node labeling with strings from Σ * , such that P matches in G if and only if F is satisfied by some truth assignment of its variables. Recall that a truth assignment x is a tuple b 1 , . . . , b n , where b i ∈ {true, false} is the truth value assigned to each variable v i . We write x |= c to indicate that there exists at least one literal ∈ c satisfied by x (i.e. either = v i and b i = true, or = ¬v i and b i = false).

Our reduction builds a pattern with m = Õ(2

n
2 ) symbols from a binary alphabet Σ along with an undirected graph whose nodes are labeled with single symbols from Σ (i.e. L : V → Σ). This graph has |V |, |E| = Õ(2 n 2 ) nodes and edges, and maximum degree three. The reduction can be modified so that the graph is directed with maximum sum of indegree and outdegree at least three.

For presentation's sake, we begin with a pattern P using an alphabet of four symbols, Σ = {b, e, c, d}, whose interpretation is to label nodes according to their implicit functionality: begin (synchronization token), end (synchronization token), clause (marker), dummy (don't care); moreover, the resulting undirected graph G has unbounded degree; after that, we will show how to get the minimal degree configuration for G and how to achieve a binary alphabet, as depicted above.

We assume that n is an even number, without loss of generality, and denote by X the set of 2 n 2 possible assignments for the first n/2 variables, and by Y those for the last n/2 variables, that is,

X = {x i | x i = b (i) 1 , . . . , b (i) n 2 is a truth assignment for v 1 , . . . , v n 2 } and Y = {y j | y j = b (j) n 2 +1 , . . . , b (j) n is a truth assignment for v n 2 +1 , . . . , v n }.
We call elements of X and Y half-assignments and interpret notation |= accordingly. For example, y j |= c if and only if there is a literal ∈ c satisfied by the half-assignment y j (i.e. either = v i and b (j) i = true, or = ¬v i and b (j) i = false, for some i ≥ n 2 + 1). The reduction components to follow will be interpreted as follows. The pattern encodes by position, placing a symbol c to indicate which clauses cannot be satisfied by a half-assignment x i ∈ X; the other clauses are marked by d as they are already satisfied by x i alone; symbols b and e are employed to sync the half-assignments from X with portions of the graph, called gadgets.

The gadgets encode which clauses are satisfied by the half-assignments of Y , encoding each such clause with a distinct node labeled with c: when a symbol c in the pattern matches a node with label c in the graph, the corresponding clause is now covered by a half-assignment y j ∈ Y , while it was not yet covered by half-assignment x i ∈ X. If all the symbols c for x i are matched by the nodes of the gadget corresponding to y j , then assignment x i y j satisfyes the sat formula F ; also the other direction holds.

Parallel nodes labeled with d are introduced to deal with the cases when the pattern indicates that the corresponding clause is already satisfied by a half-assignment in X. Nodes labeled with b or e are used to match a half-assignment x i ∈ X with a half-assignment of y j ∈ Y . Details follow below.

Building the pattern

Pattern P is defined over the alphabet Σ = {b, e, c, d} using the half-assignments in X = {x 1 , . . . , x 2 If for instance we look at the first column we observe that c1,1 and c3,1 are missing meaning that y1 |= c1 and y3 |= c1. On the other hand we know that y2 |= c1 and y4 |= c1 since we have nodes c2,1 and c4,1. An example of a pattern that we are able to match is P = bccde while we would fail on P = bcdce.

∨ ) ∧ ( ¬ ∨ ∨ ) ∧ ( ¬ ∨ ¬ ) v 1 v 4 v 1 v 2 v 3 v 2 v 4 v 3 v 4 0 0 1 1 0 1 0 1 Truth Assignments y 1 y 2 y 3 y 4 c 1 c 2 c 3

Pairs of rows

for 1 ≤ h ≤ k, the hth symbol of string P xi is defined as

P xi [h] = c if x i |= c h d otherwise
We will prove that F is satisfiable if and only if we can find a match for this pattern in our graph, where the latter is made up of gadgets as specified below.

Graph gadgets for SAT formulas

Our gadget is an undirected graph G F = (V F , E F , L F ), illustrated in Figure 1 and defined as follows using the 2 In the set V F of nodes, we have a clause node c j,h for every possible pair y j , c h ∈ Y × C such that y j |= c h , and a dummy node d j,h for every possible pair y j , c h ∈ Y × C. Set V F also contains two special nodes, a begin node b and an end node e,

V F = {c j,h | y j |= c h , y j ∈ Y, c h ∈ C } ∪ {d j,h | y j ∈ Y, c h ∈ C } ∪ {b, e}
Labeling L F : V F → Σ is consequently defined, where a symbol c in the pattern that matches a node labeled with c in the graph will represent the fact a clause not satisfied by a certain half-assignment in X is actually satisfied by a certain half-assignment in Y . The d symbols are sort of "don't care", and b and e symbols synchronize the whole.

L F (u) =            b if u = b e if u = e c if u = c j,h d if u = d j,h
As shown in Fig. 1, the edges in the set E F connect b to every c h,1 and d h,1 , and connect every c h,k and d h,k to e, for 1 ≤ h ≤ k. Moreover, there is an edge for every pair of nodes that share the same j and are consecutive in terms of h coordinate (e.g. c j,h , d j,h+1 ), for

1 ≤ j ≤ 2 n 2 and 1 ≤ h ≤ k. E F ={(b, c j,1 ) | c j,1 ∈ V } ∪ {(b, d j,1 ) | d j,1 ∈ V } ∪ {(c j,k , e) | c j,k ∈ V } ∪ {(d j,k , e) | d j,k ∈ V } ∪ {(c j,h , c j,h+1 ) | c j,h , c j,h+1 ∈ V } ∪ {(c j,h , d j,h+1 ) | c j,h , d j,h+1 ∈ V } ∪ {(d j,h , c j,h+1 ) | d j,h , c j,h+1 ∈ V } ∪ {(d j,h , d j,h+1 ) | d j,h , d j,h+1 ∈ V }
We observe that pattern occurrences in G F have some combinatorial properties. As bP xi e contains k + 2 symbols, its matching path π = b, u 1 , . . . , u k , e in G F must traverse all distinct nodes by construction. Suppose by contradiction that at least one node in π has different j coordinate. This means that two consecutive nodes u h and u h+1 in π have coordinates j and j , with j = j . Node u h is actually either c j,h or d j,h , whereas u h+1 is either c j ,h+1 or d j ,h+1 . By inspection of these four possible cases, we observe that our construction of G F does not provide any edge connecting u h and u h+1 . Indeed, there is no edge that allows a node to change the j coordinate in the middle of a path. Hence we reach a contradiction. Finally, if one of the matching nodes were not consecutive in terms of h coordinate, by construction we know that we would not be following the shortest path to e (j) W hence it would not be possible to complete the match. Lemma 8. Subpattern bP xi e matches in G F if and only if there is y j ∈ Y such that the truth assignment x i y j satisfies F (i.e. x i y j |= F ).

Proof. By Lemma 7, we can focus on the k distinct nodes matching P xi , sharing the same coordinate j. We handle the two implications of the statement individually.

(⇒) Consider the partial assignment x i ∈ X. From the structure of the pattern we know that x i satisfies all the clauses c h for which P xi [h] = d. Since P xi has a match in G F , consider the assignment y j ∈ Y where j exists by Lemma 7, as observed above. We observe that by construction y j satisfies those clauses that x i cannot satisfy, namely those for which P xi [h] = c. Hence we have found a truth assignment x i y j that satisfies F .

(⇐) Consider a truth assignment x i y j that satisfies F , that is, all clauses c h for sat formula F are true. Consider now the nodes with coordinate j in G F . For h = 1, 2, . . . , k, if x i |= c h then P xi [h] = d and matching node d j,h exits in G F by its definition. If x i |= c h then it must be y j |= c h : thus P xi [h] = c and a matching node c j,h exists in G F by its construction. The definition of the edges of G F ensures that all the above nodes c j,h and d j,h , as we need, are properly linked to form a path of distinct nodes (for increasing values of h); it is so because they all share the same j coordinate. This implies that P xi matches in G F .

While the previous gadget is useful to check whether a half-assignment x i satisfies F using a given subpattern P xi ∈ b{c, d} k e, we need another "jolly" gadget that matches all subpatterns in b{c, d} k e (this is useful when x i does not satisfy F ). We concatenate 2 n 2 -1 instances of the latter gadget, thus obtaining the graph 2, whose definition is clear from the picture. The jth copy of the gadget substructure has a node b j followed by nodes c j,h , d j,h and then node e j , with 1

G U = G(V U , E U , L U ) illustrated in Figure
≤ j ≤ 2 n 2 -1 and 1 ≤ h ≤ k. The labels are L U (b j ) = b, L U (c j,h ) = c, L U (d j,h ) = d and L U (e j ) = e
(we may think about nodes c i,h and d i,h as disposed along two parallel lines). We place the edges (b i , c i, 1 ),(b i ,d i,1 ),(c i,k ,e j ),(d i,k ,e i ) for connecting the beginning and ending nodes of each gadget with its inner part. We connect nodes c i,h and d i,h with the edges (c i,h ,c i,h+1 ),(c i,h ,d i,h+1 ),(d i,h ,c i,h+1 ),(d i,h ,d i,h+1 ). We concatenate our gadgets one after the other using the edges (e i , b i+1 ), for i = 1, . . . , 2 n 2 -1.

Putting all together

Armed with gadgets G F and G U , we obtain the graph G = (V, E, L) from the sat formula F by combining them as illustrated in Figure 3. We take one instance of

G F = (V F , E F , L F ) and two instances of G U , say G (1) U = (V (1) U , E (1) U , L (1) U ) and G (2) U = (V (2) U , E (2) U , L (2)
U ), and two new nodes u and z, where their label is respectively e and b.

Then G = (V, E, L) has node set V = V F ∪ {u, z} ∪ V (1) U ∪ V (2)
U , preserving the node labels. The edge set is the union of the previous edge sets plus four edges: one connects the "last" node labeled with e in G U is connected to z. Remark. Each edge connecting a node labeled with e to a node labeled with b is a bridge in G (i.e. its removal disconnect G). As we shall see, the purpose of these bridges is dual since, within a matching path, the ith occurrence of eb in the pattern matches the ith bridge with labels e and b at its endpoints: (i) they synchronize the distinct subpatterns with the distinct (portions of the) gadgets, and (ii) they guarantee that the pattern matches a path of distinct nodes rather than a walk.

We now prove that the reduction is correct, first focusing on subpatterns of P .

Lemma 9. Pattern P matches in G if and only if a subpattern bP xi e of P matches in G F .

Proof. For the ⇒ implication, the bridges with endpoints labeled with e and b can only be traversed once in this direction, as P contains the sequence eb but does not contain be. Moreover, each occurrence of P must begin with one such bridge and end with another such bridge. For this reason each distinct subpattern bP xi e matches a path from either a distinct portion of G (l)

U (l = 1, 2)) or G F . Recall that G (1)
U and G The main result proves the correctness of our reduction.

Cost of the reduction

We analyze the cost of building the pattern P and the graph G from the sat formula F .

Implications on SETH

The last step in our proof of Theorem 4 is showing that any O(|E| 1-m)-time or O(|E| m 1-)time algorithm for pmlg unavoidably leads to a failure of seth. To this aim, assume that we have such an algorithm, say A. Given a sat formula F we perform our reduction stated in Theorem 10 obtaining pattern P and graph G in Õ(2

if F is satisfiable in Õ(2 n 2 2 n 2 (1-) ) = Õ(2 (2-) 2 n ) time. Since α = (2-)
2 < 1 we conclude that this implies to be able to solve sat in O(2 αn ) time with α < 1, making seth false.

3

From undirected graphs to DAGs, with binary alphabets

In this section we show that the graph G obtained from the reduction described in Section 2 can be transformed so that each node has degree at most three and label chosen from an alphabet of two symbols {0, 1}.

We describe how to modify the proof of Theorem 4 so that it holds for any graph of degree at least three. We observe that the graph built in the reduction in Section 2 has degree O(2 n 2 ). To obtain degree at most three, we first modify gadgets G F and G U to meet such requirement, and then adjust pattern P consequently. Finally, we obtain a binary alphabet for the labels, thus proving Corollary 5.

After that we prove Corollary 6, showing that the undirected graph can be easily transformed into a directed acyclic graph (DAG).

Maximum degree three

Revised gadget G F

As depicted in Figure 4(a), consider the O(2 n 2 ) edges connecting node b with nodes c j,1 and d j,1 in G F . We replace them by a binary tree structure whose nodes are new dummy nodes f l with labels L(f l ) = d for 1 ≤ l ≤ 2 n 2 -2. As for node e, we proceed along the same way and replace the edges connecting nodes c j,k and d j,k to e by a binary tree structure (this case is not shown in the figure). The internal nodes of these trees have degree at most three. This is not enough to guarantee degree at most three for each node in G F as nodes c j,h and d j,h could have degree four. For example, with some nodes d j,h-1 , d j,h and d j,h+1 , nodes c j,h-1 , c j,h and c j,h+1 could exists. Then both c j,h and d j,h would have degree four. This can be fixed as shown in Figure 4(b), adding two pairs of dummy nodes f with label L(f ) = d to lower the degree to three. 3 At this point, we added O(2 (2) j,h . Moreover, the new edges for the binary tree are as many as 3 One pair is placed between nodes c j,h-1 , d j,h-1 and nodes c j,h , d j,h via edges (c j,h-1 , f

(1) j,h-1 ), (d j,h-1 , f

(1) j,h-1 ) and (f (2) j,h-1 , c j,h ), (f (2) j,h-1 , d j,h ). The other pair of dummy nodes f is placed between nodes c j,h , d j,h and nodes c j,h+1 , d j,h+1 via edges (c j,h , f The edges connecting node b with nodes cj,1 and dj,1 are replaced by a binary tree structure. Note that, even if not reported in this figure, the same process is performed for the edges connecting nodes c j,k and d j,k with node e. (b) When c j,h-1 , c j,h and c j,h+1 exist, c j,h and d j,h have degree four. Hence pairs of dummy nodes are added to achieve degree three.

the nodes while for the other modifications we add one edge for each pair of dummy nodes. The overall time complexity to build the transformed G F does not increase significantly.

Revised gadget G U

Gadget G U has to be consistent with G F . We add (log 2 ) new nodes and one new edge per node, thus the overall time complexity will not be affected. The need for this step will be clearer when we will modify pattern P , as it has to match either G F or G U , so the same format of P is required in both types of gadgets.

We have another issue to handle. As in G F , there could be nodes c i,h and d i,h of degree four. In that case, we add pairs of dummy nodes f with label L(f ) = d following the same schema presented for G F and illustrated in Figure 4

Theorem 4 .

 4 For any constant > 0, the Pattern Matching in Labeled Graphs ( pmlg) problem for an alphabet of at least 4 symbols cannot be solved in either O(|E| 1-m) or O(|E| m 1-) time unless seth is false.

2 n 2 ) 2 n 2 ) = Õ( 2 n 2 ) 2 n 2

 22222222 αn ) time with α < 1. Our reduction costs Õ(time for a sat formula with n variables and k = O(poly(n)) clauses, where Õ is the shorthand for ignoring polynomial factors in n, e.g. O(kn2 . Hence the main steps can be synthesized as follows.Find a reduction from sat to pmlg.Ensure that this reduction costs Õ() time. Show that having a O(|E| 1-m) or a O(|E| m 1-) time algorithm for pmlg gives a solution for sat that makes seth fail.

n 2 } 2 eb of 2 n 2

 2222 and the set C = {c 1 , . . . , c k } of clauses of sat formula F . Specifically, it is built as the concatenation P = ebP x1 e bP x2 e . . . bP x 2 n strings where x i ∈ X and,

2 n 2 Figure 1 2 n 2 = 4

 221224 Figure 1Gadget GF for formula F , where n = 4, 2 n 2 = 4 and k = 3. If for instance we look at the first column we observe that c1,1 and c3,1 are missing meaning that y1 |= c1 and y3 |= c1. On the other hand we know that y2 |= c1 and y4 |= c1 since we have nodes c2,1 and c4,1. An example of a pattern that we are able to match is P = bccde while we would fail on P = bcdce.

n 2 2 n 2 }

 222 half-assignments in Y = {y 1 , . . . , y and the set C = {c 1 , . . . , c k } of clauses of sat formula F .

2

 2

Lemma 7 .

 7 If subpattern bP xi e matches in G F then all the nodes matching P xi share the same j coordinate and have distinct and consecutive h coordinates (i.e. either c j,h or d j,h for 1 ≤ h ≤ k). Proof. Gadget G F contains a single node b with label L(b) = b and a single node e with label L(e) = e. Morever, the shortest path from b to e contains k + 2 nodes (b and e included).

Figure 3 2 n 2 = 4

 3224 Figure 3 This figure shows how to construct G in the example we proposed before, where n = 4, 2 n 2 = 4 and k = 3. What we need to introduce to obtain the final graph G are the two solid edges that are connecting the two instances of GU with GF in the bottom part of the figure.

  labeled with b in G F ; the other connects the node labeled with e in G F with the "first" node labeled with b in G (2) U , plus u is connected to the first node labeled with b in G (1) U , and the last node labeled with e in G (2)

( 2 ) 2 n 2 2 n 2 e

 22222 U can match at most 2 n 2 -1 subpatterns of P each, while P has of them. Hence one subpattern bP xi e is forced to have a match in G F in order to have a full match for P .The ⇐ implication is trivial. In fact, if bP xi e has a match in G F then we can match bP x1 e, . . . , bP xi-1 e in G (1) U and bP xi+1 e, . . . , bP x in G

( 2 )

 2 U by construction, and have a full match for P in G.

Lemma 11 . 2 n 2 ) 2 n 2 ) 2 n 2 = Õ( 2 n 2 ) 2 n 2 2 n 2 = Õ( 2 n 2 ) 2 n 2 ) 2 n 2 ) 2 ) 2 n 2 ) 2 n 2 )

 1122222222222222222222222 Given a sat formula F with n variables, the corresponding pattern P and graph G can be built in Õ(time and space.Proof. Checking if an assignment satisfies a clause takes O(n) time which, for our goals, is negligible when compared to Õ(. Recalling that the number k of clauses is polynomially bounded in n, we observe that each P xi in P has k symbols that can be either c or d plus symbols b and e. Since P has 2 n 2 sub-patterns P xi , summing everything up we get a length of m = (k + 2) symbols. As for G U , it has gadgets each one having k nodes labeled with c, k nodes labeled with d, and nodes b i and e i . Hence there are (2 + 2k) total nodes. Each node has a constant number of incident edges (at most 4) thus their size is Õ(as well. As for G F , it has O(k nodes labeled with c and the same amount of nodes labeled with d plus those with b and e. In this case, each node has a constant number of edges but for b and e. Nevertheless, b and e have O(2 n of Exact Pattern Matching in Graphs edges each, therefore the total amount of edges is again Õ(. For connecting G F to the two instances of G U we are adding just 2 edges. Since the pattern and the graph have size Õ(, we conclude that the cost of our reduction is indeed Õ(2 n 2 ).

n 2 ) 2 n 2 ) 2 n 2 )

 22222 time by Lemma 11, observing that |E| = Õ(and m = Õ(. At this point, no matter whether A has O(|E| 1-m) or O(|E| m 1-) time complexity, we will end up with an algorithm deciding

n 2 )

 2 dummy nodes f for the binary tree, and O((k -

( 1 )

 1 j,h ), (d j,h , f (1) j,h ) and (f (2) j,h , c j,h+1 ), (f (2) j,h , d j,h+1 ).

2 Figure 4

 24 Figure[START_REF] Angles | Survey of graph database models[END_REF] The transformation of gadget GF . (a) The edges connecting node b with nodes cj,1 and dj,1 are replaced by a binary tree structure. Note that, even if not reported in this figure, the same process is performed for the edges connecting nodes c j,k and d j,k with node e. (b) When c j,h-1 , c j,h and c j,h+1 exist, c j,h and d j,h have degree four. Hence pairs of dummy nodes are added to achieve degree three.

n 2 +1 2 n 2 - 1 ) = Õ(2 n 2

 22212 ) -1 = n 2 dummy nodes f with label L(f ) = d between every b i node and the nodes c i,1 and d i,1 following it. We also add n 2 dummy nodes f with label L(f ) = d between every node e i and the previous nodes c i,k and d i,k . We are adding 2 n 2 (

2 n 2 )

 22 (b). In this way we are introducing 2(k -1)(2 n 2 -1) = Õ(new nodes and one edge for each pair of dummy nodes which do not change the time complexity of the reduction.

  1-m)-time or an O(|E| m 1-)-time algorithm for exact pattern matching on graphs cannot be achieved unless seth is false. This result explains why it has been difficult State of the art for PMLG

	Year	Authors	Graph	Exact/	Time
				Approximate
	1992	Manber, Wu [20]	DAG	approximate (1)	O(m|E| + occ lg lg m)
	1993	Akutsu [2]	Tree	exact	O(N )
	1995	Park, Kim [22]	DAG	exact (3)	O(N + m|E|)
	1997	Amir et al. [3]	general	exact	O(N + m|E|)
	1997

Table 1

 1 Legend: V = set of nodes, E = set of edges, occ = number of matches for the pattern in the graph, m = pattern length, N = total length of text in all nodes, (1) errors only in the pattern, (2) errors in the graph, (3) matches span only one edge. The two rows highlighted in gray report the best known bounds for exact and approximate pattern matching.

Theorem 10 .

 10 Pattern P matches in G if and only if the sat formula F is satisfiable. Proof. By Lemma 9, P matches in G if and only if a subpattern P xi matches in G F . By Lemma 8 this holds if and only if the truth assignment x i y j satisfies F , hence F is satisfiable.

In this paper we discuss the interesting case where k = O(poly(n)).

Acknowledgements

The first two authors are grateful to Alessio Conte and Luca Versari for providing their comments on the reduction. The last author wishes to thank the participants of the annual research group retreat on sparking the idea to study seth reductions in this context. We thank the anonymous reviewers of an earlier version of this paper for useful suggestions for improving the presentation and for pointing out the connection to regular expression matching.

Funding This work has been partially supported by Academy of Finland (grant 309048)

Revised pattern

It is worth noting that P ∈ eb ({c, d} + eb) + in this way. The number of new symbols added before and after the subpatterns is n 2 2

2 ) while the ones inserted inside them are 2(k -1)2

). The time cost of the reduction does not increase significantly.

Binary alphabet

The last step consists in defining a binary encoding α of the symbols Σ = {b, e, c, d}, namely,

Given any string x = x [1..m], we define its binary encoding α(x) = α(x [START_REF] Amir Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]

The following useful synchronizing property holds, recalling that each edge connecting a node with label e to a node with label b is a bridge in (transformed) G. Lemma 12. For any string x ∈ Σ + , its binary encoding α(x) contains 0110 if and only if x contains eb.

Proof. We observe that e and b are encoded by two bits each, while c and d are enconed by four bits each. Hence, 0110 can appear by concatenating the binary encoding of two or three symbols. On the other hand, eb occurs in x if and only if it occurs in a substring of length 3 of x. Consequently, it suffices to check the claim by inspection of all the 64 substrings of x of length 3, ccc, . . . , eee, and their encodings to see that the property holds.

Any walk matched by the revised pattern P crosses the bridges in the direction from e to b. Lemma 13. For any pattern P obtained in the reduction, its binary encoding α(P ) does not contain 1001 = α(be).

Proof. Recalling that P ∈ eb ({c, d} + eb) + , all the possible substrings of length 3 in P by construction are of the forms b{c, d}e, eb {c, d}, {c, d}eb, b{c, d} 2 , {c, d} 2 e, and {c, d} 3 . By inspection of this small number of cases, none contains be, and none of their binary encodings contains 1001.

An immediate consequence of Lemma 12 and 13 is that the encodings preserve the occurrences. Let G be the transformed graph, and P be the revised pattern in the reduction. Let α(G ) denote the graph obtained from G by relabeling its nodes with the binary encoding α of their labels.

Lemma 14. In the reduction, P matches in G if and only if α(P ) matches in α(G ).

Proof. It follows by Lemma 12 and 13, and the fact that all the edges whose endpoints have one label e and the other label b are bridges, and they are traversed in the direction from e to b when matching P .

In the encoding above, each node stores two or four bits. By replacing it with a chain of two or four nodes with a single bit as a label, we obtain the proof of Corollary 5.

Directed acyclic graphs

In order to prove Corollary 6, we observe that the proof of Theorem 4 can be easily modified in order to work also for DAGs.

Considering the definitions of edges E F and E U in the proof of Theorem 4, and the transformation described so far, we immediately obtain a directed graph G that is acyclic. Indeed, because of bridges and occurrences of eb in the pattern, each pattern match must begin with some bridge, end with a different bridge and lay along a path from the first to the last bridge in the graph. So the edges can be oriented by construction from left (first bridge) to right (last bridge), as it can be checked in Fig. 1234.

Conclusions

We studied the complexity of pattern matching on labeled graphs, giving a seth conditional quadratic lower bound for the exact pattern matching. In strings the exact pattern matching takes linear time whereas the approximate pattern matching takes quadratic time under a matching conditional lower bound. Differently from strings, our result along with the upper bounds in [START_REF] Amir | Pattern matching in hypertext[END_REF][START_REF] Rautiainen | Aligning sequences to general graphs in O(V +mE) time[END_REF] imply that the exact and approximate pattern matching (the latter with errors in the pattern) have the same complexity under the seth conjecture. Our conditional lower bound uses a binary alphabet and holds even if restricted to nodes of maximum degree at most three for undirected graphs, and to nodes of maximum sum of indegree and outdegree at most three for directed acyclic graphs (DAGs). Two border cases are left if the maximum degree or sum of indegree and outdegree is at most two: a) when the undirected graph is a simple path or a cycle, and pattern matching goes along a walk (so it is a sort of zig-zag string matching), and b) when the graph is a directed cycle. For a), we can convert each edge into a pair of arcs and apply the known quadratic algorithm in [START_REF] Amir | Pattern matching in hypertext[END_REF]. On the other hand, we can extend our reduction to derive a matching seth lower bound for this case [START_REF] Equi | On the complexity of exact pattern matching in graphs: Determinism and zig-zag matching[END_REF]. For b), we can adapt any known string matching algorithm (e.g. [START_REF] Knuth | Fast Pattern Matching in Strings[END_REF]) to get linear time.

An interesting and natural question for directed graphs is what happens when the graph is deterministic, that is, for each symbol c and each node v, there is at most one neighbor of v labeled with c. Unfortunately, this does not make the problem any easier. Although our reduction creates an inherently non-deterministic graph, it is possible to alter the reduction scheme to create a deterministic graph [START_REF] Equi | On the complexity of exact pattern matching in graphs: Determinism and zig-zag matching[END_REF].


Valence Cristiani

Maxime Lecomte

Thomas Hiscock

A Bit-Level Approach to Side Channel Based Disassembling

Keywords: Side-channel analysis, Reverse engineering, Hardware security, Leakage analysis

Side-Channel Based Disassembling (SCBD) is a powerful application of side-channel analysis that allows recovering instructions executed by a processor from its physical leakages, such as the electromagnetic field (EM) emitted by the chip. These attacks directly compromise code confidentiality, but they can also reveal to an adversary many critical information on the system's internals. In this work, we propose a new approach for SCBD that directly focuses the bit encoding of an instruction using local EM leakage. We exploit a very precise bit-level leakage model and derive from it new algorithms that aim at recovering the actual bit values. We also propose strategies to automate the complex tasks of finding the best EM probe positions and combining them to improve results. On a PIC16 target, our method succeed in recovering the bits of an instruction with an average rate of 99,41% per bit. Compared to the state of the art, our disassembler is easier to train, recovers more information about instructions than just opcode and requires almost no modifications to target other processor architectures. Thus, this kind of disassemblers might become a threat to more complex processors, where side-channel disassembling has not been proved to be feasible yet.

Introduction

Side-Channel Based Disassembling (SCBD) is the task of recovering instructions executed by a device based on its physical signature, known as side-channel leakages. For more than two decades many techniques and tools have been developed to extract secrets from sources such as timing variations [START_REF] Kocher | Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[END_REF], power consumption [START_REF] Kocher | Differential power analysis[END_REF], electromagnetic field [START_REF] Quisquater | Electromagnetic analysis: Measures and countermeasures for smart cards[END_REF] (EM), acoustic noise [START_REF] Genkin | RSA key extraction via low-bandwidth acoustic cryptanalysis[END_REF] and many others. While side-channel analysis research is primarily concerned with the security of cryptographic primitives, there is also an active research on SCBD [START_REF] Eisenbarth | Building a side channel based disassembler[END_REF][START_REF] Msgna | Precise instruction-level side channel profiling of embedded processors[END_REF][START_REF] Park | Power-based side-channel instruction-level disassembler[END_REF][START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF]. Indeed an accurate quantification of the instruction leakage is a very useful security indicator for many systems. Obviously, SCBD is a direct threat to code intellectual property, which can be a requirement for manufacturers that put lots of efforts into the development of an algorithm. The instruction stream can also reveal sensible code regions such as block ciphers or function entries. Such information can be exploited by an attacker to drive more specific attacks such as fault injections. Interestingly, SCBD can also be used as a non-intrusive malware detection mechanism [START_REF] Msgna | Verifying software integrity in embedded systems: A side channel approach[END_REF].

The SCBD task can be regarded as a supervised machine learning classification problem, where a side-channel trace has to be associated to a sequence of executed instructions. The natural approach is to divide the global trace into instruction traces correctly labeled. These traces will then feed a learning algorithm in order to build a classifier able to make accurate predictions on the instructions that corresponds to an attack trace. However, training such a classifier is difficult in practice, as many target-specific knowledge is required to create a model. Furthermore, with complex processor architectures and deep pipelines, the switching noise generated by other activities in the core becomes preponderant. A proper randomization of all of these surrounding elements requires a huge amount of data, as well as complex profiling code snippets. Thus, while the opcode classification approach proved to work on small microcontrollers [START_REF] Park | Power-based side-channel instruction-level disassembler[END_REF][START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF] it is unlikely that it would scale to more complex processors.

Contributions. In this work, we propose an alternative approach to SCBD that overcome these issues. The core idea is to create a classifier directly on the bits that encode the instructions. This approach requires almost no assumptions on the target architecture, as in any processor, the bits of the instructions are transferred from memory to the processor and then manipulated, which may introduce leakages that can be exploited. Furthermore, the training is greatly simplified: the profiling can be performed on random code snippets, and by construction a bit-level approach allows having more training data available per class. We also show how exploiting very local leakages and combining EM measured at different positions greatly improves the accuracy.

Through this paper, we detail the construction of a bit-level SCBD (section 3) and evaluate its performances on a PIC16F microcontroller (section 4 and 5). We manage to get an average of 99.41% recognition rate per bit which leads to an opcode recognition rate as efficient as current state of the art. However, our disassembler recovers much more information encoded in the instructions (literal values, register numbers, etc.). These results suggest that the bit-level approach proposed is worth considering for SCBD on more complex cores.

Background

Structure of a side-channel disassembler

The high-level structure of a side-channel disassembler as a supervised machine learning classification task is shown in Figure 1. During a profiling phase, the attacker has access to a clone of the target device on which he can run arbitrary programs. He then collects side-channel data, such as the EM field, during the execution of several profiling code snippets in order to train a classifier. During the attack phase, the classifier is applied on unknown traces to predict and recover instructions. An attack trace usually contains many instructions, thus a preliminary step is required to divide the trace of a program into individual instruction traces. On small devices, instructions have a constant execution time, hence a fixed-size windows is enough to extract instructions. But with complex cores this operation may require a more advanced strategy. For each class c, the profiling phase infers the parameters µ c , Σ c from a set of observations (x c ) using classical statistical estimators. Due to its proximity with the quadratic discriminant analysis (QDA) technique in the machine learning field, we use the terms QDA and TA interchangeably.

However, not all samples in a trace contain relevant information. A common practice is to apply feature extraction techniques to reduce the computational cost of the attack. In a nutshell, these techniques transform a trace of p samples into a trace of d samples (with d p) while preserving -hopefully-most of the information. Both the training and the attack phases are performed in this reduced feature space. The most common feature extraction techniques include the Principal Component Analysis (PCA) and Linear Discriminant analysis (LDA).

Related work

Early side-channel based reverse engineering. The use of side-channel analysis for software reverse engineering was first suggested by Quisquarter et. al [START_REF] Quisquater | Automatic code recognition for smart cards using a kohonen neural network[END_REF] in 2002, who described an instruction classifier based on a neural network. Unfortunately, they did not provide experimental results. A leakage analysis on a Java card by Vermoen et. al [START_REF] Vermoen | Reverse engineering java card applets using power analysis[END_REF] proved that some instructions (Java bytecodes) could be identified in a power trace, but they did not propose an instruction recovery algorithm. In his master thesis, Goldback [START_REF] Goldack | Side-channel based reverse engineering for microcontrollers[END_REF] constructed a very detailed power leakage model of a 8-bit Microchip PIC16 microcontroller. He managed to perform a template attack [START_REF] Chari | Template attacks[END_REF] to recover up to 75% of correct instructions on a small set of 4 opcodes.

Concurrently, Novak et. al [START_REF] Novak | Side-channel based reverse engineering of secret algorithms[END_REF] and Clavier et. al [START_REF] Clavier | Side channel analysis for reverse engineering (SCARE), an improved attack against a secret A3/A8 GSM algorithm[END_REF] used side-channel analysis to perform reverse-engineering on encryption algorithms involving secret permutation tables (A3/A8). While these attacks are often referred as "Side Channel Analysis for Reverse Engineering" (SCARE), they do not allow any kind of instruction flow reconstruction.

Side-channel based disassembly. The first real side-channel based disassembler was described by Eisenbarth et. al [START_REF] Eisenbarth | Building a side channel based disassembler[END_REF] in 2010. They constructed an opcode classifier using a template attack. Thanks to Hidden Markov Models they managed to exploit prior knowledge on instruction distribution and improve the accuracy of their disassembler by a few percents. On a PIC16 microncontroller using power consumption, they managed to get a 70% recognition rate on test data and 40% on real programs. Strobel et. al [START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF] also described an opcodebased side-channel disassembler, working on EM. They concluded that EM contains much more information than power consumption and managed to get 90% recognition rate on real programs and 95% on test programs. Msgna et. al [START_REF] Msgna | Precise instruction-level side channel profiling of embedded processors[END_REF] constructed an instruction classifier based on a k-Nearest Neighbors (k-NN) algorithm. They reported a 100% instruction recognition on 35 instructions of an ATMega163 microcontroller. However, this classifier was not evaluated on real programs and [START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF] could not reproduce their results. Park et. al [START_REF] Park | Power-based side-channel instruction-level disassembler[END_REF] constructed a SCBD on a ATMega328P exploiting knowledge of the hardware used by each instruction. They reported a 99.03% recognition rate thanks to advanced noise reduction preprocessing techniques (based on discrete wavelet transforms) and a hierarchical classification as suggested by McCann et. al [START_REF] Mccann | Towards practical tools for side channel aware software engineering: 'grey box' modelling for instruction leakages[END_REF][START_REF] Mccann | ELMO: Emulating leaks for the ARM Cortex-M0 without access to a side channel lab[END_REF].

3 Construction of a bit-level side-channel disassembler

Challenges of bit-level instruction recovery

Processor instructions are usually encoded as a binary word (denoted I for the rest of this paper) of 8 up to 128 bits which contains information such as the opcode, registers and literal values used in the instructions. Our approach consists in attacking bits of I independently, which requires to train a distinct classifier for each bit of the instruction. Although this idea sounds pretty straightforward, it comes with viability questions that we discuss hereafter.

Distinguishing bit level variations, which impact consumption in a very tiny manner, requires a high signal to noise ratio. More than this, each bit should have its own leakage characteristics, otherwise, distinguishing for example the 2digits binary words 01 and 10 would not be possible. As explained in section 3.4, we suggest using EM with multiple probe positions to exploit local leakage and thus, increase chances of detecting such leakage differences between bits.

Another problem is that we suggest to attack independently some bits whose impact on the physical quantities measured are not independent. Small groups of bits of I are sometimes only interpretable as a whole and not separately. To address this issue, we propose to analyze only the part of the trace that corresponds to the fetching of the instruction, totally ignoring the actual execution of the instruction. While this may be interpreted as a loss of information, this drastically reduces the dependencies between the bits on the power consumption. In other words, we only analyze the update of the instruction register and not its actual execution behavior.

Leakage model and classification

A leakage model for individual bits of the instructions has to be selected in order to derive the set of classes C of the bit classifiers. The most common models are the Hamming Weight and Hamming distance models which at the bit level, respectively estimate the leakage as the bit value and as the bit toggle. A more accurate model known as the "signed Hamming distance" (SHD), introduced in [START_REF] Peeters | Power and electromagnetic analysis: Improved model, consequences and comparisons[END_REF] states that with precise electromagnetic measurements, the direction of the bit toggle can also be distinguished.

Based on these observations, we selected a leakage model with 3 possible target events at a given time for each bit: the bit stayed constant, it switched from 0 to 1 or switched from 1 to 0. We denote T = {constant, 0 → 1, 1 → 0} the set of these transitions. Following the formalism introduced in section 2.1, for each bit of the instruction a classifier with C = T is created. It combines LDA for feature extraction and QDA for the actual classification. The training phase can be done on random instructions, with correctly labeled bit transitions, which greatly simplifies the process. Then, for an observed sequence of N instructions, the classifier is applied to all the instructions successively, and yields a finite sequence of pair: T = (t n , p n ) 1≤n≤N of bit transition associated with its probability.

From Signed Hamming distance to bit values

The sequence T still needs to be transformed into a sequence of bit values. However, finding the optimal bit sequence is not straightforward, as each bit prediction influences the predictions for other bits. We propose a simple algorithm that perform this task. The sequence T generated by the classifier is given as input to the FindBits Left function (shown in Algorithm 1) which maintains a state bit (b s ) and updates its value according to the transitions encountered. In case of 0 → 1 or 1 → 0, the current state bit is set to the transition final value. When no transition occurred, the current bit value is kept. The algorithm also computes a confidence in the bit value returned (p s in Algorithm 1). This value is overwritten on a bit toggle, but is decreased when a constant transition is taken. Intuitively, we should be less confident in a constant transition as we take the precedent value as output, which could also be wrong. We explored different strategies to update p s in this case. Based on our experiments, an efficient one is to multiply p s by the confidence of the actual transition. This confidence value is useful for comparing different predictions for the same bit. Indeed, a transition reveals information about both the initial value and the final value. The FindBits Left procedure only uses the final value so far. Thus, a possible improvement is to tweak this function and define FindBits Right which perform the same algorithm in reverse order to exploit the information on the initial value. The right scan works the same way as the left scan but uses the initial value of the transition as the current bit value instead of the final value. The improved algorithm, denoted FindBits L+R , runs both versions of FindBits, align the two output sequences so that the n th element of each sequence corresponds to the same bit transition, and compare the two sequences selecting the bit value with the highest confidence. An example of this algorithm is shown in Figure 2. We notice that by construction FindBits Left and FindBits Right cannot give output until the first bit toggle encountered. From the previous algorithms the success rate (SR) of our classifier is defined as the number of correct bit predictions divided by the number of instructions.

Exploiting local information

Our classification uses EM field as input data rather than power consumption. Indeed, EM field with a careful probe positioning allows capturing very local effects such as single bit leakages. As we attack each bit of I independently, the best positions are likely to be different between the bits.

Choosing the best positions. The ideal approach to select the best probe position would be to exhaustively walk a grid of n × m positions above the circuit, run the attack on each position and select the one with the highest SR. However, this strategy can quickly become too expensive in terms of computations. For example, even a small 20 × 20 grid leads to 400 different positions. In our case, the longest part of the attack is the feature extraction (LDA). In order to speed up the cartography we perform the attack on a very reduced set of k points of interest (PoI). It can be viewed as an additional feature extraction step performed before the LDA during the cartography. This PoI extraction transforms the input traces (x i ) of p samples into k p dimensional vectors (x i ). We choose to keep the k samples x(t) that maximize the Mean Difference (MD):

M D(t) = c 1 ,c 2 ∈T , c 1 =c 2 E[X(t) | C = c 1 ] -E[X(t) | C = c 2 ]
Choosing the value of k can be done empirically observing the evolution of the SR as k decreases, at some fixed positions. Although the SRs may be lower with this additional step, we assume that this should not drastically change the ranking of the positions. Once the best positions has been found, the actual attack can be run with either a higher value of k or without the PoI extraction.

Algorithm 2: FindPos

Input: M, a list of EM measurements at different positions in a set G Output: P ⊂ G, a subset of positions to be combined Combining different positions. In a previous work, Strobel et. al. [START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF] combined EM traces acquired from different positions by concatenating them before the features extraction. However, finding the best combination of positions (which maximise the SR for instance) is hard in practice due to an exponentialsize search space. We propose a simple greedy algorithm (see algorithm 2) that searches a good subset of positions to attack one bit. In a nutshell, the algorithm builds iteratively a set P of best positions. At each iteration, the algorithm attempts to add each one of the remaining positions to P. The one that improves the most the SR is added to P. The algorithm may exit earlier if the success rate does not improve enough (this threshold is defined by ).

Leakage analysis of the PIC16F

Overview of the PIC16F

Our experiments are conducted on a PIC16F15376 Microchip microcontroller from the MPLAB Xpress evaluation board. Besides being ubiquitous in embedded systems, this family of PIC microcontrollers is a common reference in the SCBD literature [START_REF] Eisenbarth | Building a side channel based disassembler[END_REF][START_REF] Goldack | Side-channel based reverse engineering for microcontrollers[END_REF][START_REF] Strobel | SCANDALee: a side-channel-based disassembler using local electromagnetic emanations[END_REF] and allows a fair comparison of our results. The PIC16F15376 has around 50 instructions which are encoded on 14 bits. A typical instruction contains from 3 to 6 bits that are used to match the instruction (the opcode in some sense). The remaining bits encode the arguments of the instruction such as a control bits, source/destination registers or literal values.

Architecture. A simplified internal architecture of the PIC16F is depicted on Figure 3. Excluding jumps, all instructions require 4 clock cycles to complete. During the execution of an instruction, the next one is prefetched from FLASH memory, thus this processor has a 2-stage pipeline: prefetch and execution. The instruction bit leakages are most likely to be caused by this prefetching and the instruction register activity. Jump instructions require 4 additional clock cycles to be executed but can be regarded as the actual instruction followed by a nop. This dummy instruction is actually only used to refill the pipeline after the jump and our disassembler always detect it as a nop.

3: Architecture of the PIC16F

Side-channel behavior. A taste of EM and power side-channel traces obtained during the execution of 3 instructions are shown in Figure 4. Both were acquired using the measurement setup described in section 4.2. We stress that in all of the experiments, the PIC16 is clocked at 20 Mhz, except for Figure 4 where the clock was reduced to 1MHz to distinguish power peaks (at 20Mhz, the power curve is flat). The 4 execution cycles are clearly visible on the traces. As expected, the EM behavior is much more local: some peaks have different amplitudes and small temporal shifts based on the probe position.

Our experimental setup

Our experimental setup is presented in Figure 5. We acquire the near field electromagnetic emanations of the PIC16F through an EM Langer probe, an ICR HH 100 27 with a bandwidth of 6 GHz. The probe is placed over the IC package without any depackaging, at less than 500µm from the package thanks to a high precision motorized XYZ table. The probe is connected through a lownoise amplifier to a digital oscilloscope (DSO) from Rohde & Schwarz (RTO 2024) which has a bandwidth of 2 GHz and a sample rate set to 10 GS/s. The PIC is clocked by an external reference set at 20 MHz. A GPIO of the PIC is used to synchronize the oscilloscope acquisition with the computation. A typical trace may span over several milliseconds and is made of thousands of instructions. To avoid synchronization issues, the clock of the PIC is generated by a signal generator (FI5350GA) which is also connected to the reference clock of the DSO. This setup ensures that the PIC and the DSO stay synchronized and that no post processing is required to divide a trace into individual instructions.

Study of single bit leakages

This section presents three experimental results which confirm that there exists probe positions where 1) single bit leakages actually occur, 2) each bit influences the EM field independently from other bits and 3) the SHD leakage model suggested in section 3.2 is appropriate. These experiments are seen as pre-attack analysis to validate the requirements for a bit-level disassembler to be successful. For concision and simplicity, only the behavior of the 8 lower bits of I (14-bit PIC instructions) are analyzed. These specific bits encode literal values and can be set to an arbitrary value still creating a valid instruction if the remaining 6 upper bits of I are set to an opcode that uses a literal value. As an example, we will use movlw k (which is encoded as 110000 k base 2 ) that loads the literal value k into the processor accumulator register.

Leakage differences between bits. To demonstrate that single bit leakages are distinguishable, we perform Welch's t-test [START_REF] Schneider | Leakage assessment methodology[END_REF] between traces of movlw 0 and movlw 2 j , with 0 ≤ j ≤ 7. This test evaluates whether there are significant differences on traces when a single bit of the instruction changes. In the profiling code, a nop (encoded with fourteen 0s) is placed before each movlw instruction, so that the test works for any leakage model. The t-test is performed on all 400 probe positions of a square (2mm × 2mm) grid (20 × 20) centered over the chip. Many probe positions with a successful t-tests (that goes over a threshold of 4.5) were found, which means that the SNR in our setup is good enough to detect single bit variations. Figure 6a and6b show respectively positions where a t-test for j = 0 and for j = 4 are very different from the others. Intuitively, these two positions may bring useful information to determine respectively the value of bit 0 and bit 4 of I. Figure 6c shows a position where all t-tests are distinct from each other. The same experiment was performed with other literal instructions such as addlw or xor and gave similar results.

L literal (k) = L(movlw k) -L(movlw 0)
If the leakage of bits are independent, one would expect that the leakages of individual bits can be summed to obtain the leakage of a given word, formally for any subset J of {0, 1, 2, 3, 4, 5, 6, 7}, one should have:

j∈J L literal (2 j ) = L literal   j∈J 2 j  
We verified this equation empirically for some of the probe positions found in the previous experiments. Figure 7 shows an example where J = {0, 1, 2, 3, 4, 5, 6, 7}. All the small amplitude curves represent the leakage function L literal (2 j ) for 0 ≤ j ≤ 7. The dark and light blue lines represent respectively the sum of all the individual leakages and the leakage of 255 which is equal to 7 j=0 2 j . These two lines clearly seem to match. One could argue that this experiment is not enough to really show that each bit contributes independently to the global leakage. However, it still increases our confidence in the feasibility of the attack. Fig. 7: Leakage independence Leakage model. All experiments presented so far analyzed the fetching of instructions preceded by a nop, so that the results are agnostic to the leakage model. To confirm that the signed Hamming distance is an appropriate model, we choose some the probe positions with high t-test associated to one particular bit of I. Then, we analyzed the leakages in terms of transitions of this bit (all the other bits being constant). Figure 8 shows the EM traces for multiple transitions of the bit 0. This clearly illustrates that the three classes from the SHD model create a good partitioning of traces.

Mono-spatial attack

The attack was first conducted for each bit on each of the 20 × 20 grid (400 positions) that was used for our leakage analysis. The SR of the attack (using the FindBits L+R algorithm) on all the grid and for each bit is shown in Figure 9 (a Gaussian interpolation has been applied to the raw data). Surprisingly, each bit has its own spatial signature: the "hot areas", where the attack has a better success rate, strongly depend on the bit. The best success rates obtained for each bit are given in table 1. The FindBits L+R algorithm slightly improves the accuracy of the attack. While most bits are recovered with a high accuracy, a few (bits 8, 9, 10, 11), hardly get above 80%. These results can be improved by combining measurements from multiple positions. 1: Success rate at the best probe position for each bit

Multi-spatial attack

We evaluate the multi-position attack described section 3.4 by collecting and combining data from up to 14 positions using algorithm 2. Figure 10 shows how adding more positions affects the SR of each bit. Note that for a given bit, we stop collecting new positions when the SR improvement is too low. These results show that the low SR of some bits in the mono-spatial case (bits 8 to 11) can be brought up to 97 % and more with several additional positions. Once the best position combination has been found it is still possible to increase the number of sample kept by the PoI extraction: table 2 shows the SR of a multi-spatial attack where the number of PoI is higher (k = 400). All the SR are above 98.4 %, we achieved a 100 % SR for 6 bits. The average of the 14 SR is 99.41% which leads to 95% of the instructions being recovered without any faults. The acquisition time for this attack is about one hour, the training of all the classifiers takes approximately 30 minutes and the actual attack is instantaneous. Table 2: Success rate for a multi-spatial attack

Template portability

In a realistic context, the training phase would be performed on a clone of the target. This introduces the risk of overfitting on the clone device characteristics. Our first attempt to port the attack was no exception to the rule: applying our classifier to a different target completely failed. However, the SR cartography for two different targets shown in figure 9 reveal clear similarities, which suggests that the attacks behave almost the same on the two targets. More precisely the SR cartography is almost the same but shifted by a constant vector of norm around 300µm. We successfully conducted an attack between the two target with roughly the same SR as in the mono-target case simply by shifting all the probe position at the acquisition time on the second circuit. In a real attack scenario, we argue that the shift could be brute-forced (until a high SR is reached) by attacking a known sequence of instructions such as the boot code.

Conclusion and further work

In this work, we described a new kind of side-channel disassembler that uses bit-level classifiers to recover instructions from non-invasive EM measurements. This approach requires a very precise experimental setup to discriminate small bits variations in traces, especially on very a low-power device like a PIC16F microcontroller. Fortunately, the algorithms proposed in this paper can fully automate the recovering process. Furthermore, we observed that the disassembler is portable between different chips of the same family, which makes this kind of attacks truly realistic. A bit-level instruction disassembler is a huge gain in terms of genericity. The training process is greatly simplified compared to an opcode classifier because it can be performed on random binaries instead of carefully crafted assembly snippets. We demonstrated that such a disassembler achieve good recognition rate, with an average success rate of 99.41% on a bit level and 95% on the full 14-bits instruction. This result may be improved by exploiting prior knowledge on the program such as instruction transition probability, invalid opcode, etc. . . It seems that our approach can be extended to recover other valuable information from processors such as runtime register values. Moreover, this work opens interesting perspectives regarding the side-channel disassembling on pipelined processors, which remains an open problem. Future work will aim at validating our approach on more complex processors.

Fig. 1 :

 1 Fig. 1: High level architecture of a side-channel disassembler The goal of a classifier is to associate a class c ∈ C to a trace x (a realization of a random variable X) of p samples. In an opcode-based classifier C is the set of opcodes of the target architecture, for example C = {add, xor, load, . . . }. The template attack (TA) of Chari et. al [1], used by most opcode-based classifiers [3, 13, 18] build an estimation of Pr(X | C = c) during the profiling phase which is then used in the attack phase to compute Pr(C = c | X) thanks to Bayes' theorem. Given an unknown instruction trace x, an attacker selects the class that maximizes Pr(C = c | X = x). The TA models the per-class probability density Pr(X | C = c) as a multivariate Gaussian distribution denoted N (µ c , Σ c ), where µ c is the mean vector and Σ c the covariance matrix of the distribution. For each class c, the profiling phase infers the parameters µ c , Σ c from a set of observations (x c ) using classical statistical estimators. Due to its proximity with the quadratic discriminant analysis (QDA) technique in the machine learning field, we use the terms QDA and TA interchangeably. However, not all samples in a trace contain relevant information. A common practice is to apply feature extraction techniques to reduce the computational cost of the attack. In a nutshell, these techniques transform a trace of p samples into a trace of d samples (with d p) while preserving -hopefully-most of the information. Both the training and the attack phases are performed in this reduced feature space. The most common feature extraction techniques include the Principal Component Analysis (PCA) and Linear Discriminant analysis (LDA).

Algorithm 1 :Fig. 2 :

 12 Fig. 2: Example of the different bit recovery algorithms proposed

Fig. 4 :

 4 Fig. 4: Power and EM field measured during the execution of 3 instructions.

Fig. 5 :

 5 Fig. 5: Experimental setup With these settings, the 4 clock cycles of an instruction last for 200 ns and represents 2000 samples of the oscilloscope. A typical trace may span over several milliseconds and is made of thousands of instructions. To avoid synchronization issues, the clock of the PIC is generated by a signal generator (FI5350GA) which is also connected to the reference clock of the DSO. This setup ensures that the PIC and the DSO stay synchronized and that no post processing is required to divide a trace into individual instructions.

Fig. 6 :

 6 Fig. 6: Single bit T-Tests results at different positions

Fig. 8 :

 8 Fig. 8: EM traces grouped according to transition of bit 0 5 Evaluation This section presents the results of our bit-level SCBD. The training and evaluation phases use two different sets made of 2000 random valid instructions. Each acquisition is averaged 1000 times to improve the SNR. The results were also confirmed on simple programs written in C. The disassembler first a PoI extraction of k = 50 points that maximize the MD, then applies a LDA to the results and keeps 2 components. Then, the fourteen QDA-based classifiers, one for each bit of I, are applied to recover the 1999 bit transitions among the 3 transition classes T introduced in section 3.2. Finally, the algorithms described in section 3.3 are applied to recover the 1999 corresponding bit values.

Fig. 9 :

 9 Fig. 9: Cartography of the SR of the bit-level classifiers

Fig. 10 :

 10 Fig. 10: Evolution of the success rate by adding new positions

Fig. 11 :

 11 Fig. 11: Leakage cartography for two different devices (same scale as Figure 9)

  FindBitsLeft 100 94.1 99.2 83.1 97.0 90.7 93.5 97.4 71.8 78.6 75.9 72.8 88.7 92.0 FindBitsL+R 100 94.8 99.5 85.7 98.2 93.1 94.6 97.9 74.5 80.6 78.7 74.2 90.9 93.5

	Bit	0	1	2	3	4	5	6	7	8	9	10 11 12 13
		Table

Acknowledgments

The authors would like to thanks the reviewers for their helpful comments. This work was funded thanks to the French national program "Programme d'Investissement d'Avenir IRT Nanoelec" ANR-10-AIRT-05.