A Dessiatnikoff

R Akrout
email: rakrout@laas.fr

E Alata
email: ealata@laas.fr

M Kaâniche
email: kaaniche@laas.fr

V Nicomette
email: nicomett@laas.fr

A clustering approach for web vulnerabilities detection

Keywords: Web security assessment, security scanners, Web vulnerabilities, clustering, dynamic analysis

This paper presents a new algorithm aimed at the vulnerability assessment of web applications following a blackbox approach. The objective is to improve the detection efficiency of existing vulnerability scanners and to move a step forward toward the automation of this process. Our approach covers various types of vulnerabilities but this paper mainly focuses on SQL injections. The proposed algorithm is based on the automatic classification of the responses returned by the web servers using data clustering techniques and provides especially crafted inputs that lead to successful attacks when vulnerabilities are present. Experimental results on several vulnerable applications and comparative analysis with some existing tools confirm the effectiveness of our approach.

I. INTRODUCTION

Web application vulnerabilities have become in the recent years a major threat to computer systems security. This is illustrated by the 2010 CWE/SANS top 25 most dangerous software errors report published by MITRE in which the two top positions are taken by web application vulnerabilities (Cross-Site Scripting and SQL injections) [START_REF] Mitre | CWE/SANS Top 25 most dangerous software errors[END_REF]. This situation can be explained e.g., by the increase in complexity of web technologies and their frequent evolution, the short development cycles of web applications during which testing and validation activities are limited, and also, in some cases, by the lack of security skills and culture of the developers.

Web applications vulnerabilities can be exploited by the attackers to gain unauthorized access, obtain or modify sensitive data or even perform denial of service attacks. To cope with these threats, several solutions have been developed to prevent, detect or tolerate potential intrusions. Such techniques can be used during the development phase and also during the operation phase. As an example, we can list the following techniques.

• Static analysis of the source code [START_REF] Huang | Securing Web Application code by static analysis and runtime protection[END_REF], [START_REF] Livshits | Finding security errors in Java program with static analysis[END_REF], [START_REF] Jovanovic | Static analysis for detecting taint-style vulnerabilities in web applications[END_REF], [START_REF] Xie | Static detection of vulnerabilities in scripting languages[END_REF], [START_REF] Wassermann | Sound and precise analysis of web applications for injection vulnerabilities[END_REF], [START_REF] Lam | Securing Web Applications with static and dynamic information flow tracking[END_REF] allowing the identification of vulnerabilities before web application deployment.

• Detection and possible sanitization at runtime of malicious requests before they reach the server. The corresponding tools can run on the server [START_REF] Pietraszek | Defending against injection attacks through context sensitive string evaluation[END_REF], [START_REF] Kruegel | Anomaly Detection of Web-based Attacks[END_REF], or between the client and the server acting as a proxy [START_REF] Kirda | Noxes: A client-side solution for mitigating cross-side scripting attacks[END_REF]. Application-level firewalls can be included in the latter category.

• The security testing of web applications based on the use of black-box security scanners [START_REF] Stefan | SecuBat: a web vulnerability scanner[END_REF]. These tools consist in crawling the target application to identify reachable pages and possible input vectors, and generate specially crafted inputs to determine the presence of vulnerabilities. In this paper, we focus on web vulnerability scanners. A large number of vulnerability scanners have been developed, including commercial tools such as Acunetix WVS, WebInspect and AppScan [START_REF]Top 10 vulnerability scanners[END_REF], open source tools such as W3af, Wapiti, Nikto, and other publicly available tools such as Secubat [START_REF] Stefan | SecuBat: a web vulnerability scanner[END_REF]. Given the high complexity of current web sites that include a large number of pages to be analyzed, these tools provide a useful support for the identification of vulnerabilities in such systems. Recent analysis focused on the assessment of such tools have pointed out the need to improve their detection effectiveness, and to enhance the automation capabilities offered by such tools ( [START_REF] Fonseca | Testing and Comparing Web vulnerability scanning tools for SQL injections and XSS attacks[END_REF], [START_REF] Bau | State of the art: Automated black-box web application vulnerability testing[END_REF], [START_REF] Doupé | Why Johnny can't pentest : An analysis of black-box web vulnerability scanners[END_REF]). Indeed, depending on the target application, current tools may exhibit a significant number of false positives and false negatives. These tools are designed to provide the request aimed at revealing the possible existence of vulnerabilities. They are not designed to automatically provide the specific requests allowing the exploitation of the identified vulnerabilities.

Clearly there is still room for improving the capabilities of web scanners. The research summarized in this paper is aimed at contributing to fulfilling this goal. The first step in our approach to achieve this objective consists in: i) analyzing the main principles behind the vulnerability detection algorithms implemented in recently developed open-source web scanners (such as Skipfish, W3af, and Wapiti) and then ii) identifying possible rooms for improving the detection ability of these algorithms to address some of the limitations. Such analysis cannot be based on commercial or other tools for which the source code is not available. In the second step, we developed a new algorithm allowing the automated detection of different types of web vulnerabilities including SQL injections, OS commanding, File Include, XPath, etc. The proposed algorithm builds on some of the concepts inherited from existing tools and includes significant extensions. It is based on the automatic classification of the responses returned by the web servers using data clustering techniques and provides specially crafted inputs that should lead to successful attacks when vulnerabilities are present. The automatic generation of requests allowing the successful exploitation of detected vulnerabilities should be useful to facilitate web applications validation and penetration testing. In order to assess our algorithm, we have run two sets of experiments. In the first experiments, we have injected specific vulnerabilities in five open-source applications and analyzed the detection ability of the new algorithm compared to the algorithms used by Skipfish, W3af and Wapiti. In the second set of experiments, we have considered five other vulnerable applications without modifying them. These experiments allowed us to illustrate the potential benefits of our proposed algorithm.

The paper is structured into 8 sections. Section II briefly describes the principle of vulnerability scanners. Section III discusses related work focussing on the analysis of the vulnerability detection algorithm used by several well-known freeware vulnerability scanners and shows some weaknesses of these tools that we aimed to address by proposing a new algorithm. Section IV presents our clustering algorithm for detecting web application vulnerabilities. The principle of this algorithm is presented as well as examples for SQL injections. The application of this algorithm to other vulnerabilities is discussed in Section V. Section VI briefly presents the scanner we developed to implement this algorithm, called WASAPY. We describe in Section VII the experiments performed in order to validate our approach and assess the efficiency of our scanner. Finally Section VIII concludes this paper and discusses future work.

II. VULNERABILITY SCANNERS PRINCIPLES

Most frequent attacks on web servers include SQL injection attacks (for web servers connected to an SQL database) and code injection attacks (Flash, Javascript, etc., carried out through so-called Cross Site Scripting or XSS attacks). These attacks generally correspond to the exploitation of the same kind of vulnerability related to the lack of sanitization of URL parameters or of HTML form inputs. In the following, we will focus on SQL injection attacks.

To check whether SQL injection attacks are possible, the vulnerability scanners send specially crafted requests and analyze the responses returned by the server. A server may respond with a rejection page or with an execution page. A rejection page corresponds to the detection of syntactically incorrect or invalid inputs. An execution page is returned by the server as a consequence of a successful execution of the request. This page may correspond to the "normal" scenario, i.e., in the case of a legitimate use of the web site, but may also result from a successful exploitation of an injection attack. These latter requests are those we consider in this paper, as our objective is to identify the vulnerabilities that can be successfully exploited by the attackers. For instance, the successful exploitation of a vulnerability in a login form may lead to bypass an authentication, and the successful exploitation of a vulnerability on a search form may lead to display extra data like /etc/passwd file content. In order to identify the vulnerabilities of a web site, the scanners generally send specially crafted requests via the identified injection points allowing them to determine whether the input parameters submitted to the target system are sanitized or not. The identification of potential vulnerabilities is generally based on the identification of the rejection pages.

The issue is thus the analysis of the responses to determine if they actually correspond to rejection or execution pages. Two main approaches can be identified based on the analysis of related work on this topic. These approaches are discussed in the next section. In the following, we denote as false positive the fact that a vulnerability scanner detects a vulnerability in a web page while this vulnerability does not exist. A false negative occurs when the vulnerability scanner does not detect a vulnerability in a web page while it actually exists.

III. RELATED WORK

Two main approaches exist to detect the presence of a vulnerability in a web application. The first one relies on an error pattern matching algorithm and is presented in section III-A. The second one relies on the analysis of similarities between the pages returned by the server and is presented in section III-B. The last section III-C proposes a discussion regarding the limits of these approaches.

A. Error pattern matching approach

To identify SQL injections, this approach consists in sending crafted requests to the application and looking for specific patterns in the responses: database error messages. The basic idea is that the presence of an SQL error message in a HTML response page means that the corresponding request has not been sanitized by the application. Therefore, the fact that this request has been sent unchanged to the SQL server reveals the presence of a vulnerability. Scanners such as W3af1 (sqli module), Wapiti2 and Secubat [START_REF] Stefan | SecuBat: a web vulnerability scanner[END_REF] adopt such approach. As an example, to detect injection vulnerabilities in authentication forms, the sqli module of W3af, sends three requests based on the SQL injection: d'z"0 (or d%2Cz%220 encoded in ASCII). The three corresponding responses are then analyzed. If they include SQL error messages (e.g. Mysql_ and supplied argument is not a valid Mysql), W3af informs the user that the application is vulnerable.

The list of keywords adopted by Secubat for the error pattern matching approach is presented in [START_REF] Stefan | SecuBat: a web vulnerability scanner[END_REF]. This list, derived by analyzing reponse pages of vulnerable web sites, is aimed to cover a wide range of error reponses and a variety of database servers. A confidence factor that measures the level of confidence that the attacked web form is vulnerable is also assigned to each keyword.

B. Similarity approach

This approach relies on three assumptions: 1) execution and rejection pages are different, 2) it is easy to build requests that generate rejection pages (by generating random or syntactically incorrect requests for instance) and 3) it is difficult to build requests including injection attacks that actually generate execution pages (i.e., requests that successfully exploit a vulnerability). The principle of the approach consists in sending different crafted requests to the web application and comparing the similarity of the corresponding responses using a textual distance, in order to identify execution pages among the response pages (i.e., pages that correspond to the successful execution of an injection attack).

Let us consider as an example the approach adopted by Skipfish3 for detecting SQL injection vulnerabilities. It sends three requests to the web application (A-'", B-\'\" and C-\\'\\"). The responses are compared two by two. According to Skipfish, a vulnerability is present if both responses associated to B and C are not similar to the response associated to A. The similarity test uses a distance based on the frequency of the words in the response pages.

The algorithm presented in [START_REF] Huang | Web Application security assessment by fault injection and behavioral monitoring[END_REF] is also based on the similarity approach. It differs from other implementations in the additional use of the error pattern matching approach at a first step to guide the classification. The similarity approach is used to address the uncertainty that arises about the presence or absence of a vulnerability when an injection does not generate an error message.

Another example illustrating the use of the similarity approach in another context is the formAuthBrute module of W3af, that deals with weak passwords identification. This module first sends two requests including randomly generated usernames and passwords. The responses likely correspond to rejection pages. They are used as reference pages. Then, the dictionary attack is carried out in the second step. A large number of requests is generated based on a dictionary. Each response is compared to the reference pages, using the Levenshtein distance [START_REF] Levenshtein | Leveinshtein distance[END_REF]. The response is assumed to correspond to an execution page if the distances between this page and reference pages are higher than 0.65. Otherwise, this page is considered as a rejection page. The threshold value 0.65 is empirically configured by the developer.

C. Discussion

The assumption used by the error pattern matching approach is questionable. Indeed, error messages that are included in HTML response pages do not necessarily come from the database server itself. A database related error message may also has been generated by the application. Moreover, even if the message is actually generated by the database server, this is not sufficient to affirm when receiving this message, that an SQL injection is possible. Indeed, this message means that, for this particular request, the inputs have not been sanitized. But it does not mean that the SQL server does not sanitize all the SQL requests.

Regarding the similarity approach, it is more easy to generate random or syntactically incorrect requests to obtain rejection pages than to send valid injection attacks to obtain execution pages. Since the main assumption is based on the observation that the content of a rejection page is generally different from the content of an execution page, it is important to ensure a wide coverage of the different types of rejection pages that could be generated by the application. This can be achieved by generating a large number of requests aimed at activating different types of error pages. However, the existing implementations of this approach, especially in Skipfish, generate too few requests. Skipfish uses only 3 requests. But, if the responses correspond to different rejection pages, it will wrongly conclude that a vulnerability is present.

Also, as in any classification problem, the choice of the distance is very important. The one used in Skipfish doesn't take into account the order of the words in a text. However, this order generally defines the semantics of the page. Thus it is important to take it into account to assess the similarity, as performed in [START_REF] Huang | Web Application security assessment by fault injection and behavioral monitoring[END_REF] with a text similarity distance. As an example, the two following pages use the same words in a different order, but they have a different semantics:

The algorithm presented in Section IV builds on some of the concepts of the similarity approach and is aimed at addressing the issues raised in the discussion above. In particular, it allows: i) the generation of a large number of requests, that can be tuned by the user, to activate different rejection pages returned by the application, ii) the automatic generation of various types of specially crafted requests using a grammar and iii) the automatic clustering of the corresponding HTML pages returned by the web server to distinguish between rejection pages and execution pages and automatically identify successful injections. This algorithm is also designed to identify and successfully exploit various types of vulnerabilities. Besides SQL injections, the proposed approach can address XPATH, OS Commanding and File Include vulnerabilities. Regarding related work, while our work shares some of the ideas and objectives presented in [START_REF] Huang | Web Application security assessment by fault injection and behavioral monitoring[END_REF], we follow different approaches. For example, the clustering approach which is the core of our algorithm is not used in [START_REF] Huang | Web Application security assessment by fault injection and behavioral monitoring[END_REF]. They use a different technique combining error pattern matching and the similarity analysis of application response pages. Also, their approach is firstly based on error pattern matching and hence shares the same concerns raised above.

IV. THE PROPOSED ALGORITHM

Let us first define the notion of injection point, which is used by our algorithm. An injection point is a piece of a Web page into which a code can be injected: a parameter in the URL or a field of a form, etc. In the following, we consider an authentication form for the sake of illustration and we focus on SQL injections. In subsection IV-A, we present the clustering algorithm used to classify pages. In subsection IV-B, we discuss the distance used to parameterize the algorithm. Finally, we explain in subsection IV-C how we generate the requests sent to the web server.

A. Pages clustering

Our goal is to identify, among several SQL injections, those which allow an attacker to bypass the authentication. The main challenge lies in the automation of this process. Our approach relies on the following assumptions: a) the content of an execution page is far different from the content of a rejection page, b) two rejection pages may be different from each other and c) two execution pages may also be different from each other. For example, let us consider a login page. Responses to valid requests include welcome messages and responses to invalid requests include PHP or SQL error messages. The essential point is the existence of differences between execution pages and rejection pages.

Our approach focuses on the analysis of these differences. The objective is to identify, among several responses, those which correspond to execution pages. In other words, we learn the behavior of the application based on the clustering of web server response pages that are similar enough. The entry point of our algorithm is a set of initial requests that have a common property: it is easy to classify the associated responses (either execution page or rejection page). Obviously, it is easier to generate requests, which generate rejection pages than requests that generate execution pages. To generate rejection pages, we can, for example, use random usernames and passwords to fill the authentication form. We can also easily generate requests which correspond to malformed SQL injections that would lead to error messages.

In our proposal, we distinguish three sets of requests: R r is the set of requests generated from words randomly chosen from the list [a-zA-Z0-9]+. The main issue is to determine whether the response is a rejection page or an execution page. To do so, these responses are compared to those associated to sets R r and R ii .

We note S r , S ii and S vi the responses associated to R r , R ii and R vi respectively. The principle of our algorithm is then as

diff(ai, bj) =      n -i + m -j i = n or j = m diff(ai+1, bj+1) ai = bj, i < n, j < m 1 + min(diff(ai+1, bj), diff(ai, bj+1)) ai = bj, i < n, j < m d(a, b) = diff(a1, b1) (n + m)

B. Distance for response pages similarity assessment

As discussed in Section III-C, it is important to take into account the position of the words in a text when analyzing the similarity between two pages. Thus, to compute the distance between two pages, we use the normalized difference, based on a slightly modified version of the Unix diff operator [START_REF] Hunt | An Algorithm for Differential File Comparison[END_REF]. Let a and b be two responses of length n and m. We also denote a i and b j the i-th character in a and the j-th character in b. The distance is defined in Figure 1.

A threshold is required to determine whether two responses are similar or not. This threshold may vary from one injection point to another. Indeed, it depends on the size of responses and the amount of data that changes between two responses. In our algorithm, the threshold is defined empirically by the shortest distance between: i) the maximum distance between the responses belonging to S r and ii) the maximum distance between the responses belonging to S ii . Using this threshold, we are able to identify clusters of similar responses. For that purpose, we use the hierarchical clustering technique [START_REF] Johnson | Hierarchical Clustering Schemes[END_REF].

Using this classification, we are able to identify the type of requests. Note that a request is associated to a response and vice versa. So, in order to identify the type of requests, it is enough to identify the types of corresponding responses. This identification concerns responses in S vi . Indeed, this is the only set containing responses with type not yet defined. The following rule is used:

1) A request, for which the response belongs to a cluster that also contains responses of S r or S ii , is an invalid SQL injection; otherwise the request corresponds to a valid SQL injection. An illustrative example is presented in Figure 2. In this example, the third cluster contains only requests from R vi : these correspond to valid SQL injections. The first cluster contains both requests from R r and R vi . However, this cluster is not the only one associated with requests that generate rejection pages: there are different error messages for this example. Other tools (like Skipfish) may consider that a response included in the second cluster corresponds to a valid SQL injection simply because it is far from the reference

C. Requests generator

One important aspect of the proposed algorithm is its ability to identify the presence of a vulnerability in an injection point based on multiple responses generated from this injection point. To improve the accuracy of the results, we need to generate a large number of responses, allowing to achieve a high coverage of the response domain. Let us note that other approaches are often based on a small number of responses (for example, 3 for Skipfish).

One possible way to generate a significant number of responses (and associated queries) is to record in a static file, queries obtained from security experts (similar e.g., to SQL sheets [START_REF] Kiezun | Automatic creation of SQL Injection and cross-site scripting attacks[END_REF]). A more flexible approach would be to define a grammar to automate this process. Such approach can be compared to some extent to fuzzing techniques [START_REF] Gutesman | gFuzz: An Instrumented Web Application Fuzzing Environment[END_REF]. In the following, we outline the grammar that we have defined to automate the generation of R r , R ii and R vi requests.

On the Web server side, most of the time, a SQL query is forged by concatenating SQL terms and parameters sent by the client. For example, the following PHP script deals with the authentication of a user given the username and password sent by the client: $query = "SELECT id FROM users WHERE name='$name' AND pass='$pass'";

Given a correct (username, password) couple, the forged SQL query is considered syntactically correct. Also, the forged query associated to a (username, password) couple generated based on a dictionary attack is considered syntactically correct, even if the authentication failed. From this observation, an SQL injection is defined as a string that may change the semantics of the generated SQL query. In many situations, a SQL injection is interesting if it leads to a tautology in the WHERE clause of the forged SQL query. In the previous example, such a SQL injection is: name="' OR 1=1 OR string='" Therefore, the grammar of SQL injections is just a part of the grammar of SQL queries. The advantage of a grammar is that it enables to easily generate as many SQL injections as needed. We can apply the same reasoning to the set of randomly generated words (R r ), and to the set of SQL injections that are inappropriate for the given injection point (R ii ). A tiny grammar for the set R vi (i.e. the set of SQL injection requests that are constructed in order to generate execution pages) can be expressed using BNF 4 This grammar generates different variations of SQL injection attacks whose principle consists in inserting a tautology inside an expression evaluated by a WHERE clause, in such a way that this expression becomes a tautology itself. To inject the tautology, the initial expression is splitted into several pieces. The TAUTAG rules are examples of such tautologies and the INJECTION rules express how the tautology is included in an initial expression, i) by closing the expression with delimiter characters (', ", or )), ii) by inserting the tautology (through a disjonction) and iii) by opening a new expression using the same delimiter characters.

V. EXTENSION TO OTHER VULNERABILITIES

The SQL injection vulnerability detection principle can be generalized. Indeed, many attacks adopt the same behavior: the client sends a string which changes the semantics of the forged query. According to the context, the forged query is sent to a specific web server side component such as the XPATH engine, the OS, etc. The name of the corresponding injection attacks are derived from the name of this component leading to the so-called XPATH injection, OS Commanding, etc. Thus, the clustering algorithm that we have illustrated through SQL injection examples in the previous section can also be used for other kinds of vulnerabilities.

The adaptation of our algorithm to other kinds of vulnerabilities only requires the definition of the three sets of requests R r , R ii and R vi for each kind of vulnerability. Once these sets are established, the algorithm is always the same: sending these requests, storing the corresponding results and obtaining clusters using the distance presented in the previous section. Due to space limits, we briefly present in the following an example that illustrates how our algorithm can be applied for the detection of OS Commanding vulnerabilities. Examples corresponding to XPATH and File Include vulnerabilities are presented in [START_REF] Dessiatnikoff | HTML pages clustering algorithm for web security scanners[END_REF].

In the case of OS commanding vulnerability, the string sent by the client is used to create a command propagated to the OS. This command is then executed by the OS with the privilege of the web server process. The exploitation of this vulnerability allows an attacker to execute arbitrary commands and, for example, to make read or write accesses on the file system. An example of a vulnerable PHP web page on the server side is as follows: <?php system("cat ".$_GET['cmd']); ?> This code executes the cat command with arguments extracted from the cmd parameter. As this parameter is not sanitized, the code is vulnerable.

Syntactically invalid and valid requests may respectively look like: R ii : .;. LeSS /OFr/BxEBHM . cAt /sCs/wJjqCg R vi : | more /././etc/././passwd

The first request contains invalid Unix commands and is constructed to be invalid. The second one contains a valid pipe towards a command that is supposed to display the content of the /etc/passwd file.

VI. IMPLEMENTATION

Figure 3 presents a high-level view of the tool that we have developed to implement the proposed algorithm following an iterative approach. When the user runs the tool, he provides the initial URL. Most of the time, it corresponds to the main page of the application (index.html). Then, the crawling of the application begins, starting from this initial injection point. This crawling identifies all potentially vulnerable injection points. This first stage ends when all accessible injection points have been reached. The second stage begins at this moment. It corresponds to the execution of our clustering algorithm on each injection point, considering the different vulnerabilities presented in the previous section. This second stage may lead to the identification and exploitation of a vulnerability. If so, we obtain a new injection point which was not accessible in the first stage. Consequently, it is possible that a new area of the application becomes accessible from now. Hence, the tool then starts again the first stage using the newly discovered injection point. Figure 3 presents these two stages.

The tool was developed using Python language. The Python libraries make easy the management of HTTP concepts (cookies, parameters, etc.). Our tool is linked to the statistical analysis tool, R. The base installation of R gives a set of packages useful to achieve hierarchical clustering. They have been used to develop our clustering algorithm. The crawler is developed by ourselves in order to easily integrate it with the vulnerability exploitation part of our algorithm. Our tool is named Wasapy. Wasapy stands for Web Application Security Assessment in PYthon.

VII. EXPERIMENTAL RESULTS AND DISCUSSION

This section presents the experiments that we have carried out to validate and assess our algorithm. We have considered several applications using Wasapy and the three opensource vulnerability scanners discussed in this paper: W3af 1.1, Skipfish 1.9.6b and Wapiti 2.2.1. The experiments are run on a Gnu/Linux (2.6 kernel) host running several virtual machines thanks to the VirtualBox utility. All the virtual machines run the Apache web server 1.3.37 or 2.2.8 with PHP 4.0.0 or 5.0.0 and MySQL database server 5.

This section is organised as follows. Subsection VII-A presents notations and abbreviations. Subsection VII-B presents the first experiments realized in order to assess our approach. Five web applications including SQL vulnerabilities are used. We purposely injected these vulnerabilities to calibrate Wasapy. Subsection VII-C the second set of experiments with vulnerable off-the-shelf applications, without any modification of these applications. This subsection compares Wasapy to other vulnerability scanners on non-purposely injected vulnerabilities. For some of these applications, evaluation reports based on commercial scanners are available in [23]. We reported some of these results in order to compare these scanners with Wasapy. Subsection VII-D presents the summary of all these experiments.

A. Notations

The results of our experiments are presented in different tables. We use following notations and abbreviations:

The vulnerability has been detected by the corresponding scanner The vulnerability has not been detected by the corresponding scanner -The injection point is not tested by the scanner SQLi stands for SQL Injection XPa stands for XPath Injection OsC stands for OS Commanding FIn stands for File Include CVE reports the CVE reference of the considered vulnerability if it exists NR The vulnerability does not have a CVE A vulnerability is considered as detected if the scanner actually sends an alert for this vulnerability, whatever the method used to detect it. A vulnerability is considered as not detected if the scanner actually tested the corresponding injection point without sending any alert. A vulnerability is considered as ignored by the scanner if the corresponding injection point is not tested by the scanner.

B. Experiments with modified applications

The five applications chosen for this first set of experiments are described hereafter:

• phpBB-3: This application5 is a forum manager written in PHP and using a MySQL database. We modified the authentication form of the application so that it includes a vulnerability (v1) that can be exploited by a SQL injection. This vulnerability allows an attacker to reach the restricted administration area of the forum.

• SecurePage: This application 6 written in PHP, is designed to protect the access of a web site through authentication. Valid couples for this authentication are stored in a MySQL database. A vulnerability (v2) was purposely injected, it is similar to v1.

• HardwareStore: We developed this application, in PHP 5.0. This application allows a user to inventory computer equipments in a database and to interrogate this database. The user needs first to be authenticated. Five SQL vulnerabilities were purposely injected in this application. v3 allows SQL injection in a search form, and allows an attacker to access the whole database. v4 allows SQL injection in the authentication form. v5 allows SQL injection in a parameter of a HTML request. For this vulnerable HTML page, we have purposely disabled the error message reporting, in order to compare the behavior of W3af and Wapiti in such a situation with the behavior of Wasapy. Vulnerability v6 is similar to v4 but it is used in a different context: the error message reporting is deactivated. Vulnerability v7 can only be exploited after the successful exploitation of v4. Indeed, this vulnerability is included in a page that can only be accessed after successful authentication on the application or after a successful bypass of the authentication mechanism (through exploitation of v4). XPATH, OS Commanding and File Include vulnerabilities were also injected in this application. Vulnerability v10, in the authentication page, allows an attacker to bypass the authentication through a XPATH injection. v11 is an Os Commanding vulnerability that can be exploited only after v4 is successfully exploited. Indeed, this vulnerability is included in a page that is only accessible after authentication (or bypass of the authentication through successful exploitation of v4). Vulnerability v12 is a File Include vulnerability, it is included in the same page as v11 and can be exploited in the same conditions as v11.

• Insecure: This application was developed in Ruby on Rails in the context of the Dali project 7 . It is an ecommerce site, including user sessions through virtual shopping carts. A vulnerability (v8), which allows an attacker to inject SQL code, was purposely included in the authentication form of the application. This vulnerability, functionally equivalent to v4 is anyway different because Insecure is implemented in Ruby and the error reporting messages differ from the Apache error reporting messages.

• Damn Vulnerable Web Application (DVWA): This application 8 is written in PHP and uses MySQL server. A vulnerability v9, similar to v3, was purposely introduced in the application. Figure 4 shows that the performances of W3af and Wapiti are similar in average, even if the vulnerabilities detected are not the same (Wapiti successfully detects v1 and v2 whereas W3af does not detect them; on the other hand, W3af detects v4 and v8 whereas Wapiti does not detect them). This result is consistent with the fact that both scanners use a pattern matching-based algorithm. The observed variations are related to the generation of different requests by these tools. Wasapy allows us to detect all these vulnerabilities. This confirms that the vulnerability detection clustering algorithm presents a better coverage than the pattern matching algorithm for these vulnerability classes.

Regarding vulnerabilities v1 and v2, we manually checked the injections performed by Skipfish ('", \'\" and \\'\\") and stored the corresponding responses (respectively A, B et C). As discussed in Section III, Skipfish considers that the pages A and C must be different so that a vulnerability is present. Unfortunately, for these two injection points, this is not the case. The responses correspond to SQL error messages that are very similar.

Regarding vulnerabilities v5 and v6, they are included in PHP pages for which we purposely deactivated the error reporting message feature 9 in the configuration file of PHP5. In this particular case, none of the three scanners (Skipfish, W3af and Wapiti) is able to detect vulnerabilities.

Regarding vulnerability v7, Wasapy is the only scanner that is able to detect it. Moreover, it is the only scanner that is able to test the corresponding injection point. Indeed, this injection point is included in a HTML page that can only be accessed after a successful authentication or after the successful exploitation of vulnerability v4. As Wasapy is the only scanner able to actually exploit v4, it can automatically access the page including vulnerability v7. For the other scanners, it is necessary to manually perform the exploitation of v4 so that it is possible to access the page including v7. Vulnerabilities v11 and v12 were identified only by our tool for the same reasons: they remain masked until the authentication is bypassed.

The purpose of these initial tests was the calibration of Wasapy. The calibration of our tool consists in defining empirically the number of requests to generate for each group and injection point. We set this number to 30 for all the applications tested (i.e., 90 requests per injection point). We have observed that a higher number does not provide significantly higher accuracy, while a lower number generates false negatives.

These initial tests also allowed us to check the grammars that we presented in the previous section. Of course, the corresponding vulnerabilities have been identified for this purpose. So, these results are not aimed to be used to make an absolute comparison between the scanners. A more representative comparative assessment of the different tools should be based on vulnerable applications in which vulnerabilities have not been deliberately injected by ourselves. These experiments are presented in the next subsection.

C. Experiments with non-modified vulnerable applications

This second set of experiments allowed us to have a more precise idea of the coverage of our detection algorithm. For that purpose, we compared it to the detection algorithms of Skipfish, W3af and Wapiti on not purposely modified vulnerable web applications. For some of these applications, 9 The configuration file of PHP5 includes: For production web sites, you're strongly encouraged to turn this feature off, and use error logging instead. we could compare our algorithm with some commercial vulnerability scanners, considering the results available in [23]. In this document, the author presents the vulnerability detection results obtained with three commercial scanners: WebInspect from HP, AppScan from IBM and Web Vulnerability Scanner from Acunetix. These results provide only some preliminary indications to analyse the performance of our tool on the same set of applications and are not meant to be used for a validation purpose.

Skipfish

For our experiments, we selected five web applications (most of them tested in [23]), known to include vulnerabilities. These applications cover different functionalities and execution contexts. We installed these applications, and performed vulnerability detection tests without modifying them.

• Cyphor10 is a configuration Webforum, which uses PHP 4.0.0 session capabilities to authenticate users and a MySQL database.

• Seagull11 is an OOP framework for building web, command line and GUI applications. This project allows PHP developers to integrate and manage code resources, and build complex applications. This application requires the following configuration: PHP 4. the scanners found all the vulnerabilities because error messages are reported to the client. Thus, it is easy to distinguish successful vulnerability exploitation from error messages. The underlined results correspond to detections made possible by supplying a valid (login/password) to the scanners to perform authentication. In other words, the corresponding vulnerability is only visible when logged in the site (the authentication page does not contain any SQL-injection vulnerability, it is the only way for any scanner to access the page including the vulnerability).

The results reported for Seagull in Figure 6 show that Wasapy is the only one that reports a vulnerability in this application. Others are unable to do so because the application does not report errors to the client. Regarding File Include vulnerabilities, the injection points which allow their exploitation are not directly visible by the client. Hence, the source code is necessary to identify these vulnerabilities. This explains the failure of all scanners.

Fttss is an application that has been tested in [23]. Hence, some results associated to the three commercial scanners considered are available (cf. Figure 7). The commercial scanners do not detect the OS commanding vulnerability, which is the only vulnerability known of this application. In contrast, W3af and Wasapy are able to identify this vulnerability. It is noteworthy that none of tested scanners reports false positives in this case.

Regarding Riotpix (cf. figure 8), the results are similar to those of Cyphor. The vulnerabilities are only accessible to successfully authenticated users. Therefore we had to provide a valid login/password to all scanners. Two vulnerabilities have not been found by any scanner. They correspond to code injection into variables that are not visible to the client and thus cannot be discovered by scanners (their identification would require a source code analysis). These results also show that Wasapy is efficient for this kind of vulnerability.

Regarding the Pligg application (cf. figure 9), all vulner- abilities but the first two are available on hidden injection points. The scanner must be aware of the presence of the injection point in order to test the vulnerability. For the first two vulnerabilities, Wasapy found them, whereas the other scanners found only one of these vulnerabilities. This is due to the fact that error messages are not forwarded to the client.

D. Summary

The main lessons learned form all our experiments are summarized in the following:

• Wasapy is an efficient scanner, especially in particular conditions for which it has been designed : 1) it is more efficient than the other freeware scanners tested when the error reporting is disabled, 2) it is more efficient than the other scanners to discover and exploit vulnerabilities that are included in pages not directly accessible (pages that require the successful exploitation of a vulnerability to be accessed). Indeed, our scanner is the only one which is capable of actually exploiting the vulnerability, and supplying the exact corresponding injection requests.

• Wasapy is globally as efficient as the other vulnerability scanners tested on not modified vulnerable applications.

• Our clustering algorithm can be easily adapted to different kinds of vulnerabilities. Besides SQL injections, the results of the experiments show that Wasapy also detects XPATH, OS Commanding and File Include vulnerabilities and that it is at least as efficient as the other vulnerability scanners.

VIII. CONCLUSION

In this paper, we presented a vulnerability scanner that implements a new algorithm aimed at detecting web applications vulnerabilities, following a black-box approach. Our algorithm is based on the automatic generation of specially crafted inputs allowing the successful exploitation of detected vulnerabilities, using data clustering techniques and language theory. We used a large set of applications with and without deliberately injecting vulnerabilities into them in order to validate our approach and analyse its effectiveness compared to three other open source web scanners. The experimental results are promising. In particular, we have shown that our algorithm can contribute to improve the detection capabilities of some existing tools and to pushes one step forward the automation of the vulnerability detection process (by allowing for instance the successful detection of vulnerabilities in pages that are not directly accessible but only accessible after the successful exploitation of a first vulnerability).

In this paper we focussed on SQL injection vulnerabilities. Nevertheless, we have also shown that the proposed algorithm can be successfully applied to other vulnerability types. A more extensive validation case is needed to confirm the promising results obtained so far. The proposed algorithm has been implemented in a new tool Wasapy. This algorithm can also be integrated in the open source tools that we have investigated (such as W3aF and Skipfish to take advantage of the other powerful facilities offered by these tools.

Overall, the experimental results presented in the paper also highlight the usefulness of combining different kinds of vulnerability scanners at the same time to enhance the vulnerability detection capabilities of current scanners. A first kind can be represented by W3aF which performs pattern matching on web responses and the second kind can be represented by our scanner which uses a different approach. Such an architecture leads to the problem of correlation of the results provided by diverse tools. It will be interesting to perform a new evaluation considering scanners working together with an overall detection correlation mechanism. The corresponding results may contribute to propose an efficient method to wisely combine different scanners.

Fig. 1 .

 1 Fig. 1. Distance for clustering

Fig. 2 .

 2 Fig. 2. Example of classification

  TAUTAG [' POR TAUTAG] | WORD" POR TAUTAG [" POR TAUTAG] POR := ' or ' / ')' POR '(' TAUTAG := hex('A')='41 | '1'='1 | '[f-m]' between '[a-e]' and '[n-z]' WORD := [0-9a-zA-A]* ...

Fig. 3 .

 3 Fig. 3. Principle of the algorithm

  R vi is the set of SQL injection requests that are constructed to generate execution pages in the presence of vulnerabilities, but they might as well generate rejection pages in the absence of vulnerabilities. For example:

	http://address/directory/page.php?
	login=test&pass=' or '1'='1

They are very likely to generate rejection pages. For example: http://address/directory/page.php? login=ABCDEF&pass=ABCDEF R ii is the set of SQL injection requests inappropriate for the given injection point. They are constructed to produce a syntax error in the SQL query sent to the SQL server by the HTTP server. Usually, these requests are composed of an odd number of quotes. They are also very likely to generate rejection pages. For example: http://address/directory/page.php? login='''&pass='''

http://w3af.sourceforge.net

http://wapiti.sourceforge.net

http://code.google.com/p/skipfish

-You are authenticated, you have not entered a wrong login. -You are not authenticated, you have entered a wrong login.

BNF stands for Backus Normal Form. It is a notation for grammar writing.

http://www.phpbb.com

http://www.01php.com/fiche-scripts-126.html

ANR's program ARPEGE(2009-2011).

http://www.dvwa.co.uk

http://webscripts.softpedia.com/script/Snippets/Cyphor-27985.html

http://seagullproject.org/

http://fttss.sourceforge.net

http://www.riotpix.com/

http://www.pligg.com/


Mohamed Kaâniche
email: kaaniche@laas.fr

Karama Kanoun
email: kanoun@laas.fr

Mourad Rabah
email: mrabah@univ-lr.fr

Multi-Level Modeling Approach for the Availability Assessment of e-Business Applications *

Keywords: e-business, Internet, dependability, availability, hierarchical modeling

This paper defines a multi-level modeling approach for availability assessment of e-business applications, based on two main steps: 1) hierarchical description of the system and its interactions with the users, from the functional and structural points of view, and 2) hierarchical construction and solution of the availability models based on information from the first step. Four modeling abstraction levels are considered. The highest level (user level) describes the availability of the e-business application as perceived by the users. Intermediate levels describe the availability of functions and services provided to the users. The lowest level describes the availability of the component systems on which functions and services are implemented. The availability measures of a given level are computed based on the measures provided by the immediately lower level.

Introduction

The explosive growth of Internet users has caused a dramatic increase in electronic markets with several categories of business [START_REF] Bakos | The Emerging Role of Electronic Marketplaces on the Internet[END_REF][START_REF] Maes | Agents That Buy and Sell[END_REF][START_REF] Shim | Business-to-Business E-Commerce Frameworks[END_REF]: business-to-business, business-to-customer, customer-tocustomer, etc. In this context, the services provided to the users result from the cooperation of several systems that are interconnected and widely distributed over the Internet. Given the critical nature of many such systems, the assessment of the quality of service as perceived by the users is a key issue for e-business service providers (eBP). Dependability and performance related measures provide useful indicators for the designers to assess the impact of component failures (software, hardware, communication links and protocols) on the quality of service provided to the users. It is important to estimate such measures early in the design process to assist the designers in making objective architectural decisions. Indeed, by comparing several architectural solutions, they can identify potential areas of improvement of the eBP infrastructure to better fulfill user expectations.

Little support is provided today for modeling and evaluating the dependability of largely distributed applications from the user perspective. The objective of this paper is to present a multi-level modeling approach for evaluating the availability of e-business applications (eBAs). Although this paper focuses on availability, the proposed framework should also allow the evaluation of other dependability and performability measures.

Our main challenge is to avoid as far as possible the construction of complex models that are difficult to process and analyze. Largeness is avoided by using hierarchical model composition and refinement techniques. Modeling is carried out in two main steps: the first step consists in describing the target eBA (from the functional and structural point of view) and its interactions with the user, according to four levels: user, function, service and resource. The second step is devoted to the hierarchical construction and solution of the eBA availability model based on the information provided at the first step. According to this scheme, the highest level (user level) describes the availability of the eBA as perceived by the users. Intermediate levels describe the availability of functions and services provided by the eBP. Finally, the lowest level describes the availability of the component systems on which the e-business functions and services are implemented. The availability measures characterizing a given level are computed based on the availability measures provided by the immediately lower level.

This paper elaborates on previous work reported in [START_REF] Kaâniche | A Framework for modeling the Availability of e-Business Systems[END_REF]. It is organized as follows. The second Section describes the work context and the main key players involved in the provision of the services delivered by an eBA. The third and fourth Sections present the multi-level modeling framework that we propose for availability evaluation from the user perspective. The fifth Section gives more insights into the low level models. The sixth Section presents some related work and the seventh Section concludes the paper.

Problem Statement

eBAs are generally based on a complex distributed infrastructure, with multiple interconnected layers of software and hardware components. Three key players are typically involved in the provision of the services delivered by such applications (see Fig. 1):

• The users, (i.e., the customers) who interact with the eBP site(s) to invoke a set of e-business functions.

• The e-business service provider (eBP), who implements the e-business functions that can be invoked by the users; these functions are based on a set of services and resources that are internal to the eBP site(s) or are provided by external suppliers.

• The external suppliers, who contribute to the implementation of some of the functions and services delivered by the eBP to its users. Every transaction initiated by a user is processed in several steps. In particular, it starts in the user's applications, flows through the Internet, executes through the business applications of the provider, and generally through the applications of external suppliers. For example, an eBP can offer a book selling electronic service by outsourcing shipping, payment, and billing to other service providers (external suppliers). At the provider level, the user requests and the interactions with the external suppliers are supported by a set of complex distributed applications and middleware such as Web servers, application servers and database servers. Also, similar infrastructures are used at the external supplier sites.

To model the availability of eBAs as perceived by the users, it is necessary to identify the main functions and services provided to the users and the main resources contributing to their accomplishment. Based on this, one can build a model to assess the impact of component failures and repairs on the quality of service delivered to the users.

Users generally exhibit different behaviors and therefore may invoke the various e-business functions in different ways and with different frequencies. Considering a travel agency, the various classes of users (i.e., managers, tour operators, sellers, customers, etc.) have different aims and hence solicit differently the system. In addition, within the same class of users, the behavior may be unlike.

For example, some customers may be heavy buyers while others may do extensive searching and browsing but very seldom buy from the provider site(s). Thus, the types of functions invoked and the resources involved in the accomplishment of these functions are not necessarily the same. As a consequence, the availability of the eBA may be perceived differently by these classes of users. Indeed, the user perceived availability is influenced by the user operational profile (i.e., workload) and the state of the components involved in the accomplishment of the functions invoked by the user. The latter may be influenced by several factors including network related failures, hardware or software component failures affecting the architecture of the provider or external suppliers.

Generally, the eBP has a full control of its own architecture. Hence, a detailed availability modeling and analysis of this architecture can be carried out to support design architectural decisions. Fig. 2 presents a typical multi-tiered architecture used in large eBP sites, composed of a load balancer and a set of interconnected web servers, application servers and database servers. Several variants of this architecture can be modeled and compared with respect to the availability objectives to be fulfilled.

Information characterizing the failures and repairs of each architecture component can be obtained and incorporated into these models. However, only limited information is generally available to analyze the availability of the services provided by the external suppliers. In this context, remote monitoring and measurement can be used to characterize the corresponding availability [START_REF] Kalyanakrishnan | Reliability of Internet Hosts: a Case Study from the End User's Perspective[END_REF][START_REF] Long | A Longitudinal Survey of Internet Host Reliability[END_REF][START_REF] Machiraju | E-services Management Requirements[END_REF]. There are several commercial products available today that service providers can use to carry out these measurements. The data provided by these measurements can be used to evaluate the parameters characterizing the services provided by external providers. These parameters will be used in the models to analyze and evaluate the availability as perceived by the users.

Fig. 2 -A typical multi-tiered architecture

The discussion above shows that several issues should be taken into account when modeling the availability of eBAs as perceived by their users. Due to the complexity of the target system, a systematic and pragmatic approach is needed to support the construction of availability models.

Hierarchical modeling is well suited to alleviate the problems of model specification and solution. It consists in describing the target system at different abstraction levels, with a sub-model associated to each level. The sub-models are composed hierarchically. Each sub-model incorporates parameters that result from the processing of lower level models. In this paper, we propose a framework for the hierarchical modeling of eBA availability as perceived by the users, based on two main steps: 1) hierarchical description of the eBA and its interactions with the users, from the functional and structural point of view, and 2) hierarchical construction and solution of the eBA availability model based on the information provided by the first step. These two steps are described in Sections 3 and 4, respectively.

E-Business Application Hierarchical Description

The information needed to analyze the e-business quality of service from the user perspective can be structured into four levels presented in Fig. 3. The first level describes how the users interact with the eBA, and the three remaining levels detail how the user requests are implemented.

• The user level describes the user operational profile in terms of the types of e-business functions invoked and the probability of activation of each of them.

• The function level describes the set of functions available at the provider site(s).

• The s e r v i c e l e v e l describes the main services needed to implement each function and the interactions among them. Two categories of services are distinguished: those provided by the eBP and those provided by external suppliers.

• The resource level describes the architecture on which the services identified at the service level are implemented. At this level, the architecture and the fault tolerance and maintenance strategies implemented at the provider site(s) are detailed. Indeed, the function and the service levels mainly consist in describing, according to a top-down approach, how the applicative software implementing the e-business logic is structured and decomposed, whereas the resource level describes the corresponding execution environment (executive software, communication middleware, hardware components, etc.).

Fig. 3. eBA hierarchical description

The above hierarchical description builds on some concepts proposed in [START_REF] Menascé | Scaling for E-Business: Technologies, Models, Performance, and Capacity Planning[END_REF] to evaluate the performance of eBAs. However, as our framework focuses on availability modeling and evaluation from the user perspective, we have adapted these concepts and refined them to fulfill the objectives of our study.

In the following subsections, we present each of these levels and place emphasis on how this hierarchical description will help in modeling the availability of eBAs in a hierarchical way.

User Level

This level describes the user operational profile describing all the execution scenarios performed by the user when visiting the eBP site(s). Each scenario is defined by the set of functions invoked and the probability of activation of each function in the corresponding scenario. As illustrated in Fig. 4, the user operational profile can be described as a graph with a set of nodes and transitions. A compact description of this graph is given by the matrix representation. The Start and the Exit nodes correspond to the beginning and end of a user scenario when visiting the provider site(s). Each node F i means that function F i is invoked by the user. A transition from node F i to node F j means that function F j is executed after execution of F i . The associated conditional probability is p ij . The output transitions from the start node, and the corresponding probabilities p si , specify the first function executed by the user when entering the eBP site(s). Finally, parameters p ix specify the probability of leaving the eBP site after executing function F i . Parameters p ij associated with the transitions can be estimated based on general techniques used to build operational profiles for computer systems (see e.g., [START_REF] Musa | Software Reliability Engineering[END_REF]).

Fig. 4. Users operational profile

The availability as perceived by the users can be evaluated by considering a particular scenario or by taking into account all the scenarios from the start node to the exit node. The availability measure will be affected by the probability of the corresponding scenario(s) and the availabilities of the functions involved in these scenarios. It is worth noting that different operational profiles with different probability matrices can be defined to analyze different classes of users: heavy buyers, occasionally buyers, etc.

Function Level

This level identifies the set of functions offered to the users at the eBP site(s). Table 1, extracted from [START_REF] Menascé | Scaling for E-Business: Technologies, Models, Performance, and Capacity Planning[END_REF], gives some examples of such functions. Some of these functions (e.g., Search, Login) may be found in most eBP sites, whereas others are characteristic of certain eBP sites or of specific types of eBP sites. The identification of all functions offered by the eBP site and the classification of these functions according to their criticality require a thorough analysis of the eBP specifications and the expectations of the users in terms of quality of service. Different levels of degradation of the quality of service delivered to the users can be defined based on the assessment of the impact of temporary loss or degradation of each function and the cost (e.g., loss of revenue) caused by such events. Such a classification should also take into account the impact of the loss or degradation of several functions.

Service Level

This level describes the mapping between the e-business functions and the services needed to implement them. Each function identified at the function level is decomposed and refined into a set of services implemented by various software entities (i.e., servers). Examples of servers include Web, Application, Authentication, Name, File, Database and Communication servers. Generally, the execution of one function may involve more than one server. Based on the analysis of client-server interactions, we can define a matrix specifying the mapping between the functions identified at the function level and the servers identified at the service level. [START_REF] Caswell | Using Service Models for Management of Internet Services[END_REF][START_REF] Ensel | Automated Generation of Dependency Models for Service Management[END_REF][START_REF] Rodosek | Determining the Availability of Distributed Applications[END_REF]). The graphical representation given in Fig. 5 is based on the concept of the Interaction Diagram defined in [START_REF] Menascé | Scaling for E-Business: Technologies, Models, Performance, and Capacity Planning[END_REF]. The interaction starts and ends with the client node ("Begin" and "End" nodes). Each path between a pair of client nodes identifies the set of servers involved in the interaction. numbered for the sake of clarity and each arc between two nodes i and j is labeled with the probability of occurrence of the corresponding transition (denoted q i,j ).

Fig. 5. Interaction diagram for the Browse function

The three scenarios are described as follows:

• 123: the user sends a request to the web server (node 2). The web server refuses a connection and the request fails. The user (represented by node 3) receives a reply message. This marks the end of this interaction.

• 12456: the web server accepts the request from the user and sends it to the application server (node 4) that returns a dynamically generated page to the web server that replies to the user (node 6). The database is not involved in this case.

• 12478910: the application server requires some specific data items, it will send a request to a database server (node 7). After the database server has answered the application server, the latter will generate an HTML page for the web server, which is then forwarded to the user.

All paths in the interaction diagram, from a "Begin" to an "End" node, should be accounted for in the evaluation of the availability of the corresponding function.

Resource level

This level describes the mapping between the services defined at the server level and the resources involved in the achievement of these services. Also, it provides information on the replication of each service as well as the fault tolerance and maintenance strategies implemented at the eBP site(s). A resource is a component system or an element of a component system (computer host, software and hardware components, communication link) that contributes to the implementation of e-business services. Indeed, one service may be partitioned and replicated among several resources or clusters of resources and one resource may host many services. At this level, we distinguish between internal and external services.

As the architecture on which the external services are implemented is not known, we associate to each of them a single resource that is considered as a black box. For example, an Internet service provider can be represented by a single resource providing connectivity service.

As regards internal services, a detailed analysis of the eBP site(s) architecture can be performed.

We must define the mapping between the resources and the services, as well as the interactions among these resources, since the availability of each service will depend on the availability of the corresponding resources. Table 3 gives a simple example for illustration: three resources (computer hosts A, B and C) are involved in the provision of the web service, while the application service and the database service are implemented on host D. All these resources are connected through a Local Area Network (LAN).

Several alternative architectural solutions may be considered for implementing the internal services. These solutions may be defined based on:

• various organizations of the services on the hardware support (e.g., dedicated hosts for each server, vs. multiple servers on the same host);

• various fault tolerance strategies (non-redundant servers vs. replicated servers);

• various maintenance strategies adopted by the eBP (e.g., immediate maintenance vs. delayed maintenance, dedicated vs. shared repair resources). Alternative architectures may be compared to help the designers in the selection of the most appropriate solution from the availability point of view. The analysis of the architectures should lead to the definition of the mapping between the resources and the services implemented on these resources. Various levels of service degradation may be defined depending on the state of the resources involved in its accomplishment. For instance, when a service is distributed on several computer hosts, the level of degradation can be defined as a function of the number of hosts that are operational. Architecture analysis and availability modeling at the resource level provides the information that is needed to define service accomplishment levels and to establish the link between the state of the resources and the corresponding accomplishment levels. For each service, different accomplishment levels can be defined depending on the types of failures affecting the corresponding resources. In particular, when the service is distributed on several resources, the service accomplishment levels can be defined according to the number of resources that are still available to run the service (graceful degradation concept). Knowledge of the system architecture is required for modeling purposes. Fig. 6 presents examples of configurations of a Web server: a) a non-redundant configuration with a single server, b) a redundant configuration with geographically distributed replicas, and c) cluster-based configuration with several Web servers interconnected through a LAN and centralized at a single site with a load balancer directing incoming requests to one of the servers. Configuration (b) requires the replica states to be kept mutually consistent to ensure that clients do not get out-of-date information. This is not easy to achieve on a large-scale system [START_REF] Ingham | Constructing Dependable Web Services[END_REF]. Alternative solutions are proposed for instance in [START_REF] Bowen | Towards Continuous Availability of Internet Services through Availability Domains[END_REF] to ensure a weak coupling between functions implemented on geographically distributed servers. The clusterbased configuration is widely used for the implementation of internet-based applications. This configuration is able to handle heavy traffic loads, however it has a single point of failure, the load balancer. Therefore, fault tolerant solutions with error detection and recovery capabilities should be considered for the load balancer. Popular web sites generally combine the clustering approach with geographically distributed servers in order to provide high performance and available web service (see for instance, the architecture deployed by IBM for the Nagano Olympic games [START_REF] Iyengar | High-Performance Web Site Design Techniques[END_REF]).

Fig. 6. Example of configurations for a Web server

Fault tolerance solutions should also be considered to ensure reliable communication among the Web servers as well as the availability of the data accessed by Web server processes. For example, data can be partitioned among the server machines and accessed through a shared bus. Under normal conditions, each server serves the data contained in its primary disk. When a server fails, another one takes over and serves its disk in addition to its own. alternative configuration can be used, where a shared master copy of the data is accessed by all the servers through a distributed file system. Each web server mounts and serves the same data set from the distributed file system.

Equivalent analyzes should be done with respect to all servers (e.g., the application and database servers in the example of Table 3).

Availability Modeling Approach

The hierarchical modeling approach, represented in Fig. 8, is directly related to the hierarchical description given in Fig. 3. It has been defined in such a way that the outputs of a given level are used in the next immediately upper level to compute the availability measures associated to this level. Accordingly, at the service level, the availability of each service is derived based on the availability of the resources involved in its accomplishment. Similarly, at the function level, the availability of each function is obtained from the availability of the services implementing it. Finally, at the user level, the availability measures are obtained based on the availability measures of the functions invoked by the user.

Fig. 8. Hierarchical availability modeling

A (F i ) = j A ( j (F i )) j =1 M (1)
where:

• M is the number of execution scenarios for function F i in the interaction diagram

• j is the probability of of execution scenario j

• j (F i ) is the set of servers and networks involved in execution scenario j

• A( j (F i ) is the availability of the servers and networks involved in execution scenario j

This formula is general and can applied whether the services are independent or not. When the services are independent, A(F i ) can be expressed as:

A(F i ) = j A(S p ) p j (F i ) j =1 M ( 2
)
where A(S p ) is the availability of a server or a network, S p , involved in execution scenario j.

At the user level, the availability model for a given user class is based on the knowledge of the execution paths followed by the user when visiting the eBP site(s) (described in the model characterizing the user operational profile, as defined in Section 3.1) and the availability of the functions invoked by the user in each path. The outputs of this level are the availability as seen by the various classes of users {A (user k )}.

Alike the function level, A (user k ) can be obtained by the following formula:

A(user k ) = i A(L i ) i = 1 N (3)
where:

• N is the number of scenarios in the Markov chain describing the user operational profile i is the probability of activation of scenario i

• L i is the set of functions involved in scenario i A(L i )

is the availability of functions involved in scenario i

In particular, when the functions are independent:

A(user k ) = i A(F q ) qL i i = 1 N (4)
where A(F q ) is the availability of function F q executed in scenario i.

What precedes shows that when the stochastic independence, or weak dependence assumptions hold, combinatorial logic can be used to obtain the availability measures associated to the levels, whereas detailed modeling using state based models is generally needed when strong dependencies exist among components. Such dependencies are likely to occur at the two lowest levels (i.e., resource and service levels). However, when strong dependencies are identified at the function level, a modeling approach based on Markov chains or stochastic Petri nets, considering the three lowest levels together could be required as it is more faithful to reality.

The availability models, defined within the multi-level modeling approach, can be solved using analytical or simulation based techniques. In particular, simulation techniques should be used when the models include particular assumptions that cannot be handled with traditional analytical techniques.

For the purpose of illustration, the next section presents some simple examples of resource and service availability modeling considering the independence and dependence modeling assumptions.

Examples of resource and service availability modeling

Generally, the servers implemented at the eBP site(s) are interconnected through one or several Area Networks (LAN). Therefore, two main components can be distinguished at the resource level: the communication links and protocols, represented for instance by the LAN, and the hosts on which the servers are implemented. In the following, we present simple examples that illustrate how availability sub-models can be built to evaluate the availability of a LAN and a server, implemented on a single computer or replicated on several hosts. server modeled in this section could be any of those referred to in Section 3 (i.e., a Web server, an application server or a database server).

The availability results obtained from the models presented in this section can be directly used in equations ( 1) and (2) given in Section 4.

1) Software and hardware component behaviors are stochastically independent 2) Software and hardware component behaviors are stochastically dependent

Stochastic independence assumption

Let us denote by sw ( hw ) the software (hardware) failure rate, and by µ sw (µ hw ) the corresponding restoration rate, and assume that software and hardware behaviors are stochastically independent. The availability of the server can be evaluated from the Markov Chain of Fig. 10 as the product of software and hardware availabilities, as follows:

server = A sw .A hw = µ sw (µ sw + sw ) . µ hw (µ hw + hw ) (6)
If the server is replicated on N hosts and these hosts are repaired independently of each other, the availability of the corresponding server is obtained as follows:

A server = 1 [1 A sw .A hw ] N = 1 1 µ sw (µ sw + sw ) . µ hw (µ hw + hw ) N (7)

Stochastic dependence assumption

The model of Fig. 10 does not distinguish between the impact of permanent faults and temporary faults. Also, it does not take into account the stochastic dependencies that might arise from the fault tolerance mechanisms implemented at the software or the hardware level, or from shared maintenance resources.

Fig. 10 -Host availability model with stochastically independent SW & HW

Owing to the importance of temporary faults on the behavior of hardware and software components, both permanent and temporary faults should be considered. Error propagation channels resulting from the activation of these faults should also be identified and analyzed. For example, an error due to the activation of a temporary fault in a hardware processor may propagate to the software processes running on the corresponding host, and thus affect a subset or all the services running on the corresponding site. Similarly, an error due to the activation of a permanent hardware fault will cause all the supported software processes to be stopped and then restarted after the hardware is repaired.

Errors may also propagate between software processes that dialog with each other. This is the case for instance of software replicas that need to exchange their state to support error detection and recovery.

A Markov chain can be built as for the previous case to model such behaviors. However, to master the complexity of model construction, it is recommended to use GSPNs. This is illustrated on a simple system constituted by a software component and a hardware component with embedded error detection mechanisms, and assuming that errors caused by transient hardware faults may propagate to the software. • The detected error is processed by means of exception handling mechanisms during a short time 1/ s . Two cases are distinguished: 1) if the fault is temporary (probability (1-p s )), its effects are eliminated and the software resumes its normal mode of operation, and 2) if the fault is permanent (probability p s ), the software has to be restarted (restart rate µ s ) to eliminate its effects.

• The effects of a non detected error may be eliminated (rate s ), or perceived (rate s ), in which case the software has to be restarted.

Equivalent assumptions are made regarding the hardware behavior:

Faults are activated with rate h :

• With probability p h the fault is permanent, (probability of a temporary fault (1-p h )).

• The effects of an error due to a temporary fault are eliminated within a short time 1/ h .

• An error due to a permanent fault is either detected with probability d h , or not detected (1-d h ). Error detection rate is h .

• The effects of a non-detected error, resulting from a permanent fault, may be perceived later through their effects on service delivery (rate h ).

• The repair rate is µ h .

The difference between hardware and software nets lies in the fact that for hardware, temporary and permanent faults are differentiated in this model by their respective consequences following activation, whereas for software, they are distinguished after specific processing [START_REF] Laprie | On the Temporary Character of Operation-Persistent Software Faults[END_REF].

The error propagation net is initialized via Prop after firing of transition h (non-detected error) or of transition 1-p h (an error due to a temporary fault) in the hardware net. With probability ph , the error is not propagated, and with p ph , it is propagated. The effect on the software is described via the immediate transitions t p and t n .

Finally, the software stop net is initialized by the marking of place: a) STP following firing of transition d h (detection of an error) or transition h (perception of a non-detected error) in the hardware net, or b) AR at the end of the hardware repair to enable software restart. The effects on the software net are modeled via the immediate transitions of the software stop net.

In this example, the availability of the server is computed from the Markov chain corresponding to the reachability graph of the GSPN model. Analytical equations of system availability (such as those given in equations ( 5), ( 6) and ( 7)) cannot be derived easily for this complex model. Usually, tools such as the SURF-2 tool developed at LAAS [START_REF] Béounes | SURF-2: A Program for Dependability Evaluation of Complex Hardware and Software systems[END_REF], are used to obtain system availability. The obtained measure is then used in equations ( 1) to (4) of Section 4 to derive the availability as seen by the users.

Clearly, this example illustrates the modeling when detailed assumptions about the hardware and the software are considered.

Related work

Our work is related to availability modeling of e-business applications. As far as we are aware of, no previous work addressed specifically this problem using a global modeling approach. The main advantage of our modeling approach is in structuring the e-business application itself in a hierarchical manner that can be modeled following the same hierarchical approach. Also, various measures related to different abstraction levels can be assessed.

Nevertheless, the basic modeling techniques used in our multi-level modeling approach are similar to those used for modeling complex systems. In particular, the primary problem when building availability models for complex systems is related to state explosion. Techniques addressing this problem are of two categories: "largeness avoidance" and "largeness tolerance" [START_REF] Trivedi | Techniques and Tools for Reliability and Performance Evaluation: Problems and Perspectives[END_REF]. A review of modeling techniques can be found in [START_REF] Arlat | Dependable Systems of Systems: State of the Art Survey, DSoS Project[END_REF].

Largeness avoidance techniques try to circumvent the generation of very large models by constructing sub-models that can be processed in isolation. The results of the sub-models are integrated into a single overall model that is small enough to be processed. Among them we have the behavioral decomposition technique [START_REF] Balbo | Combining Queuing Networks and GSPNs for the Solution of Complex Models of System Behaviour[END_REF], the hybrid hierarchical technique [START_REF] Balakrishnam | Component-wise Decomposition for an Efficient Reliability Computation of Systems with Repairable Components[END_REF], the data structure technique for the Kronecker solution of GSPNs [START_REF] Ciardo | A Data Structure for the Efficient Kroneker Solution of GSPNs[END_REF], the method of superposed GSPNs [START_REF] Donatelli | Superposed Generalized Stochastic Petri net: definition and efficient solution[END_REF] or of the asynchronous communicating modules [START_REF] Campos | Structured Solution of Asynchronously Communicating Stochastic Modules[END_REF]. Most of these techniques are efficient when the submodels are loosely coupled. main objective of largeness tolerance techniques is to master the generation of the global system model through the use of concise construction methods. The basic idea is to generate models of a modular system by composition of the sub-models of its components. In our previous work, we have defined some such techniques that are referenced all over this paper, and several techniques have been published by other authors (see e.g., [START_REF] Bondavalli | Dependability Modelling and Sensitivity Analysis of Scheduled Maintenance Systems[END_REF][START_REF] Meyer | Specification and Construction of Performability Models[END_REF][START_REF] Rojas | Compositional Construction of SWN Models[END_REF]). Roughly speaking, largeness tolerance techniques are recommended when several dependencies do exist between system components, making it very hard to combine the results using a largeness avoidance technique, in a tractable manner.

Our multi-level modeling approach combines the two categories of modeling techniques: it advocates largeness avoidance techniques at the levels where independence or weak dependency assumptions hold, and largeness tolerance techniques for constructing the sub-models that exhibit strong dependencies (in particular at the resource and service levels).

Conclusion

The quest for the construction of a dependable electronic business starts with the definition of the eBP architecture and the identification of the internal services as well as the possible external services complementing them. We have defined a multi-level approach for modeling the availability e-business applications, taking into account the infrastructure of the provider site(s), the availability of the external services and the user's profile. We have shown how to describe and model progressively an eBA.

From a practical point of view, our modeling approach aims at developing independent models, as far as possible, and combine the results. Indeed, even with the proposed approach, large and complex availability models cannot be totally avoided due to the large number of elements and the complexity inherent to e-business systems.

Certainly, we have not covered all topics that need to be addressed when designing an eBP site, but we put emphasis on how to decompose the main problems to solve them in an easier manner than considering all levels at the same time. We have shown the kind of calculations and modeling that are required for the various steps.

In particular in this paper, we have considered the case of a single host with one hardware component and one software component. We did not take into account, e.g., the replication of the servers, the organization of the software replicas on the hardware support or the communication among these replicas. Indeed, it is not easy to illustrate the modeling of such issues on a general case.

Currently, we are defining a case study to illustrate the approach. However, we have already some experience in modeling real-life systems (e.g., air traffic control systems [START_REF] Fota | Dependability Evaluation of an Air Traffic Control Computing System[END_REF][START_REF] Kanoun | Modeling the Dependability of CAUTRA, a Subset of the French Air Traffic Control System[END_REF] and instrumentation and control systems [START_REF] Betous-Almeida | Dependability Evaluation From Functional to Structural Modelling[END_REF]) as well as more generic systems (e.g., the GUARD architectures [START_REF] Arlat | Dependability Assessment of GUARDS Instances[END_REF] and multipurpose multiprocessor systems [START_REF] Rabah | Dependability Evaluation of a Distributed Shared Memory Multiprocessor System[END_REF]). The complexity of the above referenced systems is equivalent to the complexity of eBP site(s), and the dependability modeling techniques that could be used are analogous. In addition, we have applied our multi-level modeling approach to a Web travel agency [START_REF] Kaâniche | User-perceived Availability of a Web based Travel Agency[END_REF].

Fig. 1 .

 1 Fig. 1. E-business key players.

Fig. 5

 5 Fig. 5 presents three possible scenarios for the execution of the "Browse" function. The nodes are

Fig. 11

 11 Fig.11presents the corresponding model. The model is based on the block modeling approach presented in[START_REF] Kanoun | Fault-Tolerant System Dependability -Explicit Modeling of Hardware and Software Component-Interactions[END_REF]. It is structured as follows:

TABLE 1 : Examples of Functions Provided by E-Business Sites

 1

	Category	Function	Description
	Common	Login	Login to the site
		Register	Register as a new user
		Search	Search site database
		Select	Show one of the results of a search
		Browse	Follow links within the site
	Retail	Add Item	Add item to shopping cart
		Remove Item	Remove item from shopping cart
		See Shopping Cart	Check contents and value of shopping cart
		Create Registry	Create a gift registry
		Add to Registry	Add item to gift registry
		Check Status	Check status of previous order
		Pay	Pay for items in shopping cart
	Trading	Open Account	Open account for trading
		Get Quotes	Get delayed or real-time quotes
		Get Report	Get performance report on companies
		View Chart	View chart of closing prices
		View Indexes	View values of indexes
		Trade	Buy/sell/exchange stocks or mutual funds
		Create Portfolio	Create stock/funds portfolio
		Add to Portfolio	Add stock/funds to portfolio
		Delete from Portfolio	Delete stock/funds from portfolio

Table 2

 2

presents a static view of the link between functions and servers. It does not specify clearly if all servers are needed for each execution or if only subsets of them are needed for different execution scenarios. The latter are obtained from the analysis of the dynamic interactions among the servers during function executions. Several graphical notations and formalisms can be used to describe the dynamic interactions and dependencies among the servers that implement an e-business function (see, e.g.,

TABLE 2 : Example of Mapping Between Functions and Servers

 2

	Web	Trading	Authentication	Application	Database
	Server	Server	Server	Server	Server
	Login
	Register
	Search
	Select
	Browse
	Open Account
	Get Quotes
	Get Report
	View Chart
	View Indexes
	Trade
	Create Portfolio
	Add to Portfolio
	Delete from Portfolio

TABLE 3 : Example of Mapping Between Internal Services and Resources

 3

	Host A	Host B	Host C	Host D	LAN
	Web Service
	Application Service
	Database service

* This work is partially supported by the European Community (Project IST-1999-11825: DSoS, Dependable Systems of Systems)

Considering the service level, we made a distinction between internal and external services. The latter are delivered by providers for whom only little information is known. It is however expected that specific experiments or measurements such as those performed in [START_REF] Kalyanakrishnan | Reliability of Internet Hosts: a Case Study from the End User's Perspective[END_REF][START_REF] Long | A Longitudinal Survey of Internet Host Reliability[END_REF][START_REF] Machiraju | E-services Management Requirements[END_REF] provide the availability measures {A(Se j )}. It is assumed that external services are independent.

Internal services are supplied by the resources of the eBP. Depending on the infrastructure of the provider site(s), some services may be implemented on the same resources, some of the resources may share the same repair facilities and some services or resources may be replicated or fault-tolerant. As a consequence, strong dependencies may exist between the services due to dependencies between the resources. For such infrastructures, it is more efficient to consider the service and the resource levels together, the corresponding level is simply denoted as the service/resource level. At the service/resource level, one or several availability models are built based on the knowledge of the e-business infrastructure and the resources implementing the expected services, together with the fault tolerance and recovery mechanisms, and the maintenance policies at the provider site(s).

Different techniques may be used to build and solve these availability models, including combinatorial techniques (e.g., fault trees, reliability block diagrams), and state-based techniques (e.g., Markov chains, Generalized Stochastic Petri Nets, GSPNs) [START_REF] Reibman | Reliability Modeling: An Overview for System Designers[END_REF][START_REF] Trivedi | Techniques and Tools for Reliability and Performance Evaluation: Problems and Perspectives[END_REF]. The selection of the right technique to be used mainly depends on whether i) the services are stochastically independent or not, and ii) the resources are independent or not. Markov chains and GSPNs are well suited to evaluate the service availability in the presence of strong dependencies. In particular, the modeling approaches described in [15, 21 , 30 ] have been successfully applied to complex real-life systems, can be used to take into account explicitly the stochastic dependencies that might exist between the various components of the service/resource availability model. Some examples of models at the service/resource level are given in Section 5. The outputs of this modeling step are the availability of the various internal services {A

The availability model at the function level is based on the knowledge of the availability of all services involved in function accomplishment, along with the matrix giving the mapping between Functions and Services and the path probabilities derived from the interaction diagrams as defined in Section 3.3. The outputs of this level are the availability of the various functions {A (F i )} that can be defined as follows.

LAN availability modeling

The availability of the local area network can be analyzed with respect to two main failure modes: permanent failures and transient failures. Transient failures correspond to the temporary loss communications, for example, as a result of the congestion of the network. These failures disappear when normal traffic conditions over the network are restored. Permanent failures correspond to hardware and software failures of network elements that require a maintenance action. Fig. 9 presents the Markov chain describing the behavior of the LAN.

The parameters used in this model are defined as follows: The availability of the LAN in the steady state can be obtained by evaluating the probability for the LAN to be in state 0. The processing of the corresponding Markov chain leads to the following equation:

Server availability modeling

To evaluate the availability of a server we need to take into account the impact of software and hardware failures that affect the host on which the server is implemented. Two cases are distinguished in the following: The software net is based on the following assumptions: Faults are activated with rate s :

• With probability p s the fault is permanent, (probability of a temporary fault (1-p s )).

• An error is either detected with probability d s , or not detected (1-d s ). Error detection rate is s .