S V Andreev
email: serguei.andreev@u-psud.fr

Resonant pairing of excitons in semiconductor heterostructures

We suggest indirect excitons in two-dimensional semiconductor heterostructures as a platform for the realization of a bosonic analog of the Bardeen-Cooper-Schrieffer superconductor. The quantum phase transition to a biexcitonic gapped state can be controlled in situ by tuning the electric field applied to the structure in the growth direction. The proposed playground should allow one to go to strongly correlated and high-temperature regimes, unattainable with Feshbach resonant atomic gases.

The phenomenon of pairing lies at the heart of superconductivity in metals. Here, Cooper pairs of fermionic particles (electrons), can Bose-Einstein condense to carry electric charge without dissipation. An in-depth study of this scenario, commonly known as the Bardeen-Cooper-Schrieffer (BCS) theory, has been performed by using the technique of Feshbach resonances (FRs) in ultracold atomic gases [1]. In Fermi gases this technique has allowed for the observation of a crossover from a BCS-like state made of spatially overlapping pairs of atoms to a Bose-Einstein condensate (BEC) of tightly bound diatomic molecules [2,3]. This so-called BCS-BEC crossover has become a paradigm of the many-body physics, sharing important analogies with high-temperature superconductivity [4] and neutron stars [5].

A natural idea expounded in a series of papers [6] has been to apply the same FR technique to degenerate Bose gases. It has been shown that in the case of bosons, the smooth crossover is replaced by a thermodynamically sharp phase transition from a coherent mixture of atoms and molecules to a pure molecular superfluid [START_REF] Kuklov | The case of a two-component Bose gas pertinent for the system we introduce in the present work has been analyzed[END_REF]. The latter is distinguished by the absence of atomic off-diagonal long-range order and gapped atomic excitations. Though being of great fundamental interest in its own right, until now this research has not met its applicationoriented counterpart in the physics of the solid state. Moreover, experimental attempts to realize a unitary Bose gas of atoms did not succeed. This is due to the coalescence of three and more atoms (few-body recombination) [8] and mechanical instability when approaching the resonance on the attractive side [9].

In this Rapid Communication, we propose a solid-state setting for the study and manipulation of resonantly paired bosonic superfluids. Bosonic quasiparticles we consider are indirect excitons in biased semiconductor heterostructures. Our excitonic analog of BCS is expected to be stable across the whole range of scattering lengths. The scattering length of the excitons can be conveniently tuned by the bias electric field. A distinct feature of an indirect exciton is a large dipole moment oriented perpendicularly to the structure plane. In the system under consideration, an interplay between the long-range dipolar repulsion and the resonant interaction may result in the formation of a fragmented biexcitonic supersolid.

In order to better present our idea, we first recall the basic phenomenology of the FR in atomic systems [Fig. 1(a)]. At low energies the interaction of two atoms in the open channel (OC) can be modeled as scattering via an ersatz two-body potential, schematically shown in Fig. 1(b). At short distances this potential has a minimum separated from the continuum by a large barrier. A (quasi)bound state inside the well corresponds to the closed molecular channel (CC), the outer continuum of states to the OC, and the barrier emulates coupling of the two channels due to hyperfine interactions [2]. The energy ε of the discrete level is proportional to the magnetic field detuning of the OC with respect to the CC. For a strictly two-dimensional (2D) collision (relevant for our system) the scattering length would be given by

a = r * e α , ( 1
)
where α = ε/β, the parameter β characterizes the barrier transmission (for ε β it gives the lifetime of a quasibound state inside the well according to τ = /πβ), and r * is the microscopic range of the potential. By changing ε from negative to positive values, one could realize the scattering regimes where a r * and a r * , respectively. Our proposal of a tunable excitonic interaction is based on the following observation. Consider excitons in their ground state in a wide zinc-blende semiconductor quantum well (QW). These are bosons composed of an electron with spin ± 1 2 and a heavy hole with spin ± 3 2 . Depending on the mutual orientation of the fermionic spins, the spin of an exciton can take four possible values: ±1 (the so-called "bright" excitons) and ±2 ("dark" excitons) [START_REF] Ivchenko | Optical Spectroscopy of Semiconductor Nanostructures[END_REF]. The interaction of two bright (dark) excitons having the same spin, as well as the interaction of a bright exciton with a dark one, is repulsive. At short distances such excitons avoid each other due to the Pauli exclusion of the constituent electrons and (or) holes. On the other hand, the exchange of fermions in a pair of the bright (dark) excitons with opposite spins can result in the binding of these excitons into molecules (biexcitons) [START_REF] Miller | [END_REF].

Suppose now that we apply an electric field in the direction perpendicular to the QW plane. The excitons would become polarized in the same direction. The pairwise interaction in all channels would acquire a pronounced repulsive character at the distances of the order of the dipolar length, where κ is the dielectric constant of the semiconductor, m is the exciton mass, and d is the effective distance between an electron and a hole layer in a biased QW. In the channel where the excitons have opposite spins, the dipolar repulsion would introduce a potential barrier between the outer continuum of states and the biexciton. With an increase of d the biexciton binding energy |ε| would decrease, until, at some critical value d c (to be specified below), the true bound state would disappear and become replaced by a resonance (the state with ε > 0). Close to d c ,

r * = me 2 d 2 /κ 2 , ( 2)
ε ∝ d -d c , (3)
which holds both for d > d c and d < d c , providing that ε β. One can see that there is a one-to-one correspondence between the interaction of excitons with opposite spins and the generic potential introduced to model the FR in atomic systems [Fig. 1(b)]. In particular, the result (1) with the substitution (2) applies directly to give the low-energy excitonic scattering length. The latter thus can be controlled by tuning the effective distance in the vicinity of d c . The narrow interval

|d -d c | d ∝ β (4)
corresponds to the regime of vanishing interaction. Here, not only does the proportionality law (3) not hold, but the very meaning of the parameter ε as the energy of a (quasi)bound state is no longer adequate. For d ≤ d c this energy is given by ε = -2 /ma 2 , where the scattering length a diverges according to the exponential law (1) with the power

α = α 0 ∝ d/(d c -d). ( 5
)
The full evolution of the shape of the exciton interaction potential as a function of d has been calculated numerically for GaAs coupled quantum wells (CQWs) [12,13]. The structure consists of two GaAs layers separated by a thin AlGaAs barrier [Fig. 1(c)]. From these studies one can deduce d c ≈ 7 nm. A straightforward dimensional analysis [13] indicates that d c should scale as the effective electron Bohr radius a e = 2 κ/m e e 2 when changing the compound. Clearly, these arguments can be adopted to a wide single QW as well. The advantage of the single QW with respect to the CQW configuration is that it offers a possibility to explore excitonic interactions over a wider range of d, including the limit d → 0.

Crucially, the Fermi statistics of electrons and holes prohibits bound states of more than two excitons. By virtue of the Pauli principle, the interaction of the third exciton with at least one exciton in the pair is always repulsive. The absence of trimers and larger excitonic complexes in quantum wells has been confirmed experimentally [14]. Hence, one may think of using the proposed playground for the realization of a stable bosonic analog of BCS. A distinct property of resonantly paired excitons would be long-range dipolar repulsion. In what follows, we shall discuss how it could manifest in the collective behavior of the system.

We start with the dilute regime, where one can approach the problem perturbatively. For simplicity, we shall consider a binary mixture of bright (or dark) excitons only and assume an equal population of up ("↑") and down ("↓") spin branches. Spin-polarized configurations, relevant for possible experiments in the magnetic field, will be studied elsewhere. The Hamiltonian of the system reads

Ĥ = σ =↑,↓ ˆ † σ (ρ) - 2 2m + V ext (ρ) ˆ σ (ρ)dρ + 1 2 σ,σ ˆ † σ (ρ) ˆ † σ (ρ )V σ σ (ρ-ρ ) ˆ σ (ρ) ˆ σ (ρ )dρ dρ, ( 6
)
where integration is taken over the structure area, ρ = (x,y).

In the ultracold limit the microscopic two-body interaction V σ σ (ρ -ρ ) can be substituted by effective k-dependent pseudopotentials,

V 2D σ σ (k,k ) = g σ σ -2π 2 /m|k -k |r * for a pure 2D [V ext (ρ) ≡ 0] [15] and V 1D σ σ (k x ,k x ) = g σ σ √ 2πa y + 2 mr * (|k x -k x |r * ) 2 ln(|k x -k x |r * ) (7)
for a quasi-1D geometry [16]. The latter is realized by introducing the external potential V ext (y) = mω 2 y y 2 /2 tightly confining the system in one direction, and models a waveguide of the half width a y = /mω y in the structure plane. The momentum-dependent terms in the above formulas describe the long-range dipolar repulsion (a common feature for all channels). The contact parts will be taken as positive constants for the interaction of excitons having the same spin, g ↑↑ = g ↓↓ ≡ g bg > 0, and of the resonant type

g ↑↓ = g bg + 2 m 2π ln(1/ka) + 2 k 2 /mβ (8)
for the channel where a biexciton can be formed. Here, a is the 2D scattering length given by Eq. ( 1) and in the condensate one should let 2 k 2 /m = 2μ for the energy of colliding excitons, with μ being the chemical potential. Formula ( 8) is only meaningful if ε β. In the interval (4), where the bound state disappears, one should subtract g bg from (8) and use the result (5) for the power of the exponent in (1).

Having in mind a possible application of our theory to the investigation of exciton superconductivity in 2D wires, we shall focus on the quasi-1D geometry. The main conclusions drawn here hold for the 2D case as well. Let us assume ε μ > 0, so that the situation schematically illustrated in the bottom of Fig. 1(b) is realized, with the energy of the resonance greatly exceeding the exciton energy. In this case, the ground state (GS) of ( 6) corresponds to the true kinetic equilibrium of the system with respect to the binary collisions. The GS wave function is the excitonic order parameter with the components

↑,↓ (x,y) = (n 1 /2 √ πa y )
1/2 e -y 2 /2a 2 y , having Gaussian profiles across the waveguide and uniform 1D densities n 1 (x) ≡ n 1 in the longitudinal direction. The chemical potential reads μ = n 1 g/ √ 2πa y + ω y /2. The effective coupling constant g ≡ (g ↑↑ + g ↑↓ )/2 is governed by ε, according to Eq. ( 8). The standard Bogoliubov approach [START_REF]The validity of the Bogoliubov approach for a quasi-1D configuration, i.e., in the absence of a true Bose-Einstein condensate[END_REF] yields the elementary excitation spectrum of the form

ε m (k) = E k ≡ 2 k 2 /2m, ε r (k) = E 2 k + 2n 1 E k [g/ √ 2πa y + r * ln(kr * ) 2 k 2 /m].
The first branch, having the form of a free-particle dispersion, describes the excitation of magnons (spin waves) [START_REF] Halperin | [END_REF]. The interactions manifest in the second branch. At small k it has the typical linear form with the slope c = √ ng/m (n ≡ n 1 / √ 2πa y ). Away from the resonance, where g ≈ g bg , the linear dispersion law monotonously turns to a quadratic one at higher momenta. By ramping ε down to μ, however, one can make g to be anomalously small [see Eq. ( 9) below], so that ε r (k) develops a roton-maxon structure.

Rotonization of the spectrum implies a dynamical instability [15,19,20]. In the frame of the model (6) the system would collapse . Such pathological behavior can be regularized by introducing three-body repulsive forces [21]. In our case these can enter the game on the attractive side of the resonance due to the formation of weakly bound excitonic pairs. The pair effectively behaves as a single body in collisions with the third particle, which can give rise to the three-body term

g 3 /2 ( ˆ † ↑ ˆ † ↑ ˆ † ↓ ˆ ↑ ˆ ↑ ˆ ↓ + ˆ † ↑ ˆ † ↓ ˆ † ↓ ˆ ↑ ˆ ↓ ˆ ↓ )dρ
at the two-body approximation level [22]. The three-body repulsion prevents the collapse. Instead, at the point

g = g c ≡ π 2 a y r * 2 m e -1/2n 1 r * -1 - 3 32π n 1 g 3 a y , (9)
the GS undergoes a first-order quantum phase transition to a supersolid-a condensate with a periodical modulation of density [19,21,[START_REF] Kirzhnits | [END_REF].

Physically, the onset of the roton instability reflects the tendency for the system to crystallize. It is well known that for particles interacting via long-range repulsive forces it may be profitable to arrange into a periodic structure at sufficiently high pressure and low temperature [24]. The effect of resonant attraction in a dipolar BEC consists in the possibility of building up a lattice potential already in the dilute limit. The lattice constant is of the order of the healing length ξ = 2 /mng, i.e., in contrast to usual crystals it spans a macroscopically large amount of particles.

By increasing the pressure one can bring the system to the dense and, generally speaking, strongly correlated regime. The perturbative theory fails to predict properties of the GS there. Instead, some phenomenological arguments can be applied. Thus, it can be postulated [16,25,26] that the equilibrium state of a strongly coupled excitonic BCS still manifests macroscopic long-range order, though the healing length is now much less than the lattice constant. Each unit cell of this state may be regarded as a trapped 2D BEC in the Thomas-Fermi limit. Possible quantum phases and transition between them within a condensate can be examined by using the Hamiltonian [16]

Ĥ = σ =↑,↓,B ˆ † σ (ρ) - 2 2m σ -μσ ˆ σ (ρ)dρ + 1 2 σ,σ ˆ † σ (ρ) ˆ † σ (ρ )V σ σ (ρ -ρ ) ˆ σ (ρ) ˆ σ (ρ )dρ dρ + ε ˆ † B ˆ B dρ - 2 β 2πm ( ˆ † ↑ ˆ † ↓ ˆ B + ˆ ↑ ˆ ↓ ˆ † B )dρ, (10)
with μ↑ = μ↓ = μB /2 ≡ μ being the local chemical potentials and m ↑ = m ↓ = m B /2 ≡ m. The two-body potentials can be taken in the form V σ σ (ρ -ρ ) = g σ σ δ(ρ -ρ ) with some parameters g σ σ > 0 to be defined from the experiment. The resonant interaction in [START_REF] Ivchenko | Optical Spectroscopy of Semiconductor Nanostructures[END_REF] appears explicitly as the last term which converts two excitons with opposite spins to a biexciton (the corresponding field operator is labeled by B) and vice versa.

By adjusting the external bias voltage such that μ ε one can completely eliminate the excitonic component and obtain a purely molecular (biexcitonic) BEC. The elementary excitation spectrum of this phase is shown in Fig. 2. In addition to the usual sound mode, it has a gapped branch corresponding to the pair-breaking excitations. The gap can be controlled by the applied electric field (via the parameter ε). Both branches satisfy the Landau criterion for superfluidity. For μ ε the gapped mode lies above the phonon one and the critical velocity is given by the velocity of sound c B = √ ng BB /m. For sufficiently large values of g σ σ 's, quantum fluctuations of the relative phases arising from depleted regions in between the condensates drive the supersolid to a number-squeezed configuration [25,27], akin to the fragmented BEC in optical lattices [28]. In this regime the tunneling between the adjacent lattice sites is frozen and the condensates do not talk with each other. The system resembles more a crystal than a quantum liquid. The size of a cell is governed by the balance FIG. 2. Fragmented biexcitonic supersolid. Fine tuning of the contact part of the exciton interaction by means of the electric field yields a roton instability (upper spectrum on the right) of a uniform density distribution (light gray color on the left). The instability drives the condensate to a supersolid state, characterized by periodical modulation of the density (gray, on the left). Stability of this state is guaranteed by a three-body repulsive interaction of excitons (single arrows) with their biexcitonic molecules (paired arrows). Upon a density increase, the supersolid fragments into a periodical chain of molecular condensates (dark gray), characterized by strong repulsion and a gapped elementary excitation spectrum (bottom, on the right). We take the parameters typical for the experiments on GaAs CQWs [29,30].

between the kinetic and entropy terms in the free energy of the fragmented supersolid [25]. At typical exciton densities in GaAs QWs a cell would be about 10 μm large and contain 10 4 particles.

As we have seen above, by going deep into the molecular regime (μ ε), the cells of the supersolid can be made superfluid. The characteristic temperature of biexciton superfluidity would be on the order of the Kosterlitz-Thouless (KT) transition point k B T KT ∼ 2 n/m. The upper limit on the density n is imposed by quantum dissociation of excitons that occurs when the mean interexciton distance becomes comparable to the exciton size. The latter can be significantly reduced by using the so-called van der Waals heterostructures based on transition metal dichalcogenides (TMDs) [31]. A general strategy for achieving record-high values of T KT with TMDs has been worked out in Ref. [32]. By using the results of that work, we estimate T KT ∼ 20 K and c B ∼ 5 cm/μs for the largest values of the superfluid temperature and velocity which one may expect in a prototype MoS 2 /h-BN structure.

In conclusion, we have shown that dipolar excitons in coupled 2D films can be used for the realization of a stable bosonic analog of the BCS superconductor. The state of a resonantly paired excitonic gas can be controlled by the electric field applied perpendicularly to the structure plane. The proposed setting should allow one to create novel dense and strongly correlated quantum phases of bosons. As an illustration, we predict a fragmented biexcitonic supersolid.

FIG. 1 .

 1 FIG. 1. Basic idea of the excitonic Fano-Feshbach resonance (FR). In the atomic FR (a), scattering of two atoms along the dashed potential curve, called the open channel (OC), can be modified by coupling to the closed molecular channel (CC) (solid curve). The effect of CC on OC can be taken into account by replacing the actual OC potential by the one schematically shown in (b). Remarkably, the potential of the same type describes the interaction of two indirect excitons in coupled semiconductor layers (c). The energy ε of the (quasi)biexciton is proportional to the difference dd c , where d is the distance between the layers and d c is the critical separation at which the true bound state disappears.

The author acknowledges D. S. Petrov, A. A. Varlamov, and G. V. Shlyapnikov for clarifying discussions. The research leading to these results received funding from the European Research Council (FR7/2007-2013 Grant Agreement No. 341197) and from the Government of the Russian Federation (Grant 074-U01) through ITMO Postdoctoral Fellowship scheme.


S V Andreev

Formation of exciton rings and localized bright spots in coupled semiconductor quantum wells

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

I. INTRODUCTION

The observation of the external ring [1,2] and localized bright spots (LBS) [1,3,4] in PL patterns of indirect excitons in biased semiconductor QW's has attracted much attention both on the experimental [5][6][7][8] and the theoretical [9][10][11] sides during the past 14 years. All these features were shown to originate from the reaction-diffusion dynamics of electrons and holes. The electrons are injected in the nearest to the positive lead QW layer by the current filaments due to the applied gate voltage. In the absence of photoexcitation, these electrons fill uniformly the layer plane. A focused laser is then used to excite electron-hole pairs in the surrounding barriers. Holes are captured efficiently by the QW layer close to the negative lead and form a lake of a positive charge around the excitation spot [START_REF]To be more precise, the lake of a positive charge is formed by an[END_REF]. Electrons from the current filaments going through the lake bind with the holes to form excitonic ensembles seen as LBS rings in the PL pattern. The interface between the hole lake and the outer unperturbed electron sea is seen as the external PL ring.

The external and LBS rings are sources of cold exciton gases. Spontaneous onset of extended spatial coherence [13,14], polarization textures [16], and macroscopic ordering [1] in the PL from these rings have been observed. Theoretical interpretation of these phenomena goes beyond the classical reaction-diffusion model and suggests emergence of novel quantum phases of excitons, in which the interplay between the dipolar interaction and spin degree of freedom can be studied at the macroscopic level [15][16][17][18][19][20].

Until now it has been assumed that, after an exciton has been created, it propagates out from the charge interface under combined action of diffusion and repulsive electrostatic interaction with other excitons. Careful analysis of the available experimental data indicates, however, that the assumption of free propagation of a single exciton in the radial direction should be revised. As can be inferred from the exciton PL patterns, the clouds squeeze (reduce the width) with lowering of temperature [1,4]. This experimental fact raises doubts on the free radial expansion picture, notably at low temperatures, where the exciton motion was argued to become ballistic * serguei.andreev@u-psud.fr [16,17,19]. Indeed, in contrast to the width of a cloud, the exciton coherence length increases when the temperature is lowered [14].

Here, we argue that in-plane translational motion of indirect excitons generated at the rings is confined in the radial direction. The confinement originates from electrostatic interaction of the exciton dipole moment with in-plane electric field induced by the macroscopic charge separation. The field tilts the dipoles, thus polarizing excitons in the structure plane. Polarized excitons seek for the region where the in-plane field is higher, i.e., the region of the charge interface. This way, we show that the external and LBS rings represent trapped exciton clouds.

Our argument provides a natural explanation to a whole series of experimental facts. First, it explains the aforementioned squeezing of the clouds when the temperature is reduced. Secondly, it allows us to reproduce the excitation power versus temperature (PT) phase diagram of the external ring reported in Ref. [1] (and, simultaneously, in Ref. [2]). Furthermore, it provides understanding to the "Mexican hat" spatial profile of the exciton blueshift measured in the vicinity of an LBS [3]. In fact, this observation had initially prompted a phenomenological interpretation of LBS's as trapped exciton clouds [3,4]. The bump in the central part of the energy profile has been explained as due to stimulated flux of excitons towards the center of the trap. This hypothesis is further supported by the experimentally observed universality in thermodynamic behavior of cold exciton gases: different LBS's containing strongly different number of excitons, develop the extended coherence and polarization textures all at the same critical temperature. This peculiar phenomenon was shown to be the distinct feature of two-dimensional Bose-Einstein condensation in an ensemble of harmonically trapped gases maintained at the same chemical potential [21,22].

The paper is organized as follows. In Sec. II, we consider interaction of a dipolar exciton with an in-plane field and obtain the formula for the exciton potential energy due to this interaction. To calculate the spatial distribution of the field (exciton potential energy), one needs to know distributions of electron and hole densities in charged regions. These are introduced in Sec. III following Ref. [9]. In Sec. IV, we calculate the electric field in the vicinity of the electron-hole interface. Section V is devoted to discussions and comparison FIG. 1. The macroscipic charge separation induces an in-plane electric field which hybridizes 1s and 2p states of an indirect exciton. As a consequence, the excitons become polarized along the field. Classically, one can say that the field tilts the exciton dipole moment. Polarized excitons will seek for the regions where the induced electric field is stronger and, therefore, will become localized at the ringshaped boundary.

of our results with the available experimental data. We conclude this section by showing that our model of an LBS provides an adequate basis for theoretical interpretation of the coherence [14] and polarization [16] textures as well.

II. TRAPPING MECHANISM

Since the first experiments on cold exciton gases in QW's several trapping configurations have been proposed and realized. These include strain-induced traps [23][24][25][26], traps created by laser-induced interdiffusion [27], magnetic traps [28], laser-induced traps [29], and a large variety of proposals which rely on the electrostatic interaction of the exciton dipole moment with collinear electric field E z (z is the structure growth direction) [30][31][32][33]. In the latter case, the interaction energy is given by ε(x,y) = -edE z (x,y), showing that the excitons will seek for the regions in the (x,y) plane where the electric field is stronger.

In our case, the external transverse electric field applied to a bilayer QW structure is roughly uniform in the structure plane, so that no artificial potential landscapes for excitons is created. An indirect exciton generated at the ring has been assumed to propagate out from the source as a free particle (if one neglects the exciton-exciton interaction). We are going to show that at the carrier densities achieved in this kind of experiment the radial motion of excitons is confined, i.e., excitons are localized at the ring. The microscopic mechanism of this confinement is detailed below.

As we have already mentioned, the exciton ring appears at the boundary between the internal hole-rich region and the external electron-rich region. Thus one can expect the existence of in-plane electric field E r (r,θ ) in the vicinity of the ring oriented everywhere outwards the center, along the radii. In the ground state an exciton does not interact with this field, since the relative two-dimensional motion of the electron-hole pair is characterized by a symmetric wave function. However, the interaction is already possible in the first order of the perturbation theory due to admixing of the 2p-exciton state. Classically, the electric field "stretches" the exciton, tilting its dipole moment (Fig. 1). As in the case of the artificially created potential profiles discussed above, interaction of an in-plane component of the exciton dipole moment with the built-in electric field at the boundary results in appearance of an electrostatic trap for the exciton in the radial direction, which localizes excitons at the ring.

The corresponding interaction energy can be estimated following the general rules of quantum mechanics. For that purpose, let us consider the quantum-mechanical problem of the relative in-plane motion of an electron and a hole confined to different QW's (or to diffrent edges of a wide single QW) and binded into an indirect exciton. The relative e-h motion is described by the Hamiltonian

H X 0 = - 2 2μ ∂ 2 ∂ρ 2 + 1 ρ ∂ ∂ρ + 1 ρ 2 ∂ 2 ∂ϕ 2 - e 2 0 ρ
, where ρ = (x,y) and we have let z e = z h for simplicity. This is nothing but the Hamiltonian of a two-dimensional Hydrogen atom. Its eigenfunctions can be found in analytical form [34]. Here we will be interested in 1s and 2p states. The corresponding wave functions read as

φ 1s X (ρ) = 2 π (2a B ) 2 e -ρ/2a B (1)
for 1s state and

φ 2p↑ X (ρ) = 2 9 1 3π (2a B ) 2 ρ 2a B e -ρ/6a B (cos ϕ + i sin ϕ), φ 2p↓ X (ρ) = 2 9 1 3π (2a B ) 2 ρ 2a B e -ρ/6a B (cos ϕ -i sin ϕ), φ 2p X (ρ) = 2 9 1 6π (2a B ) 2 1 - 2 3 ρ 2a B e -ρ/6a B (2)
for 2p states. The latter, in the absence of magnetic field, form a degenerate triplet at the energy ε 2p . This energy can be approximately estimated as the energy of 2s state reported in Ref. [35].

Treating the spontaneously induced electric field E r as a perturbation one can write (in the first order)

φ 1sp X (ρ) = φ 1s X (ρ) + 2p 1s| V |2p ε 2p -ε 1s φ 2p X (ρ), (3)
where the summation is over the states (2) and the dipolar interaction operator V is given by

V = -e E r • ρ = -eE r ρ cos ϕ.
From Eq. ( 3) one can see that due to the admixing of 2p states the exciton becomes polarized in the direction of the field E r in the structure plane. Therefore it can now interact with this field and the interaction energy is given by

ε(r) = 1sp| V |1sp = 2p | 1s| V |2p | 2 ε 2p -ε 1s .
In general, however, the in-plane electric field can be strong enough to transform the 1s indirect exciton into a strongly mixed hybrid state. The potential energy of such sp hybridized exciton can be found by diagonilizing a 3 × 3 Hamiltonian,

Ĥsp = ⎛ ⎝ s v v v p 0 v 0 p ⎞ ⎠ ,
where we have denoted s = ε 1s , p = ε 2p and v = 1s| V |2p ↑ = 1s| V |2p ↓ = eE r a B /2 √ 6. One obtains the following set of eigenvalues:

ε = p,
which corresponds to the p-shell oriented perpendicularly to E r and

ε(r) = s + p ± (s -p) 2 + 8v 2 (r) 2 for the sp hybrids oriented along E r .
In what follows, we will be interested in the dependence of the ground-state energy,

ε 0 (r) = δ -δ 2 + 8v 2 (r) 2 , (4)
(we have introduced δ = ps) of the polarized indirect exciton on the distance from the center of the ring r. Our main goal is thus to calculate the radial electric field E r as a function r.

III. RADIAL DISTRIBUTION OF ELECTRON AND HOLE DENSITIES

To calculate E r , one needs to know the electron and the hole density distributions, n e and n h . These can be obtained from the reaction-diffusion model supplemented with the drift term due to the induced electric field. Here we employ the simplest model proposed in Ref. [9], neglecting the interaction with the electric field and allowing the analytic expressions for n e and n h . In this model, one neglects the escape of photogenerated holes from the topmost quantum well and assumes that n e and n h are strictly zero inside and outside the ring, respectively. The latter approximation is reasonable for the system studied in Ref. [1], since no significant PL signal is seen in the inner region between the ring and the photoexcitation spot. Kinetic equations for steady state then take the form

D h ∇ 2 n h (r) + P x δ(r) = 0 r R, ( 5a
)
D e ∇ 2 n e (r) + G - n e (r) τ e = 0 r > R. ( 5b
)
Here, D e,h are the electron (hole) diffusion constants, G is a spatially uniform source for electrons, P x is the amount of holes injected into the QW per second, 1/τ e is the electron escape rate due to tunneling. The linear equations ( 5) can be solved analytically. The relevant length scale of the problem is fixed by the electron depletion length l = √ D e τ e . In the limit R l, one finds

R = P x 2πGl ,
i.e., the ring radius depends linearly on the excitation power.

For the system under consideration, such behavior of the ring radius has been observed experimentally [15]. This justifies a posteriori the assumption R l. In the same limit, the expressions for n e and n h take the form

n h (x) = p ln(x -1 ) 0 < x 1, ( 6a
)

n e (x) = n(1 -x -1/2 e -ζ (x-1) ) x > 1, (6b)
where we have introduced p = P x /2πD h , n = Gτ e , x ≡ r/R, and ζ = R/ l.

IV. CALCULATION OF THE ELECTRIC FIELD

The knowledge of the electron and hole density profiles allows one to calculate radial distribution of the electrostatic field E r . The further simplification of the model, which one can make here, is to neglect the curvature of the interface. The numerical study shows that this is indeed correct at least for large enough ring radii (compared with the width of the ring) and when one is interested in the field distribution in the vicinity of the interface [the latter corresponds to x = 1 in ( 6)].

In this simplified geometry, the total electric field at the point y ≡ r/R can be represented as the superposition of electric fields from a large number of elementary filaments parallel to the interface:

E r (y) = e 2π 0 1 n h (x)dx y -x - 1 n e (x)dx y -x . ( 7
)
The calculation of integrals in Eq. ( 7) is not trivial. The integrals have logarithmic divergencies at the point we are interested in and should be regularized in the sense of the principal value. The resulting set of equations, suitable for numerical calculations, has the form E r (y) = e 2π 0 |y-1| 0 ±n e,h (y + x) ∓ n e,h (yx)

x dx

+ x 0 |y-1| n h (y -x) + n e (y + x) x dx |y -1| x 0 , E r (y) = e 2π 0 x 0 0 ±n e,h (x + y) ∓ n e,h (x -y) x dx |y -1| > x 0 , ( 8
)
where the sign +/as well as the subscript e/h states for y > 1 or y 1, respectively. Finally, one should bear in mind, that the CQW's are surrounded by conducting contact layers. The contacts will contain electrostatic images of the electron and the hole lakes, located on the distances 2kh from the QW's, where h is the barrier width (we neglect the space between the QW's) and k = 1,2, . . . is an integer. The contribution from the images can be taken into account by replacing

n e,h -→ n e,h 1 + 2x ∞ k=1 (-1) k x 2 + k 2 ξ 2 (9)
in the integrals (8), where ξ ≡ 2h/R. FIG. 2. Built-in electrostatic trap for the radial in-plane motion of indirect excitons at different laser excitation powers. By increasing the excitation power P one injects more holes in the upper QW and, provided that the gate voltage V g is fixed, makes the ring expanding. Assuming that the parameter p depends linearly on the laser power, for the values of parameters chosen one obtains the linear growth of the ring radius R with P . At the same time, the depth of the trap increases as is shown in the inset.

V. RESULTS AND DISCUSSION

A. External ring

We first discuss trapping of excitons at the external ring. The exciton potential energy profiles calculated using Eqs. ( 4) and ( 8) are presented in Fig. 2. We used the following set of parameters: n = 6 × 10 10 cm -2 , = 12.9, a B = 10 nm, h = 200 nm, l = 10 μm, and δ = 2 meV. The parameter p which governs the radial distribution of holes according to (6) took the values in the range 5.6-11.2 × 10 10 cm -2 , which corresponds to the increasing laser power P . The fixation of the parameter n corresponds to the fixed gate voltage V g .

Consistently with the experimental results presented in Refs. [2,15], we assumed the ring radius R being proportional to p. For the given value of p the upper bound x 0 in the integrals (6) had been increased until the shape, the effective width and the height of the trap saturated. This criterion was already achieved at x 0 ∼ 0.2, that justifies the simplied geometry we have used. Further increase of x 0 leads to the shift of the whole picture towards higher energies. The numerical procedure described above qualitatively corresponds to the experimental configuration of Ref. [5] where the PT phase diagram of the external ring was obtained. Remarkably, the depth of the electrostatic trap increases when increasing P as one can see in the inset of Fig. 2. This observation is in agreement with the excitation power versus the temperature (PT) phase diagram of the external ring reported in Refs. [1,2]. Indeed, the depth of the trap should roughly correspond to the temperature at which the external ring washes out: as soon as the thermal kinetic energy of the excitons exceeds the potential barrier height, the excitons become delocalized.

We point out that even in this simplified model one has a large set of parameters. As expected, the depth of the trap is strongly sensitive to the electron and hole densities. The latter can be estimated from the laser excitation density (see Ref. [START_REF]To be more precise, the lake of a positive charge is formed by an[END_REF]). The background electron density n = Gτ e can in principle be determined by measuring the electron current through the sample in the absence of photoexcitation [13], provided that the electron escape time from the QW due to tunneling is known in advance [7]. To the best of our knowledge, neither the electron current nor the tunneling time have not been measured yet. Therefore n was an adjustable parameter of the problem.

B. Linear polarization and coherence textures around an LBS

An LBS is essentially a ring of a small radius where the electron and the hole density distributions are inverted. As the ring shrinks the excitons form a dense cloud in the center which is seen as a bright spot in the PL pattern. At low temperatures, extended spontaneous coherence and polarization textures have been observed around an LBS. The motion of the excitons forming the coherent state is governed by an effective potential produced by the repulsive interaction with the dense bright core from the internal side and by the electrostatic confinement potential in the outer region. This assumption is consistent with the "mexican-hat" profile of the exciton energy observed in Ref. [3]: the bump in the central part of the hat roughly corresponds to the maximum of the PL intensity. Below we show that the linear polarization and forklike defects in the PL coherence pattern around an LBS can be interpreted as due to spin-orbit coupled BEC of excitons at the ring-shaped trap.

An exciton in GaAs-based quantum wells considered here is composed of an electron with the spin ±1/2 and a heavy hole with the spin ±3/2. Depending on the mutual orientation of the e and h spins, the spin of an exciton may take four possible values:

|X = ⎛ ⎜ ⎝ e +1/2 h +3/2 e +1/2 h -3/2 e -1/2 h +3/2 e -1/2 h -3/2 ⎞ ⎟ ⎠ = ⎛ ⎜ ⎝ X +2 X -1 X +1 X -2 ⎞ ⎟ ⎠, (10)
where e ±1/2 and h ±3/2 stem for the electron and the hole spin components, respectively. As a consequence of the orbital momentum conservation rule, only X -1 and X +1 components are optically active and contribute to the left (σ -) and right (σ + ) circularly polarized emission of the excitons. The X +2 and X -2 components are dark. Earlier theoretical works on spinor condensates (see, for example, Ref. [36]) exploited mainly the idea borrowed from the physics of ferromagnetism: short-range exchange interaction can favor a phase with broken rotational symmetry. The orientation and position of the domain walls in this case are defined by fluctuations of external potential. However, this is not the case for the condensate of indirect excitons. The observed polarization textures are pinned to the crystallographic axes and their orientation is the same for each bright spot.

As was first noticed by A. Kavokin [START_REF]Private discussion at the International School on Nanophotonics and Photovoltaics in Tsakhkadzor (Armenia)[END_REF], this experimental fact suggests that the exciton spin texture is due to spin-orbit interaction (SOI). Translational motion of an electron and a hole in the electrostatic field of ion cores results in the spin-dependent splitting of the corresponding subbands. In the absence of structural inversion asymmetry (SIA), the FIG. 3. Schematic illustration of the exciton condensate localized at the ring-shaped channel around an LBS. Color shows the regions with positive (orange) and negative (blue) degrees of linear polarization in a qualitative agreement with the experiment [16]. The emitted light is polarized everywhere along k according to the result (16).

Hamiltonian of a free exciton takes the form [START_REF]Noteworthy, the Hamiltonian (11[END_REF] Ĥ

X BIA = 2 k 2 2m + ⎛ ⎜ ⎜ ⎝ 0 β h ke -iφ β e ke iφ 0 β h ke iφ 0 0 β e ke iφ β e ke -iφ 0 0 β h ke -iφ 0 β e ke -iφ β h ke iφ 0 ⎞ ⎟ ⎟ ⎠ , ( 11
)
where k is the absolute value of the exciton wave vector k, and φ is the angle between k and the x axis. The off-diagonal part of ( 11) can be obtained as a tensor sum Ĥ e BIA ⊕ Ĥ h BIA of an electron [START_REF] Dyakonov | [END_REF], Ĥ e BIA = β e σ x k e

xσ y k e y , [START_REF]To be more precise, the lake of a positive charge is formed by an[END_REF] and a hole [40,41],

Ĥ h BIA = β h σ x k h x + σ y k h y , (13)
|X φ = 1 2 e ik 0 r ⎛ ⎜ ⎝ 1 -e iφ -e -iφ 1 ⎞ ⎟ ⎠ (14)
with

k 0 = m 2 (β e + β h ). ( 15
)
In our case the local orientation of k is imposed by the ring-shaped confinement, as detailed above and shown schematically in Fig. 3. The macroscopic occupation of the single-particle state (14)

The results ( 16) and (19) show that the emitted light is polarized everywhere along the condensate velocity v 0 = m k 0 . This is schematically illustrated in Fig. 3. The linear polarization texture (19) corresponds very well to the textures observed around an LBS [16,42]. This way, according to our hypothesis, an LBS can be regarded as a (quantized) vortex of a dilute exciton BEC pinned to a dense core (the origin of the core remains to be understood). Numerical simulations of the shift-interferometry measurement shows that a quantized vortex should be characterized by a pair of opposite forks [14].

VI. CONCLUSIONS

To conclude, we have shown that the rings of dipolar excitons observed in coupled GaAs quantum wells at low temperatures represent trapped exciton gases. The trapping is due to the electrostatic interaction of the excitons with in-plane electric field induced at the boundary between electron-and hole-rich regions. Our results are in a good agreement with the available experimental data. We suggest that the polarization and coherence patterns observed around LBS can be due to spin-orbit coupled Bose-Einstein condensation of excitons in a ring-shaped trap.

spin

  Hamiltonians, where one should let k e = m e k/(m e + m h ) and k h = m h k/(m e + m h ) (we implicitly average out the relative motion of an electron and a hole within the exciton). The coordinate axes are chosen as x || [100] and y || [010].The ground state of the Hamiltonian(11) is the plane wave

  results in circulation of excitons around the dense core. The direction of the exciton flow (clockwise or counter-clockwise) is not important for our consideration. By evaluating the intensities I x = |x x| = 1 2 n(ρ) cos 2 φ, (16a) I y = |y y| = 1 2 n(ρ) sin 2 φ linear polarization degree ρ l ≡ I x -I y I x + I y = cos(2φ).

ACKNOWLEDGMENTS

The author acknowledges M. Petrov for numerical verification of the results and simulation of ring-shaped traps of a small radius. This work has been supported by the Government of the Russian Federation (Grant 074-U01) through ITMO Postdoctoral Fellowship scheme.


Agata Niescieruk

Bogdan Ksiezopolski

Motivation-based risk analysis process for IT Systems

Information security management is one of the most important issues to be resolved. The key element of this process is risk analysis. The standards are (ISO/IEC 27000, ISO/IEC 31000) based on the complex and time consuming process of defining vulnerabilities and threats for all organisation assets. In the article we present a new approach to analysing the risk of an attack on information systems. We focus on human factor -motivation, and show its relation to hacker profiles, as well as impacts. At the beginning we introduce a new model of motivationbased risk analysis. Then we describe case study illustrating our approach for a simple set of organisation processes.

Introduction

The ISO/IEC 27001 standard, as the part of the growing ISO/IEC 27000 family of standards, brings information security under explicit management control. Being a formal specification, ISO/IEC 27001 provides requirements for establishing, implementing, maintaining and continuously improving an Information Security Management System. ISO/IEC 27001 requires a systematic examination of information security risks, taking into account threats, vulnerabilities, and impacts, designing and implementing a coherent and comprehensive suite of information security controls to address those risks, as well as adopting an overarching management process to ensure that the information security controls continue to meet the information security needs. Information security risks can be estimated according to the different approaches which can be categorised as the quality or quantity analyses, with deterministic or probabilistic methods. However, the most common methods (FRAP, STIR, CRAMM, CORAS, STIR - [START_REF] Othmane | Using Attacker Capabilities and Motivations in Estimating Security Risk[END_REF][START_REF] Vavoulas | A Quantitative Risk Analysis Approach for Deliberate Threats[END_REF]) consist of the same three stages -risk identification, risk estimation and risk prioritization. All these methodologies have two significant limitations. The first is that while estimating the probability of an attack [START_REF] Sheyner | Automated generation and analysis of attack graphs[END_REF] the methods focus on vulnerabilities [START_REF] Gerber | Management of risk in the information age[END_REF], threats, weaknesses of resources only in one dimension, treating elements as independent. The second limitation is that motivation as a human factor is neglected. The literature on the subject contains only brief discussions of motivation as a factor influencing risk [START_REF] Rogers | Self-reported computer criminal behavior: A psychological analysis[END_REF][START_REF] Barber | Hackers Profiled -Who Are They and What Are Their Motivations?[END_REF][START_REF] Gao | Ontology-Based Model of Network and Computer Attacks for Security Assessment[END_REF][START_REF]Risk Management Guide for IT Systems[END_REF].

The main contribution of the paper is introducing a new motivation-based risk analysis process which focuses on human motivation as the main factor which determines the decision of the attack on an IT system. Another contribution, as opposed to traditional risk analysis, which study individual assets in isolation, is that our method is multidimensional. We try to combine processes and assets involved in them.

The Model

In the article we propose a new model for motivation-based risk analysis process. Our modified model is presented in the figure 1. In the following sections all steps are described.

Step 1 -Organisation's processes

In the first step we have to focus on all processes in the organisation. They are crucial in realisation of business objectives and require many different resources. In this step we create a set of processes for which the risk will be estimated: P 1 , ..P n .

Step 2 -Assets

In the second step we have to enumerate all assets which take part in the processes defined in the first step. All assets we will denote by A. Referring to ISO 27002 we have 6 groups of our assets, so A = {I, S, H, T, R, P }, where 1. I = {I 1 , ..., I n } -information; 2. S = {S 1 , ..., S n } -software; 3. H = {H 1 , ..., H n } -hardware; 4. T = {T 1 , ..., T n } -services' tools; 5. R = {R 1 , ..., R n } -non-material assets -reputation; 6. HR = {HR 1 , ..., HR n } -human resources.

For each type of processes n the number of assets can be different. Now for chosen processes we should identify their assets. We will ascribe assets for process P j as A j . All assets influence the performance and the development of a company. Each single asset is involved in at least one process, each process uses at least one asset.

Step 3 -Impact

Undisturbed work of each process is crucial to an organisation and has certain influence. We would like to introduce process impacts as a method of distinguishing between processes. We expect these impacts belong to at least one of these groups:

finance (higher costs, lower profits, shares depreciation) [f in]; reputation (violation of trust, damage to brand reputation) [rep]; organisation (redundancies, lowered morale) [org]; law (legal obligations, leakage of personal data) [law]; sense of security (loss of control, awareness of a threat) [sec].

Therefore each single asset a is represented as a vector of impacts:

imp a = [f in a , rep a , org a , law a , sec a ]
where individual elements correspond to the list above and each of them has values from [0..1] with 0 meaning none and 1 meaning the highest possible impact. Similarly for each process P j , we have a vector of impacts:

imp Pj = [f in Pj , rep Pj , org Pj , law Pj , sec Pj ]
Now we can calculate total impacts for each process and all its assets. Having process P j and a set of all its assets A j , the total impacts will be:

imp Pj ,Aj = [f in Pj ,Aj , rep Pj ,Aj , org Pj ,Aj , law Pj ,Aj , sec Pj ,Aj ]
where each element of this vector is calculated as follows:

x Pj ,Aj = x Pj • [max a∈Aj + (1 -max a∈Aj ) • (median Aj \max a∈A j )],
where: x ∈ {f in, rep, org, law, sec}. The reason why we take the maximum and add it to the median multiplied by 1 -maximum is the fact that we want to have total impacts as numbers from [0..1].

Step 4 -Motivation

Different impacts for the assets determine certain types of motivation. These categories of motivation [START_REF] Rogers | A two-dimensional circumplex approach to the development of a hacker taxonomy[END_REF][START_REF] Barber | Hackers Profiled -Who Are They and What Are Their Motivations?[END_REF] that are related to attack on IT system could be one or combination of more of these listed below: The impacts and the motivations are strongly related. In [START_REF]Risk Management Guide for IT Systems[END_REF] they are parts of sequential steps. However, we did not find this relation directly described in the literature. That is why we introduce 5 levels to describe it: 1 -very high, 0.75high, 0.5 -medium, 0.3 -low, 0.1 -very low. For each type of motivation various impacts have various meanings. Using levels above, the relation is illustrated by matrix:

-finance [f inm]; -curiosity [cur]; -experience/
mot imp =         f inm f in f inm rep f inm org f inm law f inm sec cur f
        = =         1
       
Each element of this matrix bind a certain type of motivation with a certain type of impact, i.e. for whichever x y , x is a kind of motivation, y -type of an impact. E.g. f am org is about fame motivation and organisation impact. To obtain exact values, the proper motivations for our process are:

mot Pj = [f inm Pj , cur Pj , exp Pj , rev Pj , f am Pj , soc Pj ]
where each element of this vector is calculated in a similar way, e.g.:

f inm Pj = max(f in Pj ,Aj • f inm f in , rep Pj ,Aj • f inm rep , org Pj ,Aj • f inm org , law Pj ,Aj • f inm law , sec Pj ,Aj • f inm sec )

Step 5 -Hacker profile

The next component of our model is a hacker profile. It is determined by his or her motivation [START_REF] Grunske | Quantitative risk-based security prediction for componentbased systems with explicity modeled attack profiles[END_REF]. According to article [START_REF] Rogers | A two-dimensional circumplex approach to the development of a hacker taxonomy[END_REF] we define the taxonomy of hackers. There are nine primary categories of hackers: Novices We have to link these hacker profiles with motivation. Referring to the categories of motivation above and to the hacker profiles [START_REF] Rogers | A two-dimensional circumplex approach to the development of a hacker taxonomy[END_REF] we define the relationship between them which are presented in the tab. 1. In this step, having calculated values for all types of motivation for a chosen process j we will be able to determine hacker profile. Basing on [START_REF] Rogers | A two-dimensional circumplex approach to the development of a hacker taxonomy[END_REF] and [START_REF] Barber | Hackers Profiled -Who Are They and What Are Their Motivations?[END_REF] we propose matrix which will be used to represent levels of motivation for all types of hackers.

mot hac =         0
0.5 0.3 0.7 0 0 1 0.5 0 0 0 0 0 0.5 0.5 0 0 0 0.5 0 0 0 0 0.5 0 0 0 0 0 0.7 0.3 0.5 0 0 0 0 0 0.5 0 0 0 0 0 0 0.5 0.5 0 0 0 0 0 0 0.5 0.5

       
Each column corresponds to a hacker profile (first to N o, second to CP , etc.) and each row is for a different type of motivation (f inm, cur, exp, rev, f am, soc). E.g. mot hac [1, 1] = f inm N o = 0 is finance motivation for Novices, mot hac [START_REF] Grunske | Quantitative risk-based security prediction for componentbased systems with explicity modeled attack profiles[END_REF][START_REF] Grunske | Quantitative risk-based security prediction for componentbased systems with explicity modeled attack profiles[END_REF] = rev P T = 0.3 is revenge for Petty Thieves. Now we can multiply a vector of motivations for a process j (mot Pj ) by this matrix of hackers (mot hac ). As a result we obtain vector which has 9 elements, and each one corresponds to one hacker profile:

mot Pj ,hac = mot Pj • mot hac = = [N o Pj , CP Pj , In Pj , P T Pj , V W Pj , OG Pj , P C Pj , IW Pj , P A Pj ]

Step 6 -Hackers' skills

We have our processes, assets, impacts, motivation and hacker profiles. However, there is one more crucial factor -hackers' skills. Each group of hackers is at a certain level of knowledge and we need to include that factor to our analysis.

According to [START_REF] Rogers | A two-dimensional circumplex approach to the development of a hacker taxonomy[END_REF] the least skilled group are N o, the next are CP and P T , then In, V W , and the most skilled are OG, P C, IW and P A. We define the skills vector as: All elements of this result vector are from [0..1]. For a number less than 0.1 we will talk about a small likelihood of an attack, for numbers from [0.1..0.5] the likelihood will be at a medium level. Finally, values greater than 0.5 will mean the likelihood is high. Our method has just showed whether the process is critical and could be interesting for a hacker of a certain type -the likelihood of an attack. The question whether this attack will be successful or not could not be answered here as we did not analyse safeguards.

skl hac = [skl N o ,

Step 8 -Safeguards

In the next step the safeguards for all analysed processes must be defined. We suggest using a scale: 1 -very high, 0.75 -high, 0.5 -medium, 0.25 -low, 0 -very low. That means, if there is a level 1, the safeguards are strong, so the assets are properly protected. At the same time, level 0 means that the assets are practically unsecured. We will denote the safeguard level as SF , and it is a number used for all assets taking part in the specific process. However the analysis could be extended to a version where we identify separate safeguard levels for each asset.

Step 9 -Risk

Finally, the risk of specific processes can be calculated -Risk Pj (Risk for the process j). The risk is estimated by the following formula.

Risk Pj = (1 -SF 2 ) Pj • att Pj
In our model the risk can be a value from 0..1 where 0 means no risk and 1 means that it is highly probable that potential attack will be successful. That is why, we multiply the likelihood by 1 -SF 2 . Results greater or equal 0.5 show a very high risk of a successful attack.

The Case Study

In the next section we demonstrate our new method for motivation-based risk analysis. Due to the space limitations we are prepare an analysis of a simple example where each component of our model will be described and final risk of an attack will be calculated.

Step 1 -Processes

In our example we define a small online store. Let P 1 , P 2 , P 3 be our crucial processes in this chosen company. P 1 is registration of a new customer (standard form on the website and then an authentication mail sent to an address given), P 2 is a payment for an order (with finished shopping going to a bank webpage), P 3 is viewing archive orders (list of an user's previous orders with prices and products bought). As a result of this step we have a list of defined processes.

Step 2 -Assets

According to our model, now we have to present assets. There are many of them in this company, but those that are relevant to our processes are:

-I 1 (databases with personal data, orders, and products data); -S 1 (web server), S 2 (mail authentication app.), S 3 (api to bank payments); -H 1 (server), H 2 (router); -T 1 (air conditioning), T 2 (power).

-R 1 (good reputation); -HR 1 (administrator).

In process P 1 we have all assets except S 3 , in P 2 all assets except S 2 , in P 3 all assets except S 2 and S 3 . Therefore:

A 1 = {I 1 , S I , S 2 , H 1 , H 2 , T 1 , T 2 , R 1 , HR 1 } A 2 = {I 1 , S I , S 3 , H 1 , H 2 , T 1 , T 2 , R 1 , HR 1 } A 3 = {I 1 , S I , H 1 , H 2 , T 1 , T 2 , R 1 , HR 1 }

3.3

Step 3 -Impact

Having processes and assets, we should define impacts for all of them. As it was presented in section 2.3, below we combine impacts with assets: Similarly, impacts for processes are:

imp I1 = [
imp P1 = [0.

Step 4 -Motivation

The following step is to calculate vectors of motivation for each process. We do that by taking the maximum of the products from multiplying elements of mot imp -matrix with 1, 0.75, 0. We may conclude that this process is alluring for Professional Criminals, which does not seem to be astonishing. What is also worth mentioning is that P 3 is safe, only the last value is for medium likelihood, but it is low.

Step 8 -Safeguards

The safeguards are in our method for all assets, so let our company be in the middle of a scale with SF = 0.5. That means there is some security but it could be not sufficient enough.

Step 9 -Risk

To obtain risk, we now calculate the likelihood of an attack by 1 -SF 2 = 0.75. It gives us: During the analysis of results one can see that the risk vector for the second process has several values greater than 0.5. It means that there is a high probability of a successful attack on this process and a risk reduction method should be applied.

Risk P1 = [0.
The risks analysis for IT systems is one of the major activities in the information security management. In the article we present motivation-based risk analysis which estimates the risk based on the attack motivation as the human factor. The presented approach is less complicated that the standard one which based on the vulnerabilities and threats analysis. Another feature of the presented approach is that the new method for risk analysis is multidimensional. Owing to that, the calculated risks of the a given process will take into account all assets taking part in the analysed process. In the article we present a case study for our methodology where risks of simple processes were calculated. The proposed risk analysis method can be used as part of Quality of Protection models [START_REF] Ksiezopolski | QoP-ML: Quality of Protection modelling language for cryptographic protocols[END_REF][START_REF] Ksiezopolski | On the efficiency modelling of cryptographic protocols by means of the Quality of Protection Modelling Language (QoP-ML)[END_REF] which introduce adaptable security [START_REF] Ksiezopolski | Adaptable security mechanism for the dynamic environments[END_REF] for IT Systems.

Fig. 1 .

 1 Fig. 1. The model of motivation-based risk analysis process

  0.5 0.3 0.5 0.3 0.3 0.75 0.5 0.1 0.75 0.1 0.5 0.75 0.3 0.75 0.75 0.75 0.1 0.5 0.3 0.5 0.75 0.5 0.5 0.5 0.5 1 0.5 0.3 0.3

  [N o], Cyber-punks [CP ], Internals [In], Petty Thieves [P T ], Virus Writers [V W ], Old Guard hackers [OG], Professional Criminals [P C], Information Warriors [IW ] and Political Activists [P A].

  0.6, 0.5, 0.4, 0.4, 0.5], imp S1 = [0.3, 0.8, 0.6, 0.5, 0.5], imp S2 = [0.1, 0.5, 0.7, 0.7, 0.4], imp S3 = [1, 0.6, 0.5, 0.8, 1], imp H1 = [0.6, 0.5, 0.7, 0.4, 0.6], imp H2 = [0.5, 0.5, 0.4, 0.3, 1], imp T1 = [0.6, 0.4, 0.75, 0.1, 0.4], imp T2 = [0.6, 0.75, 0.6, 0.3, 0.4], imp R1 = [0.75, 1, 0.4, 0.4, 0.4], imp HR1 = [0.5, 0.4, 0.75, 0.5, 0.75].

  knowledge [exp]; revenge/anger [rev]; fame/notoriety [f am]; social -membership of group (e.g. radical beliefs, political activists) or a desire to impress a group [soc].

  in cur rep cur org cur law cur sec exp f in exp rep exp org exp law exp sec rev f in rev rep rev org rev law rev sec f am f in f am rep f am org f am law f am sec soc f in soc rep soc org soc law soc sec

Table 1 .

 1 The combination of hacker profile with motivation

		Motivation
	Hacker profile f inm cur exp rev f am soc
	N o	no no yes no no yes
	CP	yes no no no yes no
	In	yes no no yes no no
	P T	yes no no yes no no
	V W	no yes no yes no no
	OG	no yes yes no no no
	P C	yes no no no no no
	IW	yes no no no no yes
	P A	no no no no yes yes

  skl CP , skl In , skl P T , skl V W , skl OG , skl P C , skl IW , skl P A ] =

	= [0.2, 04, 0.6, 0.4, 0.8, 1, 1, 1, 1]
	2.7 Step 7 -Likelihood of attack
	Having a vector of hacker profiles and a vector of their skills we could now
	estimate which groups of hackers are highly probable to attack. We estimate it
	by the following multiplication.

att Pj = mot Pj ,hac • hac = = [att N o,Pj , att

CP,Pj , att In,Pj , att P T,Pj , att V W,Pj , att OG,Pj , att P C,Pj , att IW,Pj , att P A,Pj ]

  5, 0.3 and 0.1 by already calculated elements of the impact vector, for each process imp Pi,Ai . Now we can multiply motivation vectors by hacker profile matrix (mot hac ) and we obtain three vectors that correspond to hacker profiles.

	3.6 Step 6 -Hackers skills
	As we defined before, the skills vector is as follows:
	skl hac = [0.2, 04, 0.6, 0.4, 0.8, 1, 1, 1, 1],
	where consecutive values correspond to N o, CP , In, P T , V W , OG, P C, IW ,
	P A.
	3.7 Step 7 -Likelihood of attack
	Finally we will calculate the likelihood of an attack -multiplying mot Pj ,hac by
	skl hac :
	att P1 = [0.14, 0.208, 0.33, 0.196, 0.48, 0.6, 0.44, 0.62, 0.7]
	att P2 = [0.138, 0.304, 0.492, 0.368, 0.568, 0.68, 1, 0.85, 0.61]
	att P3 = [0.098, 0.152, 0.24, 0.136, 0.36, 0.41, 0.3, 0.45, 0.52]
	mot P1 = [0.44375, 0.6, 0.6075, 0.6, 0.6, 0.8]
	mot P2 = [1, 0.675, 0.675, 0.75, 0.525, 0.7]
	mot P3 = [0.3, 0.45, 0.375, 0.45, 0.45, 0.6]
	3.5 Step 5 -Hacker profile
	mot P1,hac = [0.7, 0.52, 0.55, 0.49, 0.6, 0.6, 0.44, 0.62, 0.7]
	mot P2,hac = [0.69, 0.76, 0.82, 0.92, 0.71, 0.68, 1, 0.85, 0.61]
	mot P3,hac = [0.49, 0.38, 0.40, 0.34, 0.45, 0.41, 0.30, 0.45, 0.52]

All values are in range [0..1]. However the highest value is for process P 2 -we see that att P C,P2 = 1.

  105, 0.156, 0.2475, 0.147, 0.36, 0.45, 0.33, 0.465, 0.525] Risk P2 = [0.1035, 0.228, 0.369, 0.276, 0.426, 0.51, 0.75, 0.6375, 0.4575]

	Risk P3 = [0.0735, 0.114, 0.18, 0.102, 0.27, 0.3075, 0.225, 0.3375, 0.39]

Acknowledgements

This work is supported by Polish National Science Centre grant 2012/05/B/ST6/03364


Kurt Stenzel

Kuzman Katkalov

Marian Borek

Wolfgang Reif

Formalizing Information Flow Control in a Model-Driven Approach

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

Introduction

Smartphones are useful digital assistants that simplify our life. However, they store larger and larger amounts of private data. This data can and should be accessed by apps, but we would like to have control over the when and how, and what happens with the data afterwards. Information flow control (IFC) is an area of research to achieve this. IFC (e.g., [START_REF] Goguen | Security Policy and Security Models[END_REF][START_REF] Rushby | Noninterference, Transitivity, and Channel-Control Security Policies[END_REF][START_REF] Mantel | Possibilistic definitions of security -an assembly kit[END_REF]) is stronger than access control, and can be applied to a large number of systems and applications. However, it is not easy to use in practice because the theory is quite intricate, and it is easy to lose track of what information is released. IFlow is a model-driven approach designed specifically for IFC. The overall approach is fully implemented and explained in [START_REF] Katkalov | Model-driven development of information flow-secure systems with IFlow[END_REF]. This paper briefly introduces an example (Sect. 2), and then describes the advantages of the model-driven approach for the formal specification: formal proofs become easier, and specification errors are avoided (Sect. 3). Sect. 4 concludes.

An Example Application

The travel planner app is a typical distributed application consisting of a smartphone app and web services. The user enters his travel details into the app. The app connects to a travel agency web service which in turn contacts an airline web service for suitable flights. The found flights are returned via the travel agency to the app. The user selects a flight and books it with his credit card (which is stored in a credit card center app) directly at the airline. Finally the airline pays a commission to the travel agency. Fig. 1 shows this behavior as a sequence diagram. The lifelines represent the (real human) users, the apps, and the web services. Arrows denote message passing as in UML, but a domain-specific language is used that supports, e.g., assignments to provide more information. Additionally, every message is annotated with a security domain in curly brackets, e.g. {User TravelAgency, Airline}. They are used in the formal information flow framework.

Together with a class diagram (not shown), and a security policy (Fig. 2) the sequence diagram contains enough information and is precise enough to generate a formal specification as well as Java code. 1 Two information flow properties are of interest:

1. The user's credit card data does not flow to the travel agency. 2. The credit card data flows to the airline only after explicit confirmation and declassification.

As the formal framework we chose Rushby's intransitive noninterference [START_REF] Rushby | Noninterference, Transitivity, and Channel-Control Security Policies[END_REF] which is an extension of Goguen's and Meseguer's transitive noninterference [START_REF] Goguen | Security Policy and Security Models[END_REF], and specifically Rushby's access control instance of intransitive noninterference because it uses locations. On the one hand it is very natural to think about information stored in locations that flows to other locations, and on the other hand locations become fields in the generated Java code so that there is a tight connection between the formal model and the code. It works like this: Actions a modify the state with a step function step(s, a) that computes the new state. Actions have a security domain d (e.g., public or secret), and read (observe) and/or modify (alter ) the values of the locations. Security is defined w.r.t. an interference policy defined on domains and a generic function output(s, d). The interference policy describes allowed information flows, i.e., if d 1 d 2 then information may flow from d 1 to d 2 . output(s, d) defines what an attacker with security domain d can observe in a given system state. The idea is that an attacker has a given security domain and tries to obtain some secret information. More specifically, an attacker should not be able to distinguish (by observing different outputs) between a run of the system where something secret happens and another run where the secret things do not happen.

For a given IFlow UML model an instance of Rushby's framework is generated for the theorem prover KIV [START_REF]KIV homepage[END_REF][START_REF] Balser | Formal system development with KIV[END_REF] that is based on Abstract State Machines (ASMs [START_REF] Börger | Abstract State Machines-A Method for High-Level System Design and Analysis[END_REF]) and algebraic specifications.

Unwinding theorem

Rushby [START_REF] Rushby | Noninterference, Transitivity, and Channel-Control Security Policies[END_REF] proves an unwinding theorem that implies security if four unwinding conditions hold. The second condition was later weakened by van der Meyden [START_REF] Van Der Meyden | What, indeed, is intransitive noninterference?[END_REF] (we show van der Meyden's version):

-RM1: s 1 ≈ d s 2 → output(s 1 , d) = output(s 2 , d)
If two states look alike to an attacker with domain d (≈ d ) then the attacker's output is the same in both states. -RM2:

s 1 ≈ dom(a) s 2 ∧ s 1 (l) = s 2 (l) ∧ l ∈ alter(dom(a)) → step(s 1 , a)(l) = step(s 2 , a)(l)
If two states look alike to the security domain of an action a and this action is executed (with the step function) then every location that is altered by the domain and has the same value in the initial states has the same value in the two new states. (See [START_REF] Van Der Meyden | What, indeed, is intransitive noninterference?[END_REF] for a discussion.)

-RM3: step(s, a)(l) = s(l) → l ∈ alter(dom(a))
If the execution of an action modifies a location then this location is contained in the alter set for the action's domain.

-AOI: alter(d 1 ) ∩ observe(d 2 ) = ∅ → d 1 d 2
Alter/observe respects interference: if a location is altered by one domain d 1 and observed by another domain d 2 then there is an information flow from d 1 to d 2 . This must be allowed by the interference policy .

Condition RM3 basically ensures that the definition of alter is correct: If an action a modifies a location l then l must be contained in the action's domain alter set. Similarly, RM2 ensures that the definition of observe is correct. RM2 and RM3 use the step function, i.e., here every action of the system must be executed (once in the case of RM3 and twice in RM2). Hence, they are the really expensive proof obligations for larger systems. On the other hand they only depend on alter and observe (since ≈ is defined with observe), but not on output or the interference policy .

In IFlow the generation of the formal model from the UML guarantees that -RM1 is always true because of the fixed definition of output.

-RM2 is always true because observe is computed correctly from the UML model. -RM3 is always true because alter is computed correctly from the UML model.

Therefore, proving AOI AOI:

alter(d 1 ) ∩ observe(d 2 ) = ∅ → d 1 d 2
(which is trivial) already implies that a system is secure. This shows a great benefit of IFlow's model driven approach that cannot be achieved otherwise.

Automatic Declassification

Intransitive noninterference allows to model secure systems with controlled or partial information release. However, if used excessively or in an arbitrary manner the result may be a system that is secure in terms of the formal definition, but has cryptic or undesired information flows. Again, the model-driven approach can be helpful because usage of intransitive domains can be controlled. This will be explained with the help of the travel planner example. In general the interference relation may be an arbitrary relation. In IFlow some restrictions apply. Fig. 2 shows the security policy for the example. An edge denotes a (direct) interference, i.e., {User, TravelAgency, Airline} {User, Airline}. The unmarked edges are transitive (i.e., {User, TravelAgency, Airline} also interferes {User}), and the relation is automatically reflexive. Intransitive edges may only be used for declassification (also called downgrading) as shown Fig. 2: Both edges to and from a declassification domain must be intransitive and inverse to the "standard" policy, and a declassification domain must have exactly one incoming and one outgoing edge. In effect, we have a usual transitive policy with possibly some declassification domains.

When a declassification domain is used (message 13) it must be contained in its own action to avoid undesired interferences. A program counter is introduced automatically to ensure that actions/messages 12, 13, and 14 are executed in the correct order. There is another complication. Generating the formal model results in an insecure system, i.e., the only remaining unwinding condition AOI does not hold. The problem are messages 15-17 in Fig. 1: The airline receives a booking message with the credit card details (message 15) that is labeled {User, Airline}, and processes the booking (message 16) at the same security level. However, in message 17 the airline pays a commission to the travel agency that is labeled {User, TravelAgency, Airline}. If messages 15-17 are contained in one action with domain {User, Airline} the action writes to domain {User, TravelAgency, Airline} (the mailbox containing the PayCommission message) which is an illegal information flow.

However, our desired property (Credit card details never flow to the travel agency) holds because the PayCommission message does not include the credit card details. The travel agency (or, to be more precise the {User, TravelAgency, Airline} domain) does learn that a booking took place (otherwise it would not receive a commission) but not the parameters of the booking message. This may or may not be seen as a problem, but is independent from the desired property. So we want to modify the formal system so that it is secure, but would still detect that the credit card data flows to the travel agency in a faulty model.

The solution is to introduce a new declassification domain from {User, Air-line} to {User, TravelAgency, Airline} that leaks only the information that a booking took place but nothing more. Fig. 2 shows how this works. The original action is split into three actions, one that receives the booking and processes the booking (messages 15 and 16), but then sets a boolean flag to true (donePB) to indicate that it is finished. Then the declassification domain {HighLow} sets the flag doPayC to true to indicate that PayCommission can happen. The third action checks the flag and pays the commission. Both flags are reset after they are read (not shown in Fig. 2).

The action leaks only the information that donePB was true. This modified system is secure, i.e., the unwinding condition AOI holds. On the other hand, an illegal information flow will still be detected. Assume that the Pay-Commission message includes the credit card details as parameter (PayCommission(ccd decl)). Then the third action in Fig. 2 observes ccd decl (which must be a local variable), and the first action alters it (because it writes the credit card details to ccd decl). In effect {User, TravelAgency, Airline} interferes {User, Airline} directly which is forbidden by the policy. And the {HighLow} domain obviously does not leak the credit card details either. So we have exactly the desired effect.

The main point is that all this (adding a new declassification domain and splitting the original action into three) is done automatically during generation of the formal model. This guarantees that the {HighLow} domain is not used anywhere else (by generating a new unique name) and that the new action only accesses the two flags, and nothing else. A user specifying this by hand could easily make mistakes. This again shows the benefits of a model-driven approach.

Conclusion

Information flow control is a promising technique, but difficult to use in practice. IFlow is a model-driven approach that supports the development of distributed applications with guaranteed and intuitive information flow properties. The resulting UML specification is automatically transformed into a formal model based on intransitive noninterference where IF properties can be proved, and into Java code with the same IF properties. To the best of our knowledge IFlow is the only work that uses a model-driven approach for IFC (a broader comparison with related work must be omitted due to lack of space). We showed that the model-driven approach has additional benefits for IFC: proofs become simpler because functions like observe and alter can be computed, and specification errors can be avoided by the automatic introduction of declassifications with guaranteed properties.

Fig. 1 .

 1 Fig. 1. Sequence diagram for the travel planner app.

Fig. 2 .

 2 Fig. 2. Security policy and new actions.

This work is part of the IFlow project and sponsored by the Priority Programme 1496 "Reliably Secure Software Systems -RS 3 " of the Deutsche Forschungsgemeinschaft.

See our web page http://www.informatik.uni-augsburg.de/lehrstuehle/swt/ se/projects/iflow/ for the full model.


Tomoya Tanjo
email: tanjo@ism.ac.jp

Kazuhiro Minami
email: kminami@ism.ac.jp

Ken Mano
email: mano.ken@lab.ntt.co.jp

Hiroshi Maruyama

On Safety of Pseudonym-based Location Data in the Context of Constraint Satisfation Problems

Pseudonymization is a promising technique for publishing a trajectory location data set in a privacy-preserving way. However, it is not trivial to determine whether a given data set is safely publishable against an adversary with partial knowledge about users' movements. We therefore formulate this safety decision problem based on the framework of constraint satisfaction problems (CSPs) and evaluate its performance with a real location data set. We show that our approach with an existing CSP solver outperforms a polynomial-time verification algorithm, which is designed particularly for this safety problem.

Introduction

Nowadays, a location data set, which is obtained by collecting GPS data from people's mobile devices, can be used for various analytic purposes, such as realtime traffic monitoring [START_REF]Google maps[END_REF] and urban planning for future sustainable cities [START_REF] Seike | Research on the applicability of "mobile spatial statistics" for enhanced urban planning[END_REF]. However, due to the significant concern about location privacy [START_REF] Anthony | Privacy in location-aware computing environments[END_REF], the sharing of mobile users' location traces has largely been restricted to k-anonymized data sets [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF], which degrade the granularity of location data to ensure that every location contains more than k people. Such a k-anonymized data set provides little information on trajectory patterns of mobile users.

We, therefore, consider a dynamic pseudonym scheme for constructing a location data set that retains users' path information while preserving their location privacy. The basic idea is to exchange multiple users' pseudonyms randomly when they meet at the same location to eliminate the linkability of their pseudonyms before and after that exchange. Roughly speaking, a user's location privacy is preserved if we can find enough number of plausible alternate paths for that user in the data set. We believe that such a dynamic pseudonym approach is effective enough to publish large segments of the users' whole trajectory paths in a privacy-preserving way if the data set involves a large number of users whose trajectory paths intersect with each other many times.

However, it is not trivial to count the numbers of users' alternate paths under the presence of an adversary who owns partial information on users' movements (e.g., a user's home location). Such an adversary can eliminate some of the users' alternate paths that are inconsistent with his external knowledge. We thus need to address the issue of multi-path inconsistencies among multiple users and formulate this problem in the context of constraint satisfaction problems (CSPs) [START_REF] Freuder | Constraint satisfaction: An emerging paradigm[END_REF].

{(u i , l k , t k )} {(p i , l k , t k )}
A CSP is defined as a set of variables whose values must satisfy a number of constraints expressed with arithmetic and logical operators. We can declaratively define constraints on each user's pseudonym assignments considering the possibility of pseudonym exchanges at mix zones and consistency requirements with an adversary's external knowledge. Once we formulate all constraints on users' plausible trajectory paths, we can compute the number of possible alternate paths with an existing CSP solver; that is, the number of different pseudonyms that are possibly taken by the same user corresponds to the uncertainty about that user's possible destinations.

Although the time complexity of solving a CSP is exponential at the worst case, our experimental results with a real location data set show that our CSPbased approach outperforms a polynomial-time algorithm we previously developed for this problem [START_REF] Mano | Privacy-preserving publishing of pseudonym-based trajectory location data set[END_REF]. Therefore, we believe that our CSP-based approach is effective in many realistic situations.

Privacy model

We first define our system model for a psedonymized location data publishing service, and introduce a technique of dynamic pseudonym exchanges at a mix zone. Next, we establish our privacy metrics we consider in this paper. Figure 1 shows our system model. We assume that each user u i carrying a GPS-enabled mobile device periodically reports a triplet (u i , l k , t k ), which indicates that user u i is at location l k at time t k . The data publisher receives identifiable location data from multiple users, replaces their identities with pseudonyms, and provides a dataset user with a pseudonymized location data set. This data set is an output from the data publisher in Figure 1.

To replace a user's identity on a given moving path with a static pseudonym does not necessarily protect the user's location privacy. The danger is that if an adversary knowing that a target user u is at location l at time t finds a data point (p, l, t) where p is a pseudonym from the received data set, the adversary can associate p with the user's identity u. Furthermore, he also learns that all the data points with the same pseudonym p in the data set belong to the same user u; that is, the adversary can identify user u's whole trajectory path. To limit undesirable information disclosure from the above inference attack, we take an approach of changing each user's pseudonym dynamically when multiple users meet at the same location, which we call a mix zone. The basic idea is to divide a whole path of the same user into multiple segments with different pseudonyms such that the linkability of any neighboring segments is eliminated. Figure 2 shows an example of two users' exchanging their pseudonyms. Two users who own pseudonyms p i and p j , respectively, randomly exchange their pseudonyms when meeting at the intersection. Although the user who previously owned pseudonym p i actually turns right at the corner, we consider that the alternate path of the users' turning left is also possible. The other user similarly has the two possible paths after passing the intersection.

If we consider the possible paths of a single user, whenever the user meets another user, we can add a new branch as a possible segment of the path. However, such a possible path must be consistent with an adversary's external knowledge. Suppose that the adversary knows users' home location and that every user starts its path with his home location and eventually returns home. We need to eliminate some possible branches if taking that direction makes it impossible for the user to return home. Furthermore, even if one user u i is able to return home along a possible path, another user u j who exchanged her pseudonym with u i might lose a possible route to her home location. We thus need to consider possible pseudonym sequences for multiple users simultaneously. We call this requirement the multi-path consistency requirement, which is expressed as a set of constraints in a CSP in Section 3. We assume that an adversary learns a user u's location only at some mix zones; that is, the adversary observes user u where many people get together (e.g., a zebra zone on the street or a public space such as a hospital).

We consider the number of pseudonyms at a given time t on possible pseudonym sequences satisfying the multi-path consistency requirement as our location privacy metrics. Figure 3 shows such multiple pseudonym sequences of user u i . If an adversary knows u i 's location at times t 0 and t * , there is no uncertainty about a pseudonym taken by u i at both times. However, user u i is likely to have some uncertainty about his pseudonym in the middle of his trajectory after passing multiple mix zones. We now define the notion of (k, t)-pseudonym location privacy as follows.

Definition 1 ((k, t)-pseudonym location privacy) If user u i can take k or more pseudonyms at a given time t while satisfying the multi-path consistency requirement, we say that user u i satisfies (k, t)-pseudonym location privacy.

Background on constraint satisfaction problems

We give a brief overview of a constraint satisfaction problem (CSP) [START_REF] Rossi | Handbook of Constraint Programming[END_REF], which is sufficient to formulate the safety problem of location data psuedonymization in the context of CSP in Section 4. A CSP is a problem of finding a solution satisfying all the given conditions on a set of variables. We define a CPS in a declarative way such that a CSP solver finds a solution in a computationally efficient way. Although solving a CSP is known as NP-hard, existing CSP solvers, which have been widely used in many areas (e.g., [START_REF] Backofen | Bioinformatics and constraints[END_REF][START_REF] Hooker | Operations research methods in constraint programming[END_REF]), usually show good performance for practical purposes. We first define a constraint network and a CSP as follows.

Definition 2 (Constraint network) Constraint network (or Network) N is a tuple (X, D, C) where -X is a finite set of integer variables, -D is a mapping from X to a set of all possible finite subsets of integers which represents their possible values (domain), and -C is a finite set of constraints over X which represents a conjunction of constraints (∧). Each constraint consists of:

• Arithmetic operators (such as +, -)

• Arithmetic comparisons (such as =, =, ≤)

• Logical operators (such as ∧, ∨, ⇒)

• Global constraints (such as same: described later)

A global constraint is a constraint between non-fixed number of variables. For example, the same constraint takes two integer sequences X =< x 1 , x 2 , . . . , x n > and Y =< y 1 , y 2 , . . . , y n >, and it represents X is a permutation of Y .

An assignment is a mapping from X to a set of integers and a partial assignment is a mapping from a subset of X to a set of integers.

Definition 3 (Constraint Satisfaction Problem) Let N = (X, D, C) be a constraint network. A constraint satisfaction problem (CSP) is a problem to find an assignment α such that α satisfies all the constraints c ∈ C and α(x) ∈ D(x) holds for all integer variables x ∈ X.

If there exists such assignment α, it is called a solution of the CSP.

An existing CSP solver typically finds a solution in the following way. First, it picks one variable x i from X and defines a partial assignment to x i . Second, the solver removes inconsistent values from the other domains by applying a constraint propagation algorithm. If another domain for a variable x j becomes an empty set (i.e., the partial assignment cannot be extended to any solution), the solver picks a different value x i from D(x i ) and repeats the same process to extend the partial assignment to variable x j . This process is iterated until the solver finds a solution by extending the partial assignment to an assignment for all the variables.

Formalizing the CSP safety problem

We formalize the safety problem in Section 2 as the k-pseudonym decision problem and show how to solve that decision problem using a CSP solver.

The k-pseudonym decision problem

We use letters u and u 1 , u 2 , . . . for users and p and p 1 , p 2 , . . . for pseudonyms respectively. We denote N t * as a finite set of integers {1, . . . , t * }. Definition 4 (Mix Zone) Let U be a finite set of users. A mix zone m over U is a subset of U whose size is greater than one. We denote by M U all the set of mix zones over U .

We next define the mix zone function that takes a time t as an input and outputs a finite set of mix zones, which occur at time t as follows.

Definition 5 (Mix zone function) Let U be a finite set of users, t * be a positive integer, and M U be a set of all possible mix zones over U . The mix zone function f U,t * : N t * → 2 M U is a mapping from N t * to a finite subset of M U where M U is the set of all mix zones.

To formulate a k-pseudonym decision problem, we express an adversary's external knowledge and each user u's security requirements as follows.

Definition 6 (External knowledge) External knowledge is a finite set of pairs (u, t), which represents the fact that an adversary knows a user u's location at time t. Definition 7 (Security requirement) A security requirement is a tuple (u, t, k) where u ∈ U is a user and 1 ≤ t ≤ t * and k ≥ 1 are integers.

This requirement represents the fact that a user u can possibly take more than k different pseudonyms at time t. We expect that each user specifies multiple security requirements on a given pseudonymized data set.

We next define the pseudonym function which returns a pseudonym for the user u at time t. Definition 8 (Pseudonym function) Let U be a finite set of users, P = {p 1 , p 2 , . . . , p |U | } be a finite set of pseudonyms, and t * be a positive integer. The function pseudonym s : U × N t * → P maps a pair of a user u and time t to a pseudonym p ∈ P such that a user u has a pseudonym p at time t.

Finally, we define the k-pseudonym decision problem as follows.

Definition 9 (k-pseudonym decision problem) Let U be a finite set of users, t * be a positive integer, and E be an adversary's external knowledge. Let (u, t, k) be a security requirement. The k-pseudonym decision problem (f U,t * , (u, t, k), E) is a problem to decide whether there exist k candidates for s(u, t) that are consistent with the external knowledge E.

Solving k-pseudonym decision problem

We first represent the k-pseudonym decision problem as a constraint network and show how we solve it with a CSP solver in an incremental way. Figure 4 shows the function generateCSP that generates a constraint network from the given mix zone function. Quoted variables or constraints such as 's t u ' in Figure 4 show the variables or constraints in the network. Here are the overview of the function generateCSP :

-We introduce an integer variable s t u ∈ P which represents a pseudonym s(u, t) for each user u and each time t. The domain of s t u is {1, 2, . . . , i, . . . , |U |-1, |U |} where each domain value i corresponds to the pseudonym p i in the set of pseudonyms P .

-Without loss of generality, we add constraints for specifying the pseudonyms of users at time t = 0. -For each time t ∈ {1..t * }, we add the following constraints.

• s(u, t) = s(u, t -1) holds if the user u is not included in any mix zones at time t.

• same(< s(u i , t -1), s(u j , t -1), • • • >, < s(u i , t), s(u j , t), • • • >) holds if
there is a mix zone {u i , u j , . . . } at time t. case, our safety versifier outperforms our previously algorithm. This results show that the CSP solver, which has been done with various performance turning, efficiently makes a safety decision with realistic location data sets.

Related work

Using pseudonyms is a promising way to make location data unlinkable to a particular user. Beresford and Stajano [START_REF] Beresford | Location Privacy in Pervasive Computing[END_REF] were the first to discuss the idea of dynamically changing pseudonyms in a mix zone where multiple people meet, in order to prevent an adversary from linking two pseudonyms of the same user. However, they only consider the situation where an adversary has just a local view of users' movements and observes pseudonyms of entering or leaving the same mix zone. Hoh and Gruteser [START_REF] Hoh | Protecting location privacy through path confusion[END_REF] present a path perturbation algorithm that adds noises to original location data so that each user can construct alternate possible paths by exchanging his pseudonym with those of other users when they meet at the same place. However, their scheme does not consider an adversary's external knowledge that can associate each user with a particular location, as we assume in this paper.

Conclusions

In this paper, we introduce the safety definition of pseudonym-based location data and show how to represent the original safety problem in the context of constraint satisfaction problem. Our experimental results with a real location data set show that our approach with an existing CSP solver outperforms a polynomial-time verification algorithm, which is designed particularly for this safety problem.

Fig. 1 .

 1 Fig. 1. Pseudonymized location data publishing. The data publisher replaces a user's identity ui with a pseudonym pi before releasing location data to data set users.

Fig. 2 .

 2 Fig. 2. Example pseudonym exchange. Two users exchange their pseudonyms pi and pj at the intersection. The solid lines denote each user's actual path while the dotted lines denote an alternate possible path.

Fig. 3 .

 3 Fig. 3. Concept of (k, t)-pseudonym location privacy.

Fig. 5 .

 5 Fig. 5. Comparison of the processing time. CSP is the result with a CSP solver and DP is the results with our previously developed polynomial algorithm.

Acknowledgments

This research is supported by the Strategic Joint Research Grant for NTT and Research Organization of Information and Systems (ROIS) and by the Grantsin-Aid for Scientific Research C, 11013869, of Japan Society for the Promotion of Science.

// U : a finite set of users, f : mix zone function, t * : maximum time def generateCSP(U , f , t * ) X = ∅ C = ∅ // introduce integer variables foreach u in U foreach t in 0..t * X = X ∪ {'s t u '} end end // pseudonyms at time t = 0

// The same constraint should hold for each mix zone. foreach M in f (t)

an user u is not included in any mix zones, // 's t u ' is same as the pseudonym at the previous time. D,C) where D(s) = {1..|U |} for all s in X end Fig. 4. A pseudo code to generate a constraint network from the given mix zone function

In addition to the constraint network generated by the function generateCSP , we need to express extra constraints for the external knowledge. If an adversary knows only one external knowledge (u, t), she knows that one of the possible values in D(s t u ) corresponds to the user u. She cannot infer further information because she only knows the external knowledge at mix zones as described in Section 2. Therefore we do not need additional constraints in this case.

If the adversary knows two external knowledge {(u, t 1 ), (u, t 2 )} (i.e., she know the information about s(u, t 1 ) and s(u, t 2 )), she can infer more information from the external knowledge at the worst case where s(u, t 1 ) = s(u, t 2 ) holds. To consider this worst case, we add an extra constraint s t1 u = s t2 u to the generated constraint network. If there is more than two elements in the external knowledge, we add the corresponding constraints in the same way.

Let N be a constraint network which is generated with the function generateCSP (U, f, t * ) and let us consider

is the function for removing all inconsistent values from the domains. Each domain value d ∈ D G (s t u ) corresponds to a possible pseudonym which is computed with s(u, t). Therefore, we can solve k-pseudonym decision problem by checking whether |D G (s t u )| ≥ k holds for the security requirement (u, t, k). However, many CSP solvers do not use Φ G in practice because it requires too much computation time. Those solvers usually use the algorithms for other consistencies which are weaker but more reasonable with respect to execution time or memory consumption. Therefore, we propose an incremental solving method, which can be applicable to existing CSP solvers.

In the incremental solving method, we first generate a constraint network (X, D, C) from the given mix zone function, and check whether the network (X, D, C ∪ {s t u = i}) has a solution for each domain value i ∈ D(s t u ).

Experimental results

We develop the safety verification program for solving the k-pseudonym decision problem from a given mix zone function. It is written in Groovy with 409 lines using the Choco library [START_REF]The choco team. choco: an open source Java constraint programming library[END_REF] as an external CSP solver. Using this program, we further develop an optimization program based on dynamic programming that finds the minimum number of mix zones satisfying a given safety requirement.

We use the dataset [START_REF] Piorkowski | CRAW-DAD data set epfl/mobility (v. 2009-02-24[END_REF] containing mobility traces of taxi cabs in San Francisco, USA. It contains GPS coordinates of approximately 500 taxis collected over 30 days in the San Francisco Bay Area. When we conduct our experiments with a given number of users, we randomly pick a specified number of users from the dataset.

Figure 5 shows performance results of finding the minimum set of mix zones satisfying all the security requirements changing the number of users in a dataset. We randomly define security requirements of up to five to randomly chosen users. We compare results with our safety verification program using the CSP solver with those using our previously developed polynomial-time algorithm [START_REF] Mano | Protecting location privacy with kconfusing paths based on dynamic pseudonyms[END_REF]. Although the time complexity of the CSP solver is exponential at the worst