Xiangyang Li
email: lixiangyang806@gmail.com

Minhua Wu

Zhiping Shi
email: shizhiping@gmail.com

The Retrieval of Shoeprint Images Based on the Integral Histogram of the Gabor Transform Domain

Keywords: fragmental images, Gabor filtering, integral histogram, image retrieval

Shoeprint images which are extracted at the scene of cases are a kind of important modern forensic clue and evidence. Retrieving the images of the same or the similar shoeprint images from the database quickly and accurately is very important to criminal investigation. To deal with the fragmental shoeprint images, we propose a shoeprint images matching and retrieval algorithm which computing the integral histogram in the Gabor transform domain. First, through the integral histogram find out the most similar position of the fragmental image in the intact image. Then, extract the features of the region found in the first step. At last, compute the similarity of the two components. Experiment results prove that this algorithm leads an increase of 4.82% in the retrieval precision, compared with computing the global features of two images directly.

Introduction

Shoeprint images are common found at the scene of the crime, which are easy-to-beleft, multiple, specific, relatively stable, continuous. They play a very important role in the criminal investigation and forensic evidence. The traditional methods of managing and retrieving shoeprint images are mainly based on manual coding. For all kinds of shoeprint images, we need to design a coding standard given different coding for different images. Then according to the standard, implement shoeprint images recognition [START_REF] Xiao | Methods on shoeprint matching[END_REF]. The manual coding method relies on the operator too much, so the operator's subjective factors have much influence on the identification result. And at the same time, with the rapid increase of shoeprint images, it's very difficult to achieve a satisfactory result. Retrieving the images according to user's requirements quickly and accurately is related to the efficiency of cases in the department of police. Therefore, it is very important to develop a shoeprint images retrieval algorithm with high retrieval accuracy and high speed.

In general, image features mainly include color, texture, shape and spatial location which are extracted from the entire image or from one region [START_REF] Zhang | A review on automatic image annotation techniques[END_REF][START_REF] Chadha | Comparative study and optimization of feature extraction techniques for content based image retrieval[END_REF]. How to extract the features efficiently is the key of content based image retrieval (CBIR). Shoeprint is imprinting of the sole contact with the ground, so color features is meaningless, only features such as texture, shape and space layout are useful. Guan [START_REF] Guan | Research and realization of recognition for shoe soles based on outline feature[END_REF] had proposed a method of recognition for shoeprint images based on outline features, which find out the outline points at the longest distance according to the truth that the length of shoe sole was longer than any other parts in a shoe sole, and then calculated the angle shaped by the two points and horizontal axes. It proofreaded the shoe soles in terms of calculated angle , extracted 9 features of shoes sole automatically, and then measured the similarity of shoe soles by Euclidean distance. This method uses the global contour features of the image, so it is not suitable when there are fragmental images among the shoeprint images. Jia [START_REF] Jia | Shoe prints identification and classification methods based on texture characteristics[END_REF] had proposed a method which classified the shoeprint images by using the characteristic quantity got from the Laws template convolution of the image. It can identify the type of grain and point pattern. But to complex type such as mixed type, edge block type and circle type, it does not have good recognition efficiency. Xiao [START_REF] Xiao | Methods on shoeprint matching[END_REF] had proposed a method based on PSD (power spectral density) and Zernike moment. But if the segmentation of the shoeprint image is inaccurate, the Zernike moment features do not performs well. Zhang [START_REF] Zhang | Image retrieval based on contour[END_REF] had proposed a method for retrieving multi-texture images based on counter and texture segmentation. Gabor wavelet transform is applied to extract the features of images. It has a higher retrieval precision, but it is not suitable to process incomplete images alignment, because it uses the global features.

To deal with the fragmental shoeprint images, we propose a shoeprint images matching and retrieval algorithm based on the integral histogram in the Gabor transform domain. Filter the image with Gabor filter cluster, use the index of the filter which has the maximum response to replace the gray value of the image in every pixel, and then, compute the integral histogram of the transformed image. Through the integral histogram, find out the most similar position of the fragmental image in the intact image. Then, extract the features of the region found in the former step. At last, compute the similarity of the two components. Experiment results prove that this method provides a higher retrieval precision, and it is adaptive to fragmental image processing.

2

Retrieval process of shoeprint images

The retrieval process of shoeprint images is shown in Figure 1. Firstly, pre-process the images obtained on the scene, and then convert them to binary images. Secondly, index these images based on features extracted from them. Finally, we can implicate image retrieval. Due to the complex environment on the scene of the crime, the incomplete contact between the sole and the ground, and the limit of image segmentation technology, a lot of shoeprint images are incomplete. Therefore, after preprocessing, the images have inconsistent size and integrity. As shown in Figure 2, the fragmental image is only part of the full image.

Shoeprint Preprocessing

Useful information of shoeprint images is included in the binary description of the images, so it is important to determine whether the pixel is shoeprint grains or background. Binary image not only reduces the storage capacity, but also can make big contributions to image identification in the later process. There are four main steps in the binarization preprocessing.

─ Smooth the original image with a low-pass filter to reduce the noise. ─ Divide the images into three parts: the soles, the arch and the heel, the portion rate are 0.45, 0.25 and 0.3. And then every part is divided into 3*3 blocks. The division of shoeprint is shown in Figure 3. ─ To each small block, use the cvAdaptiveThreshold function provided by Opencv 2.4.3 [START_REF] Bradski | Learning Opencv[END_REF] for adaptive threshold binarization., where the first two parameters src and dst are the input and output images, parameter max_val is set to 255, this means the pixel value which is greater than the threshold is set to 255. Parameter adaptive_method is set to ADAPTIVE_THRESH_MEAN_C, block_size is set to the maximum odd value which is not bigger than the width and weight of the small block, the value of the parameter param1 is set to 0. In this way, every pixel is processed by the threshold of the average weighted sum of size b*b from its neighbours. ─ Use morphological operations to process the images to eliminate the noise of the small points, and connect the area broken by binarization.

The binarization results of the images are shown in Figure 4.

2.2

Feature extraction

Shoeprint images are binary images after pre-processing, so texture feature and shape feature are mainly considered. Texture is the basic structure of the surface or attribute of an object. It is generally acknowledged that texture is the grayscale change or color change of the image on the space. Comparing the Hu invariant moments [START_REF] Hu | Visual pattern recognition by moment invariant[END_REF], cooccurrence matrix [START_REF] Gao | GLCM-Based texture feature extraction[END_REF] and Gabor texture feature, the experimental results show that the last one is the best, so we choose the Gabor texture feature as texture descriptor. Gabor filter is widely used in image representation, recovery and segmentation, as well as other fields, which is mainly based on the following two points: First, Gabor filter can simulate mammalian visual cortex simple cells receptive field, which is conformed to the characteristics of visual physiology. Second, Gabor filter is able to obtain the best joint resolution in frequency domain and space domain [START_REF] Sing | Content-Based image retrieval using Color Moment and Gabor texture feature[END_REF]. Texture varies in direction, frequency and extent, and the wavelet transform window can be adaptively adjusted to the change of the window center frequency. Therefore, to extract the texture features of an image, we usually use a cluster of self-similar Gabor wavelets obtained from a mother Gabor wavelet instead of a single one. The Gabor function is a sine wave modulated by Gaussian function. A two dimensional Gabor function h(x, y) and its Fourier transform H(u, v) can be written as [START_REF] Roslan | Texture feature extraction using 2-D Gabor filter[END_REF]:

2 2 1 1 ( , ) exp ( ) 2 2 x y g x y x y x y                (1)   ( , ) ( , ) exp 2 h x y g x y jWx   (2) 2 2 1 ( ) ( , ) exp ( ) 2 2 u W v H x y v u               (3)
where g(x, y) is the Gaussian function, σ x and σ y are mean square errors in x axis and y axis, which determines the shape of the Gaussian envelope, W is the frequency of the sinusoidal function on the horizontal axis. A cluster of self-similar functions, referred to as Gabor wavelets in the following discussion, is now considered. Let h(x, y) be the mother Gabor wavelet, then self-similar filter dictionary can be obtained by appropriate dilations and rotations of h(x, y) through the generating function [START_REF] Manjunath | Texture feature for browsing and retrieval if image data[END_REF]:

( , ) ( ' , '), 1, , m h x y a h x y a m n Z mn     (4)
' ( cos sin ), ' ( sin cos ), / m x a x y y x y n K              (5)
where α -m is the scale factor, S is the number of scales and K is the number of orientations, m=0, 1, …, S-1 and n=0, 1, …, K-1. Assuming that the class of Gabor wavelets contains S scales and K directions, and the frequency ranges from U l to U h , the parameter selection method is as follow:

, 1/(S-1) n a=(U /U ) U =a U h l (n) l σ =(a-1)U /[(a+1) 2ln2] u(n) (n) 2 2 σ =tan(mπ/(2k))[U(n)-2ln2( /U )]/ 2ln2-(2σ ln2/U ) v(n) (n) u(n) (n) (6)
Gabor filter has the characteristics of multi-channel and multi-resolution analysis, through the Gabor filter to extract the features of an image can achieve high resolution in both spatial domain and frequency.

Integral Histogram

Histogram is one of the most widely used features in image recognition and retrieval with high recognition efficiency as it is simple to be calculated. But it cannot be applied to the local alignment of the image because it is the global feature. An improved method is to compute the histogram of the local area we are interested in. Integral Histogram is a method to compute the histograms of all possible target regions in a Cartesian data space with high efficiency [START_REF] Porikli | Integral histogram: a fast way to extract histograms in Cartesian spaces[END_REF][START_REF] Park | Block-based fast integral histogram[END_REF] For the image, H(x, y) is defined as: H(x, y)={Hu, u=1, 2, …, d}, where d is the scope scale of the gray image. H(x, y) is the histogram of the rectangle formed by the origin point and the point (x, y) of the image.

( , ) ( (0, 0, , ))

H x y K R x y  ( 7
)
where K is the operation of computing the histogram. The histogram of any rectangular in the image can be quickly computed from its Integral histogram. In Figure 5, there are four vertices. The histogram of the rectangular shaped by the points A, B, C and D is:

( ( 1, 1, 2, 2)) ( 2, 2) ( 2, 1) ( 1, 2) ( 1, 1) K R x y x y H x y H x y H x y H x y     (8)
When the integral histogram of an image is computed, the histogram of target region can be computed easily using simple arithmetic operations.

The process of the algorithm

To deal with the fragmental shoeprint images, we propose a shoeprint images matching and retrieval algorithm based on the integral histogram in the Gabor transform domain. First, filter the image with the Gabor wavelets. Because the Gabor wavelets are a cluster of self-similar wavelets, so each pixel can get a response value from each filter. In order to transform the image into the characteristics space, use the index of the filter which has the maximum response to replace the gray value of the image in every pixel. Let the original grayscale value of the image is f(x, y), after the transformation, the value '( , ) f x y is defined as: The shoeprint images retrieval algorithm is described as shown in Figure 6.The retrieval process is: Filter the image with Gabor filters cluster, use the index of the filter which has the maximum response to replace the gray value of the image in every pixel, and then, compute the integral histogram of the transformed image. To compute the similarity of the fragmental image and the complete image, first, we need to find out the most similar position of the fragmental image in the intact image through the integral histogram. Then, extract the features of the region found in the first step. At last, compute the similarity of the two components. For the image of similar size, compute the similarity directly according to the histogram using the metric method of histogram intersection.

Experimental Results and Comparisons

In paper, the shoeprint images retrieval algorithm based on integral histogram is implemented in Visual Studio 2010 and Opencv 2.4.3 platform with c++ language. The experiment environment is: Intel Core i5-3470 3.20GHz, Windows 7, 4.00 GB. There are 2000 binary images which are the processing results of the shoeprint images captured on the scene of the crime. To evaluate the performance of the algorithm, we choose 195 images as a test set. There are 13 categories in the test set, and each category has 15 images. The images are binary images with black background after a series of processing, such as denoising, segmentation, etc. Sometimes, there are large black blocks at the edge of an image. The black edge not only doesn't carry characteristics of the image, but also increases the amount of calculation when filtering it. Hence, to each image, we compute its vertical histogram and horizontal histogram.

After this, we can get the effective area of an image. Then, we extract the features of this area. The effective areas of images are shown on Figure 7. As shown in Figure 2, the outside large rectangle is the effective area of the image. The inner small rectangles of the intact image are the most similar position of the fragmental images computed through integral histogram.

Usually the retrieval performance of a CBIR system is measured by precision and recall [START_REF] Chadha | Comparative study and optimization of feature extraction techniques for content based image retrieval[END_REF]. Precision (Pr) is defined as the ratio of the number of relevant images retrieved (N r ) to the number of total retrieved images K. Recall (Re) is defined as the number of retrieved relevant images N r over the total number of relevant images available in the database Nt.

Pr / , Re / r r t N K N N   (10)
Retrieve each image in the test set, and then compute the average precision. Every time, the system returns 15 images which are most similar to the input images, the former, the more similar, and the most similar 13 images are shown. Figure 7 is the shoeprint retrieval system interface showing the retrieval results. We use Pr to measure the performance of different algorithm. Table 1 is a comparison of several different algorithms. They are described as follow.

─ Hu invariant moments features [START_REF] Hu | Visual pattern recognition by moment invariant[END_REF]. Calculate the Hu invariant moments features of the image, and use Euclidean distance to measure the similarity (Hu). ─ Co-occurrence matrix features [START_REF] Gao | GLCM-Based texture feature extraction[END_REF]. Compute the gray level co-occurrence matrix of the image. The matrix is generated by the parameters: step length is 1 pixel and the orientations are 0, 45, 90, 135 degrees. And then, compute the deficit, energy and entropy of these matrixes and use Euclidean distance to measure the similarity (CoMatrix). ─ Extract the GTH feature from the image, and use Euclidean distance to measure the similarity (GTH-E). ─ Extract the GTH feature from the image, use histogram intersection to measure the similarity (GTH-I). ─ Filter the image with Gabor wavelets. For each filter, we can get a middle image after the filtering, compute the mean and variance of the middle image. Use them as the features of the image (GMV), and use histogram intersection to measure the similarity. GMV are multi-channel features get from the filtered image, so it is not suitable to use Euclidean distance to measure the similarity (GMV-E). ─ Extract GTIH features from the image and use histogram intersection to measure the similarity. If the image is fragmental image, find out its most similar position in the intact image, through the integral histogram, compute the feature of the found region (GTIH-I). ─ Use the method of GTIH-I to find out the most similar position. Use Gabor cluster filters to filtering the found region to extract the features. Then use histogram intersection to measure the similarity (GTIH-I-R).

In Table 1, Time is the average retrieve time of one image. The experimental results show that the features extracted by Gabor filters are effective to describe the characteristics of the images. Compared with GTH-I, GTH-E proved that the distance measurement histogram intersection is a little better than Euclidean distance, but the difference is small. GTIH-I search for the local features, so its accuracy is better than GTH-I which uses the global features. GTIH-I-R re-extracts the features of the found region, so it increases the retrieval accuracy obviously. GTIH-I-R improves the precision by 4.82% on average compared with the GMV-E. As shown in Table 2, to measure the similarity of fragmental image and intact image, the result of the method using integral histogram to compute the features of the most similar region is 0.902385. The result of the method using the cluster of Gabor filters to re-extract the features of the most similar region is 0.938849. The results show that the re-extract features has higher retrieval efficiency. Because the re-extract features of the most similar region have no characteristics of other regions, so they are more localized and more accurate.

Conclusion

The paper has presented a shoeprint images retrieval algorithm based on Gabor transform domain. The algorithm can provide a higher retrieval precision, especially when the images contain fragmental ones. The innovation of the algorithm is: use the index of the filter which has the maximum response to replace the gray value of the image in every pixel, and then, compute the integral histogram of the transformed image. Use the integral histogram to efficiently find the region in the intact image which the fragmental one is most similar to; avoid comparing the global features directly. Measure the similarity of the features re-extracted from the found region and the features of the fragmental image, to improve the shoeprint images retrieval precision.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Shoeprint image retrieval process

Fig. 3 .

 3 Fig. 3. The division of the shoeprint Fig. 5. Integral Histogram

Fig. 4 .

 4 Fig. 4. The original shoeprint images and the images after binarization

Fig. 6 . 7 .

 67 Fig. 6. Flow chart of the algorithm Fig. 7. The retrieval result

Table 1 .

 1 The Performance of Different Algorithm

	Algorithm	Percision	Time (second)
	Hu	0.228718	0.002523
	CoMatrix	0.233504	0.011149
	GTH-E	0.396923	4.688564
	GTH-I	0.403077	4.277297
	GMV-E	0.419487	4.580621
	GTIH-I	0.419145	208.085226
	GTIH-I-R	0.467692	317.529205

Table 2 .

 2 Compute the features of the most similar region

	Method		Features (12-demensional)
	The feature of the	0.205336	0.083475	0.139575
	original	fragmental	0.107085	0.063219	0.031357
	image		0.054153	0.038420	0.075421
			0.006755	0.059016	0.007900
	Use the integral	0.183289	0.093500	0.194598
	histogram to compute	0.122024	0.073280	0.038685
	the features directly	0.069721	0.049539	0.127830
			0.008835	0.025142	0.013555
	Use the cluster of	0.194752	0.076310	0.151491
	Gabor filters to re-	0.096853	0.063219	0.033249
	extract the features	0.092727	0.041732	0.062361
			0.007493	0.042909	0.008626

Acknowledgment

This work was supported in part by National Nature Science Found Grants No. 60903141 and No. 61165009. The authors are grateful for the many specific and valuable comments made by the reviewer.


Xiangyang Li
email: lixiangyang806@gmail.com

Shuqiang Jiang
email: sqjiang@ict.ac.cn

, Xinhang Song

, Luis Herranz
email: luis.herranz@vipl.ict.ac.cn

Zhiping Shi
email: shizhiping@gmail.com

Multipath Convolutional-Recursive Neural Networks for Object Recognition

Keywords: multiple paths, convolutional neural networks, recursive neural networks, classification

Extracting good representations from images is essential for many computer vision tasks. While progress in deep learning shows the importance of learning hierarchical features, it is also important to learn features through multiple paths. This paper presents Multipath Convolutional-Recursive Neural Networks(M-CRNNs), a novel scheme which aims to learn image features from multiple paths using models based on combination of convolutional and recursive neural networks (CNNs and RNNs). CNNs learn low-level features, and RNNs, whose inputs are the outputs of the CNNs, learn the efficient highlevel features. The final features of an image are the combination of the features from all the paths. The result shows that the features learned from M-CRNNs are a highly discriminative image representation that increases the precision in object recognition.

Introduction

Visual recognition is a major focus of research in computer vision and machine learning. In the past few years, many works have been done on visual descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Bo | Kernel descriptors for visual recognition[END_REF]. These methods have shown robustness against visual complexities, such as changes in scale, illumination, affine distortions, and pose variations [START_REF] Lobel | Hierarchical joint Max-Margin learning of mid and top level representations for visual recognition[END_REF]. For example the SIFT operator [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], which can be understood and generalized as a way to go from pixels to patch descriptors, applies oriented edge filters to small paths and determines the dominant orientation through a winner-take-all operation. Finally, the resulting sparse vectors are added over large patches to form local orientation histograms. Designing algorithms to get meaningful features is important but requires deep domain knowledge, and it is often difficult to expand the scope and ease of its applicability.

To overcome this weakness of feature engineering, feature learning learns transformations of the data that make it easier to extract useful information when building classifiers or other predictors [START_REF] Bengio | Representation learning: a review and new perspectives[END_REF]. There are a variety of works about feature learning, such as hierarchical sparse coding [START_REF] Yu | Learning image representations from the pixel level via hierarchical sparse coding[END_REF], deep autoencoders [START_REF] Le | Building high-level features using large scale unsupervised learning[END_REF], convolutional deep belief networks [START_REF] Lee | Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations[END_REF], and convolutional neural networks [START_REF] Lawrence | Face recognition: a convolutional neuralnetwork approach[END_REF]. These approaches learn image features from raw pixels through multiple feature transforms layers.

Recent work on convolutional-recursive deep learning [START_REF] Socher | Convolutional-recursive deep learning for 3D object classification[END_REF] is very efficient. Combining CNNs to extract low-level features from RGB and depth image, and RNNs to map the learned features into a lower dimensional feature space, the result of the model outperforms a lot of designed features and algorithms. Compared to standard feed forward neural networks with layers of similar size, CNNs have much fewer connections and parameters, thus being easier to train, while their theoretically-best performance is likely to be the same [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF]. A single convolutional neural network layer provides useful translational invariance of low level features such as edges and allows part of an object to be deformable to some extent. Recursive neural networks, combine convolution and pooling into one efficient and hierarchical operation, project inputs into a lower dimensional space through multiple layers. Concerned about the multi-facet nature of visual structures, Bo et al. [START_REF] Bo | Multipath sparse coding using hierarchical matching pursuit[END_REF] proposed multipath hierarchical matching pursuit. Discriminative structures, which we want to extract in feature learning procedures, may appear at varying scales with varying amounts of spatial and appearance invariance. Multipath hierarchical matching pursuits capture the heterogeneity, and build it into the learning architecture.

Motivated by this, and using the simplicity and high efficiency of convolutionrecursive neural networks (CRNNs), we propose multipath convolutional-recursive neural networks (M-CRNNs). The overview of this framework is illustrated in Fig. 1.

A single path M-CRNNs is built upon a single-path CRNNs and learns features through many pathways on multiple bags of patches of varying size, by encoding each patch through multiple paths with a varying number of layers. The M-CRNNs architecture is important as it significantly and efficiently expands the richness of the image representation and contributes to improvement to image classification.

The remainder of this paper is organized as follows. In section 2, we propose M-CRNNs model and present learning procedures in detail. In section 3, experiment results are presented and discussed. Finally we conclude the paper in section 4.

Multipath convolutional-recursive neural networks

In this section, we describe our multipath convolutional-recursive neural networks. We first learn CNNs filters and then feed image patches into CNNs layers. The invariant features extracted from CNNs are given to recursive neural networks. RNNs learn higher order features that represent the image. All features from different paths are concatenated to form the final features that can then be used to classify images.

Convolutional neural networks

The main idea of CNNs is to convolve filters over the input image to extract distinctive features. We convolve an image of size (height and width) L d with N square filters of size P d , resulting in N filter responses, each of dimensionality 1

L P d d   .
We then pool them with square regions of size l d and a stride size of s, to obtain a pooled response with width and height equal to ( 1 ) / 1

L P l r d d d s      .
So the output Y of the CNNs layer applied to one image is a N r r   dimensional 3D matrix. We apply this same procedure to both RGB images and grayscale images separately.

The structure of our layer of CNNs is similar to the one proposed by Jarrett et al. [START_REF] Jarrett | What is the best multi-stage architecture for object recognition[END_REF]. Different systems use different strategies to construct filters to extract features from images. For single layer models, filters sometimes are hard-wired, such as Gabor Wavelets [START_REF] Serre | Object recognition with features Inspired by visual cortex[END_REF]. For multi-stage vision systems, there is no prior knowledge that would conduct us to design sensitive filters for the second or higher layers. Hence filters are learned using supervised or unsupervised methods in many models. We use Predictive Sparse Decomposition (PSD) [START_REF] Kavukcuoglu | Fast inference in sparse coding algorithm with applications to object recognition[END_REF] and k-means to learn the filters.

A single stage of CNNs model includes four layers: filter bank layer, rectification layer, local contrast normalization layer and average pooling and subsampling layer. In the filter bank layer, the input is a 3D array with 1 n 2D feature maps of size 2 3 n n  . Each element is denoted as ijt x , and each map is denoted as i x . The filter bank has N filters. Each filter ij k has a size of 1 2 l l  , and transforms the input feature map i x into the output feature map i y . The module computes: ( )

j j ij i i y g f k x     ( 1
)
where f is a nonlinear function such as tanh,  is the 2D discrete convolutional operator and j g is a trainable scalar coefficient. The output of the filter bank layer is a 3D array y composed of N feature maps of size 1 2 m m  . We have

1 2 1 2 3 2 1, 1 m n l m n l       .
The rectification layer simply applies the function:

| | ijk ijk y x 
. The third layer performs local subtractive and divisive normalizations, enforcing a sort of local competition between adjacent features in a feature map, and between features at the same spatial location in different maps. The objective of average pooling and subsampling layer is to build robustness to small distortions, which plays the same role as the complex cells. Output value is

, , ijk pq pq i j p k q y w x     
, where pq w is uniform weight window ("boxcar filter"). Each output is then subsampled spatially by size S horizontally and vertically.

For multi-layer CNNs models, the higher layer feature extractor is fed with the results of its prior layer. The feature extraction procedure is the same as in the singlelayer model.

Recursive neural networks

Recursive neural networks have been used in natural language parsing [START_REF] Socher | Learning continuous phrase representation and syntactic parsing with recursive neural networks[END_REF]. The main idea of RNNs is to learn hierarchical feature representations by repeatedly applying the same neural network recursively in a tree structure. Unlike previous works, the structure of the RNNs we use allows each layer to merge blocks of adjacent vectors instead of only pairs of vectors. Each image is denoted as a 3D matrix X  K  r  r , and the columns are K-dimensional. We define a block to be a list of adjacent column vectors which are merged into a parent vector p  K . In our work, we only consider square blocks. Blocks are of size K w w   . For example, if we merge vectors in a block with 5 w  , the input of one merging procedure is a structure of total size 5 5 K   . In general, we have w 2 vectors in each block. The neural network for computing the parent vector is:

2 1 . . . w x p f W x                          (2)
where the parameter matrixW

2 K b K 
, f is a nonlinear function such as tanh. Eq. (2) will be applied to all blocks of vectors in X with the same weights W. The structure of recursive neural networks is illustrated in Fig. 2. In our work N RNNs are used, each of which output a k-dimensional vector. So the output of RNNs is a NKdimensional vector.

Multipath convolutional-recursive neural networks

In many visual recognition models, images were regarded as unordered collections of small patches, such as in the bag-of-features model. These traditional models do not consider the spatial positions of patches and relationships between patches, which are useful for visual recognition. The spatial pyramid pooling strategy overcomes this drawback by organizing patches into spatial cells at multiple levels and then concatenating them to a long feature vector [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF]. The compelling advantages of spatial pyramid model are: ─ The pyramid model generates a larger number of features and decreases the chance of overfitting. ─ Adds local invariance and stability of the learned features using spatial pooling. ─ It can capture invariant structures at multiple levels, because of different pooling sizes in the pyramid.

A single path convolutional-recursive neural network has the first two advantages. To combine the advantage of multiple patch sizes and the strength of hierarchical architectures, our multipath convolutional-recursive neural networks learn image features in multiple pathways, varying patch sizes and number of layers. Different paths with different receptive fields can capture different features. This combination of layers contains more information.

Fig. 2. Recursive neural network

The overview framework can be seen in Figure 1. Images of different size are put into CNNs to get low-level features. Each path corresponds to a specific patch size and number of layers. The final layer of each path is a feature vector for the whole image. All the features are then concatenated and used by a svm classifier for object recognition. The inputs of P1 and P3 are grayscale images, and the inputs of P2 and P4 are RGB images, so the features we finally get not only contain gray information, but also contain color information.

Experimental results

In this section, we report the result of M-CRNNs for object category recognition. All our experiments are carried out on Caltech-101. The dataset contains 9,144 images of 101 object categories and one background category. Following the standard experi-ment setting, we trained models on 30 images and tested on no more than 50 images per category.

For the grayscale path, we first pre-process images with a procedure similar to [START_REF] Pinto | Why is real-world visual object recognition hard[END_REF]. First, we convert the image to grayscale and resize it with its largest dimension set to 151 pixels, while preserving its aspect ratio. Second, we subtract its mean deviation. Third, we apply divisive normalization. Finally, the image is zero-padded to 143 143 pixel. For the RGB path, the image was resized to 143 143.

Random filters and unsupervised learned filters

While convolutional pooling architectures can be inherently frequency selective and translation invariant, even with random weights [START_REF] Saxe | On random weights and unsupervised feature learning[END_REF], the filters in our model can be set to random values and kept fixed. In our framework, the filters convoluted with the RGB images are learned by k-means, and the ones convoluted with the grayscale images are learned by PSD. We compared the performance of learned filters and random-fixed filters in Table 1.

We estimate the accuracies of random filters and filters learned by PSD on the model. PP1 denotes: one-layer CNNs with 256 filters of size 9 9, 10 10 boxcar, 5  5 down-sampling (ds), and three-layer RNNs. PP2 denotes two-layer CNNs, the same configuration as P3 (as described in 3.2). Prefix R denotes the filters are randomly initialized, and PSD means the filters are learned in an unsupervised way using of PSD. As we can see in Table 1, for one-layer CNNs, the performance of the leaned filters and the randomly initialed one are nearly the same, but in two-layer CNNs, the learned ones are much better. So, the filters in our work are leaned through unsupervised training. The final features of an image are the concatenated features extracted from all the paths. The accuracy of different paths is shown in Table 2. Generally speaking, P1 works well for object classification due to its hierarchical architecture. Compared with the accuracy 65.5 of [START_REF] Jarrett | What is the best multi-stage architecture for object recognition[END_REF], the architecture of P1 illustrates that CRNNs works slightly better than single CNNs. Different paths can capture visual invariant features at different scales. By concatenating the entire paths, the combined features have higher accuracy than each single path.

Comparison to other methods

In this section we compare our model to related models in literature in Table 3. SVM-KNN [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF] is a hybrid of SVM and NN which focus on shape and texture. Soft threshold coding (SIFT+T) [START_REF] Coates | The importance of encoding versus training with sparse coding and vector quantization[END_REF] and spatial pyramid matching [START_REF] Zhang | SVM-KNN: discriminative nearest classification for visual category recognition[END_REF] approaches based on SIFT features. Invariant predictive sparse decomposition (ISPD) [START_REF] Kavukcuoglu | Learning invariant features through topographic filter maps[END_REF], convolutional deep belief networks (CDBN) [START_REF] Lee | Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations[END_REF], convolutional neural networks (CNNs) [START_REF] Jarrett | What is the best multi-stage architecture for object recognition[END_REF], and deconvolutional networks (DN) [START_REF] Zeiler | Deconvolutional networks[END_REF] are approaches of hierarchical feature learning.

Our method outperforms many SIFT-based approaches as well as hierarchical feature learning methods.

Conclusion

We have proposed multiple path convolutional-recursive neural networks to learn meaning full representations from raw images. The proposed method combines convolutional neural networks and recursive neural networks, and learns the filters in an unsupervised way, which allows for parallelization and high speeds. Learning features through several pathways with varying number of layers, makes the visual features capture invariances at different scales. The architecture feeds grayscale patches and RGB patches to the CNNs, so it contains gray information and color information. Our future work will aim at the combination of multiple paths and deep convolutional neural networks.

Fig. 1 .

 1 Fig. 1. Architecture of M-CRNNs

4

  downsampling step. The output of a 3D matrix of size 256 44 is fed to a two- layer CNN with 128 RNNs. The final output of P1 is a 256 128 vector. Path two (P2) is done on RGB images. First, 400000 random patches of size 9 9  3 are extracted. Then the patches are normalized and whitened. Pre-processed patches are clustered into 256 centers by running k-means. The boxcar filter and ds of the one layer CNNs are both 5 5. The output feature of size 256 2727 is fed to a three layers RNNs. The size of the filters is 9 9 3 pixels (see Fig. 3). Path three (P3) has two layers CNNs and three layers RNNs. The first stage of CNNs is with 64 filters of size 17 17, 7 7 boxcar and 5 5 ds. The second stage of CNNs is with 256 16=4096 filters of size 7 7, 3 3 boxcar and 2 2 ds. Path four (P4) has one stage CNNs and two stages of RNNs. The size of filters is 19 193. The filters in our architecture are shown in Figure 3. Left are the 64 filters of P1 in the first CNNs layers. In the middle, there are 64 filters in path P3 of the first CNNs layers. Right are the 256 filters in P2.

Fig. 3 .

 3 Fig. 3. Visualization of filters

Table 1 .

 1 Random filters and filters learnedWe outline the four paths used in our experiment with multipath convolutionalrecursive neural networks in our experiments.Path one (P1) is done on gray images. First images are pre-processed, two stages of CNNs and two stages of RNNs are performed to extract the features. The first CNN stage has 64 filters of size 9 9, 10 10 boxcar filter, and 5 5 ds. The second CNN stage is composed of 256 output feature maps, each of which combines a random subset of 16 feature maps from the first one. So the total number of convolutional filters is 256 16=4096. The average pooling model uses 6x6 boxcars filter with a 4

		R-PP1	52.6995	R-PP2	56.9440
		PSD-PP1	52.5976	PSD-PP2	65.7046
	3.2	Architecture of M-RCNNs

Table 2 .

 2 Accuracy of each path

	P1	66.9610	P4	56.9779
	P2	56.1290	P2+P3	71.4092
	P3	65.7046	P1+P2+P3+P4	72.1902

Table 3 .

 3 Classification accuracy on Caltech-101

	SIFT+T	67.7	CDBN	65.4
	SPM	64.4	CNNs	65.5
	SVM-KNN	66.2	DN	66.9
	IPSD	65.5	M-CRNNs	72.1

Acknowledgements

This work was supported in part by National Natural Science Foundation of China: 61322212 and 61350110237, in part by the Chinese Academy of Sciences Fellowships for Young International Scientists: 2011Y1GB05, in part by the Key Technologies R&D Program of China under Grant no. 2012BAH18B02.


Hanshi Wang

Chenxiao Wang
email: wangchenxiao0329@126.com

Lizhen Liu

Chao Du

Jingli Lu

Identification of co-regulated gene network by using path consistency algorithm based on gene ontology

Keywords: gene ontology, conditional semantic similarity, path consistency algorithm, co-regulated gene network

Recently, the reconstruction of co-regulated gene network has become increasingly popular in the area of bioinformatics. It tries to find the associated information and network topology among genes through large numbers of biological data. In this paper, we proposed a novel method PC-GO by using path consistency (PC) algorithm based on gene ontology (GO). GO provides a basis for measuring the conditional semantic similarity between genes, and then PC algorithm is applied to remove links between genes with less correlation in the network. We successfully applied our algorithm to yeast data. Experimental results show that the accuracy and integrity of the co-regulated network acquired by our method outperforms previous methods.

Introduction

High-throughput techniques have produced vast amounts of sequence, expression and structure data [START_REF] Obayashi | ATTED-II: a database of co-expressed genes and cis elements for identifying co-regulated gene groups in Arabidopsis[END_REF]. As the data source of bioinformatics, gene expression data is now in an increasingly important position. Increasing evidences suggest that interactions between genes have an impact on the regulation of gene expression [START_REF] Lanctôt | Dynamic genome architecture in the nuclear space: regulation of gene expression in three dimensions[END_REF]. Currently, many scholars are committed to find the association of genes [START_REF] Korbel | Systematic association of genes to phenotypes by genome and literature mining[END_REF][START_REF] Lee | Rational association of genes with traits using a genome-scale gene network for Arabidopsis thaliana[END_REF][START_REF] Perez-Iratxeta | Association of genes to genetically inherited diseases using data mining[END_REF] since during getting the associated information between genes, one of the major challenges is the identification of co-regulated gene network. Gene co-regulated network, which aims to find the associated information among genes through large numbers of biological data expressed by genes and visualize the network topology representing gene interactions, as well as reveals the complex reaction mechanism among genes, is regarded as one of the most important objectives in the field of bioinformatics.

Numerous analytical methods have been developed to identify gene co-regulated network from gene expression profiles [START_REF] Berri | Characterization of WRKY co-regulatory networks in rice and Arabidopsis[END_REF]. Genes that are part of the same operon in prokaryotes, or have the same expression pattern in eukaryotes, are co-regulated transcriptionally [START_REF] Teichmann | Conservation of gene co-regulation in prokaryotes and eukaryotes[END_REF]. Generally speaking, we considered a network of genes co-regulated if the percentage that has one or more common TFs is above 80%. Researches on the regulation relationship and regulatory mechanism provide the opportunity for understanding the underlying and predicting genes function, which can help to systematically characterize the process of life activities.

Gene Ontology (GO) [START_REF] Ashburner | Gene Ontology: tool for the unification of biology[END_REF] is a standard vocabulary of functional terms and allows for coherent annotation of gene products. These annotations provide a basis for new methods to compare the similarity of genes and gene products regarding their molecular function and biological role. The semantically similarity of annotation information on genes can be an evidence for functionally similarity of genes. Meanwhile, gene products that participate in the same biochemical reaction, have similar biological functions [START_REF] Wei | Transcriptional coordination of the metabolic network in Arabidopsis[END_REF]. Constructing a gene co-regulated network automatically based on GO is still a big challenge at present. In this paper, the Yeast dataset was used as the test data. We present a new PC algorithm using the CSS based on GO. It consists of two parts: the first part is to calculate the CSS between genes based on GO, and the second is to remove links between genes based on pair-wise similarity by using PC algorithm. Experimental results show that our method has improved the accuracy and integrity of the co-regulated network.

Method

In this section, we will introduce the CSS calculation method, as well as the PC-GO method for identifying co-regulated gene network.

Conditional semantic similarity (CSS) of genes

The function similarity between genes can be determined by comparing the semantic similarity. To improve the accuracy of the semantic similarity of genes, we must consider the semantic similarity of GOs annotating genes, and the key is to measure the semantic similarity of GO terms. This is achieved by considering the Wang's method [START_REF] Wang | A new method to measure the semantic similarity of GO terms[END_REF] of computing semantic similarity between gene pairs. Based on Wang's method, we proposed a new conceptconditional semantic similarity (CSS), which can be applied to the PC algorithm.

Since the semantic of a GO term are determined by its location in the GO graph and semantic relations with all of its ancestor terms, the directed acyclic graph (DAG)

starting from the specific GO term and ending at the root GO term (a sub-DAG of an ontology) is used to show all the relationship of this specific GO term in the ontology. Formally, a GO term A can be represented as ( , , )

A A A DAG A T E 
, where A T is the GO terms set in A DAG , including term A and all of its ancestor terms in sub-DAG, and A E is the set of edges (semantic relations) connecting the GO terms in sub-DAG. The semantic value of GO term A is defined as the aggregate contribution of all terms in sub-DAG. The contribution of a GO term (including A) to the semantic meaning of A is defined as S-value. S-value is calculated by:

  '' ( ) 1
( ) max ( ) | ( ) A A e A SA S t S t t childrenof t t A            (1)
where e  is the semantic contribution factor of two edge types of semantic relationship -"is a" and "part of". Through large numbers of repeated experiments, Wang obtained that the semantic contribution factors for "isa" and "partof" are 0.8 and 0.6, respectively. Given ( , , )

A A A DAG A T E  and ( , , ) B B B

DAG B T E 

for GO terms A and B respectively, the semantic similarity, ( , )

GO S A B , is defined as ( ) ( ) ( , ) ( ) ( ) AB AB t T T GO S t S t S A B SV A SV B      ( 2
)
where t is the intersection GO term of sub-DAG of A and B, .

As each gene is annotated by GO terms, the semantic similarity between two genes

A and B can be represented by the semantic similarity of two GO terms sets, which annotated the corresponding gene. Assuming

    1i 2 2 j 1 1 i m 1 j n 12 Sim go ,GO Sim(go ,GO ) Sim G ,G mn         (3)
In this formula, 1 ( , ) max ( , )

i k GO i Sim go GO S go go  
, that is,

( , )

Sim go GO is defined as the maximum semantic similarity between term go and any of the k terms in set GO .

In this work, we proposed a new concept -conditional semantic similarity (CSS), which indicates the similarity of two genes given the state of another gene. CSS between three genes can be written as:

1 2 1 3 2 3 1 2 3 22 1 3 2 3 | ( , ) ( , ) * ( , ) | ( , | ) 1 ( , ) * 1 ( , ) Sim G G Sim G G Sim G G Sim G G G Sim G G Sim G G    (4)

2.2

The PC-GO method

After we obtain the semantic similarity and CSS through formulation ( 3) and ( 4), the PC algorithm is used to remove the edges, which the semantic similarity or CSS value is smaller than the threshold  given in advance. The  value is experimentally set 0.8 for the reason that genes in a co-regulated network are highly functionally related.

The process of PC-GO begins with a complete graph and attempts to remove as many links as possible. First, for adjacent gene pair i and j, compute the semantic similarity ( , )

Sim i j (0-order). If the gene pair i and j has a lower semantic similarity, it presents functionally irrelevant, then we delete the edge between genes i and j. Second, for adjacent gene pair i and j, select the adjacent gene k of them and compute CSS value

( , | )
Sim i j k (1-order). If the gene pair i and j has a low CSS, delete the edge between them. The next step is to compute higher order CSS until there are no more adjacent edges. At each round, the number of neighbors in the conditional set increases one by one. A conceptual representation of this approach is presented in Figure 1. In this figure, ( ,

)
Sim  is the semantic similarity and

( , | )
Sim    is the CSS. The semantic similarity and CSS lower than the given threshold represent functionally irrelevant between genes.

Evaluation

Yeast Biochemical Pathway Database (YeastCyc) was used as the test data set. The YeastCyc Biochemical is a collection of manually curated metabolic pathway and enzymes of Saccharomyces cerevisiae. There are 217 metabolic pathways in the YeastCyc database. A total of 6381 yeast genes got from 217 pathways were selected for our investigation and GO terms search for all 6381 genes were performed based on the April 2014 releases of GO terms and gene annotations for Saccharomyces cerevisiae from the Gene Ontology Consortium [START_REF] Ashburner | Gene Ontology: tool for the unification of biology[END_REF]. We calculated the semantic simi-larities and CSS of gene pairs, and then partitioned genes into functionally related co-regulated networks.

Genes that share the same TF(s) are co-regulated, which can be a criterion to estimate whether genes are in a co-regulated network. The YEASTRACT database [START_REF] Teixeira | The YEASTRACT database: a tool for the analysis of transcription regulatory associations in Saccharomyces cerevisiae[END_REF] (Yeast Search for Transcription Regulators And Consensus Tracking) is a curated repository of more than 106000 regulatory associations between TFs and target genes in Saccharomyces cerevisiae, which can be used to search for common TFs of genes in each network. In the YEASTRACT database, we used the "Rank by TF" function and considered only expression evidence in the "documented" regulation to obtain the percentage of the genes in each network that are commonly regulated by one or more known TFs.

For each gene network, the summation of all the semantic similarity was calculated.

Genes in a co-regulated network are considered to be co-regulated if the percentage of genes that have one or more common TFs is above 80%. Therefore, we eliminated networks containing less than five genes in order to achieve the 80% when one gene did not have a TF in common. Finally, 623 networks were obtained for analysis. All 415 networks were searched for documented TF-target relationships in the YEASTRACT database. Networks meet the rule that 80% genes have one or more common TFs account for 76.4% with the actual number of 476. Genes that in each network functionally participate in various biological processes, such as protein translation, RNA metabolism, carbohydrate metabolism, etc. Compared to other methods using gene expression profiles with the proportion of 52%, our method improved the accuracy significantly.

We choose two networks with the maximum and minimum summation if all the semantic similarity for verification. The verification result is shown in Table 1. As shown in Table 1, the network with maximum summation is a co-regulated network since Cst6 is the common TF of all the genes contained in this network while the network with minimum summation is not co-regulated as no more than 63.64% genes are regulated by one TF.

Conclusions

We early proposed a novel PC-GO method by using path consistency algorithm based on gene ontology to identify gene co-regulated network, which provides a new way to the bioinformatics research. The effectiveness of the proposed approach has been experimentally demonstrated through its application to a well-researched yeast dataset.

One of the strengths of our approach is that the prediction of co-regulated gene group does not require the availability of gene expression profiles. However, the result generated by the gene conditional semantic similarity calculation method may have an impact on the accuracy of PC algorithm, which require us to improve the accuracy of each procedure in the future research work.

  the semantic value of GO term A and B. The semantic value of GO term M is calculated

Fig. 1 .

 1 Fig. 1. Diagram of PC-GO method

Table 1 .

 1 Part of verification results

			Common TFs and
	Network	Contained genes	percentages of
			commonly regulated
			Cst6	100%
		TFC3, EFB1, YAL004W, SPO7,	Ace2	78.57%
	Network with	CYS3, YAL018C, MAK16, POP5,	Spt20	71.43%
	maximum sum-	YAL037W, ERV46, YAR023C,	Msn2	71.43%
	mation	YAR066W, YAR075W,	Sfp1	71.43%
		YBL077W	Gcr1	57.14%
			Snf2	50%
			Msn2	63.64%
			Msn4	63.64%
	Network with	ECM4, CSN9, ARI1, YAR1,	Yap1	54.55%
	minimum sum-	ATG15, SAW1, GAL7, RPB9,	Bas1	54.55%
	mation	PHM7, PCA1, COA4	Hsf1	54.55%
			Yhp1	45.45%
			Snf2	45.45%

Acknowledgements. This work was supported in part by National Natural Science Foundation of China under Grants No. 61303105; the Beijing Natural Science Foun-Hanshi Wang, Chenxiao Wang, Lizhen Liu, Chao Du, Jingli Lu dation under Grants No.4133084; the Beijing Educational Committee Science and Technology Development Planned under Grants No.KM201410028017 and the Beijing Key Disciplines of Computer Application Technology.


Fei Jiang
email: jiangfei0128@sina.com

Tianlong Gu

Liang Chang
email: changl@guet.edu.cn

Zhoubo Xu

Case Retrieval for Network Security Emergency Response Based on Description Logic

Keywords: Emergency response, Network security incident, Case based reasoning, Description logic, Case retrieval

Network security emergency response (NSER) is an important topic in information security. Nowadays, a large number of NSER systems and tools are developed, which can effectively detect part of security incidents and provide general best-practice guidelines for handling some type of security incidents, but not give a reasonable, fast, effective processing method for every security incidents in actual environment. An intelligent method based on case-based reasoning (CBR) and description logic (DL) is proposed for NSER. Firstly, a case base for NSER is organized in such a way that domain knowledge of NSER is described by the DL ALCO(D). Secondly, based on refinement operator and refinement graph in DLs, an algorithm for measuring the similarity of ALCO(D) concepts is designed and used for retrieving cases from the case base. It is demonstrated that our method can reuse past experiences on security incidents to generate response automatically.

Introduction

Network security emergency response (NSER) is a kind of service that helps to mitigate further damage when network security incident occurred, which has a positive role in protecting the security of enterprise and terminal, and it is also the centre of future information security policy. Since Cliff Stoll's the first book, the Cuckoo's Egg, introduces methods to hack the computer ,as well as a large number of Computer Emergency Response Team Coordination Centers (CERT/CC) are established in the world, the ideas about NSER began to get attention. In recent years, Mitropoulos [START_REF] Mitropoulos | On Incident Handling and Response: A state-of-the-art approach[END_REF] et al. has theoretically investigated the research and application of NSER before 2006, and gave a reasonable security incident processing system framework. To provide data model for CERT and share the information of incidents and vulnerabilities related to the information exchange standard -IODEF [START_REF] Danyliw | RFC 5070:The Incident Object Description Exchange Format[END_REF] (Incident Object Description and Exchange Format) has been developed. In order to help to effectively handle security incidents, the literature [3] provides best-practice guidelines to detect, analyze and handle part of security incidents, and the brief steps to handle some different types of security incidents.

However, most literature are focused on "high impact" incidents (which have high impact on society and network security techniques) on the research of security incidents, and does not help to improve the overall level of NSER and to handle specific security incidents. So some scholars proposed using CBR [START_REF] De Mantaras | Retrieval, reuse, revision and retention in case-based reasoning[END_REF] method for NSER. Considering new various types of security incident are ongoing, these incidents always have the similarity, and the similar incidents have similar incident response. By using the past similar cases to help to solve the current security incidents is found. Capuzzi et al. [5] combined with CBR develops a complete security tool based on ID/PS and which integrates the log Association, attack classification and response plan generation, but it ignores the fact that IDS with high false alarm rate, almost 98%, and it can be said that is unpractical. Considering the high false-positive rate of IDS, Kim et al. [6] proposes using RFM (Recency, Frequency, Monetary) method combined with the analysis of log file to directly detect abnormal incidents and to reduce the false-positive rate of IDS, and then combine with CBR to find the most similar case, but its primary intention is only to detect security incidents, rather than respond to incidents. In order to effectively respond to security incidents, the literature [7] proposes by using some meta knowledge in the NSER domain to help organize case base, and then implementing CBR reasoning to provide NSER, but its meta knowledge representation and retrieval algorithm for solving security incidents too rough to solve the incidents.

Considering the knowledge of case base with good structure, automatic classification concept, and the implementation of corresponding CBR reasoning for NSER, this paper introduces ALCO(D) logic (a form of DL) to describe the knowledge of NSER. DL is a form of knowledge representation, which has good semantic, expression and inference capability, and allow for an automatic classification of concepts. DL has been systematically researched for several decades, its application can be used very effective and fast. Making full use of the advantages of CBR and DL, this paper develops an intelligent method to help to solve the problem of NSER, and to prevent and handle network security incidents.

This paper is organized as follows: Section 2 using ALCO(D) logic represents the knowledge of NSER. Section 3 and 4, design a case retrieval method for retrieving the most similar incidents, and illustrates the given method and its validity. Finally, discuss the existing problems and future work.

Knowledge representation of NSER

A case CA can be described in three tuples, i.e. CA = (P, S, O),where P, S, and O are used to describe the problem or situation of network security incident, its solution or method of NSER, and the outcome obtained by the solution S to the given problem P, respectively. For a given case base CB, with P i , S i , and O i respectively denoting the problem description, solution and outcome of a case CA i , so that CA i CB,

,n is the number of cases in the CB. A large variety of case representation formalisms have been proposed. Depending on different applications, case representation will be different, mainly includes feature vector representations, structured representations, and textual representations. NSER is a knowledge intensive domain, and this paper adopts the structured approach-DL to represent the problem(situation) of security incidents and its outcome for classifying and integrating the knowledge, and the text formalism to present its solution.

Problems (P i ): An incident is generally related to the time, location, executors, recipient, state and effects, and network security incident is also not exceptional. For describing security incidents, we also need to describe the information about the type, time, organization, information about potential attackers, affected resources and its information, effects, state and information about measures has been taken to solve incidents in a security incident. All of this information will help to describe security incident quite clearly.

Type: According to the literature [3], network security incidents can be divided into the following categories: malicious code incidents, denial of service(DoS) incidents, unauthorized access incidents, inappropriate usage incidents or a single incident that encompasses two or more incidents above. When security incidents occurred, the type of security incidents should be first considered in order to determine the most appropriate response strategies. A security incident is a DoS incident, inappropriate usage incident or other incidents, only by determining the type of security incident, its response strategy will become quite clear. DoS attack incident does not involve in actual invasion, so it is the easiest to respond and the most difficult to prevent. Inappropriate usage of resources is usually the insider using others computer in inappropriate ways, it usually needs to consider more the internal factors. Fig. 1 shows a hierarchical relationship for different types of security incidents, including the hierarchical relationship between the virus, worm and DDoS incident. It also expresses an inclusion relationship between some concepts about security incidents by using ALCO(D) logic (e.g. DoS_incident⊒DDoS_incident). Besides the hierarchical relationship mentioned above,some incidents have their own unique characteristics, for example, virus incidents has the characteristics of propagation ways. These characteristics are also considered to better distinguish different incidents, and to provide more information for retrieving and proposing emergency repose strategy.

Fig. 1 Hierarchy relationship diagram of type of security incident

Time: With the progress of computer science and technology, security incidents is designed with more and more powerful function, its destructive force and influence are also increasing. After some new security incidents arise, security defense level for the security incidents will be improved. The old methods of attack in security incidents have no effect on new environment in the future. Considering the time factor, we can make it associated to the recent security incidents, facilitate to find more and better similar incident for the current incident. In addition, in the process of NSER, the longer a security incident lasts, the more potential there is for damage and loss. So we describe the time of a incident for NSER as: Time⊒hasOccurrenceTime. = h year hasDuration. = f hour Where h is a natural number, and f is a positive real number.

Organization: Security incidents often occurred in different personal hosts and organizations, whose response and focus will be different. For example, the response is different between commercial organizations and governmental agencies. The response to security incidents in financial institutions emphasizes the continuity of business and the pecuniary loss, and government emphasizes the publicity and the confidential data loss. In order to handle security incidents better, this paper considers the organization, i.e. governmental agencies, commercial organizations, military institutions, medical institutions, scientific and educational institutions, network service providers. By using ALCO(D) logic, it can be represented as:

Organization⊒(Commerce⊔Education⊔ISP⊔Military⊔Govement )
Attacker's information in the incident: Information such as IP address, communication protocol or port which the attackers used, will help to NSER to track the attacker or close the channels which being attacked and further to block the attack. So the attacker's information can be described as:

Attacker_Info⊒hasAttackerInfo. (IPAddress⊔Port⊔Protocol)
Affected resource: Different resources (firewalls, web servers, network connection, user workstations and applications, etc.) to organizations and individuals have different significance. The different resources which have different effects on the organizations and individuals, the priority to NSER will be different. The incidents which refer to criticality resources or resources which have great potential influence need to handle first. These resources includes: the compromised host, network and its services, network equipment, etc. In order to NSER, we need to know the situation (information) about the compromised host. The information includes the function of host, the number of hosts, the type of operating system, the anomalous phenomena of system, security tools, applications, services, and hardware in affected host. The anomalous phenomenon such as the host always pops up the suspicious content of message or window and suddenly slows down, the security tools (antivirus software, anti-spam software, etc.) warn that the system has viruses or abnormal attacks, the audit from the operating system, service or application was found with intrusion will help to analyze the security incident. Consider network and its service with different state such as network can't be connected, network traffic anomaly, NSER will be different. By using ALCO(D) logic, some knowledge about the affected resource can be represented as follow:

Affected-Resource (Affected-Host Affected-Network Affected-NetworkDevice).

Affected-Host⊒(hasOS.OS⊓hasHostFunction.Host_Function⊓hasNumber.= m tai⊓hasAabnormal. (Host_System Host_Application Host_Hardware)).

OS Windows Linux Unix Android iOS. Host_Function (Client Server). Server (FTP_server Web_server Data_server Mail_server). Host_Application Security_Tool IE. Host_Hardware Keyboard Loudspeaker. Host_System Host_SystemService. Effect: The security incidents may impact on victims and lead to some disruption and loss, including the loss of money, damage of reputation and data loss, leakage, and destruction. We also consider the factor for NSER and describe it as:

Effect {Money_Loss, Publicity_Loss, Data_Loss} State: Reponses-taken will be use to different security incidents under different conditions. Some attacks will have symptoms, before the damage occurs, the response we performed is to prevent, while some attack has occurred and destroyed the service, we must quickly mitigate the damage which cause by incident, deal with the security incidents, and restore the system. It can be represented as follows:

State finished, ongoing, unhappened, unknown}. Response-taken: When the security incidents occurred, organizations or individuals will handle it by disconnecting from the network or closing the infected host. It can be represented as follows:

Response-taken {Close_Host, Disconnect_Network}. In order to handle security incidents better, all of the information about security incident should be retrieved or revised, and can transform into the data that computer can be identified. After there are all of the needful elements to depict the network security incidents mentioned above, this paper using ALCO(D) logic represents the problem (P) of a case. Solution (S): Describe the whole process of NSER to deal with specific security incidents. The textual representation is mainly used to describe solution to the given problem (security incident).

Outcome (O):

The results of NSER may be good or bad, how to measure it? The user's satisfaction is used to evaluate the result. The satisfaction is high, the solution is good, and can be adopted; the satisfaction is very low, the solution is not appropriate, and used to learn the lessons. The value of user's satisfaction we can evaluation by the mean value of acceptability,feasibility, flexibility, operability, integrity and consistency of the solution about incident after user use the solution and assess. The Outcome is also described by using the ALCO(D) logic.

The structure of case CA i is shown as follow.

Fig.2 Structure of cases

As can be seen, ALCO(D) logic with the strong ability of description, have clear semantics for describing network security incidents, which can describe the internal structure of cases, depict more comprehensive knowledge, close to man's mind-set and expression powerfully. It will also benefit case retrieval and revise.

Case retrieval for network security incident

When new network security incidents occur, the system needs to retrieve the similar security incidents from case base. Case retrieval is a key stage in CBR design. In case retrieval, similarity is usually used. The more close to 1 it is, the higher degree of similarity between the two cases are. Case retrieval directly affected the relevancy of cases, and affected whether to generate the appropriate solution to problem or not. Depending on different application, about similarity, different case representation has different measuring methods. Cunningham [START_REF] Cunningham | A Taxonomy of Similarity Mechanisms for Case-Based Reasoning[END_REF] investigated the mainstream method of similarity measure for different applications in CBR areas. Sá nchez-Ruizet [START_REF] Sá Nchez-Ruiz | Measuring similarity in description logics using refinement operators[M] Case-Based Reasoning Research and Development[END_REF][START_REF] Sá Nchez-Ruiz | Refinement-Based Similarity Measure over DL Conjunctive Queries[M] Case-Based Reasoning Research and Development[END_REF] et al. put forward the similarity measure in the space of concepts and in the space of conjunctive queries between concepts and individuals about εL logic. According to the type of different attributes about disaster events such as the numerical, interval, character type in the field of disaster emergency, Amailef [START_REF] Amailef | Ontology-supported case-based reasoning approach for intelligent m-Government emergency response services[END_REF] et al. use the attributes of disaster emergency based ontology to define case structure, and give different similarity metrics.

Based on the previous research, this paper uses the ALCO (D) logic represent the case, this section will further give a similarity strategy based on refinement operator and refinement graph for network security incidents. Now the section briefly summarizes the notation for refinement operator and the relevant concepts for this paper. Refinement operators are defined over quasi-ordered sets. A quasi-ordered set is a pair(S, ),where S is set, and is a binary relation among elements of S. If and , we say that . Refinement operator are defined as follows: A down refinement operator over a quasi-ordered set(S, ) is a function such that ; A up refinement operator over a quasi-ordered set(S, )is a function such that

.Down operator refinement operators generate elements of which are smaller (which in this paper will mean "more specific"), in contrast, up operator refinement operators generate elements of which are bigger (which in this paper will mean "more general").

The Least common subsumer (LCS) of a set of given concepts, C 1 ,...,C n is another concept C=LCS(C 1 ,...,C n )such that , and for any other concept such that , holds. If given two concepts C and D such that , it is possible to reach C from D by applying a downward refinement operator to D a finite number of times, i.e. . The length of the refinement chain to reach C from D, which we will note by

, is an indication of how much more information C has that was not contained in D. Given any two concepts, their LCS is the most specific concept which subsumes both. The LCS of two concepts contains all that is shared between two concepts, and the more they share the more similar they are. So, we can now define similarity between two concepts C and D. i.e. the similarity between two concepts C and D is assessed as the amount of information contained in their LCS divided by the total amount of information in C and D.

To measure similarity of two cases of network security incident, we suppose the problem of cases CA 1 ,CA 2 is P 1 and P 2 respectively. Where C i , D j (i =1,…, n ; j =1,…, m) are the ALCO(D) formula ,then we can define the similarity between CA 1 and CA 2 .

, , ( 1 )
Where , In this paper,the correlation coefficient  we take 0.98, i take 0.5, then 24/(24+12+7)=0.558, the similarity of CA 1 ,CA 2 is 0.554.

, ( 3 ) , ( 4 ) , ( 2 )
In order to verify the validity of the proposed algorithm, this paper collected more than 20 typical cases for nearly 3 years from the CNCERT and calculated their similarity measure. As shown in Fig. 3, the case 1-7 are virus or worm incidents, case 8-11 are mobile malware incidents, case 12-14 are DDoS incidents, case 15-17 are phishing site or Trojan incidents, case 18-20 are webpage tamper incidents. Their similarity with three different types of incident is calculated. As can be seen from the graph, The conficker worm incident is concentrated in case 7, 8 with higher similarity, and DDoS incident is concentrated in case 12-14 with its high similarity. This can be explained that the retrieval algorithm has a certain degree of differentiation, which can effectively distinguish the different form of the virus, worm and DDoS incidents, retrieve previous incidents to match the target case, and obtain a method for appropriately handling security incidents in actual environment.

Fig. 3

Similarity of cases

Conclusion

This paper presents a method for appropriately handling security incidents under specific environment by exploring the past similar cases. characteristics of DL with clear semantics and good inference capability, this paper mainly use the formalization DL to represent NSER cases, thus providing an effective way to classify and search the knowledge of case base. In order to enhance the overall effect of retrieval, it design a good matching algorithm of similarity based on refinement operator and refinement graph to distinguish different cases in case base and retrieve the most similar cases. Finally, this paper proves the similarity metric with good effects by experiments. The further work as following: design the case reuse and revise process, combine the failing cases to design some more reasonable method of retrieve, reuse and revise.

(

  weighted factors,k is the number of concept with the same type of role and numerical value in concrete domain. If F. = d 1 , F. = d 2 and max not equal min, then max and min are the maximum and minimum value of concrete role with data type d 1 and d 2 , respectively. If F.=d 1 , F.=d 2 and max equal min, then the right side of equation equals to ,i.e.| d 1 -d 2 |/|max-min| equal 1. Due to the description of P (problem) in the case of security incident in essence is a concept, formula (2) defines the overall similarity between two cases. The calculation of is the correction similarity between two cases, which used to assess similarity of two different concept with the same type role and different numerical value in concrete domain of case representation, such as the similarity between hasOccurredTime.= 2010 year and hasOccurredTime.= 2009 year. According to the need of knowledge representation, the concrete domain D only used one feature and a predicate formula, i.e. the situation of  F. d andF. d.

4 Case study

  Suppose there are two cases CA 1 and CA 2 which are described by two concepts Tiger_virus_incident and Dummycom_virus_incident respectively as follow

	Then ,their least common subsumer (LCS) is:
	LCS(Tiger_virus_incident,Dummycom_virus_incident) 
	hasType.(Virus_Incident⊓
	hasTransMethod.(LAN⊔Mobile-memory-media⊔{Affected-exefile}))
	⊓hasOccurrenceTime.=n year⊓hasOrg.Organization
	⊓hasAffectedResource.((hasOS.Win-xp)⊓ hasHostFunction.Client⊓hasNumber.=m tai
	⊓hasAbnormal.((Antivirus⊓hasSign.{unavailable})
	⊓System⊓hasSign.{slowdown}⊓ Exe-file⊓hasSign.{infected}
	⊓ (IE⊓hasSign.{abnormal}) )
	⊓hasState. {ongoing}⊓hasEffect. Effect.
	Tiger_virus_incident 
	hasType.(Virus_Incident ⊓ Worm_Incident ⊓
	hasTransMethod.(Webshell ⊔ Mobile_memory_media ⊔ LAN_WeakPW
	⊔{IE_day_vulnerability, Affected-exefile}) )
	⊓ hasOccurenceTime. = 2010 year ⊓ hasOrg. Commerce
	⊓ hasAffectedResource.(hasHostFunction.Client ⊓ hasOS.(Win7⊔Win-xp) ⊓
	hasNumber.=20 tai ⊓
	hasAbnormal.(Antivirus⊓hasSign.{unavailable}⊓
	CPU⊓hasSign.{usage_high}⊓IE⊓hasSign.{abnormal}⊓
	System⊓hasSign.{slowdown}⊓Exe-file⊓hasSign.{infected}⊓
	Hard-disk ⊓hasSign.{Read_fast}))
	⊓hasState.{on-going} ⊓ hasEffect.{Money_Loss}.
	Dummycom_virus_incident 
	hasType.(Virus_Incident
	⊓hasTransMethod.(LAN_ARP⊔Mobile_Memory_media⊔{Affected-exefile}))
	⊓hasOccurenceTime.=2009 year⊓hasOrg. Education
	⊓hasAffectedResource.(hasHostFunction.Client  hasOS.Win-xp⊓
	hasNumber.=100 tai⊓
	hasAbnormal.((Exe-file⊓hasSign.{infected})⊓
	Antivirus⊓hasSign.{unavailable})⊓
	Hidden_file⊓hasSign.{Not_display})⊓
	System⊓hasSign.{slowdown, time_distorted, blue_screen}⊓
	IE⊓hasSign.{Sec_tool_web_no_access}))
	⊓hasState.{ongoing}⊓hasEffect.{Data_lost}.

Acknowledgements. This work is supported by the National Natural Science Foundation of China (Nos. 61262030, 61363030, 61100025), the Natural Science Foundation of Guangxi Province (No.2012GXNSFBA053169) and the Science Foundation of Key Laboratory of Trusted Software.


Meng Li

Quanliang Jing
email: quanliangjing@ict.ac.cn

Zhongjiang Yao
email: zhongjiangyao@163.com

Jingang Liu

On the Prevention of Invalid Route Injection Attack

Keywords: invalid route, injection, OSPF, BGP, route attack

In recent years, the Internet is suffering from severe attacks from the global routing system, such as prefix hijack, digital cannon. These attacks break down network services and sabotage infrastructures. In this paper, we present a novel attack on route control plane---invalid route injection, and simulate the attack by adding controlled software routers in the stub and check the resource consumptions of routers before and after the attack. The experimental results demonstrate that invalid route injection can bring severe damage to routers in the Internet. Based on the analysis of the results, we discuss the prevention of the attack and propose some effective protection and countermeasures to the attack.

Introduction

With the rapid development and growth of IP technology, Internet has penetrated into politics, economy, military and daily life and brought it a corresponding increased reliance on the underlying infrastructures. Therefore, it is essential to ensure the security of the Internet. Route security is an important part of Internet security. It is becoming vitally important and facing significant challenges at the same time.

The Internet is composed of tens of thousands of Autonomous Systems (ASes) which operate individual parts of the infrastructures. ASes exchange route information via an external gateway protocol like BGP [START_REF] Kent | Secure border gateway protocol (S-BGP)[J]. Selected Areas in Communications[END_REF] (Border Gateway Protocol). Within an AS, routers communicate with each other through intra-domain routing protocols [2] such as OSPF (Open Shortest Path First Protocol) which has been widely used currently, and IS-IS (Intermediate System to Intermediate System) which is developing and spreading gradually. These protocols can efficiently distribute dynamic topological information among its participants, facilitate route calculations and make packet forwarding decisions. They form the heart of Internet infrastructures.

However, these routing protocols are not so robust for their disadvantages and loopholes which can cause some incidents or be used by malicious attempts to compromise the availability of the network [3]. For example, since its own route information cannot be validated by BGP itself, it has to fully trust all the other peering routers [5]. Based on that, On 24 th February 2008, Pakistan Telecom started an unauthorized announcement of prefix 208.65.153.0/24. PCCW Global, one of Pakistan Telecom's upstream providers, forwarded this announcement to the rest of the Internet, which resulted in the hijacking of YouTube traffic on a global scale [6]. For another, Max Schuchard, from the University of Minnesota in 2010 put forward the concept of 'digital cannon' [7], which showed that a digital cannon using a 'botnet' composed of 25000 computers can destroy the entire Internet using BGP protocol. These routing incidents result in irreparable damage to the politics and economics.

In order to detect the routing attacks effectively and provide a theoretical foundation for routing attack detection, in this paper we present a novel network routing attack named invalid route injection. Then we do some simulate experiments to verify the attack. The results show that the invalid route injection attacks do have an effect on the communication among the hosts or routers, causing a serious impact on the stability and security of the network. Finally we discuss some preventive measures.

Related Work

Using the control plane to attack the Internet has recently been proposed to the literature. 'Digital cannon', which interferes information exchange by using data plane to affect control plane, is one of such attacks. The attack causes routers frequently exchanging neighbor routing information, resulting in the exhaustion of CPU, memory and other resources of the routers, and eventually crushing control plane. However, this method needs to get the topology of the entire network and critical devices. Once the network devices filter the ICMP packets, the attack will not happen [START_REF] Liu | LDC: Detecting BGP Prefix Hijacking by Load Distribution Change[END_REF] . Currently, there are also many instances of 'prefix hijacking' attacks in the Internet, which are caused by mis-configuration of routing information or malicious attempts. The AS that hijacks a prefix can intercept all the hijacked traffic, result in a denial-of-service attack against the hijacked AS. Also the hijacks can redirect the traffic to an incorrect destination for phishing attack. Although prefix hijack has many cases in theory, it is hard to implement in reality since the Internet has not only very strict access strategy of the Internet, but also the attack need to configure the routes directly [START_REF] Lad | PHAS: A prefix hijack alert system[C][END_REF] . This paper introduces a new method of routing attack-invalid route injection attack. This methodology avoids directly manipulating core routers running BGP, and is easy to be implemented.

There are also many measurement studies on routing attack related problems, for example, analyzing route changes and their causes, measuring how the end-to-end performance is impacted by protocol policy, and studying black-holes in the Internet [START_REF] Zheng | A light-weight distributed scheme for detecting IP prefix hijacks in real-time[END_REF][START_REF] Hu | Accurate Real-time Identification of IP Prefix Hijacking[C]// Security and Privacy[END_REF][START_REF] White | Securing BGP through secure origin BGP (soBGP)[END_REF][START_REF] Oorschot | On interdomain routing security and pretty secure BGP (psBGP)[END_REF] . Here, we make some control measurement to prevent the potential invalid route attack, to narrow down the scope of the attack. Since the attack is carried on by following the protocols, we identify changes when the attack happens, and record some parameter thresholds, helping better understand the characteristics of the attack.

3

Attack Description

Methodology

Invalid route injection attack aims at routers running intra-domain protocols. The attackers first establish neighbor relationship with routers in the AS, after that it will advertise many invalid routes to impact the border routers, eventually make other routers in the area affected. Since the border routers are core equipment of the network, it is difficult to attack them directly. Instead of acquiring control of BGP, invalid route injection attack is manipulated by using features of OSPF or IS-IS protocols. It will cause depletion of routers' resource and instability even a loss of connectivity in the network.

To validate the effectiveness of the attack presented above, we design a topology similar to the real network, and simulate the attack on the topology. Since the results of this experiment have nothing to do with the specific autonomous system, the real autonomous system number is not necessary. We use Cisco 1800 series routers in the experiment.

Fig. 1. Invalid Route Injection

The set of intra-domain routers is defined as R r = {router-id} each element represents a router that is identified by its router-id. C router-id represents the memory size of each router. The maximum memory within the router can be expressed as:

} C { max = C id - router max
The minimum memory within the router can be expressed as:

Attacker AS1 Area 0 Area 2 Attacker Area 1 } C { min = C id - router min
The amount of memory occupied by the attacker's invalid route is defined as Y. Theoretically, Y ≥ C max means that memory resource of the routers within the entire domain is exhausted after the injection; C min ≤Y≤ C max means that part of routers' memory resources has been used up; Y ≤ C min means the injection would not affect the area. Since the router not only handles protocol interactions but also does packet forwarding and calculation of routing paths, the impact of the amount of memory above on a router is an upper bound. Figure1 illustrates the invalid route injection attack, the basic principle of the attack is to add controlled router in the stub by establishing OSPF/IS-IS neighborhood with normal routers, meantime declaring a large number of false or invalid transient messages, thus resulting in many routers' resources deplete in the network. By means of DDoS (Distributed Denial of Service) theory, it will impact the routers of the entire network including highperformance boarder routers through deploying distributed controlled routers.

Implementation of the attack 1)

Attack position. First we choose a position to attack. Since previous attacks require to know about the core routers or to get the status of the entire network topology in advance, they are difficult to be carried out. However, invalid route injection attack only needs to find routers running OSPF/IS-IS protocol in the stub and to establish OSPF/IS-IS neighbor relationship with normal routers. Hence, it is much easier to implement in practice.

2)

Invalid route generation. Next we generate a lot of static routes as invalid injection. There are many ways to introduce static routes. For instance, we can probe the data layer such as traceroute and ping to get the network segment address, and accordingly to generate a lot of static routes. Also it can be generated in random. After that, the invalid routers can be propagated into the network by flooding mechanism of the protocol, and exhaust the CPU, memory and other resources, thereafter affecting the entire network.

)

Invalid route injection. Then, we inject route in the network. The way of injection depends on routing protocol running among routers in the network. If using OSPF, the attacker would establish OSPF neighbor relationship with the routers and generate invalid routes redistributed into OSPF, and affect other local routers and other routers in the network; If using IS-IS, the attacker would establish IS-IS neighbor relationship, and directly inject the invalid entries into the IS-IS network.

4)

Invalid route revocation.

On the Prevention of Invalid Route Injection Attack

Finally, in order to advance the attack impact, we revoke or add static route repeatedly to affect the entire network. It will cause the control plane unstable and make the network in a turbulent environment. Thus routers would consume routers' resources, and packets forwarding and neighbor relationship establishment would be affected among routers.

4

Simulation and Experimental Analysis

Definition of evaluation

In order to demonstrate the effect of invalid route implantation to the network, we define three evaluation indicators for routers: average CPU utilization, average memory utilization and average packet loss rate. Routers' average CPU utilization is calculated as follows:

AVE_CPU = M D p i q j ij p ∑∑ 1 = 1 = (1)
Let p be the number of the AS, q p be routers' number in AS p, we define D as CPU utilization, M as total number of routers in the network. Memory utilization of a router is expressed as:

AVE_Mem = M O B p i q j ij ij p ∑∑ 1 = 1 =
(2)

As the same, p is the number of the AS, q p to be router number in AS p, we denote B as memory footprint of a router, O as a router's total amount of memory, M as total number of the routers in the network.

Average packet loss rate is calculated as equation [3]. Here, p represents the number of packets sent, S i means packets number of the i-th, A means the packets number that have been sent successfully for the i-th.

AVE_Loss = p S A p 1 = i i i ∑ (3)

Network topology and experiment design

As shown in Figure 2, AS1, AS2 and AS3 represent different autonomous system; connection among them has been marked. The topology of each AS is shown in Figure 3, there are three areas in one AS, each AS has eight routers, and three routers in area 2 can connect multiple hosts or packet tester.

In the experiment, we first make the network reach a steady state and add attacker in area 2 or area 0 respectively according to the methodology described in Section3. Then we inject a large number of static routes and observe changes in CPU utilization, memory utilization and packet loss rate. Since the value of CPU utilization and memory usage have instantaneous effect, we need to wait for the network to be stable again after the injection and calculate the statistics for router's CPU, memory usage.

We wait about 15 minutes after the injection. The router CPU utilization for each router is calculated using the following formula:

B = p p 1 = i i R ∑ (4)
We denote p as times of calculation, Q measures CPU utilization rate for each time.

When checking the router CPU utilization, we type in 'show processes' in the command line of the router. Three values of CPU utilization will be showed, which respectively represent the value within nearest 5 seconds, nearest 1 minute and nearest 5 minutes. In order to ensure the accuracy of the data, we adopt the CPU utilization values within five minutes for each time.

Fig. 2. Topology of Simulation

Fig. 3. Topology of AS1

Memory footprint is calculated as equation ( 5), let p represent times we check, R to be the footprint of each view. We type 'show memory' in the command line to check the memory utilization of the router.

BGP Router AS 1 Area 0 Area 2 Area 1 AS1 AS3 AS2 D = p p 1 = i i Q ∑ (5)

Experimental analysis

Figure 4 reflects changes about the average CPU utilization of the router. In two attackers' situation, with the invalid route entry increasing from 10000 to 80000, the percent of average CPU utilization rise rapidly from 5% to 90%, followed by it is in smooth change. Comparing two attackers' case with the only one attacker situation, the former one has higher average CPU utilization. Also there is a large gap between them, indicating a plurality of attackers would have a greater impact on the network. Within a certain period of time, the CPU processing capacity of a router is limited. When too many invalid routes injected, CPU utilization is so high that other processes are blocked to take CPU. Thus we draw a conclusion that the attack does have an impact on the packets forwarding and neighborhood establishment.

Fig. 4. Average CPU Utilization Trend

Figure5 shows router average memory utilization changes with the number of injected invalid routes. In two attackers' situation, with the increasing of invalid route injection, the average memory utilization strikes a steady upward trend at the initial phase. When injection entry reach 80000, the average memory utilization reaches 90%, and then leveled off. It means that when there are enough static routes, the attack will consume almost all the memory of routers. Then we continue to increase the number of static routers, the utilization increasing is no longer in linear trend but stabilized. Since the router's memory is limited, when the invalid routes occupy too much memory, it will affect the normal operation of routers, and have an impact on the establishment of neighbor relations and packets forwarding.

Fig. 5. Router Average Memory Utilization

With the injection of invalid route, packet loss rate throughout the network is shown in Figure 6. In two attackers' situation, the basic network data packets are rarely lost when the invalid route entry is less than 50000, However, the invalid entry and the packet loss rate are increased significantly with the increasing of invalid entry. While the invalid routes reached 60000, packet loss rate is 70%. While 100000 entries, the packet loss rate could even reach 95%. As shown in the figure, the tendency of the network packet loss rate is in line with the average CPU utilization and average memory utilization. The number of Attackers could result in a big gap in the router packet loss rate, before and after the attack, providing that more Attackers, greater impact on the network. According to the attack principle, routers will be affected if an invalid route injects into the network in the corresponding AS. However, if BGP router's reachability information in the corresponding AS is brought into the network through the static mode, the attack will not spread to other AS, thereby narrow down the affected scope of invalid route injection attack.

In Figure 4, within two Attackers in the network, the average CPU utilization of the router changes significantly after we set one static route of into the network. When invalid route entry injected reach 60000, there is 35% gap increase, and the gap will remain at this level following the increasing number of injection. Routers' memory utilization has direct relation with the number of injection. Introducing a router in a static way will influence number of invalid route in the network. It can be seen in Figure 5, at the initial stage, the average memory utilization of the router already has about 20% gap, then gradually stabilized. Similarly, the packet loss rate shown in Fig. 6, the difference began to become larger, about 25% when invalid route injection entry reach 60000, in line with the trend of average CPU utilization and average memory utilization.

Warning threshold for routers

The invalid routes injected to the network could be learned and propagated by routers. We can deploy route entry detection system in service provider's network. Once the route entry detected is beyond a certain baseline, we will make a warning alarm to remind the provider to take measures and reduce losses caused by the attack.

The above methods and other preventive measures such as: the use of QOS mechanism to control the level of security resources [START_REF] Liu | LDC: Detecting BGP Prefix Hijacking by Load Distribution Change[END_REF] , modify the route protocol [14][15][16] , with a variety of detection methods [START_REF] Zheng | A light-weight distributed scheme for detecting IP prefix hijacks in real-time[END_REF][START_REF] Hu | Accurate Real-time Identification of IP Prefix Hijacking[C]// Security and Privacy[END_REF][START_REF] White | Securing BGP through secure origin BGP (soBGP)[END_REF][START_REF] Oorschot | On interdomain routing security and pretty secure BGP (psBGP)[END_REF] to check the attacks. Those are not the fundamental solution for static route injection attacks. To prevent attacks fundamentally, we need redesign the existing router or amend the protocols to strengthen network security and prevent attacks against the protocols radically.

Conclusion

Through in-depth study of network route protocols, we investigate the invalid route injection attack which can cause severe damage to the network. The key point of the attack is to declare a large number of invalid route information into the network resulting in massive route updates, eventually causing routers' resources exhausted in the network. Meanwhile we provide the specific steps in the generation and injection of invalid route. We also verify the attack by experiment and analyze the changes in the network after attacks. Finally, we discuss some preventive measures of the attack. These measures can reduce the losses caused by the attack effectively.

Fig. 6 .

 6 Fig.6. Packet Loss Rate Trend

Acknowledgment

This is supported by Research Foundation of Education Bureau of Hebei Province (No. Z2013124).