David Vicente

An Anisotropic Mumford-Shah Model

Introduction

This work is motivated by the segmentation problem of sets strongly elongated in some directions as, for instance, tubes or thin plates in an image of dimension n ∈ {2; 3}. In Computer Vision, the Mumford-Shah model is one of the most studied [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variationnal problems[END_REF]. It consists, for a given image g ∈ L ∞ (Ω), in finding a couple (u, K) which minimizes the following energy

E M S (u, K) = Ω\K (u -g) 2 dx + Ω\K |∇u| 2 dx + H n-1 (K), (1.1)
where u ∈ W 1,2 (Ω \ K), K is compact and H n-1 is the (n -1)-dimensional Hausdorff measure. To minimize this energy, K must fit the set of discontinuity of the image and u must represent the regular part of the intensity. In order to adapt this model for the particular case of thin and elongated sets, we have introduced in [START_REF] Vicente | Anisotropic bimodal energy for segmentation of thin tubes and its approximation with Γ-convergence[END_REF] a Finsler metric ϕ which must fit the anisotropy of the image. At any point x ∈ Ω, ϕ(x, •) is a norm whose unit ball coincides with the elongation of the sets we want to detect. So, we set

E(u, K) = Ω\K (u -g) 2 dx + Ω\K |∇u| 2 dx + K ϕ(x, ν)dH n-1 , ( 1.2)
where u ∈ W 1,2 (Ω \ K), K is a compact (n -1)-dimensional submanifold and ν is an unit vector orthogonal to K. This kind of model which consists in an energy with a volumic and a surfacic parts also arises in Fracture Mechanics Theory ( [START_REF] Braides | Energies in SBV and variational models in fracture mechanics[END_REF][START_REF] Chambolle | An approximation result for special functions with bounded deformation[END_REF][START_REF] Iurlano | A density result for GSBD and its application to the approximation of brittle fractures energies[END_REF] for example). In this setting, the analysis for the case where ϕ is a constant norm has been treated in [START_REF] Focardi | On the variational approximation of free-discontinuity problem in the vectorial case[END_REF]. To our knowledge, the inhomogeneous case, where ϕ also depends on x, has not been done yet.

Since the compact submanifolds of Ω cannot be endowed with a topology which ensures that the direct methods apply, a weak formulation of the problem is needed. To do this, De Giorgi and Ambrosio [START_REF] Giorgi | A new type of functional in the calculus of variations[END_REF] proposed to set this kind of problem in the space SBV of special functions with bounded variation. Thus, setting K = J u in (1.2) and defining E(u) = E(u, J u ), it gives

E(u) = Ω (u -g) 2 dx + Ω |∇u| 2 dx + Ju ϕ(x, ν u )dH n-1 , ( 1.3)
where u ∈ SBV(Ω), ∇u is the derivative of u with respect to the Lebesgue measure, J u is its jump set and ν u is an unit vector orthogonal to J u . The abstract theory in SBV has been developed: Ambrosio established the existence result [START_REF] Ambrosio | A compactness theorem for a new class of functions of bounded variation[END_REF][START_REF] Ambrosio | A new proof of the SBV compactness theorem[END_REF], and regularity for minimizers of this kind of energy has been proved [START_REF] De Giorgi | Existence theorem for a minimum problem with free discontinuity set[END_REF][START_REF] Ambrosio | Partial regularity of free discontinuity sets i[END_REF][START_REF] Ambrosio | Partial regularity of free discontinuity sets ii[END_REF][START_REF] Bucur | Monocity formula and regularity for general free discontinuity problems[END_REF]. Those results ensure that any minimizer u of the relaxed problem in SBV provides a couple (u, J u ) which also minimizes the initial model E.

The numerical approximation for solutions is hard because of the treatment of the jump set J u . To overcome this difficulty, the idea is to perform a variational approximation of the functional E in the sense of De Giorgi Γ-convergence [START_REF] Giorgi | Su un tipo di convergenza variazonale[END_REF][START_REF] Maso | An introduction to Γ-convergence[END_REF] with Ambrosio-Tortorelli's approximation.

In order to approximate (1.3), we propose two slightly different families of functionals (E ε ) ε and ( E ε ) ε defined by

E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 (1 -z 2 ) 2 dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx, (1.4
)

E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 [η ε + (1 -z 2 ) 2 ]dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx.
(1.5)

For both versions, the function z takes its values in [0; 1] and plays the role of a control on the gradient of u. In the second one, the parameter η ε is infinitesimal with respect to ε. The first functional is directly inspired by the initial Ambrosio-Tortorelli's approximation [START_REF] Ambrosio | Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence[END_REF], while the second one was introduced later in [START_REF] Ambrosio | On the approximation of free discontinuity problems[END_REF] and it was used in various papers, for example [START_REF] Focardi | On the variational approximation of free-discontinuity problem in the vectorial case[END_REF][START_REF] Focardi | Asymptotic analysis of Ambrosio-Tortorelli energies in linearized elasticity[END_REF][START_REF] Conti | Phase field approximation of cohesive fracture models[END_REF]. Those functionals are more adapted for numerics since usual finite element methods can be directly applied. They formally differ by the introduction of the term

η Ω |∇u| 2 dx. (1.6)
By this way, E ε admits as natural domain of definition the classical Sobolev space (W 1,2 (Ω)) 2 . However, this term is not strictly necessary in our study because all the results which are proven for E ε are also true for E ε . For this simplification, the cost to pay is a slightly longer analysis in order to introduce an adapted domain for E ε which ensures that its minimization is still a well-posed problem.

The Γ-convergence result when ε → 0 + will be proven for both E ε and E ε . However, in the Image Processing context, the parameter ε is devoted to be small but fixed. Indeed, for stability of the algorithms, ε has to be bounded by below by a positive constant which depends on the size of the grid (see [START_REF] Chen | Applications of semi-implicit Fourier-spectral method to phase field equations[END_REF]). As in practice we can not take the limit ε → 0, we may choose the first version in order to avoid the additional diffusion in the numerics due to the term (1.6).

One may think that such Γ-convergence result is useless for applications because of the lower bound for ε. Nevertheless, this result provides a continuous model (1.2) of the discrete energy which may be used as a mirror to understand the proper geometry of the problem. Then, an automatic determination of the (numerous) parameters of the algorithms is possible if we have an apriori on the image we want to get (see [START_REF] Bergounioux | Parameter selection in a Mumford-Shah geometrical model for the detection of thin structures[END_REF][START_REF] Vicente | Anisotropic bimodal energy for segmentation of thin tubes and its approximation with Γ-convergence[END_REF]).

In section 2, we introduce the geometric framework and we recall some results on spaces of functions with bounded variation. In section 3, we introduce the family of functionals (E ε ) ε with their domains, we give our main result and its complete proof.

Functional framework

In all the paper, Ω is an open and bounded domain with Lipschitz boundaries. We adopt the notations:

• •, • for the canonical scalar product, | • | for the euclidean norm in R n , dist for the associated distance and • for the associated matricial norm,

• B(Ω) for the Borelian functions and L n for the Lebesgue measure on Ω,

• H k for the k-dimensional Hausdorff measure,

• ūN for the truncation min(N, max(u, -N )),

• f is superadditive if f (A ∪ B) ≥ f (A) + f (B) for any disjoints sets A, B, • f is non decreasing if f (A) ≤ f (B) for any sets A, B such that A ⊂ B.
In all the paper, in order to emphasize on the 1-D specific technic, we denote ∇v by v for any function v which is defined on R.

Local metrics and Minkowski content

We introduce the geometric framework adapted to the anisotropic setting.

i) for any x ∈ Ω, ϕ(x, •) is a norm on R n ,
ii) there exists λ > 0, Λ > 0, such that, for any

(x, v) ∈ Ω × R n , we have λ|v| ≤ ϕ(x, v) ≤ Λ|v|. (2.1)
To any metric we may associate its dual as follows.

Definition 2.2. For ϕ ∈ M(Ω), its dual metric ϕ o is defined by

ϕ o (x, v) = sup{ v, v : ϕ(x, v ) ≤ 1}.
A well known consequence of the definition is the following assertion: if ϕ ∈ M(Ω) then ϕ o ∈ M(Ω) and ϕ oo = ϕ. For S ⊂ Ω, we may consider the associated geodesic distance:

d ϕ o (x, y) = inf 1 0 ϕ o γ, γ dt : γ ∈ W 1,1 ([0; 1]; Ω), γ(0) = x, γ(1) = y , d S ϕ o (x) = inf {d ϕ o (x, y) : y ∈ S} .
According to (2.1), d S ϕ o is Lipschitz and then it is differentiable almost everywhere. Furthermore, we have the following (see [START_REF] Bellettini | Some results on surface measures in calculus of variations[END_REF]) Proposition 2.1. Let S ⊂ Ω be a closed set and ϕ ∈ M(Ω). Then, we have

ϕ(x, ∇d S ϕ o (x)) = 1
at each point x ∈ Ω \ S where d S ϕ o is differentiable. We recall that, for S ⊂ R n , the (n -1)-dimensional upper Minkowski content of S is defined by

M (S) = lim sup ρ→0 + L n ({x : dist(x, S) < ρ}) 2ρ .
In our anisotropic setting, the associated anisotropic Minkowski (n -1)-dimensional upper content is defined by the limit

M ϕ o (S) = lim sup ρ→0 + L n ({x ∈ Ω : d S ϕ o (x) < ρ}) 2ρ . (2.2)
In [START_REF] Federer | Geometric Measure Theory[END_REF] (Theorem 3.2.39), under regularity assumptions on S, it is proved that M (S) ≤ H n-1 (S). We need the following generalization of this result. Proposition 2.2. Let K ⊂ Ω be a finite union of (n -1)-dimensional simplexes and ϕ ∈ M(Ω). Then, we have

M ϕ o (K) ≤ K ϕ(x, ν)dH n-1 .
The proof is given in Appendix A.

BV spaces and slicing results

For the classical definitions and results on BV and SBV we refer to [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]. We recall that, if u ∈ BV(Ω), then its derivative Du belongs to the space of vectorial Radon measures and, if u ∈ SBV(Ω), then the Cantor part of Du is null and we obtain

Du = ∇u • L n + (u + -u -)ν u • H n-1 J u ,
where ∇u is the density of Du with respect to the Lebesgue measure L n , u + (resp. u -) is the approximate upper (resp. lower) limit and H n-1 J u is the restriction of H n-1 to its jump set J u . The slicing results are crucial in our study. Definition 2.3. Let ν ∈ S n-1 be fixed. We denote by Π ν the hyperplane

{x ∈ R n : x, ν = 0} . If x ∈ Π ν , we set Ω x = {t ∈ R : x + tν ∈ Ω} , Ω ν = {x ∈ Π ν : Ω x = ∅} .
For any function u defined on Ω and any x ∈ Ω ν , we set

(u) x : Ω x → R t → u(x + tν).
The following Theorem is proved in [START_REF] Ambrosio | A compactness theorem for a new class of functions of bounded variation[END_REF].

Theorem 2.1. Let u ∈ L ∞ (Ω) be a function such that, for all ν ∈ S n-1 , i) (u) x ∈ SBV(Ω x ) for H n-1 a.e. x ∈ Ω ν , ii) Ων Ωx |(u) x |dt + H 0 (J (u)x ) dH n-1 (x) < +∞;
then, u ∈ SBV(Ω) and H n-1 (J u ) < +∞. Conversely, let u ∈ SBV(Ω) ∩ L ∞ (Ω) be such that H n-1 (J u ) < +∞. Then i) and ii) are satisfied. Moreover, we have iii) ∇u(x + tν), ν = (u) x (t), for a.e. t ∈ Ω x and H n-1 -a.e. x ∈ Ω ν , iv)

Ju | ν u , ν |dH n-1 (x) = Ων H 0 (J (u)x )dH n-1 (x).
We state a result (Proposition 1.16 in [START_REF] Braides | Some results on surface measures in calculus of variations[END_REF]) which will simplify the presentation of the slicing technics. Let us now introduce a sub-class of SBV functions. Definition 2.4. Let W(Ω) be the space of all u ∈ SBV(Ω) such that i)

H n-1 (J u \ J u ) = 0; ii) J u is the intersection of Ω with a finite number of (n -1)-dimensional simplexes; iii) u ∈ W k,∞ (Ω \ J u ) for every k ∈ N.
The following Theorem (see [START_REF] Cortesani | A density result in SBV with respect to non-isotropic energies[END_REF]) provides a density result which will be useful for the approximation proof.

Theorem 2.2. Let u ∈ SBV(Ω) ∩ L ∞ (Ω) be such that H n-1 (J u ) < +∞, ∇u ∈ L 2 (Ω), then there exists a sequence (u k ) k ⊂ W(Ω) such that i) u k → u strongly in L 1 (Ω); ii) ∇u k → ∇u strongly in L 2 (Ω); iii) lim sup k u k ∞ ≤ u ∞ ;
iv) for every A ⊂⊂ Ω and for every uppersemicontinuous function ϕ

: Ω × R × R × S n-1 → [0; +∞] such that ϕ(x, a, b, ν) = ϕ(x, a, b, -ν) for every x ∈ Ω, a, b ∈ R and ν ∈ S n-1 there holds lim sup k→∞ A∩Ju k ϕ(x, u - k , u + k , ν u k )dH n-1 ≤ A∩Ju ϕ(x, u -, u + , ν u )dH n-1 .

Approximate Differentiability and GSBV space

Due to the non coercivity of

Ω |∇u| 2 (1 -z 2 ) 2 dx in W 1,2
(Ω), we need to introduce a weaker definition for ∇u and a larger domain for (1.3).

Definition 2.5. Let x ∈ Ω be a Lebesgue point of u ∈ L 1 (Ω); we say that u is approximately differentiable at x if there exists L ∈ R n such that lim r→0 + L n (B(x, r)) -1 B(x,r) |u(y) -u(x) -L, y -x | r dy = 0.
If u is approximately differentiable at x then L, uniquely determined by this equality, is called the approximate differential of u at x and denoted by ∇u(x).

Remark 2.1. The concept of approximate differentiability of u at x can be rephrased as the convergence in L 1 loc (R n ) of the functions v r (y) = [u(x + ry) -u(x)]/r to the linear function Ly. As (v r ) r converges to Du in the sense of distributions, if u ∈ L 2 (Ω) and its approximate differential exists and belongs to L 2 (Ω; R n ), then u belongs to W 1,2 (Ω) and its weak derivative coincides with its approximate differential almost everywhere.

This definition of the differentiability satisfies the following result [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] (Theorem 3.83).

Theorem 2.3. If v ∈ BV(Ω), then v is approximately differentiable almost everywhere in Ω.

Moreover, the approximate differential ∇v is the density of the absolutely continuous part of Dv with respect to the Lebesgue measure.

We need the three following technical Lemmas.

Lemma 2.2. If u, v ∈ B(Ω), u is approximately differentiable at x and

lim r→0 + L n ({y ∈ B r (x) : u(y) = v(y)}) r n = 0, then v is
: v(x) = 0}.
While the proof of Lemma 2.3 is given in Appendix B, the proofs of Lemmas 2.2 and 2.4 may be found in [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] (Proposition 3.71 and 3.73). Eventually, as no L ∞ bound is imposed by our functional (1.3), then it is useful to consider the following wider class

GSBV(Ω) = {u ∈ B(Ω) : ūN ∈ SBV(Ω) for any N ∈ N}.
The structure of the generalized derivative of a GSBV function is similar to that of a SBV function [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] (Proposition 3.73 and Theorem 4.34). In this case, we have

J u = ∞ M =1 J ūN (2.3)
and J u is also countably H n-1 -rectifiable; for any N, M ≥ 1, it satisfies

ν ūN (x) = ν ūM (x), for H n-1 -a.e. x ∈ J ūN ∩ J ūM . (2.4)
Moreover, u is also approximately differentiable L n -a.e. in Ω and

∇u(x) = ∇ū N (x), for L n -a.e. x ∈ {|u| ≤ N }, (2.5
)

∇ū N (x) = 0, for L n -a.e. x ∈ {|u| > N }, (2.6)
Thus, relations (2.3), (2.4) and (2.5) provide a slightly more general meaning for ∇u, J u and ν u and then it ensures that our functional (1.3) is well defined in GSBV(Ω).

Γ-convergence result

This section is entirely devoted to the approximation process. In subsection 3.1 we define the domains for both E ε and E ε . Then, we give the main Theorem of this paper. In subsection 3.2 we prove, for ε > 0 fixed, that the minimization problems admit a solution. Eventually, in subsection 3.3, we give the complete proof of Γ-convergence for both E ε and E ε .

The functionals, their domains and the main Theorem

Formally, we define

E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 (1 -z 2 ) 2 dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx, E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 [η ε + (1 -z 2 ) 2 ]dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx.
Both functionals E ε and E ε are well defined in

D n (Ω) = W 1,2 (Ω) × W 1,2 (Ω; [0; 1]). Contrary to E ε ,
the functional E ε is not coercice for the Sobolev norm because the coefficient (1 -z 2 ) 2 removes the coercivity with respect to u. For that, we need to introduce a specific domain for E ε that ensures the existence of a minimizer. If, in addition, u is bounded, we have

|∇(u(1 -z 2 ))| 2 = |∇u(1 -z 2 ) -2uz∇z| 2 , ≤ 2|∇u| 2 (1 -z 2 ) 2 + 4 u ∞ |∇z| 2 .
It gives

Ω |∇(u(1 -z 2 ))| 2 dx ≤ 2 + 4 u ∞ λε E ε (u, z).
So, it is natural to set

D n (Ω) = (u, z) : u ∈ B(Ω), z ∈ W 1,2 (Ω; [0; 1]), ūN (1 -z 2 ) ∈ W 1,2 (Ω) for any N ≥ 1 .
Assuming (u, z) ∈ D n (Ω) does not ensure that u ∈ W 1,2 (Ω) and ∇u can not be defined as the gradient of u in the Sobolev space. For that, the gradient of u is interpreted as in Definition 2.5 and then, the following Proposition ensures that E ε (u, z) is well defined in D n (Ω).

Proposition 3.1. If (u, z) ∈ D n (Ω), then u is approximately differentiable in {x ∈ Ω : z(x) = 1} and z is approximately differentiable in Ω.
Moreover, almost every where in {x ∈ Ω : z(x) = 1}, we have

(1 -z 2 )∇u = ∇[u(1 -z 2 )] + 2uz∇z, (3.1)
where ∇ is the approximate derivation on the left hand side and the weak derivation in W 1,2 (Ω) on the right hand side.

Proof. As Ω is bounded, then the inclusion W

(1 -z 2 )∇ū N = ∇[ū N (1 -z 2 )] + 2ū N z∇z,
where ∇ is the approximate derivation. As z, ūN (1 -z 2 ) ∈ W 1,2 (Ω), according to Theorem 2.3, their approximate derivatives correspond to their weak derivatives almost everywhere. According to Lemma 2.2, u and u(1 -z 2 ) are a.e. approximately differentiable in {|u| < N } and we have

∇ū N (x) = ∇u(x), ∇[ū N (1 -z 2 )](x) = ∇[u(1 -z 2 )](x), ūN (x) = u(x),
for a.e. every x ∈ {|u| < N }, which concludes the proof.

We consider the following functionals:

• E : B(Ω) → [0; +∞] defined by E(u) = Ω (u -g) 2 dx + Ω |∇u| 2 dx + Ju ϕ(x, ν u )dH n-1 if u ∈ GSBV(Ω)
, and E(u) = +∞ otherwise;

• E ε : B(Ω) × B(Ω) → [0; +∞] defined by E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 (1 -z 2 ) 2 dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx if (u, z) ∈ D n (Ω)
, where (1 -z 2 )∇u is defined by the right hand side of (3.1). Moreover, we set

E ε (u, z) = +∞ otherwise; • E ε : B(Ω) × B(Ω) → [0; +∞] defined by E ε (u, z) = Ω (u -g) 2 dx + Ω |∇u| 2 [η ε + (1 -z 2 ) 2 ]dx + Ω εϕ(x, ∇z) 2 + z 2 4ε dx if (u, z) ∈ D n (Ω), E ε (u, z) = +∞ otherwise.
The main result of the paper is the following Theorem 3.1. If g ∈ L ∞ (Ω) and ϕ ∈ M(Ω), then we have the following assertions.

i) For any ε > 0, E ε admits a minimizer, denoted by (u ε , z ε ). Moreover, we can assume that

u ε (x) = g(x) on {x ∈ Ω : z ε (x) = 1}.
ii) For any (ε k ) k converging to 0 + , there exists a subsequence, still denoted by (ε k ) k , and u ∈ GSBV(Ω) such that (u ε k , z ε k ) k converges to (u, 0) almost everywhere and u is a minimizer of E.

If, by addition, η ε = o(ε), the same result holds true for E ε .

We set (P) :

Min{E(u) : u ∈ B(Ω)}, (P ε ) : Min{E ε (u, z) : (u, z) ∈ B(Ω) × B(Ω)}, ( P ε ) : Min{ E ε (u, z) : (u, z) ∈ B(Ω) × B(Ω)}.
Theorem 3.1 i) implies that, for ε > 0 fixed, (P ε ) and ( P ε ) are well posed problems, its proof is given in Section 3.2. Theorem ii) implies that, up to the extraction of a subsequence, the sequence of solutions of (P ε k ) and ( P ε k ) converge to a solution of (P), its proof is given in Section 3.4.

Existence result for (P ε ) and ( P ε )

We prove Theorem 3.1 i) for E ε , which is a straightforward consequence of Propositions 3.2 and 3.3.

The arguments for E ε are the same, so its proof is omitted.

Proposition 3.2. Let ϕ ∈ M(Ω) and ε > 0 be fixed. There exists

(u k , z k ) k a minimizing sequence of E ε such that (u k ) k is a bounded sequence in L ∞ (Ω), (z k ) k weakly converges to z in W 1,2 (Ω), (u k , z k ) k
converges almost everywhere to (u, z) ∈ D n (Ω) and u(x) = g(x) on {x : z(x) = 1}.

To prove it, the following Lemma is needed.

Lemma 3.1. For (u, z) ∈ D n (Ω) and ν ∈ S n-1 fixed, we have (u x , z x ) ∈ D 1 (Ω x ) for H n-1 -almost every x ∈ Ω ν (see the notations of definition 2.3), and

u x (t) = ∇u(x + tν), ν , z x (t) = ∇z(x + tν), ν , for almost every t ∈ Ω x \ {s : z(x + sν) = 1}.
The proof is given in Appendix C. Now, we prove Proposition 3.2.

Proof. Let (u k , z k ) k be a minimizing sequence for E ε . We fix N ≥ g ∞ and we consider the truncated functions u N k . As for the proof of Proposition 3.1, we get that u N k (1 -z 2 k ) and 1 -z 2 k are approximately differentiable almost everywhere and u N k is approximately differentiable almost everywhere in {x : z k (x) = 1}. According to relations (2.5) and (2.6), ∇u N k (x) = 0 almost everywhere in {x :

|u N k (x)| = N } and ∇u N k (x) = ∇u k (x) almost everywhere in {x : |u N k (x)| < N }. So, we get Ω |∇u N k | 2 (1 -z 2 k ) 2 dx ≤ Ω |∇u k | 2 (1 -z 2 k ) 2 dx. (3.2) We deduce that E ε (u N k , z k ) ≤ E ε (u k , z k ) and then (u N k , z k )
k is also a minimizing sequence. According to (2.1), we have

Ω |∇z k | 2 dx + Ω z 2 k dx ≤ 1 λε + 4ε E ε (u k , z k ),
and then (z k ) k is a bounded sequence of W 1,2 (Ω). So, there exists a subsequence, still denoted by (z k ) k , which converges almost everywhere to z ∈ W 1,2 (Ω) and z takes also its values in [0; 1]. For

w k = u N k (1 -z 2 k ), we have Ω |∇w k | 2 dx + Ω w 2 k dx ≤ 2 Ω |∇u N k | 2 (1 -z 2 k ) 2 dx + 2N 2 Ω |∇z k | 2 dx +N 2 Ω (1 -z 2 k ) 2 dx
and then (w k ) k is a bounded sequence of W 1,2 (Ω). Then, we may extract a subsequence, still denoted by (w k ) k , which converges almost everywhere to w ∈ W 1,2 (Ω). In particular, (u N k (x)) k converges for almost every x ∈ {y : z(y) = 1} to u(x). If x ∈ {y : z(y) = 1}, we set u(x) = g(x). This construction ensures that (u, z) ∈ D n (Ω).

Proposition 3.3. Let ϕ ∈ M(Ω) and ε > 0 be fixed. If (u k , z k ) k ⊂ D n (Ω) converges almost every- where to (u, z) ∈ D n (Ω), (u k ) k is a bounded sequence in L ∞ (Ω) and (z k ) k weakly converges to z in W 1,2 (Ω), then lim inf k→∞ E ε (u k , z k ) ≥ E ε (u, z). Proof. Fatou Lemma gives lim inf k→∞ Ω (u k -g) 2 dx ≥ Ω (u -g) 2 dx, lim inf k→∞ Ω z 2 k 4ε dx ≥ Ω z 2 4ε dx. ( 3.3)
As ϕ oo = ϕ, we have

ϕ(x, v) = sup ν∈S n-1 1 ϕ o (x, v) v, ν .
Let ν ∈ S n-1 be fixed and A ⊂ Ω an open set. It gives

A ϕ(x, ∇z k ) 2 dx ≥ A 1 ϕ o (x, ν) 2 ∇z k , ν 2 dx. (3.4)
As (z k ) k weakly converges to z in W 1,2 (Ω), then ( ∇z k , ν ) k weakly converges to ∇z, ν in L 2 (A). Moreover, x → 1/ϕ o (x, ν) belongs to L ∞ (A), so we deduce that ( ∇z k , ν /ϕ o (x, ν)) k weakly converges to ∇z, ν /ϕ o (x, ν) in L 2 (A). As the L 2 -norm is lower semi-continuous with respect to the weak convergence, we deduce that lim inf

k→∞ A 1 ϕ o (x, ν) 2 ∇z k , ν 2 dx ≥ A 1 ϕ o (x, ν) 2 ∇z, ν 2 dx (3.5)
Let (ν i ) i be a countable dense family of S n-1 . We set

µ(A) = lim inf k→∞ A ϕ(x, ∇z k ) 2 dx, ψ i (x) = 1 ϕ o (x, ν i ) ∇z(x), ν i .
As sup i ψ i (x) = ϕ(x, ∇z(x))

|∇u k | 2 (1 -z 2 k ) 2 dx ≥ Ω |∇u| 2 (1 -z 2 ) 2 dx. (3.7)
We first consider the one-dimensional case n = 1 and then by a slicing argument we get the lower semi-continuity for the general case n ≥ 1.

For any δ ∈]0; 1[, we set A δ = {x ∈ Ω : z(x) < 1 -δ}. As n = 1, then z is a continuous function, A δ is an open set and (z k ) k uniformly converges to z. In particular, we have

A ⊂ {x ∈ Ω : z k (x) ≤ 1 -δ/2}
for k large enough, and so it yields

A δ |u k | 2 dx ≤ 1 1 -(1 -δ/2) 2 E ε (u k , z k ).
With the same argument as for Remark 2.1, we deduce that (u k ) k is a bounded sequence of W 1,2 (A δ ). We may assume that this sequence is weakly convergent to u in W 1,2 (A δ ) and as (z k ) k is uniformly convergent to z, we get

A δ |u | 2 (1 -z 2 ) 2 dx ≤ lim inf k→∞ A δ |u k | 2 (1 -z 2 k ) 2 dx.
Passing to the limit δ → 0 + gives

Ω |u | 2 (1 -z 2 ) 2 dx ≤ lim inf k→∞ Ω |u k | 2 (1 -z 2 k ) 2 dx.
Now, we generalize this result to the dimension n ≥ 1. With the notation u x introduced in Definition 2.3, using the previous result obtained in dimension 1, Lemma 3.1 and Fatou Lemma, give

A | ∇u, ν | 2 (1 -z 2 ) 2 dx = Aν Ax |u x (t)| 2 (1 -z x (t) 2 ) 2 dtdx, ≤ Aν lim inf k→∞ Ax |(u k ) x (t)| 2 (1 -(z k ) x (t) 2 ) 2 dtdx, ≤ lim inf k→∞ Aν Ax |(u k ) x (t)| 2 (1 -(z k ) x (t) 2 ) 2 dtdx, ≤ lim inf k→∞ Aν Ax | ∇u k (x + tν), ν | 2 (1 -z k (x + tν) 2 ) 2 dtdx, ≤ lim inf k→∞ A | ∇u k , ν | 2 (1 -z 2 k ) 2 dx, ≤ lim inf k→∞ A |∇u k | 2 (1 -z 2 k ) 2 dx,
for any open set A ⊂ Ω and every ν ∈ S n-1 . Let (ν i ) i be a dense and countable family of S n-1 . We set

ψ i = | ∇u, ν i | 2 (1 -z 2 ) 2 , ψ = |∇u| 2 (1 -z 2 ) 2 , µ(A) = lim inf k→∞ A |∇u k | 2 (1 -z 2 k ) 2 dx.
As µ is superadditive on A(Ω), according to Lemma 2.1, we may conclude

Ω |∇u| 2 (1 -z 2 ) 2 dx ≤ lim inf k→∞ Ω |∇u k | 2 (1 -z 2 k ) 2 dx.

Γ-convergence result for ε → 0 +

This section is dedicated to the proof of Theorem 3.1 ii). For that, we will prove the following Γ-convergence result.

Theorem 3.2. Let ϕ ∈ M(Ω) be fixed and (ε k ) k be a sequence which converges to 0 + . Then, we have

i) if u ∈ B(Ω), (u k , z k ) k ⊂ D n (Ω) and (u k , z k ) k converges to (u, 0) in L 1 (Ω), then lim inf k→∞ E ε k (u k , z k ) ≥ E(u); (3.8)
ii) for any u ∈ B(Ω), there exists a sequence

(u k , z k ) k ⊂ D n (Ω) such that (u k , z k ) k converges to (u, 0) in L 1 (Ω) and lim sup k→∞ E ε k (u k , z k ) ≤ E(u).
(3.9)

If η ε = o(ε), the same result holds true for E ε k . Moreover, the same sequence (u k , z k ) k than for E ε k may be used for (3.9).

The inequality for the lower Γ-limit

We prove the first inequality of Γ-convergence (3.8). As the domain of

E ε k is included in the domain of E ε k , it
E ε k (ū N k , z k ) ≥ E(ū N )
holds true for any N ≥ 1, as

E ε k (ū N k , z k ) ≤ E ε k (u k , z k ) for any N ≥ g ∞ and (E(ū N )) N converges to E(u) when N converges to +∞, then we get (3.8). Let u ∈ L ∞ (Ω) and (u k , z k ) k ⊂ D n (Ω) such that (u k ) k is bounded in L ∞ (Ω) and (u k , z k ) k converges to (u, 0) in L 1 (Ω).
In the sequel, we emphasize on the domain of the function: for U an open subset of Ω, we adopt the following notation

F (u; U ) = U |∇u| 2 dx + Ju∩U ϕ(x, ν u )dH n-1 , F ε k (u k , z k ; U ) = U |∇u k | 2 (1 -z 2 k ) 2 dx + U ε k ϕ(x, ∇z k ) 2 + z 2 k 4ε k dx.
It is implicit that U = Ω in the previous notation if it is not mentioned. Fatou Lemma yields

lim inf k→∞ Ω (u k -g) 2 dx ≥ Ω (u -g) 2 dx
and then it suffices to prove that lim inf F ε k (u k , z k ) ≥ F (u). We perform the proof in two steps: the first step deals with dimension 1. The second generalizes it for dimension n ≥ 2.

The one-dimensional case. We first give a lower bound for the surface term in dimension n = 1.

As we argue like in [START_REF] Ambrosio | Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence[END_REF], [START_REF] Ambrosio | On the approximation of free discontinuity problems[END_REF], [START_REF] Braides | Some results on surface measures in calculus of variations[END_REF], we only mention the result. In this paragraph, we assume that Ω = I is an open interval and that ϕ is a constant m > 0. Moreover, we assume in this section that m is fixed. We denote the 1-D approximating functional by

G ε (u, z; I) = I |u (t)| 2 (1 -z(t) 2 ) 2 dt + I mε|z (t)| 2 + z(t) 2 4ε dt, (3.10)
where the domain is

D 1 (I) = {(u, z) : u ∈ L ∞ (I), z ∈ W 1,2 (I; [0; 1]), u(1 -z 2 ) ∈ W 1,2 (I)}.
We denote the lower Γ-limit, by

G -(u; I) = inf lim inf k→∞ G ε k (u k , z k ; I) ,
where the inf is taken over all sequence (u k , z k ) k ⊂ D 1 (I) such that (u k , z k ) converges almost everywhere to (u, 0) in I. We have the following

I |u (t)| 2 dt + m 1/2 H 0 (J u ∩ I) ≤ G -(u; I).
Generalization to dimension n ≥ 2. We give the proof of (3.8).

Let u ∈ SBV(Ω) ∩ L ∞ (Ω) and (u k , z k ) k ⊂ D n (Ω) converging in L 1 (Ω) to (u, 0) such that (u k ) k is bounded in L ∞ (Ω).
Up to the extraction of a subsequence, we may assume that its convergence is pointwise almost everywhere. We have to prove that lim inf k→∞

F ε k (u k , z k ) ≥ F (u). (3.11)
We assume that lim inf F ε k (u k , z k ) is finite, otherwise the result is ensured.

Claim: We denote µ(A) = lim inf F ε k (u k , z k ; A). For any A ∈ A(Ω) and ν ∈ S n-1 , we have µ(A) ≥ A ∇u, ν 2 dx + Ju∩A 1 ϕ o (x, ν) 2 | ν, ν u | dH n-1 .
(3.12)

Let δ > 0 be fixed. As ϕ is uniformly continuous, there exists a finite family

(A i ) i ⊂ A such that diam(A i ) ≤ δ, ∪ i A i = A and, for any i ∈ I, it satisfies |ϕ(x, v) -ϕ(y, v)| ≤ δ|v|, ( 3.13)
for any (x, y) ∈ A 2 i and v ∈ R n . We fix a i ∈ A i for all i ∈ I. Let ν ∈ S n-1 be fixed. According to (3.13), (2.1), for any (x, v)

∈ A i × R n , we have |ϕ(x, v) -ϕ(a i , v)| ≤ δ|v|, ≤ δλ -1 ϕ(a i , v).
We set C(δ) = (1 -δλ -1 ) 2 , then, for any x ∈ A i , we get

ϕ(x, ∇z k (x)) 2 ≥ C(δ)ϕ(a i , ∇z k (x)) 2 . (3.14) As (ϕ o ) o = ϕ, we get ϕ(x, v) = sup ν∈S n-1 1 ϕ o (x, ν) v, ν and then ϕ(a i , ∇z k (x)) 2 = sup ν∈S n-1 1 ϕ o (a i , ν) 2 ∇z k (x), ν 2 (3.15)
According to (3.14) and (3.15),

F ε k (u k , z k ; A i ) is greater than A i |∇u k | 2 (1 -z 2 k ) 2 + C(δ) 1 ϕ o (a i , ν) 2 ε k ∇z k , ν 2 + z 2 k 4ε k dx.
With the notation introduced in Definition 2.3, (v) y is the function defined on (A i ) y ν as (v) y (t) = v(y + tν). According to Lemma 3.1, we have (u k ) y (t) = ∇u(y + tν), ν and (z k ) y (t) = ∇z(y + tν), ν , so Fubini Theorem implies that F ε k (u k , z k ; A i ) is greater than

(A i )ν (A i ) y ν |(u k ) y | 2 (1 -((z k ) y ) 2 ) 2 + C(δ) 1 ϕ o (a i , ν) 2 ε k |(z k ) y | 2 + ((z k ) y ) 2 4ε k , According to Claim, µ(A) ≥ A ψ i dx. As sup i ψ i (x) = |∇u(x)| 2 , Lemma 2.1 yields (3.

16).

Step 2: Jump Part. For any A ∈ A(Ω), we prove that

lim inf k→∞ F ε k (u k , z k ; A) ≥ Ju∩A ϕ(x, ν u ) dH n-1 . (3.17)
We consider (ν i ) i ⊂ S n-1 and µ as in Step 1 and we set

ψ i (x) = 1 ϕ o (x, ν i ) | ν u (x), ν i |.
According to Claim, we have µ(A)

≥ A ψ i dH n-1 . As sup i ψ i (x) = ϕ(x, ν u (x)), Lemma 2.1 yields (3.

17).

Conclusion: Let µ be the Borel measure on Ω defined for any Borelian A ⊂ Ω by

µ(A) = Ju∩A ϕ(x, ν u ) dH n-1 .
Let δ > 0 be fixed, according to the inner regularity of Borel measures (Proposition 1.43 in [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]), there exists a compact

K ⊂ J u such that µ(J u \ K) ≤ δ, that is Ju\K ϕ(x, ν u ) dH n-1 ≤ δ. ( 3.18)
We set

K τ = {x ∈ Ω : dist(x, K) < τ }. First Step implies that Ω |∇u| 2 dx is finite. As K ⊂ J u , then we get H n-1 (K) < +∞
F ε k (u k , z k ; Ω) ≥ lim inf k→∞ F ε k (u k , z k ; K τ ) + lim inf k→∞ F ε k (u k , z k ; Ω \ K τ ), ≥ Ju∩Kτ ϕ(x, ν u ) dH n-1 + Ω\Kτ |∇u| 2 dx, ≥ Ju ϕ(x, ν u ) dH n-1 + Ω |∇u| 2 dx -2δ.
Taking the limit δ → 0 + concludes the proof.

The inequality for the upper Γ-limit

In this section we prove the upper inequality of Γ-convergence, that is ii) of Theorem 3.2, for both E ε k and E ε k . As for the lower inequality case, it is sufficient to prove it with u ∈ L ∞ (Ω). Indeed, if for any N ≥ 1 there exists a sequence (u k,N , z k,N ) k which converges to (ū N , 0) in L 1 (Ω) and which satisfies lim sup

k→∞ E ε k (u k,N , z k ) ≤ E(ū N ),
then by a diagonal extraction, there exists a sequence (u k , z k ) k which converges to (u, 0) in L 1 (Ω) and which satisfies (3.9). So, let u ∈ B(Ω) ∩ L ∞ (Ω) be fixed. We prove that there exists a sequence

(u k , z k ) k ⊂ D n (Ω) such that (u k , z k ) k converges to (u, 0) almost everywhere, lim sup k→∞ Ω |∇u k | 2 (1 -z 2 k ) 2 dx + Ω ε k ϕ(x, ∇z k ) 2 + z 2 k 4ε k dx is lower than Ω |∇u| 2 dx + Ju ϕ(x, ν u )dH n-1 and lim sup k→∞ Ω |∇u k | 2 η ε k dx = 0.
According to Theorem 2.2 and Proposition 2.2, with a diagonal extraction, it suffices to prove a weaker result, where Ju ϕ(x, ν u )dH n-1 is replaced by its approximation with a Minkowski content. More precisely, it suffices to prove the following Proposition 3.5. Let ϕ ∈ M(Ω) be fixed, (ε k ) k be a sequence converging to 0 + and

η k = o(ε k ). For u ∈ SBV(Ω) ∩ L ∞ (Ω), there exists a sequence (u k , z k ) k ⊂ D n (Ω) such that (u k , z k ) k converges to (u, 0) almost everywhere, (u k ) k is bounded in L ∞ (Ω) and lim sup k→∞ F ε k (u k , z k ) ≤ Ω |∇u| 2 dx + M ϕ o (J u ), lim sup k→∞ Ω |∇u k | 2 η k dx = 0. (3.20)
Proof. Without loss of generality, we may assume that |∇u| ∈ L 2 (Ω) and M ϕ o (J u ) < +∞, otherwise the result is obvious. If u ∈ W 1,2 (Ω), then J u = ∅ and the stationary sequence

u k = u, z k = 0 is a solution. If u ∈ W 1,2 (Ω), then J u = ∅ and (1 -z 2 k ) 2 has to be infinitesimal near of J u . For ρ > 0, we set (J u ) ρ = {x ∈ Ω : d Ju ϕ o (x) < ρ}. (3.21)
We separate Ω in three parts:

(J u ) b k , (J u ) a k +b k \ (J u ) b k , Ω \ (J u ) a k +b k (3.22) with a k = -4ε k ln(ε k ), b k = √ ε k η k . ( 3.23)
Let Ψ k defined by

Ψ k (x) =      1 ∀x ∈ (J u ) b k /2 , 2 -2d Ju ϕ o (x)/b k ∀x ∈ (J u ) b k \ (J u ) b k /2 , 0 ∀x ∈ Ω \ (J u ) b k . ( 3
|∇Ψ k | ≤ 2 b k λ . We set u k = (1 -Ψ k )u and then u k ≡ u in Ω \ (J u ) b k . As (b k ) k converges to 0 then u k converges to u almost everywhere. As we have ∇u k = -∇Ψ k u + (1 -Ψ k )∇u, we get Ω |∇u k | 2 η k dx ≤ η k u ∞ 8 b 2 k λ 2 L n ((J u ) b k ) + 2 Ω |∇u| 2 dx .
As M ϕ o (J u ) < +∞, there exists (ω k ) k a sequence which converges to 0 + such that

L n ((J u ) b k ) ≤ 2b k (M ϕ o (J u ) + ω k ), (3.25)
it gives

Ω |∇u k | 2 η k dx ≤ η k u ∞ 16 b k λ 2 (M ϕ o (J u ) + ω k ) + 2 Ω |∇u| 2 dx . As η k /b k → 0 and η k → 0, we deduce that lim sup k→∞ Ω |∇u k | 2 η k dx = 0
and then the second inequality of (3.20) is proven. It remains to prove the first one. For that, we set

z k = 1 in (J u ) b k and z k = ε 2 k in Ω\(J u ) a k +b k . In (J u ) a k +b k \(J u ) b k we adopt the following construction: we introduce θ k (t) = ε 2 k exp t 2ε k and we set zk (t) =      1 ∀t ∈ [0; b k ], θ k (a k + b k -t) ∀t ∈]b k ; a k + b k ], ε 2 k ∀t ∈]a k + b k ; +∞[. (3.26)
This is a continuous and decreasing function defined on [0; +∞[, moreover, for any

t ∈]b k ; a k + b k [, it satisfies ε k (z k (t)) 2 = (z k (t)) 2 4ε k . (3.27) We set z k = zk • d Ju ϕ o . As z k is constant in (J u ) b k ∪ (Ω \ (J u ) a k +b k ), we have F ε k (u k , z k ) = Ω\(Ju) a k +b k |∇u| 2 (1 -ε 4 k ) 2 dx + (Ju) a k +b k \(Ju) b k |∇u| 2 (1 -z 2 k ) 2 dx + (Ju) a k +b k \(Ju) b k ε k ϕ(x, ∇z k ) 2 + z 2 k 4ε k dx + ε 3 k 4 L n (Ω \ (J u ) a k +b k ) + 1 4ε k L n ((J u ) b k ).
(3.28)

As |∇u| ∈ L 2 (Ω) and (a k + b k ) k converges to 0, the first term of (3.28) converges to Ω |∇u| 2 dx. As z k ∞ ≤ 1, the second term converges to 0. As Ω is a bounded domain, the fourth term converges to 0. According to (3.25), the fifth term is lower than 1 2 ε k (M ϕ o (J u ) + ω k ). So, the fifth term converges to 0. To compute the limit of (F ε k (u k , z k )) k , it remains to study the convergence of

A k (z k ) = (Ju) a k +b k \(Ju) b k ε k ϕ(x, ∇z k ) 2 + z 2 k 4ε k dx.
For almost every x ∈ (J u ) a k +b k \ (J u ) b k , we have

∇z k = z k • d Ju ϕ o ∇d Ju ϕ o .
It gives

A k (z k ) = (Ju) a k +b k \(Ju) b k ε k (z k • d Ju ϕ o ) 2 ϕ(x, ∇d Ju ϕ o ) 2 + (z k • d Ju ϕ o ) 2 4ε k dx.
According to Proposition 2.1, ϕ(x, ∇d Ju ϕ o (x)) = 1 for almost every x. So, we may write

A k (z k ) = (Ju) a k +b k \(Ju) b k ε k (z k • d Ju ϕ o ) 2 + (z k • d Ju ϕ o ) 2 4ε k ϕ(x, ∇d Ju ϕ o )dx.
We may apply an anisotropic version of the coarea formula (see [START_REF] Maso | Integral representation on bounded variation spaces of Γ-limits of variational integrals[END_REF]), it gives

A k (z k ) = a k +b k b k ε k z k (t) 2 + zk (t) 2 4ε k Ω ϕ(x, D1 (Ju)t ) dt. (3.29) We set H ϕ (t) = Ω ϕ(x, D1 (Ju)t ), A ϕ (s) = s 0 H ϕ (t)dt.
Applying another time coarea formula gives

A ϕ (s 2 ) -A ϕ (s 1 ) = s 2 s 1 Ω ϕ(x, D1 (Ju)t ) dt, = (Ju)s 2 \(Ju)s 1 ϕ(x, ∇d Ju ϕ o )dx, = L n ((J u ) s 2 \ (J u ) s 1 ). So, A ϕ ∈ W
A k (z k ) = a k +b k b k ε k z k (t) 2 + zk (t) 2 4ε k H ϕ (t)dt, = a k +b k b k zk (t) 2 2ε k H ϕ (t)dt, = z2 k (a k + b k ) 2ε k A ϕ (a k + b k ) - z2 k (b k ) 2ε k A ϕ (b k ) - 1 ε k a k +b k b k z k (t)z k (t)A ϕ (t).
The first term obviously converges to 0. As for (3.25), we have

A ϕ (b k ) ≤ 2b k (M ϕ o (J u ) + ω k )
and then the second term converges to 0 too. As s → A ϕ (s) is non decreasing, then

A ϕ (t) ≤ 2t(M ϕ o (J u ) + ω k ) for any t ∈ [b k ; a k + b k ].
For the last term, we apply another time this inequality, it gives

- 1 ε k a k +b k b k z k (t)z k (t)A ϕ (t)dt ≤ - (M ϕ o (J u ) + ω k ) ε k a k +b k b k 2tz k (t)z k (t)dt. ( 3.30)
Integrating by parts yields

a k +b k b k 2tz k (t)z k (t)dt = (a k + b k )z k (a k + b k ) 2 -b k zk (b k ) 2 - a k +b k b k zk (t) 2 dt. ( 3
(a k + b k )z k (a k + b k ) 2 -b k zk (b k ) 2 = o(ε k ) (3.32)
and equation (3.27) gives

a k +b k b k zk (t) 2 dt = 2ε k a k +b k b k |z k (t)|z k (t)dt, = ε k (1 -ε 2 k ). ( 3
F ε k (u k , z k ) ≤ Ω |∇u| 2 + M ϕ o (J u ).
To conclude the proof, it suffices to notice that (u k , z k ) k ⊂ D n (Ω).

Compactness result for (P ε ) ε and ( P ε ) ε

In this Section we prove Theorem 3.1, ii). As the same arguments hold for both cases, we only give the proof for (P ε ) ε . According to Theorem 3.1 i), for any ε > 0, there exists (u ε , z ε ) a minimizer of E ε . According to (3.2), with N ≥ g ∞ , we have

L n ({x ∈ Ω : |u ε (x)| > N }) > 0 ⇒ E ε (u N ε , z ε ) < E ε (u ε , z ε ).
We deduce that u ε ∞ ≤ N for any ε > 0. For

ω ε = u ε (1 -z 2 ε ), we get ∇ω ε = ∇u ε (1 -z 2 ε ) -2u ε z ε ∇z ε . It yields Ω |∇ω ε |dx ≤ L n (Ω) 1/2 Ω |∇u ε | 2 (1 -z 2 ε ) 2 dx 1/2 + 2N Ω |∇z ε |z ε dx. (3.34) Applying the inequality 2ab ≤ a 2 + b 2 with a = zε 2ε 1/2 and b = ε 1/2 |∇z ε | gives Ω |∇z ε |z ε dx ≤ Ω ε|∇z ε | 2 dx + Ω z 2 ε 4ε dx. ( 3

.35)

According to ellipticity inequality (2.1), we get

Ω ε|∇z ε | 2 dx ≤ 1 λ E ε (u ε , z ε ). ( 3
Ω |∇ω ε |dx ≤ L n (Ω) 1/2 (E ε (u ε , z ε )) 1/2 + 1 + 1 λ E ε (u ε , z ε ).
Let (ε k ) k be a sequence converting to 0 + . As E ≡ +∞, according to Theorem 3.2 ii), we deduce that

(E ε k (u ε k , z ε k )) k is bounded. So, (ω ε k ) k is bounded in BV(Ω)
and there exists a subsequence, still denoted by (ω ε k ) k which converges almost everywhere to ω ∈ BV(Ω). As Ω z 2 k dx ≤ ε k E ε k (u ε k , z ε k ), then (z k ) k converges to 0 in L 2 (Ω) and there exists a subsequence, still denoted by (z k ) k , which converges almost everywhere to 0. As ω ε k = u ε k (1 -z 2 ε k ), then (u ε k ) k converges almost everywhere to u ∈ L ∞ (Ω). According to Theorem 3.2, u is obviously a minimizer of E.

Conclusion

This paper is the theoretical background needed to introduce our new model. A forthcoming paper will present the numerical point of view. The main assumption of this work is the existence of an anisotropic metric ϕ which must represent the anisotropy of the image. For that, we may consider the case where ϕ is a Riemannian metric. That is, ϕ is given by a field of symmetric definite positive matrices M such that ϕ(x, v) = M(x)v, v 1/2 .

In order to favorize elongated sets, M is constrained to take its values in a compact sub manifold of symmetric definite positive matrices with fixed spectrum. In order to combine the segmentation task with the computation of this metric, the couple (u, M) must minimize the functional

Ω (u -g) 2 dx + Ω |∇u| 2 dx + Ju Mν u , ν u 1/2 dH n-1 + Ω DM n+α dx,
where α > 0 is fixed in order to satisfy the regularity condition ϕ ∈ M(Ω). Indded, according to the Sobolev embedding Theorem, the finiteness of the last term ensures that the metric is uniformely continuous. Existence of a minimizer of this energy and approximation with Γ-convergence are straightforward consequences of what we have presented in this article.

for any x, y ∈ C and v ∈ R n . It gives

M ϕ o (K i ) ≤ C∈C M ϕ o (K i ∩ C), ≤ (1 + ε(η)) C∈C M ϕ o C (K i ∩ C), ≤ (1 + ε(η)) C∈C K i ∩C ϕ C (ν)dH n-1 , ≤ (1 + ε(η)) 2 C∈C K i ∩C ϕ(x, ν)dH n-1 , ≤ (1 + ε(η)) 2 K i ϕ(x, ν)dH n-1 .
Taking the limit η → 0 + gives the result of Second Step for each compact K i . To conclude the proof of Proposition 2.2, it suffices to notice that

M ϕ o (K) ≤ i M ϕ o (K i ).

B Proof of Lemma 2.3

Let x ∈ Ω be a point such that v 1 , v 2 are approximatively differentiable at x. First, we remark that x is a Lebesgue point for v 1 , that is lim

C Proof of Lemma 3.1

As Ω is bounded, then W 1,2 (Ω) ⊂ SBV(Ω) and then, according to Calderón-Zygmund Theorem (3.83 in [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]), the derivative in the Sobolev sense is equal to the approximate differential for almost every point in Ω. Moreover, according to Theorem 3.107 of [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF], for v ∈ SBV(Ω) and ν ∈ S n-1 , we have ∇v(x + tν), ν = ∇v x (t) a.e. t ∈ Ω x for almost every x ∈ Ω ν . According to Fubini Theorem, if v ∈ W 1,2 (Ω), then v x ∈ W 1,2 (Ω x ) for almost every x ∈ Ω. Applying this property with v = z and v = u(1 -z 2 ) concludes the proof of Lemma 3.1.

Lemma 2 . 1 .

 21 Let A(Ω) be the family of open sets of Ω, µ : A(Ω) → [0; +∞[ be a superadditive function on disjoint open sets, λ be a positive measure on Ω and ψ k : Ω → [0; +∞] be a countable family of Borel functions such that µ(A) ≥ A ψ k dλ for every A ∈ A(Ω). Set ψ = sup k ψ k , then µ(A) ≥ A ψdλ for every A ∈ A(Ω).

Proposition 3 . 4 .

 34 Let I ⊂ R be an open interval and u ∈ B(I). If G -(u; I) < ∞, then u ∈ SBV(I) and

  .31) According to the definitions of (a k , b k , z k ), (3.23) and (3.26), we have

  r→0 + L n (B(x, r)) -1 B(x,r) |v 1 (y) -v 1 (x)|dy = 0. (B.1)Then, we decomposeL n (B(x, r)) -1 B(x,r) |v 1 (y)v 2 (y) -v 1 (x)v 2 (x) -v 1 (x)∇v 2 (x) + v 2 (x)∇v 1 (x), y -x | r dy ≤ L n (B(x, r)) -1 B(x,r) |v 2 (x)| |v 1 (y) -v 1 (x) -∇v 1 (x), y -x | r dy +L n (B(x, r)) -1 B(x,r) |v 1 (y)| |v 2 (y) -v 2 (x) -∇v 2 (x), y -x | r dy +L n (B(x, r)) -1 B(x,r) |(v 1 (y) -v 1 (x)) ∇v 2 (x), y -x | r dy.As v 1 , V 2 are approximatively differentiable at x and v 1 ∈ L ∞ (Ω) the two first terms converge to 0. As we have | ∇v 2 (x), y -x |/r ≤ |∇v 2 (x)| for any y ∈ B(x, r), according to (B.1), the last term also converges to 0.

  is sufficient to prove the result only for E ε k . Moreover, it is also sufficient to prove this result with (u k ) k and u uniformely bounded in L ∞ (Ω). Indeed, if lim inf

	k→∞

  .[START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] This definition ensures that Ψ k is a continuous function with support in (J u ) b k , which is equal to 1 in a neighborhood (J u ) b k /2 of J u and which shrinks to J u when k → ∞. Ellipticity inequality(2.1) yields Ju ϕ o is Lipschitzian and Rademacher Theorem ensures that ∇d Ju ϕ o exists for almost every x ∈ Ω. It gives

	|d Ju ϕ o (x) -d Ju ϕ o (y)| ≤ d ϕ o (x, y),
	≤ λ -1 |x -y|.
	So, d

  1,1 loc (]0; +∞[) and ∇A ϕ = H ϕ almost everywhere. Using equality (3.27) and then integrating by parts (3.29) gives

Acknowledgements

The author is with the Institute of Mathematics and Scientific Computing, University of Graz, Austria. The Institute of Mathematics and Scientific Computing is a member of NAWI Graz (www.nawigraz.at) and BioTechMed Graz (www.biotechmed.at). This work was supported in part by the Austrian Science Fund (FWF) under grant SFB F32 (SFB "Mathematical Optimization and Applications in Biomedical Sciences").

where the integration is done over the product measure dt dH n-1 (y). With the one-dimensional notations (3.10), it gives

where m = C(δ)

We may apply Lemma 3.4, with I = (A i ) y ν and u = (u) y , it gives that (u) y ∈ SBV((A i ) y ν ), for H n-1 almost every y ∈ (A i ) ν and we have

We deduce µ(A

If we replace m by its value, it gives

As the function ϕ is uniformly continuous, then ϕ o is also uniformly continuous and there exits a function, still denoted by C(δ), such that C(δ) → 1 for δ → 0 + and which satisfies

As µ is superadditive, we get

We take δ → 0 + , it concludes the proof of the Claim. Hereafter, we divide the remaining part of the proof in two steps corresponding on the estimate on the regular part and on the jump part of u.

Step 1: Regular Part. For any open set A ⊂ Ω, we prove the following inequality

Let (ν i ) i ⊂ S n-1 be a countable set of point which is dense in S n-1 . We set

A Proof of Proposition 2.2

We prove this result in two steps: we first assume that ϕ is homogeneous and after we generalize the result in the inhomogeneous setting.

First

Step: We assume that K ⊂ Ω is a (n -1)-simplex and ϕ is homogeneous, i.e. it does not depend on x ∈ Ω.

With the same notations as in (3.21), we set K r = {x ∈ Ω : d K ϕ o (x) < r}. We separate K r in two parts:

As ϕ is an elliptic metric (ϕ is comparable to the euclidean distance) and ∂K is a finite union of (n -2)-dimensional simplexes, we have

As we assume that ϕ is homogeneous,

where ν is an unitary and normal vector to K. As ϕ oo = ϕ, we deduce that

According to (A.1) and (A.2), we conclude that M ϕ o (K) ≤ ϕ(ν)H n-1 (K).

Second

Step: We assume that K = ∪ i K i is a finite union of (n -1)-simplexes and that ϕ depends on x ∈ Ω.

We may assume that K ϕ(x, ν)dH n-1 is finite, otherwise the result is ensured. As ϕ ∈ M(Ω), there exists λ > 0 such that

and then H n-1 (K) is also finite. For t ∈ R and i ∈ {1, . . . , n}, we set Π i t = {x ∈ Ω : x, e i = t}. Thus, for k ∈ N fixed, t ∈ R : H n-1 (K ∩ Π i t ) > 1/k is finite and then, for any i ∈ {1, . . . , n}, the set t ∈ R : H n-1 (K ∩ Π i t ) > 0 is at most countable. So, if we consider the cubes whose faces are orthogonal to the vectors of the orthogonal basis, there exists a partition C of Ω by cubes with diameter less than η, such that for any C ∈ C, we have


Carolina Zarate

Simson Garfinkel

Aubin Heffernan

Scott Horras

Kyle Gorak

Analysis of the Use of XOR as an Obfuscation Technique in a Real Data Corpus

Keywords: XOR, obfuscation, steganography, bulk extractor

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A variety of single-byte operators have been used for simple data hiding or obfuscation. A classic technique involved the use of the ROT13 operator [START_REF] Venkata | Cryptography and steganography[END_REF] to hide off-color jokes disseminated on the early Internet. Common techniques used today include single-byte XOR and singlebyte rotate operators. These operators are essentially poor encryption algorithms with 8-bit keys: they are trivial to decode, but to do so the analyst or tool must specifically probe for evidence of their use. If no detection algorithm is employed, even 8-bit encryption is sufficient to hide data.

The only digital forensic tools known to the authors that provide forensic investigators with an automated approach for finding XORobfuscated data are DCCI Carver and DC3 Carver, two general-purpose forensic carving tools developed by the Defense Cyber Crime Center (DC3). Existing commercial and open source digital forensic tools largely ignore single-byte obfuscation techniques. Although it is relatively easy to modify forensic and anti-malware tools to scan for data that have been obfuscated, most digital forensic tools and malware scanners eschew steganography detection because it is computationally expensive and the use of steganography is thought to be low. However, simple obfuscation techniques are sufficient to bypass most commercial and open source malware detection techniques, rendering the lack of de-obfuscation features in tools a vulnerability.

This paper focuses on a specific obfuscation technique, which we call XOR(255). XOR is the exclusive-or binary operation. XOR binary operations are performed with "keys." A key is a series of bytes with which a source file is XORed. XOR(255) is a special case of a single-byte key with the value 0xFF. Bytewise XOR(255) has the effect of inverting every bit in a source file. XOR(255) has the advantages of being fast (it typically executes in less than one clock cycle on modern architectures), reversible and performed in-place. XOR(255) has the additional property of leaving the file entropy unchanged, allowing processed data to remain invisible to tools that search for encrypted data using entropy techniques. We focused on XOR(255) because of its ease of use and effectiveness at obscuring data.

We created a plug-in for the open source tool bulk extractor [START_REF] Garfinkel | Digital media triage with bulk data analysis and bulk extractor[END_REF] that processes data with XOR(255). The structure of bulk extractor is such that each scanner is applied independently to each block of data during processing. The modified tool was employed to scan a corpus of several thousand drive images extracted from used storage devices that had been purchased on the secondary market. The analysis was limited to email addresses, URLs, JPEG photographs, Windows executables, ZIP files and other kinds of easily recognizable data that had been obfuscated by XOR(255). The tool optimistically applied XOR(255) before and after every decompression or decoding step in its search for recognizable structured data.

The analysis revealed that simple obfuscation techniques were present on the drives purchased on three continents over a ten-year period, with some examples of obfuscation as recent as 2009. The use of XOR(255) was limited to a small fraction of the corpus, but the applications of obfuscation are very relevant to forensic investigations. In particular, obfuscation was used to hide signatures in malware and user-generated content that appeared to be targeted for exfiltration. Also, obfuscation was used by legitimate programs to prevent reverse engineering.

Prior Work

Simple data obfuscation techniques predate the modern Internet. The ROT13 operator was used in the 1980s to distribute off-color jokes and the answers to riddles on Usenet.

Use of XOR

The academic literature on XOR obfuscation is relatively sparse. Indeed, documented examples of XOR use are largely confined to online blogs of malware investigators. Mueller [START_REF] Mueller | XOR entire file or selected text[END_REF] notes that Norton Antivirus uses XOR to obfuscate its log files and Quarantine folder; we verify this observation in this paper. Hussey [START_REF] Hussey | Decoding data exfiltration -Reversing XOR encryption[END_REF] suggests that XOR is sometimes used as an obfuscation technique to hide data as it is being exfiltrated; we discovered evidence of XOR used for this purpose.

Several types of malware have been reported as using simple obfuscation techniques to hide data being exfiltrated from a victim machine. Trojan.NTESSESS XORs the results of its commands, including uploaded files, with a changing nine-byte key [START_REF]Malware obfuscated within PNG files > Sample 2[END_REF]. Even advanced malware such as Stuxnet, Duqu, Flame and Red October use XOR as the basis of obfuscation algorithms to hide data [START_REF] Virvilis | The big four -What we did wrong in advanced persistent threat detection[END_REF]. Stuxnet uses a 31-byte key with XOR [START_REF] Falliere | Stuxnet Dossier, Symantec[END_REF]. Duqu XORs data from its keylogger, which it sends to its server [START_REF] Virvilis | The big four -What we did wrong in advanced persistent threat detection[END_REF]. Like Duqu, Flame employs XOR obfuscation techniques on captured keystrokes, screenshots, email messages and conversations recorded via the computer microphone [START_REF] Virvilis | The big four -What we did wrong in advanced persistent threat detection[END_REF]. Red October also uses XOR obfuscation techniques when exfiltrating information from Nokia phones, iPhones and networks [START_REF] Virvilis | The big four -What we did wrong in advanced persistent threat detection[END_REF].

Simple obfuscation techniques have proven to be popular for protecting malicious code and exfiltrated data from anti-virus software and forensic investigators. The SymbOS/OpFake.A!tr.dial malware from Opera Updater is one such example. Apvrille [START_REF] Apvrille | Symbian malware uses a 91-byte XOR key[END_REF] found the Opera Updater malware to contain a 91-byte XOR key as a more complicated algorithm for hiding itself. Similarly, variations of Trojan.PingBed and Trojan.NTESSESS employ XOR obfuscation and embedding techniques in PNG files to evade anti-virus scanners [START_REF]Malware obfuscated within PNG files[END_REF][START_REF]Malware obfuscated within PNG files > Sample 2[END_REF]. Cannell [START_REF] Cannell | Obfuscation: Malware's best friend, Malwarebytes[END_REF] suggests that malware may contain XORed URLs as references to malicious files and executables online, creating the appearance of benign files. An example is Trojan.Win32.Patched.mc, which disguises itself as a harmless Flash file. The Trojan file main.swf analyzed by StopMalvertising [START_REF]Trojan.Win32.Patched.mc, StopMalvertising ([END_REF] contains an XORed hexadecimal string, which allows an XORed malicious executable to be downloaded. This poses a problem for anti-virus scanners because the files appear harmless, but proceed to download files from URLs that are known to be malicious. XOR has also been used by advanced malware as a method for hiding their main code from antivirus software -Stuxnet, Duqu, Flame and Red October all obfuscate their payloads and main executables with XOR [START_REF] Virvilis | The big four -What we did wrong in advanced persistent threat detection[END_REF]. In addition, the Storm botnet and other advanced botnets have begun to take advantage of the technique, obfuscating their traffic with XOR in order to avoid identification [START_REF] Kang | Towards complete node enumeration in a peer-to-peer botnet[END_REF].

Previous research has examined how well anti-virus systems deal with simple obfuscation in malware. Common commercial anti-virus systems tested by Christodorescu and Jha [START_REF] Christodorescu | Testing malware detectors[END_REF] frequently did not identify obfuscated malware, demonstrating that simple obfuscation is an effective technique to defeat anti-virus scanners. The Internot Security Team [START_REF]Bypassing anti-virus scanners[END_REF] examined a similar case and found that simple obfuscation allowed malware to easily bypass many anti-virus scanners.

Other researchers have provided insight into techniques that could help undermine XOR obfuscation. Cannell [START_REF] Cannell | Nowhere to hide: Three methods of XOR obfuscation, Malwarebytes[END_REF] suggests that patterns inside XORed material can be used to find the XOR key. Malware normalization has also been proposed by Christodorescu, et al. [START_REF] Christodorescu | Malware Normalization[END_REF] as a method for undermining obfuscation techniques by normalizing a file, enabling anti-virus scanners to detect malicious content.

Manual Analysis Tools

Although numerous digital forensic tools can de-obfuscate a region of bytes with an XOR mask or use XOR pre-processing in malware analysis, only one tool applies XOR as part of automated processing. The other tools that de-obfuscate data require the techniques to be manually invoked by the operator. Some tools offer methods for de-obfuscating data, but leave the interpretation up to the operator. Hex editors often implement such a feature, enabling the user to view data in hex and offering de-obfuscation functions. The open source Hexplorer [START_REF] Dudek | Hexplorer[END_REF] has the ability to XOR regions before they are displayed. The translate.py script [START_REF] Stevens | [END_REF] also allows an investigator to XOR a file with a single-byte key. Other tools are specifically tailored to de-obfuscating certain components of a forensic investigation. The MemoryDump plugin [START_REF] Aeon | MemoryDump[END_REF], for instance, has an option for XORing a memory dump before outputting the data to the user.

Other tools examine data to look for XOR keys, leaving it up to the user to de-obfuscate and analyze the information. XORBruteForcer [START_REF] Esparza | XORBruteForcer[END_REF] uses a brute-force algorithm to determine the keys that were most likely to have been used in XORing the data. In contrast, NoMoreXOR [START_REF] Edwards | NoMoreXOR[END_REF] attempts to guess an XOR key using frequency analysis.

String searching is also a frequently-used feature in obfuscation analysis tools. XORSearch [START_REF] Stevens | XORSearch and XORStrings[END_REF] uses a brute-force approach to search for specific strings that have been obfuscated using XOR, ROL and ROR. Similarly, XORStrings [START_REF] Stevens | New tool: XORStrings[END_REF], an extension of the XORSearch tool, scans a given file for strings that have been XORed with a specific sequence. The iheartxor tool [START_REF] Hanel | iheartxor (hooked-on-mnemonics[END_REF] offers a similar function, using brute-force to search for certain obfuscated regular expressions and plain strings.

Automated Analysis Tools

As mentioned above, DCCI Carver and DC3 Carver are the only digital forensic tools that provide investigators with an automated approach for uncovering a wide variety of XOR obfuscated files in storage media. In addition to these tools, a literature search turned up tools that provide automated assistance in identifying obfuscated malicious files. Several programs can search for XORed executables embedded in files. Hexacorn's DeXRAY tool [START_REF] Hexacorn | [END_REF] acts as a file carver and can identify obfuscated malicious files under a single XOR layer. OfficeMalScanner [START_REF] Boldewin | Frank Boldewin's www[END_REF] has a feature to scan for traces of XORed malicious data in Office documents using a brute-force method. Another document scanner tool, Cryptam [START_REF]Cryptam document scanner[END_REF], uses cryptanalysis to identify obfuscated embedded executable files and is effective at detecting XOR obfuscation [START_REF] Tracker | New malware document scanner tool released[END_REF].

Materials and Methods

We modified an open source tool to preprocess all the examined data with XOR(255). We then processed data from 2,411 forensic images and found 324,144 XOR artifacts on 698 of the images, with a maximum of 21,031 validated artifacts on a single forensic image.

The goal of the research was to identify the different ways that XOR obfuscation is used in real data in order to determine if the quantity and quality of obfuscation cases are sufficient to suggest implementing XOR de-obfuscation functions as a standard step in automated forensic processing. In particular, we analyzed a corpus of data seeking to determine the extent to which XOR(255) is implemented as an obfuscation technique.

Real Data Corpus

The Real Data Corpus [START_REF] Garfinkel | Bringing science to digital forensics with standardized forensic corpora[END_REF] is a collection of several thousand digitized digital storage devices collected from countries around the world between 1998 and 2013. The corpus contains data from computer hard drives, cell phones, CD-ROMs, DVDs and thumb drives purchased from secondhand computer stores and markets. The corpus thus permits the sampling of XOR usage over a 15-year period in countries around the world, essentially representing a real-world data set.

A limitation of the Real Data Corpus is that it does not include data sets that are known to have been used by malicious entities. Thus, it would be difficult to draw conclusions regarding the importance of extracting and examining XOR obfuscated files in criminal, counterintelligence and counterterrorism investigations without further research. In addition, since the analysis was limited to email addresses, URLs, JPEG photographs, Windows executables, ZIP files and other kinds of easily recognizable data, we did not search for all the types of files that would be considered relevant to these types of investigations.

bulk extractor

The bulk extractor forensic tool can scan digital media for email addresses, phone numbers, Internet domain names and other data of interest to investigators. The tool is employed by triage and malware investigators [START_REF] Garfinkel | Digital media triage with bulk data analysis and bulk extractor[END_REF]. The tool employs compiled regular expressions and hard-coded finite state machines to extract features from digital media. Features are pieces of key information such as credit cards, emails and URLs that are encountered in forensic investigations. For each feature, bulk extractor determines the feature encoding and records the information in its output. The program labels features found using XOR(255) de-obfuscation with the string "XOR(255)."

The bulk extractor tool tracks the features that result from the application of each scanner; this information is recorded in the program output. By using the tool in this manner, it was possible to search the entire corpus systematically for different uses of XOR obfuscation. For example, we were able to detect and distinguish the case of a JPEG photograph being XORed and then archived in a ZIP file from a series of JPEGs that were archived in a ZIP file and then XORed. The identify filenames.py tool included in the bulk extractor package was used to associate identified features with the files in which they were located. For each feature, the tool indicated if the feature occurred in an allocated file, a deleted file or disk sectors that could not be associated with any file. This allowed the identification of the files containing XORed information and also helped understand the purpose and extent of the obfuscation.

Feature Selection

We examined the encodings of domains, URLs, email addresses, ZIP file data structures and Windows Portable Executable (WINPE) headers in order to find examples of XOR(255) usage. The problem with looking for XORed features is to distinguish actual XORed features from "false positives" or matching data that appear by chance, but that are not actual features.

We observed a much greater percentage of false positives (i.e., significantly lower precision) for the features that were found with XOR encodings than is typical for bulk extractor output (which normally has high precision). We assume that the error rate or the number of false positives detected by bulk extractor is constant for random input and a large set of data. When the input contains a substantial signal, such as when running bulk extractor to find plaintext features, the precision is high. However, with an XOR filter, the signal is low because the majority of the features in the data are not XORed. Since the signal is lower, but the error rate remains constant, the precision is lower.

The higher incidence of false positives complicated the analysis. We addressed the error incidence by restricting the analysis to features with significant internal structure that are automatically checked for internal consistency (Table 1). The features are, thus, self-validating; as a result, they are extracted with an extremely low false positive error rate. Selfvalidating features can also be easily confirmed to be legitimate at a glance, such as opening a JPEG file or clicking a URL to visit a site. Thus, we could safely assume that most of the identified features were true positives.

Because our goal was to evaluate files containing certain XOR(255)encoded features, we ignored features that were not being evaluated in order to restrict the data set. In particular, we removed features that were not XORed, features that were not being considered and "false positive" features that we did not recognize as legitimate features.

Analysis of Identified Files

After identifying the features that had been XOR-encoded, we proceeded to identify the files that contained them. The Sleuth Kit [START_REF] Carrier | The Sleuth Kit[END_REF] was used to extract the files that identify filenames.py associated with intriguing XORed features. We analyzed the original files and the files after decoding with XOR(255) to determine the purpose for which the XOR obfuscation was used.

Evaluation of URLs

The vast majority of the XOR-encoded features discovered were URLs. Malware files may contain some mechanisms to further infiltrate a victim, while appearing benign at the same time. For example, malware often contained URLs of malicious sites for downloading additional malicious executables and other files. We examined the XORed URL features outputted by bulk extractor because it has been reported that some malware samples use XOR to obscure embedded URLs. We evaluated the XORed URLs using the Google Safe Browsing API [START_REF]Google, Safe Browsing API, Mountain View, California[END_REF] and the McAfee TrustedSource Real-Time Threat Service [START_REF] Mcafee | TrustedSource -Check Single URL[END_REF].

Results and Discussion

This section presents the results and discusses their implications.

XOR Obfuscation as a Watermark

We found several cases in which an innocuous URL was XOR(255)encoded and embedded in a legitimate program. For example, drive image AE10-1023 contained a copy of Nero 7 with the byte sequence 97 8b 8b 8f c5 d0 d0 88 88 88 d1 91 9a 8b 90 d1 9c 90 92 0a at decimal offset 15,416,790,675. This maps to byte offset 112 of the file Program Files/Nero/Nero 7/Nero CoverDesigner/def.dat, a 13,630byte file with an MD5 value of 8f4b534ed6a82e1885e155541aab0940 that is reported to be part of the Nero Premium distribution [START_REF]Systweak CheckFileName, View Nero Premium Details[END_REF]. The

XORed URL Analysis

A total of 281,712 XORed URLs were found in the drive images, 30,684 of them were distinct. Google's Safe Browsing (GSB) database only checks the domains of sites and is quite conservative. For each XORed URL, GSB reports if the URL's domain is "OK" or "Malware." McAfee's Real-Time Threat Service considers the entire URL and provides better discrimination. For each URL, we recorded if McAfee considered it to be "High Risk," "Medium Risk," "Minimal Risk" or "Unverified."

Table 2 shows how the URLs were evaluated by Google's Safe Browsing API and McAfee's Real-Time Threat Service. Overall, roughly 10% of the distinct URLs found in the XORed data were tied to malware.

XOR Obfuscation in Anti-Virus Software

Confirming Mueller's observatin [START_REF] Mueller | XOR entire file or selected text[END_REF], we found many XOR-obfuscated URLs in Norton Anti-Virus log files and virus definitions. We also discovered some files in the Quarantine directory that had been obfuscated with XOR(255). The drive image il3-0161 contained one such collection of XORed quarantined malware. bulk extractor determined that the file 05FB1F54.exe contained an XORed WINPE header. The file was also indicated to be located under Program Files/Norton Antivirus/Quarantine/ with an MD5 value of a96ae9519ea968ac0089-d6b53cef9b2b. Examination of the hex dump of the original file revealed that it had no executable code or strings. However, after the file was XORed, the entire file appeared to be malware, containing strings such as "RegDeleteKeyA," "DownloadFile" and "Download.Trojan."

Malware is often distributed via "drive-by downloads" from compromised web servers and, thus, the presence of a malicious URL is a key indicator of malware. Norton and other anti-virus scanners use this approach to identify malware. By obfuscating malware signatures and log files, anti-virus scanners avoid accidentally identifying themselves as malware.

Obfuscated URLs in Malware

We found a significant number of XORed domains and URLs in programs that were clearly associated with malware. In many cases, the URLs were verified as malicious by Google's Safe Browing API or had names that were clearly malicious. One example is the file SENDFILE.EXE in the drive image IN10-0145, which has an MD5 value of 3d419f96-355b93e641ba097c08121937. The unobfuscated version of the file contained several malicious strings, including URLs linked to malware and instances that modify the registry and processes. For example, the 47byte sequence b7 ab ab af c5 d0 d0 ac bc be b1 b1 ba ad d1 a9 d2 a7 d2 ac bc be b1 b1 ba ad d1 bc b0 b2 d0 ac ba ab aa af d0 b9 b6 b3 ba d1 af b7 af appears at the decimal offset 4426 in SENDFILE.EXE. After it was processed by XOR(255), the string became HTTP://SCANNER.VAV-X-SCANNER.COM/SETUP/FILE.PHP. Based on this analysis, it is clear that some examples of malware use XOR(255) obfuscation in their normal operations.

The use of XOR(255) by anti-virus scanners and malware is problematic. In our testing, many program samples containing malicious XORed URLs were not identified as malicious by any of the 46 anti-virus engines at VirusTotal.com. However, after the files were de-obfuscated, many of the engines were able to identify the malware. Clearly, the engines simply look for the malicious URLs (because applying XOR(255) to the entire executable would also corrupt the Windows PE header and damage the executable code). It is troubling that common anti-virus engines and professional forensic tools do not even offer this simple technique for finding obfuscated malicious data, especially given the widespread use of XOR(255) in malware that we encountered in the Real Data Corpus and in our literature search.

Anti-Reverse Engineering

In many of the drive images, we observed XOR-obfuscated variations of an email address belonging to Reznik (co-developer of the RealAudio and RealVideo algorithms [START_REF] Conklin | Video coding for streaming media delivery on the Internet[END_REF]) in DLLs associated with software from his company. The email address and its variations appeared to have been repeated several times in blocks throughout the Real codecs. One example was found in the drive image AE10-1029 in the file Program Files/ Real/RealPlayer/converter/Codecs/erv4.dll. The erv4.dll file is 483,328 bytes in size and has an MD5 value of e8b759859b53e19c261162 783dae9869. The byte sequence a6 8a 8d 96 86 df ad 9a 85 91 96 94 df c3 86 8d 9a 85 91 96 94 bf 8d 9a 9e 93 d1 9c 90 92 c1 ff, which appeared at offset 61,120, was de-obfuscated to Yuriy Reznik <yreznik@real.com>. We contacted Dr. Reznik and learned that his obfuscated email address was embedded in the binary as a key for decrypting code tables used by the RealVideo 8 codec.

We also found several instances of XOR(255)-encoded JPEG digital photographs that appeared to be from Adobe Flash video games. Drive image IN10-0060 contained the Battle Rush Adobe Flash game menu screen background, drive image SG1-1062 had an XORed menu screen of Gutterball 2 and drive image TH0001-0010 had many Beach Party Craze backgrounds. We believe that the JPEG pictures were encoded as an anti-reverse engineering measure.

XOR(255)-Encoded ZIP File

On one drive image, we observed remnants of multiple ZIP files in unallocated space that contained confidential information that had been archived and XOR-encoded. The disk was from a computer running Windows 95 that had been purchased on the secondary market and imaged in 2007. The most recent use of the drive was in 2006.

On the drive image, we found a total of 802 documents with timestamps in the ZIP archive ranging from 1991 through 1999, with the majority of the files from 1998 (112 files) and 1999 (623 files). No archived files were found with timestamps after 1999.

After finding these files, we proceeded to modify the ZIP scanner of bulk extractor to carve the remnants into files that could be transferred to another system and analyzed. Upon reviewing the extracted files, we found spreadsheets, personal emails and other sensitive documents containing employee names, home addresses and government identification numbers. We located a batch file, EMPACA2.BAT, that zipped the documents to create the archive on the drive image. We were unable to find evidence of the tools that had been used to obfuscated the archive and, thus, could not prove that the obfuscation was the result of an exfiltration attempt.

There are several possible explanations for the obfuscation. The data could have belonged to the individual who was obfuscating the data; this individual could have been developing an application to protect a set of data or to protect his/her own data. Alternatively, the obfuscated ZIP file could be the result of software processing the data. On the other hand, the data could have been obfuscated by a rogue employee to hide the data or in an attempt to exfiltrate the data.

Performance Impact

We saw a significant increase in the processing time after adding the XOR scanner. One standard test drive image required 53% additional processing time, while another required 70% additional time (Table 3). Timing was performed on a 12-core HP Z800 with dual Intel Xenon E5645 CPUs running at 2.4 GHz with 24 GiB of RAM. The operation system was Fedora 19 Linux.

Because bulk extractor recursively processes decompressed data and the XOR scanner attempts to de-obfuscate the data at each step of the pipeline, the actual increase in time is dependent on the data in a disk image. The increase in time is also proportional to the amount of data that is compressed and have to be re-processed, but it is not proportional to the amount of XOR-obfuscated data. For example, the NPS Realistic drive image nps-2011-2tb contains a large number of Adobe PDF files, each of which has multiple zlib-compressed regions. Applying XOR deobfuscation to these bytes quadruples the processing time required by other bulk extractor scanners: the bytes were processed with the scanners as they sat in the disk image, after XOR de-obfuscation, after decompression, and after decompression and XOR de-obfuscation.

Accuracy of bulk extractor

We were interested in substantiating the accuracy of bulk extractor in detecting features obfuscated with XOR(255). Two standard forensic drive images, nps-2009-domexusers (40 GB) and nps-2011-2tb (2 TB), were used to study the accuracy of bulk extractor's XOR scanner. We took a random sample of 500 features from each type of feature from each drive image. Each feature was determined to be a true positive or false positive by hand. We found that, for each type of feature, bulk extractor had almost all the features as true positives or all the features as false positives. There was a higher incidence of features on the 2 TB drive image that were almost completely false positives than on the 40 GB drive image.

XOR(255)-UNZIP-XOR(255) Property

We were surprised to discover several instances in which the sequence XOR(255)-UNZIP-XOR(255) applied to a fragment of a ZIP-encoded file yielded the same result that would be produced by the straightforward application of UNZIP. We hypothesize that is the result of zlib's use of an adaptive decompression algorithm. We subsequently suppressed XOR(255)-UNZIP-XOR(255) processing with a modification to the bulk extractor XOR scanner.

Conclusions

The analysis of the Real Data Corpus revealed multiple cases of XOR(255) obfuscation. XOR(255) was used to encode URLs in antivirus scanner files and malware in order to avoid detection. XOR(255) obfuscation was also used to hinder the reverse engineering of RealVideo 8 codecs and several Adobe Flash video games. In one case, XOR(255) was likely used in a successful attempt to exfiltrate sensitive data.

The study of XOR obfuscation in the Real Data Corpus revealed several instances where XOR obfuscation is relevant to digital forensic investigations. However, the increase in processing time by bulk extractor and other forensic tools may be problematic when large data sets have to be examined in a limited amount of time. Therefore, while forensic tools should implement features that would allow investigators to perform simple de-obfuscation, the de-obfuscation should be adjustable by the investigator to run in a manual or automatic mode (similar to the XOR feature in DCCI Carver and DC3 Carver). Additionally, because the analysis has demonstrated a need for de-obfuscating malware and exfiltrated data, a forensic tool should be operated with the de-obfuscation function enabled in order to capture all the information. Likewise, XOR de-obfuscation should be enabled in child exploitation and objectionable content cases to address the so-called "botnet" or "SODDI" defense [START_REF] Brenner | The Trojan horse defense in cybercrime cases[END_REF]. Our XOR scanner is included in the bulk extractor 1.4 release and is enabled using the flag -e xor.

Our future research will focus on enhancing bulk extractor's XOR scanner to run with little noticeable performance impact. Another line of research is to conduct a thorough survey of the prevalence and purpose of other simple obfuscation and steganography techniques such as rotate and the ROT13 algorithm, as well as, XORing with different keys. Finally, efforts should focus on enhancing anti-virus systems to detect malware that has been obfuscated; the fact that simple XOR obfuscation can successfully evade today's anti-virus systems is troubling indeed.

The opinions and views expressed in this paper are those of the authors and do not reflect the views of the Naval Postgraduate School, the U.S. Military Academy, the Department of the Navy, the Department of the Army or the U.S. Department of Defense.

Table 1 .

 1 bulk extractor features used in the study.

	Feature
	URLs
	WINPE headers
	Local file headers of ZIP archives
	Exif headers (from JPEGs)

Table 2 .

 2 Cross-tabulation of the classification of the 30,684 URLs.

	McAfee Risk Google OK Google Malware Total
	High Risk	1,938	143	2,081
	Medium Risk	1,301	9	1,310
	Minimal Risk	24,090	6	24,096
	Unverified	2,216	5	2,221
	Total	29,545	163	29,708
	string was transformed to http://www.nero.com after being processed
	by XOR(255).

Table 3 .

 3 Processing times for bulk extractor with and without the XOR scanner.

	Test Image	Size Without XOR With XOR	∆
	nps-2009-domexusers 40 GB	522 sec	799 sec +53%
	nps-2011-2tb	2 TB	34,140 sec	58,147 sec +70%

Acknowledgements

We wish to thank Robert Beverly, Michael Shick and Yuriy Reznik for their help with this research. We also wish to thank Dave Ferguson from DC3, and Colonel Greg Conti, Lieutenant Colonel Matt Burrow and Lieutenant Michael Nowatkowski from the U.S. Military Academy.