The present invention relates to a controlled discovery of Grid services based on semantic annotation of access control policies using ontologies and semantic rules. In particular, the present invention relates to a method and a system for controlled discovery in grid computing environment, in particular to an environment where service instances are

(semi)automatically discovered.

BACKGROUND OF THE INVENTION

Grid technologies or Grid computing (or the use of a computational grid) is the application of several computers to a single problem at the same time - usually to a scientific or technical problem - that requires a great number of computer processing cycles or access to large amounts of data.

For instance, the SIMDAT (Data Grids for Process and Product Development using Numerical Simulation and Knowledge Discovery, http://www.simdat.org) is an European Commission 1ST (Information Society Technology) FP6 (the sixth Framework Programme) project, which aims at developing generic Grid technologies for the solution of complex application problems hi four industrial application sectors: Automotive, Pharma, Aerospace and Meteorology (see C. Upstill, and M. J. Boniface, "SIMDAT," CTWatch Quarterly, vol. 1, no. 4, pp. 16-24, Nov. 2005).

In the SIMDAT Pharma sector, the focus is on the provision of a global knowledge Grid for life sciences, which is able to integrate thousands of Grid enabled biological data services and analysis services to support collaboration between research institutes (e.g., within EMBnet, http://www.embnet.org/), and in particular, between businesses (e.g., between Inpharmatica Ltd., http://www.inpharmaticaco.uk/, and GlaxoSmithKline, http://www.gsk.com/). These biological services are typically provided by several famous bioinformatics tools including SRS (Sequence Retrieval System; see T. Etzold, A. Ulyanov, and P. Argos, "SRS: information retrieval system for molecular biology data banks," Methods Enzymol., vol. 266, pp.l 14-142, 1996), MRS (Maarten's Retrieval System; see M.L. Hekkelman, and G. Vriend, "MRS: A fast and compact retrieval system for biological data," Nucleic Acids Research, vol. 33, ρp.766-769, 2005), BLAST (Basic Local Alignment Search Tool; see S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and DJ. Lipman, "Basic local alignment search tool," J. of MoI. Biology, vol. 215, pp. 403-410, 1990), InterProScan (see E. M. Zdobnov, and R. Apweiler, "InterProScan - an integration platform for the signature- recognition methods in InterPro," Bioinformatics, vol. 17, no.9, pp.847-855, 2001), and EMBOSS (European Molecular Biology Open Software Suite; see P. Rice, I. Longden, and A. Bleasby, "EMBOSS: the European molecular biology open software suite," Trends Genet., vol. 16, no. 6, pp.276-283, 2000), etc. In SIMDAT, they are further wrapped through an industry-strength Grid middleware GRIA (Grid Resources for Industrial Applications; see M. Surridge, S. Taylor, D. De Roure, and E. Zaluska, "Experiences with GRIA- Industrial Applications on a Web Services Grid," in Proc. 1st Int. Conf. on e-Science and Grid Computing, Melbourne, Australia, Dec. 2005, pp. 98-105), thus possess enhanced capability in security, QoS (Quality of Service), and business management. With regard to the security, due to intellectual property requirements, most of biological services in SIMDAT are secured through an Access Control (AC) mechanism, i.e., PBAC (Process based Access Control), which can control users' access to services and their different operations in terms of user credentials and pre-defined service AC policies.

As the service discovery is rather challenging in SIMDAT, the inventors of the present invention previously designed and implemented a semantics enabled service discovery framework, which is able to assist users in (semi-) automatically discovering and selecting service instances based on different service features such as service I/O (Input/Output), service classification, and service category etc (see Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SrMDAT Pharma Grid", in J. IEEE Trans, on Information Technology in Biomedicine).

However, as so far the service discovery framework has not yet taken into account services' security configuration, the controlled discovery, i.e., AC policy based service discovery, is not yet addressed.

As a result, the current service discovery result set is sometimes "incorrect", including service instances which users are indeed not allowed to access. This is particularly problematic in SIMDAT. As SIMDAT is a workflow centered Grid computing environment wherein service instances for building a biological workflow are (semi-) automatically discovered and selected through the service discovery framework (see e.g.: Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid", in J. IEEE Trans, on Information Technology in Biomedicine, and M. Ghanem, N. Azam, M.Boniface, and J. Ferris, "Grid-Enabled Workflows for Industrial Product Design," in Proc. 2nd IEEE International Conference on e-Science and Grid Computing (e-Science'06), Amsterdam, The Netherlands, Dec. 2006, pp.96), functionally executable workflow may ultimately fail due to AC restrictions on specific users from a specific service instance. This may lead to a chain of problems specific to the workflow and Grid, e.g., accounting problems, etc.

In the following a typical Process Based Access Control (PBAC) over Biological Grid Services, in the particular on the basis of SIMDAT Pharma Grid will be discussed in detail with regard to Fig.1.

The access control is the key security component in the SIMDAT Pharma Grid to protect biological services against unauthorized access. It defines sets of restrictions, i.e., AC policies, on what users can do, which resources they have access to, and what operations they are allowed to perform. In SIMDAT, the access control is enforced through the PBAC module of the GRIA middleware (see e.g.: M. Surridge, S. Taylor, D. De Roure, and E. Zaluska, "Experiences with GRIA- Industrial Applications on a Web Services Grid," in Proc. 1st Int. Conf. on e-Science and Grid Computing, Melbourne, Australia, Dec. 2005, pp. 98- 105).

The PBAC is a dynamic AC mechanism for stateful Web/Grid services, which provides a context and process-based method of controlling access to defined resources in a remotely accessed system. The PBAC model is derived from the most commonly used AC model, RBAC (Role Based Access Control; see R. S. Sandhu, EJ. Coyne, H.L. Feinstein, and CE. Youman, "Role-Based Access Control Models", IEEE Computer 29(2): 38-47, 1996), with several enhancements in functionality to address peculiarity of AC components in a Grid computing environment, in particular contextualization. As all AC components in PBAC are subject to specific contexts, the PBAC model is more complex than RBAC, possessing more AC components and relationships between them.

Figure 1 illustrates a typical PBAC model, which comprises of the following components as well as relationships among these components.

The components Resources (R), States (S), and Operations (O):

As an AC model specifically designed for a WSRF (Web Service Resource Framework; see OASIS WSRF TC, "Web Service Resource Framework") compliant Grid middleware, the principal component of the PBAC model is resource (R), which is originally defined in the WSRF specification. Each resource has a process state (S), and different operations (O) on the resource are possible in different states. In general, Grid services create resources and allow users (U) to perform operations (O) with them. When a user (U) tries to access a resource (R) by invoking an operation (O) on a service, the PBAC module checks that the user (U) is authorized to perform the requested operation (O) on that resource (R). It should be noted that each service itself can be a resource (R). Operations (O) which are not directed at a specific resource (R) are treated as operations on the service resource, thus also subject to access control by PBAC.

The components Users (U), and Process Roles (P):

Each possible operation (O) of a given state (S) has a set of process roles (P) which may invoke it. Each user (U) has a set of process roles (P) for the resource (R). The user (U) can only invoke the operation (O) if the intersection of these two sets is non-empty, i.e., if they have one of the permitted roles.

The user authentication in PBAC is typically based on PKI (Public Key Infrastructure). Currently, two authentication schemes are preferably supported by PBAC, respectively X.509 certificate (International Telecommunication Union, X.509:Information technology - Open Systems Interconnection - The Directory: Public-key and attribute certificate frameworks) and SAML (Security Assertion Markup Language; see OASIS Security Services (SAML) TC, "Security Assertion Markup Language"; http://www.oasis-open.org/committees/security/) assertions.

PBAC, however, does not define AC policies directly based on users' authenticated attributes, but based on process roles. In other words, the inventors of the present invention noted that the PBAC model is essentially independent of user authentication schemes.

According to the present invention, the "user credential" component and "credential assignment" relationship are intentionally excluded from the PBAC model, though they are apparently indispensable to the PBAC enforcement.

The relationships User Assignment (UA), Permission Assignment (PA), Operation

Assignment (OA), and State Assignment (SA)

User Assignment or User-Role Assignment (UA ε U x P) represents a many-to-many user (U) to process role (R) assignment relation. Generally, UA tends to change over time, i.e., it is preferred to dynamically define and adjust UA (see "cursive font" in Fig. 1). Permission Assignment or Role-Operation Permission Assignment (PA ^e P x O), State

Assignment or State-Operation Assignment (SA e S x O), and Operation Assignment or Operation-Resource Assignment (OA ^e O x R) respectively represents a many-to-many operation (O) to process role (P) assignment relation, a many-to-many resource state (S) to operation (O) assignment relation, and a many-to-many resource (R) to operation (O) assignment relation. These relations are typically relatively stable (see "normal font" in Fig. 1), tending to change less often after the service has been developed and its typical usage has been determined (often called "stable part").

As a typical derivative of the RBAC, the PBAC does not define AC policies directly based on users' authenticated attributes, but based on process roles. Each process role (P) is defined only with reference to service interactions. When an interaction process starts, a set of subject criteria are defined for each process role (P) that relates to that interaction. Thus,

PBAC AC policies can logically be separated into two parts:

(1) static AC policies, which define permitted operations (O) per state (S) and process roles (P); and

(2) dynamic AC policies, which define subject criteria for process roles (P).

In correspondence to the PBAC model illustrated in Fig.l, the static AC policies include PA, SA and OA (shown in normal font), while the dynamic policies principally consist of UA (shown in cursive font). For a service deployed through the GRIA middleware, its static AC policies are typically configured in the form of an XML file during the service deployment. These policies can then dynamically be adjusted during the service run-time, but rather unlikely.

On the other hand, the dynamic AC policies are typically defined and adjusted during the lifetime of the resource through a set of "match rules" applicable to each resource. At present, GRIA supports the use of two types of match rules to dynamically define UA:

(i) "sufficient rules" and (ii) "deny rules" (see for example Table 2 below). For a user to have a particular process role, they must match at least one "sufficient rule" and no "deny rules"

(see e.g.: M. Surridge, S. Taylor, D. De Roure, and E. Zaluska, "Experiences with GRIA-

Industrial Applications on a Web Services Grid," in Proc. 1st Int. Conf. on e-Science and Grid Computing, Melbourne, Australia, Dec. 2005, pp. 98-105). GRIA provides typically five rule patterns to support the definition of both sufficient and deny rules:

Subject DN is ... : This rule pattern will only match a user with that exact Distinguished Name (DN), signed by a particular CA (Certificate Authority).

Certificate is signed by ... : This rule pattern will match anyone whose identity is vouched for by a particular CA.

Has SAML attribute ... : This rule pattern will match anyone with a SAML assertion signed by the issuer asserting that they have the specified attribute. Member of group ... : This rule pattern will match anyone who is a member of the group. Each group itself is a resource, and has its own set of match rules to determine who is a member.

Anyone: This rule pattern will simply match anyone at all. In the following, the definition of PBAC based service AC policies based on a case study of a practical biological service deployed in the SIMDAT Pharma Grid will be discussed in more detail.

GeneMark™ is a protein prediction tool for evaluating the protein-coding potential of a

DNA sequence by using Markov models of coding and non-coding regions for various prokaryotic and eukaryotic species (see e.g. Lomsadze A., Ter-Hovhannisyan V., Chernoff Y. and Borodovsky M.,"Gene identification in novel eukaryotic genomes by self-training algorithm", Nucleic Acids Research, 2005, Vol. 33, No. 20, 6494-6506). In the SIMDAT

Pharma Grid, GeneMark™ is deployed by different institutions as a GRIA service through a

GRIA wrapper program. This wrapper program typically exposes the whole sets of GeneMark™ functionalities as four service operations:

^■ getAnalysisOptions: This operation enables users to list non graphic-related options like files to upload, threshold values, etc.

^■ getGraphicOptions: This operation enables users to list graphic-oriented options like output formats required (postscript, pdf) etc. ■ makePersonalizedMatrix: This operation enables users to generate its own gene- finding matrices for specific species.

^■ runAnalysis: This operation enables users to run the GeneMark™ analysis.

The AC policies defined for the GeneMark™ service are basically intended to protect its license based usage. As GeneMark™ is free for academic users, but requires a license to be used for industrial users, the service AC policies have to be defined at lease for differentiating between these two groups of users. Going a step further, some institutions may also want to impose more fine-grained access control over different operations of the GeneMark™ service. Taking the GeneMark™ service instance installed in ULB (Universite libre de Bruxelles) as an example, whereas other GeneMark™ service operations have no specific AC restrictions on licensed users, the "makePersonalizedMatrix" operation only permits the access from (licensed) expert users. The following Table 1 and Table 2 respectively show a simplified definition of static and dynamic AC policies for the ULB GeneMark™ service instance.

Table 1: Static AC policies, i.e., PA, SA, and OA defined for the ULB

GeneMark™ service instance.

Rule l If a user has the SAML attribute (Department = "Bioinformatics"), and is signed by the ULB CA, the user has the process role of User.

Rule 2 If a user's certificate is signed by the ULB CA, the user has the process role of ExpertUser

Rule 3 If a user's certificate has the subject DN of "Richard Katnuzinzi" and is signed by the ULB CA, the user does not have the process role of ExpertUser.

Rule 4 If a user's certificate is signed by the NEC CA, the user has the process role of User.

Rule 5 If a user's certificate has the subject DN of "Changtao Qu" and is signed by the NEC CA, the user does not have the process role of User.

Table 2: Dynamic AC policies, i.e., UA defined for the ULB GeneMark service instance

As shown in Table 1, the definition of static AC policies is rather straightforward. For instance, three process roles are defined: User, ExpertUser, and Administrator, and the associate permission on each service operation per state to different process roles (For simplicity, only one resource state ("Ready") in example AC policies is demonstrated. Typically, a resource has more states associated with each operation, e.g., at least "uninitialized state" and "destroyed state" additionally for a typical WSRP resource). The definition of dynamic AC policies through GRIA match rules is also not quite difficult. Basically, "sufficient rules" like Rule 1, Rule 2, and Rule 4 are the most commonly used match rules for defining UA relationships, which can explicitly assign a process role (P) to a specific user (U) or user groups. However, when "sufficient rules" are used to assign a group of users, "deny rules" are often necessary for excluding specific users from the group, just like Rule 3 versus Rule 2 as well as Rule 5 versus Rule 4. As the GRIA match rule pattern "Member of group ...:" is based on other four rule patterns, this rule pattern are not demonstrated in the example AC policies. Generally, it is deemed that Table 2 has covered all currently available rules patterns in GRIA.

In the following a scenario of Controlled Service Discovery in the SIMDAT Pharma will be discussed in more detail. The typical usage of biological services in SIMDAT is through the SIMDAT workflow toolkit, which, by means of a graphical user interface, can assist users in designing the abstract workflow, (semi-) automatically discovering/selecting service instances, and sequentially instantiating the abstract workflow into executable/concrete workflow. In order to demonstrate the usage of the GeneMark™ service in such a scenario, Figure 2 illustrates an abstract workflow design for an "in silico" experiment, which uses GeneMark™ as one workflow component to perform protein prediction, and then uses BLASTP (Basic Local Alignment Search Tool) as another component to compare a protein sequence with a protein databank such as SwissProt (see http://www.expasy.org/sprot/). In the SIMDAT domain ontology, GeneMark™ is modeled as a subclass of protein prediction services with aforementioned four operations. For building the abstract workflow, the users can leverage the SIMDAT domain ontology to specify their requirements on the first workflow component, e.g., service type, service I/O, as well as desired service operations. So is also the case with the second workflow component. Fig. 2 shows all these user requirements directly under each workflow component. In the article by Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid", it has been detailed how to structure these user requirements into the semantic query in terms of the SIMDAT domain ontology and OWL-S (D. Martin, et al., "OWL-S: Semantic Markup for Web Services"; http://www.daml.0rg/services/owl-s/l.2/overview/) based service description model. The discovery of concrete service instances for each workflow component is through the service discovery framework. For simplicity, it is firstly assumed that there exist several GeneMark™ service instances in the SIMDAT Pharma Grid testbed, and all these service instance are appropriately annotated thus can be discovered based on the semantic query against the first workflow component. Among these service instances, it is further assumed that the ULB GeneMark™ service instance is the best candidate in terms of some ranking criteria, thus is always on the top of the discovery result set. Besides, it is also assumed that the second workflow component can always be instantiated in the workflow, and all BLASTP service instances have no access control over resources. Under such assumptions, it is clear that the above abstract workflow can always be instantiated into executable workflow through (semi-) automatically selecting the ULB GeneMark™ service instance to fulfill the first workflow task, and any available BLASTP service instance to fulfill the second workflow task.

However, in terms of the AC policies defined for the ULB GeneMark™ service instance as in Table 1 and Table 2, this workflow is ultimately only executable by the users from ULB excluding the user "Richard Kamuzinzi" (see Rules 2 and 3), as only these users can get an ExpertUser role thus are authorized to conduct two service operations desired. This fact can however not be foreseen during the service discovery/instantiation process, provided that the service discovery framework cannot support the controlled service discovery. As a result, the chance to select other GeneMark service instances for the first workflow task is lost, and some users may be rather frustrated when they start the workflow but get no results. Much worse is, if the "failed" service instance is located in the middle of a workflow, the Grid resources may be wasted, and in particular, the Service Level Agreement (SLA) may be compromised. In a Grid computing environment, these problems are often deemed more serious than in legacy computing environments.

With the support for the controlled service discovery the service discovery framework of the present invention may be able to foresee unexecutable workflow during the service discovery/instantiation process. According to a preferred embodiment, for a user unauthorized to access a service instance, the service instance will simply not be present in the discovery result set, thus the user or workflow enactor will not consider the service instance at all for the actual workflow execution. If a workflow is deemed not executable during the service discovery/instantiation process, the users may consider to either use other users' accounts to execute the workflow (e.g., through delegation), or simply limit their desired operations on the service instance. Continuing the above discussed example of the ULB GeneMark™ service example (see Fig. 2), if the users would limit the desired operations on the GeneMark service instance to runAnalysis only, the workflow becomes executable for users from NEC additionally, though the user "Richard Kamuzinzi" and "Changtao Qu" are still excluded. In general, with the support for the controlled service discovery in the service discovery framework according to the present invention, users may have more alternatives to build executable workflow before going into complex SLA negotiation or data staging process. In a sense, through the new service discovery framework according to the present invention, the SIMDAT Pharma Grid is a bit personalized, which can provide different users with different views on the service deployment in the Grid. It should be noted that for the controlled service discovery according to the present invention, the user credentials need not explicitly be represented in the queries. As GRIA is a context aware Grid middleware, the user credentials can sustain through a chain of service invocations thus can directly be retrieved by the service discovery framework from the invocation message. The user credential information may then be translated into the semantic descriptions of the user individual, which are further used for deducing AC assertions through the controlled service discovery algorithm.

There are several semantic policy languages proposed in recent years, which can be used to describe service AC policies and further enable AC policy based service discovery and matchmaking. Most of these languages are purposed to address generic Web service policies, although AC policies are usually their principal focus. Among them, Rei (see e.g.: L. Kagal, T. Finin and A. Joshi, A Policy Based Approach to Security for the Semantic Web, 2nd International Semantic Web Conference, Sanibel Islands, Florida, USA, 2003) proposes a RDF-S based semantic policy language for representing security requirements of Web entities, which also possesses the capability to express policy rules encoded in RDF and Notation 3. In comparison to OWL-DL and SWRL (A Semantic Web Rule Language), the Rei language is however less expressive, and it is also unclear how to represent dynamic AC policies through Rei, e.g., deny policies. In particular, as so far there are no generic policy engines for the Rei language, it is rather difficult to use Rei practically. Besides Rei, KaOS (see e.g.: A. Uszokand and J. Bradshaw, KaOS policies for web services, in Proc. W3C Workshop on Constraints and Capabilities for Web Services, Redwood Shores, CA, USA, Oct. 2004 and V. KoIo vski and Bijan Parsia, Ws-policy and beyond: application of owl defaults to web service policies, in Proc. 2nd Semantic Web Policy Workshop, Athens, Georgia, USA, Nov. 2006) also propose two respective OWL-DL based semantic policy languages without the support for the rule definition. These languages are less expressive than Rei, and it is also hard to represent dynamic AC policies through these languages. This is also the case with some semantic languages specifically designed for defining AC policies such as discussed in the articles: L. Qin and V. Atluri, Concept-Level Access Control for the Semantic Web, in Proc. ACM Workshop on XML Security, Fairfax, VA, USA, 2003; E. Damiani, S. De Capitani di Vimercati, C. Fugazza, and P. Samarati, Extending Policy Languages to the Semantic Web, in Proc. 4th International Conference on Web Engineering, Munich, Germany, July 2004 and S. Javanmardi, M. A. and R. Jalili, An Access Control Model for Protecting Semantic Web Resources, in Proc. 2nd Semantic Web Policy Workshop, Athens, Georgia, USA, Nov. 2006. These languages are suited to represent finegrained static AC policies, but inappropriate to represent dynamic AC policies.

Moreover, the article by H. Li, X. Zhang, H. Wu and Y. Qu, Design and Application of Rule Based Access Control Policies, in Proc. Semantic Web and Policy Workshop, Galway, Ireland, Nov. 2005 proposes an approach to represent AC policies using OWL-DL ontologies and SWRL rules. The usage of semantic rules in this article is to express implicit ontology terms. In contrast, according to the present invention, semantic rules are preferably used to declaratively represent service access control policies, which is an absolutely different usage.

It is therefore an object of the present invention to provide an improved method and/or system for providing a controlled service discovery framework. It is also an object of the present invention to provide controlled service discovery for internet services, and to demonstrate importance of the controlled service discovery for internet services.

This and other objects are achieved by the features of the independent claims. Further preferred embodiments are characterized in the dependent claims. In particular, the combination of ontologies and semantic rules for controlled service discovery implementation according to the present invention provides an effective solution to the above objects.

SUMMARY OF THE INVENTION hi order to support the controlled discovery of services in a Grid, e.g., biological services in SIMDAT, the inventors of the present invention provide a method and system which extends the existing semantics enabled service discovery framework to provide the capability to semantically annotate service AC policies and preferable sequentially discover/select service instances based on the user credentials and service AC policy annotations. As service AC policies in SIMDAT are rather dynamic, service AC policies according to the present invention are separated logically into a (i) static part and a ii)dynamic part and preferably leverage OWL (Web Ontology Language) ontologies and semantic rules to represent static and dynamic AC policies, respectively. By means of the ontology and rule reasoning, sets of AC assertions can dynamically be deduced in the rule base, which can then naturally be integrated into the existing service discovery framework and uniformly be handled in the semantic matchmaking algorithm besides other annotated service features.

According to a first aspect, the present invention relates to a system or method for controlling service Access Control (AC) policies, preferably in order to discover/select service instances in a Grid. The System or method is characterized in that the service AC policies comprise AC policy annotations with a static part and a dynamic part.

According to a preferred embodiment, the system and/or method is an extension for existing service discovery frameworks, wherein the static part is preferably represented by a security ontology to represent a PBAC model and/or to user credential ontology and/or the static AC policies. The dynamic part is preferably represented by semantic rules to declaratively represent dynamic AC policies based on the security ontology and/or static AC policy annotation.

According to a further aspect, the controlled service discovery is based on OWL-DL to represent the security ontology.

In particular, the static part is preferably based on ontologies, preferably on the basis of the Web Ontology language (OWL). For instance, the static AC policies comprise PA, SA and OA.

The dynamic part is preferably based on semantic rules. In particular, the dynamic part is preferably based on a user credential ontology. For instance, the dynamic part may comprise UA relations which are adjusted on the fly by means of formal rule languages.

According to a preferred embodiment, the dynamic AC rules are interpreted through a rule engine.

According to a further preferred embodiment, SWRL and/or Jena rules are used to declaratively define the dynamic AC policies, in particular for covering complex deny rules.

The AC policy annotation is preferably separated from the usual service annotation.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will now be described in detail with respect to preferred embodiments with reference to accompanying drawings, wherein:

Fig. 1 shows a typical PBAC model with static relations in normal font and dynamic relation in cursiv font as known from the art;

Fig. 2 shows an abstract workflow using GeneMark™ as one workflow component as known from the art;

Fig. 3 shows an architecture desing of an extended semantic enabled service discovery framework with semantic rule support according to the present invention; Fig. 4 shows a PBAC ontology according to the present invention;

Fig. 5 shows a user credential ontology according to the present invention;

Fig. 6 shows semantic annotation of static AC poicies based on a security ontology according to the present invention;

Fig. 7. shows a performance evaluation of a controlled service discovery algorithm according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION A preferred feature of the present invention is based on the semantic annotation of service Access Control Policies. The system and method of the present is preferably designed as an extension for existing service discovery frameworks. For instance, as an extension in the existing service discovery framework in SIMDAT, the controlled service discovery should preferably be implemented following the same design as the original system, e.g., in case of SIMDAT by using the same technologies such as OWL-DL (Description Logic; see D. L. McGuinness, and F. van Harmelen, "OWL Web Ontology Language Overview" http://www.w3.org/TR/owl-features/) to represent the security domain ontology, OWL-S [16] to accommodate the AC policy annotation, and ontology reasoning to deduce AC assertions for the service discovery and matchmaking. However, as service AC policies are much more complex than usual service features like service classification, QoS, etc., it is rather difficult to handle AC policies within the existing service discovery framework, in particular within the existing technology scope.

First of all, whereas static AC policies, e.g., PA, SA and OA (see Figure 1) can easily be annotated through ontologies, it is rather hard to annotate dynamic AC policies, e.g., UA, using the same approach. As the UA relation is preferably dynamically defined and adjusted, it is impractical to pre-model all dynamic relationships into the security ontology, and sequentially update them very frequently. According to a particular embodiment of the present invention, in order to annotate service AC policies, in particular dynamic AC policies, the present invention preferably proposes to extend the existing service discovery framework with two new components: (1) OWL-DL based security ontology, which can be used to explicitly represent the PBAC model, user credential model, and further static AC policies; and (2) semantic rules, which can be used to declaratively represent dynamic AC policies based on the security ontology and static AC policy annotation. Whereas all static PA, SA and OA relations can efficiently be modeled through the security ontology, dynamic UA relations can preferably be mapped to a set of semantic rules, which can conveniently be defined and adjusted on the fly by means of formal rule languages. In a common rule base with the security ontology and static AC policy annotation, the dynamic AC rules can be interpreted through the rule engine to dynamically infer new, or update existing AC assertions, based on which the controlled service discovery can be implemented. Second, although it is possible to integrate the service AC policy annotation, both static and dynamic one, into the OWL-S based service annotation model (For example, it can be done through using service Parameter property in the OWL-S service profile to accommodate static AC policy annotations, and using pre-condition in the OWL-S service model to accommodate dynamic AC policy annotations.), it is preferable not to mash up the service AC policy annotation and "usual" service annotations within the same OWL-S data model. As the controlled service discovery involves complex rule definition and rule reasoning, and in particular the rule reasoning is computationally rather expensive, embedding AC policy annotations into the complex OWL-S data model may introduce additional complexity and computation overhead into the rule definition and inference process. In view of this, for the controlled service discovery, it is preferred to intentionally separate the AC policy annotation from the usual service annotation, and set up a logically separate rule base to store AC policy annotations. This implies that the rule reasoning functions over a comparatively small knowledge base, which can efficiently ensure the performance of the controlled service discovery algorithm. Last but not least, for the semantic rule reasoning over dynamic AC policies, new rule engines are preferably introduced into the existing framework. While "Pellet" has been used in the existing service discovery framework as an ontology reasoner (Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid"), the present invention preferably makes use of the SWRL (Semantic Web Rule Language; see I. Horrocks, et al.,SWRL: A Semantic Web Rule Language Combining OWL and RuIeML; http://www.w3.org/Submission/SWRL/) reasoning capability to support the SWRL rule reasoning (see E. Sirin, B. Parsia, B. Cuenca Grau, A. Kalyanpur, and Y. Katz., "Pellet: A practical OWL-DL reasoner," J of Web Semantics, vol. 5, no.2, pp.51-53, June 2007). Besides, as SWRL cannot address all annotation requirements of dynamic AC policies, in particular deny policies (see discussion below), the Jena rule engine (see Jena Project, Jena 2 Inference support, Available: http://jena.sourceforge.net/inference/#api) may also be introduced into the framework as another rule reasoner supporting non-monotonicity resolution. Thus, in the extended service discovery framework according to the present invention, there may be for instance four different combinations of ontology reasoners and rule engines to provide different reasoning capabilities, e.g.:

(I) OWLIM + Pellet for the OWL-DLP ontology and SWRL rule reasoning; (II) OWLIM + Jena rule engine for the OWL-DLP ontology and Jena rule reasoning;

(III) Pellet +Jena rule engine for the OWL-DL ontology and Jena rule reasoning; and

(IV) Pellet itself for both the OWL-DL ontology and SWRL rule reasoning.

With regard to OWLIM, please be referred to A. Kiryakov, D. Ognyanov, and D. Manov, "OWLIM - a Pragmatic Semantic Repository for OWL," in Proc. hit. Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS 2005), New York, USA, Nov. 2005. With regard to OWL-DLP, please be referred to Grosof, B., Horrocks,L, VoIz ₅ R., and Decker, S. Description Logic Programs: Combining Logic Programs with Description Logics, in Proc. of WWW 2003, Budapest, Hungary, May 2003. Figure 3 illustrates the architecture design of a preferred embodiment of an extended semantics enabled service discovery framework with controlled service discovery support according to the present invention, hi comparison to a known system (see Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid", in J. IEEE Trans, on Information Technology in Biomedicine), major extension components are denoted with asterisks.

The SIMDAT security ontology is purposed to provide formal semantics to the PBAC model and user credential model, which serves as the basis of the semantic annotation of AC policies, both static and dynamic ones. Besides, the security ontology also provides common vocabularies for constructing semantic queries, e.g., user desired operations, etc. Following a modular design pattern, the SIMDAT security ontology may be divided into three parts:

(I) the PBAC ontology, (II) user credential ontology, and (III) VO (Virtual Organization) ontology. Similar to the SIMDAT domain ontology developed in the article by Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid", the SIMDAT security ontology is represented through OWL-DLP/O WL-DL.

Figure 4 illustrates an example of an OWL concepts and properties modeled in the PBAC ontology. In correspondence to the PBAC model illustrated in Fig. 1, all PBAC components and relationships between them are semantically modeled as OWL concepts and properties in the PBAC ontology. The static assignment relations PA, SA, and OA are respectively represented through the property "allowsProcessRole" (≡ PA), "hasState" (≡ SA), and "hasOperation" (≡OA).

In the service AC policy annotation according to the present invention, these properties can directly be used to link corresponding OWL individuals thus represent static AC policies. The dynamic assignment relation UA is represented through the property "hasProcessRole" (≡ UA). It is however not explicitly assigned in the service AC policy annotation, rather is preferably dynamically inferred through the rule reasoning. In the PBAC ontology, there is also another property "hasAccessTo", which represents the ultimate AC assertions about users and services, and is preferably dynamically assigned. These AC assertions are actually deduced through a generic AC rule based on all PA, SA, OA, and UA relations in the rule base (see discussion below).

It should be noted that in the PBAC ontology there are two properties which are not present in the PBAC model as in Fig 1. The property "hasDesiredOperation" is used for representing users' desired operations on a service, thus only for the query purpose. The property "hasNegativeRole" is used for defining deny AC policies, as detailed in the discussion below.

The user credential ontology is purposed to model user authentication identity, based on which the dynamic UA relation can be represented. The design of the user credential ontology is based on current authentication schemes applied in the PBAC model for defining UA, thus is not intended to cover all PKI or SAML vocabularies as in the articles of A. Kim, J. Luo, and M. Kang, Security Ontology for Annotating Resources, in Proc. 4th Int. Conf. on Ontologies, Databases, and Applications of Semantics, Agia Napa, Cyprus, 2005 and in the article by G. Denker, L. Kagal, T. Finin, M. Paolucci, and K. Sycara, Security for DAML Web Services: Annotation and Matchmaking, in Proc. of the 2nd Int. Semantic Web Conference, San Sanibel, Florida, USA, Oct 2003.

Figure 5 illustrates OWL concepts and properties modeled in the current user credential ontology. Except for the concept CertificateAuthority (CA), the instantiation of the user credential ontology occurs in the VO ontology, which contains all semantically represented user individuals in the SIMDAT VO. As the SIMDAT VO operates based on a fully X.509 compliant PKI, the instantiation of the user credential ontology can automatically be done through a program, which can retrieve users' X.509 certificates and sequentially make credential assertions in the VO ontology. It should be noted that the VO ontology is only useful for the semantic annotation of dynamic AC policies through service administrators. It can guarantee that service administrators can correctly identify each (semantic) user individual during the annotation process. However, whereas the user credential ontology is an integral part of the rule base for the controlled service discovery, the VO ontology is not.

As the user authentication attributes currently used in PBAC are quite a few, the user credential ontology is fairly lightweight at present. With the introduction of more authentication schemes in PBAC, the inventors of the present invention expect that the user credential ontology will further be extended. In particular, some exiting security ontologies such as described in the article by A. Kim, J. Luo, and M. Kang, Security Ontology for Annotating Resources, in Proc. 4th Int. Conf. on Ontologies, Databases, and Applications of Semantics, Agia Napa, Cyprus, 2005 and the article by G. Denker, L. Kagal, T. Finin, M. Paolucci, and K. Sycara, Security for DAML Web Services: Annotation and Matchmaking, in Proc. of the 2nd Int. Semantic Web Conference, San Sanibel, Florida, USA, Oct 2003 may directly be re-used in the user credential ontology to represent various user authentication attributes.

Semantic Annotation of Static AC Policies based on the Security Ontology

The semantic annotation of static PBAC AC policies is the process of instantiating OWL concepts in the PBAC ontology and further assigning PA, SA, and OA relationships between them. Taking static AC policies defined for the ULB GeneMark™ service in Table 1 as an example, Figure 6 lists part of their semantic annotations with some of "allowsProcessRole" relationships omitted for simplicity. The process role instances specific to each service instance are basically defined in the static AC policy annotation, which implies that service administrators can customize the usage of their services freely. Note that for each process role instance, we also define a negative role instance, which is associated with its counterpart through the symmetric property hasNegativeRole. In fact, the negative roles have no direct usage in the static AC policy annotation. They are however necessary for representing deny AC policies, as detailed in the following. Semantic Annotation of Dynamic AC Policies using Semantic Rules

The semantic annotation of dynamic AC policies is the process of defining semantic rules for representing AC restrictions, which, together with the security ontology and static AC policy annotations, are used for dynamically deducing the UA relationship (i.e., hasProcessRole) and final AC assertions (i.e., hasAccessTo) through the rule reasoning. In PBAC, dynamic AC policies can be defined through sufficient rules and deny rules, which results in two types of dynamic AC policies: sufficient AC policies such as Rule 1, Rule 2, and Rule 4 in Table 2, and deny AC policies such as Rule 3 and Rule 5. While sufficient AC policies can be dealt with through both the SWRL and Jena rule engine, deny AC policies can only be handled through the Jena rule engine.

In the following the Annotation of Sufficient AC Policies using SWRL and Jena Rules will be discussed in more detail. Both SWRL and Jena allows users to write Horn-like rules expressed in terms of OWL concepts to reason about OWL individuals. As all sufficient AC policies can directly be mapped to Horn clause rules, it is rather straightforward to represent three sufficient AC policies in Table 2 using either SWRL syntax or Jena rule syntax. The following Table 3 list the semantic annotation of above three sufficient AC policies in the SWRL syntax.

Rule l credential:User (?user) ^Λ credential: S AMLAttribute (?saml) ^A pbac:hasCredential (?user, ?saml) ^Λ credential: issuedBy (?saml, credential:ULB_CA) ^Λ credentiakhasProperty (?saml, "Department") ^Λ credential rhasValue (?saml, "Bioinformatics") => pbac:hasProcessRole (?user, ulb:User )

Rule 2 credential :User (?user) ^Λ credentiahCertifϊcate (?certiticate) ^Λ pbachasCredential (?user, ?certificate) ^Λ credential: issuedBy (?certificate, credential :ULB_C A) => pbac:hasProcessRole (?user, ulb:ExpertUser)

Rule 4 credential:User (?user) ^Λ credentiakCertificate (?certiticate) ^Λ pbac:hasCredential (?user, ?certiflcate) ^Λ credential: issuedBy (?certificate, credential :NEC_CA) => pbac:hasProcessRole (?user, ulb:User)

Table 3. Semantic annotation of sufficient AC policies using SWRL rules

The semantic annotation of dynamic AC policies directly references process role instances defined in the static AC policy annotation, as well as OWL concepts defined in the security ontology. Whereas these rules can be used to dynamically deduce the UA relationship, there is preferably needed a generic AC rule that can be used to dynamically infer final AC assertions, i.e., hasAccessTo. This generic AC rule can be represented in the SWRL syntax as: credential :User (?user) ^Λ pbac:ProcessRole (?role) ^Λ pbac:Resource (?service) Λ pbac: Operation (?desiredθperation) ^Λ pbac: Operation (?serviceθperation) Λ pbac:hasProcessRole (?user, ?role) ^A pbac:allowsProcessRole (?serviceθperation, ?role) ^A pbac:hasDesiredOperation (?user, ?desiredθperation) ^Λ pbac:hasθperation (?service, ?serviceθperation) ^Λ pbac:hasName (?serviceθperation,?any) ^Λ pbac:hasName (?desiredθperation, ?any) => pbac:hasAccessTo (?user, ?service) In human readable language, this rule can be read as "if a service has the operation which is desired to operate by the user, and the user possesses the process role which is allowed by the operation, then the user has the access to the service ". It is deemed that this rule is generic as it is independent of user instances, role instances, service instances, and operation instances, and applicable to the whole rule base. As the result of firing the rule, any user instance in the rule base is dynamically associated with service instances through the hasAccessTo property, provided the rule body is satisfied. Note that in the generic AC rule, several tricks are leveraged to overcome the syntax limitation of rule languages. For example, the hasName property defined for the Operation concept in the PBAC ontology is leveraged to determine that users' desired operation instance is the same as the service operation instance, although the both are actually located in different namespaces (Whereas the service operation instance is located in individual service namespace, the user desired operation instance is always defined in the common query namespace as described in Qu, C. F. Zimmermann, K. Kumpf, R. Kamuzinzi, V. Ledent, and R. Herzog, "Semantics enabled Service Discovery Framework in the SIMDAT Pharma Grid", in J. IEEE Trans.). Annotation of Deny AC Policies using Jena Rules

The use of definite Horn clauses in SWRL restricts the use of negation, i.e., the capability to directly represent deny AC policies such as Rule 3 and Rule 5 in Table 2. This is also the case with the Jena rules language. Basically, this is not a simple "syntax" problem, rather due to the fact that SWRL can only support monotonic inference, and it is generally beyond SWRL' s capability to address the non-monotonicity introduced by deny rules. As can be seen from Table 2, Rule 3 apparently introduces UA assignment assertions which are logically conflict with assertions inferred through Rule 2. Whereas such conflictions can easily be resolved by the PBAC enforcement mechanism through prioritizing deny rules over sufficient rules, it is hard, if not impossible, to logically deal with such conflictions in the rule base using the SWRL language.

Whereas common SWRL engines such as Pellet have no capability to address non- monotonicity in the rule base, the Jena rule engine provides a workaround to resolve the non- monotonicity, as discussed above, through its builtin primitives remove and drop. Whereas the remove primitive can delete the statements which caused the n'th body term of a (forward- only) rule to match, and sequentially propagate the change to other consequent rules including the firing rule, the drop primitive can do the same manipulation on statements except for firing rules as a consequence. Although the behaviors of complex rule sets through these two non-monotonic operations are not yet fully clear, we can effectively use these two primitives in the controlled service discovery to resolve the non-monotonicity introduced by "simple" deny rules, hi correspondence to two deny AC policies in Table 2, we list their semantic annotations in the Jena rule syntax hi Table 4.

:NEC_C A) (?user Table 4. Semantic annotation of deny AC policies using Jena rules

As the Jena rule language also makes use of Horn clauses, it cannot represent negation in both rule body and rule head, just like SWRL. For the negation purpose, we explicitly define a negative role for each process role instance in the static AC policy annotation, which are respectively Non_User, Non_ExpertUser, and Non Administrator in the ULB GeneMark service example. Through a symmetric property hasNegativeRole defined hi the PBAC ontology, the negative relations between the counterpart roles can be represented and understood by the rule engine. Based on this, the non-monotonicity introduced by deny rules can be resolved through a generic role negation rule, which can be represented in the Jena rule syntax as:

[Generic_Role_Negation: (?user rdf:type credential :User) (?role rdf:type pbac:ProcessRole) (?negative_role rdfrtype pbac:ProcessRole) (?user pbacrhasProcessRole ?role) (?user pbac:hasProcessRole ?negative_role) (?role pbac:hasNegativeRole ?negative_role)-> remove(3,4)] In human readable language, this rule can be read as "//α user is assigned a process role and at the same time also its negative role, then simply remove both roles". Similar to the generic AC rule, this generic role negation rule is also independent of user instances or process role instances, and applicable to all hasProcessRole assertions in the rule base. After firing, this rule can remove any conflict assertions through leveraging hasNegativeRole assertions to determine whether the hasProcessRole assertions about a user are conflict or not. Taking the user "Changtao Qu" as an example, as he is assigned the User role through Rule 4 and at the same time the Non User role through Rule 5, he will get neither User role nor Non_User role as the result of firing the generic role negation rule. This implies that the previously assigned process role is revoked, thus there exists no non-monotonic assertions in the rule base any more. Basically, such a logical handling of deny rules in the rule base is in line with the behaviors of the PBAC enforcement mechanism, i.e., deny rules are prioritized thus can always revoke roles assigned through sufficient rules.

Controlled Service Discovery: the Algorithm and Performance Evaluation

The controlled service discovery is ultimately based on the AC assertions about the property hasAccessTo, which are dynamically inferred in terms of static and dynamic AC policy annotations in the rule base. Although it is possible to directly integrate the controlled discovery into the existing service matchmaking algorithm, we determine to implement it as a separate module, which functions as a "filter" upon the service discovery result set. For each service instance in the result set, this "filter" module verifies whether a user has the access right to the service, and if yes, the service instance will be added to the final result set and presented to the user. Such an implementation is mainly purposed to ensure the performance of the controlled service discovery algorithm. As the controlled service discovery involves the rule reasoning over all service instances in the rule base, its performance will dramatically decrease with the increase of the number of services. By means of a "filter" approach, the controlled service discovery algorithm may only need to deal with small part of service instances which have been discovered through the original service matchmaking algorithm, thus achieve an acceptable performance.

The following method steps illustrate a preferred embodiment of a controlled service discovery algorithm according to the present invention.

1. retrieve the user credential information from the invocation message, retrieve user's desired operation from the query 2. for each service in the discovery result set

3. if the service instance has no AC policy annotation then

4. add service to the final result set

5. else

6. initialize the rule base through loading generic AC rule, generic role negation rule, PBAC ontology, user credential ontology, service's static and dynamic AC policy annotation.

7. build the user individual in terms of the information retrieved from Step 1.

8. add the user individual to the rule base

9. query the rule base and verify if the AC assertion (user hasAccessTo service) exists.

10. if exits, then 11. add service to the final result set.

12. end if In the algorithm, the actual rule reasoning occurs at Step 8 and Step 9, i.e., when a user individual is added to the rule base and a query is sent. In each round of the rule reasoning, only one user instance, one service instance, and corresponding service's AC policy annotations are involved. It is clear that the overall performance of the algorithm depends on the size of the discovery result set. If a large number of service instances have to be verified through the "filter" program, the performance of the controlled service discovery algorithm will dramatically decrease.

In order to evaluate the actual performance of the controlled service discovery algorithm, we conduct a simulation experiment to particularly evaluate the overhead of the rule reasoning. The simulation is based on a workstation of AMD Opteron 252, 2.6GHz, with 1MB L2 cache and 2GB memory, Sun JDK 5.0 with the JVM (Java Virtual Machine) heap size set to IGB, and Jena 2.5.3. In the experiment, up to 10,000 sufficient rules and deny rules are generated to define dynamic AC policies for a service instance, which cover all dynamic AC policy patterns as in Table 2. For the sufficient rule experiment, we use the pattern of Rule 1 , Rule 2, and Rule 3 without negation. For the deny rule experiment, we use the pattern of Rule 2 and Rule 3, and for the sufficient & deny rule experiment, we combine all rule patterns applied in above two experiments. All dynamic AC rules in the experiments are represented in the Jena rule language, and the Jena rule engine is configured to operate in the backward mode. The static AC policies defined for the service instance are the same as ones for the example ULB GeneMark service instance, including four service operations, one resource state, and three process roles. Figure 8 illustrates the performance evaluation result. The query overhead here is the sum of computation time from Step 6 till Step 13 in the controlled service discovery algorithm. As expected, the query overhead increases roughly linearly with the number of the rules, and this is the case with all three experiments. Although deny rules introduce the non- monotonicity and the rule engine has to resolve it through the generic role negation rule, the query overhead of deny rules is roughly equivalent to that of sufficient rules. This can be explained by the fact that the rule reasoning in our algorithm has only to deal with one user instance, thus the number of conflict role assertions in the rule base is rather small. The query overhead of sufficient & deny rules is relatively high. This is simply because that the actual number of rules in the experiment is one time more than those in other two experiments. In Fig. 8 we can see that the query overhead of sufficient & deny rules is also roughly the sum of the query overhead of other two experiments, just as expected. Although the rule reasoning performance per round is basically acceptable, we also have to evaluate the overall performance of the algorithm, which is dependent on the size of the discovery result set, as indicated in Fig. 7. It is clear that the overall performance of the algorithm can be improved by reducing the number of service instances considered in the algorithm. Comparing the performance evaluation result of the original service discovery framework, we can see that the overall performance of the controlled service discovery is roughly acceptable with a middle-sized rule base, e.g., containing 1000-2000 rules, and a middle-sized discovery result set, e.g., containing around hundreds of service instances. In this case, the overall query overhead of the controlled service discovery algorithm is roughly comparable to the one of the original service matchmaking algorithm, hi general, our experimental results basically indicate two ways to improving the overall performance of the controlled service discovery. On the one hand, the semantic queries should carefully be designed in order to minimize the size of discovery result set. On the other hand, different match rule patterns should flexibly be combined in order to minimize the number of dynamic AC rules. While it has been previously demonstrated how to build efficient semantic queries through combining multiple OWL-S data entries, in Table 2 it is also shown how the combination of sufficient and deny rules can effectively reduce the total number of rules.

The controlled service discovery according to the present invention is mainly purposed to address AC policy based service discovery in a Grid computing environment, wherein service AC policies need to be dynamically defined and frequently adjusted in order to adapt to dynamic environments of VOs. Through separating AC policies into the static and dynamic parts, we can explicitly define static AC policies through ontologies, and declaratively represent dynamic AC policies as semantic rules. Whereas ontologies make each service's security properties explicitly available, semantic rules make existing knowledge more complete and allow for linking of existing security properties in a previously unforeseen manner. Going a step further, semantic rules can also be exploited to enhance ontology based (static) policies, e.g., improve the expressiveness, dynamically detect and resolve policy confliction, etc. Working together, ontologies and semantic rules can efficiently manage dynamically changing knowledge for decision making, just like we demonstrate through our work.

With the focus on semantic rules and dynamic AC policies, in this paper we do not show all forte of the controlled service discovery, in particular its capability to deal with finegrained access control through the static AC policy annotation. In fact, we can represent more complex AC policies in the static AC policy annotation than ones in our example use case, e.g., AC policies involving hierarchical roles, hierarchical operations, and hierarchical states, etc. Basically, it is the strength of ontologies to model such complex relationships. Note should be paid that for such fine-grained AC policies, the dynamic AC policy annotation does not necessarily become complex, and sometimes is quite the contrary. For example, if a user is assigned a process role, he will automatically get all parent-concept roles without the need for explicit rule definitions. These implicit role assertions as well as sequential AC assertions are automatically deduced through the OWL subsumption reasoning. Although the subsumption reasoning will unavoidably introduce additional overhead into the controlled service discovery algorithm, it is far from comparable to the rule reasoning overhead thus has little negative influence on the overall performance of the algorithm.