Lasse Borup

Rémi Gribonval
email: remi.gribonval@irisa.fr.

Morten Nielsen
email: mnielsen@math.wustl.edu

BEYOND COHERENCE : RECOVERING STRUCTURED TIME-FREQUENCY REPRESENTATIONS

Keywords: sparse representation, overcomplete dictionary, matching pursuit, basis pursuit, time-frequency dictionaries, wavelets, Wilson basis, linear programming, greedy algorithm, identifiability, inverse problem

We consider the problem of recovering a structured sparse representation of a signal in an overcomplete time-frequency dictionary with a particular structure. For infinite dictionaries that are the union of a nice wavelet basis and a Wilson basis, sufficient conditions are given for the Basis Pursuit and (Orthogonal) Matching Pursuit algorithms to recover a structured representation of an admissible signal. The sufficient conditions take into account the structure of the wavelet/Wilson dictionary and allow very large (even infinite) support sets to be recovered even though the dictionary is highly coherent.

I R I S A

Sur l'identification de représentations temps-fréquence parcimonieuses structurées Résumé : Nous nous intéressons au comportement des principaux algorithmes d'approximation parcimonieuse sur des signaux admettant une représentation à la fois parcimonieuse et structurée dans des dictionnaires temps-fréquence particuliers constitués de l'union d'une base d'ondelette et d'une base de Wilson, qui sont utilisés pour certains schémas de codage audio dits hybrides. Il s'agit de déterminer des conditions de "structure" suffisantes garantissant qu'une représentations d'un signal dans ce type de dictionnaire soit retrouvée par les algorithmes de type Matching Pursuit (MP) et Basis Pursuit.

Les conditions suffisantes les plus classiques, basées sur la cohérence (cumulative) du dictionnaire, sont en effet inopérantes dans ce contexte car elles amènent à se restreindre à des signaux qui coincident avec un atome du dictionnaire, et les résultats probabilistes valables pour des dictionaires aléatoires ne peuvent être directement appliqués sur un tel dictionnaire très structuré. En supposant que le dictionaire est généré à partir de fonctions (ondelette mère et fenêtre d'analyse) suffisament régulières, nous exprimons ici des conditions suffisantes beaucoup moins pessimistes qui prennent en compte la structure particulière du dictionnaire hybride ondelettes/Wilson. Les conditions obtenues reposent sur le fait que ce dictionnaire peut être décomposé en sous-ensembles d'ondelettes et de fonctions de base de Wilson approximativement associés à des "blocs" temps-fréquence disjoints, et qui forment essentiellement l'union de deux bases maximalement incohérentes des fonctions ayant ces blocs pour support.

Mots clés : représentation parcimonieuse, dictionnaire redondant, matching pursuit, basis pursuit, dictionnaire temps-fréquence, ondelette, base de Wilson, programmation linéaire, algorithme glouton, séparation de sources, traitement du signal multicanal, identifiabilité, problème inverse.

Introduction

Let Φ = [g i ] i∈F be an at most countable collection of normalized elements in a Hilbert space H. We say that Φ is a besselian dictionary if the associated linear map Φ : ℓ 2 (F ) → H given by Φ[(c k ) k ] = i∈F c k g i is bounded. In this note we consider the problem of recovering a sparse representation S X = Φ(S),

S ∈ ℓ 2 (F ), (1)
of a signal X ∈ H relative to a besselian dictionary Φ with a specific structure. Sparse representations provide a very useful tool to solve many problems in signal processing including blind source separation, feature extraction and classification, denoising, and detection, to name only a few (see also [START_REF] Gribonval | Sparse Approximations in Signal and Image Processing[END_REF], and references therein). Several algorithms, such as Basis Pursuit (ℓ 1 -minimization) and Matching Pursuits (also known as greedy algorithms), have been introduced to compute sparse representations/approximations of signals. The problem we face is that such algorithms a priori only provide sub-optimal solutions. That is, we do get a representation of the type ( 1), but we may not recover the sparse representation S of X.

Several recent papers [START_REF] Donoho | Optimally sparse representation in general (nonorthogonal) dictionaries via l 1 minimization[END_REF][START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF][START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF][START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF][START_REF] Gribonval | Sparse representations in unions of bases[END_REF][START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF] have identified situations where algorithms such as Basis Pursuit actually compute an optimal representation of a given signal, in the sense that they solve the best approximation problem under a constraint on the size of the support of the signal. Typically, one calculates the coherence of Φ

µ(Φ) = sup i =j | g i , g j |.
Then for signals X with a representation X = Φ(S) satisfying | supp(S)| < ⌊ 1 2 (1 + 1/µ)⌋, Basis Pursuit will recover the representation S. One serious problem with this type of results using the coherence is that they represent worst case estimates. For example, the coherence is close to one as soon as we have one pair of atoms that are approximately colinear while the rest of the dictionary may be much nicer. A more refined type of result can be obtained by considering the cumulative coherence introduced by Tropp [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]

µ 1 (Φ, m) := sup |Λ|=m sup j ∈Λ i∈Λ | g i , g j |.
However, the cumulative coherence also gives a worst case estimate that does not take into account the finer structure of the dictionary, and the mentioned bounds are too weak for many applications.

One way to overcome these shortcommings is by shifting to a probabilistic viewpoint and consider random dictionaries. The probabilistic approach has been considered in a number of recent papers, see e.g. [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Donoho | Compressed sensing[END_REF]. Random dictionaries are typically created by picking a number of unit vectors randomly from some larger ensemble. The results on sparse representations using random dictionaries are typically much better than the corresponding deterministic results. One problem is that the results are difficult to intrepret when we consider a specific dictionary.

We follow a different deterministic path in this note. The goal is to give more optimistic results for some concrete dictionaries that are often used in signal processing and harmonic analysis. The idea is to take into account some of the internal structure of the dictionary.

Irisa

The typical example of an admissible dictionary is the union of a nice wavelet basis and a Wilson basis.

The main tool to extend the classical estimates is to consider the setwise p-Babel function , which trivially extends the setwise Babel function defined in [START_REF] Gribonval | Beyond sparsity : recovering structured representations by ℓ 1 -minimization and greedy algorithms[END_REF] as follows. For 1 ≤ p < ∞ and a set I ⊆ F we define

µ p (Φ, I) := sup i / ∈I j∈I | g i , g j | p 1/p . (2)
For S a family of subsets of F , we define the structured p-Babel function as

µ p (Φ, S) := sup I∈S µ p (Φ, I). (3)
Notice that we allow infinite dictionaries Φ so it may happen that µ p (Φ, I) = +∞. The structured 1-Babel function µ 1 (Φ, S) generalizes the Babel function µ 1 (Φ, m). In fact, let

S m = {I ⊆ F : |I| = m}, m = 1, 2, . . . , |F |. Then µ 1 (Φ, m) = µ 1 (Φ, S m
). The case p = 1 is especially interesting due to the following result considered by Tropp [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF] for the Babel function. The proof of Lemma 1 is a straightforward generalization of the proof in [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF] and was pointed out in [START_REF] Gribonval | Beyond sparsity : recovering structured representations by ℓ 1 -minimization and greedy algorithms[END_REF]. It involves the sub-dictionary Φ I = [g i ] i∈I made of atoms from the set I ⊆ F .

Lemma 1. Let X = Φ(S) and suppose that supp(S) = I is such that

µ 1 (Φ, I) + max ℓ∈I µ 1 (Φ I , I\{ℓ}) < 1. (4)
Then Basis Pursuit and Orthogonal Matching Pursuit exactly recover the representation S of X.

In the special case where the nonzero coefficients in the representation S have similar magnitudes |c k | ≈ cst, the condition (4) is also sufficient to ensure that simple thresholding will recover S [START_REF] Gribonval | Towards an adaptive computational strategy for sparse signal approximation[END_REF][START_REF] Herrity | Sparse approximation with iterative thresholding[END_REF]. A similar condition involving the 2-Babel function instead of the 1-Babel function was recently shown to be related [START_REF] Gribonval | Average case analysis of multichannel thresholding[END_REF] to the probabilty of recovery with thresholding for simultaneous (multichannel) sparse approximation. All recovery results, which are expressed here for noiseless models X = Φ(S), have been shown to be stable to noise.

To illustrate how we can use dictionary structure to get improved recovery results, let us consider two examples. The first example is finite dimensional. In C N we consider Φ F D given as the union of the Dirac and the Fourier orthonormal basis for C N . One easily checks that the dictionary is maximally incoherent with µ(Φ F D ) = 1/ √ N. Thus, the classical result shows that Basis pursuit recovers sparse signals having a a representation with support less than ⌊ 1 2 (1 + √ N )⌋ atoms. Here we only estimate the size of the support. The second example is infinite dimensional. We consider Φ HW defined as the union of the Haar system (see e.g. [START_REF] Hernández | A first course on wavelets[END_REF]) B 1 = {h n } ∞ n=0 and the Walsh system (see [START_REF] Golubov | Walsh series and transforms[END_REF])

B 2 = {W n } ∞ n=0 on [0, 1].
The Haar system and the Walsh system both form an orthonormal basis for L 2 ([0, 1]) so Φ HW is a tight frame for L 2 ([0, 1]). The point we wish to make is the following; it is easy to check that µ(Φ HW ) = 1, so naively one would expect that no decent recovery result is possible. However, Φ HW has a lot of structure we can exploit. In the timefrequency plane, the Walsh function

W n is supported in the block [0, 1] × [n, n + 1] while PI n˚1833
the Haar function h n with 2 j ≤ n < 2 j+1 is supported on [START_REF] Golubov | Walsh series and transforms[END_REF]. Moreover, the 2 j -dimensional subdictionary Φ HW (j) := Q(j) ∪ Q ′ (j) is perfectly incoherent with µ(Φ HW (j)) = 2 -j/2 . Hence, if a signal x has a representation

H j,0 := [0, 1] × [2 j , 2 j+1 -1]. In fact, let Q(j) = {h k } 2 j+1 -1 k=2 j and Q ′ (j) = {W k } 2 j+1 -1 k=2 j . Then W j := span Q(j) = span Q ′ (j) with W j ⊥W j ′ for j = j ′ , see
x = c 0 + ∞ j=0 2 j -1 k=0 c j,k h 2 j +k + d j,k W 2 j +k , with | supp({c j,k } k )| + | supp({d j,k } k )| < 1 2 (1 + 2 j/2
) for j ≥ 0 (the notation supp() stands for the support set where a sequence is nonzero, and | • | denotes the cardinality of such a set), then we can use the simple finite dimensional estimate using the coherence (and the fact that W j ⊥W j ′ for j = j ′ ) to conclude that MP and BP recover this representation of x. Notice how this estimate takes into account the structure of the dictionary and not only the size of the support of signals.

The main result of this paper is to extend the straightforward considerations for Φ HW to other dictionaries with the same type of underlying structure. However, we will not assume that the dictionary can be decomposed into orthogonal finite dimensional dictionaries which will give rise to some added technicalities in the estimates. Our result holds for unions of an orthonormal wavelet basis {ψ j,k } and a Wilson basis {g n,m } with sufficient smoothness, a type of dictionary which was proposed for audio signal modeling and compression by Daudet and Torrésani [START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF]. For any pair c := c j,n and d := d n,m of coefficient sequences we define c j,2 j n+ℓ ψ j,2 j n+ℓ + d n,2 j +ℓ g n,2 j +ℓ .

N j (c, d) := sup n∈Z max | supp({c j,2 j n+ℓ } 2 j -1 ℓ=0 )|, | supp({d n,2 j +ℓ } 2 j -1 ℓ=0 )| .

Wavelet and local cosine dictionary

In this section we introduce the main function dictionary considered in this paper. The dictionary is the union of an orthonormal wavelet and local cosine basis and is consequently a tight frame with frame constant 2. We will not discuss the details involved in the construction of these bases here, but just refer the reader to e.g. [START_REF] Hernández | A first course on wavelets[END_REF]. To avoid unnecessary technicalities, we only consider the univariate case.

Basis functions

Let φ and ψ be a scaling function and a wavelet, both with compact support, such that

B 1 := {φ k } k∈Z ∪ {ψ j,k } j≥0,k∈Z
, is an orthonormal wavelet basis for L 2 (R), where

ψ j,k (x) := 2 j/2 ψ 2 j x -k and φ k (x) := φ(x -k).
Irisa Suppose that g is a smooth compactly supported "cut-off" function, and let

g n,m (x) := √ 2g(x -n) cos(π(m + 1 2 )(x -n))
for n ∈ Z and m ∈ N 0 := N ∪ {0}. For a suitable choice of g, B 2 := {g n,m } n∈Z,m∈N 0 is an orthonormal basis for L 2 (R), see [START_REF] Hernández | A first course on wavelets[END_REF]Sec. 1.4]. The besselian dictionary considered is the tight frame Φ = B 1 ∪ B 2 . It is indexed by F = F φ ∪ F ψ ∪ F g where F φ (resp. F ψ , F g ) indexes scaling functions (respectively wavelets, local cosines).

Cumulative coherence

We may partition any index set I ⊂ F into scaling function indices I φ = I ∩ F φ , wavelet indices I ψ = I ∩ F ψ and local cosine indices I g = I ∩ F g . Since each basis is orthogonal, the p-cumulative coherence of I is given by

µ p p (Φ, I) = max    sup ψ ′ ∈(F φ ∪F ψ )\I   ψ∈I φ ∪I ψ | ψ ′ , ψ | p + g∈I g | ψ ′ , g | p   , sup g ′ ∈F g \I   ψ∈I φ ∪I ψ | g ′ , ψ | p + g∈I g | g ′ , g | p      ≤ max    sup ψ ′ ∈F φ ∪F ψ g∈I g | ψ ′ , g | p , sup g ′ ∈F g ψ∈I φ ∪I ψ | g ′ , ψ | p    (5)
where we slightly abused notations by confusing basis functions with their indices, e.g., in the notation g ∈ I g .

Sketch with time-frequency blocks

To estimate each of the two terms which appear in the maximum (5) we will partition further the index sets I φ , I ψ and I g . Given j ∈ N 0 and n ∈ Z, it is easy to see that for a nice mother wavelet ψ, the 2 j functions {ψ j,k } 2 j n≤k<2 j (n+1) are essentially localized in time in the neighborhood of the interval [n, n + 1], and essentially localized in frequency in the neighborhood of the interval [2 j , 2 j+1 ]. In other words, they are localized around the "time-frequency block"

H j,n := [n, n + 1] × [2 j , 2 j+1
]. The same goes for the 2 j local cosine functions {g n,m } 2 j ≤m<2 j+1 , if g is well-localized in time and frequency. The coherence between any wavelet and Wilson function "living" on such a block is of the order 2 -j/2 . The distinct regions {H j,n } n∈Z,j∈N 0 essentially 1 tile the time-frequency plane, and in contrast to the relatively large coherence between functions from the same tile of the partition, the coherence between any two functions in two different pieces is (much) smaller. Thus, we may cut the sets I ψ and I g into pieces in parallel to the tiling of the time-frequency plane, and define for j ≥ 0 and n ∈ Z

I ψ j,n := {ψ j,k ∈ I ψ , 2 j n ≤ k < 2 j (n + 1)} I g j,n := {g n,m ∈ I g , 2 j ≤ m < 2 j+1 }.
1 For a complete tiling one would also need to include low frequency regions [n, n

+ 1] × [0, 1] PI n˚1833
Borup, Gribonval & Nielsen For a given wavelet ψ j,k / ∈ I ψ , letting n := ⌊2 -j k⌋ be such that 2 j n ≤ k < 2 j (n + 1) we have

g∈I g | ψ j,k , g | p = j ′ ≥0 n ′ ∈Z g∈I g j ′ ,n ′ | ψ j,k , g | p ≈ g∈I g j,n | ψ j,k , g | p ≈ |I g j,n | • 2 -jp/2 (6)
provided that the above sketchy analysis is valid. A similar estimate holds if the role of the wavelet and local cosine bases is exchanged, and the numbers

N j (I) := sup n∈Z max |I ψ j,n |, |I g j,n | (7)
are therefore involved in the estimation of the coherence. Indeed, if we assume that the index set I does not contain any scaling function (i.e., I φ = ∅) and no Wilson function g n,0 either, we get the following estimate of the p-cumulative coherence

µ p (Φ, I) ≈ sup j≥0 2 -j/2 N j (I) 1/p . ( 8
)
The above approach is only a sketch: in practice the inner products between wavelets and local cosine functions do not depend as sharply as depicted here on the time-frequency block to which their indices belong, and we will see below how the above approach should be corrected. Note that we assumed in this sketch that the index set I did not contain any lowfrequency atom (i.e., no scaling function and no Wilson function of the type g n,0 ). This restriction is only natural since scaling functions and Wilson functions of this type have very similar shapes, and have a very large coherence, so if they were to be included in I then the p-cumulative coherence would almost certainly exceed one.

Inner products between wavelet and local cosine basis functions

To estimate the p-coherence from above we will need to control the inner products | ψ j,k , g n,m | between wavelets and local cosine functions. The following lemmata give the fundamental estimates and are proved in Appendix A.

Lemma 2. Let φ, ψ, and g be three univariate functions such that for some C < ∞ and

A > 1 we have max(| φ(ξ)|, | ψ(ξ)|, | g(ξ)|) ≤ C (1 + |ξ|) -A . ( 9
)
Then, for all k, n ∈ Z, and m, j ∈ N 0 , we have

| ψ j,k , g n,m | ≤ C • 2 -j/2 (1 + 2 -j |m|) -A , | φ k , g n,m | ≤ C • (1 + |m|) -A , with C := (1 -A -1 ) -1 • 2 3/2 (2 A + 3 A )C 2 . ( 10
)

Irisa

Lemma 2 is proved using the frequency localization of the wavelet and Wilson basis. The next simple lemma uses the time localization to obtain other estimates of the inner products.

Lemma 3. Suppose that supp(φ), supp(ψ) ⊆ [-λ, λ] for some λ < ∞, and supp(g) ⊆ [-1/2, 3/2]. Then we have the estimates

| ψ j,k , g n,m | ≤ 2 -j/2+1 min{λ, 2 j }, if 2 j (n -1/2) -λ < k < 2 j (n + 3/2) + λ 0, else,
and

| φ k , g n,m | ≤ 2λ, if n -1/2 -λ < k < n + 3/2 + λ 0, else.
for all j, k, n ∈ Z, and m ∈ N.

Upper bound on the cumulative coherence

Using the estimates above we can now upper bound the cumulative coherence as expressed in the following result.

Theorem 2. Let φ, ψ, and g be three univariate functions with supp(φ), supp(ψ) ⊆ [-λ, λ] for some λ < ∞, and supp(g

) ⊆ [-1/2, 3/2]. Assume that for some C < ∞ and A > 1 we have max(| φ(ξ)|, | ψ(ξ)|, | g(ξ)|) ≤ C (1 + |ξ|) -A . ( 11
)
Consider a support set I which does not contain any scaling function, and no Wilson function g n,0 of frequency index 0 either. Then, for any p,

µ p p (Φ, I) ≤ 2(λ + 1) • Cp • j≥0 N j (I) • 2 -jp/2 . ( 12
)
with C given by [START_REF] Gribonval | Sparse representations in unions of bases[END_REF].

Comparing this result with the sketch (8) we notice that, in addition to a constant factor, the supremum over j has been replaced by a sum, which is quite strong but does not fundamentally change the rate at which N j (I) can grow with j. One can compare it to going from a weak ℓ 1 norm to a strong ℓ 1 -norm.

Proof. First we estimate sup g ′ ∈F g ψ∈I φ ∪I ψ | g ′ , ψ | p . For that we consider a given Wilson basis function g ′ = g n ′ ,m ′ ∈ F g . By Lemma 2 we have, for all j ≥ 0 and k ∈ Z

| g ′ , ψ j,k | ≤ C • 2 -j/2 (1 + 2 -j |m ′ |) -A .
By Lemma 3 the only indices k which may yield a nonzero inner product are in the interval 2 j (n ′ -1

2 )λ, 2 j (n ′ + 3 2 ) + λ , which covers at most 2 + 2 1-j λ ≤ 2(λ + 1) intervals of the form [2 n ℓ, 2 j ′ (n + 1)). Therefore, we may take the p-th power and sum up to get

n∈Z ψ j,k ∈I ψ j,n | g n,m , ψ j,k | p ≤ 2(λ + 1) • N j (I) • Cp • 2 -jp/2 • (1 + 2 -j |m ′ |) -Ap .

PI n˚1833

Since we assume I ψ is empty, summing up over j gives

ψ∈I φ ∪I ψ | g ′ , ψ | p ≤ 2(λ + 1) • Cp • j≥0 N j (I) • 2 -jp/2 • (1 + 2 -j |m ′ |) -Ap
and by taking the supremum over m, which is achieved at m = 0, it follows that sup

g ′ ∈F g ψ∈I ψ ∪I φ | g ′ , ψ | p ≤ 2(λ + 1) • Cp • j≥0 2 -jp/2 • N j (I) (13)
Reversing now the roles between Wilson basis functions and wavelets we now want to estimate sup ψ ′ ∈F φ ∪F ψ g∈I g | ψ ′ , g | p . We consider a given wavelet ψ ′ = ψ j ′ ,k ′ . By Lemma 2 we have for any n ∈ Z, m ≥ 1 and j ≥ 0 such that

2 j ≤ m < 2 j+1 | ψ ′ , g n,m | ≤ C • 2 -j ′ /2 (1 + 2 -j ′ |m|) -A ≤ C • 2 -j ′ /2 (1 + 2 -j ′ 2 j ) -A .
Moreover, by Lemma 3, the only indices n for which this inner product can be nonzero satisfy

-1 2 -2 -j ′ λ < n -2 -j ′ k ′ < 3 2 + 2 -j ′ λ
, so there is at most λ2 1-j ′ + 1 ≤ 2(λ + 1) of them. Therefore, taking the p-th power and summing we get

n∈Z gn,m∈I g j,n | ψ ′ , g n,m | p ≤ 2(λ + 1) • N j (I) • Cp • 2 -j ′ p/2 • (1 + 2 j-j ′ ) -Ap .
Since we assume I g does not contain any g n,m with m = 0, summing up over j gives

g∈I g | ψ ′ , g | p ≤ 2(λ + 1) • j≥0 N j (I) • Cp • 2 -j ′ p/2 • (1 + 2 j-j ′ ) -Ap (14)
Similarly, for any scaling function ψ ′ = φ k we obtain

g∈I g | ψ ′ , g | p ≤ 2(λ + 1) • j≥0 N j (I) • Cp • (1 + 2 j ) -Ap
and we notice that the right hand side is exactly that of (14) for j ′ = 0. Therefore we obtain sup

ψ ′ ∈F φ ∪F ψ g∈I g | ψ ′ , g | p ≤ 2(λ + 1) • Cp • sup j ′ ≥0 j≥0 2 -j ′ p/2 • (1 + 2 j-j ′ ) -Ap • N j (I) . ( 15
)
Since A > 1 2 it follows that for any ℓ ∈ Z, 2 ℓp/2 (1 + 2 ℓ ) -Ap ≤ 1. Therefore, for any j, j ′ ≥ 0 we have

2 -j ′ p/2 • (1 + 2 j-j ′ ) -Ap = 2 (j-j ′ )p/2 • (1 + 2 j-j ′ ) -Ap • 2 -jp/2 ≤ 2 -jp/2 .
Combining these facts with [START_REF] Gribonval | Sparse Approximations in Signal and Image Processing[END_REF] and [START_REF] Hernández | A first course on wavelets[END_REF] we get the desired result [START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF].

We have the following corollary.

Irisa

Corollary 1. Assume that a wavelet basis and a Wilson basis satisfy the decay conditions of Theorem 2, and consider a support set I which does not contain any scaling function, and no Wilson function g n,0 of frequency index 0 either. If

j≥0 N j (I) • 2 -j/2 < 1 4(λ + 1) C ( 16
)
then all standard pursuit algorithms will (stably) recover the support of any combination of atoms from the support set I.

Proof. For any ℓ ∈ I we consider the subset J ℓ = I\{ℓ} and notice that, for all j, N j (J ℓ ) ≤ N j (I), therefore, applying Theorem 2 with p = 1 we get under the condition ( 16) that

µ 1 (Φ, I) + sup ℓ∈I µ 1 (Φ I , J ℓ ) ≤ µ 1 (Φ, I) + sup ℓ∈I µ 1 (Φ, J ℓ ) ≤ 4(λ + 1) C • j≥0 N j (I) • 2 -j/2 < 1.
Our theorem can also be combined with the main theorem in [START_REF] Gribonval | Average case analysis of multichannel thresholding[END_REF] to prove that, under a white Gaussian model on the coefficients S, if

j≥0 N j (I) • 2 -j < 1 2(λ + 1) C2 (17)
then the probability that multichannel thresholding fails to recover the support set I decays exponentially fast with the number of channels.

Conclusion

In this note we have derived sufficient conditions for the Basis Pursuit and Matching Pursuit algorithms to recover structured representations of admissible signal with respect to an infinite dictionary given as the union of a nice wavelet basis and a Wilson basis. The sufficient conditions, although quite natural given the known coherence results for finite dictionaries, take into account the time-frequency structure of the dictionary and are thus much more optimistic than estimates taking only into account the overall dictionary coherence or its cumulative coherence. The conditions allow very large (even infinite) support sets to be recovered. These results somehow explain the success of audio signal processing techniques such as those proposed by Daudet and Torrésani [START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF] in recovering meaningful signal representations in a union of a wavelet and a local Fourier basis

PI n˚1833

A Time-frequency estimates

This appendix contains estimates of the inner product between a wavelet ψ j,k and a Wilson atom g n,m using the time and frequency localization of the respective systems. First we give a proof of Lemma 2. The result is similar to Lemma 3.12 in [START_REF] Hernández | A first course on wavelets[END_REF]Chapter 6]. Let us nevertheless give the proof.

where ξ 0 := 2 -j m. Define (2 A + 3 A ) 1 -A -1 2 -j (1 + |ξ 0 |) -A . Since this estimate is indepent of the sign of ξ 0 , we can conclude by combining the estimate with Eq. (18). The other inequalities are proved similarly.

Irisa

Proof. Proof of Lemma 3 The result follows from the fact that supp(ψ j,k ) ⊆ [2 -j (kλ), 2 -j (k + λ)] and supp(g n,m ) ⊆ [n -1/2, n + 3/2).

  A T O I R E S P U B L I C A T I O N I N T E R N E N o

Theorem 1 .

 1 There is a constant K (which depends on the support size and smoothness of the mother wavelet ψ and Wilson window function g) such that any pair of sequences satisfying j≥0 N j (c, d) • 2 -j/2 < K will be recovered by both Basis Pursuit and (Orthonormal) Matching Pursuit performed on the signal x = ∞ j=0 n∈Z 2 j -1 ℓ=0

Example 1 .

 1 The compactly supported Daubechies wavelets {φ N }, {ψ N } (filter length 2N)satisfy supp(φ N ), supp(ψ N ) ⊆ [-N, N] with max(| φ N (ξ)|, | ψ N (ξ)|) ≤ C (1 + |ξ|) -µN -1 ,with µ ≈ 0.1887, see[START_REF] Daubechies | Ten lectures on wavelets[END_REF] Chap. 7]. Thus we can apply Theorem 2 and its corollary with A = µN + 1 with any infinitely differentiable cut-off function g with supp(g) ⊆ [-1 2 ,3 2 ].

Proof. (Proof of Lemma 2 ) 2 R( 1 + 2 R( 1 +

 22121 Suppose m = 0. Notice that| ψ j,k (ξ)| = 2 -j/2 | ψ(2 -j ξ)| ≤ C2 -j/2 (1 + |2 -j ξ|) -A ,and likewise| g n,m (ξ)| ≤ 2 -1/2 | g(ξm)| + | g(ξ + m)| ≤ 2 -1/2 C (1 + |ξ -m|) -A + (1 + |ξ + m|) -A . Thus | ψ j,k , g n,m | = | ψ j,k , g n,m | ≤ 2 -1/2 C 2 • 2 -j/|2 -j ξ|) -A (1 + |ξ -m|) -A + (1 + |ξ + m|) -A dξ = 2 -1/2 C 2 • 2 j/|ξ|) -A (1 + 2 j |ξξ 0 |) -A + (1 + 2 j |ξ + ξ 0 |) -A dξ,

E 1 =E 1 ∪E 2 ( 1 +( 1 + 3 ( 1 +( 1 +R( 1 +( 1 +

 1121131111 {ξ ∈ R : |ξξ 0 | ≤ 1}, E 2 = {ξ ∈ R : |ξξ 0 | > 1 and |ξ| > 1 2 |ξ 0 |}, E 3 = {ξ ∈ R : |ξξ 0 | > 1 and |ξ| ≤ 1 2 |ξ 0 |}. For ξ ∈ E 1 we have 1+|ξ 0 | ≤ 1+|ξ -ξ 0 |+|ξ| ≤ 2+|ξ|. If ξ ∈ E 2 we have 1+|ξ 0 | < 1+2|ξ|. Thus, for ξ ∈ E 1 ∪ E 2 , we have 1 + |ξ 0 | ≤ 2(1 + |ξ|), and obtain for j ≥ 0 |ξ|) -A (1 + 2 j |ξξ 0 |) -A dξ ≤ 2 A (1 + |ξ 0 |) -A R (1 + 2 j |ξξ 0 |) -A dξ ≤ 2 A 2 -j (1 + |ξ 0 |) -A R |ξ|) -A dξ. If ξ ∈ E 3 , |ξ 0 -ξ| ≥ 1 2 |ξ 0 | and 3|ξξ 0 | = |ξξ 0 | + 2|ξ 0 -ξ| > 1 + |ξ 0 |. Thus, 1 + 2 j |ξξ 0 | > 2 j |ξξ 0 | > 2 j (1 + |ξ 0 |)/3. Therefore, E |ξ|) -A (1 + 2 j |ξξ 0 |) -A dξ ≤ 3 A 2 -Aj (1 + |ξ 0 |) -A R |ξ|) -A dξ.Since A > 1, combining the above estimates we get for j ≥ 0 |ξ|)-A (1 + 2 j |ξξ 0 |) -A dξ ≤ (2 A + 3 A )2 -j (1 + |ξ 0 |) -A R |ξ|) -A dξ =

This paper has been submitted for possible publication to Applied and Computational Harmonic Analysis. This work is supported in part by the European Union's Human Potential Programme, under contract HPRN-CT-2002-00285 (HASSIP).


Felix C Freiling

Sebastian Schinzel

Detecting Hidden Storage Side Channel Vulnerabilities in Networked Applications

Side channels are communication channels that were not intended for communication and that accidentally leak information. A storage side channel leaks information through the content of the channel and not its timing behavior. Storage side channels are a large problem in networked applications since the output at the level of the protocol encoding (e.g., HTTP and HTML) often depends on data and control flow. We call such channels hidden because the output differences blend with the noise of the channel. Within a formal system model, we give a necessary and sufficient condition for such storage side channels to exist. Based on this condition, we develop a method to detect this kind of side channels. The method is based on systematic comparisons of network responses of web applications. We show that this method is useful in practice by exhibiting hidden storage side channels in three well-known web applications: Typo3, Postfix Admin, and Zenith Image Gallery.

Introduction

Covert Channels and Side Channels. A covert communication channel is a communication channel that was not intended to transfer information at all [START_REF] Lampson | A note on the confinement problem[END_REF]. Today it is accepted that covert channels are impossible to avoid and hard to control. In practice, the sender P often does not intend to communicate with C but still leaks information. To distinguish this from the scenario of covert channels, the term side channel was used. Side channels abound and have been the focus of much research in areas like cryptographic hardware [START_REF]The Side Channel Cryptanalysis Lounge[END_REF], API design [START_REF] Bond | API-level attacks on embedded systems[END_REF] or non-electronic media [START_REF] Backes | Compromising reflections-or-how to read LCD monitors around the corner[END_REF].

In this paper we focus on side channels in applications running in the World Wide Web (web applications). Web applications are a prime communication mechanism today and side channels in web applications are relevant. Side channels are known as a special type of covert channel and covert channels are categorized into timing and storage channels. We thus adopt this discrimination for side channels and extend the general area of covert channels by distinguishing storage side channels from timing side channels. Whereas timing side channels are well researched in the World Wide Web, to our knowledge there is no well-founded research on the detection of storage side channels in web applications.

To fill this gap, we give a general method by which storage side channels can be detected in web applications. As main example we show that in many existing web applications with user management it is possible to find out whether a certain high-privileged user account exists or not. This information is usually treated as confidential because knowledge of high-privileged user names eases password guessing and phishing attacks.

Side Channels in Web Applications: Related Work. Most related work has focused on constructing or detecting timing channels on the web (see for example Felten and Schneider [START_REF] Felten | Timing attacks on web privacy[END_REF], Bortz, Boneh and Nandy [START_REF] Bortz | Exposing private information by timing web applications[END_REF] or Nagami et al. [START_REF] Nagami | An independent evaluation of web timing attack and its countermeasure[END_REF]). A timing covert channel appears when one "process signals information to another by modulating its own use of system resources (e.g., CPU time) in such a way that this manipulation affects the real response time observed by the second process" [START_REF] Of | Defense Standard[END_REF].

Only comparatively few authors have investigated possible storage channels on the web, i.e., channels that reside in the direct output of web applications. Bowyer [START_REF] Bowyer | Firewall bypass via protocol stenography[END_REF] and Bauer [START_REF] Bauer | New covert channels in HTTP[END_REF] describe the possibility of hidden channels in HTTP. Bowyer suggests using superfluous URL parameters to form an upstream connection, and HTTP header fields or image steganography as downstream connection. Bauer chooses HTTP redirects, Cookies, referrer headers, HTML elements or active content to hide communication over the HTTP protocol. Kwecka [START_REF] Kwecka | Application layer covert channel -analysis and detection[END_REF] summarizes five different methods that were used to create covert channels within application layer headers: Reordering of headers, case modifications, use of optional fields and flags, adding a new field, and using linear white space characters.

We are aware of only two papers on the detection of hidden storage channels on the web. Chen et al. [START_REF] Chen | Side-channel leaks in web applications: a reality today, a challenge tomorrow[END_REF] detected a side channel in the packet size of encrypted traffic between browser and several web applications that process critical information such as healthcare information. Their target was to detect side channels that are visible for a man-in-themiddle who has access to the encrypted network traffic. Borders and Prakash [START_REF] Borders | Quantifying information leaks in outbound web traffic[END_REF] present a method to determine the maximum bandwidth of covert channels. They focus on covert channels where P is the web browser and C is the web server, which is the opposite direction of our approach. Their method neither detects, nor prevents covert channels, but focuses on determining the upper boundary of a covert channel's bandwidth. They analyze storage covert channels that enabled P to purposefully pass information to C. However, storage side channels appear if P accidentally and unknowingly passes information to C.

Detecting Storage Side Channels in Web Applications. In this paper, we exhibit a method for detecting storage side channels by comparing the differences in multiple responses. We call a storage side channel hidden if users will not detect it by observing only the visible elements of responses. In contrast to timing attacks, we measure differences in the content of the responses of web applications. The idea is to correlate the differences of web application responses with some secret information stored in the web server. Storage side channels are noisy, i.e. if a user performs the same requests multiple times, many web applications will seemingly display the same content in the user's web browser. However, looking closely at the data of the web server's responses, one discovers that the responses differ slightly in many cases. We show that by a structured analysis it is possible to detect those differences that correlate with secret information, and are thus leaking information. Applying this method to three practical systems (Typo3, Postfix Admin, and Zenith Image Gallery), we were able to extract confidential information about existing user names and private images in public galleries.

Contributions.

In this paper, we study deterministic hidden storage side channels in web applications and make the following three contributions:

-We formalize the context in which side channels in networked applications occur and identify necessary and sufficient conditions for hidden storage side channels to exist. -We develop a general method to detect hidden storage side channels in networked applications and apply the method to web applications. -We use our method to identify side channels in three common web applications: the popular content management system Typo3 [START_REF] Association | Typo3 content management system[END_REF], Postfix Admin [START_REF] Admin | Web based administration interface[END_REF], which is a webbased administration system for the popular email server Postfix, and Zenith Image Gallery [START_REF] Cyberiapc | Zenith picture gallery[END_REF], a web-based image gallery.

Outlook. The paper is structured as follows: In Sect. 2 we introduce a formal model of hidden storage side channels and give a necessary and sufficient condition for their existence. In Sect. 3 we derive a detection technique for such channels in networked applications and apply the method to three well-known web applications in Sect. 4. We conclude in Sect. 5.

Hidden Storage Side Channels in Networked Applications

We now abstract from concrete network protocols and investigate general networked applications and their susceptibility to side channels.

System Model. Our system model, depicted in Fig. 1, consists of an information producer P and an information consumer C. Both are modelled as deterministic state automata. Both P and C are connected through a shared resource R. In our case, R can be thought of as a network connection such as one using TCP over the Internet. Abstractly, R just allows to reliably transport a stream of bytes from P to C. The information that P sends to C can be any "high-level" digital object, e.g., a graph, a web page or a spreadsheet. P carefully constructed the high-level object in a way so that it only contains information that C is allowed to see. Producer P uses an encoding function ϕ that maps the high-level object into a bytestream suitable for transport over R. Similarly, C uses a decoding function ψ that transforms the received bytestream into the same high-level object again. Note that P 's high-level object is the same as C's high-level object.

P C R bytestream high-level object ! low-level object secret high-level object ! low-level object
Formally, let H denote the set of all abstract "high-level" objects and L denote the set of all allowed byte-sequences that can be transported over R. We assume that L is closed under subsequences, i.e., if x ∈ L and x is a subsequence of x then x ∈ L as well. We use x • y to denote the concatenation of two byte-sequences x, y ∈ L.

Using this notation, ϕ is a function that maps elements from H to L, and ψ is a function that maps elements from L to H.

Definition of Hidden Storage Side Channels.

A covert channel is a unidirectional communication channel that allows P to covertly communicate with C over R. P and C agreed on ϕ and ψ beforehand. The purpose of those channels is to hide the fact that P communicates with C over R.

A side channel is a special covert channel in which P unintentionally communicates with C over R. Side channels do not appear on purpose but appear accidentally during system construction. C's challenge is to discover and decode the side channel in order to get the information from P .

Intuitively, a storage side channel allows C to infer a secret value from the content that P sent. A hidden storage side channel is a storage side channel that can only be detected in low-level values from L, as the high-level values are identical so that an observer of H will not detect the differences.

In general, we assume that the decoding function ψ is the inverse of the encoding function ϕ, i.e., ∀h ∈ H : ψ(ϕ(h)) = h. However, many encoding formats in practice contain redundancy in the sense that the same high level objects can be encoded differently by ϕ. This can cause hidden storage side-channels, as we now explain.

Abstractly, a storage side channel regarding some secret information exists if P encodes some object h ∈ H dependent on some secret (see Fig. 1). For example, if the secret consists of just one bit, P could encode h into l 0 if the bit is 0, and into l 1 = l 0 if the bit is 1. If both l 0 and l 1 will be decoded into the same high-level object h again, hidden storage side channels appear. Investigating the encoding of l 0 and l 1 reveals the secret.

A Necessary and Sufficient Requirement. Note that our system model subsumes the scenario of Kemmerer [START_REF] Kemmerer | Shared resource matrix methodology: An approach to identifying storage and timing channels[END_REF] since P and C are connected through a direct communication link. Therefore, it is clear that side channels may exist. However, we refine Kemmerer's conditions to our case and derive a sufficient requirement for hidden storage side channels to exist in our system model.

It is sufficient for storage side channels to exist in our system model if there exist ψ-synonyms in L, i.e. there exist distinct values l 1 and l 2 in L that ψ maps into the same value in H, formally:

∃l 1 , l 2 ∈ L : l 1 = l 2 ∧ ψ(l 1 ) = ψ(l 2 )
To prove that this is a sufficient condition we have to show how a hidden storage side channel can be constructed. This is rather straightforward, as explained above: Depending on the secret s, the producer (possibly unintentionally) selects either l 1 (for s = 0) or l 2 (for s = 1). By investigating the low-level encoding of the message, i.e., before applying ψ, the consumer can learn the value of s.

We now argue that the condition of ψ-synonyms is also a necessary condition. For this we have to prove that the existence of hidden storage side channels implies that ψ-synonyms hold on the encoding.

So assume that we have a system in which hidden storage side channels exist. From the definition of storage side channel and in contrast to timing side channel, we know that information is transported using the content of messages exchanged over R. Since the channel is hidden, the channel is not visible on the level of H.

There are two cases to consider:

1. The content directly reflects secret information, i.e., a value l 1 implies s = 0 and l 2 implies s = 1. In this case, we directly have the condition of ψ-synonyms. 2. The content reflects secret information via the order of byte sequences exchanged over R. In the simplest case, this means that there are two byte sequences l and l such that l • l encodes s = 0 and l • l encodes s = 1. Note that ψ(l • l ) must be equal to ψ(l • l). In this case, choose l 1 = l • l and l 2 = l • l and the condition of ψ-synonyms holds again.

So overall, if hidden storage side channels exist, then the requirement of ψ-synonyms must hold. Therefore, the requirement is not only sufficient but also necessary.

Attacker Model. We assume that the attacker is in full control over the the information consumer. The goal of the attacker is to deduce the secret that resides in the information producer P . The allowed interactions between the attacker and P must conform to the protocol used on the shared resource (e.g., HTTP), i.e., we do not consider protocolspecific attacks.

Detecting Storage Side Channels in Networked Applications

We now study the question, how to detect the existence of storage side channels for a given networked application. This is a non-trivial task since the dependency of the lowlevel encoding on the secret may not be known or may be time or context dependent.

Secret-dependent and Secret-independent Differences. Consider the case where P leaks secret information over a storage side channel to C and this secret consists of one bit s. Now assume two possible worlds a and b that are identical in all aspects except the value of the secret bit s: In world a we have s = 0 and in world b we have s = 1. P now sends a message via R to C. Let A denote the message sent in world a, and let B denote the message sent in world b. If a and b are identical except for the values of s, then any difference between A and B is a direct influence of the difference of the secret value. (Recall that both P and C are deterministic automata.) Hence, measuring the differences between A and B yields secret-dependent differences in messages.

Ideally, we want to identify secret-dependent differences since they can be used to infer the value of s. However, in practice, it is difficult to construct two identical worlds a and b in which P has absolutely the same state (even using virtualization). To make our method more robust and practical, we allow observing messages at different points in time as shown in Fig. 2. If we send two successive messages A 0 and A 1 in world a, for example, then we can measure the differences between these two messages. Since s = 0 for both messages, any differences between A 0 and A 1 must be secret-independent. Secretindependent differences can result from different times or relative orders of the sending of A 0 and A 1 . Now assume that a message in world a is sent at time t 0 and another

X X s-independent differences s-dependent differences t1 t0 1 (world b) 0 (world a) X A0 A1 B0 s T B1 s-independent differences + s-dependent differences X t2
Fig. 2. Realistic measurements yield a mix of secret-dependent and secret-independent differences. The challenge is to reliably extract secret-dependent differences from the mix. message in world b is sent at time t 1 . Let A 0 denote the former and B 1 denote the latter message. If we compare A 0 and B 1 , we find a composition of secret-dependent and secretindependent differences (see Fig. 2). The challenge is to identify the secret-dependent differences and associate them with particular values of s. In the following section, we describe our method that we used to successfully uncover storage side channels in web applications.

Definitions and Notation.

Let A be a byte sequence A = a 0 , a 1 , a 2 , . . .. We define an edit e of A to be a tuple (p, q) such that 1. p ∈ N : 0 ≤ p < |A| and 2. q ∈ N : 0 ≤ q ≤ |A| -p.

Intuitively, an edit describes a "change" of the byte sequence, more specifically a removal of q bytes starting at position p. We formalize this by defining what it means to apply an edit to a byte sequence.

Let e = (p, q) be an edit of A. The application of e to A, denoted A| e is the byte sequence resulting from removing q bytes starting at index p in A, formally: A| e = a 0 , a 1 , . . . , a p-1 , a p+q , a p+q+1 , . . .

Here are some examples: Assume A is the byte sequence "01234". Then A| 0,2 = 234, A| 1,3 = 04, A| 4,1 = 0123, A| 2,1 = 0134 and A| 1,0 = 01234. In contrast, both A| 2,4 and A| 5,0 are undefined because both (2, 4) and (5, 0) are not edits of A.

We now describe what it means to apply multiple edits to A. We say that an edit (p, q) is compatible with edit (p , q ) iff (if and only if) p + q < p . Intuitively, two edits are compatible if they affect different parts of A. They are not compatible (incompatible) if they overlap. For example, for A = 01234, edit (1, 3) and (4, 1) are compatible whereas [START_REF] Admin | Web based administration interface[END_REF][START_REF] Bauer | New covert channels in HTTP[END_REF] and (4, 1) are incompatible.

Let E be the set of all possible edits of A and E = e 1 , e 2 , e 3 , . . . , e n be a sequence of n edits of A such that for all i, 0 < i < n, e i is compatible with e i+1 . The application of E to A, denoted A| E , is defined as:

(. . . ((A| en )| en-1 )| en-2 . . .)| e1
Note that the definition applies edits in reverse order, i.e., starting with e n . This is not a necessary requirement as edits could be applied in any order. However, it simplifies the definition since index numbers for subsequent edits e n-1 , e n-2 , . . . remain the same.

In the next step, we use the notion of edits to define the longest common subsequence and a special difference operator ∆. Let A and B be two byte sequences. The byte sequence x is a common subsequence (CS) of A and B iff there exists two sequences of compatible edits E A and E B such that A| E A = x and B| E B = x. In other words, x can be constructed from A by applying E A to A and x can be constructed from B by applying E B to B.

The byte sequence x is a longest common subsequence (LCS) of A and B if x is a common subsequence of A and B and |x| is maximal. We denote this by writing x = LCS (A, B).

Note that there can be multiple LCS s for pairs of byte sequences. For example, for A = 212 and B = 121 there are two longest common subsequences, namely 21 and 12. In our implementation, we chose to return the "leftmost" LCS of the left parameter, i.e. LCS (212, 121) = 21 and LCS (121, 212) = 12.

We are now ready to define the "difference" operator ∆ that will be important in our method to detect storage side channels. Let A and B be two byte sequences. The operation A ∆ B results in a compatible sequence of edits E of A such that A| E = LCS (A, B). In other words, E is the sequence of edits needed to produce out of A a longest common subsequence of A and B. For example, let A = 212 and B = 121, then A ∆ B = (2, 1) and A| (2,1) = 21.

The Difference Algorithm. In practice, secret-independent differences often result from dynamic values like session identifiers or time stamps. Note that for time dependent values, the time period during which the measurements were taken is important. For example, if the day field of a time stamp changes only after 24 hours (once every day), we will not be able to observe this dependency if all measurements are taken within the same day. For two such byte strings A 1 and A 2 , we must expect |LCS (A 1 , A 2 )| > 0, i.e., even two randomly generated byte strings are likely to have an LCS with non-zero length. So the idea is to incrementally compute the LCS of a sequence of byte strings A 1 , A 2 , A 3 , . . ., i.e., first LCS (A 1 , A 2 ), then LCS (LCS (A 1 , A 2 ), A 3 ), then LCS (LCS (LCS (A 1 , A 2 ), A 3 ), A 4 ), etc. At some point, say while going from A i to A i+1 , the length of the resulting byte sequence will not change any more. This means that all random elements have been eliminated from all A i , i.e., we have computed the "static core" of the response sequence A i . A1, A2, ..., An

LCS LCS

B1, B2, ..., Bn

!

XA XB E

Step 1:

Step 2:

Step 3:

s=0 s=1
Fig. 3. The difference algorithm.

In the following, we will now generalize our observations into an algorithm to identify secret-dependent differences. Fig. 3 shows a graphical representation of the steps.

1. Record n responses with s = 0 (denoted A 1 , A 2 , . . . , A n ) and n responses with s = 1 (denoted B 1 , B 2 , . . . , B n ). The value of n depends on how many responses are required to detect all dynamic parts in the response's content. Section 4 introduces empirical values of n for different applications. 2. For all 1 ≤ i ≤ n recursively calculate

X A = A 1 for i = 1 A i | Ai∆Xi-1 for 1 < i ≤ n
Compute X B similarly using responses B i . Intuitively, the byte sequences X A and X B correspond to the "static" parts of A i and B i , respectively, in which any secretindependent differences are removed. Finding the secret-independent differences E A of a response A 1 is straight forward:

E A = X A ∆ A 1 . 3. Now compute E = X A ∆ X B .
The set E contains an approximation of all secretdependent differences. If E = ∅ the probability of a storage side channel is high.

Looking closely at the edits in E it is often possible to decode the storage side channel, as we show in the following sections where we apply this method to real-world web applications.

Application of Method to HTTP/HTML

We now apply our method to web applications in which we wish to detect storage side channels. Such side channels can be, for example, the information whether a certain user account exists in a web application. Another example is the fact whether certain data items (such as images) are stored in a database. We start by verifying whether the condition of ψ-synonyms is satisfied in HTTP/HTML. Then, the attacker has to perform two steps. First, the attacker needs to find out whether the targeted application leaks the required information over a storage channel. Second, given that the targeted application is vulnerable to storage side channels, the attacker creates a search pattern. If the search pattern is applied to a single response, the attacker can find out the secret.

Storage Side Channels in HTTP and HTML. We now apply our system model to HTTP and HTML, and define that P is the web server, C is the web client, and R is the TCP channel between C and P . The set of high-level objects H consists of all web pages in the form of bitmaps displayed in C's web browser. The set of low-level objects L is the set of all ASCII sequences sent over R. Therefore, ϕ is the function used by P that "turns" a web page's intended bitmap into a valid HTML document and attaches it to a HTTP response before it is sent via R to C. The function ψ is the parser in C's web browser that reads the content of the HTTP response, creates the page's bitmap, and displays it on the screen of C.

HTTP responses contain a set of common headers, one of which is the Server header. The value of this data field is usually set to the particular type and version of the web server. However, this value is almost never used by the client and can therefore be set arbitrarily without affecting the web page displayed in C's web browser. Other examples for synonyms come from the fact that HTTP header fields are not case sensitive, i.e. "date" and "dATe" denote the same header field name. Moreover, HTML allows including meta information (e.g., author) in the HTML header which can be set to arbitrary values without affecting the content displayed in the browser.

To summarize, HTML as well as HTTP allow synonymous values and are therefore potentially vulnerable to storage side channels.

Detecting Storage Side Channels in Web Applications. As a precondition for our first attack scenario, the attacker needs to know at least two existing user names and two non-existent user names in one instance of the targeted software. The attacker performs n login requests with known to be valid user names and records the responses A i . All login requests in this scenario will fail because the attacker does not know any valid password in the target system. Thus, the system will always return an error message. He then calculates X A from all responses and observes the decreasing length of the static part. In parallel, the attacker performs n login requests with invalid user names and records the responses (B i ). Again, these login attempts will fail because the user name does not exist. Then, he calculates X B . n was large enough if the LCS of the responses stays constant for larger n.

The attacker then calculates the set of edits (E) representing secret-dependent differences. If E = ∅, the application leaks information about whether a user name exists through a storage side channel.

For our second attack scenario, the attacker needs to have access to at least one gallery containing no private pictures (A) and another gallery with at least one private picture (B). The attacker records n responses of A and n responses of B and calculates X A , X B , and E. If E = ∅, the application leaks information about whether private images exist in a gallery through a storage side channel.

For the implementation of our algorithm, we chose Myers' LCS algorithm [START_REF] Myers | An O(N D) difference algorithm and its variations[END_REF]. It has near linear time and space requirements with regard to the size of the two responses that need be compared. A Java implementation of the algorithm performed around 70 LCS operations per second on responses with 12 Kilobytes.

Exploiting Storage Side Channels in Web Applications. The attacker now creates a search pattern from the secret-dependent edits in E. The application of this pattern to the response of a login request to any instance of the vulnerable web application determines whether the login request was performed using a valid or invalid user name.

The calculation of E was a one time effort. From now on, the attacker can learn about the existence of a chosen user name with a single request and on any system on the web which runs the vulnerable software. The quality of the results is independent of the network conditions and of the amount of changed bytes in the secret-dependent difference.

In the following, we apply our method to three real-world examples.

Example 1: Storage Side Channels in Typo3. In our first example, we analyze whether the user authentication logic of the backend administration interface of Typo3 [START_REF] Association | Typo3 content management system[END_REF] version 3.6.0rc2-0.0.1, an open source and well-known content management system (CMS), is vulnerable of storage side channels. For this, we installed a copy of Typo3 in our lab. By default, Typo3 already creates one administrative user account (admin) during installation. It is possible to delete or rename this user name after installation, but we can assume that not all web administrators do this. Although we performed the measurements in our lab, this measurement could have been performed at any Typo3 instance on the web. Let s be the boolean value denoting whether a user name exists. We now record a set of responses from login attempts with valid user names and another set with invalid user names. We then generate the "static core" of both sets, namely X A and X B . The set of edits E = X A ∆X B yields the set of secret-dependent differences.

Interestingly, the different sizes of X A and X B correlates with s and therefore suggests that the analyzed functionality is vulnerable of storage side channels. Unfortunately, the size of the response will most certainly differ among several installations because of sitespecific customizations of the web page and the web server type and configuration. An attacker would therefore need to analyze the response size for each target before performing the actual attack, which makes the attack easier to detect. Furthermore, if the web page contains secret-independent dynamic data with differing size, e.g. from a news ticker or changing ads, the response size is dynamic as well, which would require additional probabilistic analysis and even more measurements. Our method is immune to these disturbances as it produces the exact positions of secret-dependent differences, which allows the creation of search patterns for this particular change. Fig. 4 shows the positions of secret-independent differences in the byte stream of X A . It is apparent that some values in the header, presumably time stamps, and one position in the HTML body change independently of s. Fig. 5 shows secret-dependent differences which form a storage side channel. This storage side channel leaks the existence of a given administrative user name. Note, that our method distinguishes secret-independent differences and secret-dependent differences even if they overlap, as it is the case here. It seems that the differences are located in the HTTP headers, because the positions of the secret-dependent differences are far to the left.

Fig. 6 shows a direct comparison of the HTTP headers generated with s = 0 and s = 1, respectively. The secret-dependent differences are highlighted in both responses. A manual analysis of these exposed secret-dependent differences yields that not only the values of the HTTP headers in Typo3 change depending on s but also the order in which the headers are declared. Note that the content sizes of both responses are equal, i.e.

Non-existent user name (s=0)

Existing user name (s=1) Fig. 6. Secret-dependent changes in Typo3's HTTP header that depend on whether a user name exists.

the change of response size we observed earlier in this section does not affect the HTML content but solely happens in the HTTP header.

Example 2: Storage Side Channels in Postfix Admin. In our second example, we analyze whether the user authentication logic of Postfix Admin [START_REF] Admin | Web based administration interface[END_REF] version 2.3 rc7, an open-source Email administration frontend [START_REF] Admin | Web based administration interface[END_REF], is vulnerable of storage side channels. We calculated X A , X B , and E as described previously. After roughly n = 15 comparisons, the sizes of X A and X B do not change any more. Fig. 7 shows the positions of the secret-dependent and the secret-independent differences in the responses. Fig. 8 shows a direct comparison of the secret-dependent differences in the HTTP headers and in the HTML content generated with s = 0 and s = 1, respectively. The secret-dependent differences are highlighted in both responses. A manual analysis of the exposed secret-dependent differences yields that Postfix Admin automatically fills a user name in the form field of the response if and only if the user name exists in the database and is an administrative user. Strictly speaking, by the definition given in this paper, this vulnerability does not qualify as a hidden storage side channel, as it can be observed in the browser. In practice, however, it is unlikely that this storage side channel is detected in a manual security test, because of the subtle nature of the difference. Actually, common web browsers may remember user names that a user filled in the same login form earlier, in order to automatically fill in the same user name for subsequent requests. We thus want to highlight, that our method will also detect "visible" storage side channels that would probably slip through most manual security analysis.

Non

Example 3: Storage Side Channels in Zenith Image Gallery. In our last example, we analyze whether the Zenith Image Gallery [START_REF] Cyberiapc | Zenith picture gallery[END_REF] version v0.9.4 DEV, a well-known open source picture gallery, is vulnerable of storage side channels. Zenith allows administrators to upload pictures, which anonymous users can view. Administrators can also delete pictures from the gallery or mark them as private pictures. Private pictures are still shown to administrators but are hidden for anonymous users. Here, we analyze if an attacker can find out the existence of private pictures in the public gallery.

Let s be the boolean value denoting whether private pictures exist in a chosen gallery with seven public images and one additional private picture. We then record a set of responses B from this gallery with the additional private picture (s = 1) and another set A from the same gallery in which the private picture is deleted (s = 0). The measurements are performed as anonymous users and only 7 pictures are visible during both measurements. We then calculate X A , X B , and E. After roughly n = 11 comparisons, the sizes of X A and X B do not change any more. A-responses as well as B-responses have 35 secret-independent bytes. Only a single byte forms the hidden storage side channel. A manual analysis yields that the secret-dependent number represents the sum of public image and private images. In case of s = 1, the number is 8 as there are 7 public pictures plus 1 private picture in the gallery. Thus, the hidden storage side channel not only leaks the fact that there are private pictures in a gallery, but also the amount of private pictures in the gallery.

Conclusions

The success of our detection method critically depends on the secret that is to be observed and therefore it is hard to automate. This makes it extremely difficult to quantitatively assess the significance of side channel vulnerabilities in web applications in general. For this paper, we analyzed 15 applications for hidden storage side channels and quickly identified the three examples documented here.

In principle, it is rather straightforward to avoid storage side channels by avoiding the condition of ψ-synonyms that we identified in this paper. This can be done, for example, by "fixing" the encoding function ϕ so that there are no synonymous values in L. In reality, however, the encoding scheme is often given and, for the case of HTTP and HTML, it is not feasible to remove the general existence of synonymous values.

So in practice, more pragmatic approaches are necessary, such as trying to remove the relation between s and the choice of the synonymous values, to make the inference from L objects to the value of s (and vice versa) impossible. This approach, however, largely depends on the vulnerable application and on how this application chooses synonymous values depending on s. In practice, therefore, side channels in web applications will have to be treated in a similar way as covert channels in other systems: Educate developers and give them effective techniques for detecting such channels in their systems. Furthermore, future protocol designers should carefully avoid conditions in which synonymous values are acceptable.

Fig. 1 .

 1 Fig. 1. System model.

Fig. 4 .Fig. 5 .

 45 Fig.[START_REF] Bauer | New covert channels in HTTP[END_REF]. The positions of secret-independent differences in a response of Typo3.

Fig. 7 .

 7 Fig. 7. The positions of secret-dependent and secret-independent differences in a response of Postfix Admin.

Fig. 9 .

 9 Fig.9. The secret-dependent difference in Zenith's HTML content of a gallery that depends on the existence of private pictures in a gallery.

Fig. 9

 9 Fig.9shows a comparison of the HTML content of a gallery web page. Interestingly, only a single number depends on s. A-responses (no private images) have a constant size of 12460 bytes. B-responses (1 private image) have the same size with 12460 bytes. A-responses as well as B-responses have 35 secret-independent bytes. Only a single byte forms the hidden storage side channel. A manual analysis yields that the secret-dependent number represents the sum of public image and private images. In case of s = 1, the number is 8 as there are 7 public pictures plus 1 private picture in the gallery. Thus, the hidden storage side channel not only leaks the fact that there are private pictures in a gallery, but also the amount of private pictures in the gallery.

Control: no-cache, must-revalidate Pragma: no-cache Last-Modified: Mon, 25 Jan 2010 11:47:45 GMT

	HTTP/1.1 200 OK Date: Mon, 25 Jan 2010 11:47:55 GMT Server: Apache/2.2.9 (Debian) PHP/5.2.6-1+lenny4 with Suhosin-Patch X-Powered-By: PHP/5.2.6-1+lenny4 Expires: Thu	HTTP/1.1 200 OK Date: Mon, 25 Jan 2010 11:47:45 GMT Server: Apache/2.2.9 (Debian) PHP/5.2.6-1+lenny4 with Suhosin-Patch X-Powered-By: PHP/5.2.6-1+lenny4 Expires: 0 Cache-Vary: Accept-Encoding
		Content-Type: text/html;charset=iso-8859-1
		Content-Length: 5472

, 19 Nov 1981 08:52:00 GMT Last-Modified: Mon, 25 Jan 2010 11:47:55 GMT Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Pragma: no-cache

	Vary: Accept-Encoding
	Content-Type: text/html;charset=iso-8859-1
	Content-Length: 5472

  Secret-dependent changes in Postfix Admin's HTTP header and HTML content that depend on whether a user name exists.

	-existent user name (s=0)	Existing user name (s=1)
	...	...
	Content-Length: 3612	Content-Length: 3626
	...	...
	<tr>	<tr>
	<td>Login (email):</td>	<td>Login (email):</td>
	<td><input class="flat" type="text" name="fUsername"	<td><input class="flat" type="text" name="fUsername"
	value="" /></td>	value="admin@admin.de" /></td>
	</tr>	</tr>
	Fig. 8.

Acknowledgments. We thank Martin Johns for the helpful comments on a previous version of this paper.

Sebastian Schinzel was supported by Deutsche Forschungsgemeinschaft (DFG) as part of SPP 1496 "Reliably Secure Software Systems".


Mohd Jali

Steven Furnell

Paul Dowland

Quantifying the Effect of Graphical Password Guidelines for Better Security

Keywords: Graphical passwords, Authentication, Usability, Security, HCI

Authentication using images or graphical passwords is one of the possible alternatives for traditional authentication based upon passwords. This study aims to investigate the practicality of giving guidelines or advice to users before they start choosing their image passwords, the effectiveness of using a smaller tolerance (clickable areas) and the optimum combination of click and image passwords. An alternative graphical prototype known as the Enhanced Graphical Authentication Scheme (EGAS) was developed in order to achieve these aims which implemented two different types of data collection (internal and external). From the findings, both internal and external groups indicated that the implementation of guidelines alone cannot guarantee the security of image passwords created by participants; but, in combination with other usability measurements this study has shown positive outcomes.

Motivation

Using images to authenticate users is one possible alternative for password-based authentication. Previous work has divided image-based authentication into three categories; namely 'click-based', 'choice-based' and 'draw-based'. The click-based approach refers to the action of clicking on the provided/chosen image(s) (i.e. selecting an element of the image), choice-based refers to the action of selecting a series of images (i.e. choosing images from a selection on screen) and draw-based refers to the action of drawing/sketching in order to be authenticated.

Regardless of the methodologies, previous studies have reported positive results, especially in the aspects of recall and memorability (i.e. participants were able to remember their secrets (i.e. image passwords) accurately after long periods of time) and usability (i.e. using images is user friendly) [START_REF] De Angeli | Is a picture really worth a thousand words? Reflecting on the usability of graphical authentication systems[END_REF], [START_REF] Chiasson | Graphical password authentication using Cued Click-points[END_REF] and [START_REF] Hinds | Increasing security and usability of computer systems with graphical password[END_REF]. Conversely, studies have also reported the disadvantages. Davis et al. [START_REF] Davis | On user choice in graphical password schemes[END_REF] and Tullis and Tedesco [START_REF] Tullis | Using personal photos as pictorial passwords[END_REF] found that users chosen secrets were influenced by gender. Chiasson et al. [START_REF] Chiasson | User interface design affects security: Patterns in click-based graphical passwords[END_REF] reported that the concept of clicking on images (e.g. Passpoint [START_REF] Wiedenbeck | PassPoints: design and longitudinal evaluation of a graphical password system[END_REF]) was not secure as users tended to create hotspots (i.e. focussing upon one area in an image) and generating similar patterns (e.g. a straight line from top-bottom or left-right). Oorchot et al. [START_REF] Oorschot | Purely automated attacks on Passpointsstyle graphical passwords[END_REF] claimed that it was possible to crack users' secrets regardless of the background image, with the study by Everitt et al. [START_REF] Everitt | A comprehensive study of frequency, interference, and training of multiple graphical passwords[END_REF] reporting that having multiple secrets resulted in more errors when compared with password-based authentication.

With respect to security, the main problem with the click-based method can be referred to as 'hotspot' while the problem with the choice-based method can be referred to as 'hot-image'. The problem of hot-image happens when a similar image is selected by many users. This problem could also be associated when users choose similar categories/themes or through gender preferences (e.g. males choose cars and females choose flowers). The hotspot problem could occur in two conditions. Firstly, the user clicks within the same or similar point on the given image or clicks on the same point or area when two or more images are given. Secondly the user produces predictable shapes such as straight lines and clicks on obvious/predictable objects within the image. Studies related to security in graphical passwords can be found in [START_REF] Dirik | Modelling user choice in the Passpoints graphical password scheme[END_REF], [START_REF] Golofit | Click passwords under investigation[END_REF], [START_REF] Golofit | Picture passwords superiority and picture passwords dictionary attacks[END_REF] and [START_REF] Peach | Heuristic Attacks against graphical password generators[END_REF].

In an attempt to address or reduce the aforementioned problems and at the same time maintain users' memorability, many studies have been published with regards to the effect of using various types of images. Examples include using images of cartoon characters [START_REF] Hinds | Increasing security and usability of computer systems with graphical password[END_REF], images of geometric shapes [START_REF] Lin | Graphical password using images with random tracks of geometric shapes[END_REF] and using images that were later transformed into unclear or distorted forms during login [START_REF] Harada | A User Authentication System Using Schema of Visual Memory[END_REF] and [START_REF] Hayashi | Use Your Illusion: secure authentication usable anywhere[END_REF]. With respect to the click-based method, a technique known as persuasion has been proposed [START_REF] Chiasson | Influencing users towards better passwords: persuasive cued click-points[END_REF] where the software recommends to the user possible 'safe' areas in which to create their secrets.

As far as the authors are aware, no study was found to have investigated or introduce user guidelines as part of the enrolment process. Therefore, the authors introduced a set of guidelines for graphical authentication, referred to as the Graphical Password Guidelines (GPG) which was presented to the user before they began choosing their secrets.

The authors also conjectured that GPGs on their own (Table 1) would not be a universal solution due to inherent human behaviour (i.e. certain users, although aware of the guidelines, sometimes violate the rules). To address this, restrictions were applied during registration. Two restrictions implemented in this study are as follows:

1. Users were only permitted to choose one image per category. 2. Users were not permitted to click on the same areas within an image. If they choose more images, they were also not permitted to click on the same area within the images.

The above restrictions together with the GPG were integrated into a software prototype. The software applied these restrictions by displaying warning messages if the software identified the user attempting to breach the rules.

The study was conducted in order to examine the impact on usability as well as user perception towards the introduction of the GPGs and image selection restrictions. Each participant had two types of secret; namely click-secrets (based upon the action of clicking on an image) and image-secrets (based upon the action of choosing a sequence of images). In addition to this, the study aimed to find ideal (usable and secure) combinations of click and image-secrets. A third investigation was undertaken to evaluate the impact of reducing the tolerance of the click positions. Tolerance can be explained as the extent of the area surrounding the users' secret clicks which are still accepted as legitimate. Prior research has indicated that participants were quite good when entering their secrets, both during registration and login [START_REF] Chiasson | A second look at the usability of click-based graphical passwords[END_REF]. Thus, the authors believed that using a smaller tolerance is possible and for this reason, users' performance when using smaller tolerance was investigated.

Table 1: Graphical password guidelines.

Task Guideline Explanation

Choosing images

Choose different themes and images

Users perceives image differently and previous studies have found gender bias in user image selections [START_REF] Davis | On user choice in graphical password schemes[END_REF], [START_REF] Tullis | Using personal photos as pictorial passwords[END_REF] and [START_REF] Jali | Assessing image-based authentication techniques in a web-based environment[END_REF]. As a result, the user is advised to choose different images, the image itself should not related to gender and more importantly, they are advised to choose images that they think could offer them memorable areas for placing their secret clicks. Oorchot et al., [START_REF] Oorschot | Purely automated attacks on Passpointsstyle graphical passwords[END_REF] showed that some users' secret were predictable. To reduce this, the user is advised to create their secret randomly. Specifically, they are not permitted to click on or within the same area (also applied to many images), advised not to create an easy to guess pattern (e.g. straight line) and encouraged not to click on obvious objects (e.g. edge, centre of each image).

Try to click on various areas, not only on an obvious object Please avoid predictable patterns (e.g. straight line, edges, central of images, etc)

The next section of this paper highlights the methodology, followed by the results, discussion and conclusions.

Methodology

A graphical software prototype known as the Enhanced Graphical Authentication System (EGAS) was developed using Microsoft Visual Basic 2008. EGAS is an alternative graphical authentication employing a combination of both click and choice-based methods. In the EGAS software prototype, users are given the freedom to choose their preferred number of clicks (secret clicks), with the software assigning the number of images (secret images) they need to choose. Table 2 shows the combination of secret clicks and secret images. Two types of data collection were implemented; named as 'internal' and 'external'. Internal means the experimenter observed participants during trial (similar with the one to one usability testing) and they had to complete current task before proceeding to the next (controlled by the software prototype). Participants within the external group had to install the software prototype into their personal computer and use it for three weeks, with all of their activities recorded into a database (no means of control was enforced by the software prototype).

Participants for both groups (internal and external) had to register their details (username and secrets) in the software prototype, were then required to log into the software using their chosen secrets and finally provide feedback via a questionnaire. All tasks were done within the software prototype.

During the secret registration (enrolment), the GPG were first displayed to them (by which they had to acknowledge the GPG) before they chose their secret. During image selection, participants were able to choose images from 10 different themes (buildings, abstract, food, animals, flowers, view, people, sport, transport and fruits), with each of them consisting of 9 distinct images (arranged in 3x3 grids).

Participants within the internal group were asked to login three times, while the external group needed to login on four different days in week 1, two different days in week 2 and finally login once in week 3. This aimed to examine their familiarity and competency (e.g. login time, clicking accuracy, total attempts).

The trial was conducted over two months with the participants of the internal group recruited via an open call for volunteers within the authors' university. Participants of the external group were colleagues/friends of the author (external to the University) and invited via email, chat messengers and text messages.

The data were interpreted and reported into five main categories; namely number of attempt, timing, pattern, accuracy and finally users' feedback. The number of attempt looks upon participants' failure and success trials during both registration and login tasks while timing reports the time needed for these tasks. Pattern discusses the occurrences of 'hotspot' and 'hot-image', with accuracy mainly focuses upon the participants' ability to click on their secret clicks and finally users' feedback reports participants' perception on the questionnaire.

Results and Discussion

In total, there were 48 participants participated. Table 3 gives information for both groups highlighting the gender split and number of participants who had previously participated in graphical password studies [START_REF] Jali | Assessing image-based authentication techniques in a web-based environment[END_REF]. Participants who changed their click decided to choose the lowest click. Of the total seven participants who initially chosen three clicks on each image, five of them went to one click, while the remaining chosen two clicks. Moreover, all five participants who initially chosen two clicks and one participant who initially chosen four clicks also decided to choose one click.

During login, all participants within all click groups performed well where they managed to login, these results improved with experience. Only ten participants recorded a complete failure to login. There were six occurrences of failed attempts for login one, four occurrences for login two and only three occurrences for login three. The ability of participants to login with fewer failed attempts suggests participants performance improved with experience.

External group

With eighteen participants within this group, the software recorded a total of 283 login attempts in week one, 61 trials for week two and finally 30 for week three. Of these, there were 92 successful logins for week one, 51 for week two and 20 for week three (note that there were participants who logged into the software more than was asked for).

Investigation of successful usernames who continued with the login tasks found mixed results. It was found only 12 participants followed the login interval task, with the remaining 6 participants using the software occasionally. For those who logged into the software according to specified tasks, 9 participants had chosen one click, 1 participant chose two clicks and 2 participants chose five clicks. Analysis has also found that 6 participants (who did not complete the login tasks) infrequently login during week one, with three of them logged twice for week two and finally all of them logged into the software in the third week. Five of them had chosen one click, while the remaining participant went for five clicks.

Only eight of the external group participants managed to register by using their first username. Of the remaining 10 participants who used a second username, six of them changed their secret click to the least click. Unless otherwise stated, most of the analysis for this group was based upon 18 participants who completed the specified tasks.

Timing

Internal group

The time for participants to register and then log into the software prototype was recorded with the time during registration calculated from the point when they pressed the 'register account' button until to the result for registration is displayed. The time for login was calculated from when the participant started to enter their username until the last click for their secret images.

Table 4 shows participants' time (average, shortest, longest and standard deviation) during registration and three logins, in minutes, (m) and seconds, (s). For all click groups, the registration time can be considered long due to the action of selecting images and then clicking on the chosen images. It can be reported that for all click groups, the time to login during login attempts one to three are significantly shorter. The study also found that participants do not immediately select their click area, often taking several seconds before they start clicking on it. This action is believed to be due to the small tolerances used, which suggests it could directly affect login time and security if the users were observed.

External Group

Table 5 shows the time for 12 participants as they managed to login according to the specified login intervals. L1 to L5 refers to the login times (measured in seconds, (s)) for week one, L6 and L7 are login times for week two and finally L8 refers to the login time for the third week. It was found that the login time across the three weeks varied, although with one click, participants showed little change.

Accuracy

As reported earlier, the numbers of failed attempts during registration were high. As a result, participants had to use other usernames and changed their preference secret click or image. The authors discovered two main errors associated with such scenario, as indicates below.

a) Participant was unable to click within the allowable tolerance. b) Participant did not click in sequence order, as the result of forgetting their secret order or areas.

From the data for both internal and external groups, it can be revealed that errors during both registration and login were correlated with participants who selected more clicks. In specific, there were slightly more participants who made tolerance errors than order errors. This is probably due to the software prototype using a small click tolerance.

Particularly within the external group, participants were unable to click accurately when they first started using the prototype. However, they managed to click within the clickable areas as they became familiar with using the software and understood what they needed to accomplish.

Pattern

Patterns are created during image selection when participants chose the same images (in the case of changing username of click), gender skew selection (e.g. men choosing sports car while women chose flowers) and following image order (e.g. participants choosing the first image in each theme). Moreover, patterns during the click selection are created when participants clicked on the same area across all images, producing obvious shapes or clicking their secrets in a straight line (e.g. top, bottom and left side of image area), and clicked on the image that appeared to be offering a pattern.

Results for both groups are reported together within this section as they used similar software prototype.

With the internal group, the study found the majority of participants who changed their username or secrets (click or image) used their previously chosen images. One participant from the five clicks group used both of his previous images while two participants from the two clicks group used three and one of their previous images respectively. Of all the participants from the one click group who changed their username or clicks, only one did not used their previous image. Specifically for the one click group, two participants used four of their previous images while the others were ranging from one to three. In addition, it was also found one of these participants selected the first image for each theme as their secret images.

The external group also used their previous secret images with one participant using all of their previous images, with six other participants using between one to two of their previous chosen images .It was also found that two participants of the one click group chose their images in sequence (choose the first six themes); however their chosen images were different with each other.

Table 6: Image popular with their associated number of male and female. Table 6 presents the number of participants who chose popular images for each theme. It was found that the view and sport themes are the most popular, with the transport and people themes as the least popular selection.

Theme

Although it was found that a number of participants clicked within similar areas when creating their secret clicks, such action was eliminated due to the software prototype preventing participants from clicking on the same area within multiple images.

Analysis was carried out to examine the area of clicking for participants who chose more clicks and although it can be reported that participants with two or three click groups create less obvious pattern, participants of the five clicks group clearly create patterns. The authors deduced that such scenarios are related to the images themselves, which clearly offer a pattern to be created.

Analysis was also done to examine the click areas in popular images for each theme. Analysis on the one-click group who chose the most popular image revealed that ten of the twelve participants who chose popular images in the sports theme clicked on the three most popular areas (see left side of the fig. 1), with seven out of twelve participants who chose the most popular image for the 'view' theme clicked on the same area (see right side of the fig. 1). Equally, all other popular images have shown a pattern where participants clicked on similar spots. From the collected data, the authors summarised that participants who chose more clicks tended to create patterns during their clicking task, while the existence of pattern during image selection was unidentified. Meanwhile, participants who chose more images (fewer clicks) tended to create patterns during both image and click selection. Patterns where users chose the first or last image for each theme was also reported. Although the authors' approach of not implementing restrictions for image selections and depending solely upon the guidelines is less effective then the introduction of guidelines. The GPG itself has resulted in the reduction of gender bias image selection and image order patterns.

It can, however, also be said that the restrictions together with the guideline during secret click selection played a minor role during the click selection task. Although not representative, participants with a higher number of clicks created more patterns (possibly as it is easier for them to remember), with analysis towards one click participants revealing the existence of hotspot.

Users' Feedback

A Likert five points scale rating was used to obtain participant feedback with the lowest score indicating participants' agreement with the statements while the highest score indicating disagreement. Table 7 reports the mean score of feedbacks for the first three questions within the internal group. When asked about participants average login time (with the software prototype displaying their average login time), it can be revealed that twenty participants found their login time were acceptable, with eight unacceptable. Seventeen participants agreed that their total registration time was acceptable while the remaining eleven disagreed. With the statement on the optimum combination of image and click, twenty two of the participants felt that having more images was more memorable than having more clicks, while five participants felt that the balance between both click and images were still memorable.

Participants who were new to the graphical method felt the method could be very useful and provided excellent protection. However, the majority of the participants who were involved in the previous trial felt that having larger clickable areas was more usable. In addition, they felt that having more clicks could be troublesome as they had to memorise too many spots and finally all participants agreed that in order for them to perform better, they needed to become more familiar with the method.

Conclusions and future work

This paper presented an investigation of the practicability of giving guidelines to a user before they chose their secrets for a graphical authentication system as well as evaluating user attitudes and opinions to the enhanced techniques.

During the registration task, participants struggled to click accurately within the allowable click tolerance and those who chose more clicks often failed to click in the correct order. As the result, they had to change to create new accounts or change to fewer clicks. The login task had shown improvement as they managed to login with fewer failed attempts, and the time to login to the software prototype was reduced marginally across login interval. The above findings reflect participants' familiarity with the software prototype as they used the software regularly.

Introducing guidelines to the participants before they start selecting their secrets had obtained positive perception from the majority of participants. However, this study has shown that guidelines on their own cannot guarantee the security and safety of the method itself. This is because participants used their previous images and created secret clicks using easy to remember spots, which resulted in predictable click-areas. By combining the introduction of guidelines with restrictions, user behaviour can be controlled to safeguard the method. This was proven where cases such as clicking on similar areas within the same or multiple images and where creating predictable pattern were reduced.

Finally, this paper has shown that the click patterns created by users who chose more clicks had a direct relationship with the nature of the image itself. It could be said that the introduction of guidelines gave no effect on participants' usability performance, but might give positive or negative effects on the security. The study also suggests that using one click per image is an ideal combination. This is because using one click per image requires less memorisation (i.e. it is more suitable for users with multiple accounts), less time to authenticate, convenience and significantly safer from predictability. The study also suggests that using a small tolerance without giving sufficient opportunity for familiarity to the user could result in a lack of usability of the proposed method.

It is suggested that future work could include a larger and more varied participant based for conducting significance testing to validate the collected data, testing different restrictions with the GPG, further evaluation of the claim that 'one click per image is better' and evaluating the technique known as the 'graphical-passwordsstrength-meter', for safer secret creation based upon feedback from the system itself.

Fig. 1 .

 1 Fig. 1. Participants click areas for the popular image of the 'sport' (left) and 'view' (right) themes.

Table 2 :

 2 Click and Image details used in the software prototype.

	Secret click chosen Secret image assigned Image size/Tolerance
	1	6	200x200 / 7x7
	2	5	200x200 / 7x7
	3	4	200x200 / 7x7
	4	3	200x200 / 7x7
	5	2	200x200 / 7x7

Table 3 :

 3 Participants' information.

		Demographic	Internal group External group
		Male participant	12	10
		Female participant	18	8
		Experienced using GA	10	2
	3.1	Number of Attempt

3.1.1 Internal group

Members of this group undertook 356 of authentication attempts. Of these, 94 logins were successful and 47 failed, 156 failed during registration and 66 were able to register successfully (note that software recorded two trials for each participant if they managed to register).

Table 4 :

 4 Timing for the internal group.

	Click Participant	Time	Registration Login One Login Two Login Three
			Average	5m 23s	24	20	18
	1	18	Shortest Longest	1m 43s 21m 58s	15 42	11 42	9 4
			SD	4m 43s	8	8	6
			Average	10m 29s	40	35	27
	2	5	Shortest Longest	2m 23s 23m 33s	28 71	25 69	18 40
			SD	7m 56s	17	18	8
			Average	9m 56s	39	33	33
	3	3	Shortest Longest	5m 47s 16m 46s	36 43	23 39	22 42
			SD	5m 58s	4	9	10
			Average	2m 56s	26	20	23
	5	2	Shortest Longest	1m 12s 4m 40s	24 28	19 21	21 24
			SD	2m 27s	3	1	2

Table 5 :

 5 Timing for the external group.

	Click Participant	Time	Register L1 L2 L3 L4 L5 L6 L7 L8
			Average 11m 17s 17 20 17 20 14 17 17 14
	1	9	Shortest Longest 47m 23s 23 39 28 37 22 31 43 21 2m 15s 14 14 13 11 12 10 10 9
			SD	14m 2s	4	8	7	10	3	6	11	3
			Average	3m 22s	19 26 21 31 16 15 18 24
	2	1	Shortest Longest	3m 22s 3m 22s	19 26 21 31 16 15 18 24 19 26 21 31 16 15 18 24
			SD	n/a	n/a n/a n/a n/a n/a n/a n/a n/a
			Average	10m 2s	33 29 23 35 25 28 20 27
	5	2	Shortest Longest 17m 25s 37 34 23 48 27 32 20 28 2m 39s 29 24 22 22 23 23 19 26
			SD	10m 26s	6	7	1	18	3	6	1	1

Number of participants choosing popular image Male Female

	Buildings	11	3	8
	Abstract	12	6	6
	Food	8	4	4
	Animals	7	3	4
	Flower	10	4	6
	View	14	7	7
	People	5	2	3
	Sport	13	8	5
	Transport	4	1	3
	Fruits	7	2	5

Table 7 :

 7 Questionnaire results.

	Question	Mean score
	Perception towards graphical password guidelines (GPG)	1.6
	Perception towards restrictions	1.8
	Perception towards combining GPG with the restrictions	1.8