Mauro Dalla Mura
email: dallamura@disi.unitn.it

Alberto Villa
email: alberto.villa@hyperinet.eu

Jon Atli Benediktsson

Jocelyn Chanussot
email: jocelyn.chanussot@gipsa-lab.grenoble-inp.fr

Lorenzo Bruzzone
email: lorenzo.bruzzone@ing.unitn.it

Classification of hyperspectral images by using morphological attribute filters and independent component analysis

Keywords: Mathematical morphology, attribute filters, independent component analysis, decision fusion, remote sensing

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

INTRODUCTION

The exploitation of the spatial information is very important for the classification of high geometrical resolution hyperspectral images [START_REF] Fauvel | Spectral and spatial classification of hyperspectral data using svms and morphological profiles[END_REF]. In fact, when the analysis is carried out by only considering the spectral response of the single pixels without taking into account the spatial context, the classification of the image usually leads to results which are spatially inaccurate (e.g., showing a high degree of over-segmentation).

The contextual relations between spatially neighboring pixels can be exploited in several ways. A widely used technique for including the information of the spatial domain in the analysis is the family of transformations belonging to the mathematical morphology framework. In particular, morphological connected operators [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF], proved to be suitable for extracting spatial information while preserving the geometrical characteristics of the structures in the image (i.e., without distorting the borders, etc.). In [START_REF] Benediktsson | Classification of hyperspectral data from urban areas based on extended morphological profiles[END_REF], morphological profiles (MPs), a sequence of multi-scale connected operators, were applied to high resolution hyperspectral images by reducing the high dimensionality of the data by a Principal Component Analysis (PCA), and computing the profiles on the first principal components extracted. Due to the limitations of PCA when extracting the informative sources from the high dimensional data, in [START_REF] Palmason | Classification of hyperspectral data from urban areas using morphological preprocessing and independent (a) (b) (c) (d) Fig. 3. Classification maps obtained by: (a) PCA with area attribute, (b) PCA fusion, (c) ICA with all the attributes, and (d) ICA fusion. component analysis[END_REF], the authors proposed to perform an Independent Component Analysis (ICA) before the computation of the MPs.

The characterization of the spatial information obtained by the application of a MP is particularly suitable for representing the multi-scale variability of the structures in the image but it might not be sufficient to model other geometrical features. To avoid this limitation, in [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF] the use of morphological attribute filters instead of the conventional operators based on the geodesic reconstruction was proposed. The application of attribute filters in a multi-level way leads to the definition of Attribute Profiles (APs) [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF], which permit to model other geometrical characteristics rather than the size of the objects. Moreover, APs showed interesting characteristics when extended to hyperspectral images [START_REF] Dalla Mura | Extended profiles with morphological attribute filters for the analysis of hyperspectral data[END_REF]. In greater details, analogously to [START_REF] Benediktsson | Classification of hyperspectral data from urban areas based on extended morphological profiles[END_REF], the APs where applied to the first principal components extracted from a hyperspectral image, generating an Extended Attribute Profile (EAP).

In this paper, a technique based on extended attribute profiles and independent component analysis for the classification of hyperspectral high resolution images is proposed. Moreover, an architecture for dealing with the increase of dimensionality generated by the EAPs based on a decision fusion strategy is presented.

The paper is organized as follows. In Section 2 the ICA is recalled, in Section 3 the concepts of morphological attribute filters and extended attribute profiles are presented. The architecture of the proposed fusion technique is presented in Section 4 and the experimental results are illustrated in Section 5. Finally, conclusions are drawn in Section 6.

INDEPENDENT COMPONENT ANALYSIS

When dealing with high dimensional data, feature reduction is one of the fundamental tasks, which consists in designing a statistical model of the observed signal, trying to minimize the loss of information. In case of data classification, this pre-processing step is useful both to avoid the Hughes'phenomenon and to reduce the computational time. PCA is often used for such a task, due to its simplicity and ease of use. Nevertheless, PCA is based on the analysis of covariance matrix and second order statistics, thus some important information can be neglected, especially when few components are 978-1-4244-8907-7/10/$26.00 ©2010 IEEE retained. In this paper, we propose the use of ICA as an effective alternative to PCA, for the purpose of feature reduction. ICA consists of finding a linear decomposition of the observed data into statistically independent components. Given an observation model:

x = As, ( 1
)
where x is the vector of the observed signals, A is a matrix of scalars corresponding to the mixing coefficient and s the vector of the source signals, ICA finds a separating matrix W such that

y = Wx = WAs, ( 2
)
where y is a vector of independent components (ICs). Independence is a much stronger assumption than uncorrelation, which is obtained with common decorrelation methods such as PCA or Factor Analysis (FA). In order to ensure independence, each component should not provide any information about higher (than second) order statistics of the other components. Because of this reason, ICs are expected to contain more information than Principal Components, and to be more suitable for classification purposes, also in the case of a small number of ICs retained. There is not an unique definition for independence, and there are several methods for estimating ICA. In this paper we have used the algorithm JADE, due to good results shown when used for feature reduction of hyperspectral remote sensing data [START_REF] Villa | On the use of ICA for hyperspectral image analysis[END_REF]. If the ICA is used as a transformation for dimensionality reduction, the feature extracted are the components that are mutually maximally independent (according to the definition of independence used). Due to the space constraints we refer the reader interested in more details about the general framework of ICA to [START_REF] Hyvarinen | Independent Component Analysis[END_REF].

ATTRIBUTE FILTERS AND EXTENDED ATTRIBUTE PROFILES

Attribute filters are a class of connected operators [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF]. They process a single band image by either entirely preserving or entirely suppressing the connected components (i.e., regions of iso-intensity spatially connected pixels) that compose the image. The suppression or preservation of the flat regions is chosen according to the fulfillment of a criterion evaluated on each component. The criterion compares the value of an arbitrary attribute (e.g., area, volume, standard deviation, etc.) measured on the component against the value of a global threshold. If the criterion is verified then the connected components are kept unaffected otherwise they are completely removed.

Example of attribute filters are attribute opening and closing. An attribute opening processes the image by removing connected components brighter than their surrounding ones (while a closing processes the darker ones), which do not fulfill the criterion of the transformation. The criterion has to be increasing (if it is verified for a connected component then it will be also verified by all the regions that contain it). If the criterion does not fulfill this property, then the transformation is not increasing anymore and becomes a thinning or thickening.

Attribute openings for binary images are obtained by computing a trivial opening, Γ T on the output of a connected opening, ΓX , applied to all the connected components of an image X. Given a point x in the image domain and a connected component C, the connected opening is computed as Being a, an attribute measured on a generic connected component C of the image, the trivial opening keeps the regions for which the criterion T (e.g., T (C) = a(C) ≤ λ) holds. This can be expressed as:

Γx(X) = n C if x ∈ C; ∅ otherwise. (3)
ΓT (C) = n C if T = true; ∅ otherwise. (4)
Attribute opening is then given by:

Γ T (X) = [ x∈X ΓT (Γx(X)). (5)
By duality, attribute closing is analogously computed by considering the background regions instead of the foreground ones. When the criterion is increasing, the extension of the operators from binary to gray-scale is straighforward by exploiting the threshold superposition principle [START_REF] Maragos | Threshold superposition in morphological image analysis systems[END_REF]. Conversely, when the criterion is not increasing, the extension to grayscale of the binary concepts is not direct and a proper filtering rule has to be selected in order to implement the filtering [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF]. We remind that attribute filters are appealing also from the computational complexity side, since they can be efficiently computed by using the Max-Tree algorithm [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF].

Attribute profiles are defined as a concatenation of L attribute openings/thinnings and L closings/thickenings with a progressively relaxed criterion U = {Ti(X) = a(X) ≤ λi} with λi ≥ λj, i ≥ j and i, j = 1, . . . , L [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF]. An example of APs computed with different attributes are shown in Fig. 1 where it is possible to notice as different structures are enhanced according to the type of attribute considered.

Extended attribute profiles (EAPs) were presented as an extension of the concept of AP to the hyperspectral domain [START_REF] Dalla Mura | Extended profiles with morphological attribute filters for the analysis of hyperspectral data[END_REF]. EAPs are based on a feature reduction stage and are obtained by concatenating the APs computed on each of the feature extracted from the image.

DECISION FUSION TECHNIQUE

The a piori choice of the most suitable attribute for extracting the information on the geospatial objects is certainly a complex task. However, by considering in the analysis all the features extracted from several APs can lead to a consistent increase of the dimensionality, thus, leading to the Hughes phenomenon. For this reason, we propose an architecture for fusing the information extracted from different profiles in order to increase the robustness of the analysis but, at the same time, by keeping low the dimensionality of the data. The general scheme of the proposed technique is presented in the following. After reducing the dimension of the hyperspectral image with PCA/ICA, EAPs with different attributes are computed on the extracted components. Subsequently, each EAP is processed by a support vector machine (SVM) classifier and the results of the classification are fused according to a decision criterion in order to generate the final classification map. The multiclass strategy selected is One Against One (OAO): a binary classifiers is applied for each pair of classes, producing a vote for the class to which the sample would be assigned. Finally, each pixel is assigned to the class that gets the highest number of votes. In the fusion approach, we try to exploit the information provided by all the classifiers. A simple, yet effective criterion is to sum the votes of the classifiers applied to the four EAPs, assigning each pixel to a class, according to a majority voting scheme. Obviously, other decision criteria can be applied. Fusing the results of several independent classifiers leads to increase the robustness of the results especially if the different EAPs generate complementary errors.

EXPERIMENTAL ANALYSIS

The experimental analysis was carried out on a high resolution hyperspectral image acquired over the Pavia University campus by the ROSIS-03 (Reflective Optics Systems Imaging Spectrometer) hyperspectral sensor. The data are composed of 103 spectral bands (ranging from 430 to 860 nm with a step of 4 nm) of 610×340 pixels with a 1.3 m geometrical resolution. Nine thematic land cover classes were identified in the scene: Trees, Asphalt, Bitumen, Gravel, Metal sheets, Shadows, Self-blocking Bricks, Meadows, and Bare soil. A total of 3921 and 42776 pixels were available as training and test sets respectively. The true color representation of the image and the test set taken as reference are shown in Fig. 2.

From the hyperspectral image the first four components of the PCA were considered for the analysis in order to explain more than 99% of the total variance of the data. Four independent components were also extracted by the ICA from the original data. Subsequently, on the features extracted by both the PCA and ICA, four EAPs were computed with different attributes: i) a, area of the regions; ii) d, length of the diagonal of the box bounding the region; iii) i, first moment invariant of Hu (or moment of inertia) [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF]; and iv) s, standard deviation of the gray-level values of the pixels in the regions. The area and the length of the diagonal of the bounding box are in-creasing attributes that process the objects according to their size. The moment of inertia attribute is a purely geometric descriptor that by being sensitive to the elongation of the regions, can perform an analysis based on the geometry of the objects regardless their scale. Finally, the standard deviation attribute measures the homogeneity of the intensity values of the pixels belonging to each region in the image and it gives information related to the spectral contrast of the pixels. Four reference values, used as global thresholds λs, were considered for building each of the four EAPs, leading to 36dimensional profiles (composed by four APs of 9 levels computed on each component extracted by the original data). The thresholding values (λ) used in the filterings were arbitrarly selected and they are listed in the following: A SVM classifier with a gradient descent based approach for the selection of the parameters was applied to the data. This approach provides results which are comparable to the cross-validation method, and is much more efficient from a computational point of view [START_REF] Villa | Gradient optimization for multiple kernel's parameters in support vector machines classification[END_REF]. The classification results were quantitatively evaluated by measuring the Overall Accuracy (OA), the Average Accuracy (AA) and the Kappa coefficient (K) on the reference data.

Table 1 presents the accuracies obtained by the PCA and ICA as feature extraction techniques. It is possible to notice, when considering the PCA, how the EAP with area attribute performed the best, with more 3% of OA more than the others EAPs. By considering the proposed method of fusion, accuracies slightly smaller than the EAP area and better than all the other EAPs were obtained. Conversely, when all the EAPs are concatenated together a lower accuracy is obtained than the average of the single EAPs. When comparing the results obtained with the PCA with those of ICA, it is clear how the latter ones outperform the former set. Conversely to the PCA, by considering the independent components, the EAP with moment of inertia attribute scored the best among all the EAPs. This proves how, in this case, it is difficult to select a priori the most suitable attribute on the data. The use of all the EAPs together performed the best among all the single EAPs even for a high dimensionality of the data. The fusion of the results given by the single EAPs involved accuracies that are slightly worse than the best EAPs but higher than all the other ones. This confirmed what was assessed before.

The increase in accuracy previously quantified for the use of the ICA instead of the PCA can be visually noticed in the classification maps shown in Fig. 3. Moreover, one can see that the most precise map is obtained when considering the ICA and all the EAPs together (see Fig. 3.c).

CONCLUSION

In this paper we have presented a technique based on independent component analysis and morphological attribute filters for the classification of high resolution hyperspectral images. In greater details, from the hyperspectral image some independent components are extracted, and different attribute profiles are computed for each one, leading to extended attribute profiles. The features obtained by the morphological processing are then classified with a SVM classifier. Moreover, we proposed a robust technique for fusing the results obtained by processing the image with different attributes. The experimental results obtained on a high resolution hyperspectral image acquired on the city of Pavia, Italy, proved how the ICA is more suitable to model the different informative sources present in the scene outperforming the results of the PCA of about 4% of overall accuracy. Moreover, the choice of the most suitable attribute has been confirmed to be a non trivial task. For example, when considering the PCA the EAP with area attribute performed the best, whereas for the ICA the most accurate results were achieved by the EAP with moment of inertia. The proposed method of combining the results of the single EAPs proved to be a robust approach when no a priori information is available on the scene. This technique has obtained accuracies slightly lower than those of the best case but better than all the others.

Fig. 1 .

 1 Fig. 1. Examples of APs computed with different attributes (from row one to three): area, moment of inertia and standard deviation. They model the objects in the image according to their scale, geometry and spectral homogeneity respectively.

Fig. 2 .

 2 Fig. 2. Pavia data set: (a) True color representation, (b) Test set.

1 .

 1 EAPa: λa = [100 500 1000 5000]; 2. EAP d : λ d = [10 25 50 100]; 3. EAPi: λi = [0.2 0.3 0.4 0.5]; 4. EAPs: λs = [20 30 40 50].

Table 1 .

 1 Classification accuracies obtained according to the described scheme. The first 4 columns represent the results of SVM applied to the single EAPs. All means that the SVM is applied to the data obtained considering the outputs of the four filters, together. Fusion is obtained with the sum of the votes of the first four classifiers.

		Area Diagonal Inertia	Std	All	Fusion
	Feat.	36	36	36	36	144	(144)
			Principal Component Analysis
	OA (%)	90.00	85.42	69.80	86.56 77.81	89.21
	κ (%)	87.06	81.24	63.22	82.82 71.08	86.06
	AA (%)	92.04	89.55	82.48	91.15 86.84	92.04
		Independent Component Analysis
	OA (%)	91.26	87.94	93.57	87.69 94.47	91.69
	κ (%)	88.55	84.31	91.63	84.14 92.80	89.13
	AA (%)	92.36	91.72	95.73	90.92 96.58	94.11

ACKNOWLEDGMENTS

The authors would like to thank Prof. Paolo Gamba, University of Pavia, for providing the ROSIS data set. This work has been supported in part by the European Community's Marie Curie Research Training Networks Programme under contract MRTN-CT-2006-035927, Hyperspectral Imaging Network (HYPER-I-NET) and by the Research Fund of the University of Iceland and the University of Trento.


Yuliya Tarabalka
email: yuliya.tarabalka@hyperinet.eu

Jón Atli Benediktsson

Jocelyn Chanussot

James C Tilton

A MULTIPLE CLASSIFIER APPROACH FOR SPECTRAL-SPATIAL CLASSIFICATION OF HYPERSPECTRAL DATA

Keywords: Hyperspectral images, classification, segmentation, multiple classifiers, minimum spanning forest

A new multiple classifier method for spectral-spatial classification of hyperspectral images is proposed. Several classifiers are used independently to classify an image. For every pixel, if all the classifiers have assigned this pixel to the same class, the pixel is kept as a marker, i.e., a seed of the spatial region, with the corresponding class label. We propose to use spectral-spatial classifiers at the preliminary step of the marker selection procedure, each of them combining the results of a pixel-wise classification and a segmentation map. Different segmentation approaches lead to different classification results. Furthermore, a minimum spanning forest is built, where each tree is rooted on a classification-driven marker and forms a region in the spectral-spatial classification map. Experimental results are presented on a 103-band ROSIS image of the University of Pavia, Italy. The proposed method significantly improves classification accuracies, when compared to previously proposed classification techniques.

INTRODUCTION

The accurate classification of remote sensing images is an important task for many applications, such as monitoring and management of the environment, precision agriculture, security issues. Hyperspectral (HS) imagery, which records a detailed spectrum of light arriving at each pixel [START_REF] Chang | Hyperspectral Data Exploitation: Theory and Applications[END_REF], opens new perspectives in image analysis and classification. While pixel-wise classification techniques process each pixel independently from the pixels in its neighborhood [START_REF] Chang | Hyperspectral Data Exploitation: Theory and Applications[END_REF][START_REF] Camps-Valls | Kernel-based methods for hyperspectral image classification[END_REF], further improvement of classification accuracies can be achieved by considering spatial dependencies between pixels [START_REF] Kettig | Classification of multispectral image data by extraction and classification of homogeneous objects[END_REF][START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF].

Segmentation techniques, partitioning an image into homogeneous regions, are a powerful tool for defining spatial dependencies. In previous works, we have performed unsupervised segmentation of HS images in order to distinguish This research is supported in part by the Marie Curie Research Training Network "HYPER-I-NET". spatial structures [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF][START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF]. Segmentation and pixel-wise classification were applied independently, then results were combined using a majority voting rule. Thus, every region from a segmentation map has been considered as an adaptive homogeneous neighborhood for all the pixels within this region. However, unsupervised image segmentation is a challenging task, since the measure of region homogeneity must be chosen. An alternative way to get accurate segmentation results consists in performing a marker-controlled segmentation. Recently we have proposed to use probability estimates obtained by the pixel-wise Support Vector Machines (SVM) classification in order to choose the most reliable classified pixels as markers, i.e., seeds of spatial regions [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. Furthermore, image pixels were grouped into a Minimum Spanning Forest (MSF), where each tree was rooted on a classificationderived marker and formed a region in the spectral-spatial classification map. The described technique led to a significant improvement of classification accuracies when compared to previously proposed methods. The drawback of this method is that the choice of markers strongly depends on the performance of the selected pixel-wise classifier.

In this work, we aim to mitigate the dependence of the marker selection procedure from the choice of a pixel-wise classifier. For this purpose, a new marker selection method based on the multiple classifier (MC) system is proposed. Several classifiers are used independently to classify an image. Furthermore, a marker map is constructed by selecting the pixels assigned by all the classifiers to the same class. We propose to use spectral-spatial classifiers at the preliminary step of the marker selection procedure, each of them combining the results of a pixel-wise classification and one of the unsupervised segmentation techniques. The proposed marker selection method is incorporated into a new Multiple Spectral-Spatial Classification scheme (MSSC-MSF) based on the construction of an MSF from region markers.

The paper is organized as follows. First, the MC approach is discussed. Section 3 describes the proposed classification scheme. Experimental results are discussed in Section 4. Finally, conclusions are drawn in Section 5.

MULTIPLE CLASSIFIER APPROACH

The traditional approach for a pattern recognition problem is to search for the best individual classification algorithm. However, in many cases, the classification accuracy can be improved by using an ensemble of classifiers. The aim of an MC system is to determine an efficient combination method that makes use of the complementary benefits of each classifier, while tackling the individual drawbacks [START_REF] Briem | Multiple classifiers applied to multisource remote sensing data[END_REF].

An important issue for an efficient MC system is that the individual classifiers should not agree with each other when they misclassify a pixel. The complementary properties of the different classifiers should ensure this requirement. Another important issue is the rule for combining the individual classifiers. In the proposed method, these two issues are addressed in the following way: 1) Different segmentation methods based on dissimilar principles lead to different classification results. 2) According to the exclusionary rule, only the most reliable pixels, i.e., the pixels where all the classifiers agree, are kept in the initial classification map. The rest of the pixels are further classified by constructing an MSF rooted on the "reliable" pixels.

PROPOSED CLASSIFICATION SCHEME

The flow-chart of the proposed MSSC-MSF classification method is depicted in Figure 1. At the input a B-band HS image is given, which can be considered as a set of n pixel vectors. Classification consists in assigning each pixel to one of the K classes of interest. In the following, each step of the proposed procedure is described.

1) Watershed segmentation: Watershed transformation is a powerful morphological approach to image segmentation which combines region growing and edge detection. The watershed is usually applied to the gradient function, and it divides an image into regions, so that each region is associated with one minimum of the gradient image [START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF]. We have extended a watershed method to the case of HS images in [START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF]: First, a one-band Robust Color Morphological Gradient (RCMG) for the HS image is computed. By applying watershed transformation using a classical algorithm [START_REF] Vincent | Watersheds in digital spaces: an efficient algorithm based on immersion simulations[END_REF], the image is partitioned into a set of regions.

2) Segmentation by expectation maximization:

The Expectation Maximization (EM) algorithm for the Gaussian mixture resolving belongs to the group of partitional clustering techniques [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF]. Clustering aims at finding groups of spectrally similar pixels. We assume that pixels belonging to the same cluster are drawn from a multivariate Gaussian probability distribution. The parameters of the distributions are estimated by the EM algorithm. When the algorithm converges, the partitioning of the set of image pixels into clusters is obtained. However, as no spatial information is used during the clustering procedure, pixels with the same cluster label can form a connected spatial region, or can belong to disjoint regions. In order to obtain a segmentation map, a connected components labeling algorithm is applied to the output image partitioning obtained by clustering.

3) RHSEG segmentation: The Hierarchical image SEGmentation (HSEG) algorithm is a segmentation technique based on iterative hierarchical step-wise optimization region growing method. Furthermore, it provides a possibility of merging non-adjacent regions by spectral clustering [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader user's manual (version 1.40)[END_REF]. NASA's RHSEG software provides an efficient implementation of the HSEG algorithm. We have investigated the use of the RHSEG technique for segmentation of HS images, choosing the standard Spectral Angle Mapper (SAM) between the region mean vectors as the dissimilarity criterion [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader user's manual (version 1.40)[END_REF], and the parameter spclust wght = 0.1 (merging of spatially adjacent regions is favored). RHSEG gives as output a hierarchical sequence of image partitions. A segmentation map at the relevant level of hierarchy is chosen interactively. Finally, labeling of connected components is performed, in order to obtain a segmentation map where each spatially connected component has a unique label.

4) Pixel-wise classification:

Independently of the previous steps, a pixel-wise classification of the HS image is performed. We propose to use an SVM classifier for this purpose which is well suited for classifying HS data [START_REF] Camps-Valls | Kernel-based methods for hyperspectral image classification[END_REF]. This step results in a classification map (each pixel has a unique class label).

5) Majority voting within segmentation regions:

Each of the obtained segmentation maps is combined with the pixelwise classification map using the majority voting principle: For every region in the segmentation map, all the pixels are assigned to the most frequent class within this region. Thus, three segmentation maps combined with the pixel-wise classification map result in three spectral-spatial classification maps.

6) Marker selection:

This step consists in computing a map of markers, using spectral-spatial classification maps from the previous step and exclusionary rule: For every pixel, if all the classifiers agree, the pixel is kept as a marker, with the corresponding class label. The resulting map of markers contains the most reliable classified pixels.

7) Construction of an MSF:

In the final step, image pixels are grouped into an MSF rooted on the selected markers [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. Each pixel is considered as a vertex v ∈ V of an undirected graph G = (V, E, W ). Each edge of this graph connects a couple of vertices corresponding to the neighboring pixels (in the following, we simply call vertices as pixels). Furthermore, a weight is assigned to each edge, which indicates the degree of dissimilarity between two pixels connected by this edge. We use an 8-neighborhood and the SAM measure for computing weights of edges, as described in [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF].

Given a graph G = (V, E, W ), the MSF rooted on a set of m distinct vertices {t 1 , ..., t m } consists in finding a spanning forest F * = (V, E F * ) of G, such that each distinct tree of F * is grown from one root t i , and the sum of the edges weights of F * is minimal. Prim's algorithm can be used for building the MSF [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. A classification map is obtained by assigning the class of each marker to all the pixels grown from this marker.

EXPERIMENTAL RESULTS AND DISCUSSION

Experimental results are presented for a ROSIS (Reflective Optics System Imaging Spectrometer) image of the University of Pavia, Italy. The image is 610 × 340 pixels, with a spatial resolution of 1.3 m per pixel and 103 spectral channels. The reference data contain nine classes of interest. More information about the image, with the number of training and test samples for each class can be found in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF].

The segmentation of the considered image is performed, using the three different techniques discussed in the previous section. For the EM algorithm, the maximum number of clusters is chosen equal to 10 (typically slightly superior to the number of classes), and a feature reduction has been previously applied, using the method of piecewise constant function approximations [START_REF] Jensen | Fast hyperspectral feature reduction using piecewise constant function approximations[END_REF] to get a 10-band image.

The multi-class pairwise SVM classification, with the Gaussian Radial Basis Function kernel, of the original image is performed, with the parameters chosen by fivefold cross validation: C = 128, γ = 0.125. The results of the pixel-wise classification are combined with the segmentation results, using the majority voting approach. Finally, the marker selection and the construction of an MSF are performed, resulting in the MSSC-MSF classification map depicted in Figure 2. Table 1 summarizes the accuracies of the pixel-wise SVM, segmentation + majority voting (WH+MV, EM+MV, RHSEG+MV for three segmentation techniques, respectively) and the proposed classification method. In order to compare performances of the proposed technique with the previously proposed methods, we have also included results of the wellknown ECHO spatial classifier [START_REF] Kettig | Classification of multispectral image data by extraction and classification of homogeneous objects[END_REF], as well as the results obtained using the construction of an MSF from the probabilistic SVM-derived markers followed by majority voting within connected regions (SVMMSF+MV) [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. Furthermore, we assess the importance of spectral-spatial approaches for marker selection. For this purpose, we have replaced the WH+MV, EM+MV, RHSEG+MV classification maps by three maps obtained using standard pixel-wise classification techniques. Maximum Likelihood (ML), SVM and 3-Nearest Neighborhood (3-NN, using the SAM distance) methods have been used for this purpose. The accuracies of the modified MC-MSF classification, as well as pixel-wise classification results are given in Table 1.

As can be seen from the table, both the global and most of the class-specific accuracies are substantially improved by the proposed MSSC-MSF method, when compared to previous spectral-spatial classification techniques. The overall accuracy is improved by 16.9 percentage points, when compared to the SVM classification. The MSSC-MSF classification accuracies are much higher than the MC-MSF accuracies. These results prove the importance of the use of MC systems and spatial information throughout the classification procedure.

CONCLUSIONS

In this paper, a new MC method for spectral-spatial classification of HS images is proposed. First, a marker map is constructed by selecting the pixels assigned by several spectralspatial classifiers to the same class. This ensures a robust and reliable selection. Then, an MSF rooted on the selected markers is built. Experimental results did show that the proposed method improves classification accuracies, when compared to previously proposed classification schemes, and provides classification maps with homogeneous regions. The presented classification accuracies are higher than all previous results we have found in the literature for the same data. Similar results are obtained for other datasets acquired by the ROSIS and the AVIRIS (Airborne Visible/Infrared Imaging Spectrometer) sensors.

In conclusion, the proposed methodology succeeded in taking advantage of multiple classifiers and the spatial and the spectral information simultaneously for accurate HS image classification.

Fig. 1 .

 1 Fig. 1. Flow-chart of the proposed MSSC-MSF classification scheme.

Fig. 2 .

 2 Fig. 2. Classification map obtained by the MSSC-MSF method for the University of Pavia image.

Table 1 .

 1 Classification Accuracies in Percentage for the University of Pavia Image: Overall Accuracy (OA), Average Accuracy (AA), Kappa Coefficient (κ) and Class-Specific Accuracies.

		3-NN	ML	SVM	ECHO	WH+MV EM+MV	RHSEG +MV	SVMMSF +MV	MC-MSF	MSSC-MSF
	OA	68.38 79.06 81.01	87.58	85.42	94.00	93.85	91.08	87.98	97.90
	AA	77.21 84.85 88.25	92.16	91.31	93.13	97.07	94.76	92.05	98.59
	κ	59.85 72.90 75.86	83.90	81.30	91.93	91.89	88.30	84.32	97.18
	Asphalt	64.96 76.43 84.93	87.98	93.64	90.10	94.77	93.16	87.01	98.00
	Meadows	63.18 75.99 70.79	81.64	75.09	95.99	89.32	85.65	83.24	96.67
	Gravel	62.31 64.57 67.16	76.91	66.12	82.26	96.14	89.15	75.37	97.80
	Trees	95.95 97.08 97.77	99.31	98.56	85.54	98.08	91.24	98.97	98.83
	Metal sheets	99.73 99.91 99.46	99.91	99.91	100	99.82	99.91	99.91	99.91
	Bare soil	57.42 70.03 92.83	93.96	97.35	96.72	99.76	99.91	93.24	100
	Bitumen	82.67 90.62 90.42	92.97	96.23	91.85	100	98.57	95.11	99.90
	Bricks	77.08 90.10 92.78	97.35	97.92	98.34	99.29	99.05	97.00	99.76
	Shadows	91.57 98.87 98.11	99.37	96.98	97.36	96.48	96.23	98.62	96.48


Nihel Ben Youssef
email: nihel.benyoussef@gmail.com

Adel Bouhoula
email: adel.bouhoula@supcom.rnu.tn

Florent Jacquemard
email: florent.jacquemard@lsv.ens-cachan.fr

Automatic Verification of Conformance of Firewall Configurations to Security Policies

Keywords: security, firewall configuration, security policy, formal verification, SMT solver

The configuration of firewalls is highly error prone and automated solution are needed in order to analyze its correctness. We propose a formal and automatic method for checking whether a firewall reacts correctly wrt a security policy given in an high level declarative language. When errors are detected, some feedback is returned to the user in order to correct the firewall configuration. Furthermore, the procedure verifies that no conflicts exist within the security policy. We show that our method is both correct and complete. Finally, it has been implemented in a prototype of verifier based on a satisfiability solver modulo theories (SMT). Experiment conducted on relevant case studies demonstrate the efficiency and scalability of the approach.

Introduction

Securing network flows is a crucial and difficult task. Some specific technical knowledge and clear ideas about the global security requirement to be establish are required, but are still insufficient in order to ensure the correctness of a security configuration. One of the main reasons is the difference in semantics between, on the one hand, the security policies (SP) used to express global security requirements, and on the other hand the firewall configuration files (FC). The former are generally specified in a high level declarative language and easy to understand, whereas the latter are low-level files subject to special configuration constraints in order to ensure an efficient real time processing by specific devices. One of these constraints is in particular that the filtering rules of a FC file are treated in the order in which they are read in the configuration file, in a switch-case fashion.

For instance, if two filtering rules associate different actions to the same flow type, then only the rule with the lower order is really applied. This is in contrast with the SP, which is a set of rules considered without order. In this case, the action taken, for the flow under consideration, is the one of the non executed rule.

Several methods have been proposed [START_REF] Pornavalai | Firewall policy analyzing by relational algebra[END_REF][START_REF] Al-Shaer | Firewall policy advisor for anomaly detection and rule editing[END_REF][START_REF] Benelbahri | Tuple based approach for anomalies detection within firewall filtering rules[END_REF][START_REF] Abbes | Inference system for detecting firewall filtering rules anomalies[END_REF] for the detection of inter-rule conflicts in FC. These work are limited to the problem conflict avoidance, and do not consider the more general problem of verifying whether a firewall reacts correctly wrt a given SP. Solutions are studied in [START_REF] Hazelhusrt | Algorithms for analyzing firewall and router access lists[END_REF], [START_REF] Eronen | An expert system for analyzing firewall rules[END_REF], and [START_REF] Lui | Firewall queries[END_REF] for the analysis of firewalls' behavior. These methods require some final user interactions by sending queries through a verification tool. Such manual solution can be tedious when checking discrepencies wrt complicated security requirements. In [START_REF] Cupens | A formal approach to specify and deploy a network security policy[END_REF] and [START_REF] Hamdi | A domain specific language for securing distributed systems[END_REF] the author address the problem of automatic verification by providing automatic translation tool of the security requirements (SP), specified in a high level language, into a set of ordered filtering rule (i.e. a FC). Therefore, these methods can handle the whole problem of conformance of FC to SP, but the validity of the compilation itself has not been proven. In particular, the FC rules obtained may be in conflict.

In this paper, we propose an automatic and generic method for checking whether a firewall is well configured wrt a security policy, given in an expressive enough declarative language. Furthermore, the proposed method ensures conflicts avoidance within the SP that we aim to establish and returns key elements for the correction of a flawed FC. Our method has been implemented as a prototype which can be used either in order to validate an existing FC wrt a given SP or downstream of a compiler of SP. It can also be used in order to assist the updates of FC, as conflicts may be created by the addition or deletion of filtering rules.

The remainder of this paper is organized as follows. Section 2 settles the definition of the problems addressed in the paper, in particular the properties of soundness and completeness of a FC wrt SP. In Section 3, we present an inference system introducing the proposed method and prove its correctness and completeness. Section 4 elaborates our the verification procedure. Finally, in Section 5 we present an automatic verification tool that we have implemented based on our method and some experiments on a case study.

Soundness and Completeness Properties

The main goal of this work consists in checking whether a FC is sound and complete wrt a given SP. In this section, we define formally these notions.

We consider a finite domain P containing all the headers of packets possibly incoming to or outgoing from a network. A firewall configuration (FC) is a finite sequence of filtering rules of the form F C = (r i ⇒ A i ) 0≤i<n . Each precondition r i of a rule defines a filter for packets of P. The structure of r i is described later in Section 5. Before, we just consider a function dom mapping each r i into the subset of P of filtered packets. Each right member A i of a rule of F C is an action defining the behaviour of the firewall on filtered packets: A i ∈ {accept, deny}. This model describes a generic form of FC which are used by most firewall products such as CISCO, Access Control List, IPTABLES, IPCHAINS and Check Point Firewall...

A security policy (SP) is a set SP of formulae defining whether packets are accepted or denied. The nature of the formulae is described in Section 4. In Section 3, we only consider the definition domain of SP , partitioned into

dom(SP ) = A∈{accept,deny} SP A . SP is called consis- tent if SP accept ∩ SP deny = ∅.
A FC is sound wrt a SP if the action undertaken by the firewall for each forwarding packet, (i.e. the action of the first filtering rule matching the packet) is the same as the one defined by the SP.

Definition 1 (soundness) F C is sound wrt SP iff for all p ∈ P, if there exists a rule r i ⇒ A i in F C such that p ∈ dom(r i ) and for all j < i, p / ∈ dom(r j ) then p ∈ SP A i .

A FC is complete wrt a SP if the action defined by the SP for each packet p is really undertaken by the Firewall.

Definition 2 (completeness) F C is complete wrt SP iff for all p ∈ P and A ∈ {accept, deny}, if p ∈ SP A then there exists a rule r i ⇒ A in F C such that p ∈ dom(r i ) \ j<i dom(r j ).

Inference System

We propose in this section necessary and sufficient condition for for the simultaneous verification of the properties

recurcall ((r ⇒ A); F C), D F C, D ∪ dom(r) if dom(r) \ D ⊆ SP A success ∅, D success if D ⊇ dom(SP ) failure F C, D fail(fst(F C), D)
if no other rule applies This latter subset represents the accumulation of the sets of packets filtered by the rules of F C processed so far. We write C SP C is C is obtained from C by application of an inference rule of Figure 1 (note that C may be a couple as above or one of success or fail) and we denote by * SP the reflexive and transitive closure of SP . recurcall is the main inference rule. It deals with the first filtering rule r i ⇒ A of the FC given in the couple. The condition for the application of this rule is that the set of packets dom(r i ) filtered by this rule and not handled by the previous rules (i.e. not in D) would follow the same action A according to the the security policy. Hence, successful repeated applications of recurcall ensures the soundness of the FC wrt the SP.

The success rule is applied under two conditions. First, recurcall must have been used successfully until all filtering rules have been processed (in this case the first component F C of the couple is empty). Second, the domain global security policy must be included in D. This latter condition ensures that all the packets treated by the security policy are also handled by the firewall configuration (completeness of FC).

There are two cases for the application of failure. In the first case, failure is applied to a couple (F C, D) where F C is not empty. It means that recurcall has failed on this couple and hence that the FC is not sound wrt the SP. In this case, failure returns the first filtering rule of F C as a example of rule which is not correct, in order to provide help to the user in order to correct the FC. In the second case, failure is applied to (∅, D). It means that success has failed on this couple and that the FC is not complete wrt the SP. In this case, D is returned and can be used in order to identify packets handled by the SP and not by the FC.

Let us now prove that the inference system of Figure 1 is correct and complete. From now on, we assume given a FC F C = r 0 ⇒ A 0 , . . . , r n-1 ⇒ A n-1 with n > 0.

In the correctness theorem below, we assume that SP is consistent. We shall present in the next sections a method for checking this property.

Theorem 1 (correctness) Assume that the security policy SP is consistent. If (F C, ∅) * SP success then the firewall configuration F C is sound and complete wrt SP .

Proof. If (F C, ∅) * SP success then we have (F C, ∅) SP (F C 1 , D 1 ) SP . . . SP (F C n , D n ) SP success, where F C n = ∅,
all the steps but the last one are recurcall and dom(SP ) ⊆ D n . We can easily show by induction on that for all

1 ≤ i ≤ n, D i = j<i dom(r j ). Let D 0 = ∅.
Assume that there exists p ∈ P and Proof. Either we can apply iteratively the recurcall rule starting with (F C, ∅), until we obtain (∅, j<n dom(r j )), or one application of the recurcall rule fails. In the latter case, there exists i < n such that dom(r i ) \ j<i dom(r j ) SP A i . Therefore, there exists p ∈ P such that p ∈ dom(r i ) \ j<i dom(r j ) and p / ∈ SP A i . It follows that F C is not sound wrt the security policy SP .

r i ⇒ A i in F C (i < n) such that p ∈ dom(r i ) \ j<i dom(r j ). It follows that p ∈ dom(r i ) \ D i ,
If (F C, ∅) * S P (∅, j<n dom(r j )) using recurcall but the application of the success rule to the last couple fails,

    c 1 ⇒ accept | e 1 c 2 ⇒ deny c 3 ⇒ accept c 4 ⇒ deny | e 4    

Figure 2. A Security Policy

then there exists A ∈ {accept, deny} and p ∈ SP A such that p / ∈ j<n dom(r j ). It follows that F C is not complete wrt the security policy SP .

Since the application of the inferences to (SP, ∅) always terminates, and the outcome can only be success or fail, it follows immediately from the Theorem 1 that if the firewall configuration F C is not sound or not complete wrt the security policy SP , then (F C, ∅) * SP fail (completeness of failure).

To summarize the above results, we have the following sufficient and necessary conditions for soundness: ∀i < n, dom(r i ) \ j<i dom(r j ) ⊆ SP Ai , completeness: soundness and dom(SP ) ⊆ i<n dom(r i ).

Verification Procedures

We describe in this section how to express the conditions for the above inference system of Section 3 as satisfiability problems for propositional formulae.

We consider a security policy which is presented as a finite set of directives:

SP = {c i ⇒ A i |e i | 1 ≤ i ≤ m}.
Each directive can be simple or complex. A simple directive describes whether a traffic destinated to one or more services that are required by one or more sources and given by one or more destinations (as described by the condition c i ) must be accepted or refused (according to A i ∈ {accept, deny}). A complex directive is basicly a simple directive but considering some exceptions defined in e i . The following examples are respectively simple and complex directives.

• A sub network LAN A has the right to access to the web service provided by a machine B located in the sub network LAN B .

• A sub network LANA, except the machine A , has the right to access to the web service provided by a machine B located in the sub network LANB.

The condition of the above second directive refers to the flow between the source LAN A and the destination B, the directive action is accept, and its exception is the source machine A . The conditions and the exceptions are expressed as conjunctions of logic propositions describing the following main fields: source(s), destination(s) and service(s).

Security Policy Consistency

As explained in Section 3, the SP must be consistent in order to ensure the correctness of the verification method. Hence in a first step, we shall check that the domains of accepted and denied packets, SP accept and SP deny , do not overlap. The set of accepted packets SP accept , is the union of one set for each directive. Each set represents either the domain of a simple directive, if the action of the corresponding condition is accept, or the domain of a complex directive's exception, if its action is deny or else the difference between the domains of the condition and the exception of a complex directive if its main action is accept. The set of denied packets is definied symmetrically. We express the above sets by propositional formulas φ a and φ d defining respectivelly the domains of accepted and denied packets. In the case of the SP of Figure 2, their definitions are

φ a ::= (c 1 ∧ ¬e 1 ) ∨ c 3 ∨ e 4 φ d ::= e 1 ∨ c 2 ∨ (c 4 ∧ ¬e 4 )
In order to ensure that the domains do not overlap, we prove the insatisfiability of the following propositional formula φ a ∧ φ d . It ensures that no packet satisfies simultaneously φ a and φ d .

Soundness Verification

Our goal is to check whether a firewall configuration F C = {r i ⇒ A i | 0 ≤ i < n} is sound wrt the above security policy SP .

According to Section 3, the condition for the soundness of F C wrt SP is that, for each filtering rule r i ⇒ A i , the domain dom(r i ) minus the accumulated domains of the previous rules, is included in the set of packets that should undergo, according to SP , the same action as A i of the filtering rule. The soundness condition is equivalent to the insatisfiability of all the following propositional formulae, for 0 ≤ i < n (expressing the negation of the soundness condition in Section 3): φ i ∧¬φ A i where φ i ::= φ r i ∧¬(∨ i-1 j=1 φ r j ) and φ Ai is defined as above.

Completeness Verification

As explained in Section 3, in order to verify the completeness property of a firewall configuration, we check that the domain of the security policy SP is included in that of the firewall configuration F C. Theses domains are made of the unions of the respective domains of filtering rules and security directives, as expressed by the following formulae.

φ SP ::= m i=1 c i φ F C ::= n-1 i=0 r i
The completeness condition of Section 3 is the insatisfiability of of the following formula: φ SP ∧ ¬φ F C .

Automatic Verification tool

The above presentation of the conditions of Section 3 permits the automation of the verification of soudness and completeness of FC wrt SP. In fact, in the previous section, these properties are expressed as satisfiability problems.

We have used a recent satisfiability solver modulo theories, Yices [START_REF] Dutertre | The yices smt solver[END_REF], in order to describe the different inputs and to automate the verification process. Yices provides different additional functions, compared to simple satisfiability solvers. These functions are based on theories like those of arrays, list structures and bit vectors.

The first input of our verification tool is a set of firewall rules. Each rule is defined by a priority order and composed of the following main fields: the source, the destination, the protocol and the port. The source and destination fields correspond to one or more machines identified by an IPv4 address and a mask coded both on 4 bytes, each bit being represented by a proposition variable. For better readability, we consider in this section the IP coding on 4 bits. For example, the following expression written in Yices syntax refers to the third filtering rule concerning UDP or TCP flow, coming from the source network 1.0.0.0/2 and reaching the network 1.1.0.0/3 for a destination port belonging to the subrange [20 -60].

(define r :: (-> int bool))(assert (= (r 3) (and ips4 (not ips3) ipd4 ipd3 (not ipd2) (>= port 20) (<= port 60) (or (= protocol tcp) (= protocol udp))))).

In order to illustrate the verification procedure proposed, we have chosen to apply our method to a case study of a corporate network represented in Figure 3. The network is divided into three zones delineated by branches of a firewall whose initial configuration F C corresponds to the rules in Table 1. The security policy SP that should be respected contains the following directives. In the following, we note that d i and d i are respectively the condition and the exception of the security directive sp i . Table 1. Firewall Configuration to be Verified

Our goal is to verify that the configuration F C is conform to the security policy SP by checking the soundness and the completeness properties. But first, we must verify that the security policy is consistent.

Security Policy Consistency Verification

After we specified the security policy SP in Yices syntax, checking the consistency of SP amounts to check satisfiability. We have obtained the satisfiability result displayed in Figure 4.

Note that the Yices option e (evidence) displays a model if the logic expression is satifiable. In our case, this means that the security policy is not consistent. An analysis of the model obtained shows that the directives sp 1 and sp 3 have contradictory decisions. It concerns on the flow coming from a machine belonging to net 1 and destinated the DNS service of the DNS server 1.0.0.1. Indeed, the third directive indicates that the network net 1 has not the right to access to the DNS server of net 2 while the first directive permits it. One possible correction would be to replace the two directives in conflict by the following single complex directive.

Soundness Verification

Once ensured that the security policy is consistent, we proceed to the verification of the firewall configuration soundness, using the formulae of Section 4, which express the conditions of Section 3. The satisfiability result obtained is displayed in Figure 5. The outcome shows that the firewall configuration F C is not sound wrt the security policy SP , i.e. that there exists some packets that will undergo an action different of that imposed by the security policy. It indicates also that r 3 is the first rule that causes this discrepancy precisely with the exception of directive sp 1 . Indeed, the model returned corresponds to a packet accepted by the firewall through the rule r 3 while it should be refused according to the first directive of the security policy. This conflict can be resolved by adding a rule immediately preceding the rule r 3 , which allows to implement the first directive exception precised by the given model. Table 2 presents this modification.

Completeness Verification

After that the soundness property has been established, we proceed to the verification of the completeness of the firewall configuration. We obtained the satisfiability result displayed in Figure 6.

According to this outcome, the configuration F C is not complete wrt the security policy SP : some packets handled by the security policy are not treated by the filtering rules. Indeed, the rule r 4 addresses only a subnetwork of net 2.

Figure 6. Completeness verification

The packet corresponding to the model returned belongs to another part of net 2, which is untreated. One possible solution would be to change, as shown in Table 3, the mask used in the destination address of the rule r 4 to consider all the first directive domain. We note that YICES validated the three properties after the modifications taken in sections 5.1, 5.6 and 5.3 by displaying in each case an insatisfiability result.

Experimental Results

In order to better assess the performance of the Yices tool for checking satisfiability of propositional formulas, we consider time treatement factor that we review by varying the different parameter sizes provided by the solver. In overall terms, we consider the average processing time of the three verification procedures (securtity policy consistency, firewall configuration soundness and completeness) by varying the total number of Boolean variables used. We note that we treat real field values such IPv4 address and port range. To perform this study, we used the option st of Yices to collect statistical information. The experimental tests were conducted on an Intel Dual core 1.6 GHz with 1 Gbyte of RAM.

Table 4. Processing time evaluation

The experimental results are summarized in Table 4. The tool processing time obtained shows that our tool performed efficiently on the case studies.

Conclusion

In this paper, we propose a formal method for certifying automatically that a firewall configuration is sound and complete wrt a security policy. Otherwise, the method provides key information helping users to correct configuration errors. Our method permits also to prove the consistency of a security policy which is a necessary condition for the verification procedure. Finally, our method has been implemented using the satisfiability solver Yices. The experimental results obtained are very promising.

As further work, we are considering to extend the approach in order to handle stateful firewall configurations.

Figure 1 .

 1 Figure 1. Inference System

sp 1 :

 1 net 1 has the right to access to net 2.

sp 2 :

 2 The machine admin has the right to access to the FTP service provided by the FTP server belonging to net 3.

sp 3 :

 3 net 1 has not the right to access to the DNS service provided by the DNS server belonging to net 2.

Figure 3

 3 Figure 3. Network Architecture Example src adr dst adr protocol dst port action r 1 1.1.1.1 0.1.1.1 21 tcp accept r 2 1.1.1.0 1.0.0.1 53 udp deny r 3 1.1.1.0/3 1.0.0.0/3 * * accept

Figure 4 .Figure 5 .

 45 Figure 4. Coherence verification

  and, by the condition of recurcall that p ∈ SP Ai . Hence F C is sound wrt SP .Let A ∈ {accept, deny} and p ∈ SP A . By the condition of the inference rule success, p ∈ D n = j<i dom(r j ). Let i be the smallest integer k such that p ∈ dom(r k ). It means that p ∈ dom(r i ) \ j<i dom(r j ). As above, it follows that p ∈ SP Ai , and hence that A i = A, by the hypothesis that SP is consistent. Therefore, F C is complete wrt SP . SP fail then the firewall configuration F C is not sound or not complete wrt the security policy SP .

Theorem 2 (completeness) If the firewall configuration F C is sound and complete wrt the security policy SP then (F C, ∅) * SP success. Proof. Assume that F C it is sound and complete wrt SP . The soundness implies that for all i < n and all packet p ∈ dom(r i ) \ j<i dom(r j ), p ∈ SP A i . It follows that (F C, ∅) SP (F C 1 , D 1 ) SP . . . SP (F C n , D n ) with D i = j<i dom(r j ) for all i ≤ n and F C n = ∅, by application of the inference recurcall. Moreover, the completeness of F C implies that every p ∈ dom(SP ) also belongs to D n . Hence (F C n , D n ) SP success, and altogether (F C, ∅) * S P success. Theorem 3 (soudness of failure) If (F C, ∅) *

Table 2 . A Sound Firewall Configuration

 2

Table 3 . A sound and complete FC

 3

		src adr	dst adr	protocol	dst port	action
	r 1	1.1.1.1	0.1.1.1	21	tcp	accept
	r 2	1.1.1.0	1.0.0.1	53	udp	deny
	r 3	1.1.1.1	1.0.0.1	53	udp	deny
	r 4	1.1.1.0/3 1.0.0.0/2	*	*	accept