Tim Claudius Stratmann
email: tim.claudius.stratmann@uni-oldenburg.de

Susanne Boll
email: susanne.boll@uni-oldenburg.de

Demon Hunt -The Role of Endsley's Demons of Situation Awareness in Maritime Accidents

Keywords: situation awareness, accident analysis, maritime, Human Error

Human Error is the cause of most maritime accidents. In a majority of the cases the source of the Human Error is a lack of Situation Awareness. Endsley et al. have identified eight causes that corrupt the Situation Awareness of human operators, the so-called Demons of Situation Awareness (SA Demons). We analyzed over five-hundred maritime accident reports for each of the eight SA Demons to provide a ranking of the causes and to identify the most prominent ones. Addressing these SA Demons enables maritime system designers to enhance the Situation Awareness of maritime operators and thereby improves the safety at sea.

Introduction

Human Error accounts for 80-85% of maritime accidents [START_REF] Baker | Accident database review of human element concerns: What do the results mean for classification?[END_REF]. The type of Human Errors are diverse, however they can be classified. Prior work of Grech et al. showed that a lack of Situation Awareness causes about 71% of all Human Error related accidents [START_REF] Grech | Human error in maritime operations: Analyses of accident reports using the leximancer tool[END_REF]. Similar findings have been made in other transportation domains. The problem of a lack in Situation Awareness was extensively investigated in the aviation domain.

Mica R. Endsley has defined Situation Awareness as "the perception (level 1) of the elements of the environment within a volume of time and space, the comprehension (level 2) of their meaning, and the projection (level 3) of their status in the near future" [START_REF] Endsley | Toward a theory of situation awareness in dynamic systems[END_REF]. In 1999 Endsley introduced a taxonomy of Situation Awareness errors [START_REF] Endsley | Situation awareness and human error: Designing to support human performance[END_REF]. This taxonomy later led to the definition of the so-called Demons of Situation Awareness (SA Demons) [START_REF] Endsley | SA Demons: The Enemies of Situation Awareness[END_REF]. The SA Demons stand for eight common causes for a lack of Situation Awareness. They address all three levels of Situation Awareness.

The aim of our work is to classify maritime accidents by Endsley's SA Demons. Moreover we provide our corpus of 1376 maritime accident reports and perform our analysis on a subset of it. We investigate the occurrences and distribution of the eight SA Demons in a corpus of 535 maritime accident reports. Information about occurrences and distribution of the SA Demons enables maritime system designers to adjust their systems to the SA related needs of the operator and to build assistance systems that focus on mitigating the specific cause of SA errors.

Related Work

Most scientific accident analyses in the maritime domain focus on the statistical classification of error causes, whereas the investigations of safety authorities focus on deriving guidelines to prevent the same accidents from happening again. Human Error as cause of maritime accidents is no new phenomenon. As long ago as 1987 Wagenaar et al. analyzed 100 maritime accidents, of which 96 were caused by Human Error [START_REF] Wagenaar | Accidents at sea: Multiple causes and impossible consequences[END_REF].

In 2005 Baker et al. published their three year enduring analysis of maritime accidents from the United States, Australia, Canada, Norway and the United Kingdom. Their results show that the frequency of accidents is declining, but that Human Error continues to be the dominant factor in approximately 80 to 85% of maritime accidents [2] [3]. According to their findings failures in Situation Awareness are a causal factor in the majority of accidents attributed to Human Error. They identified some significant factors associated with Situation Awareness failures which include: Cognitive and decision errors, Knowledge-Skill-Ability errors, task omissions and risk taking. They expect most of them to be artifacts of fatigue. There is more data available than can be processed by the human "bandwidth". SAD5 Misplaced Salience (SA level 1) Salience is the "compellingness" of a piece of data, often dependent on how it is presented. SAD6 Complexity Creep (SA level 1, 2 and 3)

Complexity slows down the perception of information and it undermines the understanding and the projection of information.

SAD7 Errant Mental Models (SA level 2 and 3)

Wrong mental model may result in incorrect interpretation of data. SAD8 Out-of-the-loop syndrome (SA level [START_REF] Antão | Analysis of maritime accident data with bbn models. Safety, reliability and risk analysis: theory, methods and applications[END_REF] For example: Automated systems that do not involve the human until there is a problem.

Antão et al. used BNN models to analyse maritime accidents [START_REF] Antão | Analysis of maritime accident data with bbn models. Safety, reliability and risk analysis: theory, methods and applications[END_REF]. Other work dealing with human error in maritime accidents is [START_REF] De La Campa Portela | Maritime casualties analysis as a tool to improve research about human factors on maritime environment[END_REF], [START_REF] Chauvin | Human and organisational factors in maritime accidents: Analysis of collisions at sea using the hfacs[END_REF], [START_REF] Koester | Human error in the maritime work domain[END_REF] and [START_REF] Rothblum | Human error and marine safety[END_REF].

Corpus

Performing an analysis on specific SA error causes requires a data source with a high level of detail. Therefore we retrieved full-text reports of maritime accident investigations. The full corpus consists of 1376 maritime accident reports from five transportation safety authorities between the years 1987 and 2015. The reports were gathered from the British Marine Accident Investigation Branch (MAIB)2 , the American National Transportation safety Board (NTSB)3 ,the United States Coast Guard (USCG) 4 , the Australian Transportation safety Board (ATSB) 5and the Transportation safety Board of Canada (TSBC) 6 . We specifically chose authorities from these countries, because they have English as their first language and a high number of available full-text reports. We share our full corpus on request to support further research in this area. For our following analysis we focused on the MAIB sub-corpus, but we intend to apply the same method of analysis to the whole corpus in the future.

Authority

Analysis

Figure 1. This chart shows a segmentation of the corpus in relevant subsets. The SA Demons are colored in blue.

The MAIB corpus consists of over five hundred accident reports. In order to classify these accident reports we applied a request-oriented classification approach. We used boolean queries to perform a full-text search on all documents in the corpus. Beforehand the corpus had to be prepared and a list of keywords had to be created in order to build meaningful queries. The preparation of the corpus is described in the following. Thereafter we describe the generation of keywords and our classification method. In order to perform an analysis on the gathered corpus of accident reports some pre-processing of the corpus is necessary. We gathered full-text maritime accident reports in English and PDF-format from five transportation safety authorities. As preparation for the analysis we extracted the plaintext from the reports in PDF-format and performed simple cleaning of the reports by removing the front page and fixing character encoding issues. Further we converted the reports to lowercase in order to simplify caseinsensitive search. As some reports consisted of several files we merged these documents into one. After this preparation one document represents one accident.

Preparation

For the exploration of the corpus we created a document-term-matrix of the corpus and checked the most frequent terms. Furthermore this enabled us to check term correlations in the corpus. We used R version 3.2.4 with a number of text-mining packages to perform this. The creation of the document-term-matrix requires some further pre-processing in R. The following pre-processing steps were conducted on the data-frame in R, only. We removed URLs, punctuation, numbers, standard English stop-words and some custom stop-words from the corpus. From the pre-processed corpus we created a tf-idf-weighted document-term-matrix. Figure 2 shows a word cloud of the one hundred most frequent terms in the corpus.

Generation of Keywords

A list of keywords for each SA Demon was created. The selected keywords were derived from the description of the SA Demons and examples from [START_REF] Endsley | SA Demons: The Enemies of Situation Awareness[END_REF] and keywords identified during the exploration of the corpus. The keyword list was complemented with fitting synonyms of the keywords using wordnet [START_REF] Miller | Wordnet: a lexical database for english[END_REF].

A meaningful choice of keywords and the proper construction of the boolean queries is critical to the success of the retrieval. Adjusting the query based on the exploration of the corpus always bears the danger of overfitting the queries to the specific corpus. Furthermore the composition of the queries directly influences the precision and recall of the retrieval. Although we did not measure the recall, we tried to achieve a good balance between precision and recall.

The iterative exploration of the corpus showed unexpected usage of keywords, such as 'fatigue' in 'fatigue wear' of machine parts. The identification of these negative keyword combinations helped us to increase the precision of our search queries. We increased the recall of the query be reducing the keywords in the queries to their stems. The aim was to create a list of queries that can be applied to any set of maritime accident reports in English.

The generation of fitting keywords is a semi-automated process that highly relies on the judgment of a human analyst. In summary, the process consists of the following steps:

1. derive keywords from definitions and examples 2. find fitting synonyms for keywords using wordnet 3. explore corpus, find term-correlations for the keywords, and add new keywords 4. reduce some keywords to their stems to increase the recall based on human judgment Furthermore we added keywords for Situation Awareness and Human Error to be able to search on a meta level if none of the keywords for a SA Demon returns any results. 2. This table shows the generated keywords for each SA Demon. Some of them are reduced to their stem to increase their recall.

Retrieval Method

We classified the documents into the SA Demon categories by using boolean queries constructed from the SA Demon keywords. We performed test queries to identify the keyword combinations with the best balance of precision and recall. Table 3 shows the final queries we used to retrieve the accidents caused by the SA Demons.

For SAD2, SAD5, and SAD6 we could not find a fitting query that specifically retrieves them. Queries constructed from SAD6 keywords always delivered SAD7 problems, as the keywords are to similar. The keywords for SAD5 are often used by the authors of the accident reports to emphasize their findings and recommendations, e.g. " [...] draw the attention of Owners, Skippers, Mates and crews to [...]". We therefore used a more general query for these SA Demons.

We applied the pipeline and filters design pattern to implement the boolean queries as a unix pipeline combining the unix programs find and grep. The advantage of this approach over using an indexing search engine is the support of full-text search. To remove false positives, the query results were inspected manually in the context of the sentences containing the positive keywords. If we were unsure, the sentence before and after the finding was also inspected. 3. This table shows the composition of the boolean search queries for each SA Demon.

SA Demon Query

SAD1 (preoccupied ∧ (himself ∨ herself)) ∨ (pre-occupied ∧ (himself ∨ herself)) ∨(attent ∧ not) ∨ focus SAD2 (human ∧ error) ∨ (human ∧ element) ∨ (human ∧ factor) ∨(situation ∧ aware) SAD3 fatigue ∧ ¬crack ∧ ¬wear ∧ ¬not ∧ ¬unlikely ∨ workload SAD4 occupied SAD5 (human ∧ error) ∨ (human ∧ element) ∨ (human factor) ∨(situation ∧ aware) SAD6 (human ∧ error) ∨ (human ∧ element) ∨ (human ∧ factor) ∨(situation ∧ aware) SAD7 misinterpret SAD8 not ∧ aware Table

Results

The SA Demons with the highest proportion in the investigated sample were WOFAS with fatigue as main cause, errant mental models, and attention tunneling. We were not able to find accidents caused by requisite memory trap, misplaced salience or complexity creep. Not all Situation Awareness related accidents can be explained by the SA Demons. During analysis we found some accidents caused by a lack of Situation Awareness that could not be derived directly from a SA Demon, such as insufficient trip planning. Table 4 shows the results of our request-oriented classification. The table lists the absolute count of retrieved accidents and the precision of the query for each SA Demon. The query precision is the positive predictive value of the query-request on the corpus.

It is calculated as follows:

query precision = number of true positives number of true positives + number of false positives Moreover we calculated an estimate of the total number of results based on statistics from related work. This provides us with a weak sanity check of the total number of retrieved accidents related to SA problems. For the MAIB corpus this estimate amounts to 300-321 accidents. We based the estimate on the results of Baker et al. stating that in about 80-85% of maritime accidents Human Error is the dominant factor [START_REF] Baker | Accident database review of human element concerns: What do the results mean for classification?[END_REF]. Further Grech et al. have stated that about 71% of maritime accidents caused by Human Error are caused by a lack of Situation Awareness [START_REF] Grech | Human error in maritime operations: Analyses of accident reports using the leximancer tool[END_REF]. We combined these two statistics in the following calculations: estimate lower = 535 × (71% × 80%) = 535 × 56% = 300 estimate higher = 535 × (71% × 85%) = 535 × 60% = 321

Discussion

The relationship between documents and SA Demons is a many-to-many relationship. That means more than one SA Demon could have lead to the accident. Our previously introduced weak sanity check suggests that our retrieval was quite successful. However, without knowing the number of false negatives and the recall of our retrieval this is just an educated guess.

We did not find any accidents caused by requisite memory trap, misplaced salience or complexity creep. However, the fact that we were not able to find them does not mean they do not exist. We expected these demons to be hard to find. Endsley has already stated in her definition of the SA Demons that "complexity is a subtle SA Demon" [START_REF] Endsley | SA Demons: The Enemies of Situation Awareness[END_REF].Requisite memory trap is an internal processing problem that is hard to observe. The same applies to misplaced salience. As our source of data are accident reports, the completeness of the data regarding SA failures depends on the ability of the respective inspector conducting the investigation to identify human errors and their causes. The completeness therefore varies from inspector to inspector depending on their interpretation abilities and work experience.

The most frequent found SA Demons all affect Situation Awareness Level 1. This confirms prior work by Grech et al. identifying Situation Awareness Level 1 as most prominent cause for a lack of Situation Awareness [START_REF] Grech | Human error in maritime operations: Analyses of accident reports using the leximancer tool[END_REF].

Conclusion

Our results confirm that Situation Awareness Level 1 is the most prominent source of Human Error in maritime accidents. Likewise it is the most prominent one of the three levels of Situation Awareness. All in all, the SA Demons with the highest proportion in the investigated sample were WOFAS with fatigue as main cause, errant mental models, and attention tunneling. We were not able to find accidents caused by requisite memory trap, misplaced salience or complexity creep, however we still think that these exist. Unfortunately detecting these SA Demons in maritime accident investigation reports will remain difficult, unless it becomes part of the investigation itself. We advise taking special care of the SA Demons WOFAS, errant mental models, data overload and attention tunneling when designing new interfaces for ship bridges. Our findings might also be beneficial for the design of user interfaces for Vessel Traffic Management (VTM) We intend to improve our retrieval method by labeling ship personnel in the corpus using a custom-built tool for named-entity-recognition of maritime personnel such as the 'master' or the 'OOW' 7 . This will enable us to use higher level queries such as PERSON ∧ fatigue. Also, we intend to apply our method of analysis to our full corpus of retrieved reports with refined keywords and queries in the future. We expect to get similar results in relation to the corpus size and to find further examples of SA failures caused by SA Demons.

Figure 2 .

 2 Figure2. This is a word cloud of the one hundred most frequent terms in the MAIB Corpus. The terms have been reduced to their stem using the SnowballC stemming algorithm.

, Anxiety, Fatigue, and other Stressors (

  Endsley et al. determined eight types of causes for failures in SituationAwareness, the so-called Demons of Situation Awareness (SA Demons)[START_REF] Endsley | SA Demons: The Enemies of Situation Awareness[END_REF]. The following list 1 describes each SA Demon and states the Situation Awareness levels it affects.

	SAD1 Attention Tunneling (SA level 1)
	Good Situation Awareness is dependent on switching attention among
	multiple data streams. Locking in on certain data sources and excluding
	others is attention tunneling.
	SAD2 Requisite Memory Trap (SA level 2)
	The working memory processes and holds chunks of data to support
	Situation Awareness level 2. The working memory is a limited resource.
	Systems that rely on robust memory do not support the user.
	SAD3 WorkloadSA level 1 and
	2)
	Stress and anxiety are likely issues in the warning environment. WAFOS
	taxes attention and working memory.
	SAD4 Data Overload (SA level 1)

Table 1 .

 1 This

		MAIB	NTSB	USCG	ATSB	TSBC
	# Reports	535	152	202	80	407
	Period	1989-2015	1994-2015	2005-2015	1987-2015	1990-2015
	Country	Great Britain	USA	USA	Australia	Canada

table gives an overview of the retrieved corpus. The table shows the total number of available full-text reports, the time period covered by the reports and the country of origin. (last update: April 15, 2016)

  Table 2 shows the resulting list of generated keywords for each of the SA Demons.

	SA Demon	Keywords
	SAD1	preoccupied (himself/herself), pre-occupied (himself/herself),
		focus, not attent, no attent, fixate, concentrate, not note
	SAD2	forget, forgot, not remember, no memory
	SAD3	fatigue, workload, stress;
		negative keyword combinations:
		fatigue crack, fatigue wear, unlikely, distress, rope stress
	SAD4	occupied, data overload
	SAD5	caught attention, attracted attention, draw attention, distract,
		mislead attention
	SAD6	misinterpret, not understand, complex
	SAD7	misinterpret, misunderstand, misunderstood, not correct
	SAD8	not aware, unaware
	Human Error	human error, human element, human factor
	Situation Awareness situation, aware
	Table

Table 4 .

 4 Retrieved occurrences of SA Demons in MAIB Corpus. The Percentage behind the absolute counts indicates the count relative to the corpus size.

	SA Demon	Description	True Positives	Query Precision
	SAD1	attention tunneling	36 (7%)	0.14
	SAD2	requisite memory trap	not found	-
	SAD3	WOFAS	216 (40%)	0.87
	SAD4	data overload	34 (6%)	0.17
	SAD5	misplaced salience	not found	-
	SAD6	complexity creep	not found	-
	SAD7	errant mental models	40 (7%)	0.93
	SAD8	out-of-the-loop syndrome	7 (1%)	0.02
	Total		333 (62%)
	Expected		300-321 (56-60%)

based on: http://www.au.af.mil/au/awc/awcgate/noaa/anti_situation_awareness. pdf

https://www.gov.uk/government/organisations/marine-accident-investigationbranch

3 http://www.ntsb.gov/investigations/accidentreports/pages/accidentreports.

aspx 4 http://www.

uscg.mil/ 5 https://www.atsb.gov

.au/marine/ 6 http://www.tsb.gc.ca/eng/rapports-reports/marine/index.asp

Acknowledgments

We thank the Ministry of Science and Culture of Lower Saxony for supporting us with the graduate school Safe Automation of Maritime Systems (SAMS).


Changyu Dong
email: changyu.dong@imperial.ac.uk

Naranker Dulay
email: n.dulay@imperial.ac.uk

Shinren: Non-monotonic Trust Management for Distributed Systems ⋆

The open and dynamic nature of modern distributed systems and pervasive environments presents significant challenges to security management. One solution may be trust management which utilises the notion of trust in order to specify and interpret security policies and make decisions on security-related actions. Most logic-based trust management systems assume monotonicity where additional information can only result in the increasing of trust. The monotonic assumption oversimplifies the real world by not considering negative information, thus it cannot handle many real world scenarios. In this paper we present Shinren 1 , a novel non-monotonic trust management system based on bilattice theory and the any-world assumption. Shinren takes into account negative information and supports reasoning with incomplete information, uncertainty and inconsistency. Information from multiple sources such as credentials, recommendations, reputation and local knowledge can be used and combined in order to establish trust. Shinren also supports prioritisation which is important in decision making and resolving modality conflicts that are caused by non-monotonicity.

Introduction

The advances in communications and computing research have brought distributed systems and pervasive environments to new prominence. Applications are now distributed across the boundaries of networks, organisations, even countries and deployed on smaller mobile devices. The increasing scope of distributed applications also implies that applications must deal with "strangers" from other organisations and places. This leads to new challenges. How does the security system determine whether or not a request should be allowed if the request comes from an unknown user? The system must be able to decide without pre-knowledge of the user in order to authorise/deny the access. In other words, the system must determine whether and by how much does it trust a user. Trust management [START_REF] Blaze | Decentralized trust management[END_REF] was introduced in response to the challenges posed by modern distributed systems and pervasive environments.

In real-life, trust is normally non-monotonic. Consider the following:

"You are the CEO of a bank and looking for someone to manage a multi-billion pounds investment fund. A CV arrives on your computer. You quickly read through it: worked for the UK's oldest investment bank (interesting), had more than ten years experience as a derivatives trader (good), was the Chief Trader and General Manager of operations in futures markets on the Singapore Monetary Exchange (great), made £10 million a year which accounted for 10% of former employer's annual income (excellent). You almost make up your mind. Then you see the candidate's name: Nick Leeson2 . Everything is turned upside down. You trash the email." From the diagram we can see that when new information comes in, trust can decrease, as well as increase, sometimes drastically. In other words, trust is non-monotonic. The non-monotonicity of trust is a natural consequence of the existence of both goodness and badness in the world. Trust, as defined by Mayer and Davis [START_REF] Mayer | An integrative model of organizational trust[END_REF], is "the willingness of a party to be vulnerable to the actions of another party". To trust someone, the trustor needs to judge how competent, how honest, how dependable the trustee is, but more importantly, how incompetent, how dishonest and how undependable the trustee is. Positive information tells us how much we may gain from a trust relationship, while negative information tells us how much we may lose from it. Ignoring negative information may result in misplaced trust which may in turn cause serious damage to the trustor.

Although trust is non-monotonic, mainstream logic-based trust management systems [START_REF] Blaze | Decentralized trust management[END_REF][START_REF] Blaze | The keynote trust-management system, version 2[END_REF][START_REF] Jim | Sd3: A trust management system with certified evaluation[END_REF][START_REF] Li | Design of a role-based trust-management framework[END_REF][START_REF] Hess | An access control model for dynamic client-side content[END_REF][START_REF] Carbone | A formal model for trust in dynamic networks[END_REF] are monotonic. The reason is that complete knowledge is hard to achieve in large distributed systems and also that those systems are based on classical logic which cannot cope with this situation. Classical logic is monotonic which means a conclusion will never be retracted with new information, i.e. if Γ |= φ then Γ ∪ γ |= φ. To model trust with classical logic, a monotonic assumption is introduced to solve the problem and simplify the design by not using negative information about the world. Monotonic systems do not have problems with incomplete information because all missing information is positive and every decision that they make can only be more "correct" with more information. Accepting the monotonic assumption means accept-ing the world is always positive (however if there were no negative things in the world, do we still need trust management systems?). Monotonic trust management systems have many advantages, but the monotonic assumption is too limiting for many scenarios.

The gap between real world requirements and the current design of trust management systems motivates our work. A more realistic solution is needed for managing trust in distributed systems. In this paper, we describe Shinren, a novel non-monotonic trust management system based on bilattice theory and the any-world assumption. Shinren can make reasonable decisions even with incomplete information. Moreover, it can also utilise unreliable information which makes it more suitable for open distributed systems where reliable information is often hard to come by. Shinren does not just simply make use of the existing theories, it also supports prioritisation, which is achieved by a non-trivial extension of the original theories. Prioritisation is important in resolving conflicts and providing support for decision making.

This paper is organised as follows: We first summarise and compare existing nonmonotonic trust management systems with Shinren in section 2. Then we discuss the motivation of this work in section 3. In section 4 we introduce bilattice theory and the any-world assumption. In section 5, we describe Shinren, its policy language and present an example to show the details of policy evaluation in Shinren. In section 6 we show a prototype implementation. Section 7 concludes the paper.

Non-monotonic Trust Management Systems

Shinren is not the first logic-based non-monotonic trust management system. Rule-Controlled Environment For Evaluation of Rules and Everything Else (REFEREE ) [START_REF] Chu | Referee: Trust management for web applications[END_REF], the Trust Establishment System (TES) from IBM [START_REF] Herzberg | Access control meets public key infrastructure, or: Assigning roles to strangers[END_REF] and RT ⊖ [START_REF] Czenko | Nonmonotonic trust management for P2P applications[END_REF] are also nonmonotonic.

The main problem of existing logic-based non-monotonic trust management systems is semantics. A well-defined formal semantics is a critical part of any policy language. However, REFEREE and TES do not have formally defined semantics. RT ⊖ is based on the well-founded semantics which is a non-monotonic semantics proposed originally for logic programming with negation [START_REF] Gelder | Unfounded sets and well-founded semantics for general logic programs[END_REF]. The problem with using wellfounded semantics in trust management is that it is based on the closed world assumption (CWA) and the uniformity of CWA may lead to counter-intuitive results. For example, here is a simple trust policy trust(a) : -¬bad(a). Under the well-founded semantics, when bad(a) is missing or not provable, it is falsified and thus makes trust(a) true. However, this decision may seem too casual, especially when it is related to security. In Shinren, policy makers can use unknown as the default value for bad(a) while still use f alse as the default value for other positive atoms.

Existing non-monotonic trust management systems are also less expressive than Shinren. For example, RT ⊖ can only express policies using credentials. Among them, REFEREE is the most expressive one. It is capable of expressing policies utilising evidence from different sources, but it is incapable of distinguish decisions based on information of different quality. REFEREE is based on 3-valued logic, therefore there is no difference between a decision based on a statement from an authority and a decision based on rumour. The users of REFEREE may be given an unreliable trust decision without warning. In Shinren, a trust decision comes with a value which tells the user not only how true the decision is, but also how reliable it is.

Many systems attempt to assign real values to trust and develop sophisticated mathematical models to calculate trust values [START_REF] Marsh | Formalising Trust as a Computational Concept[END_REF][START_REF] Jøsang | A logic for uncertain probabilities[END_REF][START_REF] Yu | Detecting deception in reputation management[END_REF]. The values are usually based on past experience. Although they are also called trust management systems, we view them as a totally different approach from the trust management systems presented above which rely mostly on logical reasoning and view trust decisions as logical consequences of certain facts and theories. Quantitative trust management systems are usually nonmonotonic and can provide valuable information. However, the accuracy of the trust values largely depends on the amount of data input and may take a long time to get enough data. To differentiate, we call them reputation systems and Shinren can include such systems as subsystems.

Why Non-monotonic? Why Shinren?

So why do we need non-monotonic trust management systems? This is because (1) in the real world trust is non-monotonic and therefore a trust management system should be able to capture this; (2) monotonic assumption is not necessary in trust management, it is introduced merely because systems reasoning with classical logic cannot cope with the non-monotonicity in trust. The assumption does not solve the problem, it just makes systems ignore the problem. There are at least two bad consequences of monotonic assumption: first, a trust management system which can be proved correct under the monotonic assumption may not be correct in the real world because the assumption does not hold in general; second, it makes trust management systems incapable of handling certain real world scenarios.

Under the monotonic assumption, monotonic trust management systems do not consider negative information. Syntactically, this is achieved by not allowing negations in the policies. Negation-free policies work fine in some cases, however they reflect a limited view of the world and are inappropriate in many cases. For example, negationfree policies are quite inconvenient in handling exceptions. In the world modelled by negation-free policies, it is quite hard to express, "trust all the police officers except the bad ones" because without negations, we would be allowed to say "trust police officers" but not "do not trust the bad police officers". In the extreme case, we must specify for each individual good police officer a trust policy in order to exclude the bad ones. Lacking the ability for specifying exceptions can be dangerous particularly in trust management systems where delegations are used. No exceptions means that decisions have to be fully delegated to a delegatee, and the system must fully accept the delegatee's opinions. No exceptions also means that the system cannot accept part of the delegatee's decision while declining other parts. In other words, the system loses control after delegation. Another case is that negation-free policies cannot handle mutual exclusion. Coke is tasty, orange juice is tasty too. But the mixture of the two does not taste so pleasant. There are many examples that are mutually exclusive. However, with negation-free policies, there is no way to express "A is good, B is good, but A+B is not good". In terms of security policies, separation of duties and conflict of interests are the most significant examples of this type of policy.

One may argue that in the real world, people try to hide their negative aspects. Therefore, even if policies are allowed to use negative information, if the system cannot find it, the non-monotonic feature is useless. It is true that the information we can collect is always limited. But consider the following:

In monotonic trust management systems : trust :good

In Shinren : distrust :bad trust :good What is the difference? When the system cannot find bad, i.e. the negative information, Shinren can behave exactly as the monotonic ones. However, because it is not possible to use negative information in monotonic trust management systems, their decisions will still be trust even if bad is presented! In contrast, Shinren's decision will no longer be trust because the distrust policy is applied. Although not guaranteed, Shinren aims to limit any damage with its best effort approach rather than silently ignoring it. By using bilattices, Shinren suffers less from a dilemma which all trust management systems must face: on the one hand, in order to make a correct trust decision, a large amount of information is needed; on the other hand, in order to make the decision correct, most of the information available cannot be used because it is not reliable. Shinren can reason with unreliable information even with contradictory information. Monotonic trust management systems cannot. This ability is especially important in acquiring negative information.

Prioritisation is not present in any trust management systems. The philosophy is that sometimes trust is not just a Yes/No decision, but also a choice. You might want to follow one rule even if there are multiple rules you can follow, you might trust someone even if there are several persons you can trust. Prioritisation allows policy makers to specify their preferences and thus make complex policies possible. And also, in the presence of modality conflicts, prioritisation seems to be the only way to resolve them. Although there are overheads in defining and managing policies when using prioritisation, the overheads are minimised in Shiren because policy makers only assign priorities to local policies and only trust (distrust) policies are prioritised.

Preliminaries

Bilattices

Bilattice theory [START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF] was introduced by Ginsberg in the 1980s, and has been widely used in non-monotonic reasoning, knowledge representation and artificial intelligence. Bilattice is a non-empty, possibly infinite set of values with two partial orders, each one giving the set the structure of a lattice. A lattice L, is a non empty set L along with a partial order where any pair of elements l 1 , l 2 ∈ L has a least upper bound (join) and a greatest lower bound (meet) in terms of . We write

l 1 ≺ l 2 if l 1 l 2 and l 1 = l 2 .
A bilattice, denoted by B, t , k where B is a non-empty set and t , k are two partial orders called the truth-order and the knowledge-order respectively. t is an ordering on the "degree of truth". The class of bilattice that we consider in this paper is restricted to interlaced bilattices. Interlaced bilattices are bilattices which satisfy the following:

(1) if b 1 t b 2 then b 1 ⊗ b 3 t b 2 ⊗ b 3 and b 1 ⊕ b 3 t b 2 ⊕ b 3 ; (2) if b 1 k b 2 then b 1 ∧ b 3 k b 2 ∧ b 3 and b 1 ∨b 3 k b 2 ∨b 3 .
Thus in an interlaced bilattice an operation associated with one of the lattice orderings is required to be monotonic with respect to the other lattice ordering. This relates the two orderings. An alternative way of connecting the two orderings is via negation which reverses the truth ordering and is monotonic regarding the knowledge ordering.

Such bilattices can be constructed in a natural way by combining two lattices. Given two lattices L 1 , 1 and L 2 , 2 , we can construct an interlaced bilattice as

L 1 × L 2 , t , k , where (x 1 , y 1 ) t (x 2 , y 2 ) if x 1 1 x 2 and y 2 2 y 1 , (x 1 , y 1 ) k (x 2 , y 2 ) if x 1 1 x 2 and y 1 2 y 2 . Negation can be defined as ¬(x, y) = (y, x) if L 1 = L 2 .
As we will see later, the bilattice used in our system is constructed in this way. We will expand on this later.

Any-world Assumption

Non-monotonic logics allow a conclusion to be drawn on incomplete information. One way of doing such reasoning is to complete the missing part by assumptions. Taking into account assumptions means assigning truth values, implicitly or explicitly, to the unknown facts. The assumptions are usually based on the estimated states of the facts. One of the most common assumptions is the Closed World Assumption (CWA). It assumes the default truth states of atoms to be f alse, therefore any atoms that cannot be proved to be true are taken as f alse. Another well-known assumption is the Open World Assumption (OWA). OWA is a more cautious assumption in the sense that it assumes the default truth states of atoms to be unknown. Therefore, any atoms that cannot be proved to be true are taken as unknown. However it also gives us less useful conclusions. Using only one of these assumptions to represent the world uniformly is usually not appropriate.

The Any-World Assumption (AWA) [START_REF] Loyer | Any-world assumptions in logic programming[END_REF] unifies and extends the CWA and OWA by taking truth values from an arbitrary bilattice truth space and allow the default value of an atom to be any one of them. If in the assumptions, all the atoms are assigned to f alse, then it becomes CWA which says everything that cannot be inferred is false. If in the assumptions, all the atoms are assigned to unknown, then it becomes OWA which says everything cannot be inferred is unknown. The advantages are obvious: the truth, incompleteness and uncertainty can be represented in a finer granularity according to the experience and background information, therefore the assumptions we make carry more knowledge than before which in turn leads to more informed conclusions. The

Shinren

Bilattice N IN E

As introduced in Section 4.1, a standard way of constructing an interlaced bilattice is by combining two lattices. The bilattice we employ, N IN E, is also built in this standard way. N IN E is obtained by combining two identical lattices L 1 = L 2 = {0, 1 2 , 1}, ≤ where ≤ is "less than or equal". The structure of N IN E is shown in Figure 2. The truth values are represented as tuples (x, y) where x, y ∈ {0, 1 2 , 1}. The two orderings, t , k are defined as:

(x 1 , y 1 ) t (x 2 , y 2 ) if x 1 ≤ x 2 and y 2 ≤ y 1 (x 1 , y 1 ) k (x 2 , y 2 ) if x 1 ≤
x 2 and y 1 ≤ y 2 Given a statement with a truth value of the form (x, y), the intuitive meaning of the truth value is that x represents how much the statement is true (or you believe it is true), and y represents how much the statement is false (or you believe it is false). For example, (1, 0), i.e. reliably true, is given to a statement supported by very strong and reliable evidence. The possibility of the statement is actually false can be neglected.

From the above it is easy to understand the two orderings. For example, a statement which is reliably true contains more truth (or is more likely to be true) than a statement which is not so reliably true, i.e. ( 1 2 , 0) t (1, 0). On the other hand, a reliably true statement gives us more information than a not so reliably true statement, i.e. ( 1 2 , 0) k (1, 0). It is possible to extend the bilattice to a finer model of reliability or uncertainty. For example, using a lattice with the value domain {0, 1 3 , 2 3 , 1}, we can create a bilattice with 16 truth values that can represent more reliability levels. However, we do not do so for two reasons: first, enlarging the bilattice also increases the computational complexity. With enough expressiveness, we would like to avoid unnecessary cost; second, things like reliability and uncertainty cannot typically be measured precisely. There are no metrics and instruments we can use to standardise the measurement. A finer scale does not help in solving this problem, even worse, it may bring a false sense of precision. For these reasons, we stay with this basic form and extend it when it is necessary and possible.

Let us also explain the rationale behind this multi-valued truth space. Classical logic, which is the basis of many trust management systems, is bivalent, i.e. the only possible truth values are true and f alse. It gives rise to "black and white thinking" where every proposition must be ascribed to "absolutely true" or "absolutely false". However, in the real world, many would agree with the statement "the only certainty is nothing is certain" 3 . Because classical logic lacks the ability of coping with the uncertainty in truth, mainstream trust management systems restrict the information that can be taken into account to "credentials". A credential is a statement signed by an issuer containing certain information about the credential holder and is believed to be highly reliable. The problems with credentials are two-fold: first, credentials are not able to carry every bit of information about the holder. We may find that signed information is just a very small fraction of all the information we can get. Second, in practice we do not encode negative information about the holder in credentials. The reason is simple: no one bothers to ask for a credential which is useless or has a negative effect to him. Again, we usually recognise a rogue merchant not from a "rogue merchant" credential signed by a government agency, but from various other sources like reviews in internet forums. If we want a more complete view of the trustee, using only credentials is not sufficient. We need to consider more information, possibly even that from the sources which are not so reliable. The multi-valued truth space gives Shinren the ability to represent and differentiate information with different qualities. And makes it possible for Shinren to utilise unreliable information.

The meet and join operators in terms of both orderings and the negation operator are then defined as follows:

(x 1 , y 1 ) ∨ (x 2 , y 2 ) = (max(x 1 , x 2 ), min(y 1 , y 2 )) (x 1 , y 1 ) ∧ (x 2 , y 2 ) = (min(x 1 , x 2 ), max(y 1 , y 2 )) (x 1 , y 1 ) ⊕ (x 2 , y 2 ) = (max(x 1 , x 2 ), max(y 1 , y 2 )) (x 1 , y 1 ) ⊗ (x 2 , y 2 ) = (min(x 1 , x 2 ), min(y 1 , y 2 )) ¬(x, y) = (y, x) We will explain these with some examples. Given a statement p which is reliably true and q that is not so reliably true, the truth value of their conjunction is p

∧ q = (1, 0) ∧ ( 1 2 , 0) = (min(1, 1
2 ), max(0, 0)) = ( 1 2 , 0), i.e. not so reliably true. This is easy to understand. Let p be "Alice is a student" and q be "Alice is a research assistant", then the statement "Alice is both a student and a research assistant" cannot be very reliable because we are not quite sure about the fact that she is a research assistant. Consider another example: in the court of a murder case, the prosecutor submits a CCTV record as evidence showing that the suspect was at the crime scene when the murder was happening, while the counsel of the suspect has a witness, who is a friend of the suspect, to certify that the suspect was in a pub 50 km away from the scene at the same time. It turns out the conclusion of whether the suspect was at the scene after we combine these two pieces of evidence is: (1, 0) ⊕ (0, 1 2 ) = (max(1, 0), max(0, 1 2 ) = (1, 1 2 ). That is, although doubtful, we would believe the suspect is at the scene. The reason is that the video record is more reliable evidence.

Shinren Policy Language

The syntax of Shinren is based on the logic programming language Datalog [START_REF] Ceri | What you always wanted to know about datalog (and never dared to ask)[END_REF], with certain extensions. As in Datalog, we do not have function symbols. The restriction is necessary to ensure finiteness of models and termination of inference. A rule, or policy, is of the form:

A :ϕ 1 , ..., ϕ n . where A is an atom and each ϕ i is a literal, a consensus formula or a gullibility formula. ": -" is taken as "←" and "," is taken as "∧". The atom A on the left-hand side of the rule is called its head and the conjunction ϕ 1 , ..., ϕ n on the right-hand side is called its body. Certain types of rules may also have a priority label lab attached before the rules (will explain later). An assertion is a special type of rule defined as:

A :b. where A is a ground atom and b is a truth value. An assertion can be understood as A has a truth value b. A fact set is a finite set of assertions. An assumption set is also a finite set of assertions. The difference is that the fact set contains the real truth values for the atoms while the assumption set contains the assumptions, i.e. assertions about the default values of the atoms. The assumptions are used only when no facts about the atoms can be found in the fact set or be inferred. We do not need to explicitly represent assumptions of the form A : -(0, 0). If no assumption about an atom can be found in the assumption set, the default value is (0, 0). A program is the union of a finite set of rules, a fact set and an assumption set.

By using the Shinren trust policy language, policy makers can define both trust policies and distrust policies, i.e. rules whose heads are trust or distrust predicates. They can also label the policies with priority levels. The priority levels express how preferable a policy is. The priority levels in Shinren language are defined as a finite set of non-negative integers {0, 1, ..., n}. 0 is reserved for default assignment rules. The higher the number is, the higher the priority is. For each priority level, policy makers also define two thresholds in terms of t or k or both, one for distrust policies and one for trust policies. The thresholds are used to filter poor answers. Answers that satisfy the threshold are called admissible answers. Note that only trust or distrust policies need labels, the other policies are not prioritised. When the system is asked to evaluate trust, it starts from policies with the highest priority. At the same level, distrust policies are evaluated before trust policies. In other words, distrust policies have a higher priority than trust policies at the same priority level. If an admissible answer can be found, then the evaluation ends. Otherwise it continues to evaluate the trust policies at the same level. If there are still no admissible answers, the system continues with the policies at the next level. When an admissible answer is found with truth value b, an answer for its counterpart is asserted with a truth value ¬b. For example, if the evaluation ends with an admissible answer distrust(a) = ( 12 , 0), we also have trust(a) = (0, 1 2 ). If after evaluating all the policies at higher priority levels, an admissible answer is still not found, the default value is applied. The default value assignment rules may be omitted, in this case the default value is (0, 0).

The prioritisation mechanism can be used to resolve modality conflicts introduced by trust and distrust policies. Trust and distrust are semantically opposite and it is possible in some situations that both are true based on the policies. Therefore we need to handle the possible conflicts. With priority levels, the conflicts can be resolved by "interlacing" distrust and trust policies and the decisions are governed by the policies with the highest priority levels which give admissible answers. The priority levels can also be used to order trust decisions. For example, if we have decided both Alice and Bob can be reliably trusted, we may prefer Alice if the decision about her came from a trust policy with a higher priority level, i.e. a more preferable policy. The truth values and priority levels can give hints to the decision maker. If the decision is not reliable or from a less preferable policy, it may indicate that the decision is not favourable and may be risky. The decision maker can activate some compensative controls based on the truth value and priority levels.

In order to achieve prioritisation, we require the program to be locally stratified, i.e. there are no cyclical dependencies between ground atoms. This syntactical restriction is needed to guarantee the policies can be evaluated correctly.

Due to space limit, the formal semantics of Shiren is omitted here but is available in the full version [START_REF] Dong | Shinren: Non-monotonic trust management for distributed systems[END_REF]. In next section, we will show the policy language by an example. Another example can be found in the appendix.

Example 1: Electronic Marketplace

Alice is a big fan of Internet shopping and she often visits a website called tBay which is an electronic marketplace like e-bay. Although she has bought a lot of items with very low prices, she also had several unpleasant experiences. So she wants to be cautious before she bids on anything from the website. She decides that she will only bid on items from sellers who live in the UK, have been registered no less than 6 months and have at least 80% positive feedback. She will also ask her friend Bob about his opinion and will not consider a seller if Bob does not like him. However, she knows tBay has a special procedure for items with bid prices lower than £20: in case of dispute, tBay will fully refund the buyer. Since she is not going to lose money, Alice is willing to bid in such situations regardless of her other constraints above. But Alice also has a more important principle: she will never trade with someone who has cheated her. She has a blacklist of such sellers. Alice's policies are:

Alice's policies have 3 priority levels. At the highest level is the policy which should not be overridden by any other policies. At the second level is a trust policy that allows her to interact with any seller when there is no risk. The lowest level has two policies for general cases. In the policies, seller(tBay, X, Location, RegisterP eriod) represents a seller credential signed by tBay. soldBy(X, Item), itemP rice(Item, P rice) and inBlackList(X) are local knowledge predicates supplying useful information. For each priority level, Alice defines thresholds for admissible answers to be (0, 0) ≺ t , which means only answers somehow true (reliably true, not so reliably true, doubtfully true) will be admissible.

Along with the policies, Alice also has a set of assumptions:

soldBy(X, Item) : -(0, 1).

itemP rice(Item, P rice) : -(0, 1).

inBlackList(X) : -(0, 1).

Recall that (0, 1) means "reliably false". Alice's assumptions are: if she cannot find any information that says an item is sold by seller X, then this item is not sold by X; if she cannot find any information that says an item is sold for a certain price, then it is not sold for this price; if she cannot find a seller in her blacklist, then he is not in her blacklist. These are easy to understand. All the other predicates are left with default values of (0, 0), i.e. unknown. Different default values may make a big difference. For example, if Alice assumes recommendation(bob, X, bid, Item) to be false, i.e. add recommendation(bob, X, bid, Item) : -(0, 1) to her assumption set, then she cannot bid anything with a price higher than £20 when she cannot contact Bob. In such cases, since she cannot get recommendations from Bob, the default value will be used and the policy distrust(X, bid, Item) : -¬recommendation(bob, X, bid, Item).

will always give results of "distrust" with truth value (1, 0). More complicated policies are also possible. For example, if Alice has another policy which says she will bid if at least two of her friends recommend the seller. This can be written as:

trust(X, bid, Item) : -f riend(F 1), f riend(F 2), recommendation(F 1, X, bid, Item) ⊗ recommendation(F 2, X, bid, Item).
Alice collects the following facts when she tries to find a cheap iPod on tBay: Although not signed, Alice considers the information about who is the seller and the price of the item as reliable. However, the reputation is not. Alice knows at least ten ways which sellers can boost their reputation quickly.

When evaluating the policies, only the assumptions:

recommendation(bob, carol, bid, ipod) : -(0, 0)

inBlackList(carol) : -(0, 1)
are used. This is because Alice does not have any relevant information. The other assumptions are not used because Alice has collected the facts and therefore does not need to assume anything. Let us also explain how the trust (distrust) policies are evaluated. Shinren starts from priority level 3. For the distrust policy at this level, the body is inBlackList(carol) with truth value (0, 1) in the interpretation. Therefore distrust(carol, bid, ipod) is evaluated to be (0, 1), according to this policy. Because (0, 0) ≺ t (0, 1), this answer is not admissible and is discarded. The policy with priority 2 does not have an admissible answer either. Given itemP rice(ipod, 80) = (1, 0), the constraint P rice ≤ 20 is not satisfied because the price is £80. This constraint is linked to itemP rice(ipod, 80), so its truth value is ¬(1, 0) = (0, 1). Overall, trust(carol, bid, ipod) is evaluated to (0, 1) according to this policy. The answer is also discarded. Because Alice cannot get a recommendation from Bob, the default value is used and the distrust policy at priority level 1 is evaluated to (0, 0). The answer is also not admissible. The last policy is evaluated to ( 1 2 , 0) and therefore is admissible. Because it is a trust policy, we add trust(carol, bid, ipod) = ( 12 , 0) and also distrust(carol, bid, ipod) = (0, 1 2 ) to the model. Alice now knows that although Carol can be trusted, she might still be cheated.

Implementation

We have implemented a prototype of Shinren. As shown in Figure 3, Shiren consists of five major modules. Among the five modules, the credential module, the recommendation module, the reputation module and the state module are responsible for retrieving and interpreting information from different sources, and the policy interpreter module is responsible for making decisions according to the policies and the information gathered.

The Shinren prototype is implemented in Java 1.5. The policy interpreter evaluates queries in a bottom-up fashion as in many other datalog-based systems. Policies are loaded into the policy interpreter as plain text files. The rules are stratified when they are loaded by analysing the predicate dependency relationships. To answer a query, the interpreter first initialises an interpretation which is an instance of the Assertion-Set class. The interpreter queries the other four modules in order to gather facts, i.e. ground instances of the predicates with truth values, which are needed for policy evaluation. The facts are stored in tables related to the predicates in the interpretation. After the interpreter obtains all facts, it constructs the Herbrand universe by collecting all the constants from the query, rules and facts. The interpreter then puts into the initial interpretation assumptions for all the other ground atoms which are in the Herbrand base. It then starts evaluating policies iteratively from the lowest strata. Each rule in the stata is grounded with regard to the Herbrand base and then the interpreter applies the immediate consequence operator to each ground instance. The immediate consequence operator retrieves the truth values for the ground atoms in the rule body from the current interpretation and passes them through the evaluation tree of the rule to obtain the truth value of the ground head atom. The ground atom along with the truth value is a newly generated fact and the table for the head predicate in the interpretation is updated. If an entry with the same ground tuple is already in the table, the truth value of the old entry is ORed with the truth value of the new entry; otherwise the new entry is inserted into the table. Trust (distrust) policies in the same strata are evaluated sequentially by priority level until an admissible answer, i.e. an answer that satisfies the threshold defined for this level, is found. The evaluation of the strata ends when the interpretation does not change anymore. Then the interpreter evaluates the rules in the next strata. The evaluation of the query ends after the interpreter evaluates all the strata containing the rules with the queried atoms as heads.

Conclusion and Future work

In this paper, we have presented Shinren, a novel non-monotonic trust management system based on bilattices and the any-world assumption. The syntax of the Shinren policy language is based on Datalog with certain extensions such as negation, constraints and prioritisation. Shinren can utilise unreliable even contradictory information and supports prioritisation which resolves conflicts and provides decision support. We demonstrated the power of Shinren by two comprehensive examples and outlined its implementation. The semantics of Shiren extends the Kripke-Kleene semantics over bilattices and is given in [START_REF] Dong | Shinren: Non-monotonic trust management for distributed systems[END_REF].

One aspect that we would like to investigate further is prioritisation. The current prioritisation mechanism in Shinren is at the meta-level. It works but is not convenient in practice because it is external to the bilattice. However, prioritisation can also be viewed as another ordering. We would like to extend our bilattice, so that a third ordering could be integrated into the theory. This would make prioritisation a built-in feature.

The any-world assumption uses the concept of non-uniform assumption. However, its assumptions are static. We are interested in researching dynamic assumptions which would mean that changes in knowledge could lead to the change of the assumptions. Dynamic assumptions would enable a trust management system to generate more accurate conclusions according to the context. Previous works in belief revision [START_REF] Alchourrón | On the logic of theory change: Partial meet contraction and revision functions[END_REF] and dynamic prioritisation [START_REF] Brewka | Reasoning about priorities in default logic[END_REF] are possible stepping stones in this direction.

Patients' medical histories are sensitive and should only be revealed to doctors who are treating the patients. The distrust policy at level 3 says that X is not allowed to read patient Y 's medical history if X does not have a doctor credential signed by the BMA (British Medical Association). The second trust policy at the same level says X is trusted to read patient Y 's medical history if Y gives his consent. However, in real-life, it is not always possible to get the patient's consent, e.g. in the case that the patient is in coma. Then a third party consent from the patient's agent, usually the next of kin, also has the same effect. In emergency situations where no consent can be obtained, it is necessary to verify that the doctor is indeed treating the patient before letting the doctor access the information without consent. For example, the verification might be done by letting the doctor provide the patient's personal information and comparing it with the data stored, or using a location service to verify that the doctor is co-located with the patient. Accesses without consent are logged and audited.

Dr Taylor provides his doctor credential and also supplies information about Mr Johnson's birthday and address correctly. The access is granted and logged. Alas the medical history does not provide too much useful information. At the same time, Mr Johnson's condition becomes worse. He starts to have seizures and EEG (electroencephalogram) shows abnormal brain activities.

Dr Taylor suspects that the problem may be in Mr Johnson's brain. However, he is not a neurologist and needs someone to help in diagnosing the patient. Dr Taylor starts looking for help. He searches the NHS database using Shinren with the policies shown below:

2 trust(X, specialist, neurology) : -consultant(Hos, X, neurology), hospital(N HS, Hos), member(aon, X, Level), Level >= 2.

1 trust(X, specialist, neurology) : -consultant(Hos, X, neurology), hospital(N HS, Hos), member(aon, X, 1), member(aon, Y, Level), Level >= 2, recommendation(Y, X, specialist, neurology).

The first policy says that Dr Taylor will trust X as a specialist in neurology if X has a consultant credential signed by an NHS hospital which states that X is a consultant in neurology. X must also be a member of the Association of Neurologists with level no lower than senior member. The second policy says almost the same except that if the level of X in the Association of Neurologists is not high enough, he needs a recommendation from a senior member or higher.

Dr Taylor finds 20 doctors who fit his requirements. Among them, he selects Dr Ford, a senior member of the Association of Neurologists who works for Victoria Hospital. Dr Ford is also willing to offer assistance. Dr Taylor sets up a video conference with Dr Ford. After hearing the observations and checking the examination results, Dr Ford suggests that the problem could be caused by a clot in the patient's brain. However, a brain tumour also fits the symptoms. The diagnosis can be confirmed by an MRI (Magnetic Resonance Imaging) scan or a brain biopsy. However, the clinic does not have the equipment and the patient's condition is not suitable for transportation. Dr Ford then suggests that in this situation, Dr Taylor should immediately treat the patient with tPA (tissue Plasminogen Activator), a medicine which helps resolving blood clots, because a long delay could cost the patient's life. If the patient's condition gets better, then the diagnosis of a blood clot can be confirmed, otherwise it suggests a brain tumour. Dr Ford's plan could be quite dangerous. So Dr Taylor wants to hear a second opinion. To ensure the opinion is independent and fair, Dr Taylor adds another policy before he searches for the second specialist. The policy rules out all the specialists working in the same hospital as Dr Ford.

2 distrust(X, specialist, neurology) :consultant(victoria, X, neurology).

This time Dr Taylor finds Dr Grant, a senior member of the Association of Neurologists who works for the Albert Hospital. Dr Grant confirms that there is no better solution in this situation. Dr Taylor starts to treat the patient with tPA, and watches him closely. 24 hours later, the patient wakes up. After the patient's condition is stabilised, he is transferred to the nearest major hospital for further diagnosis and treatment.

Fig. 1 .

 1 Fig. 1. Non-monotonic trust for CV

b 1 t b 2

 2 means b 2 represents at least as much truth as b 1 (and possibly more). Meet and join under t are denoted by ∧ and ∨ and correspond to the classical conjunction and disjunction. k is an ordering on the "degree of knowledge". Meet and join under k are denoted by ⊗ and ⊕. b 1 ⊗ b 2 corresponds to the maximal information b 1 and b 2 can agree on, while b 1 ⊕ b 2 combines the information represented by b 1 and b 2 .

Fig. 2 .

 2 Fig. 2. The bilattice NINE

  soldBy(carol, ipod) : -(1, 0). seller(tBay, carol, uk, 12) : -(1, 0). reputation(carol, goodSeller, tBay, 0.9) : -( 1 2 , 0). itemP rice(ipod, 80) : -(1, 0).

Fig. 3 .

 3 Fig. 3. Shinren Trust Engine

Nicholas Leeson, the infamous rogue trader who caused the collapse of Barings Bank.

Pliny the Elder, Roman scholar (23-79 AD).

distrust(X, bid, Item) : -inBlackList(X).2 trust(X, bid, Item) : -soldBy(X, Item), itemP rice(Item, P rice), P rice ≤ 20.1 distrust(X, bid, Item) : -¬recommendation(bob, X, bid, Item).1 trust(X, bid, Item) :seller(tBay, X, Location, RegisterP eriod), Location = uk, RegisterP eriod ≥ 6, soldBy(X, Item), reputation(X, goodSeller, tBay, Y ), Y ≥ 0.8.

⋆ This research was supported by the UK's EPSRC research grant EP/C537181/1 (Caregrid) and EU FP7 research grant 213339 (ALLOW). 1 Shinren: the pronunciation of trust in Chinese

A Example 2: Healthcare in the Community

Dr Taylor runs a medical clinic in a small town. An unconscious patient is brought to the clinic. From the driver's licence, Dr Taylor learns that the patient is called Mr Johnson. Mr Johnson is a tourist and stayed in a local hotel before he was brought here. The owner of the hotel, who brought Mr Johnson in, tells Dr Taylor that the patient experienced breathing difficulties during breakfast and then passed out a few minutes later. Dr Taylor examines the patient's trachea and hears the lung sound. He decides to intubate the patient in order to let air pass freely to and from the lungs. The patient's temperature is normal and the results of a blood test show no signs of infection. Blood pressure and heart rate are also normal. Dr Taylor decides to check the patient's medical history in order to see whether the symptoms were caused by drugs or allergies. From his computer, Dr Taylor sends a request to the Smith GP practice, found in documents in Mr Johnson's wallet.

The electronic medical record system of the Smith GP practice uses the Shinren trust management system to control who can access patients' medical histories. The policies which regulate the access to a patient's medical history are shown blow:

3 distrust(X, read, med history, Y ) : -¬doctor(bma, X).


Adam Wójtowicz

Wojciech Cellary
email: cellary@kti.ue.poznan.pl

Representing User Privileges in Object-Oriented Virtual Reality Systems

Keywords: user privileges, virtual reality, data security, data privacy, semantic operations

In virtual reality systems which are collaborative and dynamic, i.e. where at run-time mutually interactive objects can be added or removed in different contexts and where their behavior can be modified, the problem of data security and privacy protection is renewed. In such virtual worlds operations on objects should or should not be allowed to users playing particular roles with respect to inter-object interactions. In this paper a method called VR-PR is presented, where privileges are represented by pairs: objectsemantic operations induced from object interactions. Semantic operations are generated using automatic analysis of the object method call graphs. Then they are used in the privilege creation and modification process. Privileges based on semantic operations are expressive, flexible and consistent with permanently evolving set of objects composing the virtual world, interactions between the objects, and a set of users.

Introduction

Today virtual worlds are dynamic environments where multiple objects interact with each other by calling methods in reaction to internal and external events. Virtual worlds are also creative environments, where at run-time users create new objects, modify them, assemble them into more complex objects, extend their functionality etc. In such dynamic and creative environments the problem of data privacy protection is renewed. From the business perspective, intellectual property rights of creators and publishers of objects in virtual worlds must be protected, as they are source of revenues. Thus, flexible access control using privileges based on interactions existing in a persistently running virtual world should be installed. Privileges granted to a user for a given object should be represented in a way that is compatible with the representation and semantics of intellectual property rights issued for this object. Also, the semantics of interactions between objects owned by different users should be taken into account by the privilege system. Moreover, the privilege system should automatically encompass newly created objects. In virtual worlds objects may be created from scratch by a user who becomes their sole owner, but also as compositions of preexisting objects coming from different sources. The privilege system should be expressive enough to handle such dependencies. Methods of privilege modeling developed so far, which are presented in Section 3, are either geometry-centric with no advanced interaction support or coarse-grained with no privilege semantics modeling capabilities. Those methods however are not sufficient for highly dynamic creative virtual worlds.

In this paper, a method called VR-PR is proposed of flexible user privilege representation for virtual world objects, maintaining compatibility with access control standards and the data model. The concept of this method is presented in Section 2. In Section 3 the state of the art in the field of access control models which can be applied to multi-user virtual worlds is presented, followed by critical remarks. In Section 4 VR-PR approach is presented to privilege representation and generation of semantic operations used to express privileges. In Section 5 the main issues concerned in this paper are discussed. Section 6 concludes the paper.

Contribution of the VR-PR Method to Technological Innovation

The VR-PR method concerns flexible user privilege representation for virtual world objects. The VR-PR method consists of automatic analyses of relationships and interactions between objects of a dynamic virtual world constructed according to the object-oriented data model, such as the one presented in [START_REF] Walczak | Structured Design of Interactive VR Applications[END_REF]. To this end, a semantic layer is inserted between the access control mechanism and the object-oriented data model. The semantic layer reflects real interactions between objects, represented by a set of abstract semantic operations. The set of semantic operations may slowly evolve over time. Its evolution is, however, much more stable than transformations of the virtual world objects, interactions and structure. In the VR-PR method two phases are alternately performed during virtual world run-time: the phase of automatic generation of semantic operations and the phase of privilege creation and modification. To guarantee consistency of semantic operations used during the second phase in the first phase semantic operations are created basing on automatic analysis of object method call graphs.

The following is an innovative contribution of this paper to the area of virtual world security. First, an access control model is proposed appropriate to a virtual world containing very large number of VR classes, objects and methods that is understandable and manageable for non-IT professional users who may express their will in terms of intuitively understandable semantic operations instead of object methods.

Second, a privilege system is proposed that strictly controls the allowed range of virtual world penetration by behavioral method calls. Third, an algorithm for automatic regeneration of semantic operations used in privileges is proposed, which assures privileges consistency with the data model and its integrity. It increases the security level of the security policies defined using privileges containing semantic operations.

Fourth, a two-phase induce-and-use approach is proposed, which makes the process of privilege management stable: operation set is updated on-demand, but the updates do not change as fast as the data model evolves. Semantic operations can be regenerated without modifying the existing privileges, as well as without roleprivilege and user-role assignment modifications.

State of the Art

When designing virtual worlds, to control access to objects Role-Based Access Control (RBAC) model [START_REF] Sandhu | The NIST model for role-based access control: towards a unified standard[END_REF], Attribute-Based Access Control (ABAC) [START_REF] Priebe | Supporting Attribute-based Access Control in Authentication and Authorization Infrastructures with Ontologies[END_REF], extensions of these models or their combinations may be applied. Although they are useful in the virtual worlds domain as far as roles, users and their credentials are concerned, they do not solve the problem of privilege granting in highly dynamic virtual worlds.

Research on data privacy protection in virtual environments is derived from the output of either CAD or VR communities. The majority of research effort on advanced privileges modeling in virtual environments is based on the CAD achievements as there is a need in the industry for CAD systems providing data privacy protection while enabling safe collaboration. In [START_REF] Qiu | Role-based 3D visualisation for asynchronous PLM collaboration[END_REF] a role-depended access model to 3D environments is proposed. In this approach each design feature of an object is assigned to one of predefined access levels representing modes of detail reduction. The role is defined by selecting access level for each object. It protects object geometry only -protection does not concern interactions and behaviors. Users update objects independently, then objects are synchronized by the central system. Such asynchronous approach is justified in some CAD collaborative applications, but it does not meet virtual worlds practice. In [START_REF] Wang | Intellectual Property Protection in Collaborative Design through Lean Information Modeling and Sharing[END_REF] an access control model for distributed 3D collaborative engineering systems is proposed. In this model RBAC extension is used which consists of a partial data sharing mechanism and fine grained access control. Access granularity is supported on different levels: assembly, component, feature and surface, which form a hierarchy. Dynamic geometric and non-geometric constraints can be modeled, but inter-object interactions and their different semantics are not supported as an element of the privilege system. Only basic operations such as read, write and modify are used to form privileges. In [START_REF] Cera | Role-based viewing envelopes for information protection in collaborative modeling[END_REF] FACADE system is proposed, which is synchronous collaborative 3D virtual environment enabling selective sharing of 3D objects. FACADE authors classify their work as both dataand interaction-centric, however, interaction is regarded here only as inter-user design-time interaction and not inter-object dynamic behavior. There are crosshierarchy relations between objects called "need-to-know requirements" but their nature is static and they are explicitly defined by designers. This concept provides role-based views on modeled data with read/write privileges granularity. Read privilege is extended to a continuous scale of mesh resolutions, but since only geometry is considered, there is no support for a whole spectrum of semantic operations that could form privileges.

From among non-CAD-based approaches, the most distinguished are rule-based access control models developed for the multimedia domain as a whole. Such models have even been a subject of standardization as a part of MPEG-21 -Right Expression Language (REL) [START_REF] Wang | The mpeg-21 rights expression language and rights data dictionary[END_REF]. Unfortunately, Digital Item (DI) representation which lies under it is not expressive enough to support complex behavior-rich 3D objects. Other access control standards, such as Extensible Access Control Modeling Language (XACML) [START_REF]eXtensible Access Control Markup Language (XACML) Version 2.0[END_REF], are even more general in the multimedia context.

An interesting rule-based access control model has been developed for and implemented in the DEVA system [START_REF] Pettifer | A Collaborative Access Model for Shared Virtual Environments[END_REF]. In the DEVA approach, execution of a given operation is controlled by access rules expressed by a source code defined in so-called keys. However, both operations and keys have to be explicitly defined by users. There is no automatic induction of operation dependencies, so users are responsible for maintaining access rules consistency. In [START_REF] Pettifer | A Collaborative Access Model for Shared Virtual Environments[END_REF] there is no explanation of how the DEVA approach is integrated with standard access control or how privileges are represented.

A number of papers are devoted to methods of modeling virtual worlds not only as a set of geometrical objects, but also semantically [START_REF] Latoschik | Knowledge in the Loop: Semantics Representation for Multimodal Simulative Environments[END_REF][START_REF] Lugrin | Making sense of virtual environments: action representation, grounding and common sense[END_REF][START_REF] Pittarello | Semantic description of 3D environments: a proposal based on web standards[END_REF][START_REF] Gutierrez | Semantics-based representation of virtual environments[END_REF]. Such approaches enable application of algorithms automatically exploring the content of the virtual world, reusing objects in different contexts and taking advantage of domain knowledge stored in external ontologies. However, there has been no effort to integrate semantic virtual world models with user privileges control to protect data privacy. The next research field related with this paper is structured design of virtual worlds [START_REF] Walczak | Structured Design of Interactive VR Applications[END_REF]. It focuses on methods of building VR applications in which content is dynamically configured from high-level elements, thus it can be relatively easily created and modified by domain experts and common users. Nevertheless, those reusable elements lack integrated user privilege support as well.

VR-PR Approach

Concept of the VR-PR Approach

Interactive virtual worlds admit content dynamically generated by users. In such virtual worlds the structure of the data model evolves which entails specific requirements for the access control model. In standard access control models such as RBAC and its extensions, privileges are formed as a pair operationresource. However, in dynamic virtual worlds based on object oriented paradigm a question arises: how to build an access control model appropriate to a very large number of dynamic classes, objects and methods that is understandable and manageable for users? In such virtual worlds resources have to be objects, however, operations may be defined differently. If an operation is an object method, privileges are too dependent on the data model. When a method changes, or a new class is added, the operation set used to define privileges has to be changed accordingly. If an operation represents all the object's methods, i.e. privileges are defined with the object granularity, another problem arises: different methods of an object usually have diametrically different semantics and they call different methods (i.e. have different call graphs), so their range of penetration of the virtual world is different, which is not reflected by such privilege system. Moreover, it is also very dependent on data model changes. If an operation is a primitive, such as "read" or "write", privilege system is independent of data model changes, but it does not follow the evolution of the virtual world, so it is useless in case of dynamic virtual worlds that constantly evolve. If the set of operations is not fixed but is updated by human operators according to data model changes, the risk of inconsistencies grows drastically.

In the VR-PR approach, semantic operations are used. A semantic operation is a conceptual extension of the operation from the standard access control models. Similarly to a regular operation, it is used to define privileges in conjunction with objects. But the main innovation is its semantics that is automatically induced from the object-oriented data model, instead of being defined arbitrarily. In other words a semantic operation is a set of bindings to semantically similar object methods induced from method call graphs. Each semantic operation is assigned to a given type and it has its place in the semantic operations hierarchy. Semantic operations reflect all the method calls, i.e. all in-world interactions of the objects, which may be complex, diverse, and dynamic. A semantic operation set is generated in a way assuring that each method call is bound to at least one induced semantic operation. Semantic operations are intuitively understandable by virtual content authors, publishers, administrators or other users authorized to create new privileges or modify existing ones.

In the VR-PR approach the privileges are processed in two phases. The Semantic Operations Generation Phase (SOGP) follows the virtual world data model evolution by regenerating a semantic operation set on each change. It is performed by the induction process basing on the analysis of the similarity of virtual object's method call graphs, as well as on the analysis of relationships between elements of the data model (cf. Subsection 4.2). A set of available semantic operations is generated from potential method calls known at design-time (inter-object relationship: uses-a), and from the static class hierarchy and object set structure (relationships: is-a, instance-of, part-of). During the SOGP phase semantic operation type categorization and generalization hierarchies are built.

Semantic operations are induced by semantic unification of different methods. This means that methods with similar call graphs are logically bound to a common semantic operation in the privilege system, whereas in the virtual world they are still recognized as separate ones.

From the data security and privacy point of view, measuring the level of similarity of the methods by measuring the level of similarity of their call graphs is justified. A semantic operation which groups methods with similar call graphs describes well the range of the penetration of the virtual world by a set of calls. In the VR-PR approach, the allowed range of virtual world penetration by method calls is controlled by the privilege system. As a result, the privilege function of protecting objects is satisfactory fulfilled -the system is protected against non-authorized deep method calls in a dense net of variable behavioral dependencies.

The second phase of the approach is the Privilege Creation and Modification Phase (PCMP), which is described in Subsection 4.3. Semantic operations induced during the first phase are used to form privileges by assigning them to objects. This process is controlled by an access control mechanism which makes the process consistent with the data model.

The SOGP Phase

In the VR-PR approach semantic operation induction is based on static call graph -a graph whose nodes are methods and edges are all possible calls of other methods. A node represents a method in the context of a given object, which means that if a given class has many instances, then for each method of this class there are as many nodes as instances. The call graph is created from the source code of virtual world objects. Global and local call graphs are distinguished. The global call graph contains all the methods and all the potential calls of other methods included in the source code of all the objects composing a virtual world at a given moment. It is updated incrementally when the data model changes. A local call graph is developed for each method. It is a subgraph of the global call graph built with a given method as the starting point and containing all the methods that are called by these methods, and all their callees. Semantic operations have types assigned. The types reflect the way semantic operations have been induced. When a given semantic operation is based on the methods with identical local call graphs, its type is called fully-matching. When call graphs of two unified methods cover methods belonging to the same classes (but they are based on different objects sets), the semantic operation is called class-matching.

The first phase of the VR-PR approach is composed of the following five steps (Fig. 1):

1. Construct the global call graph.

This graph is a basic data structure for the process of automatic generation of semantic operations.

Induce semantic operations.

The induction of each semantic operation is preceded by local call graph pre-selection. Each semantic operation is generated by semantic unification of different methods, basing on the analysis the similarity of local call graphs of methods and on the analysis of the static class hierarchy and object set structure. Metadata descriptions of the software modules, classes, objects and methods are taken into account during semantic unification if they are available. 5. Build semantic operations hierarchy according to composability criterion. It is orthogonal both to the role hierarchy and to the class inheritance hierarchy.

Potentially, semantic unification can be performed on two methods which are: different methods of different classes (but having similar calls); the same method, but in different object context (parameterized or using non-static field values); different methods of the same class. The aforementioned cases are distinguished during the selection of methods to be unified, as well as during call similarity analysis. Metadata descriptions of the software modules, classes, objects and methods taken into account during semantic unifications are useful in excluding semantically incoherent unifications, as well as in providing semantic labeling for the semantic operations.

The PCMP Phase

In the PCMP phase of the VR-PR approach the induced semantic operations are used to create privileges by assigning semantic operations to objects and binding so created privileges to roles (Fig. 2). Whether a given semantic operation may be assigned to a given object or not, depends on the privilege validation mechanism. Privilege validation can work in two modes: strict privileges and potential privileges. In the strict privileges mode a privilege may be created only if a given semantic operation has been induced from the requested object. In the potential privileges mode a given semantic operation can be assigned to an object even if the operation has not been induced from any of the object's methods. Such privileges are used when it can be anticipated that taking into account data model dynamism some objects will gain new competences. However, at the moment of the creation of such privileges they do not make any new method calls allowed, because those methods are as yet inexistent.

Since all the calls which are triggered by a given operation, including all the call dependencies (represented by a call graph), are known before each iteration of the privilege creation phase, during privilege assignment this knowledge can influence final decision whether a given privilege can be assigned or not. Thus, after privilege assignment, during run-time it is guaranteed that no access error will arise related to the lack of privileges to any of dependent methods called. This follows from the fact that each semantic operation stores all the bindings to the methods which were the base of its induction.

Discussion

The SOGP and PCMP phases described in Section 4 are following each other at runtime. Creating privileges is not a static task performed only during the virtual world creation, but a dynamic process following virtual world evolution. Users, roles and virtual world data model naturally evolve, while access control model core structures as semantic operations hierarchy remains persistent. In earlier approaches the operation set was static, though operations allowed on resources were defined with different semantics and complexity, i.e. read/ write, or execute/ modify/ insert/ append, or activate/ play/ reorganize. In some cases the operation set could evolve via non-automated changes following data model modifications, which does not assure privileges consistency. In the VR-PR approach, dynamism of the virtual world is inherently taken into account. Defining privileges using automatically regenerated semantic-based operations makes the process of role creation and management consistent, because of semantic operation set internal consistency and consistency with currently used data model. In the VR-PR approach semantic operations layer introduces stability into the process of privilege management. It is updated on-change (i.e. when new objects or new interactions appear), but updates do not change the semantic operations set significantly -especially when semantic operations are induced hierarchically and form a tree structure. Thus, access to semantic operations provides a safe tool to a role manager or any user who is not a 3D modeling expert nor a programmer but who is eligible to create or modify a privilege.

The VR-PR approach makes it possible to avoid unwanted frequent redefining and proliferation of roles. It may happen when privilege changes are not driven by business processes (e.g. a virtual world user gains new duties), but are forced by low level data model activity modification (e.g. when competences of the object to which privileges have been already granted are changed). The advantage of the VR-PR approach is that in this approach semantic operations can be regenerated without modifying the privileges assigned, as well as without role-privilege and user-role assignment modifications.

As an additional benefit, descriptive possibilities of semantic operations can be used in the role-mining process which is performed for security auditing purposes. In the VR-PR approach each semantic operation forming privilege assigned to a role expresses meaningful information about privilege semantics with an explicit representation. Semantic operations used in privileges can be treated as metadata unambiguously describing the role to which those privileges have been assigned. Having such metadata, role-mining process is much more straightforward.

Generally, in object-oriented virtual worlds applications during their lifetime there is a drift towards decreasing the size of the methods and increasing the number of calls. Along with increasing the number of calls, inter-object dependencies become more complex. Thus, a need for automatic analysis for security purposes becomes critical. This is yet another motivation for applying the VR-PR approach to the objectoriented virtual worlds.

Conclusions

In the VR-PR approach presented in this paper to provide data security and privacy a security mechanism is proposed based on the concept of semantic operations. They are derived at run-time from the virtual world's current data model and are applicable to access a control model as a part of a privilege. Semantic consistency of the security policies composed of privileges using semantic operations is forced by the two-phase regeneration and validation mechanism. On the other hand, this challenging functionality does not preclude expressing user rights in a precise, accurate, and flexible way.

The VR-PR approach bridges the semantic gap between abstract roles, both business roles and IT roles of virtual world users, and low-level operations executed on virtual world objects. Development of an abstract layer of semantic operations reduces the risk of inconsistent privilege modifications. It does not violate the RBAC access control model nor the object-oriented data model -it constitutes a middle layer placed between these two models developed for different purposes and it is designed with respect to 3D virtual worlds specificity.

3 .

 3 Assign types to semantic operations.

4 .

 4 Store bindings between each semantic operation and a set of methods which have been the base of its induction for further use during the PCMP phase.

Fig. 1 .

 1 Fig. 1. SOGP: semantic operations generation.

Fig. 2 .

 2 Fig. 2. PCMP: privilege creation/modification.