Gang Liu

Gui-Song Xia
email: guisong.xia@whu.edu.cn

Wen Yang
email: wenyang@whu.edu.cn

Liangpei Zhang

Texture Analysis with Shape Co-occurrence Patterns

This paper presents a flexible shape-based texture method by investigating the co-occurrence patterns of shapes. More precisely, a texture image is represented by a tree of shapes, each of which is associated with several attributes. The modeling of texture is thus converted to characterize the tree of shapes. To this aim, we first learn a set of co-occurrence patterns of shapes from texture images, then establish a bag-of-words model on the learned shape co-occurrence patterns (SCOPs), and finally use the resulted SCOPs distributions as features for texture analysis. In contrast with existing work, the proposed method not only inherits the strong ability to depict geometrical aspects of textures and the high robustness to variations of imaging conditions from the shape-based texture method, but also provides a more flexible way to consider shape relationships and high-order statics on the tree. To our knowledge, this is the first time to use co-occurrence patterns of explicit shapes as a tool for texture analysis. Experiments of texture retrieval and classification on various databases report state-of-the-art results and demonstrate the efficiency of the proposed method.

I. INTRODUCTION

As a fundamental ingredient of image structures, texture conveys important cues in numerous processes of human visual perception. While, due to the high complexity of the structures in natural images, the modeling of texture is a challenging problem in image analysis and understanding. Over the past decades, tremendous investigations have been made in texture analysis, see e.g. [START_REF] Leung | Representing and recognizing the visual appearance of materials using three-dimensional textons[END_REF]- [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF], among which an active topic is developing texture models which can efficiently depict both the statistical and the geometrical aspects of textures and are robust to the variations of imaging condition as well.

In order to represent the structural aspects of textures, some mathematical tools, such as Gabor or wavelet-like analysis, are used to probe the atomic texture elements such as elongated blobs and terminators in images, and the marginal/joint distributions of the resulted responses are subsequently utilized to describe the statistical arrangement of texture [START_REF] Leung | Representing and recognizing the visual appearance of materials using three-dimensional textons[END_REF], [START_REF] Portilla | A parametric texture model based on joint statistics of complex wavelet coefficients[END_REF], [START_REF] Zhu | What are textons?[END_REF]. The strong ability of such mathematical tools to handle multi-scale and oriented structures has made them one of the most popular tool for texture analysis. However, how to efficiently represent the highly geometrical aspects of textures, e.g. sharp transitions and elongated contours, is an open problem. To solve this problem, alternative wavelet-like approaches, e.g. Grouplet [START_REF] Peyré | Texture synthesis with grouplets[END_REF] and scattering transform [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF], have been elaborated to enable more efficient representations of structured textures. In contrast with explicit models, patch-based method [START_REF] Varma | A statistical approach to texture classification from single images[END_REF] provides another possibility for describing the structured aspects of textures, but it is not trivial to capture the multi-scale nature of textures by this kind of approaches. to viewpoint and illumination changes, many invariant texture descriptors have been proposed in the literature, including the rotation invariant local binary pattern (joint distribution of gray values on circular local neighborhoods) [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF], the multi-fractal analysis method [START_REF] Xu | A new texture descriptor using multifractal analysis in multi-orientation wavelet pyramid[END_REF], etc.. Recently, several approaches rely on the extraction of local features that are individually invariant to some geometric transforms, such as scaling, rotating and shearing [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF]. Compared with previous works dealing with invariant texture analysis, such locally invariant methods do not need any learning of the deformations. Alternatively, by relying on morphological operations, the shape-based invariant texture analysis (SITA) method [START_REF] Xia | Shape-based invariant texture indexing[END_REF] represents a texture by a tree of explicit shapes and shape attributes are locally normalized to achieve invariant texture description. SITA reported superior performance on invariant texture recognition. One limitation of this work, however, lies in its difficult to take into account high-order statistics of shapes, which has been reported as a crucial factor for texture discrimination [START_REF] Xia | Shape-based invariant texture indexing[END_REF].

Next, for meet the requirement of invariance with respect

Clustering P1 P2 PK h(P1) h(P1) h(P1) h(P2) h(P2) h(P2) h(PK) h(PK) h(PK)

Following the work of SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF], this paper contributes a more flexible shape-based texture analysis framework by investigating the co-occurrence patterns of shapes. The flowchart is illustrated in Figure 1. More precisely, given a texture, we first decompose it into a tree of shapes relying on a fast level set transformation [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF], where each shape is associated with some attributes. We then learn a set of co-occurrence patterns of shapes from texture images, e.g. by K-means algorithm. Taking the learnt shape co-occurrence patterns as visual words, a bagof-words model is finally established to describe the texture. In contrast with SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF], the proposed method provides a more flexible way to consider complex shape relationships and highorder statics on the tree. Moreover, as we shall see, SITA can be regarded as a special case of the proposed one, where only marginal distributions and simple statistics of pair of shapes were taken into account. To our knowledge, the work in this paper is the first time to use explicit shape co-occurrence patterns for the analysis of textures. Several experiments on texture recognition demonstrate the efficiency of the proposed analysis method on various databases.

In the rest of the paper, we will briefly recall the background and related work in Section II. Next, in Section III we present the proposed SCOPs-based texture analysis method in detail. In Section IV, the ability of these features to classify and retrieve textures is demonstrated on various databases. Section IV concludes the paper with some remarks.

II. BACKGROUND AND RELATED WORK

The proposed texture analysis method relying on shape cooccurrence patterns is inspired both by the shape-based texture analysis scheme and texture models using co-occurrence matrix, and is also closely related to the texton-based texture modeling paradigm. In what follows, we briefly recall these backgrounds.

1) Co-occurrence patterns in textures:

Co-occurrence matrices [START_REF] Haralick | Textural features for image classification[END_REF], [START_REF] Davis | Polarograms: a new tool for image texture analysis[END_REF] is still a popular approach for texture analysis. It characterizes image textures with a set of sufficient nonparametric and low-order statistics of pixels. The preliminary use of co-occurrence matrices involved in statistics of pairwise pixel relationships in several predefined fashions. Local Binary Pattern (LBP) [START_REF] Pietikäinen | Rotation-invariant texture classification using feature distributions[END_REF] extended the concept of co-occurrence by developing a framework for studying the statistics of cooccurrent binary patterns. Though, this kind of approaches demonstrated strong capability to characterize random and near random textures [START_REF] Pietikäinen | Rotation-invariant texture classification using feature distributions[END_REF], one limitation of them is, however, a lack of consideration for large-scale and geometrical structures in texture images.

2) Texton-based texture analysis paradigm: Julesz [START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF] found that the first-order statistics of "a few local conspicuous features", called texton, are significant for texture discrimination. The texton theory in fact led to a kind of structural approaches to texture description, which first probe texture primitives as local features and then investigates their organization. An implicit way to implement the texton theory is to use wavelet-like analysis, such as Gabor filter banks, to probe atomic texture elements in texture images and then utilize the resulted filtering responses to describe the underlying statistical texture features [START_REF] Leung | Representing and recognizing the visual appearance of materials using three-dimensional textons[END_REF], [START_REF] Portilla | A parametric texture model based on joint statistics of complex wavelet coefficients[END_REF], [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF].

An alterative implementation is to explicitly detect atomic texture elements beforehand and model the spatial arrangements of such textons. For instance, Zhu et al. [START_REF] Zhu | What are textons?[END_REF] detected textons by using a number of image bases with deformable spatial configurations, which are learned from static texture images. Lafarge et al. [START_REF] Lafarge | Geometric feature extraction by a multimarked point process[END_REF] first defined a set of geometric objects, e.g. segment, line, circle, band etc., as texture elements and then detected those elements and studied their organization through Markov Point Process (MPP). Note that a more general manner is to extract small image patches from texture, cluster them into textons and finally investigate the underlying statistics. Lazebnik et al. [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] extended this idea by removing the redundancy between patch-based textons through utilizing interest regions in images. Compared with the former implicit models, the explicit models can more easily handle structured parts in texture, such as edges and bars, which emerge in high-resolution image textures. However, the computation or detection of such textons is not trivial. It is also worth noticing that modeling the interactions between textons may involve heavy computation.

3) Shape-based invariant texture analysis: The shapebased invariant texture analysis scheme, called SITA in brief, is first proposed in [START_REF] Xia | Shape-based invariant texture indexing[END_REF]. It is based on a complete morphological image representation, called topographical map [START_REF] Caselles | Topographic maps and local contrast changes in natural images[END_REF], which is made of all the connected components of the level lines of images. The idea is to decompose an images into a tree of shapes (by using fast level set transformation (FLST) [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF]) and then develop texture features from the shape ensembles and their relationships. Note that SITA is also a texton-based texture analysis method, if we regard the explicit shapes to be textons in the paradigm. As the analysis scheme use explicit shapes to characterize textures, it demonstrated strong ability to depict the geometrical aspects of texture images, and thanks to the flexible normalization of geometrical transformations from individual shapes, it showed high efficiency for achieving geometric invariant texture features and reported superior performance on invariant texture recognition task. However, the scheme simply assumed that the shape attributes are independent and modeled textures by several marginal distributions. One limitation of such a scheme lies in its difficulty to handle the relationships of shapes, corresponding to high-order statistics on the tree, which is reported to be important for texture discriminations, see [START_REF] Xia | Shape-based invariant texture indexing[END_REF] for more details, where only the scale ratio between pair of shapes were considered and performed better than other attributes.

As mentioned before, this paper tries to combine the shapebased texture analysis scheme and the co-occurrence patterns methods in the texton-based paradigm. It can inherit, from the shape-based texture method, both the strong ability to model the geometrical aspects of textures and the high robustness to imaging conditions changes, but also provides a more flexible way to consider high-order statics on the tree by investigating the co-occurrence patterns of shapes.

III. TEXTURE MODELS WITH SCOPS

This section presents the proposed texture analysis method using shape co-occurrence patterns (SCOPs) in detail, following a short recall on the basis of SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF].

A. Texture modeling by SITA 1) Topographic map: For a gray-scale image u, the upper and lower level sets are defined respectively as χ λ (u) = {x ∈ Ω; u(x) ≥ λ} and χ λ (u) = {x ∈ Ω; u(x) ≤ λ}, for λ ∈ R. The topographic map [START_REF] Caselles | Topographic maps and local contrast changes in natural images[END_REF] of the image u is made of the connected components of the topological boundaries of the upper level sets of the image (they could be equivalently defined from the lower level sets). Observe that the connected components of upper level sets (respectively of the lower level sets) are naturally embedded in a tree structure. Monasse and Guichard combined these two redundant tree structures, by drawing on the notion of shape, and developed an efficient way to compute a hierarchical representation of images [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF], named FLST 1 as mentioned before. A shape is defined as the interior of a level line (the boundary of a level set). Figure 2 shows examples of the topographic map representation of a synthetic image and a texture. 2) SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF]: As the topographic map provides a complete representation of images, the modeling of texture u is converted to the modeling of the tree of shapes. The invariant texture features first rely on classical shape moments, then make use of the hierarchical structure of the topographic map.

The (p + q)th order central moments of shape s is defined as

µ pq = s (x -x) p (y -y) q dxdy, (1)
where (x, y) are the center of mass of s. Denote λ 1 and λ 2 as the two eigenvalues of the normalized inertia matrix of s, with λ 1 ≥ λ 2 , a as its area, p as its perimeter, u(s) to be the gray value of the pixels only contained by s, µ s and σ s as the mean and the standard deviation of gray values of all 1 The codes of FLST are included in the free software MegaWave, and can be downloaded at http://megawave.cmla.ens-cachan.fr/. pixels inside s, s r , r ∈ [1, • • • , M ] to be the r-order ancestor of shape s in the tree, and a max , a min to be two thresholds on shape area, the attributes used for characterizing shape s are given in Table I. As a summarization, the shape attributes of s can be written as,

f (s) = [ǫ, κ e , κ c , γ, α, θ], (2)
each component of which is invariant or robust to different geometrical variations remarked in Table I, respectively. SITA uses the marginal distributions of these attributes of all the shapes contained in an image as features for texture analysis.

B. Shapes co-occurrence patterns (SCOPs)

As explained in previous section, shapes relationship on the hierarchical structure of the topographic map plays an important role in texture analysis. In spatial domain, such shapes' relationship corresponds to local co-occurrence structures in an image. In the topographic map, a hierarchical tree, the main relationships are sibling and conclusion, corresponding to small branches on the tree. If we take such small branches as textons, texture modeling is then to investigate the branches arrangement laws on the tree.

In our context, we define shape co-occurrence patterns as simple and local common branches on the tree of shapes, which reflects specific spatial organization in the topographic map. Observe that, though the shape co-occurrence patterns are local on the tree of shapes, they may correspond to large spatial areas of pixels in the images, which enables us to consider highly geometrical and complex texture elements, such as cooccurred elongated or sharp edges.

1) Common SCOPs: Denoting s r as the r-order ancestor of shape s on the tree, s ′ as the sibling of s and s τ to be the grand-ancestor of s with τ > r, in this paper, we use following four common SCOPs as single shape (P 1 ) : s, shape-ancestor (P 2 ) : s → s r , shape-ancestor-grandancestor (P 3 ) : s → s r → s τ , shape-ancestor-sibling (P 4 ) : s → s r ← s ′ , respectively.

Fig. 3 illustrates two common SCOPs P 3 and P 4 , which are very popular and efficient in texture presentation as they encode rich spatial co-occurrence information.

Two parameters for constructing the SCOPs are the interval order r between the shape and its ancestor, and the levels of the interval τ r . a) The interval r: The interval r controls the correlation between two adjacent shapes in the tree. Observe that a too small r makes no sense as the two adjacent shapes will be almost the same, while a too big r will not be local enough and results in weak descriptive ability. In our context, we proposed to use r, that the difference between the areas of the pair of shapes are lager than the perimeter p of shape s,

r = min{i; a s i -a s > p(s)}, (3)
where s i denotes the i-th order ancestor of the shape s.

Note that r in fact approximates the number of blur around objects in nature images. The final choice of the interval r is the average value given by Eq. ( 3) on all shapes in the images, which corresponds to the averaging blur in textures.

b) The number of cascaded ancestors τ : τ has similar effect for texture description as r. Considering the casual relationship between two cascaded shapes in the tree structure, τ is set to be integer times of r. In our experiments, τ is set to be 2r to achieve better performances.

2) Learn SCOPs with K-means:

As a local common branch on the tree, each SCOP P k actually contains tremendous image or shape realizations described by branch attributes. For the common SCOPs (P k ) k=1,••• ,4 , the attributes are attributes of P 1 : f (s),

attributes of P 2 : [f (s), f (s r )] attributes of P 3 : [f (s), f (s r ), f (s τ )], attributes of P 4 : [f (s), f (s r ), f (s ′ )],
where f (s) is the attribute associated to s.

In order to simplify the problem, we need to quantize the shape realizations of each SCOP into limited number of clusters, named words of a SCOP. Such words can be learned from the tree of shapes of a given set of texture images, as illustrated in Figure 1. In this paper, we use K-means clustering algorithm to achieve this goal. Figure 4 shows several learned words for each SCOP.

C. Texture Descriptor from SCOPs

So far, we have the learned dictionary of visual words for several common SCOPs, in what follows, we then develop texture descriptor from them.

Following the bag-of-words strategy, each texture can be modeled by encoding the ensemble of branches of shapes it contained in the images according to he learned dictionary of SCOPs. Thus the model of a texture t is,

t ∼ [h t (P 1 ), h t (P 2 ), • • • , h t (P K )],
where h t (P k ) is the histogram of the SCOP P k of texture image t, and K = 4 in our case.

As a summary, the whole pipeline of SCOP-based texture analysis method is illustrated in Figure 1.

IV. EXPERIMENTAL RESULTS

This section first explains the experimental setting and how to compare texture images using the model introduced in the previous section. We then investigate the performances of the resulting comparison scheme by confronting it with state-of-the-art texture descriptors [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF], [START_REF] Xia | Shape-based invariant texture indexing[END_REF], [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF], [START_REF] Xu | A new texture descriptor using multifractal analysis in multi-orientation wavelet pyramid[END_REF], on two challenging texture data sets for invariant texture recognition. We replicate, as closely as possible, the experiments described by [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF], [START_REF] Xia | Shape-based invariant texture indexing[END_REF], [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF], [START_REF] Xu | A new texture descriptor using multifractal analysis in multi-orientation wavelet pyramid[END_REF]. These consist of two tasks, retrieval and classification, applied to two data sets UIUC [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] and UMD [START_REF] Xu | Viewpoint invariant texture description using fractal analysis[END_REF].

A. Experimental setup 1) Comparing textures: Given two texture samples u and v, associated with models

h u = [h u (P 1 ), h u (P 2 ), • • • , h u (P K )] and h v = [h v (P 1 ), h v (P 2 ), • • • , h v (P K )
] respectively, we choose to compare histograms through the histogram intersection kernel (HIK), which is widely used for comparing bagof-words model,

Dist(h u , h v ) = K k=1 n k i=1 min h u (P k )[i], h v (P k )[i] . (4)
where h u (P k )[i] is the i-th bin of the histogram h u (P k ) and n k is the number of bins.

Moreover, we also use the approximated geodesic distance to compare two texture samples, as it has demonstrated its capability to improve recognition performances [START_REF] Xia | Shape-based invariant texture indexing[END_REF]. More precisely, based on the computed pairwise distance matrix using HIK as in Eq. ( 4), we construct the k-nearest neighbor graph of the samples (two vertices are connected if one is among the k-nearest neighbors of the other). The geodesic distance between two points is then approximated by the shortest path between them on the graph. This shortest path may for instance be computed using Dijkstra's algorithm.

2) Data sets: We use two dataset, the UIUC [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] database and the UMD database [START_REF] Xu | Viewpoint invariant texture description using fractal analysis[END_REF]. Both of them contain 25 texture classes, each one being composed of 40 samples (i.e. 1000 samples altogether). The UIUC database is of size 640 × 480, and the samples are subject to drastic viewpoint changes, contrast changes or even non-rigid deformations inside each class. See Figure 6 for an example. In contrast, the UMD Database shows strong viewpoint and scale changes, and significant contrast differences. A significant proportion of this database is made of textures consisting in the repetition of objects. Moreover, the resolution of the images in UMD Database is 1280 × 960.

3) Parameters setting: In our experiments, the parameter r is estimated and set to be 5 and τ = 2r for both the two texture data sets. The minimal area a min and maximal area a max of the shapes are chosen as 3 and 8000 respectively. For the 4 common SCOPs, the numbers of clusters in Kmeans algorithm are set to be {100, 200, 300, 300} in the bagof-words strategy, which are used to construct the histogram representation of each texture sample.

B. Retrieval experiments

The retrieval experiment consists in using one sample of the database as a query to retrieve the N r most similar samples in the data set. For evaluation, the average number of correctly retrieved samples (generally called recall) when the query spans the whole database is drawn as a function of N r. Observe that the performances of SCOPs+Geo are largely better than those of [START_REF] Xia | Shape-based invariant texture indexing[END_REF], [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF] on both data sets. More precisely, when the recall number is 39 the retrieval rates of the proposed method are respectively 89.4% and 89.3% on the UIUC and UMD database, comparing with 61.2% and 66.1% of the scattering transform features with geodesics (ST+GEO) and 78.5% and 87.0% of the SIAT approach with geodesics (SITA+Geo).

It is interesting to note that the proposed SCOP+Geo method achieve extremely high retrieval rates on textures with 3-D deformations, for instance 100% it can retrieve the Plaid class in UIUC data set with 100% precision, which is reported to be very difficult to handle, see Figure 6 for an example 2 .

C. Classification experiments

For the classification experiment, the SVM classifiers with the histogram intersection kernel (HIK) is be used to classify the images. Different number of samples (5, 10 and 20 in our experiments) are extracted from each class in the dataset and used as a training set for classification. The final classification rate are the average of that achieved by 200 times random splitting of the data sets.

On the UIUC data set, when the training size is 20, the scattering transform with "log, scale average, multi-scale train" strategy outperforms other methods, while the proposed SCOP gives comparable results. However, when the training size decreases (e.g. from 20 to 5), our SCOP-based method 2 More results can be founded in the supplemental materials. performs much better than all other existing approaches (about 4%). Similar performances are obtained on UMD data set. A quantitative comparison on classification performances of several recent texture analysis methods are given in Table II. So far, we can conclude that the proposed texture analysis approach with SCOPs can achieve comparable classification performance with the-state-of-the-art texture analysis methods when using a large number of training samples, while, it largely outperforms all existing texture analysis approaches when a small set of training samples are available, especially for image retrieval, where only one training sample is at hand.

V. CONCLUSION

This paper introduced a texture analysis framework by investigating the co-occurrence patterns of shapes via bagof-words strategy. The proposed method inherits the good properties from the shape-based texture method, and provides a more flexible way to consider shape relationships and highorder statics on the tree. The experiments of texture retrieval and classification on two challenging texture databases demonstrate that the proposed method has strong ability to depict geometrical aspects of textures and is very robustness to the changes of viewpoints and illuminations. Remark that the SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF] is actually an special case of the proposed method, where the shape attributes are supposed to be independent and only their marginal distributions are adopted for texture characterization. As the method shows great potentials in depicting the geometrical aspects of textures as well as being robust to scale and illumination changes, it may be a good tool for analyzing high-resolution remote sensing images, where thousands of objects with various sizes and colors emerge in the same scene [START_REF] Xia | Structural highresolution satellite image indexing[END_REF]. Another possible work in the future is to use the proposed texture features as visual cues for achieving image segmentation. Fig. 5. Average retrieval performances of different methods on UIUC data set (left) and UMD data set (right). In both figures, the red curves indicate our retrieval results, while the blue and green ones illustrate the results of SITA [START_REF] Xia | Shape-based invariant texture indexing[END_REF] and Scatter Transform (ST) [START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF]. Fig. 6. A retrieval result on the Plaid class in UIUC data set using the proposed method. The image in green rectangle is the query image and the rests are the retrieved ones ranked by their similarities.

Fig. 1 .

 1 Fig.1. The proposed texture analysis method with shape co-occurrence patterns (SCOPs). First images are represented by tree of shapes via Fast Level Set Transform (FLST)[START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF]. The branches of the trees are then collected and partitioned into different clusters, called SCOPs. An image is finally encoded by the learned SCOPs and the corresponding histograms are used as the texture model for analysis.

  Representation of a synthetic image by its topographic map. Left: an original digital image; Right: representation of the image by its tree of shapes, where (A, B, . . . , I) denote the corresponding shapes. (b) Representation of a texture image by its topographic map.

Fig. 2 .

 2 Fig. 2. Topographic map representation, i.e. tree of shapes, of images.

  κc = 4πp 2 /a similarity Contrast γ = (u(s) -µs)/σs affine Scale ratio α = M a/( M r=1 a(s r )) affine Normalized area θ = (ln aln amin)/(ln amaxln amin) affine

Fig. 3 .

 3 Fig. 3. The shape-ancestor-sibling (P 4 : s → s r ← s ′ ) (a) and shapeancestor-grandancestor P 3 : s → s r → s τ (b).

Fig. 4 .

 4 Fig. 4. 4 common SCOPs with several learned words in corresponding row.

Figures 5 (

 5 Figures 5 (a) and (b) show the retrieval results of the proposed SCOPs-based descriptors with geodesic (SCOP+Geo) on the UIUC and UMD database. Observe that the performances of SCOPs+Geo are largely better than those of[START_REF] Xia | Shape-based invariant texture indexing[END_REF],[START_REF] Sifre | Rotation, scaling and deformation invariant scattering for texture discrimination[END_REF] on both data sets. More precisely, when the recall number is 39 the retrieval rates of the proposed method are respectively 89.4% and 89.3% on the UIUC and UMD database, comparing with 61.2% and 66.1% of the scattering transform features with geodesics (ST+GEO) and 78.5% and 87.0% of the SIAT approach with geodesics (SITA+Geo).

  Retrieval performance on UMD dataset[START_REF] Xu | A new texture descriptor using multifractal analysis in multi-orientation wavelet pyramid[END_REF]

TABLE I .

 I

ATTRIBUTES FOR CHARACTERIZING A SHAPE s. FOR THE NOTATION OF SYMBOLS, PLEASE REFER TO THE TEXT FOR DETAILS.

TABLE II .

 II COMPARISON OF CLASSIFICATION ACCURACY ON UIUC[START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] DATABASE AND UMD DATABASE[START_REF] Xu | A new texture descriptor using multifractal analysis in multi-orientation wavelet pyramid[END_REF].

			UIUC			UMD
	Training size	5	10	20	5	10	20
	Lazebnik [3]	87.2	92.6	96.0	84.7	89.1	92.5
	WMFS [14]	93.4	97.0	98.6	93.4	97	98.7
	SITA [4]	91.5	95.0	97.5	95.1	98.7	99.1
	ST [8]	93.3	97.8	99.4	96.3	98.9	99.7
	SCOP	95.8	97.9	98.9	97.1	98.7	99.4
	SCOP+Geo	97.7	98.4	98.7	97.9	98.8	99.3

ACKNOWLEDGMENT

The authors would like to thank Stephane Mallat, who kindly shares us with his scattering transform texture analysis codes. This work was partially founded by NSFC project No.91338113.


Keywords: Android applications, behaviors, logs, HBase, treemapping. Résumé Android applications, comportements, journaux d'événements, Hbase, treemapping

Since they are open, programmable, networked devices, smartphones have become susceptible to various threats. Unfortunately, malicious applications are increasing rapidly and are causing serious damages for users and for their privacy. Thus, it is important to study and know what applications are really doing on Android devices.The purpose of this project is to develop a tool that can display behaviors graphs for Android applications. This will be accomplished by analyzing and visualizing Android Logs, using HBase system and treemapping technique.

Acknowledgement

It is not possible to prepare a project report without the assistance and encouragement of other people. This one is certainly no exception.

On the very outset of this report, I would like to extend my sincere and heartfelt obligation towards all the personages who have helped me in this endeavor. Without their active guidance, help, cooperation and encouragement, I would not have made headway in the project.

I would like to express my profound gratitude and deep regards to M.Abdelkader LAHMADI, my supervisor at LORIA laboratory, for his exemplary guidance, monitoring and constant encouragement throughout the course of this project.

I would like to thank Mme. Hanen IDOUDI, my internship supervisor, for meticulously reviewing and validating this work and checking for its technical correctness. She deserves special praise for his availability, attention to detail and valuable insight.

Many thanks go to Zied FERCHICHI, a computer engineer for his continuous encouragement all throughout this internship and also for his critical comments and beneficial suggestions.

Last but not least, I would like to express my respect and gratitude to the jury members for the honor they have granted me to have wished to examine and evaluate this modest contribution, and all of my professors at the National School of Computer Sciences for the schooling and training they have given me and hopefully that this work will meet up to their standards.

General introduction

Throughout recent years, Android applications have been evolving in a remarkable way because android phones are widespread and gaining popularity. Since these applications have various functions, they acquire various permissions and thus become integrated with our lives, being able to access our email, social networking accounts, financial information, personal photos and even our cars and homes.

Because of the accessibility of Android market, anyone can develop an Android application and upload the developed application on the android market. Since they are open, programmable, networked devices, smartphones have become susceptible to various threats. Unfortunately, malicious applications are increasing rapidly. They cause serious damages, such as making the phone unusable, stealing private information, and sending SMS or phone call for unwanted billing to users. Therefore, it is important to study and analyze efficiently what mobile applications are really doing on Android devices.

Our graduation project fits within this context. We will focus on discovering the behavior of Android applications. In fact, we envision to design a generic and modular tool generating execution models of Android applications. The purpose of our project is to establish behaviors graphs for android applications which represent the different components with detailed information describing every single event related to their executions. This will be accomplished by taking advantage of powerful Android tools which record everything about what happens in Android devices.

General introduction

The structure of our report will be as follows : the first chapter entitled « Preliminary study », introduces the main terminology related to our project and presents a study of the existing similar products and our added value. The second chapter named « Requirements Analysis and Specification» specifies the functional and non-functional requirements followed by the use case models and scenarios examples of the system.

The third chapter entitled « Architecture and Design of the Solution », gives an overview of the architecture of the proposed solution and describes the general and detailed design. Finally, the last chapter « Implementation details » describes the development environment and provides an overview of the achieved work.

General context

Throughout this part, we put this project into its general framework. We focus primarily on presenting the host organization and laboratory, then presenting the host team and finally, exposing the work goals.

Presentation of the host organization : INRIA [N1]

Public science and technology institution established in 1967, Inria is is the only public research body fully dedicated to computational sciences. Combining computer sciences with mathematics, Inria's 3,400 researchers strive to invent the digital technologies of the future.

Educated at leading international universities, they creatively integrate basic research with applied research and dedicate themselves to solving real problems, collaborating with the main players in public and private research in France and abroad and transferring the fruits of their work to innovative companies. The researchers at Inria published over 4,800 articles in 2010. They are behind over 270 active patents and 105 start-ups. In 2010, Inria's budget came to 252.5 million euros, 26% of which represented its own resources.

Presentation of the host laboratory : LORIA [N2]

LORIA is the French acronym for the "Lorraine Research Laboratory in Computer Science and its Applications". It a research unit created officially in 1997 and which is common to CNRS, the University of Lorraine and INRIA.

The laboratory is a member of the Charles Hermite Federation, which groups the four main research labs in Mathematics, in Information and Communication Sciences and in Control and Automation.

The laboratory is structured in five departments :

• Algorithms, Computation, Image and Geometry Department : It connects six teams, sharing scientific interests in some structures, the algorithms to construct or detect them, and their mathematical or algorithmic properties. Such structures typically play a central role in geometric and imaging problems. The department studies several aspects of these structures (combinatorics, algebra, numerics ...) and applies them in different domains (bioinformatics, modeling ...).

• Formal Methods department : It loosely shares common concepts, techniques and tools. It develops the research topics like contribution to logics and proof theory, techniques for the verification of distributed and reactive systems, virology and safety.

• Networks, Systems and Services : The teams of this department tackle problems related to large parallel and distributed systems and the ability that they offer to work, manage, compute and communicate seamlessly on a previously unknown scale, accuracy and spacial distribution. Particular emphasis lies on management and cooperation in modern networks, parallel and distributed computing, and real time aspects. The palette of the applied methods comprises formal modeling and proving, design of algorithms and protocols, implementation of software, experimenting, benchmarking, and the provisioning of research platforms for emulation, simulation and real scale systems.

• Knowledge and language management department : It deals with the three closely related notions of document, language and knowledge. In a wide range of contexts, computational semantics (studying, building and reasoning with meaning) is a common research area. Many activities provide input or output to an end-user, for example in developing natural language-based interface, learning systems, or providing ontologies to experts of a domain.

• Complex Systems and Artificial Intelligence : The scientific activities of this department cover a rather wide range of topics. It's primarily interested in the computational aspects usually related to the notion of complex systems defined as systems of many entities that simultaneously and locally interact closely, and for which the study of the evolution is out of reach of a pure mathematical approach.

Presentation of the team : MADYNES

The research team MADYNES is one of the teams of Networks, Systems and Services department in LORIA. It deals with the design, validation and implementation of new supervision and control paradigms and architectures capable of controlling the increasing dynamicity of services and resistant to scalability induced by the ubiquitous Internet.

The activities of this team cover 4 basic topics :

• Vulnerabilities Management • Large-scale monitoring • Network management • Co-simulation of dynamic ambient networks

Work goals

Our work is a part of Android Environments security (AES). AES deals primarily with vulnerabilities and malicious applications of android devices. In order to facilitate this detection, we aim through this project to design a tool that can describe clearly the behavior of android applications. This tool is supposed to provide users with understandable information regarding what mobile applications are really doing on android devices.

General context

Conclusion

In this part, we put this project in its general context by presenting the host institution, the host team and work goals. In the next chapter, we will focus on the state of art of our project.

Graduation Project Report 2013

Chapter 1

Preliminary study

In the following chapter, we present the state of the art of our project where we treat the different concepts we have studied in order to understand the project. Then, we expose some tools dealing with android application analysis. Finally, we expose our approach.

State of the art

In this section, we treat diverse concepts. We begin by presenting the Android environment. Then, we expose the different components that construct android applications. After that, we detail the core basics of the Android logging system.

Android environment

Android is a software platform for mobile devices that includes an operating system, middleware and key applications. It is based on the Linux operating system and developed by Google and the Open Handset Alliance.

It was built from the ground-up to enable developers to create compelling mobile applications that take full advantage of all a handset has to offer. It was built to be truly open. For example, an application can call upon any of the phone's core functionality such as making calls, sending text messages, or using the camera, allowing developers Chapter 1 : Preliminary study to create richer and more cohesive experiences for users.

Applications are written using the Java programming language and run on Dalvik, a custom virtual machine specifically designed for embedded use. Android relies on modified Linux Kernel version 2.6 for core system services such as security, memory management, process management, network stack, and driver model. It also includes a set of Java libraries that provide the functionalities available in standard Java Programming Language, and C/C++ libraries such as SQLite relational database management system, 3D libraries, Media Libraries etc. [N3]

Mobile malware

Malicious software ("malware") that is designed specifically to target a mobile device system, such as a tablet or smartphone to damage or disrupt the device. It is broadly categorized to include viruses, botnets, worms, and Trojan horses [N4]. Most mobile malware is designed to disable a mobile device, allow a malicious user to remotely control the device or to steal personal information stored on the device. Mobile malware can do just about everything a virus on a PC can do and more. Viruses can bog down the phone's processing speeds, hack the email of the user and send out spam to all his contacts, randomly delete his important files and calendar entries, and initiate system-wide crashes. One of the worst and most recent viruses that targets only mobile phones eventually causes the infected phone to lock up completely, making it unusable. However, some smartphone malware can access camera and photos. It can steal all the images saved on the camera and actually hijack the camera to take photos at random.

Android application components

Application components are the essential building blocks of an Android application. Each type serves a distinct purpose and has a distinct lifecycle that defines how the component is created and destroyed. There are mainly five types of components by which an Android Application is made of. • Activities : Activity is an individual user interface screen in an Android application where visual elements called Views can be placed and the user can perform various actions by interacting with it.

• Services : A service is an Android application component that run in background and has no visual user interface. Services are used to perform the processing parts of your application in the background. While the user is working on the foreground user interface services can be used to handle the processes that need to be done in the background.

A service can be started by another Android application components such as an activity or other services and it will continue to run in the background even after the user switches to another application.

• Content providers : Content providers in Android provides a flexible way to make data available across applications. This is the mechanism used to expose many of a device's data resources for retrieval and update : Contacts, media store, bookmarks, phone-call log, and so on.

Chapter 1 : Preliminary study • Broadcast receivers : Broadcast receivers are used to receive messages that are broadcasted by the Android system or other Android applications. For example, an application can also initiate broadcasts to let other applications know that some data has been downloaded to the device and is available for them to use, so this is broadcast receiver who will intercept this communication and will initiate appropriate action.

• Intents : Intents are the component activating mechanism in Android. They constitute the core message system in Android and define messages to activate a particular component. The most common use of intents is to bind your application components. Intents are used to start, stop and transit between the activities within an application. [B1]

Android logging system

Event logs are text files that record chronologically the events executed by a server or computer application. Each action of a computer system (registration, program installation, web browsing ...) produces a log file. An effective logging strategy has long been recognized by system administrators as a way to keep track of problems with components and applications, provide quantifiable statistics for an application's history, help in troubleshooting issues, as well as help in monitoring the overall health of

systems. [N6]

Android is based on a Logging system which keeps a record of the execution of various applications. These logs contain a lot of information about what is happening on the phone (start/stop an application, access to shared data, connection status change, etc).

Android provides 2 different tools allowing to get access to these logs : logcat and dumpsys.

Chapter 1 : Preliminary study

Logcat

Logcat is a standalone program for viewing log messages contained in logs buffers.

These logs contain a number of metadata fields. Every Android log has a timestamp, an UID( User IDentifier), a PID( Process IDentifier), a priority and a content. The timestamp refers to the date, and invocation time of the log. The UID and PID refer respectively to the application and the process issuing the message. The priority refers to the degree of importance of the log. It is one of the following character values, ordered from lowest to highest priority : V (Verbose), D(Debug), I(Info), W(Warning), E(Error), or F(Fatal). The content represents details of the message which include precise information and have not a standard format. [N7]

Logcat messages can be used to identify the life cycle of an Android application and recognize its behavior. In fact, there are logcat messages which keep record of all events related to an application's components.

Here some examples of these logs :

Intent creation :

Dumpsys

Dumpsys is a tool to gather various information from Android device. It is a very interesting android shell command that dumps the state of various running services and also other system information. [N8]

In fact, it allows to save a snapshot of the system memory to a dump file. There are times when system memory requires analysis but it may not be possible to halt the system and take a normal crash dump. Many problems can be resolved by taking a snapshot of the system memory while the system is running. The dumpsys command performs this function after it determines that there is enough file system space to save a core dump. [N9] After executing the command, there are various service messages are outputted. The first part lists the available services for dumping. In the list, various functional services running on Android device are mentioned like location, connectivity, notification, meminfo and activity.

Then, a detailed dump of each service is listed in a simple string representation.

Keeping track of intents, services, activities, broadcast receivers and content providers of an application is efficient in identifying its whole behavior. Fortunately, Android's dumpsys command can show a snapshot of the current state of affairs. Typing «adb shell dumpsys activity» in a development computer's command window outputs an up-to-date list of actions and events related to all application components. Information found in dumpsys files differ from those found in logs messages. Thus, we can collect additional details about the different components of an Android application. In fact, we find a block dealing with activities where we can find a list of activities records containing numerous characteristics about the activity name, the package implementing it, the location of its code source, device configuration information that can impact the resources used by the current activity and other parameters. Here an example of an activity record belonging to Facebook application. The activity is entitled «FbFragmentChromeActivity» and located in /data/data/com.facebook.katana. The visible attribute is set true, thus, this activity is needed to be shown. Sleeping, when set to true, means that the activity has been told to sleep. The immersive mode is not active ; thus this activity cannot be interrupted with other activities or notifications. The activity covers the full screen and it is waiting for another activity to be visible.

In the dumpsys file, we find a list of active services records during command execution. Each service record contains information about the name, the process, the application, the location and other details defining the current service. The following block describes a service record. Here an example of registered details about a content provider issued by Google maps application : LayerInfoProvider(com.google.android.apps.maps/com.google.googlenav.layer.LayerInfoProvider) package=com.google.android.apps.maps process=com.google.android.apps.maps proc=ProcessRecord{423ec890 2935 :com.google.android.apps.maps/10061}

Chapter 1 : Preliminary study When debug engineering is necessary, a lot of useful information from dumpsys can be retrieved for debugging purpose. Thus, dumped information allows to check how an application behaves and how it affects the overall device.

Study of existing solutions

Many researches have been done in order to deal with android application analysis.In this section, we expose some of the available tools trying to figure out their features and depict their weaknesses.

Androguard

Androguard is mainly a tool written in python for android applications analysis. With its internal decompiler, it retrieves the Java source code of an application from the bytecode. By analyzing the code lines, useful details about the code, its basic blocks, its instructions and the permissions needed can be figured out.

Through an interactive shell, displaying a method, accessing to each field of an instruction, annotating a specific method or an instruction and even renaming classes are possible. As shown in the figure above, information outputted by Androguard are hardly understandable, especially for complex applications. In fact, information about source code will be displayed whithout giving logical relationship between its different portions. Thus, the identification of applications behaviors could not be an easy process.

DroidBox

DroidBox is a standbox which offers dynamic analysis of Android applications. It gives interesting clues about application behavior by providing network traffics, accessed files, data leakages, needed permissions, cryptography operations and SMS/Phone calls. These details are visualized through a graphical report as shown in figure 1.3 :

FIGURE 1.3 -DroidBox report [N11]
DroidBox represents some useful information dealing with the interaction between Android applications and the whole system. It does not give any information about applications components and their interrelationships.

Project approach

Without knowing the source code of applications, we will try to construct execution models of Android applications. The purpose of our project is to establish for android applications behavior graphs which represent the different components with detailed information describing every single event related to its executions. Thus, we aim to take advantage from Android logs which record everything about what happens in android devices.

Our envisioned tool is designed to android applications understanding of different users.

By centralizing logs information in specific server, we obtain dynamic and up-to-date graphs.

Observing applications behaviors in numerous users's devices may be efficient in detecting the normal and the malicious ones.

Chapter 1 : Preliminary study

Conclusion

The preliminary study allowed us to understand the basic concepts of the project and to analyze the strengths and weaknesses of some of the existing Android applications analysis tools. Therefore, this allowed us to get a clearer idea about our envisioned tool and to further refine the whole system's requirements which will be detailed in the next chapter.

Chapter 2 Analysis and specification of requirements

After having provided the theoretical basics that are necessary for understanding the project's concepts, we now start the specification's phase. At first, we are going to list user's needs.

Then more detailed specifications and analysis will be made through use cases diagrams. Finally, we will expose some sequence diagrams in order to bring out the behavioral aspect of the application.

Requirements analysis

In this section, we detail all functional requirements and non-functional ones that must be taken into consideration during our tool development process.

Functional requirements

Our envisioned tool is designed to analyze and visualize Android applications executed in different Android devices. In order to perform these basic functionalities, data from applications users devices are needed. Thus, the whole system has to address different functional requirements for the analyst who will have a global view of all applications of all users and for the simple user who, after making data retrieved from his device available, will visualize only his applications.

Chapter 2 : Analysis and specification of requirements Security : The system should ensure a considerable level of security.Thus,the access to the application should be restricted via authentication mechanisms.

Use cases

To specify in a formal way the required needs by the application, we opted for the realization of some Use Cases Diagrams to have a better understanding of the needs.

General use case

The following use case diagram presents the general functionalities performed by the system. It mentions for each type of users the different services offered for him.

Chapter 2 : Analysis and specification of requirements

Detailed use case

In this section, we focus on refining use cases to better clarify the requirements. We choose for each type of users some use cases to detail.

• Simple user : Send information : detailed use case Android logging system is a basic concept of our approach. Without the availability of logs, the analysis process would not be possible. End-users of mobile applications should contribute to achieve this purpose. Collecting logcat messages contained in logs buffers of each mobile device and then sending them to a server for storage must be performed.

Dumpsys files contain a large amount of efficient data for identifying an application behavior. Thus, users have to store them in the server.

FIGURE 2.2 -Send information use case

Chapter 2 : Analysis and specification of requirements

Visualize the behavior of a chosen application : detailed use case

After choosing an application to focus on, the user can visualize its behavior. The system allows him to display every single event related to its components. It offers him the possibility to gaze at a single application component and display the type of information he wants to know.

FIGURE 2.3 -Visualize the behavior of a chosen application use case

• Analyst :

Consult the list of applications of a chosen device : detailed use case

After authentication, the analyst is able to know the list of known users involved in the analysis process through their devices identifiers. By consulting this list, the analyst has the possibility to choose between available devices. Every Android device has a certain number of installed third party applications. Once the device is chosen, the analyst can consult the list of applications available on it.

Sequence diagrams :

In this section, we choose some scenarios to present through sequence diagrams in order to bring out the dynamic aspect of the application. 1. The scenario begins when the simple user gets access to the tool.

Scenario of application visualization by a simple user :

2. The tool displays the homepage.

3. The simple user choose the simple users interface.

4. The tool displays the authentication page of simple users.

5. The simple user authenticates using his device identifier. 6. The system verifies information introduced by the simple user. 7. The system gives the simple user access and displays the list of applications of his device 8. The simple user choose an application to visualize its behavior. 9. The system displays the behavioral graph of the chosen application.

Chapter 2 : Analysis and specification of requirements 5. The user authenticates using his login and his password. 6. The system verifies information introduced by the android user. 7. The system gives the Android user access and displays the list of users involved in the analysis process.

8. The analyst chooses a user's device from the list and asks to consult its applications 9. The system displays the list of application of the chosen device.

10. The analyst chooses an application to visualize its behavior. 11. The system displays the behavioral graph of the chosen application.

Conclusion

Throughout the requirements analysis and the requirements specification presented in this chapter, we have clearly identified the system actors and the functionalities that the product should offer. Indeed, the next chapter will display the global and detailed design of the solution permitting to perform these requirements.

Chapter 3

Design and structure

Having finished and analyzed the specification of our project in the previous chapter, we focus in this chapter on designing a suitable structure for the application. This step is crucial in the course of the project and aims to undertake and prepare the ground for the implementation phase. We begin by exposing the global architecture of our solution. Then, a detailed description of the architecture components is exposed.

Global design

Since we are working to develop a tool offering users services through visual views, we decided to follow Model-View-Controller(MVC) architecture. This pattern defines a useful separation of concerns which helps developing or changing parts independently. The view is responsible for establishing the different interfaces of our tool(registration, authentication, applications, graphs..). The model deals with the storage of necassary data, mainly analysts information and logs messages. The controller controls, manages and ensures interfacing between users, applications and their graphs.

The MVC architecture ensures to our application the following properties : Maintainability : MVC is designed to be stretchable and evolutionary, and foster the segmentation of responsibilities. It tend to be easier to maintain and thus easier to develop.

Testability :

The various logical layers being separated, it is much easier to test them remotely.

Chapter 3 : Design and structure

Detailed design

In this section, we start by presenting the architecture of our system. Then we move to detail each layer mentioned above in the global design.

System architecture

Figure 3.2 presents the architecture of our system.

FIGURE 3.2 -System architecture

We explain the schema mentioned above by detailing the different system layers designs.

MVC layers designs

In this section, we start by presenting the data structure that we used in the application. After that, we expose the design of controller functionalities. Finally, we focus on the application's view.

Data layer design

In our application, all needed data is centralized in a specific server. Android users have to send logcat and dumpsys messages to this server in order to make them accessible.

Chapter 3 : Design and structure

As for logcat messages sending, we have taken advantage from « Collimator probe », an android application which was designed and developed by Madynes members. Its main functionalities are collecting these logs and sending them to a server for storage.

The Collimator probe is organized under one basic user Interface, the activity Collimato-rActivity, which controls 2 background services :

• LocationService : retrieves geolocation information which is added as an extra string to logcat messages.

• CollimatorService : collects and sends the logcat messages.

Collecting and sending logs were separated. The collected logs are now stored in a buffer before sending them. The reception of each log by the server is done before sending the next log. This has been possible by the use of TCP( Transmission Control Protocol). If an error occurs when when sending, sent data is removed from the buffer, and sending process is restarted a minute later. The following figure presents the collecting and sending processes performed by the Collimator probe : Regarding dumpsys information, users have the possibility to access directly to the server via a secure shell (ssh) connection. Then, they have to deposit the contents of dumpsys files in a specific location. After a connection to the server, the tool can access to this location and explore the data stored there.

Controller layer design

The controller layer encapsulates the core controller functionalities of the application. There, we explain the controller logic by exposing packages and classes diagrams.

Package diagram :

To move to the design, we rely on the principles of object oriented approach. To this end, we

Chapter 3 : Design and structure move from a functional structure through the use cases, to an object structure based on classes and packages.

Given the number of candidate classes defined in our application, it is important to classify them into packages to better understand the overall role of each party and facilitate code maintenance. To identify packages, we relied on two criteria : consistency and independence.

Regarding the first criterion, we tried to group classes that have a strong correlation between them and belong to the same functional area. As for the second criterion, we tried to minimize the dependencies between packages by minimizing the number of connections between them.

The figure 3.4 presents the package diagram of our controller : The diagram package for our application shows the decomposition of our system in four packages :

• ToolDealer : it contains classes dealing with providing the tool functionalities.

• XmlGenarator : contains classes dealing wih XML files generation.

• Dumper : contains classes dealing with dumpsys files treatments. It contains 2 packages :

Objects which handles the definition of all objects classes and treatments which performs dumping actions.

• Logger : contains classes dealing with logcat messages. It contains also 2 packages : objects for objects classes and treatments for logs manipulation.

Classes diagrams :

The

Logger class diagram :

The package logger is composed of 2 subpackages : Objects and Treatments. In order to deal with logcat data, we have defined the following classes which constitute the Objects subpackage :

• Event : the class presenting the logcat message. It contains a description of different fields that constitute a logcat message.

• Trace : it encapsulates the different events associated to a single user.

As for the subpackage Treatments, it contains 3 basic classes :

• Connection : it ensures the connection to the database where the logs are stored.

• HbaseDealer : it contains basic functions dealing with logcat messages.

XmlGenerator class diagram :

The package XmlGenerator uses Dumper and Logger packages in order to structure data into Xml files having a specific format. Each application of each user is presented by an xml files containing logcat and dumpsys information. The ToolDealer contains all classes providing the different services offered to the differents types of users. It contains 7 classes :

• SimpleUser : the class presenting the simple user actor.

• Analyst : the class presenting the analyst actor.

• Administrator : the class presenting the administrator actor.

• Authentication : it deals with the authentication of different types of users.

• Registration : it focuses on the registration process for analysts.

• Displayer : it contains functions dealing with the extraction of the convenient devices and applications.

• Management : it refers to the management tasks performed by the administrator

Conclusion

In this chapter, we presented the general and detailed design of our solution to facilitate the transition to the implementation phase. In the next chapter, we will expose the work realized throughout this project as well as the environment which we will use to develop it.

Chapter 4 Implementation details

This chapter discusses the implementation of the applications components. We begin by presenting the environment on which we worked. Then, we present the development process. Finally, we depict some interesting interfaces of our application.

Work environment

In this section, we will present the hardware and software environment on which we have done our project.

Hardware environment

Our tool was developed on a PC having the following characteristics :

• Operating system : Linux (distribution Ubuntu).

• Processor : Intel Core 2 Duo.

• RAM : 3 Go.

In order to perform its basic tasks, the tool must have access to a distant server where different information are stored.

We have also used Android-based devices, mainly smartphones and tablets in order to depict Android applications behaviors. The component column refers to the type of the event. The datetime gives the invocation date and time of the log. Params is a family of columns giving details about the content of the log. We find in this record additional attributes. The attribute host refers to the device identifier of the sender. The attributes latitude and longitude depict the location information of the sender. These information are given by Collimator Probe, the probe used to send logs messages. The timestamp refers to the date of creation of records.

Logs visualization

The visualization was done via the treemapping technique. A Treemap, also known as After parsing the xml file, the buildXml function returns the corresponding tree to the file's hierarchy. Then, we extract the root of the tree via the getRoot() method. The initialize method constructs the treemap. In fact, it's responsible for identifying the differents elements of the hierarchy, calculate their positions and drawing them. Via setProperties() method, we set different properties of the treemap like size, color or zooming feautures.

Graphs interpretation

In this subsection, we will analyze some of the obtained applications graphs.

Paintball (Game) :

In the graph of figure 4.1, we have one block represented. In fact, this game is based only on activities. In fact, like a major part of games applications, this application focuses on the interaction with users by providing interfaces.

Tool screenshots

In this section, we depict the achieved work through some screenshots of the application.

Home page :

The user has to mention if he wants to get access to the tool as a simple user or an analyst.

Thus, figure 4.5 allows him to do that.

Conclusion

In this chapter, we presented the hardware and development environment in which we created our application. We subsequently presented the most significant steps of our development process. Finally, we depicted some interfaces of our application.

Chapter 1 :

 1 FIGURE 1.1 -Android application components types [N5]

  ServiceRecord4251aa68 com.google.android.youtube/.core.transfer.DownloadService packageName=com.google.android.youtube processName=com.google.android.youtube baseDir=/data/app/com.google.android.youtube-1.apk dataDir=/data/data/com.google.android.youtube createTime=-19m0s343ms executingStart=-18m59s300ms restartTime=19m0s342ms The service is named DownloadService. It is part of Youtube application presented by the package« com.google.android.youtube». The baseDir and dataDir attributes reprensent the lo-Chapter 1 : Preliminary study cation repositories of respectively the installation file and application resources. In the end, the creation, the executing and the restart times are mentioned. Dumpsys keeps track of intents which represent the component activating mechanism in Android. The following example is a record of a start service intent used by Facebook application to start a service entitled belonging to the same application : PendingIntentRecord41965290 com.facebook.katana startService uid=10236 packageName=com.facebook.katana type=startService flags=0x0 requestIntent=cmp=xxxxAll messages broadcasted by the Android applications are also recorded. We mention in the following block an example of a registered broadcast receiver used by the android telephony application. The PID and UID attributes refers to the process and application identifiers dealing with it. This broadcast receiver is associated to a filter which specifies which intents is listening for. In our example, it is listening to the native ACTION_BOOT_COMPLETED which fires once the device has completed its start-up sequence. ReceiverList{4186e4e0 474 com.android.phone/1001 remote :417084a8} pid=474 uid=1001 Filter 0 : BroadcastFilter{418698b0} Action :"android.intent.action.BOOT_COMPLETED" Contents providers related information are outputted by dumpsys command. A list of the recent content providers used by diverse applications executed in the android device is cited.

Figure 1 .

 1 Figure 1.2 depicts the sort of information displayed by Androguard.

FIGURE 1

 1 FIGURE 1.2 -Androguard output [N10]

FIGURE 2. 4 -

 4 FIGURE 2.4 -Consult the list of applications of a chosen device use case

FIGURE 2

 2 FIGURE 2.5 -Manage analysts use case

Figure 2 .

 2 Figure 2.6 describes a normal scenario of application visualization by a simple user : Scenario :

FIGURE 2. 7 -

 7 FIGURE 2.7 -Application visualization by an analyst

  FIGURE 3.1 -MVC pattern

FIGURE 3 . 3 -

 33 FIGURE 3.3 -Collimator probe functionalities

FIGURE 3. 4 -

 4 FIGURE 3.4 -Package diagram of the controller

  FIGURE 3.5 -Classes diagram of the controller

•

  FIGURE 3.6 -Logger class diagram

Figure3. 8

 8 Figure3.8 illustrates the XmlGenerator class diagram :

FIGURE

  FIGURE 3.9 -ToolDealer class diagram

  Heatmap, is an important tool for representing and visualizing a lot of information at a glance. A treemap displays hierarchical relationships through a set of rectangles, sized proportionately to each data point, clustered together into one large rectangle. The rectangular screen space is divided into regions, and then each region is divided again for each level in the hierarchy. Treemaps show part-to-whole relationships with each rectangle in the treemap representing a category from the dataset. The nested regions show hierarchical relationships and allow for quantitative comparisons of attribute values [N16]. In order to integrate the treemap in our application, logging information about each application of each user have been gathered in Xml files having the following format : < ?xml version='1.0' encoding='ISO-8859-1' ?> < !ELEMENT root (label,(branch |leaf)*)> < !ELEMENT branch (label,(branch|leaf)*)> < !ELEMENT leaf (label,weight,value) > < !ELEMENT label (PCDATA) > < !ELEMENT weight (PCDATA) > < !ELEMENT value (PCDATA) > Then, we have developed an appropriate algorithm of treemapping. The following pseudo code describes the basic instructions of our algorithm : Algorithm 2 Treemapping Require: f ileN ame Ensure: treemap tree ← BuildXM L(f ileN ame) root ← tree.getRoot() treemap ← initialize(root) treemap.setP roperties() return treemap

FIGURE 4 .

 4 FIGURE 4.1 -Paintball graph

FIGURE 4 .

 4 FIGURE 4.2 -Facebook graph

FIGURE 4 . 4 -

 44 FIGURE 4.4 -Telephony graph

FIGURE 4 .

 4 FIGURE 4.5 -Home page

FIGURE 4 . 6 -

 46 FIGURE 4.6 -Analyst home page

FIGURE 4 .

 4 FIGURE 4.11 -Logcat information interface

FIGURE 4 .

 4 FIGURE 4.12 -Logcat attributes view

FIGURE 4 .

 4 FIGURE 4.17 -Management view

FIGURE 4 .

 4 FIGURE 4.18 -Simple user homepage

FIGURE 4 .

 4 FIGURE 4.20 -Simple user application view

: Preliminary study Content provider update : 03

  -28 21 :47 :11.140 14447 18610 I content_update_sample : [content ://com.facebook.katana.provider.CacheProvider/cache/name/notifications_history,

	update,201,41]
	Broadcast receiver start :
	03-29 12 :12 :13.175 2806 2981 I am_proc_start :
	[28450,10063,com.google.android.apps.uploader,broadcast,
	com.google.android.apps.uploader/.ConnectivityBroadcastReceiver]
	03-29 09 :27 :58.240 280 2871 I am_new_intent :
	Service creation :
	03-29 04 :47 :32.559 2806 2869 I am_create_service :
	[1085277064,com.facebook.katana/.service.FacebookService,act=com.facebook.katana.service.51,
	14447]
	Activity restart :
	03-29 06 :55 :00.005 2806 2812 I am_restart_activity :

[10866059362,com.sec.android.app.twlauncher/.Launcher,android.intent.action.MAIN, NULL,NULL,274726912] [1085169744,10,com.sec.android.app.clockpackage/.alarm.AlarmSmartAlert] Chapter 1

  table containing logs is described by the following table :

	Field	Type	Description
	id	bigint(20)	Primary key identifying each log
	host	var(128)	A unique identifier for android devices
	timestamp	var(24)	Invocation date and time of the log
	resource	varchar(100)	The application issuing the message
	component varchar(100)	The application's component issuing the log
	params	text	The message itself
	longitude	varchar(32) Longitude registered the time of log invocation
	latitude	varchar(32)	Latitude registered the time of log invocation
	connection varchar(30)	The connectivity type, namely wifi or mobile
			TABLE 3.1 -Logs table

In order to manage analysts, we have dealt with Analyst table which contains specific information about analysts.

List of tables

So, we can define the following functional requirements depending on the type of system user :

• Simple user :

Send logcat messages :

The identification of an application behavior is strongly based on logcat messages which are internal to the Android device. Thus, the system should permit to user to make this sort of information available for use and exploration.

Send dumpsys messages :

The rich content of dumpsys files is efficient in the analysis process of Android applications. So, the user should have the possibility to provide this valuable data for analysts.

Authenticate :

In order to get access to the application, the simple user should be authenticated. Authentication is done through the use of Android device's identifier.

Consult the list of applications :

The simple user could consult the list of applications executed on his device and choose which application to visualize.

Visualize applications behaviors related to his device :

The system should allow the Android user to visualize the application's behavior and display detailed information about its different components.

• Analyst :

Authenticate :

In order to get access to the application, the analyst should authenticate. Authentication is done through the use of logon passwords (login+ password).

Consult the list of devices involved in the analysis process :

The system should allow the analyst to consult the list of the contributing devices and choose which device to explore.

Consult the list of applications executed on each user device :

The analyst should have the possibility to consult the list of applications available in the concerned device.

Visualize applications behaviors :

The analyst could visualize the application's behavior of each user and display detailed information about its basic components.

We can define also the administrator, who is an analyst, having the additional task of managing analysts. His core management functions are :

Adding analysts :

The administrator has the possibility to add analysts by confirming their registrations submissions.

Deleting analysts :

The administrator has the possibility to delete analysts.

Giving the administrative rights to analysts :

The system should allow the administrator to give analysts the right of administration.

Non functional requirements

The required system has to deliver specific and measurable improvements in : Availability : The system must be continuously available.

Fluidity :

As every posted data in the application needs to be updated periodically, refresh actions must be transparent for end users to maintain tool stability.

Response time :

The user should find out the information needed as fast as possible so generated graphs have to be instantly and easily understood.

Usability :

The tool should also be intuitive and simple to use. The analyst should be able to easily process the actions needed without any special training.

Maintainability :

The different modules of the application must be legible and understandable in order to maintain and update them quickly and easily.

Scenario of application visualization by an analyst

Dumper class diagram :

Like the logger package, the dumper package is composed of Objects and treatments subpackages. Figure 3 The subpackage Objects contains all objects classes needed to classify dumpsys information into android components categories. We have defined the following classes :

• ActivityRecord : it defines the Activity component of an android application.

• Intent : it defines a dumpsys information dealing with intents.

• Service Record : it is a service registered in the dumpsys file.

• ContentProvider : it defines the Content provider component of an android application.

• BroadcastReceiver : it's the class which deals with broadcast receivers.

The subpackage Treatments contains the following basic classes :

Software environment JAVA :

Java is an object-oriented language. It is centered on creating objects, manipulating them, and making them work together. This allows to create modular programs and reusable code. Moreover, Java puts a lot of emphasis on early checking for possible errors, since Java compilers are able to detect many problems that would first show up during execution time in other languages.One of the most significant advantages of Java is its ability to move easily from one computer system to another. In fact, Java succeeds at this by being platform-independent at both the source and binary levels and thus allowing to run the same program on many different systems.

[N12]

Because of Javas modularity, robustness and cross-platform capabilities, it has become a language of choice for providing our solution.

Eclipse Indigo :

Eclipse IDE is a free development environment with potential to create development projects implementing several languages, mainly Java language. The specifity of Eclipse IDE is that its architecture is fully developed around the concept of plug-in. This means that all of its features are developed as plug-in. In our project it helped in the development task of our tool.[N13]

HBase :

HBase is a database management system. It is modeled after Google BigTable and is part of the world's most popular big platform, Apache Hadoop. As the open source implementation of Google's BigTable architecture, HBase scales to billions of rows and millions of columns [N14]. Thus, it is well suited for big data sets, which make it, in our application, a great solution for real-time ingestion of log data. HBase is a column oriented database which stores its contents by column rather than by row. Instead of retrieving a record or row at a time, an entire column is retrieved and thus it becomes very powerful and efficient since data analytics are usually concerned with only one field or column of a record. The access becomes much faster, and much more relevant data can be extracted from the database in a shorter period of time. Moreover, HBase allows for many attributes to be grouped together into what are known as column families.

Development process

In this section, we detail the different steps of our project's process.

Logs analysis

In order to make logs messages understandable for users, we proceed with an analysis phase. For each log record, we associate a list of attributes with meaningful names. In fact, we figure out the known attributes. Then, we decompose the long ones. Moreover, we add other attributes related to logs senders (devices identifiers, location, type of connection...) Then, to store this hierarchical data, we have moved from MySQL to HBase. The following pseudo code does this conversion.

Chapter 4 : Implementation details Viber :

Viber is an application for free telephony calls. As shown in the graph of figure 4.3, it uses a considerable number of activities in order to offer its services. We find mainly, but in lower number, some intents, services and broadcasts registered by the logging system.

FIGURE 4.3 -Viber graph

Android telephony :

Android telephony is a system application which interacts with a huge number of applications. This is can be concluded by the presence of many messages related to the broadcast receivers. Figure 4.4 depicts the telephony graph :

Analysts registration :

If he is a new analyst, he should register before getting access to the tool functionalities.

The interface presented by of figure 4.7 permits him to submit his registration :

FIGURE 4.7 -Analyst registration interface

Devices view :

As shown in figure 4.8, the analyst, once authenticated, can consult the list of registered devices and choose one of them in order to explore it.

FIGURE 4.8 -Devices view

Applications view :

Once the device is chosen, the interface of figure 4.9 will be displayed to give him the possibility to consult the list of applications of that device and choose one of them in order to visualize its behavior.

Logcat information interface :

The analyst can focus on a single component and get its logcat information. By clicking a single rectangle or choosing from the tree hierarchy, the analyst can have details about a logcat event related to the chosen component. (figure 4.11)

Dumpsys information view :

The analyst can also get dumpsys information about a specific component.

Dumpsys attributes view :

The analyst can get different attributes associated to a specific element of the hierarchy.

As shown in figure 4.14, he can choose the attribute and click the rectangle associated to it.

FIGURE 4.14 -Dumpsys attributes view

Zooming view :

The visualization can be interactive allowing drilling down into some section of the hierarchy and visualizing it. As shown in figure 4.15, the system offers the possibility of zooming in and out.

Management view :

Administrators can confirm the registrations submissions of analysts. They have also the possibility to give them the administration right or deleting them completely. Figure 4.17 represents the interface permitting them to perform these tasks :

Simple user applications view :

Once authenticated, the simple user gets access the list of the applications executed in his device. Figure 4.19 depicts the interface giving him the possibility to choose which application to visualize.

FIGURE 4.19 -Simple user applications view

Simple user application graph :

The interface 4.20 gives the simple user the possibility to visualize the graph of the chosen application :

Appendix HBase guide

Hbase installation

• To setup a standalone HBase instance, hadoop and hbase installation are surely needed.

• Just like Hadoop, HBase requires at least Java 6 from Oracle.

• To have a running standalone HBase instance, we have to start it via the shell. $./bin/start-hbase.sh starting Master, logging to logs/hbase-user-master-example.org.out

Hbase shell

• After starting HBase, we can connect to your running HBase via the shell. $ ./bin/hbase shell HBase Shell ; enter 'help<RETURN>' for list of supported commands.

Hbase java API

HBase offers a java API permitting to get access to local and distant HBase and performing different operations.

We expose through the following example the basic API calls of HBase :

• We first create an instance of org.apache.hadoop.conf.Configuration. We ask the Configurationn class to create the instance. It will return a Configuration that has read HBase configuration from HBase configuration files found on the program's classpath :

Configuration config = HBaseConfiguration.create() ;

• This Configuration is subsequently used to create instances of HBaseAdmin and HTable, two classes found in the org.apache.hadoop.hbase.client Java package. HBa-seAdmin is used for administering your HBase cluster, for adding and dropping tables. HTable is used to access a specific table. The Configuration instance points these classes at the cluster the code is to work against. To create a table, we need to first create an instance of HBaseAdmin and then ask it to create the table named test with a single column family named data.

HBaseAdmin admin = new HBaseAdmin(config) ;

HTableDescriptor htd = new HTableDescriptor("test") ;

Appendix

HColumnDescriptor hcd = new HColumnDescriptor("data") ; htd.addFamily(hcd) ; admin.createTable(htd) ;

• Operating on a table, we will need an instance of org.apache.hadoop.hbase.client.HTable passing it our configuration instance and the name of the table we want to operate on.

HTable table = new HTable(config, tablename) ;

• We can put a single cell value of value1 into a row named row1 on the column named data. The column name is specified in two parts : the column family name as bytes(databytes in the code above) and then the column family qualifier specified as Bytes.toBytes("1")).

byte [] row1 = Bytes.toBytes("row1") ; Put p1 = new Put(row1) ; byte [] databytes = Bytes.toBytes("data") ; p1.add(databytes, Bytes.toBytes("1"), Bytes.toBytes("value1")) ;