Martín Barrère
email: barrere@inria.fr

Gaëtan Hurel
email: hurel@inria.fr

Rémi Badonnel
email: badonnel@inria.fr

Olivier Festor
email: festor@inria.fr

Increasing Android Security using a Lightweight OVAL-based Vulnerability Assessment Framework

Mobile computing devices and the services offered by them are utilized by millions of users on a daily basis. However, they operate in hostile environments getting exposed to a wide variety of threats. Accordingly, vulnerability management mechanisms are highly required. We present in this paper a novel approach for increasing the security of mobile devices by efficiently detecting vulnerable configurations. In that context, we propose a modeling for performing vulnerability assessment activities as well as an OVAL-based distributed framework for ensuring safe configurations within the Android platform. We also describe an implementation prototype and evaluate its performance through an extensive set of experiments.

I. INTRODUCTION

The overwhelming technological advances in the broad sense of mobile computing have made end users to experience real computers in their pockets. Android 1 [1], a Linux-based operating system for mobile devices, is nowadays the election of millions of users as the platform for governing their mobile devices. Only in the first quarter of 2012, worldwide sales of smartphones to end users reached 144.4 million units where Android-based devices leaded the market share owning the 56.1% followed by iOS 2 with 22.9% [START_REF] Gartner | [END_REF]. However, despite of the many security improvements that have been done since Android's creation, the underlying operating system as well as services and applications have also evolved providing room for new vulnerabilities. Moreover, the open and barely protected mobile environment facilitates attackers to take advantage of such vulnerabilities. Sensitive data handled by mobile users becomes easily exposed. Under this perspective, managing vulnerabilities is a crucial and challenging task that must be addressed in order to ensure safe configurations and to increase the overall security of the system.

Once a vulnerability is discovered in almost any typical software product, its patch cycle normally describes a time gap until the vulnerability is disclosed, another time span until the patch is available and yet another time span until the end user applies the patch [START_REF] Frei | Modelling the Security Ecosystem -The Dynamics of (In)Security[END_REF]. It is usually during this period that attackers activity takes place. Within the Android environment, this issue gets worse. Android is distributed as open source and device manufacturers and telecommunications carriers customize it in order to provide specific services as well as added value to their customers. When a patch is released by 1 Android is developed by Open Handset Alliance, led by Google [START_REF]Open Handset Alliance[END_REF] 2 Apple iOS [START_REF]Apple iOS[END_REF] Google, an extra time gap will occur until the manufacturer adapts it to work with its own hardware and another time span will pass until the patch is released by the carrier [START_REF] Vidas | All Your Droid Are Belong To Us: A Survey of Current Android Attacks[END_REF]. In addition to this problem, several application markets allow to fast distribute third party applications with only some security checks expecting that the community identifies and reports malicious software. With thousands of applications in the market, Android users are very likely to encounter malware 3on their devices [7].

Such scenario imperatively requires solutions for rapidly identifying new vulnerabilities and minimizing their impact. Even though no patch might be available for a new vulnerability at a given time, countermeasures can be taken in order to mitigate the problem until the disclosure of an official patch. In that context, vulnerability assessment mechanisms are highly required in order to increase the vulnerability awareness of the system. In addition, mobile devices usually have limited resources thus optimized lightweight tools should be developed to ensure efficiency without losing functionality. Moreover, there are no current solutions built over solid foundations as well as open and mature standards that foster its adoption and speed up general vulnerability information exchange.

In light of this, we propose a novel approach for increasing the security of the Android platform, though it could be applied over other mobile platforms as well, using the OVAL4 language [START_REF]The OVAL Language[END_REF] as a means for describing Android vulnerabilities. We put forward a mathematical model that supports the assessment strategy and a lightweight framework that efficiently takes advantage of such knowledge in order to detect and prevent configuration vulnerabilities. We also present an implementation prototype as well as an extensive set of experiments that shows the feasibility of our solution.

Finally, the remainder of this paper is organized as follows. Section II describes existing work and their limits. Section III presents our approach for modeling the vulnerability assessment process. Section IV details the proposed framework describing its architecture and the proposed strategy for performing self-assessment activities. Section V depicts the internals of our implementation prototype. Section VI shows an extensive set of experiments and the obtained results. Section VII presents conclusions and future work.

II. RELATED WORK

Android is an open source operating system that integrates some security features by design. It uses the Dalvik virtual machine [START_REF]Dalvik Virtual Machine[END_REF] for executing end user applications written in Java [START_REF]The Java Platform[END_REF]. It is not the same standard Java virtual machine used in most popular platforms such as Linux, Mac OS X or Windows. It has its own API 5 that is almost the same as the standard one. The Dalvik virtual machine takes the Java application classes and translates them into one or more .dex (Dalvik Executable) files generating optimized and smaller code. The internal design of the Android platform provides important security features such as the sandbox execution approach [START_REF] Vidas | All Your Droid Are Belong To Us: A Survey of Current Android Attacks[END_REF]. Such approach executes Android applications within separate instances of the Dalvik virtual machine that in turn are represented by different Linux kernel processes. In order to manage the underlying system resources, Android uses an access control policy based on unique identifiers for each application to ensure that they can not interfere between each other.

Despite of the many security features provided by the Android platform [START_REF] Enck | Understanding android security. Security Privacy[END_REF], [START_REF] Shabtai | Google Android: A Comprehensive Security Assessment[END_REF], end users still face security threats due to existing vulnerabilities within the system itself, misuse of personal data performed by applications and malicious third party software [START_REF] Enck | A Study of Android Application Security[END_REF], [START_REF] Felt | A Survey of Mobile Malware in the Wild[END_REF]. Several approaches have been proposed for analyzing Android applications and their risks [START_REF] Bartel | Automatically Securing Permission-Based Software by Reducing the Attack Surface: An Application to Android[END_REF], [START_REF] Li | Juxtapp and DStruct: Detection of Similarity Among Android Applications[END_REF]. These contributions provide a strong support for increasing the security of the Android platform. Nevertheless, vulnerability assessment mechanisms have been barely or not at all discussed. Currently, dozens of security applications exist for the Android platform developed by different providers [7], [START_REF]Norton Mobile Security[END_REF], [START_REF]X-Ray for Android[END_REF]. However, they generally use private knowledge sources as well as their own assessment techniques, and they do not provide standardized and open means for describing and exchanging vulnerability descriptions within the community.

Much of the work done in vulnerability analysis has defined the assessment infrastructure using its own vulnerability specification language arising compatibility and interoperability problems. Languages such as VulnXML [START_REF] Vulnxml | [END_REF] have been developed as an attempt to mitigate these problems and to promote the exchange of security information among applications and security entities. However, these languages are only focused on web applications covering a subset of the existing vulnerabilities in current computer systems. In order to cope with these problems, the MITRE corporation [8] has introduced the OVAL language [START_REF]The OVAL Language[END_REF], an information security community effort to standardize how to assess and report upon the machine state of computer systems. OVAL is an XMLbased language that allows to express specific machine states such as vulnerabilities, configuration settings, patch states. Real analysis is performed by OVAL interpreters such as Ovaldi [START_REF] Ovaldi | the OVAL Interpreter reference implementation[END_REF] and XOvaldi [START_REF] Barrère | Towards Machine-assisted Formal Procedures for the Collection of Digital Evidence[END_REF]. Several related technologies have evolved around the OVAL language. NIST [9] is responsible for the development of emerging technologies including 5 Application Programming Interface the SCAP 6 protocol [START_REF] Banghart | The Technical Specification for the Security Content Automation Protocol (SCAP)[END_REF] and the XCCDF 7 language [START_REF] Ziring | Specification for the Extensible Configuration Checklist Description Format[END_REF]. The SCAP protocol is a suite of specifications that includes OVAL and XCCDF, and it can be used for several purposes, including automating vulnerability checking, technical control compliance activities, and security measurement. XCCDF is a language for authoring security checklists/benchmarks and for reporting results of checklist evaluation. The use of SCAP, particularly OVAL and XCCDF, not only allows to specify vulnerabilities, but also to bring a system into compliance through the remediation of identified vulnerabilities or misconfigurations. While OVAL provides means for describing specific machine states, XCCDF allows to describe certain actions that should be taken when these states are present on the system under analysis.

Several previous contributions have taken advantage of public vulnerability databases [START_REF] Ahmed | Towards Autonomic Risk-aware Security Configuration[END_REF] and the use of the OVAL language for performing vulnerability assessment activities in large scale networks [START_REF] Ou | MulVAL: A Logic-based Network Security Analyzer[END_REF]. Currently, OVAL repositories offer a wide range of vulnerability descriptions though Android is not yet an official supported platform. In this work, we have instrumented our approach with an experimental OVAL extension for Android within the OVAL Sandbox project [START_REF]The OVAL Language[END_REF]. Such extension enables practitioners and experts within the field to specify known vulnerabilities for Android in a machine-readable manner and at the same time, it promotes the exchange and enrichment of Android security information within the community. Our work aims at defining a solution for increasing the security of Android devices by capitalizing Android vulnerability descriptions specified with the OVAL language. Such security advisories are automatically integrated in a distributed architecture where self-assessment activities are performed in order to ensure safe mobile configurations.

III. VULNERABILITY ASSESSMENT PROCESS MODEL

The process by which vulnerabilities are assessed is critical for efficiently analyzing a target system and minimizing computation costs at the same time. In this section we present a mathematical model that defines and efficiently supports the vulnerability assessment process. Usually, a vulnerability can be understood as a logical combination of properties that if observed in a target system, the security problem associated with such vulnerability is present on that system. Properties can vary depending on the nature of the vulnerability being described, some examples are: a specific process is running (e.g., httpd), a specific port is open (e.g., 80), the system has a specific version (e.g., 2.6.10.rc). Frequently, one property is required by several vulnerability descriptions and naturally one vulnerability description may require several properties. Under this perspective, the set of vulnerability descriptions that constitutes a knowledge base can be compactly represented by using a boolean pattern matrix P M defined as follows:

P M =      p 1 p 2 • • • p n v 1 a 1,1 a 1,2 • • • a 1,n v 2 a 2,1 a 2,2 • • • a 2,n . . . . . . . . . . . . . . . v m a m,1 a m,2 • • • a m,n      a i,j ∈ {0, 1}
Each matrix row encodes the properties required to be observed for the vulnerability v i to be present. Thus, each entry a i,j denotes if the vulnerability v i requires the property p j . Considering for instance a scenario with three vulnerabilities v 1 , v 2 and v 3 , a pattern matrix P M can be built as follows:

v 1 = (p 1 , p 3 , p 5 ) v 2 = (p 2 , p 4 ) v 3 = (p 1 , p 2 , p 5 )      P M 3,5 =   1 0 1 0 1 0 1 0 1 0 1 1 0 0 1  
The pattern matrix can also provide useful information for performing statistics. The vf latten operation aggregates the number of times that each property occurs within the whole set of known vulnerabilities. The resulting vector provides an indicator that helps to identify most common properties involved in vulnerabilities. Such indicator provides valuable information that can be used for closer monitoring and controlling critical components changes.

vf latten(P M ) = ( m i=1 a i1 , m i=1 a i2 , . . . , m i=1 a in )
Other useful metric can be extracted from the pattern matrix when the aggregation operation is performed horizontally, as indicated by hf latten. A column vector is obtained from its application where each entry j denotes the amount of properties required by each vulnerability v j . This metric can be utilized, among other uses, for identifying those vulnerabilities that are most likely affected by changes performed in the environment, thus assessment activities should be taken into account as well.

hf latten(P M ) = ( n j=1 a 1j , n j=1 a 2j , . . . , n j=1 a mj ) T
The state of a system can be encoded in the same manner as done with vulnerabilities, indicating for those properties under control, which ones are present and which ones are not. Thus, a system state is a boolean vector s defined as follows:

s = (s 1 , s 2 , . . . , s n ) s i ∈ {0, 1}
Each entry s i takes the value 1 if the property p i is present in the system and 0 if it is not. Considering these constructs, the results of performing the vulnerability assessment process over a given system is defined by the following equation:

w = hf latten(P M ) -[P M * s T ]
(1)

⇓ w =      n j=1 a 1j n j=1 a 2j . . . n j=1 a mj      -           a 1,1 a 1,2 • • • a 1,n a 2,1 a 2,2 • • • a 2,n . . . . . . . . . . . . a m,1 a m,2 • • • a m,n      ×      s 1 s 2 . . . s n          
The resulting assessment vector w = (w 1 , w 2 , • • • , w m ) denotes the status of each vulnerability v i in the target system. The semantic of the vector w is given by the Kronecker delta function as follows:

δ i = 0, if i = 0 1, if i = 0
A null entry w i indicates that the vulnerability v i is present in the system while non null values denotes the absence of the corresponding vulnerability. This fact can be understood as a distance metric where a positive value indicates a positive distance between the vulnerability and the target system, and a null distance indicates that the vulnerability is actually in the system. Computing matrix operations in optimized manners constitutes a field that has been studied for years [START_REF] Strassen | Gaussian Elimination Is Not Optimal[END_REF]. The integration of the proposed model into real computing systems can take advantage of such expertise providing a compact and efficient representation for performing vulnerability assessment activities.

IV. AN OVAL-BASED FRAMEWORK FOR ASSESSING ANDROID VULNERABILITIES

The previous model establishes a well-founded process for assessing vulnerabilities in an efficient manner. By taking advantage of OVAL security advisories, such model can be used for efficiently increasing the security of mobile computing devices. Mobile devices have become a daily useful resource for connecting people, entertainment, working, managing personal data and much more. This fact attracted the attention of legitimate users of these pocket-computers but also from attackers. In only the first semester of 2011, malware for the Android platform has grown at 250% [7]. It is critical to develop open security frameworks that can speed up the knowledge exchange among community users and also being able to take advantage of such information in order to augment their own security. In this section we present our approach for efficiently increasing the security of Android-based devices by automatically evaluating OVALbased vulnerability descriptions and reporting analysis results.

A. Architecture and main components

We have designed the proposed architecture illustrated in Fig. 1 as a distributed infrastructure composed of three main building blocks: (1) a knowledge source that provides existing security advisories, (2) Android-based devices running a selfassessment service and (3) a reporting system for storing analysis results and performing further analysis. The overall process is defined as follows. Firstly at step 1, the Android device periodically monitors and queries for new vulnerability descriptions updates. This is achieved by using a web service provided by the security advisory provider. At step 2, the Fig. 1: OVAL-based vulnerability assessment framework for the Android platform provider examines its database and sends back new found entries. The updater tool running inside the Android device synchronizes then its security advisories. When new information is available or configuration changes occur within the system, a self-assessment service is launched in order to analyze the device at step 3. At step 4, the report containing the collected data and the results of the analyzed vulnerabilities is sent to a reporting system by means of a web service request. At step 5, the obtained results are stored and analyzed to detect potential threats within the Android device. In addition, this information can also be used with different purposes such as forensic activities or statistical analysis.

Within the proposed approach, vulnerabilities are described by using OVAL definitions. An OVAL definition is intended to describe a specific machine state using a logical combination of OVAL tests that must be performed over a host. If such logical combination is observed, then the specified state is present on that host (e.g. vulnerability, specific configuration) [START_REF]The OVAL Language[END_REF]. Under a logical perspective, this combination can be understood as a first order formula where each OVAL test corresponds to an atomic unary predicate over that system [START_REF] Barrère | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF]. The model presented in Section III denotes these predicates as the set of properties P = {p 1 , p 2 , . . . , p n }. P represents all the predicates (OVAL tests) involved in the vulnerability descriptions (OVAL definitions) available our knowledge source. In this manner, a boolean matrix P M representing each involved OVAL test for each OVAL definition can be easily built in order to perform assessment activities. The selfassessment component depicted in Fig. 1 constitutes a critical building block because it is in charge of orchestrating the entire lifecycle of the framework in an automatic manner. Hence, optimized algorithms for performing self-assessment activities are highly required. In order to achieve this objective, we have designed and implemented a strategy that uses the model presented in Section III for minimizing the system components required to be assessed.

B. Optimized assessment strategy

Due to the limited resources provided usually by mobile devices, it is important to optimize the use of such elements without losing functionality and performance. The proposed assessment strategy takes this issue into account and minimizes computation costs by using a boolean pattern matrix P M that represents known vulnerabilities and a system state vector s that holds the current system properties. The overall assessment is then efficiently performed using both the pattern matrix and the system vector defined in Section III. Within our approach, two types of events can trigger self-assessment activities: (i) when changes occur in the system and (ii) when new vulnerability definitions are available. Algorithm 1 depicts the overall strategy for treating such events and minimizing the number of OVAL tests to be re-evaluated. In order to explain the proposed algorithm, we put forward an illustrative example that considers both situations and uses the matrix P M 3,5 illustrated in Section III. Let consider the property p 2 = {Package X has version Y} and the system state s = (1, 0, 0, 0, 1) meaning that only the properties p 1 and p 5 are present in the system. Within the OVAL language, p 2 is described using an OVAL test that involves an OVAL package object with its attribute name = X and an OVAL package state with its attribute version = Y.

Let suppose now that an event of type package updated has occurred in the system affecting the package X (line 1). Usually, a complete evaluation of each OVAL definition involving the OVAL test that describes the property p 2 should be carried out. However, only the truth value of the involved OVAL test for p 2 is required for recomputing the results of all the descriptions affected. In order to achieve this, the objects affected by the event are retrieved (line 2) and compared with the objects related to the system properties (lines 3-4).

If the object of one property is seen to be affected (line 5), the property represented by an OVAL test is re-evaluated and reflected in the system state (lines 6-7). Within our example, such optimization point will only assess and change the second entry of the system state s. Due to both events are disjoint (system changes at line 1 and definition update at line 11), we now explain the end of the algorithm for the first case and then we discuss the behavior for the second case. Let suppose that the new value for the package version is Y thus the new system state becomes s = (1, 1, 0, 0, 1). Once the Algorithm 1: Efficient event-based vulnerability assessment algorithm assessment of the OVAL test for p 2 has been done, the overall assessment result is achieved by performing two operations between boolean matrices (line 26), within our example, as given by Equation 2.

w =   3 2 3   -         1 0 1 0 1 0 1 0 1 0 1 1 0 0 1   ×       1 1 0 0 1             =   1 1 0   (2)
For each entry in the result vector w (line 28), we use the Kronecker delta function (line 29) in order to detect if the vulnerability represented by that entry is present in the target system. If it is the case, the vulnerability definition is added in the output detected vulnerability list (lines 30-31). Within our example, it can be observed that the change performed in the system has exposed itself to new security risks due to the presence of the vulnerability v 3 .

The second situation involves the arrival of new vulnerability descriptions (line 11). In this case, both the pattern matrix P M and the system state s have to be extended so as to cover the new properties involved in the OVAL definitions. In order to achieve this, the new definitions are retrieved from the event (line 12), and the properties involved within such definitions are analyzed (lines [START_REF]The Java Platform[END_REF][START_REF]The OVAL Language[END_REF]. For each uncovered property (line 15), an extension process must be applied. The extension process for the pattern matrix P M will include new columns with null entries for the new properties within existing vulnerability definitions (line 16). The system state s is extended (line 17) and updated as well with the result of the property assessment (lines [START_REF] Banghart | The Technical Specification for the Security Content Automation Protocol (SCAP)[END_REF][START_REF] Barrère | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF]. It is important to notice that the arrival of new vulnerability definitions does not imply changes on the system and that the assessment results for known properties are already loaded in the system state, thus there is no need to re-evaluate them again. Finally, for each new vulnerability definition (line 22), a new row is added in the pattern matrix P M indicating the required properties for that vulnerability to be present (line 23). The final assessment procedure is then performed in the same manner as explained in the first situation (lines 26-34). The proposed strategy constitutes a critical part of our framework and it has been integrated into our implementation prototype, which is the heart of the next section.

V. IMPLEMENTATION PROTOTYPE

In order to provide a computable infrastructure to the proposed approach, a running software component inside Android capable of performing self-assessment activities is required. Currently, 60.3% of Android users operate their devices using Gingerbread (versions 2.3.3 to 2.3.7, API level 10) and a total of 79.3% operate versions starting at 2.3.3 until its last release Jelly Bean (version 4.1, API level 16) [START_REF]Android Developers[END_REF]. Our implementation prototype has been developed to be compliant with Android platforms starting at version 2.3.3, thus covering almost 80% of the Android market share. In this section, we describe the prototyping of our solution as well as the high-level operation performed during the assessment activity.

The implementation prototype has been purely written in Java [START_REF]The Java Platform[END_REF] and is composed of four main components: (1) an update system that keeps the internal database up-to-date, (2) a vulnerability management system in charge of orchestrating the assessment activities when required, (3) an OVAL interpreter for the Android platform and (4) a reporting system that stores the analysis results internally and sends them to an external reporting system. Fig. 2 depicts the main operational steps performed during the self-assessment activity and the connection with the mentioned four main components. The prototype is executed as a lightweight service that is running on background and that can be awakened by two potential reasons. The first one is that the update system in charge of monitoring external knowledge sources has obtained new vulnerability definitions; the second one is that changes in the system have occurred hence it is highly possible that some vulnerability definitions need to be re-evaluated. The prototype is still in an early development phase so we only cover some system events such as when a package has been installed. In order to be aware of these two potential self-assessment triggers, two listeners remain active as shown at step 1. The updater listener listens the vulnerability database updater component and will be notified when new vulnerability definitions become available. The event bus listener uses the Android broadcast bus to capture notifications about system changes. If new vulnerability definitions are available or system changes have been detected, a vulnerability definition selection process is launched at step 2. This process is in charge of analyzing the cause that has triggered the self-assessment activity and deciding which assessment tasks must be performed by actually implementing the Algorithm 1. At step 3, the vulnerability manager component uses the services of XOvaldi4Android in order to perform the corresponding assessment activity. At step 4, the results of the assessment are stored in the internal results database and sent to the external reporting system by performing a web service request. Finally, a local notification is displayed to the user if new vulnerabilities have been found in the system.

XOvaldi4Android plays a fundamental role within the proposed framework because it is in charge of actually assess the Android system. XOvaldi4Android is an extension of XOvaldi [START_REF] Barrère | Towards Machine-assisted Formal Procedures for the Collection of Digital Evidence[END_REF], a multi-platform and extensible OVAL interpreter. We have ported the XOvaldi system to the Android platform obtaining a 94 KB size library. We have used the Eclipse development environment and the ADT plugin [START_REF]Android Developers[END_REF] for Eclipse to easily manage development projects for Android. The interpreter uses the JAXB 8 technology [START_REF]Java Architecture for XML Binding[END_REF] for automatically generating its internal OVAL-based data model. This technology provides means not only for modeling XML documents within a Java application data model but also for automatically reading and writing them. Such feature provides to the interpreter the ability to evolve with new OVAL versions as well as extensions, in this work for the Android platform, 8 Java Architecture for XML Binding with almost no developing cost. As shown in Fig. 2, the high-level operation performed by XOvaldi4Android follows the same assessment process proposed by OVAL. In order to provide extensibility features, the interpreter decouples the analysis of the OVAL structure from the actual collection and evaluation activities by using a plugin repository. While the former is implemented as the core of the interpreter, each plugin provides injectable functionality (collection and evaluation) for the specific type of OVAL test it was built for. In this manner, declarative extensibility of the interpreter is achieved by automatic code generation using the JAXB technology and functional extensibility is supported by its plugin-based architecture.

VI. PERFORMANCE EVALUATION

Devices with limited resources imperatively require welldesigned and optimized software that take care of such elements. In this section we present an analytical evaluation of the proposed mathematical model as well as a technical evaluation that involves a comprehensive set of experiments showing the feasibility and scalability of our solution.

A. Analytical evaluation

Within the proposed approach, the vulnerability assessment process is governed by Equation (1). Given n as the number of system properties being monitored and m the number of available vulnerability definitions, the complexity of computing the result vector w is n × m. Considering the worst case (n = m), the complexity is O(n 2 ). Being hf latten(P M ) a known value, the number of operations performed during the process are n boolean multiplications plus n -1 integer sums for each vulnerability definition. Then, the total number of boolean multiplications is m × n and the total number of integer sums is m × (n -1). Hence, m × (n + (n -1)) ≈ n 2 arithmetic operations are performed for assessing the entire knowledge repository in the worst case.

Considering a knowledge repository with 1000 vulnerability definitions involving 1000 different system properties, the size of the pattern matrix P M is 10 6 . This means that the assessment process defined by the model will perform 10 6 arithmetic operations for assessing the entire knowledge base. Considering MFLOPS 9 as the performance measure, though boolean and entire operations are cheaper than floating point operations, the assessment requires 1 MFLOP. Within our experimental devices Samsung Galaxy Gio running Android 2.3.3, we have measured an average of 8.936 MFLOPS. With this information, we can infer that a dedicated application of our strategy over a 10 6 size matrix takes less than 1 second in almost any standard Android-based device.

Moreover, latest models may achieve more than 100 MFLOPS meaning that a knowledge source of 10000 vulnerability definitions involving 10000 different properties could be mathematically assessed in less than 1 second. Currently, the OVAL repository [START_REF]The OVAL Language[END_REF] offers 8747 UNIX vulnerability Fig. 3: Scalability statistics in a simulated environment definitions including all versions and families after years of contributions made by the community. Such scenario provides real facts making the proposed approach highly suitable for efficiently performing vulnerability assessment activities.

B. Technical experimentation

We have performed several experiments in order to analyze the behavior of our implementation prototype. The proposed methodology cyclically tests the framework without other applications running in foreground. The OVAL definitions set is increased by 5 each time until a set of 100 definitions is evaluated. The used OVAL definitions are similar in size containing in average two OVAL tests. For instance, the vulnerability with the CVE-2011-3874 id permits a locally installed application to gain root privileges by causing a buffer overflow within libsysutils. This vulnerability only affects specific Android versions (first OVAL test) and requires the existence of the library libsysutils (second OVAL test). Fig. 3 illustrates the behavior of our implementation prototype over the emulated Android device. We analyze three performance dimensions: (1) the CPU utilization when XOvaldi4Android is executed (red solid line with crossings), (2) the XOvaldi4Android time (green dashed line with triangular points) and (3) the total framework execution time (blue dashed line with rounded points). During the XOvaldi4Android execution, we have observed a stable and linear behavior in terms of CPU utilization, consuming 80% in average. Its execution time is also stable as shown by the first derivative within the inner graph. While assessing 50 definitions takes about 72 seconds, 100 definitions takes almost twice the time. The overall execution time across the framework, including database updates and reporting results, shows the same behavior though slightly increased in time due to the sequential execution of its components. It is important to notice that these experiments consider extreme cases. As a matter of fact, only new definitions or a small set of definitions affected by system changes will be evaluated in most situations.

In order to analyze the framework behavior using a real device, we have performed the same experiments using a standard smartphone Samsung Galaxy Gio S5660 (CPU 800 MHz, 278 MB RAM, Android 2.3.3). Fig. 4 illustrates the obtained results. We can observe the same behavior on each curve as with the emulated device, describing a linear growth for each analysis dimension as shown in the inner graph. Nevertheless, we have also detected an improvement in terms of speed and resource usage. The average value for the CPU utilization is now about 65%. In addition, the execution time of XOvaldi4Android is almost half the emulator execution time, taking 38 seconds for analyzing 50 vulnerabilities and 75 for 100 vulnerabilities. This is probably due to a slower emulated CPU. The overall execution time is also reduced due to the faster execution of the vulnerability assessment process. However, its growth rate, though linear, is faster because the internetwork connections are real in this case.

As a final but not less important dimension to analyze, we have experimented with the memory load. Within this analysis, we have considered the allocated memory required by XOvaldi4Android when it is executed. The system classifies the allocated memory in two categories, native and Dalvik, taking in average 40% for native memory and 60% for Dalvik memory. Fig. 5 illustrates the total memory load considering both, over the emulator and the smartphone. We have observed an almost constant utilization of the RAM memory. Within the emulator (blue solid line with rounded points), XO-valdi4Android requires 12 MB in average (4.8 MB of native memory, 7.2 MB of Dalvik memory). Within the smartphone (red dashed line with rhomboid points), XOvaldi4Android requires a little less memory, 11 MB in average (4.4 MB of native memory, 6.6 MB of Dalvik memory).

VII. CONCLUSIONS AND FUTURE WORK

Vulnerability management constitutes a complex activity that must be addressed in order to increase the overall security of computing devices. In that context, we have proposed an approach for supporting vulnerability assessment tasks as the first key step for integrating this activity within the Android platform. We have put forward a mathematical model as well as an optimized strategy that provides solid foundations for its instantiation on this platform. We have proposed a lightweight framework that enables the integration of OVAL security knowledge into the management plane of mobile Android-based devices. By maintaining low-consumption services monitoring the system, the proposed approach minimizes heavy task executions by only triggering assessment activities when configuration changes are detected or new vulnerability definitions are available. In light of this, we have developed an implementation prototype that efficiently performs selfassessment activities by following the proposed optimized strategy. We have also performed an analytical evaluation of the proposed model as well as an extensive set of technical experiments that shows the feasibility of our solution.

For future work we plan to analyze protection mechanisms of the assessment framework itself as well as collaborative techniques for exchanging security information among neighboring devices over secure channels. We aim at distributing the resulting improved implementation prototype within the community as open source. In addition, botnets such as the one built by the DroidDream malware in 2011 are an emerging mobile trend [7]. We also aim at extending our previous work [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF] for quantifying compliant network nodes involved in distributed vulnerabilities in order to describe massive attack scenarios within mobile environments. Finally, we state that real autonomy can be achieved if mobile devices are capable of closing the vulnerability lifecycle by performing corrective tasks as well. In that context, we also plan to analyze remediation strategies for correcting vulnerable configurations, leading us closer to get real autonomic solutions.

Fig. 2 :

 2 Fig. 2: Self-assessment service high-level operation

Fig. 4 :Fig. 5 :

 45 Fig. 4: Scalability statistics in a real device

  Event event, PatternMatrix matrix, SystemState state Output: VulnerabilityList list 1 if event is of type SystemChange then

	2	objs ← getAf f ectedObjectsByEvent(e);
	3	foreach Property p ∈ state do
	4	o ← getObjectF romP roperty(p);
	5	if o ∈ objs then
	6	result ← evaluateP roperty(p);
	7	updateSystemState(state, p, result);
	8	end
	9	end
	10 end
	11 if event is of type Def initionU pdate then
	12	def s ← getDef initionsF romEvent(e);
	13	props ← getP ropertiesF romDef initions(def s);
	14	foreach Property p ∈ props do
	15	if p ∈ state then
	16	addEmptyP ropertyColumn(matrix, p);
	17	addEmptyP ropertyColumn(state, p);
	18	result ← evaluateP roperty(p);
	19	updateSystemState(state, p, result);
	20	end
	21	end
	22	foreach Definition d ∈ def s do
	23	addAndLoadDef initionRow(matrix, d);
	24	end
	25 end
	32	end
	33	index ← index + 1;
	34 end

Input: 26 w ← hSumM atrix(matrix) -(matrix * state); 27 index ← 0; 28 foreach Entry v ∈ w do 29 if v = 0 then 30 vulnDef ← getV ulnDef (index); 31 addT oOutputList(list, vulnDef );

Malicious software including virus, worms and spyware among others

Open Vulnerability and Assessment Language

Security Content Automation Protocol

ACKNOWLEDGEMENTS

This work was partially supported by the EU FP7 Univerself Project and the FI-WARE PPP.


Martín Barrère
email: barrere@inria.fr

Rémi Badonnel
email: badonnel@inria.fr

Olivier Festor
email: festor@inria.fr

Collaborative Remediation of Configuration Vulnerabilities in Autonomic Networks and Systems

Autonomic computing has become an important paradigm for dealing with large scale network management. However, changes operated by administrators and self-governed entities may generate vulnerable configurations increasing the exposure to security attacks. In this paper, we propose a novel approach for supporting collaborative treatments in order to remediate known security vulnerabilities in autonomic networks and systems. We put forward a mathematical formulation of vulnerability treatments as well as an XCCDF-based language for specifying them in a machine-readable manner. We describe a collaborative framework for performing these treatments taking advantage of optimized algorithms, and evaluate its performance in order to show the feasibility of our solution.

I. INTRODUCTION

Autonomic computing contributes to address the growing complexity of network management by defining a strong basis for automated systems capable of managing themselves in an autonomous manner [START_REF] Kephart | The Vision of Autonomic Computing[END_REF], [START_REF]An Architectural Blueprint for Autonomic Computing[END_REF]. Nevertheless, when selfmanagement operations are performed in order to obey highlevel policies, operated changes may lead to vulnerable states increasing the exposure of the environment. In addition, human errors occur when systems administration tasks are executed, therefore vulnerability management activities, namely, identification, classification and remediation of vulnerabilities, are required in order to ensure safe configurations. We have already shown in [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF] that it is possible to specify and assess distributed vulnerabilities involving several devices simultaneously, and also covering device-based vulnerabilities as a particular case. In this paper we propose a collaborative strategy for remediating both distributed and device-based vulnerabilities.

The scenario presented in Fig. 1 shows a typical example [START_REF] Zhang | Denial of Service Attack and Prevention on SIP VoIP Infrastructures using DNS Flooding[END_REF] where two devices, a SIP 1 server with no flooding protection and a local DNS 2 server with external unknown name resolution, constitute a distributed vulnerable state. In this situation, an attacker can perform a denial of service attack by flooding the SIP server with unresolvable domains that must be solved by a local DNS server. The local DNS server in turn is configured for solving unknown domains querying external servers, thus increasing the number of waiting requests as well as the response time for each SIP request. If at least one of the servers is not present or is not compliant with the required specific state, the distributed vulnerability has no 1 Session Initiation Protocol 2 Domain Name System place in the environment. In order to correct such security problem, different remediation tasks could be performed in the SIP server or in the DNS server. A key challenge is to define a strategy for determining how and by which devices the distributed vulnerability can be remediated. Fig. 1: Distributed vulnerability scenario [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF] We therefore introduce in this paper a collaborative approach for describing and performing treatments of configuration vulnerabilities in autonomic networks and systems. These correction advisories are taken into account by our framework in order to remediate vulnerable states found across the network and thus, reducing the exposure to security attacks. Our main contributions are: (1) a mathematical approach and an XCCDF 3 -based specification language for describing configuration vulnerability treatments, (2) a deployable infrastructure based on the Cfengine system [1], capable of enforcing the application and reporting of configuration vulnerability treatments as security policies, (3) optimized algorithms and their evaluation for performing remediation activities in a collaborative manner over the network.

The remainder of this paper is organized as follows. Section II describes existing work and their limits. Section III presents the proposed approach for modeling configuration vulnerability treatments in autonomic networks and systems. Section IV introduces DXCCDF, a language for specifying distributed vulnerability treatments. The architecture of our framework as well as the proposed remediation algorithms are described in Section V. Section VI provides an evaluation of our solution through a comprehensive set of experiments. Section VII presents conclusions and future work.

II. RELATED WORK

Vulnerability management constitutes a crucial activity for maintaining safe configurations in autonomic networks and systems. Commonly, vulnerabilities can take the form of software flaws or misconfiguration errors and they can be usually corrected by means of different methods such as applying software patches, adjusting configuration settings or removing the affected software [START_REF] Mell | Creating a Patch and Vulnerability Management Program[END_REF]. However, when corrective actions are performed changes are introduced in the environment thus change management mechanisms such as those proposed in [START_REF] Chiarini | Dynamic Dependencies and Performance Improvement[END_REF], [START_REF] Diao | Predicting Labor Cost through IT Management Complexity Metrics[END_REF] must be taken into account. Risk assessment methods are also important as they provide a strong basis for analyzing the impact of remediation activities within the vulnerability treatment process [START_REF] Setzer | Decision Support for Service Transition Management -Enforce Change Scheduling by Performing Change Risk and Business Impact Analysis[END_REF], [START_REF] Sauve | Change Priority Determination in IT Service Management Based on Risk Exposure[END_REF], [START_REF] Wickboldt | Improving IT Change Management Processes with Automated Risk Assessment[END_REF]. It is crucial to ensure safe changes not only from an operational viewpoint but from a security perspective too. While several works have been focused on vulnerability management such as [START_REF] Wang | OVM: An Ontology for Vulnerability Management[END_REF], just a few works address this topic into autonomic environments, mainly focused on the vulnerability assessment activity [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF], [START_REF] Barrère | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF], [START_REF] Chiang | Risk and Vulnerability Assessment of Secure Autonomic Communication Networks[END_REF]. Fig. 2: Languages involved in the vulnerability management process Several languages have been proposed for supporting the vulnerability management process as depicted in Fig. 2. De facto standards such as OVAL 4 [START_REF]The OVAL Language[END_REF] and XCCDF provide means for dealing with device-based vulnerabilities. OVAL is an XML-based language supported by MITRE Corporation [5] intended to standardize how to assess and report upon the machine state of computer systems, with a particular focus on vulnerability descriptions. The XCCDF language maintained by NIST [6] provides standard means for specifying security checklists under both technical and non-technical perspectives. In order to also cover distributed scenarios, we have proposed DOVAL 5 in our previous work [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF], a language built on top of OVAL for describing and assessing distributed vulnerabilities. However, there is a lack for supporting collaborative treatments capable of mitigating and remediating distributed vulnerabilities. In this paper, we propose the DXCCDF 6 language, built on top of XCCDF, as a means for specifying distributed security treatments in a generalized manner for both distributed and device-based vulnerabilities.

III. MODELING VULNERABILITY TREATMENTS

In this section we formalize configuration vulnerability treatments by extending and enhancing our previous mathe- 4 Open Vulnerability and Assessment Language 5 Distributed OVAL 6 Distributed XCCDF matical model [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF]. A distributed vulnerability is defined as a set of conditions over two or more network devices that if observed simultaneously, a potential threat is present on that network. It is important to remark that the required conditions to be observed over a specific device do not necessarily constitutes a complete device-based vulnerability description.

A. Describing distributed vulnerabilities

In order to specify a distributed vulnerability as well as the network over which this vulnerability will be assessed, the model defines a set of core definitions as follows:

• H = {h 1 , h 2 , . . . } denotes the set of devices in the network (e.g. hosts, routers).

p i ∈ S (i ∈ N) ii if α, β ∈ S, then (α β) ∈ S ∈ {∧, ∨} iii if α ∈ S, then (¬α) ∈ S.
• R = {r 1 , r 2 , . . . } denotes the set of relationships between network devices such as reachability and service provisioning. The relationships are modelled as n-ary predicates of the form r i (h i , ..., h j ).

Based on the previous definitions, a distributed vulnerability DV is defined as the compliant projection of the pattern (P H , P R ) over the network (H, R) where the constructs P H and P R are defined as follows:

• P H = {s 1 , ..., s n } denotes the set of machine states or roles required to be observed on specific network devices. • P R = {r 1 , ..., r v } denotes the set of relationships between those devices matching the required roles.

Under a logical perspective, a compliant projection of the pattern (P H , P R ) over the network (H, R) makes the following sentence to be true:

∃(h 1 , ..., h n )(s 1 (h 1 ) ∧ ... ∧ s n (h n ) ∧ r 1 (h i , ..., h j ) ∧ ... ∧ r v (h k , ..., h l )).
We specify the previous sentence in short by considering the predicate DV (H, R) that expresses the evaluation of a distributed vulnerability DV based on the pattern (P H , P R ) over a generic network (H, R).

It is important to notice that the model allows to specify a device-based vulnerability by just defining P H = {s 1 } and P R = {}, or a sequence of vulnerabilities spread across the network by considering P H = {s 1 , ..., s n } and P R = {}.

B. Specifying distributed treatments

Based on this modeling, we consider a distributed treatment DT as a body of tasks performed over a set of network devices that introduces configuration changes in order to eliminate the security weakness described by a specific distributed vulnerability DV . In order to formally define what a distributed treatment is, we extend the description model explained in Section III-A by defining the following domains:

• A = {a 1 , a 2 , . . . } denotes the set of actions applicable over network devices. • T = {t 1 , t 2 , . . . } denotes the set of tasks applicable over network devices. A task t i is a logical combination of actions and its logical value is computed based on the successful application of each action. The set T is inductively defined as follows:

i if a i ∈ A, then a i ∈ T (i ∈ N) ii if α, β ∈ T , then (α β) ∈ T
∈ {∧, ∨} In order to define the application of remediation tasks over the network, we specify the following set of core functions: We therefore define a distributed treatment DT as the compliant application of (T H , T R ) over the network (H, R) that eliminates every possible matching projection of the pattern (P H , P R ) over (H, R). Under a logical perspective, this is defined as the disjunction of task applications over each potential combination of devices and network relationships (H , R ) performing the roles required by the distributed vulnerability DV as follows:

• state H : H → S ≡
DT (H, R) = Π(T H , T R ) = task H (h 1 , t H 1 ) ∨ . . . ∨ task H (h n , t H n ) ∨ task R (r 1 , t R 1 ) ∨ . . . ∨ task R (r v , t R v ) ∀H = {h 1 , ..., h n } ⊆ H, R = {r 1 , ..., r v } ⊆ R such that DV (H , R ) holds.
Changes done for correcting different instances (H , R ) of the distributed vulnerability must not shadow performed remediations for other observed vulnerable instances of DV , thus ¬DV (H, R) must hold after the DT application.

IV. DXCCDF, A DISTRIBUTED VULNERABILITY REMEDIATION LANGUAGE

In order to capture the previous mathematical constructions, we have conceived the DXCCDF language, built on top of XCCDF, as a means for expressing vulnerability treatments in a machine-readable manner. XCCDF rules allow to specify remediation information that can be used by automated systems to perform corrective actions when specific states are detected. These states can be specified by languages such as OVAL and DOVAL. DXCCDF extends XCCDF by considering a new building block named complex-Rule under the dxccdf namespace. This extension provides the ability to specify a boolean expression involving all the potential tasks that can be performed for remediating a specific machine state. Fig. 3 depicts the mapping between the main components involved in the mathematical model and their representatives constructs within the DXCCDF language. An action a i can be understood as a simple operation, i.e. a shell command, that is performed for changing a system property p i . This property can be checked and remediated using an XCCDF rule. A task t i is a combination of actions in the form of a boolean expression intended to correct a specific state s i . Tasks are represented by means of DXCCDF complex rules. A distributed treatment DT is also represented using DXCCDF complex rules and they are finally put together into XCCDF groups. We now put forward an illustrative DXCCDF example illustrated in Listing 1 where a distributed treatment is specified in order to provide directives for remediating the distributed vulnerability previously depicted in Fig. 1. For the sake of clarity, we have omitted some XCCDF components that should be present in valid instances. Within this document, the group for vulnerability treatments is selected for evaluation containing only one treatment. The construct DXCCDF complex rule represents the distributed treatment itself. A DXCCDF complex rule allows to refer a check system for assessing the distributed vulnerability under analysis by means of a DOVAL reference, and also to specify a logical criterion involving both XCCDF rules and DXCCDF complex rules. In the proposed scenario there exist two involved roles, the SIP server and the DNS server. Within the DXCCDF example, one remediation task has been defined for each role, namely, T SIP and T DN S . The task T SIP is in turn a non-atomic task since two corrective tasks, namely, T SIP yum and T SIP web , can be alternatively performed. Thus, the distributed treatment expressed by the DXCCDF complex rule corresponds to the logical expression (T SIP yum ∨ T SIP web ∨ T DN S ) where each one of the referenced standard XCCDF rules are defined in the final part of the document. These XCCDF rules define the actual corrective actions to perform over the involved devices and they are orchestrated by the DXCCDF complex rule in order to remediate the specific distributed vulnerability.

V. A FRAMEWORK FOR COLLABORATIVELY TREATING DISTRIBUTED VULNERABILITIES

The DXCCDF language provides the capability of describing remediation activities that can be consumed by autonomic entities in order to secure the environment. In this section we propose a framework for supporting collaborative treatments specified in DXCCDF considering the main building blocks of our previous DOVAL-based assessment framework.

A. Architecture overview

In order to remediate a distributed vulnerability several tasks may be performed on different devices. At the moment of the analysis however, some of the involved devices may present particular states that do not allow them or make it more expensive to perform specific corrective actions than other involved devices. Factors such as availability, capability, or even policy consistency must be considered during the remediation process. We refer to this spectrum of factors as the cost of the node for performing a corrective task. Potential mechanisms for actually computing task costs are beyond the scope of this paper and they may involve several activities such as risk assessment and change management techniques. The main process for detecting and remediating distributed vulnerabilities considers these costs as illustrated in Fig. 4. Repositories of vulnerability descriptions as well as treatments specifications are available constituting the knowledge source of the network. At Step 1, a vulnerability description is consumed and assessed over the network as explained in [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF]. If there is one or more pattern matching instances over the network, a treatment analysis is launched at Step 2.1 and its corresponding distributed treatment is consumed from the treatments repository at Step 2.2. Based on the available tasks for correcting the security vulnerability, devices are analyzed across the network in order to find a node for performing a Fig. 4: Collaborative treatment -High level operation remediation task. Once the treatment execution has been done and the network has been secured at Step 3, a treatment report is generated at Step 4 involving the vulnerability description, the treatment description used for remediating the vulnerability as well as the information gathered from the network in order to perform the corrective activity. Generated reports are stored in a historical database providing the ability to consider past experiences in future treatments.

B. Assessment and treatment strategies

We consider in our approach that treatment descriptions may be available later in time after vulnerabilities have been discovered. In light of this, we put forward a treatment strategy that can be applied after performing assessment activities and that can also be integrated to the assessment process if treatments are available at that time.

In order to present the proposed treatment strategy, we introduce a situation where the distributed vulnerability described in Fig. 1 is present in the form of many instances. Within the example illustrated in Fig. 5, a network with a Cfengine server and five devices is considered. Devices h1, h2 and h3 are involved in the instances of the distributed vulnerability described by a DOVAL document. Once the assessment has been performed at Step 1, a DOVAL report identifying detected vulnerability instances is generated. In order to collect required information, a spanning tree is generated at Step 2 by means of Cfengine's functionalities [START_REF] Burgess | Network Patterns in Cfengine and Scalable Data Aggregation[END_REF] as used in [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF]. The Cfengine server traverses the network starting at the root of the spanning tree where each node will inform on how it can collaborate in the corrective tasks and at what cost, as depicted Fig. 5: Vulnerability treatment scenario in Algorithm 1 that we explain later. At Step 3, a report is generated including the cost of each node for correcting the roles that each one is performing. Based on this information, the Cfengine server selects a node for applying corrective actions at Step 4 and a report indicating the results of the remediation activity is generated. In the proposed approach, a spanning tree is built in order to explore the network. Algorithm 1 presents the activity performed at each active node of the tree (line 1) for gathering and analyzing devices information. Each node h reads the list of roles involved in the vulnerability instances given in the DOVAL document dv, identifies itself in the list (lines 2-3), and for each task t found in the DXCCDF document dt applicable on each specific role s that h plays (lines 4-5), the task cost is computed by the node itself and attached to the general cost table ct (lines 6-7). traversal continues on the left and right sub-trees (lines 10-11) until the whole spanning tree has been explored. This strategy can be easily integrated if treatments are available during the assessment process. By computing task costs at the same time network devices are evaluated looking for specific states, the Cfengine server will have all the required information for deciding which nodes will execute remediation tasks. Already scheduled as future work, a decentralized distributed strategy would allow any agent to start a vulnerability treatment though distributed algorithms such as leader election algorithms [START_REF] Garcia-Molina | Elections in a Distributed Computing System[END_REF], [START_REF] Castillo | A Modified O(n) Leader Election Algorithm for Complete Networks[END_REF], are necessary for deciding which node will execute corrective tasks.

Input: TreeNode h,

VI. PERFORMANCE EVALUATION

Within the proposed framework, the complexity of the process is dominated by the number of nodes in the network and Algorithm 1 is O(n). This means that the treatment process can be coupled with the assessment process without increasing its growth rate. Given a distributed vulnerability, the total assessment time under both a sequential (T A S ) and a parallel (T A P ) approach has been mathematically defined in [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF]. In order to evaluate the whole time process involving assessment and treatment activities (A + T ), we have extended these definitions by considering two additional parameters, namely, λ that denotes the average number of available tasks for each role s j , and w denoting the average time for computing the cost of a single task. The new equations are defined as follows:

T A+T S = T A S + (n * k * P (A) * λ * w) (1)
T A+T P w = T A P w + (k * λ * w) (2)
Using a sequential approach (T A+T S ), the total time is given by the time required for assessing the distributed vulnerability plus the time needed for each node (n nodes in the network) to assess its k potential roles. The probability for a node to play a certain role s j is expressed by P (A). For those roles present in the node, the number of tasks λ multiplied by the average time each task takes w is considered. Under a parallel approach (T A+T P w ) and considering the worst case, the total time is given by the time required for assessing the distributed vulnerability in the worst case plus the time needed for a node to compute the cost of every available task (λ tasks) for every role s j considering an average time w for each task. In order to prove the scalability of the proposed approach, we have performed several analytical experiments that combine the assessment and treatment processes at the same time as shown in Fig. 6. Both solid blue lines with rounded and triangular points represent the time growth when the number of network devices is increased and only the assessment process is performed under a sequential (T S (A)) and a parallel (T P w (A)) approach. Dashed red lines show the time behavior when assessment and treatment activities are performed at the same time (A + T ). T S (A + T ) illustrated by the dashed red line with rounded points shows the same growth rate than T S (A). The same phenomenon can be observed when a parallel approach is taken as depicted by T P w (A) and T P w (A + T ). Within our experiments we have overvalued the parameter w in order to obtain a visible distance between curves and be able to notice the same growth behavior. First derivatives drawn in the inner graph confirms the same growth rates for both sequential (green solid line) and parallel (green dashed line) approaches, considering only the assessment (A), and both the assessment plus treatment (A + T ) activities.

In order to provide a technical and deployable infrastructure for performing treatment activities, we are currently developing Scapalyzer, a Java-based [START_REF]Java technology[END_REF] system capable of consuming OVAL and DOVAL vulnerability descriptions as well as XCCDF and DXCCDF treatment descriptions and producing the appropriate assessment and corrective Cfengine policy rules. Scapalyzer uses the services provided by our previous system [START_REF] Barrère | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF], [START_REF] Barrère | Towards the Assessment of Distributed Vulnerabilities in Autonomic Networks and Systems[END_REF], and it is currently focused on the Cisco IOS platform [START_REF]Cisco IOS[END_REF] though more platforms can be also supported by means of its plugin-based architecture. Moreover, Scapalyzer uses the JAXB framework [START_REF]Java Architecture for XML Binding[END_REF] for managing XML related issues, thus enabling our system to seamlessly evolve with new versions of vulnerability and remediation description languages by automatically regenerating its internal data model.

VII. CONCLUSIONS AND FUTURE WORK

In this paper we propose a collaborative approach for integrating remediation descriptions into the management plane of autonomic networks and systems. We have put forward a mathematical model for defining vulnerability treatments that provides a robust foundation for its technical implantation. Indeed, an XML-based language called DXCCDF has been designed for capturing these mathematical constructs, providing the ability of describing remediation activities in a machinereadable manner. Our Cfengine-based framework takes into account these vulnerability treatment descriptions when unsafe vulnerable states are detected during the vulnerability assessment process in order to eradicate such security weaknesses. We have performed an analytical performance evaluation of our approach obtaining successful linear costs when it is integrated into the vulnerability management process. We have also introduced Scapalyzer, an under-development prototype implementation for translating DXXCDF remediation descriptions into Cfengine policy rules.

Treating and remediating vulnerabilities opens a wide spectrum of challenges that must be addressed in order to fully integrate the vulnerability management process into the management plane of self-governing environments. The proposed framework structures the remediation activity, however metrics are required for quantifying the costs of corrective remediation tasks with respect to device capacities, service dependencies and policy consistency. Sometimes the same corrective activity may solve several vulnerable states at once, therefore optimized strategies must be specified for minimizing these remediation costs. Finally, centralized approaches may generate bottleneck issues implying poor performance in certain situations. Decentralized distributed vulnerability management strategies are required for tackling this issue by balancing the workload in the network. However, the support algorithms pose hard challenges in terms of correctness and efficiency thus appropriate formal proofs should be considered as well.

Fig. 3 :

 3 Fig. 3: Mapping the model into the DXCCDF language

  <c d f : B e n c h m a r k i d =" s i p-dos-t e s t -1" x m l n s : d x c c d f =" . . . " x m l n s : c d f =" . . . " . . .> <c d f : t i t l e> DXCCDF e x a m p l e </ c d f : t i t l e> <c d f : G r o u p i d =" v u l n e r a b i l i t y-t r e a t m e n t s " s e l e c t e d =" 1 "> <c d f : r e q u i r e s i d r e f ="dv1-t r e a t m e n t " /> </ c d f : G r o u p> <d x c c d f : c o m p l e x-R u l e i d ="dv1-t r e a t m e n t " s e l e c t e d =" 1 " c h e c k =" 1 "> <d x c c d f : c h e c k s y s t e m =" h t t p : / / d o v a l . i n r i a . f r / XMLSchema / d o v a l "> <d x c c d f : c h e c k-c o n t e n t-r e f h r e f =" dvDefns . xml" name=" d o v a l : i n r i a : d e f : 1 " /> </ d x c c d f : c h e c k> <d x c c d f : c r i t e r i a o p e r a t o r ="OR"> <d x c c d f : c r i t e r i a o p e r a t o r ="OR"> <d x c c d f : c r i t e r i o n i d r e f =" f l o o d i n g-p r o t e c t i o n-yum" c h e c k =" 0 " /> <d x c c d f : c r i t e r i o n i d r e f =" f l o o d i n g-p r o t e c t i o n-custom " c h e c k =" 0 " /> </ d x c c d f : c r i t e r i a> <d x c c d f : c r i t e r i o n i d r e f =" s t o p-bind-daemon" c h e c k =" 0 " /> </ d x c c d f : c r i t e r i a> </ d x c c d f : c o m p l e x-R u l e> <c d f : R u l e i d =" f l o o d i n g-p r o t e c t i o n-yum" s e l e c t e d =" 1 "> <c d f : f i x> yum i n s t a l l a s t e r i s k -s i p-dos-p a t c h </ c d f : f i x> <c d f : c h e c k s y s t e m =" h t t p : / / o v a l . m i t r e . org / XMLSchema / o v a l "> <c d f : c h e c k-c o n t e n t-r e f h r e f =" s i p D e f n s . xml" name=" o v a l : m i t r e : d e f : 1 0 0 2 " /> </ c d f : c h e c k> </ c d f : R u l e> <c d f : R u l e i d =" f l o o d i n g-p r o t e c t i o n-custom " s e l e c t e d =" 1 "> <c d f : f i x> wget h t t p : / / d o v a l . i n r i a . f r / f i x e s / s i p / a s t e r i s k -s i p-dos-p a t c h-r 0 . 2 . rpm rpm -Uvh a s t e r i s k -s i p-dos-p a t c h-r 0 . 2 . rpm </ c d f : f i x> <c d f : c h e c k s y s t e m =" h t t p : / / o v a l . m i t r e . org / XMLSchema / o v a l "> <c d f : c h e c k-c o n t e n t-r e f h r e f =" s i p D e f n s . xml" name=" o v a l : m i t r e : d e f : 1 0 0 2 " /> </ c d f : c h e c k> </ c d f : R u l e> <c d f : R u l e i d =" s t o p-bind-daemon" s e l e c t e d =" 1 "> <c d f : f i x> s e r v i c e named s t o p </ c d f : f i x> <c d f : c h e c k s y s t e m =" h t t p : / / o v a l . m i t r e . org / XMLSchema / o v a l "> <c d f : c h e c k-c o n t e n t-r e f h r e f =" u n i x D e f n s . xml" name=" o v a l : m i t r e : d e f : 2 0 0 0 " /> </ c d f : c h e c k> </ c d f : R u l e> </ c d f : B e n c h m a r k> Listing 1: DXCCDF vulnerability treatment

Fig. 6 :

 6 Fig. 6: Time statistics for vulnerability assessment and treatment activities

  = {p 1 , p 2 , . . . } denotes the set of device properties in the form of unary predicates p i (h), h ∈ H.• S = {s 1 , s 2 , . . . } denotes the set of device states where a state s i describes a set of properties required to be observed over a network device (called role). The set S is inductively defined as follows: i if p i ∈ P , then

• P

  function that takes a device h ∈ H as input and returns its current state s ∈ S. • state R : R → 2 S ≡ function that takes a network relationship r ∈ R as input and returns a set with the current state s i ∈ S of each involved network device h i ∈ H in the relationship. H n } denotes the body of available tasks for performing over network devices where each task t H i is semantically related to a specific state s i . Usually, the following equation can hold |T H | < |P H |, meaning that treatment tasks are not always available for correcting certain device states. • T R = {t R 1 , ..., t R v } denotes the body of available tasks for performing over network relationships where each task t R i is semantically related to a specific relationship r i . Usually, the following equation can hold |T R | < |P R |, meaning that treatment tasks are not always available for correcting certain network relationships.

• action : H × A → H ≡ function that takes a device h ∈ H as input and returns the same device h after performing an action a ∈ A.

• task H : H × T → H ≡ function that takes a device h ∈ H as input and returns the same device h after performing a task t ∈ T that produces an observable change on its state. This means that at least one action a i ∈ A must introduce a change that cannot be rolled back by any other action in the task nor a combination of them.

The following property holds in the considered model: state H (h) = state H (task H (h, t)), ∀t ∈ T , ∀h ∈ H. • task R : R × T → R ≡ function that takes a network relationship r ∈ R as input and returns the same network relationship r after performing a task t ∈ T over its member devices. Based on the definition of T, is can be noticed that the task t will produce an observable change on its state and that the following property also holds: state R (r) = state R (task R (r, t)), ∀t ∈ T , ∀r ∈ R. • T H = {t H 1 , ..., T

The model and the DXCCDF language Model block Insight Applies to Expressed with

	Action ai	chmod 644	Property pi	XCCDF rule
		passwd
	Task ti	a1 ∨	State si	DXCCDF complex
		(a2 ∧ a3)		rule
	Distributed	t1 ∨ t2 ∨ . . .	Distributed	DXCCDF complex
	treatment DT	∨ t k ∨ . . .	vulnerability	rule
	Distributed	{DT1, DT2,	{DV1, DV2,	XCCDF group of
	treatments	. . . }	. . . }	complex rules

  DOVAL document dv, DXCCDF document dt, CostTable ct. Output: Table with costs for each node on each role.

	1 if currentNode h is alive then
	2	roleList ← f indRolesF orDevice(h, dv);
	3	foreach role s ∈ roleList do
	4	taskList ← f indT asksF orRole(s, dt);
	5	foreach task t ∈ taskList do
	6	cost ← queryN odeF orT askCost(h, t);
	7	updateCostT able(ct, h, s, cost);
	8	end
	9	end
	10	gatherT asksCosts(lef tT reeN ode(h), dv, dt, ct);
	11	gatherT asksCosts(rigthT reeN ode(h), dv, dt, ct);
	12 end
	Algorithm 1: gatherTasksCosts (recursive)

eXtensible Configuration Checklist Description Format[START_REF] Ziring | Specification for the Extensible Configuration Checklist Description Format[END_REF] 978-3-901882-48-7 c 2012 IFIP

ACKNOWLEDGEMENTS

This work was partially supported by the EU FP7 Univerself Project and the FI-WARE PPP.


Ph.D Martín Barrère
email: martin.barrere@inria.fr

Ovalyzer: an OVAL to Cfengine Translator (IEEE NOMS 2012 -Demo Abstract)

Topic. Vulnerability Management for Safe Configurations in Autonomic Networks and Systems.

Background. The continuous growth of networks as well as the diversification of their services have considerably increased the complexity of their management. Traditional network management approaches are not suitable for supporting this sustained dynamics because they do not scale. Autonomic computing [START_REF]An Architectural Blueprint For Autonomic Computing[END_REF] provides new perspectives with respect to this issue, through the automation of the management tasks. Autonomic networks and systems are responsible for their own management. They have to adapt their configurations with respect to their environment, to protect themselves against security attacks, to repair their own failures, and to optimize their various parameters. When autonomic related operations are performed, the environment is modified in order to achieve specific objectives. However, such operations may lead to potential vulnerable states and increase the exposure to security threats. Indeed, as systems and technologies evolve, new space for vulnerabilities comes into scene. Autonomic networks and systems should therefore integrate support mechanisms for preventing vulnerabilities. As happens in the real world, autonomic elements coexist within dynamic environments, interacting with others autonomic and non-autonomic elements. If an autonomic element is compromised, its functions and abilities become untrustworthy and eventually disabled; thus autonomic elements that use services of the former become compromised as well. This inevitably leads to distrust and failure of the autonomic environment. Thus, vulnerability awareness constitutes a fundamental property that must be present in self-governed entities. Autonomic elements unable to support this capability will age with time, becoming more vulnerable, insecure and useless. Vulnerability management is a crucial activity for ensuring safe configurations and reducing the exposure of such autonomic systems. It consists in checking their configurations, identifying the presence of vulnerable states and performing the required maintenance operations (typically, modification of configuration parameters and/or application of security patches).

Objectives. In order to integrate vulnerability descriptions in the management plane of autonomic networks and systems, we have taken advantage of external knowledge sources such as OVAL repositories enabling the ability of highly increasing vulnerability awareness in such selfgoverned environments. Cfengine [1], a widely deployed configuration and administration system, has been taken as the autonomic part of this approach while the OVAL language is the resource that provides support for vulnerability descriptions. We have chosen the IOS platform for Cisco devices as a case study, generating Cfengine policy rules capable of analyzing and detecting vulnerabilities over such platform, thus increasing vulnerability awareness in an autonomic manner.

Ovalyzer. In order to provide a computable infrastructure to the proposed approach we have developed Ovalyzer, an extensible plugin-based OVAL to Cfengine translator. The translator is responsible for the translation of OVAL documents to Cfengine policy rules that represent them. The translator takes as input the content of OVAL documents and produces Cfengine code that is structured as Cfengine policy files that can be later consumed by a Cfengine running instance [START_REF] Barrre | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF]. Figure 2 describes Ovalyzer main components and the high-level interaction between them. Fig. 2. Ovalyzer -High level operation [START_REF] Barrre | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF] At step 1, an OVAL document is consumed as the input of the translator. An OVAL preprocessor is in charge of parsing the content of the specification, adjusting some configuration aspects and feeding the OVAL analyzer module at step 2 with a memory representation of the specified input. The OVAL analyzer module is the component that orchestrates the translation flow and provides the required directives for generating Cfengine code at step 3.i. Several calls are made by the OVAL analyzer module to the Cfengine policy writer depending on the content of the OVAL document. The Cfengine policy writer is in charge of generating the main Cfengine policy entries at step 4.1 and delegating at step 4.2, specific platform rules to plugins specifically designed for generating this type of Cfengine code. Plugins will produce the required Cfengine code that will be included at step 5 inside the generated Cfengine policy files. In brief, the translator core is in charge of managing every high-level aspect of the OVAL documents it processes while available plugins provide the required functionality for generating the appropriate Cfengine code. Ovalyzer has been purely written in Java 1.6 [START_REF]Java technology[END_REF] over Fedora Core [START_REF]Fedora Core[END_REF]. The data model used by Ovalyzer is automatically generated using the JAXB technology [START_REF]Java Architecture for XML Binding[END_REF]. JAXB provides means not only for modeling XML documents within a Java application data model but also for automatically reading and writing them. Such feature provides to Ovalyzer the ability to evolve with new OVAL versions with almost no developing cost. While declarative extensibility of the translator is achieved by automatic code generation using the JAXB technology, functional extensibility is supported by a plugin-based architecture.

The demo. In this demo we will show how we can increase the vulnerability awareness of selfgoverned environments, by feeding the autonomic system Cfengine with security advisories taken from OVAL repositories and automatically translated by Ovalyzer. During the presentation, we will first introduce the background as well as the key concepts of this work by using a small set of slides. Then we will present an scenario where an emulated Cisco router using Dynamips [START_REF]Dynamips/Dynagen Cisco Router Emulator[END_REF] is controlled by an autonomous Cfengine agent, and how Ovalyzer increases the vulnerability awareness of such agent by translating OVAL vulnerability descriptions into Cfengine policy rules. We will show how the approach is capable of assessing and detecting security threats by considering different vulnerable situations over the IOS platform. Vulnerability management integration into autonomic environments poses hard challenges and supporting vulnerability awareness constitutes the first step towards secure self-managed infrastructures capable of detecting and remediating potential security breaches. As to the requirements for this presentation, there are no special needs, power supply and a projector are sufficient enough.

Fig. 1 .

 1 Fig.1. High level architecture[START_REF] Barrre | Supporting Vulnerability Awareness in Autonomic Networks and Systems with OVAL[END_REF]


Emmanuel Caruyer

Rachid Deriche

A Computational Framework for Experimental Design in Diffusion MRI

In this work, we develop a computational framework for optimal design of experiment in parametric signal reconstruction. We apply this to the optimal design of one dimensional q-space, q-ball imaging and multiple q-shell experimental design. We present how to construct sampling scheme leading to minimal condition number, and compare to state-of-the-art sampling methods. We show in particular a better noise performance of these scheme through Monte-Carlo simulations for the reconstruction of synthetic signal. This demonstrates the impact of this computational framework on acquisition in diffusion MRI.

Introduction

Diffusion MRI investigates the properties of tissue microstructure from the analysis of water molecules displacement. The diffusion characteristics, such as the ensemble average propagator or the orientation distribution function, are related to the diffusion signal attenuation through continuous transforms. Since then, the first step in the processing pipeline is usually a parametric estimation of the diffusion signal, from a series of discrete measurements. The number of samples in diffusion MRI is limited to keep the acquisition time compatible with in-vivo measurements. Therefore, the choice of sampling points in the q-space is critical for a proper reconstruction and quantitative analysis of diffusion characteristics.

The question of sampling efficiency has been widely studied for parametric estimation in diffusion MRI. Several approaches were proposed to uniformly arrange points on the sphere in q-ball imaging (QBI), using an analogy between the sampling directions and a pair of antipodal electric charges [START_REF] Jones | Optimal strategies for measuring diffusion in anisotropic systems by MRI[END_REF][START_REF] Jansons | Persistent angular structure: new insights fom diffusion magnetic resonance imaging data[END_REF], or geometric constructions [START_REF] Koay | A simple scheme for generating nearly uniform distribution of antipodally symmetric points on S 2[END_REF]. For the reconstruction of diffusion tensor MRI, the noise performance has been studied through the minimization of the condition number [START_REF] Papadakis | A comparative study of acquisition schemes for DTI[END_REF][START_REF] Skare | Condition number as a measure of noise performance of diffusion tensor data acquisition schemes with MRI[END_REF]. In q-space MRI, several studies on multiple shell sampling [START_REF] Caruyer | Optimal design of multiple q-shells experiments for diffusion MRI[END_REF][START_REF] Assemlal | Evaluation of q-space sampling strategies for the diffusion magnetic resonance imaging[END_REF][START_REF] Portnoy | A novel interlaced sampling scheme for multi-shell q-space MR microscopy[END_REF][START_REF] Daducci | Harmonic analysis of spherical sampling in diffusion MRI[END_REF] focused on the efficiency of various sampling strategies, but they do not provide a method to systematically improve the noise performance.

In this work, we give a general method for optimal design of experiment in parametric signal reconstruction. We apply this to the optimal design on one dimensional q-space experiment, q-ball imaging and multiple q-shell experimental design. In the last section, we compare the proposed method to state-of-the-art sampling strategies.

Theory

Parametric estimation of the diffusion signal

The diffusion signal is approximated in a finite, orthonormal basis of functions

∀q ∈ Ω, E(q) = R i=1 c i f i (q), (1)
where Ω ⊂ R 3 . Depending on the application, we have Ω = R (1D diffusion signal), Ω = S 2 (QBI) or Ω = R 3 (q-space imaging). Provided K measurements y k = E(q k ) of the signal at wavevectors q k , the coefficients ĉi are estimated by least squares. Put in matrix form, we write

ĉ = (H T H) -1 H T y. (2)
H is the design matrix, and has entries H ki = f i (q k ).

Information matrix and optimal design

We present a general method to choose the sampling points q k to optimize the noise performance. A useful index for noise performance and stability of the reconstruction is the condition number κ(M) = λ max (M)/λ min (M) of the information matrix M = 1/K H T H, where K is the number of measurements. The condition number is an upper bound to the error propagation from the measurements to the coefficients estimates. The optimal value of κ(M) is 1, in which case the information matrix is proportional to the identity I R . The coefficients of the information matrix M ij can be interpreted as the approximation of the continuous dot product f i , f j

M ij = 1 K K k=1 f i (q k )f j (q k ) ≈ Ω f i (q)f j (q)dΩ(q) = δ ij (3)
The basis is orthonormal, hence if this approximation is exact, M = I R , and the associated condition number equals 1. This naturally introduces the notion of quadrature formula, and its generalization to higher dimension, called the cubature formula.

Definition 1. A cubature formula for the integral I = Ω g(q)dΩ(q) is a collection of nodes q s and weights ω s such that

I = S s=1 ω s g(q s ) (4)
If such a cubature formula exists for the integral in Eq. 3, then we place the sampling points at nodes q s , and the number of repetitions K s at node q s is proportional to the weight ω s .

Methods

In this section, we derive cubature formulae for the simple harmonic oscillator basis [START_REF] Ozarslan | Simple harmonic oscillator based estimation and reconstruction for 1D q-space MR[END_REF] (1D diffusion signal), spherical harmonic basis [START_REF] Descoteaux | Regularized, fast, and robust analytical q-ball imaging[END_REF] (QBI) and spherical polar Fourier basis [START_REF] Assemlal | Efficient and robust computation of pdf features from diffusion MR signal[END_REF] (q-space imaging).

Optimal design in one dimensional q-space MRI

The simple harmonic oscillator basis for the reconstruction of real diffusion signal in one dimension [START_REF] Ozarslan | Simple harmonic oscillator based estimation and reconstruction for 1D q-space MR[END_REF] is given by Φ

i (q, u) = κ i (u) exp(-2π 2 q 2 u 2 )L -1/2 i (4π 2 q 2 u 2 ), where u is a characteristic length, L -1/2 i
the generalized Laguerre polynomial of degree i and κ i (u) a normalization constant.

Put back into the general framework presented in Section 2.2, we have Ω = R, and the basis functions are f i = Φ i . For the evaluation of the dot product in Eq. 3, we use the substitution x = 4π 2 q 2 u 2 , so that

Φ i , Φ j = 2πuκ i (u)κ j (u) ∞ 0 L -1/2 i (x)L -1/2 j (x)x -1/2 e -x dx. ( 5
)
When the basis is truncated to order N , the evaluation of Eq. 5 reduces to the problem of Gauss-Laguerre quadrature [START_REF] Abramowitz | Handbook of mathematical functions[END_REF]. The optimal samples are q s = √ x s /2πu, with K s repetitions, where K s is proportional to This basis is equivalent to the basis of harmonic polynomial of degree L on S 2 , for which cubature formulae exist and are called spherical design. Definition 2. A spherical t-design [START_REF] Delsarte | Spherical codes and designs[END_REF] is a sequence of K points X = (u k ), k = 1 . . . K on the unit sphere, such that the integral of any polynomial p(x, y, z) of degree at most t over the sphere is equal to the average value of the polynomial on X :

x s e xs /[L -1/2 N (x s )]
1

K K k=1 p(u kx , u ky , u kz ) = S 2 p(ω)d 2 ω. ( 6
)
If the sampling directions u k form a spherical 2L-design, then the approximation in Eq. 3 is exact and κ(M) = 1. For the construction of a spherical 2L-design with antipodal symmetry, we rely here on the equivalence criterion in [START_REF] Goethals | Cubature formulae, polytopes and spherical designs[END_REF]. An example of optimal direction set for order L = 4 is presented on Fig. 1, and compared to a geometric [START_REF] Koay | A simple scheme for generating nearly uniform distribution of antipodally symmetric points on S 2[END_REF] and an electrostatic [START_REF] Jones | Optimal strategies for measuring diffusion in anisotropic systems by MRI[END_REF][START_REF] Jansons | Persistent angular structure: new insights fom diffusion magnetic resonance imaging data[END_REF] arrangements of points.

3.3 Optimal design in q-space imaging

N = 1, L = 4, K = 66 N = 2, L = 4, K = 168
Constant sampling Optimal sampling Constant sampling Optimal sampling Fig. 2. 2-shell (left) and 3-shell (right) acquisition protocols: regular multiple q-shell with constant number of points per shell, and optimal arrangement with minimal condition number for reconstruction in SPF basis.

The truncated spherical polar Fourier (SPF) basis [START_REF] Assemlal | Efficient and robust computation of pdf features from diffusion MR signal[END_REF] is able to represent the diffusion signal in the whole q-space. To represent a continuous signal, which verifies E(0) = 1, we have recently proposed a slightly modified version of the SPF basis [16]. We reconstruct the signal as E(q • u) = exp(-q 2 /2ζ) + nlm a nlm C nlm (q • u). The basis functions are C nlm (q • u) = F n (q)Y lm (u), with

F n (q) = χ n q 2 ζ exp - q 2 2ζ L 5/2 n q 2 ζ , (7)
ζ is a scale factor, χ n a normalization constant, and Y lm is the real spherical harmonic function. When the radial and angular truncation orders are N and L, respectively, this basis has dimension R = N • (L + 1) • (L + 2)/2. Put back into the general framework presented in Section 2.2, we have Ω = R 3 , and the basis functions are f i = C i , where i(n, l, m) = 1, 2, . . . , R for (n, l, m) = (0, 0, 0), (0, 2, -2), . . . , (N, L, L).

For the construction of an optimal design for this basis, we build on the findings of the previous two sections. We show that the radial part of the integral in Eq. 3 reduces to a Gauss-Laguerre quadrature problem, while the angular part reduces to a spherical design problem.

Therefore we propose a design on N + 1 spheres in the q-space. The shell s has radius q s = √ ζx s , where x s is the s th root of L 5/2 N +1 . The number of points K s on shell s should be proportional to ω s = exp(-x s )/[x s (L 5/2 N (x s )) 2 ] Finally, the points on each sphere should form a spherical 2L-design. Example of points sets generated with this method are depicted on Fig. 2. They are compared to multiple shell sampling where the shell radii are evenly spaced, and the number of points equal on each shell, as suggested in [START_REF] Assemlal | Evaluation of q-space sampling strategies for the diffusion magnetic resonance imaging[END_REF]. In this section, we show the feasibility of one dimensional q-space signal reconstruction from a set of measurements on a limited support size. We compare the Gauss-Laguerre quadrature to a regular sampling on the range [0, q max ] We plot on Fig. 3 an example of reconstruction of a diffusion signal corresponding to the restricted diffusion between two parallel planes, separated by distance d [START_REF] Ozarslan | Simple harmonic oscillator based estimation and reconstruction for 1D q-space MR[END_REF]. The truncation order in the basis was set to N = 5, and the corresponding Gauss-Laguerre quadrature works on 6 nodes. The result for a total of 20 acquisitions is visually identical to the reconstruction from a regular sampling. Besides, the associated information matrix is better conditioned for the quadrature sampling. The reason why the condition number is not exactly 1 in this case is that the quadrature weight ω s is approximated by the number of repetitions at node q s , which is an integer.

Experiments and Results

Evaluation of conventional schemes in q-ball imaging

We evaluate and report on Fig. 4 the noise performance of point sets generated with electrostatic analogy [START_REF] Jones | Optimal strategies for measuring diffusion in anisotropic systems by MRI[END_REF][START_REF] Jansons | Persistent angular structure: new insights fom diffusion magnetic resonance imaging data[END_REF] and by geometrical construction [START_REF] Koay | A simple scheme for generating nearly uniform distribution of antipodally symmetric points on S 2[END_REF], for the reconstruction of SH coefficients of the diffusion signal. We compare these sampling methods to the proposed, optimal point set based on spherical design. 4. q-ball imaging: condition number of the information matrix corresponding to the truncated SH up to order L = 4 (left) and L = 6 (right), of the electrostatic, geometric and optimal point sets. The geometric configurations are only provided for K ≥ 50, as this method is reported to be dedicated to large K by the author in [START_REF] Koay | A simple scheme for generating nearly uniform distribution of antipodally symmetric points on S 2[END_REF]. Our proposed, optimal design is based on spherical design, and therefore exists for K ≥ 24 at order L = 4, and for K ≥ 46 at order L = 6 [START_REF] Goethals | Cubature formulae, polytopes and spherical designs[END_REF]. By construction, the condition number associated is exactly 1. Using the results on Gauss-Laguerre quadrature and spherical designs, we generated optimal sampling schemes on multiple shells for the reconstruction in the SPF basis. We compare this to the sampling strategy with shell radii evenly spaced and constant number of points per shell proposed in [START_REF] Assemlal | Evaluation of q-space sampling strategies for the diffusion magnetic resonance imaging[END_REF]. The condition number for the reconstruction in SPF basis is reported on Fig. 5.

We also simulate both methods, for the sampling and reconstruction of a synthetic diffusion signal corresponding to a mixture of Gaussian. Visual reconstruction is reported on Fig. 6, and quantitative comparison on Fig. 7.

Conclusion

In this work, we develop a computational framework for optimal design of experiment in diffusion MRI. For the reconstruction of 1D, spherical and 3D signal, we propose sampling scheme with minimal condition number. Monte-Carlo simulations confirm this result, as the signal to noise ratio of the parameters estimated from optimal sampling scheme is improved with respect to conventional sampling scheme, for the same number of acquisitions.

As a conclusion to this study, we claim that a sampling method is optimal for a reconstruction in a given basis and a given order. In addition to the technical and physical limitations of the imaging system, the choice of the type of reconstruction must be taken into account when designing the acquisition protocol.

Fig. 1 .

 1 Fig. 1. Arrangements of K = 50 points on the unit sphere.

4. 1 Fig. 3 .

 13 Fig.3. Evaluation of Gauss-Laguerre quadrature for one dimensional q-space. (Left) An example of signal and its reconstruction. The blue squares and the green circles represent the regular and quadrature samples respectively. The radii of the circles are proportional to the number of repeated acquisitions. (Right) Condition number of the information matrix.

  Fig.4. q-ball imaging: condition number of the information matrix corresponding to the truncated SH up to order L = 4 (left) and L = 6 (right), of the electrostatic, geometric and optimal point sets. The geometric configurations are only provided for K ≥ 50, as this method is reported to be dedicated to large K by the author in[START_REF] Koay | A simple scheme for generating nearly uniform distribution of antipodally symmetric points on S 2[END_REF]. Our proposed, optimal design is based on spherical design, and therefore exists for K ≥ 24 at order L = 4, and for K ≥ 46 at order L = 6[START_REF] Goethals | Cubature formulae, polytopes and spherical designs[END_REF]. By construction, the condition number associated is exactly 1.

4. 3 Fig. 5 .

 35 Fig. 5. Condition number of multiple shell sampling, corresponding to the SPF basis.

Fig. 6 .

 6 Fig. 6. 2 shell (top) and 3 shell (bottom) sampling in action, for the reconstruction of a synthetic diffusion signal corresponding to a mixture of Gaussian, simulating fiber crossing. The circles represent the sampling shells, and the line widths are proportional to the number of points per shell.

Fig. 7 .

 7 Fig. 7. Mean squared error for a synthetic diffusion signal corresponding to a mixture of Gaussian, with Rician noise (SNR=25).