Valentina Garibotto
email: valentina.garibotto@hcuge.ch

PhD Sara Trombella

PhD Luigi Antelmi

PhD Paolo Bosco

PhD Alberto Redolfi

MD Claire Tabouret-Viaud

MD Olivier Rager

MD Gabriel Gold

MD Panteleimon Giannakopoulos

MD Silvia Morbelli

MD Flavio Nobili

MD Robert Perneczky

Mira Didic

Eric Guedj

Alexander Drzezga

Rik Ossenkoppele

Bart Van Berckel

MD Osman Ratib

MD Giovanni B Frisoni

A comparison of two Statistical Mapping Tools for Automated Brain FDG-PET analysis in predicting conversion to Alzheimer's Disease in Subjects with Mild Cognitive Impairment

Keywords: FDG-PET, Alzheimer's disease, MCI, Automated analysis, tatistical parametric mapping, Hypometabolic pattern

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

Introduction

The availability of biological markers of neurodegeneration and synaptic dysfunction, such as FDG-PET, provides clinicians with the opportunity to improve diagnostic accuracy in clinical practice [START_REF] Chetelat | Amyloid-PET and (18)F-FDG-PET in the diagnostic investigation of Alzheimer's disease and other dementias[END_REF]. There is now evidence that pathophysiological events leading to neurodegeneration in Alzheimer's Disease (AD) initiate several years before the clinical manifestation of dementia [START_REF] Jack | Tracking pathophysiological processes in Alzheimer's disease: an updated hypothetical model of dynamic biomarkers[END_REF]. The identification of pathological subjects before clinical diagnosis of dementia constitutes one of the challenges of modern research in neurodegenerative diseases.

Mild cognitive impairment (MCI) is the diagnostic term that describes the prodromal/predementia stage of neurodegeneration. The discrimination between progressive and non-progressive MCI and the identification of different diagnostic outcomes within the class of progressive MCI patients currently has great practical relevance and stands as one of the key topics in dementia research. The more relevant clinical outcome in the MCI patient population is conversion to dementia, i.e., loss of functional autonomy, within the 2 to 3 years following the diagnosis. For this purpose, the biomarker providing the best diagnostic performance for the prediction of conversion in MCI has been identified as the typical ADpattern of hypometabolism in FDG PET images and therefore, has been included in the clinical guidelines [START_REF] Frisoni | Imaging markers for Alzheimer disease: which vs how[END_REF][START_REF] Morbelli | A Cochrane review on brain [(1)(8)F]FDG PET in dementia: limitations and future perspectives[END_REF][START_REF] Garibotto | Clinical validity of brain fluorodeoxyglucose positron emission tomography as a biomarker for Alzheimer's disease in the context of a structured 5-phase development framework[END_REF][START_REF] Albert | The diagnosis of mild cognitive impairment due to Alzheimer's disease: recommendations from the National Institute on Aging-Alzheimer's Association workgroups on diagnostic guidelines for Alzheimer's disease[END_REF][START_REF] Nobili | European Association of Nuclear Medicine and European Academy of Neurology recommendations for the use of brain (18) F-fluorodeoxyglucose positron emission tomography in neurodegenerative cognitive impairment and dementia: Delphi consensus[END_REF]. However, the analysis of FDG-PET images is still flawed by a large variability in the literature, and in clinical practice, and the method for assessment as well as the threshold for abnormality required to accurately predict conversion in MCI individuals is still a matter of debate [START_REF] Garibotto | Clinical validity of brain fluorodeoxyglucose positron emission tomography as a biomarker for Alzheimer's disease in the context of a structured 5-phase development framework[END_REF]. The lack of a homogeneous and objective reference for defining a normal test is one of the main limitations preventing stronger recommendations for the use of FDG PET in MCI [START_REF] Smailagic | 1)(8)F-FDG PET for the early diagnosis of Alzheimer's disease dementia and other dementias in people with mild cognitive impairment (MCI)[END_REF]. The statistical parametric mapping methods allow for a more objective investigation of the relationship between metabolic changes in the brain and their anatomical location, and there is an overall agreement in the community that they should support visual reading [START_REF] Frisoni | Imaging markers for Alzheimer disease: which vs how[END_REF][START_REF] Morbelli | A Cochrane review on brain [(1)(8)F]FDG PET in dementia: limitations and future perspectives[END_REF][START_REF] Frisoni | Strategic roadmap for an early diagnosis of Alzheimer's disease based on biomarkers[END_REF][START_REF] Cerami | Brain metabolic maps in Mild Cognitive Impairment predict heterogeneity of progression to dementia[END_REF]. The use of an automated method has the advantage of providing an objective threshold of normality, required for a systematic validation of the utility of FDG PET as a disease biomarker. A binary readout of FDG PET images, as well as of other biomarkers, is also encouraged by the new "ATN system," classifying subjects on the basis of the presence of A: amyloid, T: tau, and N: neurodegeneration, as adopted in the latest research criteria of the National Institute of Aging [START_REF] Jack | NIA-AA Research Framework: Toward a biological definition of Alzheimer's disease[END_REF]. While there is an agreement on the need for a standardized approach, there is no consensus on which tool should be used for this purpose, and various solutions, commercial and freeware, exist and have been tested. Previous studies have observed a highly variable diagnostic performance with the support of automated analyses, which could be strongly influenced by the use of different tools in different studies [START_REF] Cerami | Brain metabolic maps in Mild Cognitive Impairment predict heterogeneity of progression to dementia[END_REF][START_REF] Morbelli | Visual versus semi-quantitative analysis of 18F-FDG-PET in amnestic MCI: an European Alzheimer's Disease Consortium (EADC) project[END_REF][START_REF] Caroli | Summary metrics to assess Alzheimer disease-related hypometabolic pattern with 18F-FDG PET: head-to-head comparison[END_REF].

The aim of this study was to compare the parametric maps calculated by two largely used automated voxel-wise methods (SPMGrid and BRASS) in evaluating FDG PET images of MCI and healthy controls (HC) and to estimate and identify the associated diagnostic performance on baseline MCI subjects converting to AD dementia over a follow-up of three years.

Material and methods

Subject selection

The scans analyzed in this study were selected from the FDG-PET project of the European Alzheimer's Disease Consortium (EADC) (www.eadc.info), which pools FDG-PET scans with related clinical and neuropsychological information from the contributing centers. We adopted the following inclusion criteria:

1. A diagnosis of normal cognition or MCI at baseline; 2. A conversion to probable AD during follow-up or a minimum follow-up duration of 36 months for non-converters.

We selected a total number of 131 cases, in particular from the five EADC centers of Brescia (17 subjects), Genoa (61 subjects), Munich (30 subjects), Amsterdam (17 subjects), and Marseille (6 subjects). The used diagnostic criteria have been described in detail elsewhere [START_REF] Morbelli | Visual versus semi-quantitative analysis of 18F-FDG-PET in amnestic MCI: an European Alzheimer's Disease Consortium (EADC) project[END_REF].

The selected dataset included 90 MCI and 41 HC. During the follow-up time, 56 out of the 90 MCI patients progressed to AD dementia (MCI to AD -M: F = 24:32; age: 72±1).

Out of the remaining 34 MCI patients: 32 remained in the MCI stage (MCI to MCI -M: F = 20:12; age: 67±2), and 2 were reverted to normal condition during the follow-up (MCI to normal -M: F = 1:1; age: 77±0). All healthy controls remained stable (HC -M: F = 18:23; age: 67±1). This dataset optimally reflects the characteristic variability of clinical reality, inclusive of pathological subjects as well as of worried-well subjects.

Imaging

FDG-PET scans were performed within two months from baseline clinicalneuropsychological examination and were performed following the European Association of Nuclear Medicine (EANM) procedural guidelines [START_REF] Varrone | EANM procedure guidelines for PET brain imaging using [18F]FDG, version 2[END_REF]. 185-250 MBq of FDG were injected into the subject intravenously. The acquisition of 3D emission scans started at least 30 minutes post-injection and lasted at least 10 minutes. The image reconstruction was performed via an ordered subset expectation maximization (OSEM) algorithm in all centers but Amsterdam (FBP). Attenuation correction was based on CT in Brescia, Genoa, and Marseille, and on transmission scan, in Munich and Amsterdam. Scatter correction was applied using standard manufacturer software. DICOM files were exported and converted to Analyze format. Anonymous scans and clinical information were uploaded in a dedicated secured file transfer protocol (FTP) online platform. Structural neuroimaging was available for all patients (mainly, magnetic resonance imaging (MRI) or, as an alternative, computed tomography (CT) when no MRI was possible because of contraindications or patient intolerance). The study was approved by the local Medical Ethics Committee in each center and all the recruited subjects provided written informed consent [START_REF] Morbelli | Visual versus semi-quantitative analysis of 18F-FDG-PET in amnestic MCI: an European Alzheimer's Disease Consortium (EADC) project[END_REF].

Image preprocessing with SPMGrid

Baseline FDG-PET images were processed with the SPMGrid analysis tool. SPMGrid is the implementation of SPM8 [START_REF] Friston | Statistical parametric maps in functional imaging: A general linear approach[END_REF] on the online e-infrastructure for neuroimaging, neuGRID [START_REF] Redolfi | Brain investigation and brain conceptualization[END_REF]. SPMGrid provides an automated PET-based pipeline to process and test FDG-PET scans voxel-wise for hypometabolism against a control group of 107 healthy subjects from the EADC dataset with a mean age of 67.2 (SD: 6.7). Four regressors were fitted for the analysis (1. Indicator function for the test case; 2. Indicator function for the control group; 3. Subject age; 4. Total FDG uptake), yielding a total number of 103 degrees of freedom. In order to test for hypometabolism, the t-contrast [-1 1 0 0] was applied. The result of the analysis was not thresholded tridimensional Students t-map of the brain, in the ICBM152 atlas space [START_REF] Mazziotta | A probabilistic atlas and reference system for the human brain: International Consortium for Brain Mapping (ICBM)[END_REF]. Higher t-values were less consistent with the null hypothesis, and the voxelwise difference between the individual and the control group was equal to zero, indicating that the alternative hypothesis of hypometabolism got stronger as the t-value was increased.

Image preprocessing with Hermes BRASS

Baseline FDG-PET images were processed with the Brain Analysis Software v3.5 (BRASS, Hermes Medical Solutions, Stockholm, Sweden) on a Hermes workstation (Nuclear Diagnostics, Stockholm, Sweden) [START_REF] Garibotto | Regions of interest-based discriminant analysis of DaTSCAN SPECT and FDG-PET for the classification of dementia[END_REF]. BRASS provides an automated PET-based pipeline to process and test FDG-PET scans, voxel-wise for hypometabolism against a control group of 30 normal individuals with a mean age of 62.2 (SD: 7.8). Individual data are scaled to the total count in the brain volume, identified with an implicit masking of 0.8 of the maximum value. Age is not taken into account for the analysis. The result of the analysis is an unthresholded tri-dimensional Gaussian z-map of the brain in the reference template database. The more extreme the z-value, the more the tested voxel differs from the reference one.

Comparison of statistical maps

A linear transformation from the BRASS reference template space to the ICBM152 atlas space was calculated with a registration tool in FSL, FLIRT (FMRIB's Linear Imaging Registration Tool), by using the default values (https://fsl.fmrib.ox.ac.uk/fsl/fslwiki/FLIRT).

FLIRT is an automated tool allowing a robust and accurate registration of brain images, as previously shown with quantitative experiments on different modalities [START_REF] Jenkinson | Improved optimization for the robust and accurate linear registration and motion correction of brain images[END_REF]. The transformation was applied to the BRASS z-maps, resulting in images in a common reference space and numerically equivalent to the SPMGrid t-maps. Mean SPMGrid t-values and BRASS z-values were extracted for every anatomical region of interest (ROI) defined in the AAL atlas [START_REF] Tzourio-Mazoyer | Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain[END_REF]. The average BRASS z-value was plotted against the average SPMGrid tvalue for each ROI and for each subject in this study. Pearson's R correlation coefficient was computed as a measure of agreement.

For the evaluation of the level of concordance between the maps, Dice scores were computed.

A Dice score for binary variables A and B is defined as the intersection of A and B divided by the union of A and B. The Dice value will, therefore, be equivalent to 1 if A and B have the same logical value in every pixel, and a value of 0 if they always disagree. In our case, the binary variables of interest were the volumetric z-maps and t-maps thresholded at a pvalue threshold of 0.05, which were uncorrected for multiple comparisons. The two binary maps had a value of 1 for all significantly hypometabolic voxels and a value of 0 for the rest of the volume. Thus, the Dice scores provide a measure of the amount of spatial overlap of the hypometabolic patterns identified by the two software, relative to the sum of the hypometabolic regions detected by each [START_REF] Presotto | Validation of (18)F-FDG-PET Single-Subject Optimized SPM Procedure with Different PET Scanners[END_REF]. This indicator can, therefore, quantitatively complement the visual interpretation of the abnormal maps provided by the three readers.

Visual rating of statistical maps

Statistical maps were overlapped to a template MRI scan in the ICBM152 atlas space and were displayed as a fixed multislice sequence at p < 0.001, uncorrected for multiple comparisons. Three blinded independent expert readers evaluated the multislice set for visual rating. Based on the identified hypometabolic pattern, a neuro-imaging diagnosis of normal or abnormal distribution was assigned.

Raters' instructions were operationalized as follows: if negative (or only small scattered areas of abnormality), the image was considered normal, and otherwise abnormal. An agreement was reached on the neuro-imaging diagnosis based on the majority of the rates on the individual case.

Figure 1 shows examples of the SPM and BRASS output in 3 individual cases.

Statistical analysis

The assigned neuro-imaging diagnosis on FDG-PET images acquired at baseline was compared to the clinical diagnosis at follow-up, assumed as gold-standard, in order to evaluate the performance of the two tests in predicting progression to AD dementia in MCI patients. MCI patients that converted to AD at follow-up (clinical diagnosis of AD) were considered as true positive (TP) if a hypometabolic pattern was diagnosed from neuroimaging at baseline, as a false negative otherwise (normal distribution). Each MCI patient that remained stable or reverted to normal at follow-up (clinical diagnosis) was considered as a true negative (TN) if a normal metabolic pattern was radiologically diagnosed at baseline and as a false positive (FP) otherwise. Sensitivity, specificity, accuracy, and other relevant statistical values were computed for the software-assisted visual rating (both for SPMGrid and BRASS), for each rater, and the majority agreement among rater neuroimaging diagnosis, as a measure of prediction of accuracy when considering conversion to dementia. The McNemar χ2 test was applied: 1. To neuro-imaging diagnosis among MCI converting to AD only to compare the sensitivities of the two software tools; 2. To neuroimaging diagnosis among healthy only individuals to assess the significance of the difference between specificities [START_REF] Trajman | McNemar chi2 test revisited: comparing sensitivity and specificity of diagnostic examinations[END_REF].

The Intraclass Correlation Coefficient (ICC) was calculated to assess inter-rater reliability [START_REF] Shrout | Intraclass correlations: uses in assessing rater reliability[END_REF].

Results

Comparison of the output of the two tools and ROI correlation

The t-map and z-map calculated with SPMGrid and BRASS, respectively, showed a good correlation for the majority of individual cases (R > .50 for 128 subjects, out of 131), and for the majority of the ROIs, as identified in the AAL atlas (R > .50 for 98 ROIs, out of 116). A plot selection of the average BRASS z-value versus the average SPMGrid t-value, per subject and per ROI, have been reported in Figure 2, 3, and 4 (selection of relevant ROIs for the prognostic evaluation of MCI subjects). However, a low average Dice score (36%) was measured when comparing the regions of the hypometabolic patterns from the two analyses, indicating that, on average, the hypometabolic regions estimated by the two software have poor percentage overlap.

Consistently, poor agreement for the individual classification was in general observed when comparing the majority agreement neuro-imaging diagnosis for the two software tools (ICC = .54).

Computer-assisted Diagnostic performance by the two software tools

The results of the software-assisted visual rating for the two software tools have been reported in Table 1. Sensitivity was tested significantly higher for BRASS, for the three single raters and for the majority agreement (McNemar test on the diseased subject at follow-up), whereas specificity was tested significantly higher for SPMGrid, for the single raters and for the majority agreement (McNemar test over the healthy subject at follow-up).

A good to excellent inter-rater reliability was observed for SPMGrid when considering two categories of neuro-imaging diagnosis (0.86, 95% CI: 0.82-0.9), which wwere higher than the inter-rater reliability calculated for BRASS (0.76, 95% CI: 0.68-0.82).

Discussion

The most recent definition of AD, as well as other types of dementia, associates the evidence for specific underlying pathophysiology of the disease with its traditional clinical definition. FDG-PET stands among the biological markers included in contemporary diagnostic criteria for AD pathology, also in the MCI stage [START_REF] Albert | The diagnosis of mild cognitive impairment due to Alzheimer's disease: recommendations from the National Institute on Aging-Alzheimer's Association workgroups on diagnostic guidelines for Alzheimer's disease[END_REF][START_REF] Dubois | Advancing research diagnostic criteria for Alzheimer's disease: the IWG-2 criteria[END_REF]. Reimbursement of FDG-PET for the differential diagnosis of AD and FTD is nowadays authorized by the majority of national health services in Europe for the image acquisition and conventional visual reading [START_REF] Frisoni | Strategic roadmap for an early diagnosis of Alzheimer's disease based on biomarkers[END_REF].

Despite international recommendations have agreed on the fact that automated or semiautomated techniques should complement the traditional visual rating [START_REF] Varrone | EANM procedure guidelines for PET brain imaging using [18F]FDG, version 2[END_REF], no standardization has been carried out yet regarding procedures for assessing the typical hypometabolic AD pattern. The lack of standardized criteria can lead clinicians to use biomarkers in a subjective way, based on their own practice and experience, rather than clinical and evidence-based objective assumptions. The inhomogeneity of the analytic approaches explains a large part of the variability of the diagnostic performance of FDG in MCI. It has also been one of the main criticisms that a recent Cochrane review has identified [START_REF] Morbelli | A Cochrane review on brain [(1)(8)F]FDG PET in dementia: limitations and future perspectives[END_REF][START_REF] Smailagic | 1)(8)F-FDG PET for the early diagnosis of Alzheimer's disease dementia and other dementias in people with mild cognitive impairment (MCI)[END_REF]. The lack of a standardized threshold for abnormality is a major milestone in the process of the validation of the clinical utility of FDG PET as a biomarker [START_REF] Garibotto | Clinical validity of brain fluorodeoxyglucose positron emission tomography as a biomarker for Alzheimer's disease in the context of a structured 5-phase development framework[END_REF][START_REF] Frisoni | Strategic roadmap for an early diagnosis of Alzheimer's disease based on biomarkers[END_REF]. For this reason, being associated with the increasing availability of biomarkers, the need for guidelines and recommendations regulating the systematic and automated use of biomarkers for the diagnosis of AD in the prodromal stage becomes urgent. Within this context, the aim of this study has been to investigate and compare the capability of two different automated voxel-wise methods (SPMGrid and BRASS) in identifying those MCI subjects with prodromal dementia progressing to AD in a follow-up time of three years and excluding metabolic deficits in normal subjects and stable MCI. The concordance of the two analyses was tested by correlating the quantitative parameters measured by the two software tools (z-and t-scores, respectively), and by measuring the overlap of the abnormalities identified by the two methods via the Dice score. Three independent expert readers were assigned a diagnosis based on the pattern of hypometabolism detected by the two tools at the baseline, and Inter-rater reliability was also assessed for each software.

Multiple software solutions exist, but systematic cross-validation and comparison is still lacking, even if mandatory for their validated use in clinical practice. Our comparison showed that two widely used voxel-wise methods provide outputs that are significantly correlated in a majority of subjects and regions, however with systematic differences, resulting in a low Dice score for the distribution of abnormalities and consequent differences in the diagnostic decision making. We used the McNemar test to compare sensitivity and specificity of two diagnostic tests applied to a given set of individuals, some with the disease, and some without the disease, as recommended in the literature. In our dataset, SPMGrid showed a significantly higher specificity, and BRASS showed a significantly higher sensitivity, resulting in a similar AUC, with a trend for a higher performance of SPMGrid. The two softwares showed a good correlation between average t-and z-values both per ROI and per subject.

It should be noted that the performance of the two reported softwares uses reading guidelines as defined at the beginning of the study and sets the cut-off for normal/abnormal images at the p < 0.001 threshold. This could be adapted in specific settings if a higher sensitivity is required, for example, in a "screening" perspective. As an example, the subject in Figure 5 is an MCI progressing to AD, categorized as normal in this study, and who would have been categorized as AD pattern if the threshold p < 0.01 was chosen.

The ICC was computed to assess the reliability among the three raters in this study. A good to excellent ICC was retrieved for SPMGrid, which was higher than BRASS.

There are a number of issues that can explain the systematic differences observed between the two software tools. For the sake of comparability, the output from the two softwares was matched into the same unit interval and mapping space. However, we voluntarily allowed for a number of other differences, namely the control group, which is specific for each software, and the algorithm used for spatial normalization, as we decided to test each software in its standard configuration, clinically used. A larger control group in SPMGrid might explain the higher specificity and ICC, for example (107 HC for SPMGrid versus 30 HC for BRASS).

Our findings are consistent with the literature, observing that different softwares have different outputs for the identification of hypometabolic patterns; however, in a smaller or less homogeneous group [START_REF] Lim | Automated Brain FDG-PET Analysis in Patients Suspected with Alzheimer's Disease: Comparison between Computer-aided Reading using SPM and BRASS[END_REF].

The study has some limitations worth mentioning. The readers had a fixed set of images to analyze, rather than the whole volume to browse, as it would be in clinical practice. They also did not have access to the original unprocessed images or to MR data, which could have helped in, e.g., correctly identifying some abnormalities due to atrophy. This choice was made to focus on the different impacts of different software, rather than evaluating the added value of automated approaches to visual reading, as this question has already been addressed by multiple previous studies [START_REF] Morbelli | Visual versus semi-quantitative analysis of 18F-FDG-PET in amnestic MCI: an European Alzheimer's Disease Consortium (EADC) project[END_REF][START_REF] Perani | Validation of an optimized SPM procedure for FDG-PET in dementia diagnosis in a clinical setting[END_REF]. We included only MCI subjects converting to AD, asking the readers to identify a normal/abnormal distribution. The main reason for this choice was to adopt a gold standard that could be ascertained clinically, namely the conversion to AD dementia, avoiding the evaluation of different etiological diagnoses in the absence of a neuropathological verification. However, this approach did not allow us to evaluate the ability of the automated methods to identify specific patterns evoking other forms of degenerative processes. In addition, this selection process reduced the size of our dataset, and thus our population is not the largest MCI population as reported in the literature. However, our MCI sample was in the upper range of the sample sizes reported in the literature for similar studies, as recently reviewed [START_REF] Smailagic | 18F-FDG PET for Prediction of Conversion to Alzheimer's Disease Dementia in People with Mild Cognitive Impairment: An Updated Systematic Review of Test Accuracy[END_REF], and was sufficiently large enough to obtain significant findings. Finally, the parameters for FDG-PET scan acquisition and reconstruction were different between centers, and this might have affected the differentiall analyses between the two automated methods.

The present evidence provides a validation of the SPMGrid and BRASS procedures for their use in assisting the interpretation of FDG-PET images in predicting the conversion to AD. Despite an overall similar diagnostic performance, the two methods showed significant differences, resulting in a limited overlap of the abnormality maps provided by each method.

These discrepancies in the hypometabolic patterns had an impact on the interpretation of the maps by expert readers, resulting in different sensitivity and specificity and inter-rater agreement, with a tendency for a higher AUC and a higher agreement among raters when the visual rating was computer-assisted by the SPMGrid software tool.

Our results emphasize the need to establish a specific procedure for the use of statistical mapping tools to analyze FDG-PET images in clinical practice. Indeed, it would be crucial to ensure that results obtained across different centers using different statistical mapping tools are comparable and reliable. For this purpose, cross-validation across software would be a necessary step. Given the increasing availability of large, freely accessible databases, a performance test against a common reference dataset should become a requirement for introducing statistical mapping tools in clinical practice to ensure harmonization and comparability of results.

Legends to Figure

Fig. 1 :

 1 Fig. 1: Individual examples of the maps obtained with the two automated voxel-based analysis methods were tested here, namely SPMGrid and BRASS, overlapped to a standard template and displayed as multislice sequences. The threshold adopted is the same for both softwares and corresponds to a significance level of p-value < 0.001. Subfigure 1(a): Mild Cognitive Impairment (MCI) patient at baseline progressing to Alzheimer's Disease (AD) at follow-up; subfigure 1(b): Mild Cognitive Impairment (MCI) patient at baseline, stable at follow-up; subfigure 1(c): Healthy control (HC).

Fig. 2 :

 2 Fig. 2: Average abnormality values obtained with the two automated voxel-based analysis methods, SPMGrid and BRASS, in three cases. The plot shows BRASS z-value (y-axis) against the average SPMGrid t-value (x-axis) and Pearson's R correlation coefficient (in parenthesis). Subfigure 2(a): Mild Cognitive Impairment (MCI) patient at baseline progressing to Alzheimer's Disease (AD) at follow-up; subfigure 2(b): Mild Cognitive Impairment (MCI) patient at baseline, stable at follow-up; subfigure 2(c): Healthy control (HC).

Fig. 3 :

 3 Fig. 3: Average abnormality values obtained with the two automated voxel-based analysis methods, SPMGrid and BRASS, in temporal and parietal Regions of Interests (ROIs): these ROIs are relevant for the prognostic assessment of MCI subjects. Average BRASS z-value (y-axis) against average SPMGrid t-value (x-axis) and Pearson's R correlation coefficient (in parenthesis). Lx: left, Rx: right.

Fig. 4 :

 4 Fig. 4: Average abnormality values obtained with the two automated voxel-based analysis methods, SPMGrid and BRASS, in frontal Regions of Interest (ROIs). These ROIs are relevant for the prognostic assessment of MCI subjects. Average BRASS z-value (y-axis) against average SPMGrid t-value (x-axis) and Pearson's R correlation coefficient (in parenthesis). Lx: left, Rx: right.

Fig. 5 :

 5 Fig. 5: Example case of a Mild Cognitive Impairment (MCI) patient progressing to Alzheimer's Disease (AD) at follow up. The case was categorized as normal by the readers in this study, but it would have been presumably categorized as pathological if the threshold p < 0.01 or p < 0.05, showing a typical AD pattern, was instead adopted.

Table 1 :

 1 Diagnostic accuracy of SPMGrid and BRASS across raters versus clinical diagnosis at follow-up, in the whole study population (N = 131): sensitivity, specificity , positive predictive value (PPV), negative predictive value (NPV), positive likelihood ratio (LR+), negative likelihood ratio (LR-), area under the ROC curve (AUC). 95% confidence intervals in brackets. McNemar test for sensitivity and specificity to compare SPMGrid and BRASS: *: p ≤ 0.05; **: p ≤ 0.001.

		Rater1		Rater 2	Rater 3	Majority
		SPMGrid	BRASS	SPMGrid	BRASS	SPMGrid	BRASS	SPMGrid	BRASS
	Sensitivity	.57	.79*	.55	.79**	.68	.87**	.59	.82**

Acknowledgments

This work was partly funded by the Swiss National Science Foundation (SNSF) (grant number 320030 169876).

Conflict of interest

All authors declare that he/she has no conflict of interest.


Frédéric Cuppens
email: frederic.cuppens@enst-bretagne.fr

Nora Cuppens-Boulahia

Joaquín García-Alfaro

DETECTION AND REMOVAL OF FIREWALL MISCONFIGURATION

Keywords: Network Security, Firewalls, Filtering Rules, Redundancy, Shadowing of Rules

To police network traffic, firewalls must be configured with a set of filtering rules. The existence of errors in this set is very likely to degrade the network security policy. The management of these configuration errors is a serious and complex problem to solve. In this paper, we present a set of algorithms to manage rules that never apply or are redundant in a firewall configuration. Our approach is based on the analysis of relationships between the set of filtering rules. Then, a subsequent rewriting of rules will derive from an initial firewall setup to an equivalent one completely free of errors. At the same time, the algorithms will detect both shadowed and redundant rules in the initial firewall configuration.

Introduction

Many companies and organizations use firewalls to segment access control within their own networks. Firewalls are typically deployed to filter traffic between trusted and untrusted zones of corporate networks, as well as to police their incoming and outcoming interaction with other networks -e.g., the Internet 1 .

Firewalls, as many other network security components, must to be configured with a list of rules (e.g., the set of filtering rules shown in Table 1). Each rule typically specifies a decision (e.g., accept or deny) that applies to a set of condition attributes, such as protocol, source, destination, service ports, and so on. For our work, we define a filtering rule as follows:

R i : {condition i } → decision i ( 1
)
where i is the relative position of the rule within the set of rules, decision i is a boolean expression in {accept, deny} 2 , and {condition i } is a conjunctive set of condition attributes such that {condition i } equals A 1 ∧ A 2 ∧ ... ∧ A p -p being the number of condition attributes of the given set of filtering rules.

To solve conflicts when processing packages, most firewall implementations use a first matching strategy through the ordering of rules (e.g. the order field shown in Table 1). Hence, each packet processed by the firewall is mapped to the decision of the highest priority rule. This strategy introduces, however, firewall rule conflicts that result in non-firing rules (shadowing) or rules that have no effect (redundancy). We define these two general cases of firewall misconfiguration as follows.

Definition 1.1 Let R be a set of filtering rules. Then R has shadowing iff there exists at least one filtering rule, R i in R, which never applies because all the packets that R i may match, are previously matched by another rule, or combination of rules, with higher priority in order. Definition 1.2 Let R be a set of filtering rules. Then R has redundancy iff there exists at least one filtering rule, R i in R, such that the following conditions hold: (1) R i is not shadowed by any other rule; [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF] when removing R i from R, the filtering result does not change.

The detection and removal of both redundancy and shadowing is a serious problem which must to be solved, since a misconfigured set of filtering rules, if not handled correctly, is very likely to lead to a inefficient and weak security policy -since packets could be subject to the wrong actions. Although the proper managing of this configuration errors is starting to get currently a significant amount of work, such as [START_REF] Adiseshu | Detecting and Resolving Packet Filter Conflicts[END_REF][START_REF] Gupta | Algorithms for Routing Lookups and Packet Classification[END_REF][START_REF] Kurland | Firewall Builder[END_REF][START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF][START_REF] Cuppens | A formal approach to specify and deploy a network security policy[END_REF] In this paper, we present a set of algorithms for the managing of both redundancy and shadowing of rules. Our main objective is the following. Given a specific firewall setup, we want to analyze the existing firewall configuration to check whether there is errors in such a configuration, i.e., the set of filtering rules presents shadowing or redundancy as defined above.

Our approach is based on the relationships between the filtering rules' parameters: coincidence, disjunction and inclusion. We use a rule transformation process that derive from a set of filtering rules to an equivalent and valid one that is completely free of both shadowing and redundancy. The advantages of our proposal are the following.

After rewriting the rules, one can verify that each redundant or shadowed rule -considered as useless during the audit process -will be removed from the initial set of filtering rules. When such a detection occurs, the discovering process will provide an evidence of error to the administration console. This way, the security officer in charge of the network can check from the initial specification, in order to verify the correctness of the whole process. Furthermore, since the resulting rules are disjoint, the ordering of rules is no longer relevant. Hence, one can perform a second transformation in a positive or negative manner. The first -when generating only permissionscan be used in a closed policy whereas the latter -when generating only prohibitions -can be used in case of an open policy. After performing this second rewriting, the security officer will have a clear view of the accepted traffic (in the case of positive rewriting) or the rejected traffic (in the case of negative rewriting).

The rest of this paper is organized as follows: We start in Section 2 with an analysis of some related work. In Section 3 and Section 4, we formally present our algorithms, and introduce some examples and demonstrations to validate the correctness of our approach. We close with conclusions and future work in Section 5.

Related Work

A first approach to get a firewall configuration free of errors is by applying a formal security model to express the network security policy. In [START_REF] Cuppens | A formal approach to specify and deploy a network security policy[END_REF], for example, a formal model is presented with this purpose. This way, a set of filtering rules, whose syntax is specific to a given firewall, may be generated using a transformation language. Nonetheless, this approach is not enough to ensure that the firewall configuration is completely free of errors.

Some other proposals, such as [START_REF] Adiseshu | Detecting and Resolving Packet Filter Conflicts[END_REF][START_REF] Gupta | Algorithms for Routing Lookups and Packet Classification[END_REF][START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF][START_REF] Kurland | Firewall Builder[END_REF], provide means to directly manage misconfiguration. The authors in [START_REF] Adiseshu | Detecting and Resolving Packet Filter Conflicts[END_REF], for instance, consider that in a configuration set, two rules are in conflict when the first rule in order matches some packets that match the second rule, and the second rule also matches some packets that match the first rule. This approach is very limited since it does not detect what we consider serious misconfiguration errors -the two general cases defined in Section1. What they detect is just a particular case of wrongly defined rules which cause ambiguity in the firewall configuration, and that is more efficiently defined as a combination of both redundancy and shadowing.

In [START_REF] Gupta | Algorithms for Routing Lookups and Packet Classification[END_REF], two new cases of misconfiguration are considered. First, a rule R j is defined as backward redundant if and only if there exists another rule R i with higher priority in order such that all the packets that match rule R j also match rule R i . On the other hand, a rule R i is defined as forward redundant if and only if there exists another rule R j with the same decision and less priority in order such that the following conditions hold: (1) all the packets that match R i also match R j ; (2) for each rule R k between R i and R j , and that matches all the packets that also match rule R i , R k has the same decision than R i .

Although this approach seems to head in the right direction, we consider our definitions (cf. Section1, Def. 1.1 and Def. 1.2) simpler and more general, because all possible backward and forward redundant rules are specific cases of both redundancy and shadowing, but not vice versa. For instance, given the following set of rules:

R 1 : s ∈ [10, 50] → deny R 2 : s ∈ [40, 70] → accept R 2 : s ∈ [50, 80] → accept
their detection proposal, as defined above, cannot detect the redundancy of rule R 2 . Thus, we point out this work as incomplete.

Firewall Builder [START_REF] Kurland | Firewall Builder[END_REF], a well known support tool developed to assist administrators in their task of configuring firewalls, also provides detection of misconfiguration in the set of filtering rules. Nevertheless, this discovering mechanism only detects trivial equality or inclusion between the filtering rules' parameters. We checked out that more complex configuration errors are unfortunately not detected by this tool.

To our best knowledge, the authors in [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF] propose the most efficient set of techniques and algorithms to detect redundancy and shadowing in different firewall configuration setups. In addition to the discovery process, their approach also attempts an optimal insertion of arbitrary rules into an existing configuration, through a tree based representation of the filtering criteria.

Nonetheless, and even though the efficiency of their proposed discovering algorithms and techniques is very promising, we also consider this approach as incomplete. On the one hand, their approach is too weak since, given a misconfigured firewall, their discovering algorithms could not detect all the possible errors. For example, given the following set of rules:

R 1 : s ∈ [10, 50] → accept R 2 : s ∈ [40, 90] → accept R 3 : s ∈ [30, 80] → deny
their approach cannot detect the shadowing over rule R 3 due to the union of rules R 1 and R 2 . Furthermore, they do not cover, intentionally, an automatic rewriting of rules to correct the discovered errors. This way, it is the security officer who should perform the final changes.

Summing up, we believe that none of the identified related work provides a complete discovering of both redundancy and shadowing of rules -which are the cases we consider serious errors within firewalls configurations -as well as a proper handling of such a misconfiguration.

Detection Process

As pointed out in Section 1, our main goal is the discovering of both shadowing and redundancy inside an initial set of filtering rules R. Such a detection process is a way to alert the security officer in charge of the network about these configuration errors, as well as to remove all the useless rules in the initial firewall configuration.

The data for the process is the following. A set of rules R as a linked-list3 of initial size n, where n equals count(R), and where each element is an associative arraywith the strings condition, decision, shadowing, and redundancy as keys to access each necessary value. In turn, each element R i [condition] is an indexed arrayof size p containing the set of conditions of each rule; each element R i [decision] is a boolean variable whose values are in {accept, deny};

each element R i [shadowing] is a boolean variable in {true, f alse}; each element R i [redundancy]
is another boolean variable in {true, f alse}. Both shadowing and redundancy variables of each rule are initialized to f alse.

To simplify, we split the whole detection process and the removal of misconfiguration in two different processes. Thus, we define a main detection function (Algorithm 1), whose input is the initial set of filtering rules, R, and an auxiliary function (Algorithm 2) whose input is two rules, A and B. Once executed, this auxiliary function returns a further rule, C, whose set of condition attributes is the exclusion of the set of conditions from A over B. In order to simplify the representation of this second algorithm (cf. Algorithm 2), we use the notation A i as an abbreviation of the variable A[condition][i], an the notation B i as an abbreviation of the variable B[condition][i] -where i in [1, p].

Algorithm 1: detection(R) for i ← 1 to (count(R) -1) do for j ← (i + 1) to count(R) do R j ← exclusion (R j ,R i ); if R j [condition] = ∅ then R j [

.. and (A

p ∩ B p ) = ∅) then C[condition] ← C[condition] ∪ {(B 1 -A 1 ) ∧ B 2 ∧ ... ∧ Bp, (A 1 ∩ B 1 ) ∧ (B 2 -A 2 ) ∧ ... ∧ Bp, (A 1 ∩ B 1 ) ∧ (A 2 ∩ B 2 ) ∧ (B 3 -A 3 ) ∧ ... ∧ Bp, ... (A 1 ∩ B 1 ) ∧ ... ∧ (A p-1 ∩ B p-1 ) ∧ (Bp -Ap)}; else C[condition] ← (C[condition] ∪ B[condition]); end end return C;
We recall that the output of the main detection function (cf. Algorithm 1) is the set which results as a transformation of the initial set of filtering rules R. This new set is equivalent to the initial one, R, and all its rules are completely disjoint. Therefore, the resulting set is free of both redundancy and shadowing of rules, as well as any other possible configuration error -such as correlation, generalization, and irrelevance [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF].

Applying the Algorithms

This section gives a short outlook on applying our algorithms over some representative examples. Let us start by applying function exclusion over a set of two rules R i and R j , each one of them with two condition attributes -(s)ource and (d)estination -and where rule R j has less priority in order than rule R i . In this first example,

R i [condition] = (s ∈ [80, 100]) ∧ (d ∈ [1, 50]) R j [condition] = (s ∈ [1, 50]) ∧ (d ∈ [1, 50]) since (s ∈ [1, 50]) ∩ (s ∈ [80, 100]) = ∅,
the condition attributes of rules R i and R j are completely independent. Thus, the applying of

exclusion(R j , R i ) is equal to R j [condition].
The following three examples show the same execution over a set of condition with different cases of conflict. A first case is the following,

R i [condition] = (s ∈ [1, 60]) ∧ (d ∈ [1, 30]) R j [condition] = (s ∈ [1, 50]) ∧ (d ∈ [1, 50])
where there is a main overlap of attribute s from R i [condition] which completely excludes the same attribute on R j [condition]. Then, there is a second overlap of attribute d from R i [condition] which partially excludes the range [START_REF] Adiseshu | Detecting and Resolving Packet Filter Conflicts[END_REF]30]

into attribute d of R j [condition], which becomes d in [31, 50]. This way, exclusion(R j , R i ) ← {(s ∈ [1, 50]) ∧ (d ∈ [31, 50])} 4 . In this second example, R i [condition] = (s ∈ [1, 60]) ∧ (d ∈ [20, 30]) R j [condition] = (s ∈ [1, 50]) ∧ (d ∈ [1, 50])
there is two simple overlaps of both attributes s and

d from R i [condition] to R j [condition], such that exclusion(R j , R i ) becomes {(s ∈ [1, 50]) ∧ (d ∈ [1, 19]), (s ∈ [1, 50]) ∧ (d ∈ [31, 50])}. A more complete example is the following, R i [condition] = (s ∈ [10, 40]) ∧ (d ∈ [20, 30]) R j [condition] = (s ∈ [1, 50]) ∧ (d ∈ [1, 50]) where exclusion(R j , R i ) becomes {(s ∈ [1, 9]) ∧ (d ∈ [1, 50]), (s ∈ [41, 50]) ∧ (d ∈ [1, 50]), (s ∈ [10, 40]) ∧ (d ∈ [1, 19]), (s ∈ [10, 40]) ∧ (d ∈ [31, 50])}.
Regarding a full exclusion, let us now show the following example,

R i [condition] = (s ∈ [1, 60]) ∧ (d ∈ [1, 60]) R j [condition] = (s ∈ [1, 50]) ∧ (d ∈ [1, 50])
where the set of condition attributes of rule R i completely excludes the ones of rule R j . Then, the applying of exclusion(R j , R i ) becomes an empty set (i.e., 4 We do not show the first empty set corresponding to the first overlap. If shown, the result should become as follows:

exclusion(R j , R i ) ← {∅, (s ∈ [1, 50]) ∧ (d ∈ [31, 50])}.
{∅, ∅} = ∅). Hence, on a further execution of Algorithm 1 the shadowing field of rule R j (initialized as f alse by default) would become true (i.e., R j [shadowing] ← true).

To conclude, let us show a complete applying over the set of filtering rules based on Table 1, where the number of condition attributes, p, is just one. Lemma 3.2 Let R i : condition i → decision i and R j : condition j → decision j be two filtering rules.

Then {R i , R j } is equivalent to {R i , R j } where R j ← exclusion(R j , R i ).
Theorem 3.3 Let R be a set of filtering rules and let T r(R) be the resulting filtering rules obtained by applying Algorithm 1 to R. Then R and T r(R) are equivalent. Lemma 3.4 Let R i : condition i → decision i and R j : condition j → decision j be two filtering rules. Then rules R i and R j , where R j ← exclusion(R j , R i ) will never simultaneously apply to any given packet. Theorem 3.5 Let R be a set of filtering rules and let T r(R) be the resulting filtering rules obtained by applying Algorithm 1 to R. Then ordering the rules in T r(R) is no longer relevant. Theorem 3.6 Let R be a set of filtering rules and let T r(R) be the resulting filtering rules obtained by applying Algorithm 1 to R. Then T r(R) is free from both shadowing and redundancy.

For space limitation reasons, we move the correctness proofs of this section to Appendix A.

Complete Detection

Up to now, the result of Algorithm 1 offers a set of filtering rules, T r(R), equivalent to an initial set of rules R, and completely free of any possible relation between its rules. Nevertheless, there is a limitation on such an algorithm regarding the reporting of redundancy -just the existence of shadowing is reported to the security officer. Therefore, we need to modify this algorithm in order to also detect redundancy in R.

The purpose of this section is to solve this limitation, by presenting a second manner to completely discover both shadowing and redundancy errors into the initial set of filtering rules, R, based on the techniques and results previously shown in Section 3.

The reporting of redundancy is much more complex than the task of reporting shadowing. To properly overcome this complexity, we first divide the whole process in two different algorithms (Algorithm 3 and Algorithm 4).

The first algorithm (cf. Algorithm 3) is a boolean function in {true, f alse}, which, in turn, apply the transformation exclusion (cf. Section 3, Algorithm 2) over a set of filtering rules to check whether the rule obtained as a parameter is potentially redundant.

The second algorithm (cf. Algorithm 4) performs the whole process of detecting and removing both redundancy and shadowing, and is also split in two different phases. During the first phase, a potential set of redundant rules is calculated from a top-bottom scope, by iteratively applying Algorithm 3. Such a process is applied during the stage of detecting and removing shadowed rules, i.e., before the detection and removal of proper redundant rules. This information is then used when applying the second phase, from a bottom-top scope. This stage is performed to detect and remove proper redundant rules, as well as to detect and remove all the further shadowed rules resulting during the process. As a result of the whole execution, the initial set of rules, R, is transformed into an equivalent set, T r(R), whose rules are completely disjoint. Furthermore, all the discovery of both shadowing and redundancy is reported to the security officer, who may verify the correctness of the whole process.

3: testRedundancy(R,i) test ← f alse; j ← (i + 1); temp ← R i ; while ¬test and (j ≤ count(R)) do if temp[decision] = R j [decision] then temp ← exclusion(temp, R j ); if temp[condition] = ∅ then test ← true; end end j ← (j + 1); end return test; Algorithm 4: completeDetection(R) /* Phase 1 */ for i ← 1 to (count(R) -1) do if testRedundancy (R, i) then R i [redundancy] ← true; end if R i [redundancy] then for j ← (i + 1) to count(R) do if R i [decision] = R j [decision] then R j ← exclusion (R j ,R i ); if R j [condition] = ∅ then R j [shadowing] ← true; end else for j ← (i + 1) to count(R) do R j ← exclusion (R j ,R i ); if R j [condition] = ∅ then R j [shadowing] ← true; end end end /* Phase 2 */ for i ← (count(R) -1) to 1 do if R i [redundancy] then if testRedundancy (R, i) then R i [condition] ← ∅; else R i [redundancy] ← f alse; for j ← (i + 1) to count(R) do if R i [decision]=R j [decision] then R j ←exclusion (R j ,R i ); if R j [condition] = ∅ then R j [shadowing] ← true; end end end end

Applying the Algorithms

In this section we give an outlook on the full execution of the extended algorithms (Algorithm 3 and Algorithm 4) over a set of filtering rules based on Table 1, where the number of condition attributes, p, is just one. Once finished the first phase and running over the step where i equals 2, we notice that: (1) the applying of testRedundancy with R 2 as parameter becomes true; (2) the union of condition attributes of rules R 3 and R 5 enables the redundancy of rule R 2 . Hence, the status field redundancy of rule R 2 , R 2 [redundancy], switches its value to true:

/ * phase 2, step 4, i = 2 * / / * testRedundancy(R 2 ) = true * / / * R 2 [redundancy] = true * / / * R 4 [shadowing] = true * / R 1 : s ∈ [10, 50] → deny R 2 : ∅ → accept R 3 : s ∈ [60, 100] → accept R 4 : ∅ → deny R 5 : s ∈ {[1, 9], [51, 59]} → accept
For reasons of clarity, we do not show the rest of the execution, since the resulting set of filtering rules does not modify from the previous one, which is the following:

/ * resulting rules * / R 1 : s ∈ [10, 50] → deny R 3 : s ∈ [60, 100] → accept R 5 : s ∈ {[1, 9], [51, 59]} → accept
To conclude, let us recall that the following two warnings will notice the security officer to the discovering of both shadowing and redundancy errors, in order to verify the correctness of the whole detection and transformation process: For space limitation reasons, we move the correctness proofs of this section to Appendix A.

/ * warnings * / R 2 [redundancy] = true R 4 [shadowing] = true

Correctness of the Algorithms

Conclusions

In this paper we presented and audit process based on the existence of relationships between the condition attributes of the filtering rules, such as coincidence, disjunction, and inclusion. Our proposal uses a transformation process which derives from an initial set of rules to an equivalent one completely free of misconfiguration.

Furthermore, our proposal verify that any rule considered as useless is removed from the configuration. In turn, it provides an evidence of error to the security officer -he can check whether the security policy is consistent, to verify the correctness of the whole process. The complete independence between rules, moreover, enables the possibility to perform a second rewriting of rules in a positive or negative manner. If done, the security officer will have a clear view of the accepted traffic -when positive -or the rejected traffic -when negative.

Regarding the increase of number of filtering rules, because of the rewriting process, it is only significant whether the associated firewall parsing algorithm would depend on the number of rules. Nonetheless, this is not a disadvantage since the use of a parsing algorithm independent of the number of rules becomes the best solution as much for our proposal as for the current deployment of firewall technologies. The set pruning tree algorithm is a proper example, because it only depends on the number and size of attributes to be parsed, not the number of rules [START_REF] Paul | A full bandwidth ATM Firewall[END_REF].

As future work we are considering to extend our proposal to a more complex network setup. This paper is based on the hypothesis that only one firewall polices the network. More investigation has to be done when this role is assigned several network security components, that is, a distributed access control. Indeed, in particular, redundancy will not systematically be considered as an error [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF]. It may be suited to avoid inconsistent decisions between firewalls used in the same security architecture to control the access to different zones. In parallel, we are also considering to study the anomaly problems of security rules in the case where the security architecture includes firewalls as well as IDS (Intrusion Detection Systems). The objective is to avoid redundant or shadowed filtering or/and alerting rules. These two works are still in progress.

  shadowing] ← true; end end Algorithm 2: exclusion(B,A) C[condition] ← ∅; C[decision] ← B[decision]; C[shadowing] ← f alse; C[redundancy] ← f alse; forall the elements of A[condition] and B[condition] do if ((A 1 ∩ B 1 ) = ∅ and (A 2 ∩ B 2 ) = ∅ and ... .

/

  * motivation example * / R1 : s ∈ [10, 50] → deny R2 : s ∈ [40, 90] → accept R3 : s ∈ [60, 100] → accept R4 : s ∈ [30, 80] → deny R5 : s ∈ [1, 70] → accept / * step 1 * / R1 : s ∈ [10, 50] → deny R2 : s ∈ [51, 90] → accept R3 : s ∈ [60, 100] → accept R4 : s ∈ [51, 80] → deny R5 : {s ∈ [1, 9], s ∈ [51, 70]} → accept / * step 2 = step 3 = step 4 * / R1 : s ∈ [10, 50] → deny R2 : s ∈ [51, 90] → accept R3 : s ∈ [91, 100] → accept R4 : ∅ → deny R5 : s ∈ [1, 9] → accept / * resulting rules * / R1 : s ∈ [10, 50] → deny R2 : s ∈ [51, 90] → accept R3 : s ∈ [91, 100] → accept R5 : s ∈ [1, 9] → accept / * warnings * / R4[shadowing] = true 3.2 Correctness of the Algorithms Definition 3.1 Let R be a set of filtering rules and let T r(R) be the resulting filtering rules obtained by applying Algorithm 1 to R.

Algorithm

/

  * motivation example * / R 1 : s ∈ [10, 50] → deny R 2 : s ∈ [40, 90] → accept R 3 : s ∈ [60, 100] → accept R 4 : s ∈ [30, 80] → deny R 5 : s ∈ [1, 70] → acceptThen, we begin by showing the initial step within the first phase of Algorithm 4, where i equals 1, and applied over the previous set of filtering rules. Let us notice that on this first step, the execution of function testRedundancy (cf. Algorithm 3), with rule R 1 as parameter, becomes f alse. Thus, the result of this first step is the following:/ * phase 1, step 1, i = 1 * / / * testRedundancy(R 1 ) = f alse * / R 1 : s ∈ [10, 50] → deny R 2 : s ∈ [51, 90] → accept R 3 : s ∈ [60, 100] → accept R 4 : s ∈ [51, 80] → deny R 5 : s ∈ {[1, 9], [51, 70]} → acceptLet us now move to the second step, with i equals 2. In this step, rule R 4 disappears since: (1) the result of applying function testRedundancy with rule R 2 as parameter becomes true; (2) the union of condition attributes from rules R 1 and R 2 completely excludes the condition attribute of rule R 4 . Hence, rule R 4 , which is shadowed by the combination of rules R 1 and R 2 , becomes and empty set. Therefore, the status field shadowing of rule R 4 , R 4 [shadowing], switches its value to true:/ * phase 1, step 2, i = 2 * / / * testRedundancy(R 2 ) = true * / / * R 4 [shadowing] = true * / R 1 : s ∈ [10, 50] → deny R 2 : s ∈ [51, 90] → accept R 3 : s ∈ [60, 100] → accept R 4 : ∅ → deny R 5 : s ∈ {[1,9], [51, 70]} → accept At the end of the third step of this first phase, the applying of function testRedundancy, with rule R 3 as parameter, becomes f alse: / * phase 1, step 3, i = 3 * / / * testRedundancy(R 3 ) = f alse * / / * R 4 [shadowing] = true * / R 1 : s ∈ [10, 50] → deny R 2 : s ∈ [51, 90] → accept R 3 : s ∈ [60, 100] → accept R 4 : ∅ → deny R 5 : s ∈ {[1, 9], [51, 59]} → accept

Theorem 4 . 1

 41 Let R be a set of filtering rules and let T r (R) be the resulting filtering rules obtained by applying Algorithm 4 to R. Then R and T r (R) are equivalent. Theorem 4.2 Let R be a set of filtering rules and let T r (R) be the resulting filtering rules obtained by applying Algorithm 4 to R. Then ordering the rules in T r (R) is no longer relevant.

Theorem 4 . 3

 43 Let R be a set of filtering rules and let T r (R) be the resulting filtering rules obtained by applying Algorithm 4 to R. Then T r (R) is free from both shadowing and redundancy.

Table 1 .

 1 ], just few approaches seem to manage acceptable results. Example of a set of filtering rules with five condition attributes.

	order			condition			decision
		(p)rotocol	(s)ource	(sP)ort	(d)estination	(dP)ort
	1	any	xxx.xxx.xxx.[010,050]	any	xxx.xxx.xxx.xxx	any	deny
	2	any	xxx.xxx.xxx.[040,090]	any	xxx.xxx.xxx.xxx	any	accept
	3	any	xxx.xxx.xxx.[060,100]	any	xxx.xxx.xxx.xxx	any	accept
	4	any	xxx.xxx.xxx.[030,080]	any	xxx.xxx.xxx.xxx	any	deny
	5	any	xxx.xxx.xxx.[001,070]	any	xxx.xxx.xxx.xxx	any	accept

Firewalls also implement other functionalities, such as Proxying and Network Address Transfer (NAT), but it is not the purpose of this paper to cover these functionalities.

The decision field may also be a combination of both accept and deny together with some other options such as a logging or jump options. For reasons of clarity we assume that just accept and deny are proper values.

We assume one can access a linked-list through the operator R i , where i is the relative position regarding the initial list size -count(R). We also assume one can remove elements through the addition of an empty set (element ← ∅). The internal order of elements from the linked-list R keeps with the relative ordering of rules.

Acknowledgements -This work was supported by funding from the French ministry of research, under the ACI DESIRS project, the Spanish Government project TIC2003-02041, and the Catalan Government grants 2003FI126 and 2005BE77.

A Correctness Proofs

Proof of Lemma 3.2 Let us assume that:

If (A 1 ∩ B 1 ) = ∅ or (A 2 ∩ B 2 ) = ∅ or . . . or (A p ∩ B p ) = ∅ then exclusion(R j , R i ) ← R j . Hence, to prove the equivalence between {R i , R j } and {R i , R j } is trivial in this case.

Let us now assume that:

If we apply filtering rules {R i , R j } where R i comes before R j , then rule R j applies to a given packet if this packet satisfies

which corresponds to condition of rule R j = exclusion(R j , R i ). This way, if rule R j applies to a given packet in {R i , R j }, then rule R j also applies to this packet in {R i , R j }.

Conversely, if rule R j applies to a given packet in {R i , R j }, then this means this packet satisfies

Proof of Theorem 3.3 Notice that if R is a set of filtering rules, then T r(R) is obtained by recursively applying transformation exclusion(R j , R i ) when rule R i comes before rule R j , which preserves the equivalence at each step of the transformation, previously proved for Lemma 3.2.

Proof of Lemma 3.4 Notice that rule R j only applies when rule R i does not apply. Thus, if rule R j comes before rule R i , this will not change the final decision since rule R j only applies to packets that do not match rule R i .

Proof of Theorem 3.5

For any pair of rules R i and R j such that R i comes before R j , R j is replaced by a rule R j obtained by recursively replacing R j by exclusion(R j , R k ) for any k < j.

Then, by recursively applying Lemma 3.4, it is possible to commute rules R i and R j in T r(R) without changing the final decision.

Proof of Theorem 3.6 Notice that, in T r(R), each rule is independent of all other rules. Thus, if we consider a rule R i in T r(R) such that R i [condition] = ∅, then this rule will apply to any packet that satisfies R i [condition]. Hence, this rule is not shadowed.

Similarly, rule R i is not redundant because if we remove this rule, since this rule is the only one that applies to packets that satisfy R i [condition], then the filtering decision will change if we remove rule R i from T r(R).

Proof of Theorem 4.1

Let T r 1 (R) be the set of rules obtained after applying the first phase of Algorithm 4. Since T r 1 (R) is derived from R by applying

Hence, let us now move to the second phase of Algorithm 4. Let us consider a rule R i such that testRedundancy(R i ) (cf. Algorithm 3) is true. This means that R i [condition] can be derived by conditions of a set of rules S with the same decision and that come after in order than rule R i .

Since every rule R j with a decision different from the one of rules in S has already been excluded from rules of S in the first phase of the Algorithm, we can conclude that rule R i is definitely redundant and can be removed without changing the final filtering decision. This way, we conclude that Algorithm 4 preserves equivalence in this case.

On the other hand, if testRedundancy(R i ) is f alse, then transformation consists in applying exclusion(R j , R i ) to some rules R j which also preserves equivalence. Thus, in both cases, T r (R) is equivalent to T r 1 (R) which, in turn, is equivalent to R.

Proof of Theorem 4.2 and Theorem 4.3 As stated out in the proof of both Theorem 3.5 and Theorem 3.6, once shadowed and redundant rules have been removed, every rule R i is replaced by exclusion(R i , R j ) where j < i.

Therefore, a similar reasoning enables to prove both Theorem 4.2 and Theorem 4.3.