Djamel Eddine Amir
email: djamel-eddine.amir@loria.fr

Mathieu Hoyrup
email: mathieu.hoyrup@inria.fr

Comparing computability in two topologies

Computable analysis provides ways of representing points in a topological space, and therefore of defining a notion of computable points of the space. In this article, we investigate when two topologies on the same space induce different sets of computable points.

We first study a purely topological version of the problem, which is to understand when two topologies are not σ-homeomorphic. We obtain a characterization leading to an effective version, and we prove that two topologies satisfying this condition induce different sets of computable points. Along the way, we propose an effective version of the Baire category theorem which captures the construction technique, and enables one to build points satisfying properties that are co-meager w.r.t. a topology, and are computable w.r.t. another topology. Finally, we generalize the result to three topologies and give an application to prove that certain sets do not have computable type, i.e. have a homeomorphic copy that is semicomputable but not computable.

Introduction

Computable analysis provides a way to perform computations on mathematical objects, by representing them using infinite sequences of bits or natural numbers. A class of objects can be represented in several ways, and the choice of the representation has a direct impact on the computation power of the Turing machine. In particular, each representation induces its own class of computable objects. In this article, we are interested in understanding when two representations on a set induce different subsets of computable points. This problem being too general to be analyzed, we restrict our attention to standard representations of countably-based topological spaces. It is a widespread class of representations capturing most natural cases, and it enables us to develop a topological understanding of the problem.

With this restriction, the problem can be stated as follows: given two countably-based topologies on the same set, when do they induce different sets of computable points?

Our main goals are to clarify the relationship between topology and computability, and to obtain general results that can be applied in concrete cases to separate computability notions. Indeed, such separation results can be challenging in practice, which means that a theoretical development of this problem is needed. Moreover, understanding when a separation result is possible is at least more informative as the separation result itself. We give an application which would be tedious to obtain directly, which is to build a copy of a given compact set which is semicomputable but not computable.

In order to study the problem of separating the notions of computable points associated to two topologies, we first relativize it, which yields a purely topological problem: whether two topologies are σ-homeomorphic, i.e., whether the space can be decomposed as a countable union of subsets such that the two topologies agree on each subset. The relationship between the computability-theoretic content of points and the σ-homeomorphism class of the space was thoroughly investigated by Kihara, Pauly and Ng [START_REF] Kihara | Point degree spectra of represented spaces[END_REF][START_REF] Kihara | Enumeration degrees and non-metrizable topology[END_REF].

In this article, we use Baire category to study the problem of comparing two topologies and their computable contents, so we need one of the two topologies to be Polish, or that the space can also be endowed with a third topology which is Polish.

Given a set with a Polish topology τ and a weaker topology τ , we give a characterization of the case when τ and τ are not σ-homeomorphic. We then use this characterization to propose an effective version, implying that the two topologies induce different sets of computable points. We also extend the results to the case when τ is not Polish, but a third Polish topology is available.

The constructions underlying the separation results are based on the priority method with finite injury. We recast the construction into a more general result of independent interest. It is an effective version of the Baire category theorem, in which simple topological conditions are identified that make the construction possible.

Content

Let (X, τ ) be a Polish space and τ a countably-based topology on X that is weaker than τ , i.e. such that every τ -open set is also τ -open. For the effective results, we will also assume that these topologies are effective in some sense.

In Section 2, we start with an effective version of the Baire category theorem that builds τ -computable points in a set that is co-meager w.r.t. τ (Theorem 2.2). This result captures the building technique that is needed for the rest of the paper, and is based on the priority method. This theorem is of independent interest and can hopefully be applied in other contexts.

In Section 3 we introduce a definition expressing that τ is "significantly weaker" than τ in the sense that when τ and τ coincide on a set, that set must be small in the sense of Baire category. We then say that τ is generically weaker than τ (Definition 3.3). This notion immediately implies that τ is not σ-homeomorphic to τ . Using a result by Solecki and Pawlikowski-Sabok, we then show that this apparently stronger notion is actually the general case, up to restricting to some subspace: τ is not σ-homeomophic to τ if and only if there exists a Polish subspace (Y, τ Y ) of (X, τ ) on which the subspace topology τ Y is generically weaker than the subspace topology τ Y (Theorem 3.3). We then prove that when τ is generically weaker than τ in an effective way, there exist τ -computable points that are not τ -computable (Theorem 3.1). This construction is obtained by applying the effective Baire category theorem from Section 2.

In Section 4 we generalize the results to a case when the two topologies to be compared are not Polish, but a third topology is available, which is Polish.

We end in Section 5 with an application, which is a complete proof of a result announced in [START_REF] Djamel | Computability of finite simplicial complexes[END_REF] about the notion of computable type (Theorem 5.2).

Background

We assume familiarity with basic notions from computability theory: computably enumerable (c.e.) subset of N, computable function from N to N or from the Baire space N = N N to itself. We now recall a few classical notions from computable analysis, that can be found in [START_REF] Weihrauch | Computable Analysis[END_REF] or [START_REF] Schröder | Admissibly represented spaces and Qcbspaces[END_REF].

An effective countably-based space is a topological space (X, τ ) coming with a numbered basis (B i ) i∈N and a c.e. set E ⊆ N 3 such that

B i ∩B j = (i,j,k)∈E B k . A set U ⊆ X is an effective open set if U = σ∈W B i for some c.e. set W ⊆ N.
The Baire space N = N N endowed with the product of the discrete topology is naturally an effective countable-based T 0 -space. Basic open sets are given by the cylinders: if σ ∈ N * is any finite sequence of natural numbers, then the cylinder [σ] is the set of infinite extensions of σ.

A representation of a set X is a surjective partial map δ

X :⊆ N → X. A δ X -name of x ∈ X is any p ∈ dom(δ X ) such that δ X (p) = x. A point x ∈ X is computable if it has a computable name. A function f : X → Y between represented spaces is computable if there exists a computable partial function F :⊆ N → N such that f • δ X = δ Y • F . F is called a realizer of f .
An effective countably-based T 0 -space X can be equipped with its standard representation δ X encoding a point by any enumeration its basic neighborhoods, and defined as follows: a δ X -name of x is any p ∈ N such that for all i ∈ N, x ∈ B i ⇐⇒ ∃n ∈ N, p(n) = i + 1. We will say that a point x ∈ X is τ -computable if x is computable w.r.t. the standard representation associated with the topology τ . A function f : X → Y between effective countable-based T 0 -spaces is computable if and only if the preimages of basic open sets f -1 (B Y i ) are effectively open, uniformly in i.

A computable metric space is a metric space (X, d) coming with a dense sequence (s i ) i∈N such that the function (i, j) → d(s i , s j ) is computable. It is an effective countably-based space, by taking the basis of metric balls B(s i , r) for positive rational r.

A computable Polish space is a computable metric space whose metric is complete. For every computable Polish space, there exists a computable surjective function f : N → X which is effectively open, i.e. such that the images of cylinders f ([σ]) are effectively open, uniformly in σ (see [START_REF] Selivanov | Towards the effective descriptive set theory[END_REF] for instance).

On a set X endowed with two effective countably-based topologies τ 1 , τ 2 , we sau that τ 1 is effectively weaker than τ 2 if the basic τ 1 -open sets are effective τ 2 -open sets, uniformly.

A computable Baire category theorem

In this section, we prove an effective version of the Baire category theorem. In a computable Polish space, it allows to build points in a co-meager set, that are computable w.r.t. another topology. It will be applied in the next sections to build points with specific properties.

The Baire category theorem is known to help proving existence results. First, it has many classical applications in mathematics, some of which can be found in the survey [START_REF] Hawtrey | Applications of the Baire category theorem[END_REF] by Jones. Computable versions of the Baire category theorem have been developed. The simplest one allows to build computable points, and was studied by Yasugi, Mori and Tusjii [START_REF] Yasugi | Effective properties of sets and functions in metric spaces with computability structure[END_REF], Brattka [START_REF] Brattka | Computable versions of Baire's category theorem[END_REF], Brattka, Hendtlass and Kreutzer [START_REF] Brattka | On the uniform computational content of the Baire category theorem[END_REF], Kalantari [START_REF] Kalantari | Density & Baire category in recursive topology[END_REF]. Jockush [START_REF] Carl | Degrees of generic sets[END_REF] introduced 1-genericity as an effective version of Baire category that enables one to build 0 -computable points. A notion of genericity that enables one to build points that are computable w.r.t. a given topology was proposed by Hoyrup in [START_REF] Hoyrup | Genericity of weakly computable objects[END_REF]. A complexitytheoretic version of Baire category was introduced by Breutzmann, Juedes and Lutz [START_REF] Breutzmann | Baire category and nowhere differentiability for feasible real functions[END_REF] in order to build polynomial-time computable points.

We work in a computable Polish space (X, τ ), coming with an effectively weaker countably-based topology τ . We identify a condition for a sequence of subsets A n of X which imply the existence of a τ -computable point in n A n .

We first prove the result on the Baire space and then easily extend it to arbitrary computable Polish spaces. We work on the Baire space first for two reasons: it is simpler to work in a concrete space, and we need to decide whether a point belongs to a basic open set, which is only possible if the basic open sets are clopen, i.e. if the space is zero-dimensional.

On the Baire space

The Baire space is endowed with its usual Polish topology τ . We assume a countably-based topology τ that is effectively weaker than τ : its numbered basis (V i ) i∈N consists of uniformly effective τ -open sets. When topological notions are expressed with no reference to τ or τ , they are implicitly understood w.r.t. τ (for instance, interior, density, etc.).

We identify a condition on a sequence of subsets A n of the Baire space implying the existence of a τ -computable point in n A n .

Let O τ (N ) be the set of effective τ -open subsets of N .

Definition 2.1. A density function for a set A ⊆ N is a function ∆ :

N * → O τ (N ) such that for all finite sequences σ ∈ N * , ∆(σ) is a non-empty subset of [σ] ∩ A.
A set A has a density function if and only if its interior is dense in N . The simplest computable version of the Baire category theorem, as in [START_REF] Yasugi | Effective properties of sets and functions in metric spaces with computability structure[END_REF] or [START_REF] Brattka | Computable versions of Baire's category theorem[END_REF], is that if sets A n have uniformly computable density functions, then n A n contains a τ -computable point. However, having computable density functions is too strong for our purposes: typically, we want to build points that are not τ -computable, but τ -computable. Therefore, the sets we will deal with usually have no computable density functions.

We introduce the following notion: A is effectively dense if it has a density function which is computable with finitely many mind-changes, with some restriction on the way the algorithm can change its mind; the topology τ is only involved in that restriction. Definition 2.2. A set A ⊆ N is effectively dense w.r.t. (τ, τ ) if there exists a computable sequence of functions ∆[s] : N * → O τ (N ), with s ∈ N, satisfying:

1. Each ∆[s](σ) is a non-empty subset of [σ], 2. The functions ∆[s] converge to a density function ∆: for each σ, if s is sufficiently large then ∆[s](σ) = ∆(σ) ⊆ [σ] ∩ A, 3. Each ∆[s](σ) is contained in the τ -closure of ∆[s + 1](σ).
The programs behind the computable functions actually output indices of effective open sets, and for each σ the sequence of indices is eventually constant as s grows. One should think of ∆[s](σ) as a guess, at stage s, for a subset of [σ] ∩ A, which may be updated at a later stage if we obtain more information about A and discover that it is a wrong guess. In particular, ∆[s](σ) may not be contained in A for the first values of s.

What makes this notion more specific than finite mind-change computability is condition 3., which says that when there is a mind-change from ∆[s](σ) to ∆[s + 1](σ), the τ -closures of the corresponding sets can only grow.

The main result of this section states that a τ -computable point satisfying countably many properties can be built, if these properties are effectively dense w.r.t. (τ, τ ). The proof implicitly used the priority method with finite injury.

Theorem 2.1 (An effective Baire category theorem). Let A n ⊆ N be effectively dense sets w.r.t. (τ, τ ), uniformly in n. Their intersection n A n contains a τ -computable point.

Uniformity means that each A n comes with functions ∆ n [s](σ) witnessing its effective density, and that ∆ n [s](σ) is a computable function of n, s, σ.

Proof. Let ∆ n [s](σ) be uniformly computable functions witnessing the effective density of A n . We can assume w.l.o.g. that the strings defining the open sets ∆ n [s](σ) are proper extensions of σ, which can be achieved by appending a 0 at the end of each string if needed. We recall that the basic τ -open sets V i are uniformly effective τ -open sets. Let V i [s] be the finite union of cylinders obtained at stage s in the computable enumeration of V i .

The τ -computable point x will be defined as a limit x = lim s lim n σ n [s] of a computable double-sequence of finite strings σ n [s]. We will build this double-sequence with the following properties:

(i) The string σ n+1 [s] extends some string defining ∆ n [s](σ n [s]). Therefore, σ n+1 [s] properly extends σ n [s] and these strings converge to some

x[s] = lim n σ n [s], (ii) For each n, if s is sufficiently large then σ n [s] is constant and [σ n [s]] ⊆ A n , so x[s] converge to some x ∈ n A n , (iii) For i ≤ r ≤ s, if x[r] ∈ V i [r], then x[s] ∈ V i and x ∈ V i . Claim 1. Condition (iii) implies that x is τ -computable.
Proof of the claim. It implies that for each i, one has

x ∈ V i ⇐⇒ ∃s ≥ i such that x[s] ∈ V i [s]. (1)
The backward direction is immediate, using r = s. The forward direction is also easy:

if x ∈ V i then x ∈ V i [r] for some r ≥ i, so x[s] ∈ V i [r] for some s ≥ r as x[s] converges to x and V i [r] is open. As V i [r] ⊆ V i [s], one has x[s] ∈ V i [s] and moreover s ≥ r ≥ i.
As the right hand-side of (1) is c.e., the set {i

: x ∈ V i } is c.e. so x is τ -computable.
Therefore, conditions (i), (ii) and (iii) imply the result. It might be helpful to have in mind that in addition to condition (i), for each s, σ n+1 [s] will be exactly one of the strings defining ∆ n [s](σ n [s]) for almost all n.

We now build the double-sequence σ n [s], by induction on s. We first consider the case s = 0: let σ 0 [0] be the empty string, and inductively let σ n+1 [0] be the first (or any) string defining

∆ n [0](σ n [0]).
Let s ∈ N and assume that σ n [r] has been defined for all r ≤ s and all n and satisfy conditions (i) and (iii). Start with n = 0, and as long as

∆ n [s + 1](σ n [s]) = ∆ n [s](σ n [s]), define σ n [s + 1] = σ n [s] and increment n.
If equality holds for all n, then we are done, otherwise let n be minimal such that

∆ n [s + 1](σ n [s]) = ∆ n [s](σ n [s]). We now define σ n [s + 1]. To lighten the notations, let C = ∆ n [s](σ n [s]) and D = ∆ n [s + 1](σ n [s]).
By assumption, C is contained in the τ -closure of D. Let V be the finite intersection of the V i 's such that there exists r satisfying i ≤ r ≤ s and x

[r] ∈ V i [r]. It is a τ -open set. Claim 2. V intersects C. Proof of the claim. Both V and C contain x[s]. Indeed, if i ≤ r ≤ s and x[r] ∈ V i [r], then x[s] ∈ V i by induction hypothesis (iii), so x[s] ∈ V . Moreover, x[s] extends σ n+1 [s] which extends a string defining ∆ n [s](σ n [s]) = C by (i), so x[s] ∈ C. As C is contained in the τ -closure of D, V must intersect D. As a result, one can effectively find a string σ such that [σ] ⊆ D ∩ V . We then define σ n [s + 1] = σ, and inductively for m ≥ n, σ m+1 [s + 1] is the first string defining ∆ m [s + 1](σ m [s + 1]).

Conditions (i) and (iii) are satisfied by construction. Condition (ii) holds by induction on

n: if σ n [s] is constant for sufficiently large s, then so is ∆ n [s](σ n [s]) is because ∆ n [s] converges to ∆ n , so σ n+1 [s + 1] = σ n+1 [s]
for sufficiently large s. As a result, σ n+1 [s] is eventually constant when s grows.

Extension to computable Polish spaces

The result easily extends to any computable Polish space (X, τ ). Again, let τ be an additional countably-based topology on X which is effectively weaker than τ , i.e. which has a basis (V i ) i∈N consisting of uniformly effective τ -open sets.

First, the definition of an effectively dense set extends as follows.

Definition 2.3. A set A ⊆ X is effectively dense w.r.t. (τ, τ ) if there is a computable procedure that given a non-empty basic τ -open set B, outputs a sequence of non-empty effective τ -open sets U s ⊆ B satisfying:

• U s is eventually constant, with limit U ∞ ⊆ B ∩ A, • U s is contained in cl τ (U s+1 ).
The procedure actually outputs indices of effective open sets, and the sequence of indices is eventually constant.

Example 2.1. Here is the simplest example of an effectively dense set. If A ⊆ X is an effective τ -open set that is dense w.r.t. τ , then A is effectively dense w.r.t. (τ, τ ), whatever τ is. Indeed, given B, one can directly compute U = B ∩ A with no mind-change. In other words, we define U s = U ∞ = B ∩ A for all s.

Theorem 2.1 can then be extended to any computable Polish space.

Theorem 2.2 (An effective Baire category theorem). Let (X, τ ) be a computable Polish space and τ a countably-based topology that is effectively weaker than τ . If A n ⊆ X are uniformly effectively dense w.r.t. (τ, τ ), then n A n contains a τ -computable point.

Proof. As X is a computable Polish space, there exits a computable effectively open surjective map f : N → X (see [START_REF] Selivanov | Towards the effective descriptive set theory[END_REF] for instance). Using f , we can work in the Baire space, by considering the sets f -1 (A n ) and the topology τ f := f -1 (τ ). It suffices to show that these sets are effectively dense w.r.t. (τ N , τ f ), and that a point

x ∈ N is τ f -computable if and only if f (x) is τ -computable, so we can apply Theorem 2.1. First, we show how to compute ∆ n [s](σ) associated to f -1 (A n ). Given a finite string σ, compute a basic τ -open set B ⊆ f ([σ]), then compute U s and let ∆[s](σ) = [σ] ∩ f -1 (U s ). The function ∆ n [s](σ) easily satisfies conditions 1. and 2. in Definition 2.2. We check condition 3. If V ∈ τ is such that f -1 (V ) intersects [σ]∩f -1 (U s ), then V intersects U s . As U s is contained in the τ -closure of U s+1 , V intersects U s+1 . As U s+1 ⊆ B ⊆ f ([σ]), f -1 (V ) intersects [σ] ∩ f -1 (U s+1 ). Therefore, ∆[s](σ) = [σ] ∩ f -1 (U s ) is contained in the τ f -closure of ∆[s + 1](σ) = [σ] ∩ f -1 (U s+1 ).
Finally, the basic τ f -neighborhoods of x ∈ N are precisely the preimages of the basic τ -neighborhoods of f (x), so

x is τ f -computable iff f (x) is τ - computable.
In the sequel, we will see applications of this technique. As the classical Baire category theorem, Theorem 2.2 is very modular: if one can build a τ -computable point satisfying properties A n and a τcomputable point satisfying properties B n , both using Theorem 2.2, then one can build a τ -computable point satisfying A n and B n at the same time. We state a direct consequence which is particularly useful in practice. Say that P ⊆ X is a Π 0 2 (τ )-set if P is the intersection of a sequence of uniformly effective τ -open sets. Under the same assumptions as Theorem 2.2, we obtain:

Corollary 2.1. Let A n ⊆ X be uniformly effective dense w.r.t. (τ, τ ) and P ⊆ X be a Π 0 2 (τ )-set that is dense w.r.t. τ . The set P ∩ n A n contains a τ -computable point.

Proof. The set P can be written as n P n where P n are uniformly effective τopen sets that are dense w.r.t. τ . The sets P n are uniformly effectively dense w.r.t. (τ, τ ) as explained in Example 2.1. Therefore, one can apply Theorem 2.2 to the sets A n and P n .

Generically weaker topology

We now come to the main topic of this article. Let X be a set endowed with two countably-based topologies τ, τ where τ is weaker than τ . We want to understand when it is the case that every τ -computable point is τcomputable.

We first study a relativized version of this problem, which is whether id : (X, τ ) → (X, τ ) is σ-continuous, i.e., whether X can be decomposed as a countable union X = n∈N X n such that the restriction of id to each X n is continuous w.r.t. the corresponding subspace topologies.

Formal relationship between these two problems can be obtained, topological conditions being equivalent to suitable relatizations of computabilitytheoretic conditions (more details can be found in [START_REF] Kihara | Point degree spectra of represented spaces[END_REF][START_REF] Kihara | Enumeration degrees and non-metrizable topology[END_REF]). Let us just give more informal connections:

1. If id : (X, τ ) → (X, τ ) is σ-continuous, then there exists an oracle A such that id is σ-computable relative to A. In the effective case when id is σ-computable, every τ -computable point is τ -computable.

2. If id : (X, τ ) → (X, τ ) is not σ-continuous, then there exists a point x whose τ -names cannot be computed from its τ -names. We are looking for an effective version where such an x can be effectively built, i.e., where x is τ -computable but not τ -computable.

We now give a characterization, when τ is Polish, of the cases when id : (X, τ ) → (X, τ ) is not σ-continuous. We first give a sufficient condition, we show that it is also necessary, up to restricting to some subspace, and we study its effective version.

Definition

Let (X, τ ) be a Polish space and τ be a countably-based topology on X, which is weaker than τ (i.e., τ ⊆ τ ). A common reason preventing id : (X, τ ) → (X, τ ) to be σ-continuous is that any set C ⊆ X on which id is continuous is meager w.r.t. τ : it implies that X cannot be decomposed as a countable union of such sets, because (X, τ ) is a Polish space so it is not a countable union of meager sets by the Baire category theorem. We will see that this sufficient condition, which seems stronger at first, is actually necessary, up to restricting to some subspace (Theorem 3.3).

If C is a subset of X, then a topology on X induces a topology on C, obtained by intersecting the open sets with C. We say that τ and τ agree on C if they induce the same topology on C, which is the same as saying that the restriction of id : (X, τ ) → (X, τ ) to C is continuous. Definition 3.1. We say that τ is generically weaker than τ if every C ⊆ X on which τ and τ agree is meager in (X, τ ).

As discussed above, if τ is generically weaker than τ then id : (X, τ ) → (X, τ ) is not σ-continuous so there exists x ∈ X such that no Turing machine translates its τ -names into τ -names. In Section 3.4 we will be interested in building such x effectively to make it τ -computable.

That τ is generically weaker than τ is a sufficient condition to make id : (X, τ ) → (X, τ ) not σ-continuous. It is not a necessary condition, because the discontinuity of id may happen only in a small set. In Section 3.6 we show that it is almost necessary: if id : (X, τ ) → (X, τ ) is not σ-continuous, then it is possible to restrict to a subset on which τ is generically weaker than τ . It is a consequence of a result by Solecki [START_REF] Solecki | Decomposing Borel sets and functions and the structure of Baire class 1 functions[END_REF], Pawlikowski and Sabok [START_REF] Pawlikowski | Decomposing Borel functions and structure at finite levels of the Baire hierarchy[END_REF].

We now investigate our notion of generically weaker topology.

Characterization

Checking that τ is generically weaker than τ may be difficult, using the raw definition. We give a characterization that is easier to check in practice, and which will lead to an effective version.

The following notions witness that some τ -open sets are far from being τopen. 1. In the subspace B with the topology inherited from τ , U has empty interior,

Every τ -open set intersecting B already intersects

B \ U , 3. B \ U is τ -dense in B, 4. U is contained in the τ -closure of B \ U .
The following algorithmic intuition is helpful: if U is a B-witness, then for any point x ∈ U , it is not possible to know in finite time that x belongs to U if we are given a name of x in the topology τ , even with the extra information that x ∈ B.

It is also helpful to have a formulation in terms of converging sequences, illustrated in Figure 1. We now state and prove the main result of this section, which is a characterization of generically weaker topologies.

Proposition 3.2 (A characterization of generically weaker topologies).

Let (X, τ ) be a Polish space and τ be a weaker countably-based topology on X.

τ is generically weaker than τ if and only if every non-empty τ -open set B has a B-witness.

This result usually makes it very easy to check that τ is generically weaker than τ . In practice, one should start showing the existence of an Xwitness, and then adapting the proof to any subspace B ∈ τ in order to obtain a B-witness. Moreover, this characterization will naturally lead to an effective version (Definition 3.3).

Proof. Assume that some non-empty B ∈ τ has no B-witness. We first show that for every non-empty τ -open set U ⊆ B, there exists V ∈ τ such that B ∩ cl τ (V ) = B ∩ cl τ (U ). We express U as the union of all the τ -basic open sets U i ⊆ U . Each U i is not a B-witness, so there exists

V i ∈ τ such that ∅ = B∩V i ⊆ U i . Let V = i V i . One has B∩V ⊆ U , and B∩U ⊆ cl τ (V ) as V intersects each B ∩ U i . As a result, B ∩ cl τ (V ) = B ∩ cl τ (U ).
Let (U n ) n∈N be an enumeration of the basic τ -open sets contained in B and let

(V n ) n∈N be τ -open sets such that B ∩cl τ (V n ) = B ∩cl τ (U n ). Let C = n (U n V n ) c
. By definition of C, τ and τ agree on C, because U n ∩ C = V n ∩ C for all n. We show that C is τ -co-meager in B. It is sufficient to show that each U n V n is nowhere τ -dense in B, and indeed

B ∩ cl τ (U n V n ) = B ∩ (cl τ (U n \ V n ) ∪ cl τ (V n \ U n )) ⊆ B ∩ (cl τ (U n ) \ V n ∪ cl τ (V n ) \ U n ) = B ∩ (cl τ (V n ) \ V n ∪ cl τ (U n ) \ U n ) = B ∩ (∂ τ V n ∪ ∂ τ U n ).
The sets ∂ τ V n and ∂ τ U n are τ -boundaries of τ -open sets, so they are nowhere τdense. Therefore, τ is not generically weaker than τ .

Conversely, assume that each non-empty B ∈ τ has a B-witness. Let C ⊆ X be such that τ and τ agree on C, and let us show that C is nowhere dense. Given a non-empty τ -open set B, we need to find a non-empty τ -open set W ⊆ B disjoint from C. Let U be a B-witness and B be a non-

empty τ - open set such that cl τ (B ) ⊆ U . If B is disjoint from C then take W = B . If B intersects C, then let V ∈ τ be such that B ∩C = V ∩C. V intersects U so V intersects B \ U hence B \ cl τ (B ). Therefore W = V ∩ B \ cl τ (B ) is non-empty and disjoint from C.
We finally observe that in Definition 3.1, one can replace the condition of being "meager" by the apparently stronger condition of being "nowhere dense", giving the same notion.

Proposition 3.3 (Meager versus nowhere dense). Let (X, τ ) be a Polish space and τ be a countably-based topology on X that is generically weaker than τ .

If τ and τ agree on a set C ⊆ X, then C is nowhere dense.

Proof. The idea is that we can always assume that C is a G δ -set w.r.t. τ , and that a G δ -set is meager if and only if it is nowhere dense. More precisely, if τ and τ agree on C, then let (U n ) n∈N be a basis of τ and let

V n be τ -open sets such that U n ∩ C = V n ∩ C for each n. The set C = n (U n V n ) c is a G δ -set w.r.t. τ containing C, and τ agrees with τ on C because U n ∩ C = V n ∩ C for each n.
As τ is generically weaker than τ , it implies that C is meager. As C is a G δ -set, it is nowhere dense. As C ⊆ C , C is nowhere dense as well.

Examples

We give several examples of generically weaker topologies. They also illustrate how Proposition 3.2 makes it easy to show that a topology is generically weaker than another one.

Example 3.1 (Cantor vs Scott). Let (X, τ ) be the Cantor space with the Cantor topology generated by the cylinders, and τ be the Scott topology generated by the sets {x ∈ X : x n = 1}, where n ∈ N and x n is the bit of x at position n. It is easy to see that τ is generically weaker than τ .

First, the cylinder [0] contains no non-empty Scott open set so it is an Xwitness. More generally, for any cylinder [u], the cylinder [u0] contains no Scott open set intersected with [u], so [u0] is a [u]-witness.

When the topologies are induced by norms on a vector space, if a topology is strictly weaker then it is generically weaker, and there is no intermediate case. This phenomenon is at the core of Pour-El and Richards first main theorem [START_REF] Pour-El | Computability in Analysis and Physics[END_REF].

Proposition 3.4. Let X be a Banach space with a norm . 1 . Let . 2 be a strictly weaker norm on X. The topology induced by . 2 is generically weaker than the topology induced by . 1 .

Proof. Let (x n ) n∈N be a sequence satisfying x n 1 = 1 and x n 2 → 0. The ball B 1 (x, r/3) is a B 1 (x, r)-witness because any y ∈ B 1 (x, r/3) is the limit in the . 2 norm of y + (2r/3)x n ∈ B 1 (x, r) \ B 1 (x, r/3).

Example 3.2 (Uniform norm versus L 1 norm). Let (C[0, 1], τ ∞ ) be the Polish space of continuous real-valued functions with the topology of the uniform norm, and τ 1 be the topology of the L 1 norm. As τ 1 is strictly weaker than τ ∞ , τ 1 is generically weaker than τ ∞ by Proposition 3.4.

Example 3.3 (A non-example). Let (X, τ ) be the space of real numbers with the Euclidean topology, let f (x) = x 2 and τ the initial topology of f , consisting of the open subsets of R that are symmetric around 0. Although τ is strictly weaker than τ , τ is not generically weaker than τ .

Indeed, there is no (0, +∞)-witness, because on (0, +∞), τ and τ induce the same topology. Note that there exists an X-witness: the open interval (1, 2) contains no non-empty τ -open set.

Effective version

As previously discussed, if τ -generically weaker than τ then id : (X, τ ) → (X, τ ) is not σ-continuous. In particular, there exists x ∈ X whose τ -names cannot be computed from τ -names.

We now want to effectively build such an x, i.e. we want to build a τcomputable point that is not τ -computable. To achieve this, we need an effective version of the notion of generically weaker topology, which we formulate using the characterization given by Proposition 3.2. Definition 3.3. Say that τ is effectively generically weaker than τ if there is a computable function sending each basic τ -open set B to a Bwitness U B .

Note that U B can be assumed to be a basic τ -open set (because a nonempty subset of a B-witness is also a B-witness), and the computation takes an index of B as input and outputs an index of U B .

We expect that in any concrete case, the proof that τ is generically weaker than τ gives explicit witnesses and actually shows that τ is effectively generically weaker than τ . All the examples given in the previous section are effective. The following example is particularly interesting. Example 3.4 (Norms). Proposition 3.4 is effective: if . 1 and . 2 are computable norms over a computable vector space (defined by Pour-El Richards in [PER89]), and . 2 is strictly weaker than . 1 , then . 2 is effectively generically weaker than . 1 because witnesses are straightforward to compute.

We now state the main result of this section, giving relatively simple conditions implying that τ and τ do not induce the same computable points. Our effective Baire category theorem (Theorem 2.2) makes the proof very easy: we essentially have to give the strategy to defeat one Turing machine attempting to τ -compute x, and the effective Baire category theorem takes charge of the intertwinning between the strategies. Theorem 3.1. Let (X, τ ) be a computable Polish space and τ an effectively weaker countably-based topology. If τ is effectively generically weaker than τ then there exists a τ -computable point that is not τ -computable. Moreover, such a point can be found in any dense Π 0 2 (τ )-set. Proof. We apply our effective Baire category theorem (Theorem 2.2). Let A n be the set of points x whose τ -neighborhood basis is not indexed by W n , the nth c.e. subset of N. We show that A n is effectively dense w.r.t. (τ, τ ) (Definition 2.3), uniformly in n.

First, we can assume that for each basic τ -open set B, the B-witness U B satisfies: U B is contained in the τ -closure of B \ cl τ (U B ). Indeed, it can be achieved by replacing U B , which is a metric ball B(s, r) by the ball B(s, r/2).

Let us now show that A n is effectively dense w.r.t. (τ, τ ). Given a basic τ -open ball B, we output U B as long as the index of U B does not appear in W n , and then switch to B \ cl τ (U B ) if it appears. More precisely, let

U s = U B if W n [s] does not contain the index of U B , B \ cl τ (U B ) otherwise.
We check the three conditions in Definition 2.3. First, U s ⊆ B by definition. Condition 1: there is at most one mind-change, if the index of U B appears in W n at stage s. Condition 2: the limit set is U ∞ = B \ cl τ (U B ) if the index of U B belongs to W n , and U B if it does not. In any case, W n is not the set of basic τ -neighborhoods of any point in

U ∞ , so U ∞ is contained in A n . Condition 3: U B is contained in the τ -closure of B \ cl τ (U B ), so U s is always contained in the τ -closure of U s+1 .
We can apply Theorem 2.2, which produces a τ -computable point that belongs to n A n , i.e. that is not τ -computable.

Moreover, one can build such a point in n O n , where O n are dense uniformly effective open sets, because O n are uniformly effectively dense in the sense of Definition 2.3.

Example 3.5 (Norms). We continue with Proposition 3.4 and Example 3.4. Let . 1 and . 2 be complete computable norms over a computable vector space, in the sense of Pour-El Richards [START_REF] Pour-El | Computability in Analysis and Physics[END_REF]. If . 2 is strictly weaker than . 1 , then . 2 is effectively generically weaker than . 1 , so by Theorem 3.1 there exists a point x that is computable in the norm . 2 but not in the norm . 1 . It is a particular case of Pour-El Richards First Main Theorem [START_REF] Pour-El | Computability in Analysis and Physics[END_REF]. Pour-El and Richards' full result can actually be recovered by working in the Polish space formed by the graph of the linear operator, endowed with the product topology and with the topology on the first component. Details are explained in [START_REF] Hoyrup | Irreversible computable functions[END_REF].

Example 3.6 (Ergodic decomposition). This example is taken from [START_REF] Hoyrup | Irreversible computable functions[END_REF][START_REF] Hoyrup | Genericity of weakly computable objects[END_REF]. Theorem 3.4.1 in [START_REF] Hoyrup | Genericity of weakly computable objects[END_REF] states the existence of two non-computable shift-invariant ergodic measures µ 1 , µ 2 whose average µ 1 +µ 2 2 is computable. Theorem 3.1 can be applied to prove this result.

Let X be the space of pairs of shift-invariant measures. Let τ be the product of the weak* topology. Consider the average operator f : X → M(2 N ) sending (µ 1 , µ 2 ) to µ 1 +µ 2 2 , and let τ be the initial topology of f . Theorem 3.4.2 in [START_REF] Hoyrup | Genericity of weakly computable objects[END_REF] implies that τ is effectively generically weaker than τ , although it is not expressed in the same way. The idea is that if (µ 1 , µ 2 ) is a pair such that µ 1 = µ 2 , then for λ ∈ [0, 1], the pairs

((1 -λ)µ 1 + λµ 2 , (1 -λ)µ 2 + λµ 1 )
have the same τ -neighborhoods as (µ 1 , µ 2 ) and their proximity to (µ 1 , µ 2 ) in the topology τ can be freely controlled by the choice of λ.

In (X, τ ), the set of pairs of ergodic measures is a dense Π 0 2 -set. Therefore, Theorem 3.1 implies the existence of a pair (µ 1 , µ 2 ) of ergodic measures which is τ -computable but not τ -computable; in other words, µ 1 and µ 2 are not computable but their average is.

Weihrauch degree

If x is a point provided by Theorem 3.1, then τ -names of x contain strictly more information than τ -names of x. The proof of Theorem 3.1 can be adapted to show what type of non-computable information can be encoded in τ -names, that cannot be obtained from τ -names. Namely, computing τnames from τ -names is at least as hard as computing a limit, or equivalently the Turing jump.

Formally, we show that the problem of computing limits is Weihrauch reducible to the problem of converting τ -names into τ -names. Let us recall the appropriate definitions, more details can be found in [START_REF] Brattka | Weihrauch complexity in computable analysis[END_REF].

Definition 3.4. Let f : X → Y and g : Z → W be functions between represented spaces.

Say that f is Weihrauch reducible to g, written f ≤ W g, if there exist computable functions H, K :⊆ N → N such that for any realizer G :⊆ N → N of g, the function p → H(G(K(p)), p) is a realizer of f . Say that f is strongly Weihrauch reducible to g, written f ≤ W g, if there exist computable functions H, K :⊆ N → N such that for any realizer G :⊆ N → N of g, the function p → H(G(K(p))) is a realizer of f . Definition 3.5. The function lim sends a converging sequence of elements of the Baire space to its limit. Theorem 3.2 (Weihrauch reduction of lim is necessary). If τ is effectively generically weaker than τ , then lim is Weihrauch reducible to id : (X, τ ) → (X, τ ).

Proof idea. The function lim is strongly Weihrauch equivalent to the function im : N → 2 N sending p ∈ N to the set im(p) = {p(n) : n ∈ N}, so we show how to reduce im to id.

Let p ∈ N , be given as oracle. We apply the construction of the proof of Theorem 2.2. The sets A n are implicitly defined by their density functions approximations as follows: given B, let

U s = U B if n / ∈ {p(0), . . . , p(s)}, B \ cl τ (U B ) if n ∈ {p(0), . . . , p(s)}.
The construction builds a point x p that is τ -computable (relative to p). If one is given x p in the topology τ , together with p, then it is possible to inductively find for each n whether n ∈ im(p). The idea is that if we are given x p in the topology τ , then we can decide whether x p ∈ U B or x p ∈ B \ cl τ (U B ), from which we can deduce whether n ∈ im(p).

We do not know whether a strong Weihrauch reduction can be obtained. However, we will see in the next section that it is always possible to obtain a strong Weihrauch reduction, relative to some oracle.

Level of generality

We now show two results, based on theorems by Solecki and Pawlikowski-Sabok. The first one is that when id : (X, τ ) → (X, τ ) is not σ-continuous, τ is generically weaker than τ after restricting to a subspace. The second result is another relationship between the discontinuity of id and the difference between τ -computability and τ -computability, expressed in terms of Weihrauch reducibility. We gather these results into one statement.

Theorem 3.3. Let (X, τ ) be Polish, τ ⊆ τ be countably-based T 0 and let f = id : (X, τ ) → (X, τ ). The following conditions are equivalent:

1. f is not σ-continuous,
2. There exists Y ⊆ X such that τ Y is Polish and τ Y is generically weaker than τ Y , 3. lim is Weihrauch reducible to f relative to an oracle, 4. lim is strongly Weihrauch reducible to f relative to an oracle.

In that case (Y, τ Y ) is even homeomorphic to the Baire space N . The proof uses a strong result from Descriptive Set Theory, Pawlikowski-Sabok's theorem [START_REF] Pawlikowski | Decomposing Borel functions and structure at finite levels of the Baire hierarchy[END_REF]. This theorem says that every sufficiently definable map between metric spaces is either σ-continuous, or contains one particular function P , which is not σ-continuous. Let us state this result precisely.

A subset A of a Polish space X is analytic if it is the image of a continuous function f : N → X. A set A ⊆ X is bianalytic if both A and X \ A are analytic. A topological space is analytic if it embeds as an analytic subset of a Polish space. A function f : X → Y between analytic spaces is bianalytic if the preimage of every bianalytic set is bianalytic.

The Baire space N = N N is endowed with two different topologies, both obtained as the product topology of some topology on N. The first one is the usual topology obtained τ N from the discrete topology on N. The second one, τ N , is obtained by identifying N with {0} ∪ {2 -n : n ∈ N} ⊆ R, via 0 → 0 and n → 2 -n+1 for n ≥ 1. It makes (N , τ N ) homeomorphic to the Cantor space. Definition 3.6. Pawlikowski's function is defined as

P = id : (N , τ N ) → (N , τ N ).
Theorem 3.4 (Pawlikowski-Sabok [START_REF] Pawlikowski | Decomposing Borel functions and structure at finite levels of the Baire hierarchy[END_REF]). Let X, Y be analytic spaces and f : X → Y be bianalytic. Either f is σ-continuous or f contains P in the following sense: there exist two topological embeddings ϕ :

(N , τ N ) → X and ψ : (N , τ N ) → Y such that f • ϕ = ψ • P .
This result was first proved by Solecki for Baire class 1 functions in [START_REF] Solecki | Decomposing Borel sets and functions and the structure of Baire class 1 functions[END_REF], and then improved in this form by Pawlikowski and Sabok. It was observed by Carroy (personal communication) that this result has a direct consequence in terms of Weihrauch reducibility: if P embeds in f as in the statement, then P is strongly Weihrauch reducible to f relative to an oracle. We also mention an effective version of the result by Debs [START_REF] Debs | Effective decomposition of σ-continuous Borel functions[END_REF].

We use the result in our setting, showing at the same time that some version of the result holds when X is not metrizable but still countablybased.

We start by reducing countably-based spaces to metrizable spaces. It is possible because the standard representation of countably-based spaces has very good properties, already exploited in [START_REF] De | Σ 0 α -Admissible Representations (Extended Abstract)[END_REF][START_REF] De | Quasi-Polish spaces[END_REF][START_REF] Callard | Descriptive complexity on non-Polish spaces[END_REF], that allow to reduce DST on countably-based spaces to DST on subspaces of the Baire space. We give another manifestation of this phenomenon, which is proved using similar techniques. Lemma 3.1 (σ-computable vs σ-computable realizer). Let X, Y be (effective) countably-based T 0 -spaces with their standard representations. A function f : X → Y is σ-continuous (σ-computable) iff it has a σ-continuous (σ-computable) realizer.

Proof. We prove the effective version, the non-effective version being obtained by relativization to any oracle.

One implication is straightforward. Assume that f is σ-computable, i.e. X = n∈N X n and each f |Xn is computable. We can assume that the sets X n are pairwise disjoint, replacing

X n with X n \ (X 0 ∪ • • • ∪ X n-1 ) if needed. Each f |Xn has a computable realizer F n : δ -1 X (X n ) → N .
The combination of all F n 's is a σ-computable realizer of f . We now prove the other implication. Assume that f has a σ-computable realizer F : dom(δ X ) → N , with dom(δ X ) = n∈N A n and each F |An is open and that δ is total as τ is Polish. Assume that f is not σ-continuous. We apply Theorem 3.4 to g := f • δ : dom(δ ) → X, where X is endowed with the Polish topology τ . We need to check that dom(δ ) is analytic and g is bianalytic. As id : (X, τ ) → (X, τ ) is continuous, it has a continuous realizer I : N → dom(δ ), satisfying δ • I = δ. The set

R = {(p, q) ∈ N × N : δ (p) = δ(q)} = {(p, q) ∈ N × N : δ (p) = δ • I(q)} is a Π 0 2 -subset of N ×N
, therefore its first projection, which is exactly dom(δ ), is analytic.

Let A ⊆ (X, τ ) be bianalytic. Its preimage by g is

g -1 (A) = {p ∈ dom(δ ) : f • δ (p) ∈ A} = {p ∈ dom(δ ) : ∃q ∈ N , δ (
p) = δ(q) and δ(q) ∈ A} which is analytic. Applying the same argument to g -1 (X \ A), we obtain that g -1 (A) is bianalytic. Therefore g satisfies the assumptions of Theorem 3.4. Now, g is not σ-continuous. Indeed, g = f • δ has the same realizers as f . Applying Lemma 3.1 in one direction to f and in the other direction to g, we have: f is not σ-continuous, so it has no σ-continuous realizer as well as g, so g is not σ-continuous.

We can now apply Theorem 3.4 to g, which provides topological embeddings

ψ : (N , τ N ) → (X, τ ), ϕ : (N , τ N ) → (N , τ N ), satisfying g • ϕ = ψ • P , i.e. f • δ • ϕ = ψ • P .
As observed by Carroy (personal communication), it implies that P is strongly Weihrauch reducible to f relative to an oracle computing ϕ and ψ. We have proved condition 4., which also implies condition 3.

Let us prove condition 2. Both f and P are the identity functions, with different topologies on their input and ouput spaces. Therefore, the condition f • δ • ϕ = ψ • P can be rewritten as δ • ϕ = ψ. As a result, we have:

1. ψ : (N , τ N ) → (X, τ ) is a topological embedding, 2. ψ = δ • ϕ : (N , τ N ) → (X, τ ) is continuous.
Let Y = im(ψ) and τ N be the preimage of the topology τ Y by ψ. Both functions

ψ : (N , τ N ) → (Y, τ Y ), ψ : (N , τ N ) → (Y, τ Y )
are homeomorphisms. The first one comes from 1. above. The second one comes from the fact that ψ is a bijection, is continuous and open, so it is a homeomorphism.

We now need to prove that τ N is generically weaker than τ N , which will conclude the proof.

By 2., τ N is weaker than τ N which is generically weaker than τ N , so τ N is also generically weaker than τ N . As a result, τ Y is generically weaker than τ Y . Note that τ Y is Polish because (Y, τ Y ) is homeomorphic to (N , τ N ).

Although Theorem 3.3 shows that the topological versions of Weihrauch reducibility and strong Weihrauch reducibility are equivalent in this context, we do not know whether their computable versions are still equivalent. In particular, we do not know whether Theorem 3.2 can be improved to obtain a strong Weihrauch reduction.

Open question 1. Let (X, τ ) be an effective Polish space and τ be a countablybased T 0 -topology that is effectively weaker than τ . Are the following statements equivalent?

• lim is Weihrauch reducible to id : (X, τ ) → (X, τ ),

• lim is strongly Weihrauch reducible to id : (X, τ ) → (X, τ ).

Three topologies

The previous results have limitations. In this section, we propose a generalization that can be applied in other situations, which will be applied in the next section.

Let τ 1 , τ 2 be two topologies on a set X, where τ 1 is weaker than τ 2 . Our goal is again to build a point x that is τ 1 -computable but not τ 2 -computable. The previous results cannot be applied if for instance:

• The topology τ 2 is not Polish,

• Or the topology τ 2 is Polish, but the sets where τ 1 and τ 2 agree are not τ 2 -meager.

Proof. 1. ⇒ 2. Let B ∈ τ be non-empty. We assume that for every U ∈ τ 2 there exists V ∈ τ 1 such that B ∩ cl τ (U ) = B ∩ cl τ (V ), and show that τ 1 is not τ -generically weaker than τ 2 . Let (U n ) n∈N be an enumeration of the basic τ 2 -open sets, and let (V n ) n∈N be the corresponding

τ 1 -open sets. Let C = n (U n V n ) c
. By definition of C, each U n coincides with V n on C, so τ 1 and τ 2 agree on C. We show that

C is τ -dense in B. Each (U n V n ) c is a G δ -set
V ∈ τ 1 such that U ∩ C = V ∩ C. Let W = B ∩ U \ cl τ (V ) ∪ V \ cl τ (U ) .
W is disjoint from C, is contained in B and is non-empty: if it was empty, then B ∩ cl τ (U ) = B ∩ cl τ (V ) would hold.

2. ⇒ 3. Let B ∈ τ and let U ∈ τ 2 be such that there is no

V ∈ τ 1 satisfying B ∩ cl τ (U ) = B ∩ cl τ (V ). Let V be the largest τ 1 -open set such that B ∩ V ⊆ cl τ (U ). One has B ∩ cl τ (V ) ⊆ B ∩ cl τ (U ) so the inclusion is strict. Therefore, there exists a non-empty τ -open set B ⊆ B ∩ U that is disjoint from V . Take B = B \ cl τ (U ). As U ∈ τ 2 contains B and is disjoint from B , one has B ∩cl τ 2 (B ) = ∅. If a τ 1 -open set W intersects B , then W ∩ B cl τ (U ) so W intersects B \ cl τ (U ) = B . Therefore, B ⊆ cl τ 1 (B ). 3. ⇒ 2. Let B ∈ τ and let B , B ⊆ B satisfy B ∩ cl τ 2 (B ) = ∅ and B ⊆ cl τ 1 (B ). Define U = X \ cl τ 2 (B ). Assume for a contradiction that there exists V ∈ τ 1 such that B ∩ cl τ (U ) = B ∩ cl τ (V ). B is contained in B ∩ U ⊆ B ∩ cl τ (V ), so V intersects B . As B ⊆ cl τ 1 (B ), V intersects B . It implies that U intersects B , which contradicts the definition of U .

Effective version

We introduce an effective version of being generically τ -weaker, which will lead to Theorem 4.1. It is indeed an effective version, because the plain notion is obtained by relativization to an oracle.

An application

In this section, we give an application of Theorem 4.1 to give a clear and complete proof of a result that was stated in [START_REF] Djamel | Computability of finite simplicial complexes[END_REF], just with a proof idea. A complete proof appears in the unpublished preprint [START_REF] Djamel | Computability of finite simplicial complexes[END_REF] but is very technical and difficult to read. Our effective Baire category theorem enables us to give a simpler proof, as it captures most of the technicality of the construction.

Let us first introduce the relevant notions.

Background on computable type

A compact pair is a pair (X, A) where X is a compact Polish space and A ⊆ X is a compact subset. The Hilbert cube is the computable Polish space Q = [0, 1] N endowed with the metric

d Q (x, y) = i∈N 2 -i |x i -y i |.
If X is a compact space and f, g : X → Q are continuous functions, we define their distance d

X (f, g) = max x∈X d Q (f (x), g(x)). Definition 5.1. A compact set X ⊆ Q is semicomputable if the set Q\X is an effective open set. A compact set X ⊆ Q is computable if it is
semicomputable and contains a dense computable sequence.

A compact pair (X, A) has computable type if for every pair (Y, B) in Q that is homeomorphic to (X, A), if Y and B are semicomputable then Y is computable.

A compact space X has computable type if the pair (X, ∅) has computable type.

Miller [START_REF] Miller | Effectiveness for embedded spheres and balls[END_REF] proved that each sphere S n and each pair (B n+1 , S n ) have computable type. Iljazović and Sušić [START_REF] Iljazović | Semicomputable manifolds in computable topological spaces[END_REF] proved that for each compact manifold M and each compact manifold with boundary (M, ∂M ) have computable type.

In [START_REF] Djamel | Computability of finite simplicial complexes[END_REF] we studied this property for simplicial pairs, i.e. compact pairs (X, A) consisting of a finite simplicial complex X and a subcomplex A. We gave a purely topological characterization of the simplicial pairs having computable type. Definition 5.2. Let > 0. A compact pair (X, A) ⊆ Q has thesurjection property if every continuous function f : X → X satisfying f | A = id A and d X (f, id X ) < is surjective.

Theorem 5.1 ([AH22a]). A simplicial pair (X, A) has computable type if and only if it has the -surjection property for some > 0.

One implication of this theorem is that if (X, A) fails to have thesurjection property for every > 0 in an effective way (Definition 5.3), then (X, A) does not have computable type, i.e. has a copy (Y, B) in Q consisting of semicomputable sets, such that Y is not computable.

In order to formulate the definition, we recall the definition of the Hausdorff distance between non-empty compact sets A, B ⊆ Q: Definition 5.3. Let (X, A) be a computable compact pair in Q. For > 0, say that δ > 0 is an -witness if there exists a continuous function f : X → X satisfying f | A = id A and d X (f, id X ) < , such that d H (X, f (X)) > δ.

Say that (X, A) has computable witnesses if there exists a computable function sending each rational > 0 to a rational -witness δ > 0.

An application

We now state the result from [START_REF] Djamel | Computability of finite simplicial complexes[END_REF], and give a proof by applying Theorem 4.1 and therefore using our effective Baire category theorem, Theorem 2.2. Theorem 5.2. Let (X, A) ⊆ Q be a pair of semicomputable sets. If it has computable witnesses, then (X, A) does not have computable type, i.e. there exists a semicomputable copy of (X, A) such that X is not computable.

Remark 5.1. The statement given here is slightly stronger than the statement appearing in [START_REF] Djamel | Computability of finite simplicial complexes[END_REF]. Indeed, in [START_REF] Djamel | Computability of finite simplicial complexes[END_REF] the pair (X, A) is assumed to be computable. However, the simpler proof presented here only needs (X, A) to be semicomputable.

We now present the proof of this result. We assume that (X, A) is embedded as a semicomputable pair in Q which has computable witnesses. First, if X is not computable then (X, A) does not have computable type and the result is proved. Therefore, we can assume for the rest of the proof that X is computable (however, A may not be computable). Consider the space C(X, Q) of continuous functions from X to Q. It is endowed with a complete computable metric d(f, g) = max x∈Q d Q (f (x), g(x)), inducing a topology τ . The subspace I(X, Q) of injective continuous functions from X to Q is a dense Π 0 2 -subset, in particular it contains a dense computable sequence. We consider two weaker topologies τ 1 and τ 2 on C(X, Q).

We now check that B is contained in cl τ 1 (B ). Let h ∈ B = B d (g 0 , ). As β is an δ-witness, there exists g : X → X such that g| A = id A , d(g, id X ) < δ and d H (X, g(X)) > β. We define g 1 = h • g and show that g 1 ∈ B . One has d(g 1 , g 0 ) < by (3), and d H (g 1 (X), g 0 (X)) ≥ d H (g 0 (X), g 0 • g(X)) -d H (g 0 • g(X), h • g(X)) > 2 -d(g 0 , h) > by (4), so g 1 ∈ B . Moreover, g 1 (X) = h(g(X)) is contained in h(X) and g 1 (A) = h(g(A)) = h(A), so h belongs to cl τ 1 ({g 1 }) ⊆ cl τ 1 (B ). We have proved that B ⊆ cl τ 1 (B ).

Proof of Theorem 5.2. The subset of injective continuous functions from X to Q is a τ -dense Π 0 2 (τ )-subset of C(X, Q). Therefore, applying Theorem 4.1, there exists an injective continuous function f : X → Q that is τ 1computable but not τ 2 -computable. In other words, the pair (f (X), f (A)) is semicomputable, but f (X) is not computable.

It may seem that using Theorems 2.2 and 4.1 is a rather convoluted path to proving Theorem 5.2. A more direct proof is indeed possible (see [START_REF] Djamel | Computability of finite simplicial complexes[END_REF]), but at the cost of readability, because there are many ingredients to take care of and to put together. Our abstract results isolate the appropriate concepts that make the construction possible, separating the specific properties of the application (Lemma 5.1) from the general construction (Theorems 2.2 and 4.1), and can hopefully be applied in other contexts.

Moreover, even for concrete pairs (X, A), building a semicomputable copy which is not computable can be challenging and we are not aware of any simpler argument than the one presented here. Let us give such a concrete example. First, it is straightforward to show that the line segment does not have computable type: if r > 0 is a non-computable right-c.e. real number, then [0, r] is a semicomputable copy of the line segment which is not computable. However it seems that there is no such simple argument for slightly more elaborate sets, such as the set X shown in Figure 3, consisting of a disk attached to a pinched hollow torus. The results in [START_REF] Djamel | Computability of finite simplicial complexes[END_REF] imply that the set X does not have the -surjection property for any > 0, and that it has computable witnesses (Definition 5.3), so Theorem 5.2 implies that X does not have computable type.

We are not aware of any simpler and more concrete way of building a semicomputable copy of the set X which is not computable. It seems that the technique underlying the proof of Theorem 5.2 is the only way to build Figure 3: A space that does not have computable type, in a non-obvious way such a copy. We find it striking that the priority method is needed to prove simple computability properties of such concrete sets.

  Definition 3.2 (Witness). Let B be a non-empty τ -open set. • An X-witness is a non-empty τ -open set U ⊆ X that does not contain any non-empty τ -open set, • A B-witness is a non-empty τ -open set U ⊆ B that does not contain any non-empty V ∩ B where V is τ -open. Remark 3.1. Let us list a few equivalent formulations that may help understanding this notion. U is a B-witness if and only if:

Figure 1 :

 1 Figure 1: Illustration of Proposition 3.1: x n converge to x in the topology τ

d

  H (A, B) = max max a∈A min b∈B d Q (a, b), max b∈B min a∈A d Q (a, b) .

  for the topology τ , so it is sufficient to show that each one of them is τ -dense in B. The τ -closure of its complement is cl τ (U n V n ), and its intersection with B is contained in ∂U n ∪ ∂V n , so it is nowhere τ -dense in B. Therefore, C is τ -dense (even co-meager) in B. As a result, τ 1 is not τ -generically weaker than τ 2 .2. ⇒ 1. Assume condition 2. holds. Let C be such that τ 1 and τ 2 agree on C. We show that C is nowhere τ -dense. Let B ∈ τ be non-empty, we want to show that B contain a non-empty τ -open W set disjoint from C. Let U ∈ τ 2 come from condition 2. applied to B. As τ 1 and τ 2 agree on C, there exists

computable. For each n ∈ N and σ ∈ N * , let

where a set A is dense in a set B if B is contained in the closure of A ∩ B.

Let us show that the restriction f |Xn,σ is computable. Let B i ⊆ Y be a basic open set. We want to show that the preimage of B i under this restriction is an effective open subset of X n,σ , uniformly in i. As δ Y • F is computable on A n , there exists an effective open set U i ⊆ N , that can be computed uniformly in i, such that

(2)

Claim 3. One has

It remains to show that X = n,σ X n,σ . For x ∈ X, δ -1 X (x) is Polish and is covered by n∈N A n , so some A n must be somewhere dense in δ -1 X (x). In other words, there must exist some n ∈ N and some σ

Lemma 3.2. On N , the topology τ N is generically weaker than τ N .

Proof. Given a finite string u ∈ N * , a [u]-witness is given by [u0]. Indeed, every p ∈ [u0] is the limit, in the topology τ N , of the sequence p n obtained by replacing 0 by n in p at position |u|. One has

Proof of Theorem 3.3. Of course, each one of conditions 2., 3. and 4. implies 1. We show that 1. implies 2., 3. and 4. Let δ, δ be representations of X that are admissible w.r.t. τ and τ respectively. We can assume that they are In this section, we show how the results can be extended when there exists a third topology τ that is Polish and stronger than τ 2 . One can think of τ 1 and τ 2 as the topologies we want to compare, and of τ as an auxiliary topology which drives the construction.

τ -generically weaker topology

Let (X, τ ) be a computable Polish space and τ 1 , τ 2 be effective countablybased topologies such that τ 1 is effectively weaker than τ 2 and τ 2 is effectively weaker than τ . In other words, the following functions are computable:

We want to build a τ 1 -computable point that is not τ 2 -computable. The previous results can be extended to this more general setting. Definition 4.1. We say that τ 1 is τ -generically weaker than τ 2 if every set C ⊆ X on which τ 1 and τ 2 agree is τ -meager.

Again, "meager" can be equivalently replaced by "nowhere dense", with the same argument as in Proposition 3.3. This notion is a generalization of Definition 3.1, which can be obtained by taking τ 1 = τ and τ 2 = τ .

Again, we give more concrete characterizations of this notion, which will eventually lead to an effective version.

Proposition 4.1 (Characterization of τ -generically weaker topologies). The following statements are equivalent:

1. τ 1 is τ -generically weaker than τ 2 , 2. For every non-empty B ∈ τ , there exists U ∈ τ 2 such that there is no V ∈ τ 1 satisfying

3. For every non-empty B ∈ τ , there exist non-empty τ -open sets B , B ⊆ B such that

and B is contained in cl τ 1 (B ).

In condition 2., one can restrict B and U to be basic open sets in their respective topologies. In condition 3., B and B can also be assumed to be basic open sets, but not B . Again (X, τ ) is a computable Polish space and τ 1 , τ 2 are countably-based topologies such that τ 1 is effectively weaker than τ 2 and τ 2 is effectively weaker than τ . Definition 4.2. Say that τ 1 is effectively τ -generically weaker than τ 2 if given B ∈ τ , one can compute non-empty B , B ∈ τ and U ∈ τ 2 such that: It is an effective version of condition 3. in Proposition 4.1, as the set U witnesses that B is disjoint from cl τ 2 (B ). We now state the main result of this section. Again, it is easily proved thanks to our effective Baire category theorem 2.2. Theorem 4.1 (τ 1 -computable but not τ 2 -computable). Let (X, τ ) be a computable Polish space, τ 1 , τ 2 be effective countably-based topologies such that τ 1 is effectively weaker than τ 2 which is effectively weaker than τ .

If τ 1 is effectively τ -generically weaker than τ 2 , then there exists x ∈ X that is τ 1 -computable but not τ 2 -computable. Moreover, such a point can be found in any τ -dense Π 0 2 (τ )-set. Proof. As in the proof of Theorem 3.1, let A n be the set of points x whose set of τ -neighborhoods is not W n . The sets A n are uniformly effectively dense. Indeed, given B, output U s = B as long as W n [s] does not contain the index of U , and then

For each pair (U, V ) of finite unions of basic open subsets of Q, let

and let τ 1 be the topology generated by the sets V U,V as a subbasis.

For each basic open subset B of Q, let

and let τ 2 be the topology generated by the sets U B and V U,V as a subbasis.

Our goal is to build an injective continuous function f ∈ C(X, Q) such that f (X) and f (A) are semicomputable but f (X) is not computable; in other words, we want f to be τ 1 -computable but not τ 2 -computable.

We will apply Theorem 4.1, so we need to show that τ 1 is τ -generially weaker than τ 2 .

Lemma 5.1. Let X ⊆ Q be computable and A ⊆ X be semicomputable. If the pair (X, A) has computable witnesses, then the topology τ 1 is effectively generically τ -weaker than τ 2 .

Proof. We can assume that the centers of the basic metric balls in (C(X, Q), d) are injective functions. Given a metric ball B = B d (g 0 , ) in C(X, Q) (where g 0 and are computable and g 0 is injective), we need to compute B , B , U as in Definition 4.2. We are going to compute some suitable positive < and define:

These sets are clearly effective open sets in the respective topologies. Note that B ⊆ B ∩ U and B ⊆ B \ U . We now explain how to choose so that B is contained in cl τ 1 (B ).

Compute δ < /2 such that d Q (x, y) < δ implies d Q (g 0 (x), g 0 (y)) < /2. It implies that for all continuous functions g, h : Q → Q, If d(h, g 0 ) < δ and d(g, id X ) < δ, then d(h • g, g 0 ) < .

(3) Indeed, d(h • g, g 0 ) ≤ d(h • g, g 0 • g) + d(g 0 • g, g 0 ) < δ + /2 ≤ . Compute β, a δ-witness for (X, A). Compute ≤ δ such that for all x, y ∈ X, d Q (g 0 (x), g 0 (y)) ≤ 2 implies d Q (x, y) ≤ β. It implies that for all non-empty compact sets Y, Z ⊆ X, If d H (Y, Z) > β, then d H (g 0 (Y ), g 0 (Z)) > 2 .

(4)


Mohamed Amine Khelif
email: mohamed-amine.khelif@ensea.fr

Jordane Lorandel
email: jordane.lorandel@ensea.fr

Olivier Romain
email: olivier.romain@ensea.fr

Non-invasive I2C Hardware Trojan Attack Vector

Keywords: Hardware attack, Hardware Trojan, Security, I2C, smartphones, IoT

In smartphones, and more generally in IoT devices, manufacturers focus their efforts on securing communications with the outside world that are more exposed to attack while considering communications between secure components. By doing this, it results in internal communication buses with little or no security against attackers. I2C is the most used internal communication bus in IoT devices to communicate with sensors and memories. It is also used in recent smartphones to connect the Trusted Execution Environments (ARM TrustZone, Apple SEP, or Google Titan M) to a dedicated EEPROM memory that contains secret information such as encryption keys, anti-replay counter, or the boot ROM. In this paper, we propose a non-invasive attack through a hardware trojan on the I2C bus, which will allow us to perform two attack scenarios: a heart bleeding type attack which will allow retrieving additional information at each memory read, and a buffer overflow attack which will allow writing additional data in the memory at each write which can result in modifying secret information such as password or counters. These attacks can be performed on any device using the I2C bus. In the context of smartphones, these attacks will allow the extraction of sensitive information stored in the secure EEPROM memory.

I. INTRODUCTION

Smartphones have been massively adopted by consumers for the last decades. However, there are still many challenges related to security, especially for these devices containing a lot of sensitive and personal data. In 2020, the number of smartphone users worldwide exceeds 3.6 billion [START_REF] O'dea | Number of smartphone users worldwide from 2016 to 2026[END_REF], representing more than 30% of all circulating non-IoT devices [START_REF] Vailshery | Internet of things (iot) and non-iot active device connections worldwide from 2010 to 2025[END_REF]. On the other side, the number of IoT devices also grows these last years, up to 11.7 billion in 2020 [START_REF] Vailshery | Internet of things (iot) and non-iot active device connections worldwide from 2010 to 2025[END_REF]. This proliferation and the amount of personal information contained in these devices make them a privileged attack target for hackers. In order to protect these devices, a new standard was created under the name of Trusted Execution Environments (TEE). They work under a simple idea of isolating trusted security applications from other applications into two execution environments. Figure 1 represents TEE's simplified architecture.

As we can see in this figure, the Rich Execution Environment which is abbreviated as REE in literature is the Normal World. This environment has its operating system (OS), iOS, or Android for the most popular ones, and executes client applications. On the other side, we have the TEE which is isolated from the REE in three different forms depending on the vendor: virtual processor, internal co-processor (inside the SoC), or external co-processor. The TEE executes only trusted applications and it has its own OS and dedicated components (depending on the vendor) such as crypto-engine, security sensors, dedicated memory, etc. . It also shares components with the REE such as various memories, power management unit (PMU), Clocks, Crypto-engine, etc. . All the exchanges between the TEE and these components are performed using communication protocols. The most used are I2C and SPI protocols. I2C bus, in particular, is used as a data bus between the dedicated EEPROM memory and the TEE for example in iPhones [START_REF] Mandt | Demystifying the secure enclave processor[END_REF]. In this paper, we study the impact of an I2C hardware trojan attack using a new semi-invasive approach based on clock and data signal control. The attacker will be connected to the I2C bus and will act as an invisible malicious component that modifies the communication in real-time. Two attacks will be thus performed: a heartbleed attack by reading more information from the memory than requested by the master, and a buffer overflow by writing additional data into the memory. These attacks are performed on a test platform composed of an STM32 micro-controller communication with EEPROM memory. The choice of this set-up was motivated by two main constraints: being as close as possible to a TEE/EEPROM communication behavior and control the transaction in order to verify the results of the attack. In addition, STM32 is one of the most used micro-controllers in IoT devices using the HAL standard I2C communication library, which makes the impact of these attacks potentially important. This paper is organized as follows. First, section II presents 978-1-6654-1609-2/21/$31.00 ©2021 IEEE the different technologies of TEE used in smartphones and IoT devices with a focus on Apple's Secure Enclave security mechanisms and state-of-the-art attacks on communication buses. Then, section III details the I2C protocol and the implementation of the different attack scenarios. Finally, experimental results are given in section IV before the conclusion in section V.

II. RELATED WORKS A. Smartphones security

In smartphones, security is managed by a Trusted Execution Environment. TEEs are secure execution environments that monitor the integrity and security of the system and user's data [START_REF] Sabt | Trusted execution environment: what it is, and what it is not[END_REF]. Among the various tasks that are assigned to them, they mainly have to ensure a secure boot of the device through a bootRom, ensure the confidentiality of personal data by performing encryption and decryption, as well as the protection of the different counters and passwords of the smartphone.

There are three types of TEE in the market based on different technologies [START_REF] Peterlin | Breaking samsung's arm trustzone[END_REF]:

Virtual Processor: the most widely known is the ARM TrustZone (TZ) [START_REF] Pinto | Demystifying arm trustzone: A comprehensive survey[END_REF], which operates by adding an additional privilege level in addition to the classic levels (user, kernel, and hypervisor). This new level is called Secure Monitor and has two execution states: secure and non-secure. The ARM TrustZone and the main system share the different controllers and devices of the SoC. The TZ also have a dedicated operating system called TEE-OS, a Unique ID (UID) of the smartphone fused in the SoC, and a dedicated I2C and SPI bus that are used to connect the TZ to a dedicated EEPROM, to a fingerprint sensor, etc. . These shared components depend on the smartphone architecture.

Internal Co-Processor: this technology is used by Apple in their smartphones with the name of Secure Enclave Processor (SEP) [START_REF] Gulati | Security enclave processor for a system on a chip[END_REF]. In iPhones [START_REF] Mandt | Demystifying the secure enclave processor[END_REF], the SEP manages security, protection keys (password, fingerprint, faceID, GID, UID...) and data encryption/decryption. It uses encrypted memory and integrates a hardware true random number generator (TRNG). It has its own operating system, SEPOS, as well as its own devices (crypto-engine and random number generator) and its own hardware inputs and outputs (GPIO, UART, etc.). It also has shared hardware as a PMU, a memory controller, a clock generator, and the RAM. It is also connected to a dedicated EEPROM memory through the I2C bus. Communications between the Secure Enclave and the application processor are limited to an interrupt triggered mailbox.

External Co-Processor: such as Google Titan M processor which is used from 2018 in pixel 3. Titan M [START_REF] Triggs | Will google's titan m make it harder for the roming scene?[END_REF] is used as an interposer between the SoC and the boot flash in order to verify the boot firmware loaded. To do that, the processor has only dedicated components such as a cryptography co-processor, a hardware TRNG, a RAM, a ROM, a flash memory, and several communication buses such as I2C and SPI. It also embedded a dedicated operating system and a memory built-in self-test to guarantee the integrity of the processor.

B. Apple iPhone's SEP as a case of study

Apple iPhones are known to be the most secure smartphones on the market thanks to its TEE security system Secure Enclave. As said previously, the secure enclave processor is an internal co-processor integrated into Apple's devices from Apple A7 SoC. A lot of information about about the operation process of the SEP can be retrieved from Apple patent [START_REF] Gulati | Security enclave processor for a system on a chip[END_REF], iOS security guide [START_REF] Gulati | Security enclave processor for a system on a chip[END_REF] [10] and other research and reverse engineering studies [3] [11]. Figure 2 gives a simplified overview of the interaction of the SEP with the application processor (AP) and the other peripherals. The Secure Enclave (SE) is physically isolated from the AP inside the SoC and communicates through a mailbox. The SE is based on the Secure Enclave Processor which is a 32-bit ARMv7 processor working under a specific operating system called SEPOS [START_REF] Mandt | Demystifying the secure enclave processor[END_REF]. Secure Enclave also has an integrated secure AES engine and hardware TRNG used to guarantee the security of the SEP and generate encryption keys by deriving them from various keys such as UID, GID (both are fused in the SoC), and user password. It also integrates various hardware protocols such as JTAG, UART, SPI, I2C. For JTAG and UART they are deactivated in production smartphones in order to mitigate the security risks. For SPI and I2C, they are used to communicate with dedicated components outside of the SoC such as a dedicated EEPROM or various security sensors like touch ID and FaceID. This EEPROM is also called anti-rollback memory and it ensures the protection of the password attempt counter and the secure boot. The Secure enclave shares multiple components with the application processor such as boot ROM, PMGR, and an encrypted RAM partition in order to prevent attacks from malicious applications. Finally, the SE protects the data stored in the non-volatile memory (NVMe) by providing encryption keys that will be used to encrypt the data before writing them in the memory inside. This mechanism ensures the protection of personal information against off-board memory reading and bus listening besides high communication rates of the PCIe bus.

C. Attacks on communication Bus

In Trust Zones, and more generally in SoCs used in IoT devices and smartphones, the utilization of data buses to communicates with other chips of the device is of utmost importance. These buses rely on commonly used protocols that already have been the target of attacks more or less developed. From the most used we have:

1) I2C: Inter-Integrated Circuit protocol is used in smartphones and in IoT devices in general, as a communication bus between the processor/microcontroller and various sensors and/or EEPROM memory. The main attack performed on this bus targets the clock signal which has a critical role in a synchronous protocol such as I2C. These clock glitching attacks [START_REF] Gomez-Bravo | Hardware attacks on mobile robots: I2c clock attacking[END_REF] affect the system and result in a global malfunction or a denial of service. I2C can also be targeted by attacks that aim to recover the data and firmware stored in an EEPROM [START_REF] Gupta | The IoT Hacker's Handbook: A Practical Guide to Hacking the Internet of Things[END_REF] [14].

2) SPI: Serial Peripheral Interface is also one of the most used communication buses in smartphones and IoT devices. It is also very similar in peripheral type usage as I2C, except that SPI is faster and requires more space for implementation (one additional wire per slave). The bus is also vulnerable to attacks that aim to recover data and firmware from components [START_REF] Gupta | The IoT Hacker's Handbook: A Practical Guide to Hacking the Internet of Things[END_REF].

3) PCIe: Peripheral Component Interconnect express is a high-performance communication bus originally used in computers to connect high-speed components such as GPU, WiFi cards, or SSD to the motherboard. Nowadays, it is used in iPhones from the 6s version and newer as an internal bus connecting the SoC to the non-volatile memory. As demonstrated by [START_REF] Khelif | Toward a hardware man-in-the-middle attack on pcie bus[END_REF] and [START_REF] Khelif | A versatile emulator of mitm for the identification of vulnerabilities of iot devices, a case of study: smartphones[END_REF], this bus can also be targeted by hardware attack in order to passively extract information using a sniffer approach or actively interacting with the packets exchanged using a Man-in-the-Middle.

4) UART: Universal Asynchronous Receiver-Transmitter which can be an external component or integrated into the chip which allows two components to communicate without using a clock. This bus has many functionalities depending on the device and that can be exploited by an attacker, from which we denote debugging, get an unauthenticated root shell, or even access the boot loader [START_REF] Gupta | The IoT Hacker's Handbook: A Practical Guide to Hacking the Internet of Things[END_REF]. UART is generally poorly protected which makes the attack not very difficult to undertake.

5) JTAG: is a protocol developed by the Joint Test Action Group and which is named after. The JTAG is used for testing, programming, debugging, and validation of devices [START_REF] Sguigna | Mitigating jtag as an attack surface[END_REF]. This protocol is embedded from the most basic IoT device to the most evolved smartphone. As with previous protocols, JTAG is also targeted by attacks such as fault injection [START_REF] Majéric | Jtag fault injection attack[END_REF] in order to gain privilege escalation. Considering its usage and the attack opportunities allowed by this protocol, the manufacturer deactivates it at the production step in order to limit the risks. For example, in iPhones, this bus is disabled, but recently it can be enabled by exploiting a checkM8 vulnerability [START_REF]Checkm8: Open-source jailbreaking tool for many ios devices[END_REF].

6) USB: Universal Serial Bus is used as the wired communication protocol used in smartphones for different purposes such as interfacing/communicating with a computer and/or recharge the device. This bus has also been targeted by various attacks, the most known are Juice jacking attacks. These types of attacks consist of integrating a malicious device in a USB charging connector that will inject malware in a smartphone [START_REF] Lau | Mactans: Injecting malware into ios devices via malicious chargers[END_REF].

Being the most used communication protocol in IoT and non-IoT devices, the I2C bus represents a valuable source of information for attackers. In recent smartphones, it is used to connect the TEE to the secure EEPROM memory. This memory store critical information such as password counter, encryption keys, etc.

In the state of the art, researchers focus on clock glitching the I2C clock, sniffing the communication, and randomly modify the payload in order to generate errors [START_REF] Jha | Iot security -part 16 (101 -hardware attack surface: I2c)[END_REF]. With a hardware trojan attack based on controlling both SCL and SDA lines that we propose, we can perform more advanced scenarios comparing to the state of the art. with our approach, we can read or write the memory or any other device without modifying the hardware to avoid detection, simply by probing the lines through pull-up resistors.

III. METHODOLOGY

A. I2C protocol

The need for a universal bus that would be simple, inexpensive, space-saving, and easy to implement led Phillips to create the I2C bus in 1982 [START_REF] Jean-Marc Irazabal | I2c manual" application note[END_REF]. This bus allows connecting several peripherals together with relatively low communication rates. The classic architecture consists of a single master with multiple slaves that can be sensors or memories. It is also possible to have multi-master configurations with arbitration to control the communication. Initially, the I2C specification defined a maximum clock frequency of 100 kHz, later increased through three modes: fast with 400 kHz, high speed with 3.4 MHz, and ultra-fast 5 MHz. Although it is less efficient than the SPI bus in terms of throughput, the I2C has the main advantage of having a small surface requirement thanks to the fact that it is composed of only 4 wires (VCC, GND, SDA, and SCL) for a maximum of 128 slaves (in the 7-bit address configuration). This feature spreads its utilization in many IoT and non-IoT devices. Two types of communication are possible in I2C, allowing to write data into the slave and to read data from the slave. For read communication, there are three main types of packets:

• Current Address Read: read-only one byte of payload from the memory address accessed by the previous packet. • Sequential Read: read n bytes of payload from the memory address accessed by the previous packet. • Random Read: this sequence is composed of two packets: a first write packet without payload in order to update the last memory address accessed then followed by a read packet with n byte payload. For write communication, there are two types of packets:

• Byte Write: write only one byte of payload size.

• Page Write: write n bytes of payload, with n is the size of a memory page in the case of an EEPROM.

Figure 3 represents the different communication format in I2C. Write packets includes Byte and Page write, and read packet includes current address and sequential read. For random read as it is a sequence composed of two packets: write packets without payload and a read packet separated by a restart signal, it is represented separately in the figure below. The communication on the I2C bus can only happen between the master and a slave device, at the initiative of the master. It imposes a clock signal on the SCL wire by driving the line to 0 and releasing it to 1 in order to generate the signal. When the clock is generated the communication can start following these steps:

Idle: the bus is not used, SDA and SCL lines are in a high state.

Start condition (and restart or repeated start): when the master wants to communicate with the slave after the idle state, it generates a start condition by first driving the SDA line low, while SCL remains high. For a restart condition, it is similar to a start condition in driving signals, the master directly sends another packet without stopping the communication to avoid conflict with potential other masters.

Device address: the master sends 7 bits corresponding to the device slave address.

Read/Write bit: the slave address is directly followed by the R/W bit that will define the rest of the packet format.

Ack/Nack: each byte is followed by an Ack/Nack bit. For write packets and if there is no error in the communication, the slave will acknowledge each byte. For read packets, the slave acknowledges the first byte (device address and R/W bit) then the master will acknowledge every byte received from the slave until the last byte where the master sends a negative acknowledgment bit to stop the slave from sending data.

Memory address: this information is only available in write packets, and depending on the type of the peripheral it can be one byte (ex. temperature sensor) or two bytes long (ex. EEPROM).

Payload: is the data in the packet.

Stop condition: when the communication is over, the master generates a stop condition by releasing first the SCL line and then the SDA line.

B. Experimental set-up

The experimental set-up is composed of an STM32 Nucleo-F446RE kit communicating with an AT24C128 EEPROM 128kB memory from ATMEL through the I2C bus. In order to know precisely the data contained in the memory, the STM32 initializes each page with different data using a sequence of the page write, with a 64 bytes payload size (corresponding to one page in this EEPROM). Then, the micro-controller starts the communication with the memory by using a sequence of reads and writes that we target through our attack. For verification, we use also a Digilent Analog Discovery 2 to monitor signal with both the scope and the protocol decoder features. The experiment set-up is represented in Figure 4 The architecture of the attacker was implemented onto an FPGA Zedboard platform from Digilent, and the design runs at a clock frequency of 100MHz in the PL part.

SDA SCL

Master

Analog Dicovery

Decoder Scope

Attacker FPGA Slave EEPROM Fig. 4. experimental set-up architecture.

C. Approach

The proposed approach is based on two phases: a sniffing phase and an attack phase which can be one of the two proposed scenarios.

The sniffing step is performed by the FPGA in order to retrieve the necessary information about the system such as:

Master/Slaves addresses: this information can be found by sniffing the first 7 bits of each packet new packet and it will be necessary to know all slave addresses on the bus.

Number of slaves: from the previous information it will be easy to determine the number of slaves because each one has a unique address on the bus Memory addressing format: to identify a random read sequence involving the targeted slave. To do that, we need to find in the logged communication a write packet followed by a read packet, separated by a restart condition. The size of the write packet will then provide information about the memory addressing format. If the packet is two bytes long the memory address format is one byte. If the packet is three bytes long then the memory address is on two bytes. Two bytes address format corresponds to a memory address which means that the slave is a memory, in our case an EEPROM.

Sniffing the I2C communication can be performed by many devices such as the protocol decoder of the analog discovery 2, but we choose to develop an FPGA architecture in order to synchronize attack scenarios with particular events on the bus. This can also be used by attackers to perform an offline depth analysis of the recorded packets with advanced algorithms in order to find sensitive information even in encrypted communications.

In our case we decided to perform the following attacks:

1) Heartbleed attack: This attack will be used to overread the memory by controlling SDA and SCL. In order to not create conflict on the bus and been stopped by an unfortunate stop condition generated by the master, the attack will be performed by corrupting a legitimate read packet from the Master. The principle of this attack is to perform an on-the-fly analysis of the first byte of each packet looking for a read packet sent to the targeted slave. Then, from the acknowledgment of the first byte (device address + R/W bit), the FPGA attacker will control both SCL and SDA lines. For SCL, in order to avoid the release of the clock when the master has finished reading data, the FPGA attacker will generate a synchronized clock with the original one. For the SDA line, ack/nack bit sent by the master bit will be set to zero, forcing the communication to continue. Then, the memory will answer all the stored information byte by byte and page by page.

2) Buffer overflow attack: This attack will allow overwriting a section of the memory in order to replace security information in the memory such as encryption keys, counters, etc. The principle of the attack needs as for the previous one, to analyze the communication and to take control of both the SDA and SCL lines. We first analyze the communication looking for a write packet, and then from the acknowledgment bit of the first byte, we generate our synchronized clock on SCL and force SDA to zero. This will avoid the generation of stop condition and making possible to write data to the slave up to one page, which in the case of our memory is 64 bytes.

In a practical approach, this I2C hardware trojan can be inserted into an IoT device without modifying the device. In the case of these devices, the attacker will need to locate I2C pull-up resistors and interface directly by soldering wires on them or using a probing machine in order to be non-invasive.

IV. RESULTS AND DISCUSSION

To demonstrate the effectiveness of the proposed attacks, we realized the following experiments:

A. Sniffing I2C communication

For this experimentation, we decided to add another slave (temperature sensor) in the presented set-up in order to detect and define the specification of each device. Table I resume the information extracted from 30 s of I2C sniffing. The first information that we got from sniffing is the presence of two slaves because of the two different device addresses 0x18 and 0x50 with respectively 8 bits and 16 bits memory addressing format. This information is determined from the memory address of the write packet in a random read sequence. Memory addressing format gives also information about the type of slave. For 8 bits format, the slave may be a sensor because of the small number of registers embedded, and for 16 bits format, it probably corresponds to a memory chip because of the need for more addressing space. These assumptions can also be correlated to the known I2C slave address database which lists the known devices using their address [START_REF] Romkey | I2c address list[END_REF]. For addresses, 0x18 only accelerometers and temperature sensors are listed, and for 0x50 it can be a memory or a PWM driver (not so common in IoT devices). We analyze also the type of packet used for each device in order to ensure that the attacks can be performed: read packets for heart bleeding and write packets for buffer overflow. This architecture can also be used to sniff all the packets in order to perform a communication analysis and data mining relayed on multiple parameters such as the number of packets, the time between packets, payload size, etc.

B. Heart bleeding

Heart bleeding attack aims to extract more information from memory than asked by the master by a read request. To achieve this goal, the attacker must control SDA and SCL. Figure 5 shows the experimental results of the attack recorded by the analog discovery 2 protocol analyzer connected to the I2C bus. The first graph represents the normal read request sequence between the master and the memory, with a write packet to update the memory address and a read packet with 4 bytes of payload. The second graph represents the result of the attack, which forces all ack/nack bit to zero in order to avoid the negative acknowledgment that stops the memory. The attacker regenerates the clock by driving SCL to zero. This attack permitted us to extract all the data stored in memory.

When performing the preliminary tests of the attack, we noticed that the I2C clock generated by the master is at 100 kHz but the duty cycle is not at 50%. It is 47% in the high state and 53% in the low state, which has to be taken into account in order to generate a correct clock for the attack. In fact, to avoid some glitches occurring when regenerating the clock with the FPGA, we chose to generate a clock that will have a ratio of 43% in the high state and 57% in the low state. This modification will make the falling edge occurring sooner than normal in order to have a more stable SDA signal and reduce the chances to be stopped by a potential stop condition sent by the master. It could be also interesting to explore the degree of resilience of the system when the high state is reduced as low as possible, and what impact will it have on the system.

C. Buffer overflow

Figure 6 shows the experimental results of the buffer overflow attack. This attack will overwrite a complete page of the memory even if the attacker wants to write only one byte. the attack is limited to one page (64 bytes) because of the limitation of the memory that needs to temporize between writing two pages. In Figure 6, the first graph represents a normal 4 bytes payload write packet, and the second graph is the result of the attack. In order to perform the attack, the FPGA forces the SDA line to zero and generates the SCL clock from the first ack bit after the memory address. This control of SDA will corrupt the data stored in the memory and makes it impossible a stop condition. This attack will overwrite up to one page of the memory, depending on where the master starts writing.

V. CONCLUSION

In this paper, we proposed a hardware trojan capable of sniffing and attacking the I2C bus. This bus even massively used in IoT and non-IoT devices are still poorly secured. It is also used as a communication bus between the TEE and its secure memory in recent security mechanisms of smartphones. The architecture proposed proves that an attacker device connected to the I2C bus can interact with the system by manipulating data and clock signals in order to extract all the data stored in the memory through a heart bleeding attack or to overwrite up to one page of the memory through a buffer overflow attack. These attacks could be performed without being detected by neither the master nor the slaves. If the memory is not encrypted, the attacker can directly access the secrets otherwise the sniffed communication can be analyzed in order to extract other relevant information.

In future work, the architecture will be improved to perform a hardware man-in-the-middle attack, in order to fully control the bus in order to analyze and modify data on the fly. We will also study the countermeasures against our attack, such as analyzing bus behavior by the master or through implementing a dedicated chip capable of recognizing attacks.

Fig. 1 .

 1 Fig. 1. Simplified architecture of a TEE principle.

Fig. 2 .

 2 Fig. 2. Simplified architecture of Apple's SoC and interaction between AP and SEP.

Fig. 3 .

 3 Fig. 3. I2C communication frame types.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Experimental results of heart bleeding attack (recorded with analog discovery 2 Logic analyzer).

TABLE I SPECIFIC

 I METRICS EXTRACTED FROM I2C RECORDED TRAFFIC USING THE SNIFFER.

	Information from analysis	Slave 1	Slave 2
	Address	0x18	0x50
	Memory format	8 bits	16 bits
	Byte Write	No	Yes
	Page Write	Yes	Yes
	Current Address Read	No	No
	Sequential Read	No	No
	Random Read	Yes	Yes