Mirosław Trzupek
email: mtrzupek@agh.edu.pl

Semantic modelling of coronary vessel structures in computer aided detection of pathological changes

Keywords: Intelligent medical image processing and understanding, spatial modelling of coronary vessels, computer-aided diagnosis

In the paper, the author discusses the results of his research on the opportunities for using selected artificial intelligence methods to semantically analyse medical images. In particular, he will present attempts at using linguistic methods of structural image analysis to develop systems for the cognitive analysis and understanding of selected medical images, and this will be illustrated by the recognition of pathological changes in coronary arteries of the heart. The problem undertaken is important because the identification and location of significant stenoses in coronary vessels is a widespread practical task. The obtained results confirm the importance of the proposed methods in the diagnosis of coronary heart disease.

Introduction

Coronary Heart Disease (CHD) is the leading cause of death in developed countries and at the same time constitutes a crucial diagnostic problem of the 21 st century. Every year, over 19 million people globally suffer sudden, severe coronary incidents. Early diagnosis and risk assessment are widely accepted strategies to combat CHD [START_REF] Yusuf | Global burden of cardiovascular diseases, Part I. General considerations, the epidemiologic transition, risk factors, and impact of urbanization[END_REF]. The impressive technological progress in medical image diagnostics and the wide opportunities for 3D visualization of human organs have significantly improved the efficiency of medical diagnostic tasks. The 3D reconstructions of examined medical structures [START_REF] Lewandowski | Visualization of 3-D Objects in Medicine -Selected Technical Aspects for Physicians[END_REF] obtained by rendering make it possible to truly represent the selected organ (including the changes in its texture), allowing its external and internal morphology to be observed precisely. Such high technologies of image processing [START_REF] Sonka | Handbook of Medical Imaging -Volume 2. Medical Image Processing and Analysis[END_REF] are today used in almost all types of diagnostic examinations based on digital technologies and of surgical jobs performed with the use of medical robots. As a result, it has become possible to identify a greater number of qualitative parameters of the examined structure which may be significant for making the correct diagnosis, and which could not be identified if the examination was made using a conventional method (2D imaging) [START_REF] Katritsis | Three-dimensional analysis of the left anterior descending coronary artery: comparison with conventional coronary angiograms[END_REF]. However, all these achievements in the visualization technology field offer limited opportunities for automating the interpretation of the diagnostic images acquired. This is mainly due to the difficulties which informatics encounters in formally describing and modelling complex thought processes taking place in the human mind which enable the semantic interpretation of analyzed medical images. Such intelligent IT systems supporting the thought processes of a physician analyzing complex cases simply have not been developed yet. There are, however, tools which support the work of a diagnostician by making quantitative measurements of pathologies depicted in the image [START_REF] Yin | A Fully Automated Framework for Segmentation and Stenosis Quantification of Coronary Arteries in 3D CTA Imaging[END_REF], [START_REF] Oncel | Detection of significant coronary artery stenosis with 64-section MDCT angiography[END_REF], which obviously makes his/her work easier, but only understanding the essence of the disease process allows the appropriate diagnosis to be made and the correct therapy to be prescribed.

The problem of analysis and understanding of medical images

One of the main difficulties in developing universal, intelligent systems for medical image diagnostics is the huge variety of images, both healthy and pathological, which have to be taken into account when intelligently supporting physicians interpreting them. In particular, the aforementioned varied shapes of morphological elements make it difficult to create a universal pattern defining the model shape of a healthy organ, or a pathological one. On the other hand, a computer using the well-known and frequently used techniques of automatic image recognition needs such a pattern to be provided to it. This is because the information technologies applied rely to a significant extent on intuition to determine the measure of similarity between the currently considered case and such an abstract pattern. These technologies frequently fail if there are unexpected changes to the shapes of analysed organs caused by the disease process or individual variability. All of this means that attempts to effectively assess the morphology using computer software are very complicated and frequently outright impossible, because there are too many cases that would have to be analysed to unambiguously determine the condition of the structure being examined. For this reason it is necessary to use those advanced artificial intelligence techniques and computational intelligence techniques that can generalize the recorded image patterns. What is particularly important is to use intelligent description methods that would ignore individual characteristics of the patient examined and characteristics dependent on the specific form of the disease unit considered, while at the same time making it possible to locate significant morphology changes and also to interpret and determine their diagnostic significance. Such methods, aimed at focusing the image description on diagnostically significant properties to the maximum extent can then be used in intelligent computer-aided diagnostics systems.

Methodology

Research work was conducted on images from diagnostic examinations made using SOMATOM Sensation Cardiac 64 tomograph [7] in the form of animations saved as AVI (MPEG4) files with the 512x512 pixel format. Such sequences were obtained for various patients and present in a very clear manner all morphologic changes of individual sections of arteries in any plane. Coronary vessels were visualized without the accompanying muscle tissue of the heart. Since image data has been saved in the form of animations showing coronary vessels in various projections, for the further analyses should be selected the appropriate projection which will show the examined coronary vessels in the most transparent form most convenient for analysis. In the research work, attempts were made to automate the procedure of finding such a projection by using selected geometric transformations during image processing. Using the fact that the spatial layout of an object can be determined by projecting it onto the axes of the Carthesian coordinate system, values of horizontal Feret diameters [START_REF] Tadeusiewicz | Computer Analysis and Image Processing[END_REF], which are a measure of the horizontal extent of the diagnosed coronary artery tree, are calculated for every subsequent animation frame. The projection for which the horizontal Feret diameter is the greatest is selected for further analyses. To help represent the examined structure of coronary vascularisation with a graph, it is necessary to define primary components of the analyzed image and their spatial relations, which will serve to extract and suitably represent the morphological characteristics significant for understanding the pathology shown in the image. It is therefore necessary to identify individual coronary arteries and their mutual spatial relations. To ease this process, the projection selected for analyzing was skeletonised by the Pavlidis skeletonising algorithm [START_REF] Pavlidis | Algorithms for graphics and image processing[END_REF] (it leaves the fewest apparent side branches in the skeleton and the lines generated during the analysis are only negligibly shortened at their ends). This gives us the skeleton of the given artery which is much thinner than the artery itself, but fully reflects its topological structure (fig. 1.). Skeletonising is aimed only at making it possible to find points where artery sections intersect or end in the vascularisation structures and then to introduce an unambiguous linguistic description of individual coronary arteries and their branches. These points will constitute the vertices of a graph modelling the spatial structure of the coronary vessels. The next step is labelling them by giving each located informative point the appropriate label from the set of vertex labels (this set comprises abbreviated names of arteries found in coronary vascularisation). If a given informative point is a branching point, then the vertex will be labelled with the concatenation of names of the vertex labels of arteries which begin at this point. This way, all initial and final points of coronary vessels as well as all points where main vessels branch into lower level vessels have been determined and labelled as appropriate. After this operation, the coronary vascularisation tree is divided into sections which constitute the edges of a graph modelling the examined coronary arteries. This makes it possible to formulate a description in the form of edge labels which determine the mutual spatial relations between the primary components, i.e. between subsequent arteries shown in the analysed image. Mutual spatial relations that may occur between elements of the vascular structure represented by a graph are described by the set of edges. The elements of this set have been defined by introducing the appropriate spatial relations: vertical -defined by the set of labels {α, β,…, μ} and horizontal -defined by the set of labels {1, 2,…, 24} on a hypothetical sphere surrounding the heart muscle. These labels designate individual final intervals, each of which has the angular spread of 15. Then, depending on the location, terminal edge labels are assigned to all branches identified by the beginnings and ends of the appropriate sections of coronary arteries (fig. 1). The presented methodology draws upon the method of determining the location of a point on the surface of our planet in the system of geographic coordinates, where a similar cartographic projection is used to make topographic maps. This representation of mutual spatial relations between the analysed arteries yields a convenient access to the unambiguous description of all elements of the vascular structure. At subsequent analysis stages, this description will be correctly formalised using ETPL(k) (Embedding Transformation-preserved Production-ordered k-Left nodes unambiguous) graph grammar G defined in [START_REF] Tadeusiewicz | Pattern Recognition[END_REF], [START_REF] Skomorowski | A Syntactic-Statistical Approach to Recognition of Distorted Patterns[END_REF], supporting the search for stenoses in the lumen of arteries forming parts of the coronary vascularisation. Grammar G generates the language L(G) in the form of IE (indexed edgeunambiguous) graphs which can unambiguously represent 3D structures of heart muscle vascularisation visualised in images acquired during diagnostic examinations with the use of spiral computed tomography. Quoted below (1) is the formal definition of the IE graph [START_REF] Tadeusiewicz | Pattern Recognition[END_REF], [START_REF] Skomorowski | A Syntactic-Statistical Approach to Recognition of Distorted Patterns[END_REF].

H=(V, E, , , ) (1)
where:

V is a finite, non-empty set of graph node with unambiguously assigned indices  is a finite, non-empty set of node labels  is a finite, non-empty set of edge labels E is a set of graph edges in the form of (v, ,w), where v, wV,  and the index v is smaller than the index w :V is a function of node labelling After applying the presented methodology, a graph model representing the coronary arteries on the CT images was obtained (fig. 1.). Due to the fact that in obtained during diagnostic examination visualisations of coronary vascularisation, we can distinguish three different types of topologies, characteristic for these vessels, therefore, for each of the three types of topology, appropriate type of ETPL(k) graph grammars can be proposed. Each grammar generate IE graphs language, modelling particular types of coronary vascularisation. This representation was then subjected to a detailed analysis, to find the places of morphological changes indicating occurrence of pathology. This operation consists of several stages, and uses, among others context-free sequential grammars, used successfully for the detection of lesions in coronary planar images [START_REF] Tadeusiewicz | Medical Image Understanding Technology[END_REF]. Next steps in the analysis of the example coronary artery are shown in fig. 2. Artery with the vertices L_LAD 3 -LAD 6 represented by the edge 19 of the IE graph has been subjected to the operation of the straightening transformation [START_REF] Tadeusiewicz | Medical Image Understanding Technology[END_REF], which allows to obtain the width diagram of the analyzed artery, while preserving all its properties, including potential changes in morphology. In addition, such representation allows to determine the nature of the narrowing (concentric or eccentric). Concentric stenoses occur on a cross-section as a uniform stricture of the whole artery (this symptom is characteristic for a stable disturbance of heart rhythm), whereas eccentric stenoses occur only on one vascular wall (an unstable angina pectoris) [START_REF] Faergeman | Coronary Artery Disease[END_REF]. Analysis of morphological changes was conducting based on the obtained width diagrams, and using context-free attributed grammars [START_REF] Tadeusiewicz | Medical Image Understanding Technology[END_REF]. As a result of carried out operations the profile of the analyzed coronary artery with marked areas of existing pathology, together with the determination of the numerical values of their advancement level was obtained (fig. 2). Methodology presented above was implemented sequentially to the individual sections of coronary vascularisation represented by the particular edges of the introduced graph representation.

Results

The set of test images, which has been used to determine the efficiency of the proposed methods consisted of 20 complete reconstructions of coronary vascularisation obtained during diagnostic examinations of various patients, mainly suffering from coronary heart disease at different progression stages. These images were obtained during diagnostic examinations with 64-slice spiral computed tomography. Due to the different types of topologies of coronary vascularisation, the set of analyzed images consisted of three basic types (balanced artery distribution, right artery dominant, left artery dominant). Structure of the coronary vascularisation was determined by a diagnostician at the stage of acquisition of image data. This distinction was intended to obtain additional information about the importance of providing health risks of the patient depending on the place where pathology occurs in the type of coronary vascularisation. The test data also consisted of visualisations previously used to construct the grammar and the syntactic analyser. To avoid analysis of images that were used to construct the set of grammatical rules, from the same sequences frames were selected that were several frames later than the projections used to construct the set of grammatical rules, and these later frames were used for the analysis. The above set of image data was used to determine the percentage efficiency of correct recognitions of the stenoses present, using the methodology proposed here. The recognition consists in identifying the locations of stenoses, their number, extent and type (concentric or eccentric). For the research data included in the experiment, 85% of recognitions were correct. This value is the percentage proportion of the number of images in which the occurring stenoses were correctly located, measured and properly interpreted to the number of all analysed images included in the experimental data set. No indication of major differences in the effectiveness evaluation, depending on the structure of the coronary vascularisation is noticed. In order to assess whether the size of the stenosis was correctly measured, comparative values from the syngo Vessel View software forming part of the HeartView CI suite were used. This program is used in everyday clinical practice where examinations are made with the SOMATOM Sensation Cardiac 64 tomograph [7]. In order to confirm or reject the regularity of the stenosis type determination (concentric or eccentric) shown in the examined image, a visual assessment was used, because the aforementioned programs did not have this functionality implemented. As the set of test data was small the results obtained are very promising. Further research on improving the presented analysis techniques of lesions occurring in the morphology of coronary vessels might bring about a further improvement in the effectiveness and the future standardisation of these methods, obviously after they have first been tested on a much more numerous image data set.

The obtained results show that graph languages for describing shape features can be effectively used to describe 3D reconstructions of coronary vessels and also to formulate semantic meaning descriptions of lesions found in these reconstructions [START_REF] Ogiela | Picture grammars in classification and semantic interpretation of 3D coronary vessels visualisations[END_REF], [START_REF] Trzupek | Image content analysis for cardiac 3D visualizations. Knowledge-based and intelligent information and engineering systems : 13th international conference[END_REF]. Such formalisms, due to their significant descriptive power (characteristic especially for graph grammars) can create models of both examined vessels whose morphology shows no lesions and those with visible lesions bearing witness to early or more advanced stages of the ischemic heart disease. In addition, by introducing the appropriate spatial relations into the coronary vessel reconstruction, it is possible to reproduce their biological role, namely the blood distribution within the whole coronary circulation system, which also facilitates locating and determining the progression stage of lesions. The research also has shown that one of the hardest tasks leading to the computer classification and then the semantic interpretation of medical visualisations is to create suitable representations of the analysed structures and propose effective algorithms for reasoning about the nature of pathologies found in these images. Visualisations of coronary vascularisation are difficult for computers to analyse due to the variety of projections of the arteries examined. Problems related to automating the process of generating new grammars for cases not included in the present language remain unsolved in the on-going research. However, it is worth noting that generally, the problem of deriving grammatical rules is considered unsolvable, particularly for graph grammar. It can appear if the image undergoing the analysis shows a coronary vascularisation structure different from the so far assumed three cases of vessel topologies occurring the most often, i.e. the balanced distribution of arteries, the dominant right artery or the dominant left artery. In those cases it will be necessary to define a grammar taking this new case into account. The processes of creating new grammars and enriching existing ones with new description rules will be followed in further directions of research on the presented methods.

Fig. 1 .

 1 Fig. 1. The representation of the left coronary artery using IE graph.

Fig. 2 .

 2 Fig. 2. Next steps in the analysis and recognition of pathological changes occurring on the example of the left coronary artery.

Acknowledgments. This work has been supported by the Ministry of Science and Higher Education, Republic of Poland, under project number N N516 478940.


Ahlmann Nyre
email: nyre@idi.ntnu.no

Usage control enforcement -a survey

Sharing information allows businesses to take advantage of hidden knowledge, improve work processes and cooperation both within and across organisations. Thus there is a need for improved information protection capable of restricting how information is used, as opposed to only accessed. Usage Control has been proposed to achieve this by combining and extending traditional access control, Digital Rights Management and various encryption schemes. Advances in usage control enforcement has received considerable attention from the research community and we therefore believe there is a need to synthesise these efforts to minimise the potential for overlap. This paper surveys the previous efforts on providing usage control enforcement and analyses the general strengths and weaknesses of these approaches. In this paper we demonstrate that there are several promising mechanisms for enforcing usage control, but that reliable empirical evidence is required in order to ensure the appropriateness and usability of the enforcement mechanisms.

Introduction

Despite almost daily reports of security flaws and breached security, Internet users continue to share information at an increasing rate. Basically about anything from personal habits to sensitive corporate secrets, using a wide variety of communication channels. The fundamental problem is however that current security systems are unable to enforce any restrictions on the access, use or distribution of information once it has been transferred from one system to another. Hence, the sender involuntarily looses any control of the information and must resort to trusting the receiver to not misuse information. It is this problem that has lead to serious concerns about users privacy on the Internet, and the music and film industry's concern about intellectual property rights violations, and corporations concern about sensitive information misuse.

Usage control have been proposed as a means to remedy this problem by extending common security mechanisms beyond single systems such as PCs, servers or entire corporate systems. The idea is to provide a model for expressing and enforcing restrictions on how the information is to be used . Current mechanisms such as access control, Digital Rights Management, confidentiality and privacy protection all attempt to restrict information in one way or the other. The focus of usage control is to create an holistic approach to restricting information, such that it may be used for any of the purposes listed above.

The purpose of this review is to identify and analyse existing mechanisms for usage control enforcement in order to identify shortcomings and possible improvements.

The remaining parts of the paper is organised as follows. First, in Section 2 the research method employed is outlined and discussed. Next, in section 3 we provide a brief introduction to usage control. We review enforcement mechanisms in Section 4 and in Section 5 we report on the testing and evaluation that has been conducted . Section 6 includes our analysis and discussion of the enforcement mechanisms. Related work is outlined in Section 7, before our final conclusions are given in Section 8.

Research Method

The research method employed in this review is inspired by the recommendations by Kitchenham and Charters [START_REF] Kitchenham | Guidelines for performing systematic literature reviews in software engineering[END_REF] regarding systematic literature reviews in software engineering, however with softer requirements regarding rigour. This review will address the following research questions:

RQ1. What usage control enforcement mechanisms have been proposed and how do they relate to each other? RQ2. What evidence exists supporting their appropriateness?

The purpose of this review is therefore to synthesise the previous research efforts on usage control and distributed enforcement strategies to identify open issues and prevent duplication of work. To this end, we also investigate the supporting evidence of appropriateness.

The papers subject to the review were selected based on search through the main online portals of scientific publications. These portals were: IEEE Xplore, ACM Digital Library, Scopusand SpringerLink. Potential papers were selected based on a search for "usage control" and "enforcement" in title, keywords and abstracts, for each of the portals listed above. The search capabilities of these portals vary considerably, hence minor modifications have been conducted. Most notably for SpringerLink, the amount of results returned made it necessary to conduct a nested search of the two phrases.

The search strategy clearly results in several irrelevant papers being potential subject to the review. Additional criteria were therefore specified to ensure only relevant papers be included in the actual review. These criteria are referred to as inclusion and exclusion criteria, indicating both a positive definition and a negative definition of what the review should and should not contain. Published peer-reviewed papers were included in the review if meeting any of the following criteria:

-Papers presenting mechanisms for enforcement of usage control models.

-Papers reporting on testing and experience of use with such mechanisms.

The criteria may be met by only parts of the paper, thus it need not be the main focus of the paper to be included. Papers meeting one or more of the of the following criteria were excluded:

-Position papers identifying threats and challenges to usage control.

-Papers focusing solely on subsets of usage control, such as access control and digital rights management.

Note that inclusion criteria was given a higher order than exclusion criteria, such that any paper satisfying both were included in the review.

From each of the included papers, the following content was extracted and analysed:

-The main idea of the model (RQ1.).

-The main strengths and limitations of the approach (RQ1.).

-The supportive evidence of its appropriateness (RQ2.).

While the data extraction part is mainly about documenting previous efforts, the analysis part was intended to look beyond specific claims to make more general assessments of the quality and usability of the proposed enforcement mechanisms.

Usage control

The UCON (Usage Control) model was proposed by Park and Sandhu [START_REF] Park | The UCONABC usage control model[END_REF] to alleviate many of the shortcomings of existing access control mechanisms, particularly for distributed assets. The authors focus on three important parts of the model, which are Authorizations, oBligations and Conditions, resulting in what they denote the UCON ABC model. The main elements of this model are Subject an entity with a set of attributes (subject attributes) either holding or exercising rights on an object. Object an entity with a set of attributes (object attributes) that a subject hold or exercise a right on. Right a privilege held by a subject to perform certain functions on an object. Authorization a functional predicate to be evaluated in order to decide whether the subject is allowed to perform the requested rights on the object. oBligation a functional predicate to verify requirements a subject has to perform before or during a usage exercise. Condition a functional predicate to verify the requirements for the environment or system to be present before or during a usage exercise.

The family of models have later been expanded and detailed using various formalisms. A survey by Lazouski et al. [START_REF] Lazouski | Usage control in computer security: A survey[END_REF] provide a good overview of these efforts. One of the main concepts of UCON is the view on continuous enforcement (see Figure 1). Contrary to common access control mechanisms, UCON assumes authorisations to be an ongoing activity such that misbehaviour may result in real-time revocation of rights. Park and Sandhu defined 16 basic UCON models based on the different steps in Figure 1.

access will go to revoked ed by the system, or it will hes the usage. We believe mplete to specify the states d the system, as well as the ur logical model in UCON. uilt from variables and conct attributes, and system atof the attributes, we define object attribute: p(sa) or re ct attribute and an object atce, f ile1.classif ication), value).

een attributes, where the a2 here ID is a subject idenbject IDs as file1's access ), which is true if a subject This predicate is the result e system. types of variables in UCON: system attributes. We des of these variables. the original UCON model, per assume that an action is always performed instantly. In a real implementation there is mechanism to monitor the process and audit the update, so that the system can recover if any failure happens.

For system states, we define a series of actions that change the status of an access (s, o, r). As mentioned before, there are six different possible values of state(s, o, r) during a process life cycle. The transition from a state to another state is an action, as shown in Fig. 3.

Fig. 4 shows the actions that are performed by the system and by a subject during a usage. These actions are briefly explained below. performed by a subject.

Before

2. permitaccess(s, o, r): grants an access request of (s, o, r), performed by the system.

5

Fig. 1. UCON model with continuity of enforcement and mutability of properties [START_REF] Zhang | A logical specification for usage control[END_REF] 4 Enforcement mechanisms

In this section we describe the identified usage controlled enforcement mechanisms. We have separated them into three main categories which are proactive enforcement, reactive enforcement and trust-based enforcement. Although these categories are not mutually exclusive, they are often treated separately.

Proactive enforcement

In this section we elaborate on the mechanisms that are mainly focused on preventing policy violation through proactive security measures. We categorise the mechanisms into three groups of client-side enforcement: trusted computingbased enforcement, hardware-based enforcement and software-based enforcement. Finally we also provide a category for server-side enforcement. Note that some of the approaches falls into several categories, but are placed in the one that best describe the focus of the mechanism.

Trusted computing Trusted computing has been introduced as one of the main building blocks to enforce usage control policies on remote client devices. Although there are many that assume the use of trusted computing or a trusted platform, we include here only the approaches where trusted computing is essential to the mechanism. Sandhu et al. propose a Trusted Reference Monitor (TRM) residing in user space to enforce policies [START_REF] Sandhu | Client-side access control enforcement using trusted computing and pei models[END_REF][START_REF] Zhang | Security enforcement model for distributed usage control[END_REF]. A hardware-based Trusted Platform Module (TPM) is envisioned to provide a root of trust that together with a Public Key Infrastructure (PKI) may be used to attest cooperating platforms. The protocol between applications and TRM, as well as between different TRMs is based on challenge-response. Any request is followed by a challenge from the receiver. The requester subsequently attest the platform, application or environment through the means of a digital signature. Abie et al. propose a somewhat similar strategy based on a TPM to enforce usage policies on digital objects [START_REF] Abie | A distributed digital rights management model for secure information-distribution systems[END_REF][START_REF] Abie | Rights-carrying and self-enforcing information objects for information distribution systems[END_REF]. Self-enforcing objects (SEOs) are used as a secure container to transfer objects and policies and are also capable of enforcing the attached policy autonomously on any trusted platform.

A practical example of such an enforcement mechanism is given by Kyle and Brustolini [START_REF] Kyle | Uclinux: a linux security module for trusted-computingbased usage controls enforcement[END_REF]. UCLinux is a Linux Security Module that provides attestation, sealing and usage control support. Applications is provided access to the file if they are part of the trusted computing base and the file metadata contain a hash of the application. If the application is deemed trusted, UCLinux will handle any usage control enforcement to the application itself. Untrusted applications will however not be able to read nor write to the file. Alam et al. propose a similar enforcement mechanism [START_REF] Alam | Usage control platformization via trustworthy SELinux[END_REF] but also describe the concept of platform attestation [START_REF] Alam | Behavioral attestation for web services (BA4WS)[END_REF]. Prior to releasing information to an authorised requester, the system verifies through a WS-Attestation procedure that the receiving platform will behave properly. A prototype implementation indicates an introduced delay of approximately five seconds, compared to not having such attestation.

Hardware enforcement Hardware UCON Engine (HUE) [START_REF] Nauman | Hue: A hardware ucon engine for fine-grained continuous usage control[END_REF] is another enforcement mechanism based on trusted computing that unlike most mechanisms does not rely on a built-in Trusted Platform Module (TPM). Instead, HUE is designed as a secure co-processor with a designated software stack to provide integration with the operating system. While obviously more flexible and efficient than TPM-based systems, the downside is that it the tailor-made hardware is not commercially available.

Software-based enforcement

The RightsEnforcer [START_REF] Matson | The 'how' and 'why' of persistent information security[END_REF] is a product for enforcing simple usage control restrictions such as limiting the ability to view, print, copy and store. The mechanism is integrated in an e-mail client such that whenever a usage controlled object is sent to a receiver, the RightsEnforcer encrypts the content and sends the terms of use to a centralised RightsServer. The receiver is forced to use the RightsEnforcer to be able to decrypt the content and therefore the policy is always enforced.

Brustolini et al. propose a simplified version where policies are specified through allowing or denying specific operations (open, copy, print, etc.) on digital objects [START_REF] Brustoloni | Evaluating the usability of usage controls in electronic collaboration[END_REF][START_REF] Djalaliev | Secure web-based retrieval of documents with usage controls[END_REF]. The system comprises a kernel level security module for SELinux, a web browser plugin and a modified web server that offers the ability to post information objects to a web service. Upon uploading documents, users are given the option to specify any usage restrictions. When downloading content from the service, the client warns the user of unacceptable policies.

A somewhat similar strategy is employed by Kumari et al. to provide usage control enforcement for web applications [START_REF] Kumari | Distributed data usage control for web applications: a social network implementation[END_REF]. The solution is based on a web browser plugin that intercepts requests for enforcement enabled web applications and subsequently enforces the obtained policy. They demonstrate the feasibility of the approach through a modified social network application that generates policies whenever a content request is made by a user. Users can tag friends with a trust level in intervals from 0 to 1 and similarly tag content with a sensitivity on the same scale. A permission p is then computed as the product p(t, s) = t(1 -s) where t is the trust value of the subject and s the sensitivity of the content. These permissions are grouped into permission classes in five intervals such that the users may define which permission classes are allowed to perform events such as "view", "copy", etc. Any request not originating from the browser plugin is treated as permission class 0 (minimum permissions). Although currently not implemented, the authors argue that to prevent users from evading enforcement, some TPM based mechanism should be in place to guarantee that the browser plugin is not hijacked by other malicious plugins.

Server-side An enforcement architecture for server-side enforcement is given in [START_REF] Katt | A general obligation model and continuity: enhanced policy enforcement engine for usage control[END_REF]. The focus of the approach is to enforce post usage obligations on possibly remote systems. Obligations may be placed on the system or on the subject (of usage) and relates to either controllable or uncontrollable objects as seen by the system. Katt et al. argue that system obligations on controllable objects, denoted trusted obligations, do not need a fulfilment check, since the system is assumed to be trusted. However for any other untrusted obligations, the system translates the obligations into a sequence of system operations including a condition at the end. Thus, if the condition holds, the obligation is assumed to be fulfilled. In the event that the obligation is not fulfilled (e.g. a file is not deleted), the system will issue any necessary compensating action as specified in the policy.

Layered UCON (L-UCON) provides partial (or layered) usage of resources. Since digital resources often are provided in a layered fashion (e.g. the varying pixel resolution of images), L-UCON provides the user with the ability to negotiate both content and policies with the content owner. Hence, the content owner may adjust a policy based on for example the usage purpose stated by the user.

Gheorghe et al. [START_REF] Gheorghe | Enforcing ucon policies on the enterprise service bus[END_REF] utilise the Message Service Bus of Service-Oriented Architectures (SOA) to enforce business and regulatory usage control policies on messages exchanged between services. Since all messages are placed on the service bus, messages may easily be intercepted and validated for compliance with stated policies. However, policies are assumed to be fairly static and message level usage policies are not handled by the architecture.

Reactive enforcement

Reactive security measures may be seen as an acceptance of failure, since security breaches cannot be prevented, penalties are our only options. While they do seem weaker at first glance, the main reason for utilising reactive measures is lack of control. It is difficult to prevent policy violations from occurring when the enforcer has no or limited control over the target device. Since detecting such violations after the fact are in many cases easier, reactive enforcement may provide a powerful complement to any proactive enforcement. In the following we survey some of the main efforts on reactive enforcement of usage control policies.

Audit-based enforcement

The approach taken by Corin et al. is not to prevent policy violation but to ensure that users are held accountable for their actions through a proper auditing process [START_REF] Corin | Securing data accountability in decentralized systems. On the Move to Meaningful Internet Systems[END_REF]. Time stamping and signature mechanisms are used to establish evidence of communication and to bind a usage policy to the communicated objects. Then, whenever an auditing process is started by any of the communicating parties, the other parties are obliged to provide evidence that their usage is in accordance with the policies agreed upon. The communication protocol with timestamps assures that honest parties do have such evidence.

Pretschner et al. [START_REF] Pretschner | Distributed usage control[END_REF] argue that many high-level obligations may not be controllable by the content provider. They therefore separate between controllable and uncontrollable obligations, and further introduce the weaker notion of observable obligations. Unobservable obligations are weakened and adapted until they become observable, and hence subject to monitoring and auditing. Therefore, rather than controlling obligations fulfilment, the content owner can observe (indications of) policy violations. Examples include watermarking content to detect unauthorised redistribution. Pretschener et al. [START_REF] Pretschner | Distributed usage control[END_REF] lets the server (content provider) employ traditional access control first to determine applicable rules and authorisations. In the next step, the consumer is provided with the set of provisional actions that must be taken prior to access and the obligations that must be fulfilled during or after usage of the content. Subsequently the consumer must provide evidence that the provisional actions have been taken and that he has committed himself to the obligations and compensations. Compensations, or sanctions as they are termed, is also proposed formally in [START_REF] Brunel | Security policy compliance with violation management[END_REF]. The authors show how a system may violate certain rules in a policy and still be compliant with the policy through fulfilling a set of sanctions. The sanctions are specified for a rule in the policy and therefore also known to the user prior to a policy violation. APPLE (A Posteriori PoLicy Enforcement) is based on the same principles but utilises Auditing Authorities to automatically check the policy adherence of users [START_REF] Etalle | A posteriori compliance control[END_REF]. The Authorities either selects documents or objects they have become aware of, or selects one randomly. While some policy violations may go undetected, the authors argue that the possibility of being caught and held accountable will in some cases deter significant violations [START_REF] Etalle | A posteriori compliance control[END_REF].

Cederquist et al. [START_REF] Cederquist | Auditbased compliance control[END_REF] attempt to handle the problem of administrative policies in usage control. That is, who is authorised to specify and change the policy guarding a specific piece of information. In a fully decentralised system based on discretionary policies this is next to impossible, especially since it may be difficult to assess who is the owner of data after multiple changes by others. The solution by Cederquist et al. is to require that users are accountable for their actions. Such that if Alice changes a policy regarding a document before sending it to Bob, then Alice is held accountable for the change. In the event that the change is unauthorised, Bob will be able to prove that he is not to blame for the unauthorised change. Thus, the basic action required on the receiver side is to ensure that the sender is accountable. The authors also point out that as a consequence, users may perform deliberate policy infringements while accepting full responsibility for it.

Monitoring Hilty et al. [START_REF] Hilty | Monitors for usage control[END_REF][START_REF] Pretschner | Usage control in service-oriented architectures[END_REF] propose an active monitoring approach where the client-side monitoring component signals to a server-side enforcement mechanism whenever obligations have been fulfilled. Hence, if information some infor-mation should be deleted within 30 days, the monitoring component signals to the provider at time of deletion and ends the monitoring of the information object. In the event that the information is not deleted, the monitoring component signals a policy violation to the provider.

Trust-based enforcement

Trust has been extensively studied in computer science and have numerous application areas. Here we describe how trust assessments may be used for enforcement purposes.

Krautsevich et al. proposes to use trust management as means to grant usage privileges to users [START_REF] Krautsevich | Usage control, risk and trust[END_REF]. The idea is to utilise trust relationships and trust propagation between users and content providers to determine a usage control decision between parties that are mutually untrusted. Hence a user A with a credential issued by some other user or provider B may be given usage rights to a resource controlled by C if C trusts B.

Nyre and Jaatun also propose a trust-based enforcement strategy, but in their case the trust denotes whether the content receiver may be trusted to adhere to the usage policy [START_REF] Nyre | A probabilistic approach to information control[END_REF]. Further, they specify a method to compute the probability that the receiver will enforce the policy and use this probability for content dissemination decisions.

Testing and evaluation

To answer the second research question, we aimed to determine what evidence are provided to support the appropriateness of the proposed enforcement mechanisms. Here we describe the quantitative testing and evaluation of the enforcement mechanisms we have described. We do not consider qualitative selfassessments as evidence of appropriateness.

Performance analysis Performance analysis is the predominant form of testing strategy employed and primarily aimed at identifying latency introduced by the enforcement mechanisms.

In [START_REF] Gheorghe | Enforcing ucon policies on the enterprise service bus[END_REF] the introduced round-trip latency said to be around 5000 µm of which the policy decision takes about 22 µm. Although the policy decision time is insignificant compared to the round-trip time, the lack of a neutral benchmark makes it difficult to assess wether the entire round-trip time is acceptable or not. Similar shortcomings are found in [START_REF] Hu | L-ucon: Towards layered access control with ucon[END_REF] where the read and write speeds are analysed for files of varying sizes and in [START_REF] Alam | Behavioral attestation for web services (BA4WS)[END_REF] where the attestation request is said to introduce a a latency of about five seconds. Since these values are not benchmarked to a system without the implemented enforcement mechanism, it is difficult to assess the appropriateness.

Djalaliev et al. do provide a benchmark of regular HTTP and TLS traffic and show that the modified TLS used for attestation only introduces an increase in CPU usage of about 20% [START_REF] Djalaliev | Secure web-based retrieval of documents with usage controls[END_REF]. The latency analysis demonstrates that usage controlled file retrieval introduces a penalty varying from 100% to 30% with increasing file sizes.

The UCLinux implementation in [START_REF] Kyle | Uclinux: a linux security module for trusted-computingbased usage controls enforcement[END_REF] is analysed to find the system boot latency and general usage latency. General usage latency was simulated through measuring the time needed to compile a Linux kernel since this involves several different file operations. The tests show that the boot process takes 9% longer to complete on UCLinux compared to regular Linux, whereas the file operations require some 10% more time to complete.

Usability testing Brustoloni et al. [START_REF] Brustoloni | Evaluating the usability of usage controls in electronic collaboration[END_REF] conduct an end-user test of their proposed system. The test seems to support their claim that performance is not significantly affected and that user awareness of unacceptable policies are considerably improved. However, there are only ten participants in the test all of which are students and only 50% have a computer science or engineering background despite the fact that the test has been designed with such professionals in mind. Further, the test seems to have no reference group and hence comparison of awareness is only done with the test group, something which could potentially bias the result. Although there is nothing to suggest that the enforcement mechanism is inappropriate, we find the low participation and the limited procedure not convincing enough for the mechanism to be deemed appropriate.

Analysis and discussion

In this section we attempt to analyse and generalise the strengths and limitations of the enforcement mechanisms we have described so far since space limitations prevent us from dwelling into the details of each solution.

Virtually all mechanisms for usage control assume the existence of a trusted module to ensure that enforcement cannot be evaded, yet none have discussed to any extent the practical problems of establishing and maintaining a trust infrastructure based on Trusted Computing Modules. Particularly since other considerably less complex security infrastructures, such as Public Key Infrastructures, have experienced only limited success [START_REF] Lopez | Why have public key infrastructures failed so far?[END_REF]. Although the benefit of usage control may be easier to identify, most of the reasons for PKI failure described in [START_REF] Lopez | Why have public key infrastructures failed so far?[END_REF] also apply to Trusted Computing. Perhaps a property-based approach to Trusted Platform Module could alleviate some of the complexity of using binary hashes of applications [START_REF] Korthaus | A practical property-based bootstrap architecture[END_REF]. We do however agree that TPMs and Trusted Computing-based approaches are the only means of guaranteeing enforcement on remote devices.

There are cases in which enforcement guarantees are not necessarily required, particularly in closed systems such as business environments where the predominant threat is end-users' lack of awareness. In such circumstances, perhaps a more lightweight approach could be adopted that is technically infeasible for the average user to circumvent, but without the cost of a hardware-based trust infrastructure. It seems that the RightsEnforcer [START_REF] Matson | The 'how' and 'why' of persistent information security[END_REF] is the only approach investigating along these lines.

Allowing policy violation may seem like a contradiction for a policy enforcer. Massacci [START_REF] Massacci | Infringo ergo sum: when will software engineering support infringements?[END_REF] argues that enforcement should be reasonable, and therefore should allowed to be circumvented in cases where there is a just cause. If users are accountable for their action, they may only be required to justify why the violation (e.g. authorisation given orally) such that penalties may be given in retrospect. Most of the audit-based approaches do offer the violation capability, but at the same time rely on previously described compensations to be carried out. Which in essence means that only exceptions that are identified in the policy are handled by the enforcer, and therefore the rigour of the policy is not reduced.

The perhaps most striking issue we have come across is the lack of empirical evidence of the enforcement mechanisms' appropriateness. This may be due to the fact that usage control enforcement is a relatively new research field and that formal models and prototypes showing technical feasibility is a prerequisite to be able to perform proper end-user tests. However, from the effort listed here we conclude that the formal and technical basis should be well in place to allow for more user centric enforcement strategies that properly balance the usability and the security provided.

Related work

There have been some reviews conducted previously. From the digital rights management perspective, Liu et al. [START_REF] Liu | Digital rights management for content distribution[END_REF] have conducted a survey on DRM technology but does not treat the more general case of usage control. The review by Pretschner et al. [START_REF] Pretschner | Usage control enforcement: Present and future[END_REF] is also on DRM technology, but is more focused on alternative use of such technology including privacy and business information protection. Four different DRM technologies are analysed and compared to a set of general usage control enforcement capabilities. The idea is to see whether DRM can be used for all regular consumer side enforcement. While the evaluated systems do vary to some degree, their main limitation is the lack of enforcement after rendering. In this paper, we consider enforcement of much more expressive policies than the simple content protection mechanisms of most commercially available products and services.

A recent survey by Lazouski et al. [START_REF] Lazouski | Usage control in computer security: A survey[END_REF] does however target usage control in general. The centre of gravity is the UCON model proposed by Park and Sandhu [START_REF] Park | The UCONABC usage control model[END_REF] such that other initiatives are described based on how they relate to this model. Formal models, architectures, enforcement strategies and implementations are discussed and some of the open challenges outlined. Contrary to this paper, enforcement is not considered throughly.

Conclusion

This paper has identified existing approaches to usage control enforcement as identified in research question RQ1. Despite the relatively short period of time since the term and concept of Usage Control was coined, there has been considerable efforts in establishing proper enforcement mechanisms. While formal models and prototype implementations have been, and still are necessary to demonstrate the technical feasibility of usage control enforcement, more effort is required in obtaining reliable empirical data on the usefulness and usability of these approaches. Therefore we are currently unable properly address research question RQ2 to judge particular approaches as more appropriate than others.

Figure 4 :

 4 Figure 4: Subject and system actions

denyaccess(s, o, r): rejects an access request of (s, o, r), performed by the system.

revokeaccess(s, o, r): revokes an ongoing access (s, o, r), performed by the system.[START_REF] Brunel | Security policy compliance with violation management[END_REF] Semantically, the action is a transition step from the original state with old value to new state with updated value. Here we simply say the action is true.


Wei Peng
email: wpeng@nudt.edu.cn

Zimu Li

Jinshu Su

Muwei Dong
email: mwdong@nudt.edu.cn

Evaluation of Topological Vulnerability of the Internet under Regional Failures

Keywords: network topology, vulnerability, regional failure, critical distance, algorithm

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

Introduction

Complex networks like the Internet play an important role in today's world. The society and our lives heavily depend on these networks. For example, most of data communications are accomplished through the Internet. However, as a fast-growing system, the Internet may become vulnerable to intrusions and failures since it integrates more and more components, services and functions. It is generally believed that the current Internet is not so robust or resilient to failures as a critical infrastructure. A breakdown of the Internet for a short while may result in the loss of a large fortune. Considering the importance and the central role of the Internet, its vulnerability has been studied from various aspects.

The topology of a network ranks foremost among all factors which influence the network vulnerability. During the past years, great efforts have been paid in evaluating the vulnerability of a network topology and finding efficient algorithms to enhance the robustness of a network. In most of the works, a network topology is studied as a pure graph without considering the geographical properties of nodes and links. The network vulnerability is often studied on the logical network topology instead of the physical network topology.

Network nodes or links in a large geographical area may fail to work during the outbreak of electric black-outs and natural disasters like earthquakes, floods and tornadoes. For example, the Taiwan Earthquake in December 2006 damages several undersea cable systems in Asia and the communications between many Asia sites and U.S. sites are disrupted for several ten minutes to hours later. Such regional failures have geographical locations and exhibit strong space correlation among network nodes and links. Therefore, the geographical distribution of a network will have great impact on its vulnerability on regional failures. It has been shown that complex networks including the Internet are resilient to independent random failures, but fragile to intentional attacks [START_REF] Doyle | The 'Robust Yet Fragile' Nature of the Internet[END_REF]. The vulnerability of the Internet under regional failures is still an open issue.

In this paper, we study the vulnerability of the Internet under large-scale regional failures using its city-level topology. A large-scale regional failure means that a significant number of network nodes or links located in a geographical area become unavailable due to natural disasters, electrical black-outs or terroristic attacks. By studying the vulnerability of the Internet in geographical space, we can understand the impact of the geographical properties of the Internet on regional failures. It also helps to identify not only the critical nodes and links, but also the critical area in the network. By the study, we will evaluate the importance of network nodes under regional failures and explore the necessary failure impact range to incur a certain level of degradation of network performance.

To achieve the goal, we develop a binary disk-shape regional failure model as a start. Then the concept of α-critical-distance is introduced where α is a given failure impact ratio. The properties of the mapping function from failure impact range to failure impact ratio is analyzed. Based on the properties, a polynomial time algorithm is proposed to calculate the minimal α-critical-distance given the impact ratio α and a network topology. We collects topology data sets from the Internet and annotate network nodes with geographical locations. Using the real topology data, we evaluate and compare the network vulnerability of several countries. The experimental results reveal the differences among the studied topologies. We also find that smaller failure impact distances are required when the network efficiency [START_REF] Latora | Efficient Behavior of Small-World Networks[END_REF] is used as the network performance metric than the giant component size.

The rest of the paper is organized as follows. Section 2 presents a short survey on the related work. Section 3 describes the vulnerability model and the algorithm to find the minimal α-critical-distance. The experimental results using real topology data are presented in section 5. We conclude the paper at last.

Related Work

Numerous efforts have been devoted to the study of the network vulnerability, including proposing vulnerability measures and methods to evaluate the vulner-ability of a network, proposing measures and methods to find critical nodes and links in a network. However, few works have explored the network vulnerability issues under geographical correlated failures.

Basic network vulnerability measures are derived from global graph properties like the number of nodes and edges, the lengths of pairwise shortest paths. These measurement criteria include average or characteristic path length, giant component size, network efficiency [START_REF] Latora | Efficient Behavior of Small-World Networks[END_REF], N-Q measure [START_REF] Nagurney | A Network Efficiency Measure with Application to Critical Infrastructure Networks[END_REF], algebraic connectivity and natural connectivity [START_REF] Wu | Natural Connectivity of Complex Networks[END_REF]. Based on these measures, the vulnerabilities of networks with different characteristics are investigated. For example, the giant component size is widely used in the research of complex networks. It is shown that scale-free complex networks including the Internet is vulnerable to intentional attacks with their power-law features [START_REF] Doyle | The 'Robust Yet Fragile' Nature of the Internet[END_REF]. The algebraic connectivity is used to study the robustness of networks of three types subject to random node and link failures [START_REF] Jamakovic | Influence of the network structure on robustness[END_REF]. Dinh et al. [START_REF] Dinh | On New Approaches of Assessing Network Vulnerability: Hardness and Approximation[END_REF] investigated the measure called pairwise connectivity and formulate the vulnerability assessment problem as a NP-complete problem and present pseudo-approximation algorithms to detect the set of critical nodes and critical edges.

To assess the importance of nodes on the vulnerability of a network, local nodal measures are proposed, including degree centrality, betweenness centrality and closeness centrality [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF]. In [START_REF] Wehmuth | Distributed Algorithm to Locate Critical Nodes to Network Robustness based on Spectral Analysis[END_REF], a distributed algorithm for locating critical nodes is proposed based on spectral analysis. Kermarrec et al. [START_REF] Kermarrec | Second order centrality: Distributed assessment of nodes criticity in complex networks[END_REF] propose a measurement called second order centrality and use random walk to assess node criticality in a distributed manner. Arulselvan et al. [START_REF] Arulselvan | Detecting Critical Nodes in Sparse Graphs[END_REF] have shown that the critical node problem in a graph is a NP-complete problem and proposed a heuristic algorithm for it. Other approaches consider logical network attacks [START_REF] Crescenzo | Detecting Anomalies in Active Insider Stepping Stone Attacks[END_REF] and the role of humans in system security models [START_REF] Pieters | Representing Humans in System Security Models: An Actor-Network Approach[END_REF].

All above approaches aim at the logical network topology, without considering the geographical properties and correlated regional failure effects.

Hansen et al. [START_REF] Hansen | Resilient Routing Layers for Network Disaster Planning[END_REF] studied the network resilience under regional failures at routing layer. Grubesic et al. [START_REF] Grubesic | Vital Nodes, Interconnected Infrastructures, and the Geographies of Network Survivability[END_REF] Studied the Node Removal Impact Problem in the geographical context. In [START_REF] Neumayer | Assessing the Impact of Geographically Correlated Network Failures[END_REF], the vulnerability of networks is assessed in geographical space by modeling the physical network as a bipartite graph. The location of geographical disasters that maximize the capacity of disconnected links is studied. Specifically, a polynomial time algorithm for finding the location of a vertical line segment cut is proposed. The problem is further studied by applying geometric probability techniques to calculate network performance measures on a random line-cut [START_REF] Neumayer | Network Reliability With Geographically Correlated Failures[END_REF]. Agarwal et al. [START_REF] Agarwal | The Resilience of WDM Networks to Probabilistic Geographical Failures[END_REF] establish a probabilistic geographical failure model and use computational geometric tools to identify vulnerable points within a network. Their algorithms are applied in three optical WDM networks within the continental USA. In [START_REF] Bassiri | Network Survivability in Large-Scale Regional Failure Scenarios[END_REF], both nodes and links located in failure impact area are assumed to be down after a regional failure. Using the European network COST-239 as test network, the authors present some preliminary results by simulating regional failures with three impact ranges.

The previous works try to find the optimal location of geographical failures that maximize the failure impact with a given failure impact range. In contrast with these works, we try to find the optimal regional failure area or the weakest portion of a network that decreases the network performance to a threshold value.

Vulnerability Evaluation Method

3.1 Regional Failure Model Regional failures belong to the category of multiple-failure scenarios and a largescale regional failure often occurs in a geographical area where nodes or links may crash or fail to work. A regional failure can affect only a small part of the network, but it can also damage the network severely if it happens in a crucial area and affects enough number of network nodes or links. The area where a regional failure takes effects is defined as the failure area. A regional failure is described by its failure area and the failure probability of nodes and links in the area.

The failure area of a regional failure can be in any shapes. For simplicity, we define a binary disk-shape failure model which is characterized by its epicenter position and the failure impact range in a 2-dimension space. Definition 1: The binary disk-shape failure model is defined as (L0, r), where L0 is the location of the failure center and r is the failure impact range. For node i, if its distance to the failure center is measured by dd i , the state of node i after the failure will be:

s i = 0 , dd i ≤ r 1 , else (1)
The state 0 means that the node is down while the state 1 represents that the node is still up. The failure model defined above is deterministic, while one could use more complex models like the probability failure model in [START_REF] Agarwal | The Resilience of WDM Networks to Probabilistic Geographical Failures[END_REF]. In many cases, a simple model with less complexity can provide enough information for network operators, so we focus on the binary disk-shape failure model in this paper. Our model is similar to that in [START_REF] Bassiri | Network Survivability in Large-Scale Regional Failure Scenarios[END_REF] and the difference is that we do not consider links traversing the failure area.

Vulnerability Measurement

Many statistical metrics have been proposed to quantify the failure impact. In this paper, we consider the following performance metrics:

-S: giant component size, which is the number of nodes in the largest connected sub-graph after a failure; -E: network efficiency [START_REF] Latora | Efficient Behavior of Small-World Networks[END_REF], which is defined as the sum of inverse values of all shortest path lengths in a graph. Given a graph G, its network efficiency is defined as

E(G) = 1 n(n -1) i =j∈G 1 d i,j ( 2
)
where n is the number of nodes in G and d i,j is the shortest path length from node i to node j.

The giant component size is widely used in assessing the robustness of complex networks under random failures and intentional attacks. It can characterize network partitioning to some extent. However, if the network remains connected after a failure, it will fail to quantify the impact of the failure. Comparatively, the change of network topology can be revealed by the network efficiency since it will decrease with the increasing of path lengths after a failure. So it is better to assess the performance degradation using network efficiency than giant component size if the computational complexity is bearable.

Given the parameters of a failure and a network topology, we can calculate the performance metrics before and after the failure. The evaluation of the vulnerability of a network is the reverse problem. That is, we need to find the minimal failure impact range to break down a network and the crucial portion of the network. The weakest area in a network is the Achilles' heels of the network.

To achieve the goal, we introduce the concept of α-critical-distance which is the minimal impact range in a regional failure when the network performance metric is reduced to α times of the initial value before the failure. α (0 ≤ α ≤ 1) is called the impact ratio. Like the approach in [START_REF] Bassiri | Network Survivability in Large-Scale Regional Failure Scenarios[END_REF], we assume that the epicenter is the location of one node in the network. For node i, we use the mapping F i to define the relationship between the impact ratio α and the impact range r.

Formally, α = F i (r) (3)
The reverse mapping of F is denoted as 1) . Definition 2: Given α, the α-critical-distance of node i is the minimal impact range r α i when node i locates at the epicenter. That is,

F i(-
r α i = min F i(-1) (α) (4)
The mapping F i of node i has the following properties. Property 1: For any r > 0, 0 ≤ F i (r) ≤ 1. Property 2 (Monotonicity): If r 1 > r 2 , then F i (r 1 ) ≤ F i (r 2 ). Property 3: If the maximal distance from node i to any other nodes in the network is d max i , then for any r ≥ d max i , F i (r) = 0. The property 3 means that all nodes will go down if the failure impact range covers all nodes in the network. The network performance is measured as zero when all nodes go down or isolated and the network is totally unavailable.

Let the distance from node i to node j be d i,j , 1 ≤ j ≤ n, j = i. We sort the distances from node i to other nodes in ascending order. Let the sorted distances be d i,k1 ≤ d i,k2 ≤ . . . ≤ d i,kn-1 . And we assume that nodes co-located with node i on the same position will be down when the failure impact range r = 0. Based on the property 4, we can get the conclusion that there will be at most n distinct values of α for each F i . Property 5:

Property 4: (1) If d i,kj ≤ r < d i,kj+1 , 1 ≤ j ≤ (n -2), then F i (r) = F i (d i,kj ); (2) if 0 ≤ r < d i,k1 , then F i (r) = F i (0); (3) if r ≥ d i,kn-1 , then F i (r) = F i (d i,kn-1 ) = 0.
if p > q, F i (d i,kp ) ≤ F i (d i,kq ).
Figure 1 is an example to illustrate the Property 4 and 5. In fact, the mapping F i is a monotonic step-decreasing function of failure impact range r.

For node i, let F i p = F i (d i,kp ) for short. Based on the sorted distances (d i,k1 , d i,k2 , . . . , d i,kn-1 ), we define E i p as the sequence of node i followed by its p nearest nodes. Definition 3: The p-node-sequence of node i is defined as

E i p = (i, k 1 , k 2 , . . . , k p ). The complementary p-node-sequence is defined as CE i p = (k p+1 , . . . , k n-1 ). If a node v is in the p-node-sequence, it is denoted as v ∈ E i p . If for any v ∈ E i
p and any u ∈ E j p , u ∈ E i p and v ∈ E j p , then we say E i p = E j p . In such a case, the regional failure centered at node i with the impact range d i,kp will take the same effects on the network as the failure centered at node j with the impact range d j,kp . Property 6: For any p, 1 ≤ p ≤ (n -1), if E i p = E j p , then F i p = F j p . Property 7: If the complementary p-node-sequence CE i p and CE j p have the same node sequence, then for any m, (p + 1) ≤ m ≤ (n -1), F i m = F j m . Property 8: For any node i and j, max 0, (r α j -d i,j ) ≤ r α i ≤ (r α j + d i,j ) and max {0, (r α i -d i,j )} ≤ r α j ≤ (r α i + d i,j ). Property 9: For any node i, max 1≤j≤n 0, (r α j -

d i,j ) ≤ r α i ≤ min 1≤j≤n (r α j + d i,j ).
Property 7 is a special case of Property 6, because if CE i p and CE j p have the same node sequence, then for any m, (p + 1) ≤ m ≤ (n -1), E i m = E j m . Property 8 relates the α-critical-distances of two nodes with the distance between them. Property 9 can be induced from Property 8 directly.

For different values of α, a node will have different α-critical-distance values. Given the value of α, we can assess the importance of the location of a node with its α-critical-distance. Smaller the α-critical-distance is, more important the node location is. Therefore, we evaluate the vulnerability of a network by finding the node with the smallest α-critical-distance in the network.

Finding Minimal α-critical-distance

Under regional failure scenarios, the node having the minimal α-critical-distance is called the critical node of the network. The problem of finding the critical node of a network can be described as:

Given a network G and α, find i s.t. r α i = min r α j , 1 ≤ j ≤ n Because a node has n distinct values of α at most, the α-critical-distance of node i can be computed by enumerating all n possible cases. The time complexity of computing r α j will be O(n * T ) and the worst time complexity of the problem would be O(n 2 * T ). Here T is the time complexity to calculate the mapping F i (r) with given failure impact range r. The time to compute the giant component size is O(m) where m is the number of edges in the graph. The time to compute the network efficiency is O(n 3 ). Thus, the worst time complexity of the problem would be O(mn 2 ) and O(n 5 ), respectively. For large-scale networks, it will be time-costly to find critical nodes in a network. Because the α-critical-distance of a node is related to others according to Property 8, we can use the results computed in previous steps to reduce the time complexity. Here we propose a fast algorithm to find K minimal α-criticaldistance values. The input and output variables are summarized in Table 1.

The algorithm calculates the α-critical-distance for each node iteratively. In step 2 and step 3, the algorithm finds the lower bound and the upper bound of α-critical-distance that node i can take. According to Property 9, the lower and upper bounds can be computed with the α-critical-distances of other nodes found in previous steps. Then the set of candidate values of α-critical-distance is generated by selecting nodes which distances fall into the bounds. The procedure sortCandidateDistances(rset) sorts the candidate distance set rset in ascending order. The procedure binarySearch(G, i, rset) finds the α-critical-distance of node i by applying the binary search method on the candidate distance set rset. After the α-critical-distance values of all nodes are found, the procedure sortCriticalDistances(M, K) sorts the values in ascending order and outputs the first K values.

By using the binary search method, the time complexity to find the α-criticaldistance of a node can be reduced from O(n * T ) to O(log 2 n * T ). Both the step 8 and step 11 have the worst-case time complexity of O(n 2 ), e.g., if the Quicksort algorithm is applied. Thereby, the time complexity of the algorithm will be O(mnlog 2 n + n 3 + n 2 )) and O(n 4 log 2 n + n 3 + n 2 ), if the giant component size and the network efficiency are used as performance metrics respectively.

Algorithm 1: Find K minimal α-critical-distances 1: for i = 1 to n do 2: d min = max 1≤j≤(i-1) {0, M [j] -d i,j };
3:

d max = min 1≤j≤(i-1) {M [j] + d i,j }; 4: rset = ∅; 5: for j = 1 to n do 6: if d min ≤ d i,j ≤ d max then 7: rset = rset ∪ {d i,j }; 8:
end for 9: sortCandidateDistances(rset); 10: M [i] = binarySearch(G, i, rset); 11: end for 12: sortCriticalDistances(M, K); 4 Computational Results

Data Sets

To study the vulnerability of the Internet topology and evaluate the algorithm proposed in the above section, we collect some online data sets. Since an autonomous system (AS) may span across a large geographical area, the AS-level Internet topology is not appropriate for the purpose of this study. The routerlevel Internet topology is ideal for the study. However, there are few available data sets and a lot of links are missing in the public data sets due to privacy issues and limitations of network measurement methods. Instead, we use the city-level Internet topology in this paper.

The data sets come from DIMES [START_REF]The DIMES project[END_REF]. In the city-level topology data sets given by DIMES, the data set of July 2009 has the largest number of nodes and links. We extract the city-level topology from it for several countries, including United Kingdom (UK), Japan (JP), India (IN) and China (CN). The location information for each city in the original data of DIMES lacks precision, so we assign each city with the longitude and latitude looked up from the data provided by MaxMind [20]. Because many cities in the original topology have the same coordinates, we merge them into one city and make the resultant city-level topology compact. We use abbreviation of the country name to name the topology data set for each country. The basic attributes of the topology data sets are shown in Table 2. It should be noted that the topology data set is just a snapshot of the Internet's dynamic structure and the degree of incompleteness may vary greatly for different countries.

Evaluation of the Proposed Algorithm

We evaluate the proposed algorithm at first. The giant component size is used as the performance metric. To demonstrate the efficiency of the optimization operations using distance bounds (step 2-9 in algorithm 1), we compare the algorithm with and without the optimization steps. If the optimization steps are not applied, all distance values will be used in step 10, e.g., rset={d i,j , 1 ≤ j ≤ n}. Since computing the impact ratio with a given failure area takes the longest time, we use the number of function calls to evaluate the algorithm performance.

The performance improved ratio (PIR) is defined as:

P IR = C orig -C opt C orig (5)
where C orig is the number of function calls without optimization steps and C opt is that with optimization. Figure 2 demonstrates the performance of the algorithm. It is shown that the algorithm performance can be improved with the optimization steps for different network topologies. Normally, about half of the function calls can be saved, while 45% function calls can be saved in the worst case. Besides, when the impact ratio (α) is approaching its extreme value (0 or 1), the algorithm have better performance than the case when α is in the middle of its value range.

Evaluation of the Topologies

We use the proposed algorithm to find the α-critical-distances for different values of α. Figure 3 shows that with the increasing of α, the α-critical-distance decreases. For different countries, different failure impact ranges are required to get the impact ratio. When α is less than 0.6, India and China have the greater α-critical-distance values than UK and Japan. It is reasonable since large failure impact ranges are required for countries with large acreage. Japan has longer critical distances than UK for the same impact ratio. Sice the topology snapshot of Japan has less nodes but higher node degrees than the topology of UK, the former is more resilient to disk-shape regional failures than the latter.

Table 3 shows the top 10 minimal α-critical-distances when α=0.5. It is shown that a regional failure with a radius of 120 Kilometers in UK may lead to half of network nodes disconnected to others. With network efficiency as the performance metric, the algorithm finds the α-critical-distances for networks of UK and Japan. The results are shown in Figure 4. The suffix '-gc' and '-ne' are used to differentiate the curves using giant component size and network efficiency as the performance metrics respectively. Noteworthy differences can be observed. When the network efficiency is used, the network performance degrades even when regional failures have a small impact range. For example, in the worst case, a regional failure with an impact range of 29Km can lead to the network efficiency of UK's network reduced to half of the normal performance. According to the definition of the network efficiency, it is more sensitive to the change of a network topology than the giant component size. Thus, in the context of regional failures, it is easy to harm the network efficiency of a network with small failure impact range.

Conclusion

In this paper, we introduce the concept of α-critical-distance for the purpose of evaluating vulnerability of networks under regional failures. We define a binary disk-shape regional failure model and study the properties of the mapping from failure impact range to failure impact ratio. It is shown that the mapping is a monotonic step-decreasing function. Based on the theoretic analysis, we propose an algorithm to compute the α-critical-distance for a given network topology and α. Using real topology data sets, we run the algorithm to evaluate the vulnerability of city-level Internet topologies for several countries. The computational results reveal the differences of network vulnerabilities among different countries and the differences when different network performance metrics are used.

Our work provides a new way to assess the network vulnerability under largescale regional failures. The future work includes studying the network vulnerability under regional failures which take effects both on nodes and edges, correlated analysis of critical distances and node densities, and so on.

Fig. 1 .

 1 Fig. 1. Illustration of Property 4 and 5

Fig. 2 .

 2 Fig. 2. Improved ratio with optimization

Table 1 .

 1 Variables of Algorithm 1

	Input Variable	Description
	G	network represented by an undirected graph
	n	the number of nodes in G
	α	impact ratio of the network performance
	K	the number of minimal α-critical-distances
	Output Variable	Description
	M	the vector of α-critical-distances,
		M [i] is the i-th α-critical-distance
	Temporary Variable Description
	di,j	geometric distance between node i and node j
	dmin	minimal value of α-critical-distance of a node
	dmax	maximal value of α-critical-distance of a node
	rset	the set of candidate values of α-critical-distance

Table 2 .

 2 Basic Attributes of Topology Data Sets

	Data Node	Edge	Average Average
	Set Number Number Degree Path Length
	UK 1085	4044	7.454378 2.371940
	JP 117	856	14.632479 1.915119
	IN 349	1101	6.309456 2.225933
	CN 922	2002	4.342733 2.900891

Table 3 .

 3 Top 10 Critical Distances (Km) (α=0.5)

	rank UK	Japan	India	China

Acknowledgments. The work is supported by the grants from the National Natural Science Foundation of China under grant No.61070199 and 60873214, and the National 973 Grand Fundamental Research Program 2009CB320503.