Hao Jiang
email: hao.jiang@imt-atlantique.fr

Ahmed Bouabdallah
email: ahmed.bouabdallah@imt-atlantique.fr

JACPoL: A Simple but Expressive JSON-based Access Control Policy Language

Keywords: real-time access control, lightweight policy language, JSON, fast policy evaluation

Along with the rapid development of ICT technologies, new areas like Industry 4.0, IoT and 5G have emerged and brought out the need for protecting shared resources and services under time-critical and energy-constrained scenarios with real-time policy-based access control. The process of policy evaluation under these circumstances must be executed within an unobservable delay and strictly comply with security objectives. To achieve this, the policy language needs to be very expressive but lightweight and efficient. Many existing implementations are using XML (Extensible Markup Language) to encode policies, which is verbose, inefficient to parse, and not readable by humans. On the contrary, JSON (JavaScript Object Notation) is a lightweight, text-based and languageindependent data-interchange format that is simple for humans to read and write and easy for machines to parse and generate. Several attempts have emerged to convert existing XML policies and requests into JSON, however, there are very few policy specification proposals that are based on JSON with well-defined syntax and semantics. This paper investigates these challenges, and identifies a set of key requirements for a policy language to optimize the policy evaluation performance. According to these performance requirements, we introduce JACPoL, a descriptive, scalable and expressive policy language in JSON. JACPoL by design provides a flexible and fine-grained ABAC (Attribute-based Access Control), and meanwhile it can be easily tailored to express a broad range of other access control models. This paper systematically illustrates the design and implementation of JACPoL and evaluates it in comparison with other existing policy languages. The result shows that JACPoL can be as expressive as existing ones but more simple, scalable and efficient.

Introduction

Access control is an important security mechanism involving user specified policies to determine the actions that a principal can perform on resources. Typically, the access requests are intercepted and analyzed by a PEP (Policy Enforcement Point), which then transfers the request details to a PDP (Policy Decision Point) for evaluation and authorization decision [START_REF] Yavatkar | A Framework for Policy-based Admission Control[END_REF]. In most implementations, the stateless nature of PEP enables its ease of scale. However, the PDP has to consult the right policy set and apply the rules therein to reach a decision for each request and thus is often the performance bottleneck of policy-based access control systems. Therefore, a policy language determining how policies are expressed and evaluated is important and has a direct influence on the performance of the PDP.

Especially, in nowadays, protecting private resources in real-time has evolved into a rigid demand in domains such as home automation, smart cities, health care services and intelligent transportation systems, etc., where the environments are characterized by heterogeneous, distributed computing systems exchanging enormous volumes of time-critical data with varying levels of access control in a dynamic network. An access control policy language for these environments needs to be very well-structured, expressive but lightweight and easily extensible [START_REF] Borders | CPOL: High-performance policy evaluation[END_REF].

In this paper, we investigate the relationship between the performance of the PDP, the language that is used to encode the policies and the access requests that it decides upon, and identify a set of key requirements for a policy language to guarantee the performance of the PDP. We argue that JSON would be more efficient and suitable than other alternatives (XML, etc.) as a policy data format in critical environments. According to these observations, we proposed a simple but expressive access control policy language (JACPoL) based on JSON. A PoC (Proof of Concept) has been conducted through the implementation of JACPoL in a policy engine operated in reTHINK testbed [START_REF]Deliverable D6.1: Testbed Specification[END_REF]. At last we carefully positioned JACPoL in comparison with existing policy languages.

The main contribution of this work is therefore the definition of JACPoL, which utilizes JSON to encode a novel access control policy specification language with well-defined syntax and semantics. We identify key requirements and technical trends for future policy languages. We incidentally propose the new notion of Implicit Logic Operators (ILO), which can greatly reduce the size and complexity of a policy set while providing fine-grained access control. We also elaborate on the applicability of JACPoL on ABAC model, RBAC model and their combinations or their by-products. Last but not least, our implementation leads to a novel and performant policy engine adopting the PDP/PEP architecture [START_REF] Yavatkar | A Framework for Policy-based Admission Control[END_REF] and JACPoL policy language based on Node.js1 and Redis2 .

The remainder of this paper is structured as follows. In Section 2, we refine our problematic by delimiting precisely its perimeter. In Section 3 we illustrate in depth with representative policy examples the design of our policy language in terms of the constructs, semantics and other important features like Implicit Logic Operators, combining algorithms and implementation. Section 4 further evaluates JACPoL and compares it with other existing access control policy specification languages. The ABAC-native nature of JACPoL is detailed in section 5 along with a comprehensive discussion on other possible application of JACPoL to ARBAC (Attribute-centric RBAC) and RABAC (Role-centric ABAC) security models. In Section 6 we summarize our work and discuss future research directions.

Problem Statement

In the past decades, a lot of policy languages have been proposed for the specification of access control policies using XML, such as EPAL [START_REF] Ashley | Enterprise privacy authorization language (EPAL)[END_REF], X-GTRBAC [START_REF] Bhatti | X-GTRBAC: an XML-based policy specification framework and architecture for enterprise-wide access control[END_REF] and the standardized XACML [START_REF]eXtensible access control markup language (XACML) Version 3.0." Oasis Standard[END_REF]. Nevertheless, it is generally acknowledged that XACML suffers from providing poorly defined and counterintuitive semantics [START_REF] Crampton | PTaCL: A language for attribute-based access control in open systems[END_REF], which makes it not good in simplicity and flexibility. On the other hand, XML performs well in expressiveness and adaptability but sacrifices its efficiency and scalability, compared to which JSON is considered to be more well-proportioned with respect to these requirements, and even simpler, easier, more efficient and thus favored by more and more nowadays' policy designers [10][11][12] [START_REF]JSON vs XML[END_REF].

To address the aforementioned inefficiency issues of the XML format, the XACML Technical Committee recently designed the JSON profile [START_REF] Brossard | JSON Profile of XACML 3.0 Version 1.0[END_REF] to be used in the exchange of XACML request and response messages between the PEP and PDP. However, the profile does not define the specification of XACML policies, which means, after the PDP parses the JSON-formatted XACML requests, it still needs to evaluate the parsed attributes with respect to the policies expressed in XML. Leigh Griffin and his colleagues [START_REF] Griffin | On the performance of access control policy evaluation[END_REF] have proposed JSONPL, a policy vocabulary encoded in JSON that semantically was identical to the original XML policy but stripped away the redundant meta data and cleaned up the array translation process. Their performance experiments showed that JSON could provide very similar expressiveness as XML but with much less verbosity. On the other hand, as much as we understand, JSONPL is merely aimed at implementing XACML policies in JSON and thus lacks its own formal schema and full specification as a policy specification language [START_REF] Steven | FAME project of Waterford Institute of Technology[END_REF].

Major service providers such as Amazon Web Services (AWS) [START_REF]AWS Identity and Access Management(IAM) User Guide[END_REF] have a tendency to implement their own security languages in JSON, but such kind of approaches are normally for proprietary usage thus provide only self-sufficient features and support limited use cases, which are not suitable to be a common policy language. To the best of our knowledge, there are very few proposals that combine a rich set of language features with well-defined syntax and semantics, and such kind of access control policy language based on JSON has not even been attempted before and as such JACPoL can be considered to be an original and innovative contribution.

JACPoL Detailed Design

This section presents JACPoL in depth. We first recall the foundations of JACPoL, and then introduce its structures with an overview of how an access request is evaluated with respect to JACPoL policies. After that, we describe the syntax and semantics in detail along with policy examples.

Fundamental Design Choices

The goal is to design a simple but expressive access control policy language. To achieve this, we beforehand introduce the important design decisions for JACPoL as below.

First, JACPoL is JSON-formatted [START_REF]ECMA-404 The JSON Data Interchange Standard[END_REF]. Second, JACPoL is attribute-based by design but meanwhile supports RBAC [START_REF] Ferraiolo | Role-based Access Controls[END_REF]. When integrating RBAC, user roles are considered as an attribute (AR-BAC) [26], or attributes are used to constrain user permissions (RABAC) [START_REF] Jin | RABAC: role-centric attribute-based access control[END_REF], which obtains the advantages of RBAC while maintaining ABAC's flexibility and expressiveness.

Third, JACPoL adopts hierarchically nested structures similar to XACML. The layered architecture as shown in Fig. 1 not only enables scalable and finegrained access control, but also eases the work of policy definition and management for policy designers.

Forth, JACPoL supports Implicit Logic Operators which make use of JSON built-in data structures (Object and Array) to implicitly denote logic operations. This allows a policy designer to express complex operations without explicitly using logical operators, and makes JACPoL policies greatly reduced in size and easier to read and write by humans.

Fifth, JACPoL supports Obligations to offer a rich set of security and network management features.

Policy Structure

JACPoL uses hierarchical structures very similar to the XACML standard [START_REF] David | Extensible Access Control Markup Language (XACML) and Next Generation Access Control (NGAC)[END_REF]. As shown in Fig. 1, JACPoL policies are structured as Policy Sets that consist of one or more child policy sets or policies, and a Policy is composed of a set of Rules.

Because not all Rules, Policies, or Policy Sets are relevant to a given request, JACPoL includes the notion of a Target. A Target determines whether a Rule/Policy/Policy Set is applicable to a request by setting constraints on attributes using simple Boolean expressions. A Policy Set is said to be Applicable if the access request satisfies the Target, and if so, then its child Policies are evaluated and the results returned by those child policies are combined using the policy-combining algorithm; otherwise, the Policy Set is skipped without further examining its child policies and returns a Not Applicable decision. Likewise, the Target of a Policy or a Rule has similar semantics.

The Rule is the fundamental unit that is evaluated eventually and can generate a conclusive decision (Permit or Deny specified in its Effect field). The Condition field in a rule is a simple or complex Boolean expression that refines the applicability of the rule beyond the predicates specified by its target, and is optional. If a request satisfies both the Target and Condition of a rule, then the rule is applicable to the request and its Effect is returned as its decision; otherwise, Not Applicable is returned.

For each Rule, Policy, or Policy Set, an id field is used to be uniquely identified, and an Obligation field is used to specify the operations which should be performed (typically by a PEP) before or after granting or denying an access request, while a Priority is specified for conflict resolution between different Rules, Policies, or Policy Sets.

Syntax and Conventions

JACPoL uses JSON syntax to construct and validate its policies. A policy must follow correct JSON syntax to take effect. In this subsection, we do not provide a complete description of what constitutes valid JSON [START_REF]ECMA-404 The JSON Data Interchange Standard[END_REF]. However, below is a list of fundamental characteristics of JSON:

• JSON is built on two universal data structures: object and array.

• An object is denoted by braces ({}) that can hold multiple name-value pairs. For each name-value pair, a colon (:) is used to separate the name and the value, whilst multiple name-value pairs are separated by comma (,) as in the following example: {"id": 1, "effect": "permit"}. • An array is denoted by brackets ([ ]) that can hold multiple values separated by commas (,) as in the following example: ["Monday", "Friday", "Sunday"]. • A value can be a string in double quotes, or a number, or a Boolean value (true or false), or null, or an object or an array. • Whitespace can be inserted between any pair of JSON tokens ({ } [ ] " , :).

In the subsequent subsections, we will elaborate on the syntax and semantics for each policy element. To illustrate better, the following conventions are used:

• The following characters are special characters used in the description of the grammar and are not included in the policy syntax: < > ... ( ) |. • If an element allows multiple values, it is indicated using the repeated values, commas, and an ellipsis (...). Example: [<rule_block>, <rule_block>, ...]. • A question mark (?) following an element indicates that element is optional.

Example: {"condition"?: <boolean_expression>}. • A vertical line (|) between elements indicates alternatives. Parentheses define the scope of the alternatives. The default value is underlined if the field is optional. Example: {"algorithm"?: ("permitOverrides" | "firstApplicable")}. • Elements that must be literal strings are enclosed in double quotation marks.

Policy Sets, Policies and Rules

This subsection describes the grammar of the Policy Set, the Policy and the Rule. In JACPoL, a policy set, a policy, or a rule always starts and ends with a brace, which denotes a policy set block, a policy block, or a rule block.

Policy set block. Fig. 2 describes the grammar of the policy set block, which is composed of six name-value pairs that exactly correspond to the six elements of a policy set. As shown in the figure, the "id" field is a string which can be either numeric or descriptive to uniquely identify a policy set. The "target" specifies a Boolean expression indicating the resources, subjects, actions or the environment attributes to which the policy set is applied. The "policies" stores a list of policy blocks with each one corresponding to a policy. The "algorithm" field specifies the name of a decision-combining algorithm to compute the final decision according to the results returned by its child policies. The "obligation" specifies actions to take in case a particular conclusive decision (Permit or Deny) is reached. The "priority" provides a numeric value indicating the weight of the policy set when its decision conflicts with other policy sets under the highestPriority algorithm.

{

"id": "target"?: "policies": "algorithm"?: "obligation"?: "priority"?: <string>, <boolean_expression>, [<policy_block>, <policy_block>, ...], ( "permitOverrides"|"denyOverrides"|"firstApplicable"|"highestPriority"), <obligation_statement>, <number> } Fig. 2: Grammar of the policy set block Note that elements like target, algorithm, obligation and priority are optional and, if omitted, the predefined default values would be taken (e.g., target: true, algorithm: firstApplicable, obligation: null, priority: 0.5).

Policy block. As shown in Fig. 3, a policy block contains an id, a target, an algorithm, an obligation and a priority similar to a policy set. The difference is, it has a "rules" list that holds one or more rule blocks instead of policy blocks.

{

"id": <string>, "target"?: <boolean_expression>, "rules":

[<rule_block>, <rule_block>, ...], "algorithm"?: ("permitOverrides"|"denyOverrides"|"firstApplicable"|"highestPriority"), "obligation"?: <obligation_statement>, "priority"?: <number> } Fig. 3: Grammar of the policy block Rule block. Fig. 4 describes the grammar of the rule block. Unlike a policy set block or a policy block, a rule block does not contain any leaf nodes like child policies or child rules and thus a decision-combining algorithm field is not needed either. Instead, it possesses a "condition" element that specifies the condition for applying the rule, and an "effect" element that, if the rule is applied, would be the returned decision of the rule as either Permit or Deny. In comparison to a target, a condition is typically more complex and often includes functions (e.g., "greater-than") for the comparison of attribute values, and logic operations (e.g., "and", "or") for the combination of multiple conditions. If either the target or the condition is not satisfied, a Not Applicable would be taken as the result instead of the specified effect. Note that the Condition is by default true if omitted.

{

"id": "target"?: "effect": "condition"?: "obligation"?: "priority"?: <string>, <boolean_expression>, ("permit"|"deny"), <boolean_expression>, <obligation_statement>, <number> } Fig. 4: Grammar of the rule block

Targets and Conditions

As aforementioned, a Target or a Condition is a Boolean expression specifying constraints on attributes such as the subject, the resource, the environment, and the action of requests. The Boolean expression of a Target is often simple and very likely to be just a test of string equality, but that of a condition can be sometimes complex with constraints on multiple attributes (attribute conditions).

Attribute Condition is a simple Boolean expression that consists of a keyvalue pair as shown below:

{"<attribute_expression>": <condition_expression>}

The key is an attribute expression in string format that specifies an attribute or a particular computation between a set of attributes; the value is a condition expression, which is a JSON block composed of one or more operator-parameter pairs specifying specifically the requirements that the attribute expression needs to meet. The simplest format of an attribute condition is to verify the equality /inequality between the attribute (e.g., time) and the parameter (e.g., 10:00:00) using comparative operators (e.g., greater-than, less-than, equal-to, etc.):

{"<attribute>": {"<comparative_operator>": <parameter>}} However, there are also cases where we have multiple constraints (operatorparameter pairs) on the same attribute, connected by logical relations like AND, OR, NOT, which are respectively denoted by the keywords allOf , anyOf and not.

Logical Operators. JACPoL uses logical operators in a form of constructing key-value pairs. The logical operator is the key and, depending on the number of arguments, allOf and anyOf operators are to be followed by an array ([ ]) of multiple constraints, while the not operator is to be followed by an object ({ }). An allOf operation would be evaluated to true only if all subsequently included constraints are evaluated to true, but an anyOf operation would be true as long as there is at least one of the constraints which is true. An not operation would be true if the followed constraint is evaluated to false. Logical operators can be nested to construct logical relations such as not any of, not all of. For example, an attribute condition containing multiple constraints with nested logical operators as below:

{"sumOf x y": {"not": {"anyOf": [ {"between": "j k"}, {"equals": "z"}]}}} in which the string "sumOf x y" is an attribute expression. The keyword sumOf defines a function to compute the sum of attributes x and y, which is to be evaluated by the subsequent condition expression. Please note that a parameter like j, k or z can also possibly be another attribute instead of an explicit value.

In addition, logical operators can also be used to combine multiple attribute conditions in order to express complex constraints on more than one attribute easily and flexibly. As an example, the condition below expresses constraints on two attributes and would be evaluated to true only when both (allOf the two) constraints are met:

{"allOf": [<attribute_condition>, <attribute_condition>]}
Less is More: Implicit Logical Operators. A complex condition might contain many logical operators which make the policy wordy and hard to read. To overcome this, we make use of JSON's built-in data structures, object and array, and define following implicit logical operators as alternatives to allOf and anyOf :

• An object is implicitly an allOf operator which would be evaluated to true only if all the included key-value pairs are evaluated to true. • An array is implicitly an anyOf operator which would be evaluated to true as long as at least one of its elements is evaluated to true.

For example, below is a condition statement using implicit logical operators to verify if it is working hour.

{ "time":{"between": ["09:00 12:00", "14:00 18:00"]}, "weekday": {"not": {"equals": ["saturday", "sunday"]}} } As a comparison, below is for the same verification with explicit logical operators.

{

"allOf": [{ "time": {"anyOf": [ {"between": "09:00 12:00"}, {"between": "13:00 18:00"}]} },{ "weekday": {"not": {"anyOf": [ {"equals": "saturday"}, {"equals": "sunday"}]}}}] } Apparently, implicit operators save a lot size and make policies more readable, which has later turned out to be very useful in our policy engine implementation.

Combining Algorithms

In JACPoL, policies or rules may conflict and produce totally different decisions for the same request. JACPoL resolves this by adopting four kinds of decisioncombining algorithms: Permit-Overrides, Deny-Overrides, First-Applicable, and Highest-Priority. Each algorithm represents a different way for combining multiple local decisions into a single global decision: Please note that for all of these combining algorithms, Not Applicable is returned if not any of the child rules (or policies) is applicable. Hence, the set of possible decisions is 3-valued.

Obligations

JACPoL includes the notion of obligation. An Obligation optionally specified in a Rule, a Policy or a PolicySet is an operation that should be performed by the PEP in conjunction with the enforcement of an authorization decision. It can be triggered on either Permit or Deny. We employ the format as below to express obligations in JACPoL:

{"<decision>": {"<operation>": [<parameter>, <parameter>, ...]}} For example, the obligation below is for the access control of a document.

{ "permit": {"watermark": ["DRAFT"]}, "deny": { "feedback": ["ACCESS DENIED"], "notify": ["admin@gmail.com", "hr@gmail.com"] } } It specifies that if an access request is denied, the user would be informed with an access denied message and the administrator and HR would also be notified; if an access request is approved, watermark the document "DRAFT" before delivery. It worths to be mentioned that the referred obligations have an eminently locale nature in the sense that their execution is the exclusive prerogative of the PEP which can possibly rely on the information available in the PIP [START_REF] Yavatkar | A Framework for Policy-based Admission Control[END_REF]. More general and distributed obligations deserve a dedicated investigation.

Implementation

We implemented JACPoL in a Javascript/Node.js/Redis based policy engine [START_REF]reTHINK CSP Policy Engine[END_REF] which is avaiable on Github. As shown in Fig. 5, the policy engine employs the classical PDP/PEP architecture [START_REF] Yavatkar | A Framework for Policy-based Admission Control[END_REF]. The PDP retrieves policies from the PRP (Policy Retrieval Point), and evaluates authorization requests from the PEP by examining the finite relevant attributes against the policies. If more attributes are required to reach a decision, the PDP will request the PIP(Policy Information Point) as an external information source. The latter may also be requested in the case of obligations. The non-blocking nature of Node.js allows the system to provide an efficient and scalable access control, and a Redis server was employed to enable flexible and high-performance data persistence and caching. In order to validate its functionality, we have deployed this policy engine on a messaging node of reTHINK project [START_REF][END_REF]. This reTHINK policy engine [START_REF]reTHINK CSP Policy Engine[END_REF] adopted the ABAC model and customized the vocabulary of JACPoL for the requirements of reTHINK framework. With JACPoL based lightweight policies, Node.js based non-blocking I/O, and Redis based fast caching, it provided a highly performant access control according to various tailored attributes in an expressive and flexible way [START_REF]reTHINK Deliverable 6.4[END_REF]. In reTHINK, in addition to comparative operators greaterThan, lessThan, equal-sTo, JACPoL is extended to support more operators as listed in Fig. 6 with a rule example:

Other Operators

x in [a, b, c] x between "a b"

x contains "c"

x like "/resources/*" x exists { "id": "dpt-01-ac-01", "target": {"type": {"equalsTo": "create"}}, "condition": { "weekday": {"in": ["saturday", "sunday"]}, "time": {"between": "18:00 07:00"}, "url": {"like": "*/core/*/contactlist"} }, "effect": "deny" } Fig. 6: Other supported operators (left) and a rule example (right)

Comparative Analysis

This section evaluates JACPoL with a comprehensive comparison to other preand post-XACML policy languages, which respectively are JSONPL [START_REF] Steven | FAME project of Waterford Institute of Technology[END_REF], AWS IAM [START_REF]AWS Identity and Access Management(IAM) User Guide[END_REF], XACML [START_REF]eXtensible access control markup language (XACML) Version 3.0." Oasis Standard[END_REF], Ponder [START_REF] Damianou | The ponder policy specification language[END_REF], Rei [START_REF] Kagal | A policy language for a pervasive computing environment[END_REF], XACL [START_REF] Hada | XML Access Control Language: provisional authorization for XML documents[END_REF], KAoS [START_REF] Uszok | Kaos: A policy and domain services framework for grid computing and semantic web services[END_REF], EPAL [START_REF] Ashley | Enterprise privacy authorization language (EPAL)[END_REF], and ASL [START_REF] Jajodia | A logical language for expressing authorizations[END_REF], followed by a simple quantitative comparison with XACML in terms of processing delay. To begin with, we have identified the following requirements for an access control policy language to meet the increasing needs of security management for today's ICT systems:

• Expressiveness to support wide range of policy needs and be able to specify various complex, advanced policies that a policy maker intend to express [START_REF] He | Design of policy language expression in SIoT[END_REF]. • Extensibility to cater for new features or concepts of policy in the future [START_REF] Damianou | The ponder policy specification language[END_REF].

• Simplicity to ease the policy definition and management tasks for the policy makers with different levels of expertise. This includes both conciseness and readability to avoid long learning curve and complex training. • Efficiency to ensure the speed for machines to parse the policies defined by humans. This can be affected by policy structure, syntax, and data format. • Scalability to ensure the performance as the network grows in size and complexity. This is important especially in large-scale or multi-domain networks. • Adaptability to be compatible with any access control tasks derived from an ICT system. Any user could directly tailor the enforcement code and related tool set provided by the policy language to their authorization systems.

Table 1 shows the complete evaluation of these policy languages. In the table, ' ' and ' ' respectively indicate 'support' and 'strongly support', while '+', '++', '+++' and '++++' mean 'poor', 'good', 'very good' and 'excellent'. The comparison mainly focuses on their design and implementation choices regarding authorization, obligation, index, syntax and scheme, and their performance with respect to the six previously defined criteria. Among these features, index refers to whether there exists a special item for policy engine to retrieve the required policies more efficiently. Like many other languages, JACPoL provides support for authorization and obligation capabilities as previously introduced. In addition, it includes a concept of Target within each Policy Set, Policy and Rule to allow efficient policy index. In terms of expressiveness, JACPoL, Rei and KAoS extensively support the specification of constraints, which can be set on numerous attributes in a flexible expression [START_REF] Neuhaus | Survey on healthcare IT systems: standards, regulations and security[END_REF].

On the other hand, compared to XML-based languages, JSON-based JACPoL is simpler and more efficient, but meanwhile, we have to admit that JSON is less sophisticated than XML, which accordingly may make JACPoL less extensible. JACPoL is scalable and the reasons are twofold: first, its efficient performance in policy index and evaluation allows it to deal with complex policies under a large-scale network environment; second, its concise semantics and lightweight data representation make it easily replicable and transferable for distributed systems. As for adaptability, compared to other languages, the application specific nature of AWS IAM makes it relatively harder to be adapted to other systems.

A more comprehensive, quantitative and systematic performance evaluation (in terms of speed, memory consumption, etc.) of JACPoL is in progress at the moment and would be detailed in a future paper [START_REF] Jiang | Towards A Json-based Fast Policy Evaluation Framework[END_REF]. However, we present the results of a preliminary test as below in Fig. 7 and Fig. 8 which hopefully can provide some insights on the outperformance of JACPoL over XACML. We assessed respectively how both languages' policy processing time increases with the growth of nesting layers (policy depth) and with the growth of sibling rules (policy scale). First we used the two languages to express the same policy set with 400 recursively nesting child policies, and recorded the delay when each child policy was evaluated until the deepest one was reached. The result is depicted in Fig. 7. Then we did the same with a policy set containing 400 sibling child policies and got the result in Fig. 8. Each experiment was repeated 1000 times conducted using Python on a Windows 10 PC with 16G memory and a 2.6GHz Intel core i7-6700HQ processor. From this simple test we can preliminarily see that JACPoL is more efficient and scalable and processed with less latency than XACML thanks to its JSON syntax and well-defined semantics.

RBAC vs ABAC

In policy-based access control systems, a request for access to protected resources is evaluated with respect to a policy that defines which requests are authorized. The policy itself conforms to a security model upstream chosen by the system security administrator because it elegantly copes with the constraints associated with the targeted information system. In the RBAC model, roles are pre-defined and permission sets for resources are pre-assigned to roles. Users are then granted one or more roles in order to receive access to resources [START_REF]Best practices in enterprise authorization: The RBAC/ABAC hybrid approach[END_REF]. ABAC, on the other hand, relies on user attributes for access decisions. These include: subject attributes, which are attributes concerning the actor being evaluated; object attributes, which are attributes of the resource being affected; action attributes, which are attributes about the operation being executed; and environment attributes, which provides other contextual information such as time of the day, etc. [START_REF] Hu | Guide to attribute based access control (ABAC) definition and considerations[END_REF]. Generally speaking, RBAC is simple, static and auditable, but is not expressive nor context-aware, while ABAC, by contrast, provides fine-grained, flexible and dynamic access control in realtime but is complex and unauditable.

Combining these two models judiciously to integrate their advantages thus becomes an essential work in recent research [START_REF]Best practices in enterprise authorization: The RBAC/ABAC hybrid approach[END_REF] [17] [27] [START_REF] Kuhn | Adding attributes to role-based access control[END_REF].

Attribute-centric RBAC Application

JACPoL can be implemented to express permission specification policies (PSP) in an attribute-centric RBAC model. For example, Fig. 9 defines a policy set with each policy specifying permissions that associated to the targeted role. When evaluating a request, the PDP first retrieves all the roles (e.g., from the PIP) that are pre-assigned to the requester, and then examines the permission policies that are associated to these roles to reach a decision. Unlike other traditional statically defined RBAC permissions, JACPoL allows its permissions to be expressed in a quite dynamic and flexible way similar to ABAC. Please note that the role attribute is suggested to be placed as the target for the topmost level of policies in order to allow an easier view of user permissions as shown in Fig. 9. Fig. 9: An example ARBAC permission specification policy and its structure tree

Role-centric ABAC Application

JACPoL can also be used to implement a language for permission filtering policies (PFP) in a role-centric ABAC model [START_REF] Jin | RABAC: role-centric attribute-based access control[END_REF]. Similar to the ABAC model in Fig. 5, but in addition to external attributes, the PDP also relies on the PIP to get role permission sets which, as defined by NIST RBAC model, specify the maximum set of available permissions that users can have. These permission sets can be further constrained by the filtering policies based on JACPoL, as shown in Fig. 10. Note that this time the target of each PFP maps each object to a subset of the filtering rules. At the same time, the target and condition of each rule determine whether or not the rule is applicable. The applicable filtering rules are invoked one by one against each of the permissions in the permission set. If any of the rules return FALSE, the permission is then blocked and removed from the available permission set for the current session. At the end of this process, the final available permission set available to users therefore will be the intersection of P and R, where P is the set of permissions assigned to the subject's active roles and R is the set of permissions specified by the applicable JACPoL rules [START_REF] Kuhn | Adding attributes to role-based access control[END_REF].

Conclusion

Traditionally, performance has not been a major focus in the design of access control systems. Applications are emerging, however, that require policies to be evaluated with a very low latency and high throughput. Under this background, we designed and implemented JACPoL, a fast JSON-based, attribute-centric and light-weight access control policy language. JACPoL provides a good solution for policy specification and evaluation in such applications with low processing delay. We evaluated our policy language with respect to a set of representative criteria in comparison with other existing policy languages. The evaluation showed that JACPoL can be as expressive as XACML but more simple, scalable and efficient.

On the other hand, JACPoL leaves room for future improvements in many areas. For example, obligation capabilities can be further enhanced and delegation support can be formally introduced. By priority, we are currently conducting a more comprehensive experimental performance evaluation with extensive policy sets for various real-world use cases, in which a more systematic and quantitative evaluation criteria (e.g., speed, memory usage, etc.) would be considered.

Fig. 1 :

 1 Fig. 1: JACPoL's hierarchical nested structure

Fig. 5 :

 5 Fig. 5: Policy engine architecture

Fig. 7 :Fig. 8 :

 78 Fig. 7: Effect of policy depth

Fig. 10 :

 10 Fig.10: An example RABAC permission filtering policy and its structure tree

•

  Permit-Overrides returns Permit if any decision evaluates to Permit; and returns Deny if all decisions evaluate to Deny. • Deny-Overrides returns Deny if any decision evaluates to Deny; returns Permit if all decisions evaluate to Permit. • First-Applicable returns the first decision that evaluates to either of Permit or Deny. This is very useful to shortcut policy evaluation. • Highest-Priority returns the highest priority decision that evaluates to either of Permit or Deny. If there are multiple equally highest priority decisions that conflict, then deny-overrides algorithm would be applied among those highest priority decisions.

Table 1 :

 1 Evaluation and comparison between JACPoL and other policy languages

	Policy Languages Year Authorization Obligation Index	Syntax	Scheme Expressiveness Extensibility Simplicity Efficiency Scalability Adaptability
	JACPoL	2017	JSON-based ABAC	++++	++	+++	+++	+++	+++
	JSONPL	2012	JSON-based ABAC	++	++	+++	+++	+++	++
	AWS IAM	2010	JSON-based RBAC	++	++	+++	+++	++	+
	XACML	2003	XML-based ABAC	+++	+++	+	++	++	+++
	Rei	2003	Logic-based OBAC	++++	+++	+	++	+++	+++
	EPAL	2003	XML-based RBAC	+++	+++	+	++	++	+++
	Ponder	2001	Specific	RBAC	+++	+	++	++	+++	+++
	XACL	2000	XML-based RBAC	+	+	+	++	+	+
	KAoS	1997	OWL-based OBAC	++++	+++	+	++	+++	+++
	ASL	1997	Logic-based RBAC	+	+	+	++	+	++

nodejs.org

redis.io

Acknowledgement

This work has received funding from the European Union s Horizon 2020 research and innovation programme under the grant agreement No. 645342, project re-THINK. We gratefully acknowledge support from our colleagues in this project, Jamal Boulmal (Apizee), Jean-Michel Crom and Simon Becot (Orange Labs). This work would hardly be possible without their valuable suggestions and help.


Hugo Jantzi

Jean-Michel Carozza

J L Probst

Philippe Valette

Philippe Valette Geomorphological

Geomorphological adjustements of the middle Garonne River downstram of Toulouse (South-West, France) since the 1950s under the effect of in-stream gravel mining

published or not. The documents may come

I.S.RIVERS LYON 2018

Location map of the middle Garonne and the study reach (red dot) (IGN).

Background

 During the 20 th century, significant geomorphological adjustments are observed on the Garonne river leading to channel narrowing (-60 m) and incision (-1,7 m).  It occurred especially from the 1950s as a consequence of intensive human interventions, such as dam construction, channel works and mainly by in-stream gravel mining with 20 M.m -3 extracted in 20 years.  Nowadays the river presents a significant sediment deficit resulting in bedrock outcrops over 51% of the total channel surface.

Geomorphological adjustments of the middle

Objectives

 Identify the geomorphological changes occurring in the study reach under the effect of in-stream gravel mining during the 2 nd half of the 20 th century.  Quantify the riverbed degradation.

 Highlight the transition processes between alluvial channel and bedrock channel.

Methods

 Spatial analysis from aerial images:

 Topographic data analysis from cross profiles.

 Hydrological data analysis based on flood records.

Changes in channel morphology

Aerial images Georeferencing (1 st order polynomial)  This study highlights the role of in-stream mining as the dominant factor in channel degradation at the local scale.

 In-stream mining and lack of sediment connectivity resulted in an incision greater than 4 m and a high sediment deficit.

 Change of incision process from evacuation of alluvial cover by regressive erosion and gradual outcropping of the bedrock to erosion of this latter.

 Appearance of a knickpoint of more than 3 ha with 3 m difference in height.

In-stream mining

In-stream mining

In-stream mining

In-stream mining

1

  Garonne River downstream of Toulouse (South-West, France) since the 1950s under the effect of in-stream gravel mining Ajustements géomorphologiques de la moyenne Garonne en aval de Toulouse (sud-ouest, Université Jean Jaurès, GEODE UMR 5602 CNRS, Toulouse, France 2 Université de La Rochelle, LIENSS UMR 7266 CNRS, La Rochelle, France 3 Université Paul Sabatier, ECOLAB UMR 5245 CNRS/INPT-ENSAT, Toulouse, France * Corresponding author : hugo.jantzi@univ-tlse2.fr / +33 (0)5 61 50 36 26 Study site The study reach is located on the Garonne River, 10 km downstream of Toulouse at the town of Beauzelle.  Width: 130 m ; slope: 20% ; stream power: 400 W.m -2 .



  Significant narrowing and incision is recorded between 1960s and 1990s with a maximum intensity over 1970s corresponding to the period of in-stream mining: Between 1958-2010 channel morphology experiments drastic changes with 41% increase in outcrops and 10%-15% decrease in gravel and vegetated bars.



  In-stream gravel mining with 389 000 m 3 extracted over the 1970s according to archive sources. In response, the channel experiments: 1) bed channel load removal,  2) erosional regression estimated at ̴ 27 m.an -1 leading to a gas line rupture (1982) 300 m upstream of the extraction site. at low flow ̴ 45 m.s -1 (Smeag).


Katharina T Huber
email: k.huber@uea.ac.uk

Vincent Moulton
email: v.moulton@uea.ac.uk

Marie-France Sagot
email: marie-france.sagot@inria.fr

Blerina Sinaimeri
email: blerina.sinaimeri@inria.fr

Geometric medians in reconciliation spaces

Keywords: Reconciliation, Geometric median, Reconciliation space, Edit-distance, Median 2008 MSC: 54E35, 05C05, 05C85, 92B05

In evolutionary biology, it is common to study how various entities evolve together, for example, how parasites coevolve with their host, or genes with their species. Coevolution is commonly modelled by considering certain maps or reconciliations from one evolutionary tree P to another H, all of which induce the same map between the leaf-sets of P and H (corresponding to present-day associations). Recently, there has been much interest in studying spaces of reconciliations, which arise by defining some metric d on the set R(P, H, ) of all possible reconciliations between P and H.

In this paper, we study the following question: How do we compute a geometric median for a given subset of R(P, H, ) relative to d, i.e. an element med 2 R(P, H, ) such that

holds for all 2 R(P, H, )? For a model where so-called host-switches or transfers are not allowed, and for a commonly used metric d called the edit-distance, we show that although the cardinality of R(P, H, ) can be super-exponential, it is still possible to compute a geometric median for a set in R(P, H, ) in polynomial time. We expect that this result could be useful for computing a summary or consensus for a set of reconciliations (e.g. for a set of suboptimal reconciliations).

Introduction

In phylogenetics, the reconciliation problem involves trying to find a map that reconciles one leaflabelled evolutionary tree with another [START_REF] Page | Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas[END_REF]. It has important applications in areas such as ecology and genomics, and arises in various situations. For ex-ample, biologists are interested in understanding how parasite and host species [START_REF] Donati | Eucalypt: E cient tree reconciliation enumerator[END_REF], genes and species [START_REF] Doyon | Models, algorithms and programs for phylogeny reconciliation[END_REF], or species and habitats coevolve [START_REF] Rosen | Vicariant patterns and historical explanation in biogeography[END_REF] (in what follows we shall use terminology for host-parasite relationships to keep things concrete).

More formally, a phylogenetic tree T is a rooted, binary tree (i.e. every vertex of T that is not the root or a leaf has indegree 1 and outdegree 2), which has root vertex ⇢ T (with indegree 0 and outdegree 2). Given a host-parasite triple (P, H, ), that is, two phylogenetic trees P and H (the parasite and the host tree, respectively), whose leafsets represent present-day species, and a map : L(P ) ! L(H) (describing which parasite is currently on which host), a reconciliation map is a map : V (P ) ! V (H) which satisfies:

(i) The map restricted to the leaf-set of P is equal to .

(ii) If v is a vertex in the interior of P , then (v) is either strictly above or equal to (v 0 ), for any child v 0 of v.

We present an example of such a map in Figure 1.

Note that various definitions have been proposed for reconciliation maps (see e.g. [START_REF] Doyon | Models, algorithms and programs for phylogeny reconciliation[END_REF]). These model evolutionary processes including cospeciation (a host and parasite speciate together), duplication (a parasite speciates on a host), loss (a host speciates but not its parasite) and host-switches (e.g. a parasite switches to another host). In this paper, we are using the definition for a reconciliation map presented in [START_REF] Donati | Eucalypt: E cient tree reconciliation enumerator[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF], with the added assumption that we do not allow host-switches.

In general, several algorithms have been developed to compute optimal and suboptimal reconcili- ations for a pair of trees relative to some predefined cost-function (cf. e.g. [START_REF] Doyon | Models, algorithms and programs for phylogeny reconciliation[END_REF][START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF]). When host-switches are not allowed (as in this paper), collections of suboptimal reconciliations can contain thousands of elements [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF], and for more complex models (e.g.

where host-switches are permitted), this can be the case even for collections of optimal reconciliations [START_REF] Donati | Eucalypt: E cient tree reconciliation enumerator[END_REF]. It is thus quite natural to consider properties of the set of all possible reconciliations endowed with some metric which also permits their comparison.

These so-called reconciliation spaces are of growing importance in the literature [START_REF] Bansal | Reconciliations revisited: handling multiple optima when reconciling with dupli-cation, transfer, and loss[END_REF][START_REF] Chan | Exploring the space of gene/species reconciliations with transfers[END_REF][START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF][START_REF] Doyon | An e cient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework[END_REF][START_REF] Wu | Structural properties of the reconciliation space and their applications in enumerating nearly-optimal reconciliations between a gene tree and a species tree[END_REF] and permit quantitative analysis of the behavior of reconciliation maps.

In this paper, we are interested in the problem of computing geometric medians in reconciliation spaces. In general, for Y a finite set endowed with a metric D, and

Y 0 ✓ Y , an element y ⇤ 2 Y is a geometric median for Y 0 in Y if X y 0 2Y 0 D(y ⇤ , y 0 ) = min{ X y 0 2Y 0 D(y, y 0 ) : y 2 Y }.
Such elements are useful as they can act as an element which summarizes or forms a consensus for the set Y 0 . Within computational biology, geometric medians (and the closely related concept of centroids) have been used in phylogenetics to form a consensus tree for a set of phylogenetic trees [START_REF] Billera | Geometry of the space of phylogenetic trees[END_REF],

and in RNA secondary structure prediction to derive a consensus structure for a set of suboptimal RNA structures [START_REF] Ding | RNA secondary structure prediction by centroids in a Boltzmann ensemble[END_REF]. We therefore expect that being able to compute geometric medians in reconciliation spaces should be a useful addition to the theory of reconciliations.

We now summarize the contents of the rest of the paper. After presenting some preliminary definitions, in Section 3, we define the edit-distance, a metric on the set R(P, H, ) of all reconciliation maps for a host-parasite triple (P, H, ). Variants of this distance have been previously used to quantitatively analyse collections of reconciliations (cf.

e.g. [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF]). We then show that the edit-distance can be computed in a rather natural way relative to the host tree. In Section 4, we present some facts concerning medians, which we then use in Section 5

to define the concept of a median reconciliation for a subset of R(P, H, ). In Section 6, we then show that a median reconciliation is in fact a geometric median for in R(P, H, ) relative to the edit-distance. We conclude in Section 7, with a brief discussion of some potential future directions.

Preliminaries

For a phylogenetic tree T , we denote the vertex set of T by V (T ), the set of interior vertices of T by V o (T ) = V (T ) L(T ), and the root by ⇢ T . If We denote by ⌫ T the partial order of V (T ) given by T . In case the context is clear, we just use ⌫.

Also, we say for vertices x, y 2 V (T ) with x ⌫ y that y is below x and that x is above y. Furthermore, we say that y is strictly below x if y is below x and

x 6 = y and that x is strictly above y if x is above y and x 6 = y. In that case, we also put x y.

If L is a subset of L(T ) of size at least two, we let lca T (L) = lca(L) denote the least common ancestor of the set L, that is, the lowest vertex in T which is above every element of L (with respect to the ordering ⌫ T ). If |L| = 1, then we set lca T (L) = x where x is the unique element in L.

Now, let (P, H, ) be a host-parasite triple. For

v 2 V (P ), we let m(v) = lca H ({ (x) : x 2 L(P ) and v ⌫ P x}).
We also let A(v) be the subset of V (H) given by

A(v) = {v 2 V (H) : ⇢ H ⌫ v ⌫ m(v)}.
We now make some observations (cf. also [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF])we prove only (R2) as the rest are straight-forward to check:

(R0) If v 2 V o (P ) and v 0 2 Ch(v), then m(v) m(v 0 ) and A(v) ⇢ A(v 0 ). (R1) If 2 R(P, H, ), x 2 L(P ), v 2 V (P ) and v ⌫ x, then (v) ⌫ (x) = (x). (R2) If 2 R(P, H, ), then for all v 2 V (P ) we have (v) 2 A(v).
Proof. If v 2 L(P ) then the statement clearly holds. Suppose now there exist some v 2

V o (P ), but (v) 6 2 A(v). Since m(v) 2 A(v),
it su ces to consider the following two cases:

(i) m(v) (v). Note that by (R1), (v) ⌫ (x) for every x 2 L(P ) below v. Hence, (v) lca H ({ (x) : x 2 L(P ) and v ⌫ P x}) = m(v), which is impossible. (ii) m(v) and (v) are not comparable via ⌫ H .
Then there exists some

w 2 A(v) {m(v)} such that w (v). Suppose x 2 L(P ) is below v in P . By (R1), (v) ⌫ (x). But then (x) is not below m(v) in H. This contradicts the definition of m(v). (R3) By (R2), it follows that if , 0 2 R(P, H, ),
then for all v 2 V (P ), the vertices (v) and 0 (v) are comparable in H with respect to the ordering ⌫ H . In particular, it also follows that if { 1 , . . . , l } ✓ R(P, H, ), some l 1, then for all v 2 V (P ), the ordering ⌫ H induces a linear ordering on the set { 1 (v), . . . , l (v)}.

Reconciliation Spaces

To compute a geometric median for some subset of R(P, H, ), we first need to define a metric on R(P, H, ). In this paper, we focus on the editdistance, d edit , since edit-distances are commonly used to compare reconciliations (see e.g. [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF]).

The edit-distance is defined as follows. Given 2 R(P, H, ) and w 2 V (P ) with (w) 6 2

{⇢ H , (par(w))}, we define a map up w from Note that this definition is closely related to the edit-distance defined in [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF].

V (P ) to V (H) by setting up w (v) = par( (v)) if v = w and up w (v) = (v) if v 2 V (P ) {w}. More- over, given 2
To prove our results concerning geometric medians, it is useful to have an alternative description of the edit-distance which we now present.

If v, w 2 V (H), we let d H (v, w) be the length of the (undirected) path in H between v and w. Now, given , 0 2 R(P, H, ), we define the pathdistance between and 0 by

d path ( , 0 ) = X v2V (P ) d H ( (v), 0 (v)).
It is easy to check that d path is a metric on R(P, H, ) (i.e. d path ( , 0 ) vanishes precisely when = 0 , it is symmetric meaning

d path ( , 0 ) = d path ( 0 ,
), and it also satisfies the triangle inequality meaning d path ( , 00 )  d path ( , 0 ) + d path ( 0 , 00 ), for all , 0 , 00 2 R(P, H, )). We now prove the following theorem:

Theorem 1. For all , 0 2 R(P, H, ),

d edit ( , 0 ) = d path ( , 0
). In particular, since d path is a metric on R(P, H, ), so is d edit .

Our proof for this theorem is very similar to the proof of [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF]Theorem 2]), but we include it for the sake of completeness; it immediately follows from the last of the following sequence of observations.

(Up) If 2 R(P, H, ) and w 2 V (P ), and if (w) 6 2 {⇢ H , (par(w))}, then up w 2 R(P, H, ).

Proof. This follows immediately, since if v 2 (E) Given , 0 2 R(P, H, ) distinct, there exists a sequence (w 1 , t 1 ), (w 2 , t 2 ), . . . , (w p , t p ) with

V (P ) ({par(w)} [ Ch(w)) then up w (v) = (v). If v 2 Ch(w), then up w (w) = par( (w)) (w) ⌫ (v) = up w (v) and if v = par(w) then up w (v) = (v) = (par(w)) ⌫ par( (w)) = up w (w).
w i 2 V (H) and t i 2 {up, down}, for all 1  i  p = d path ( , 0 )
, such that 0 is the map obtained by successively applying up/down operations according to the pairs (w i , t i ), 1  i  p, starting with the map . Moreover, no shorter sequence of operations exists for transforming into 0 .

Proof. By the assumption on and 0 and (R3), we may assume without loss of generality that there exists some w 2 V (P ) such that 0 (w) (w).

Then either 0 (w) = ⇢ H or we may assume without loss of generality that w is such that, for all w 0 2 V (P ) strictly above w, we have that (w 0 ) = 0 (w 0 ). Hence, (w) 6 = (par(w)). Starting with the map , it is straightforward to check using (Up) that in either case we can apply a sequence of d H ( (w), 0 (w)) operations of the form (w, up) to obtain a new map 00 2 R(P, H, ) with 00 (w) = 0 (w) and 00 (v) = (v) if v 2 V (P ) {w}. If there still exist vertices w 0 2 V (P ) {w} such that 0 (w 0 ) (w 0 ), then we repeat this process until we obtain a map ⇤ 2 R(P, H, ) with the property that ⇤ (v) ⌫ 0 (v) holds for all v 2 V (P ).

If ⇤ = 0 , then Property (E) follows. Assume that ⇤ 6 = 0 . Then there must exist some

v 2 V (P ) such that ⇤ (v) 0 (v). Out of all those v 2 V (P ) with ⇤ (v) 0 (v)
, choose a vertex w such that d P (w, ⇢ P ) is maximal. We can then transform ⇤ into a new map in R(P, H, ) by using a sequence of operations of the form (w, down). To see this, note first that ⇤ (w) 0 (w) ⌫ m(w). Next, note that there cannot exist some v 0 2 Ch(w) such that ⇤ (v 0 ) = ⇤ (w) as otherwise the choice of w

implies ⇤ (w) = ⇤ (v 0 ) = 0 (v 0 ) 0 (w) ⇤ (w)
which is impossible. Since ⇤ 2 R(P, H, ), it follows by (Down) that ( ⇤ ) down w 2 R(P, H, ). If we repeat this process d H ( ⇤ (w), 0 (w)) times, we eventually obtain a map that agrees with 0 on w and is equal to ⇤ (v) for all v 2 V (P ) {w}. Repeating this process as many times as necessary, we eventually obtain the map 0 .

To obtain 0 from , we used d path ( , 0 ) operations. Moreover, we clearly need at least this number of operations.

Medians

Before moving on to computing geometric medians for reconciliations, we first collect together some basic observations concerning medians.

Given a multiset A of real numbers, we let med(A) denote the median of A. This is a real number, and is the "middle" number of the set A when the elements are arranged in order of magnitude. If the cardinality of A is even, the median is taken to be the real number that is half-way between the two middlemost numbers.

Given a real number r, we now let [r] denote the nearest integer to r in case there is only one, and to be the largest integer that is nearest to r in case there are two nearest integers to r. For example, if r = 0. We now list some useful facts concerning the above definitions.

(M0) Suppose that A is a multiset of real numbers.

If f : R ! R 0 is the function given by setting

f (r) = X a2A |a r| for r 2 R, then f (med(A))  f (r) for all r 2 R.
Proof. This is a well-known fact concerning medians. Essentially it holds because, when r moves away from med(A), then r moves away from at least as many elements of A as it approaches. Hence, f attains its minimum over all r 2 R at med(A). To see that med(A) med(B), we consider the case where m is odd; the proof for m even is similar. Let a i1 , a i2 , . . . , a im be an ordering of the elements of A such that

a i1  a i2  • • •  a im . Then, med(A) = a i m+1 2
and, by assumption, at most m+1

2 1 el- ements in B (namely, b i m+1 2 +1 , . . . , b im ) can be greater than med(A), since if 1  j  m+1 2 , then b ij  a ij  med(A). Hence, med(B) = b i m+1 2  a i m+1 2 = med(A).
(M2) Suppose that A is a multiset of integers, and f is the function defined in (M0).

Then f (zmed(A)) = f (med(A)), and so f (zmed(A))  f (r) for all r 2 R.

Proof. If A has an odd number of elements, we are done in view of (M0) since zmed(A) =

med(A).

Suppose A is even with cardinality m. If zmed(A) = med(A) then we are done again in view of (M0). Assume now that zmed(A) 6 = med(A). Then zmed(A) is of the form [r] where r = med(A) := z 0 2 for some z 0 2 Z. Therefore, there exist two nearest integers z 1 , z 2 to r that are both at distance 1 2 from r. Assume without loss of generality that

z 1 > z 2 , so that z 1 = r + 1 2 , z 2 = r 1 2 .
Then z 1 = zmed(A). But then for the function f in (M0), we clearly have f (r 0 ) = f (med(A)) for all r 0 2 [z 2 , z 1 ]. Statement (M2) now follows immediately.

Median reconciliations

In this section, we define a special type of reconciliation med = med that can be associated to any subset of R(P, H, ). In the next section, we prove that this is in actual fact a geometric median in the space R(P, H, ) endowed with the editdistance.

Suppose = { 1 , . . . , l } ✓ R(P, H, ), l 1.
If v 2 V (P ), then for 1  i  l, we let

n i = d H (m(v), i (v)).
This is well defined by (R2

) since i (v) 2 A(v), for all 1  i  l.
We now define the map med = med from V (P ) to V (H) by taking, for v 2 V (P ),

med (v) to be an element w 2 A(v) ✓ V (H) such that d H (m(v), w) = zmed(n 1 , n 2 , . . . , n l ), for v 2 V (P ).
Note that med is welldefined since zmed(n 1 , n 2 , . . . , n l ) is an integer and

zmed(n 1 , n 2 , . . . , n l )  d H (⇢ H , m(v)). We now
show that med is a reconciliation.

Theorem 2. med 2 R(P, H, ).

Proof. First note that med restricted to L(P ) is clearly equal to .

Suppose now that v 2 V o (P ) and that v 0 2 Ch(v). We need to show that med (v) ⌫ med (v 0 ).

First note that since i (v) 2 A(v) for all

1  i  l, Property (R0) implies that { 1 (v), . . . , l (v), 1 (v 0 ), . . . , l (v 0 )} is a subset of A(v 0 ). Moreover, i (v) ⌫ i (v 0 ) for all 1  i  l as each i is a reconciliation. Now, let n i = d H (m(v), i (v)) and n 0 i = d H (m(v 0 ), i (v 0 )) for all 1  i  l. Note that, by definition, med (v) is equal to some w 2 A(v) ⇢ A(v 0 ) such that d H (m(v), w) = zmed(n 1 , . . . , n l ),
and med (v 0 ) is equal to some w 0 2 A(v 0 ) such that d H (m(v 0 ), w 0 ) = zmed(n 0 1 , . . . , n 0 l ). For each 1  i  l, let

p i = n i + d H (m(v), m(v 0 )) = d H ( i (v), m(v)) + d H (m(v), m(v 0 )) = d H ( i (v), m(v 0 ))
where the last equality holds in view of (R0).

Hence, d H (m(v 0 ), w) = zmed(p 1 , . . . , p l ). Moreover, since i (v) ⌫ i (v 0 ) ⌫ m(v 0 ) for all 1  i  l, it follows that p i n 0 i . By definition and (M1), it follows that d H (m(v 0 ), w) = zmed(p 1 , . . . , p l ) zmed(n 0 1 , . . . , n 0 l ) = d H (m(v 0 ), w 0 ). Hence, med (v) ⌫ med (v 0 ), as required.

Remark: Using similar arguments, we can also define a "minimum reconciliation" for the set as follows. Let min = min : V (P ) ! V (H) be given by taking min (v) to be a lowest element in { 1 (v), . . . , l (v)} for v 2 V (P ). Note that min is well-defined by (R3). Moreover, min 2 R(P, H, ): Indeed, min restricted to L(P ) is clearly equal to . Moreover, if v 2 V o (P ), v 0 2 Ch(v), then for i, j 2 {1, . . . , l} such that min (v) = i (v) and min (v 0 ) = j (v 0 ), we have

min (v 0 ) = j (v 0 ) i (v 0 ) i (v) = min (v).
A similar approach can be used to define a"maximum reconciliation" for .

Geometric medians

In this section, we show that for a subset of R(P, H, ) endowed with the edit-distance, the reconciliation med is a geometric median for . This will follow immediately from the following theorem:

Theorem 3. Suppose that T is a phylogenetic tree and that W = {w 1 , . . . , w l } ✓ V (T ), l 1, is a subset of the set of vertices of some path in T between ⇢ T and some vertex s 2 V (T ). Let q i = d T (w i , s), 1  i  l, and let u be a vertex in such that d T (u, s) = zmed(q 1 , . . . , q l ). Then for all v 0 2 V (T ),

X w2W d T (v 0 , w) X w2W d T (u, w). (1)
Proof. Let v 0 2 V (T ). First, suppose that v 0 is a vertex in a path in T between ⇢ T and some leaf of T that contains as a subpath.

Let A = {q 1 , . . . , q l }, ↵ = d T (u, s) and = d T (s, v 0 ) if v 0 is above or equal to s in T and = d T (s, v 0 ) if v is below s in T . Then, for the function f in (M0), we have f ( ) f (zmed(A)) in view of (M2). Hence, P l i=1 | q i | P l i=1 |↵ q i |, from which the theorem follows.

Suppose now that v 0 is not of the above form.

Then there must exist some vertex t in the path such that t v 0 . Using the same argument as above for t instead of for v 0 , it follows that

X w2W d T (v 0 , w) = X w2W (d T (w, t) + d T (t, v 0 )) = X w2W d T (w, t) + |W |d T (t, v 0 ) X w2W d T (u, w) + |W |d T (t, v 0 ) X w2W d T (u, w). Corollary 4. Suppose that = { 1 , . . . , l } ✓ R(P, H, ), l 1.
Then med is a geometric median for in the space R(P, H, ) endowed with the metric d edit (= d path ).

Proof. Suppose that 2 R(P, H, ). Then by (R2), for v 2 V (P ), taking

w i = i (v), u = med (v), s = m(v) and v 0 = (v) in Theorem 3, we obtain m X i=1 d path ( med , i ) = l X i=1 X v2V (P ) d H ( med (v), i (v))  l X i=1 X v2V (P ) d H ( (v), i (v)) = l X i=1 d path ( , i ).
Note that as a consequence of our results, we can compute a geometric median for a set ✓ R(P, H, ) in polynomial time. Indeed, we can compute d H and the vertices m(v), v 2 V (P ) in polynomial time. Therefore, for each v 2

V (P ), we can compute the multiset of numbers

d H (m(v), (v)), 2
, the median of this multiset, and therefore med (v), in polynomial time.

It would be interesting to know if there is a more e cient way to compute the map med .

Discussion

In this paper, we have described how to find a geometric median for a set of reconciliations within the space of all reconciliations endowed with the path-distance (or, equivalently, the edit-distance).

It would be of interest to understand properties of a geometric median. For example, reconciliations are usually assigned some cost (see e.g. [START_REF] Doyon | Space of gene/species tree reconciliations and parsimonious models[END_REF]), and it could be interesting to understand how the cost of the geometric median of a set of reconciliations is related to the costs of each of the reconciliations in the set. Also, we have focused on the edit-distance.

However, it should be possible to define alternative metrics on collections of reconciliations, and to potentially derive geometric medians relative to these metrics.

In another direction, as stated in the introduction, we considered one of the simplest models for reconciling trees. There are more complex models which allow the inclusion of additional evolutionary processes (such as host-switches or, in the case of gene-species reconciliation, lateral gene transfer) [START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF], and it would be of interest to see whether geometric medians can also be derived for these models. This could be useful since such models can generate multiple optimal solutions [START_REF] Donati | Eucalypt: E cient tree reconciliation enumerator[END_REF]. However, it could also be quite complicated as in our proofs we heavily relied on properties of the median of a set of points in the real line, and for the more complex reconciliation models it is not clear that such arguments can be applied.

Finally, in general the geometric median can be regarded as a consensus for a set of reconciliations.

It would be interesting to find other methods for defining a consensus reconciliation and to understand how these are related to the geometric median (e.g. we could try to define a centroid reconciliation for a set which, roughly speaking, would correspond to the center of mass for the set).

Figure 1 :

 1 Figure 1: An example of a reconciliation map. Note that is given by (a) = A, . . . , (e) = E.

v 2 V

 2 o (T ), we let Ch(v) denote the set of children of v, and if v 2 V (T ) {⇢ T }, we let par(v) denote the parent of v in T .

  R(P, H, ) and w 2 V o (P ) with (w) m(w) and (w) 6 = (v 0 ) for all v 0 2 Ch(w), we define a map down w from V (P ) to V (H) by setting down w (v) to be the (only) vertex in the set A(w) \ Ch( (w)) if v = w, and down w (v) = (v) if v 2 V (P ) {w}. Now, given , 0 2 R(P, H, ), we define d edit ( , 0 ) to be the smallest number of up/down operations required to change into 0 .

(Down) If 2 R) for all v 0 2

 22 (P, H, ) and w 2 V (P ) with (w) m(w) and (w) 6 = (v 0 ) for all v 0 2 Ch(w), Ch(w) and, by (R0), A(v) ⇢ A(v 0 ) holds for all such v 0 , we havedown w (w) ⌫ (v 0 ) = down w (v 0 ), for all v 0 2 Ch(w).Since down w (x) = (x) = (x) holds for all x 2 L(P ), it follows that down w 2 R(P, H, ).

  5 then [r] = max{0, 1} = 1, if r = 0.2 then [r] = 0, and if r = 0.7 then [r] = 1. Given a multiset A of m 1 integers, we define zmed(A) to be [med(A)]. For example, if A = {1, 1, 2, 3, 4} then zmed(A) = 2, and if A = {1, 1, 2, 3, 4, 5} then zmed(A) = 3. Note that if A = {n 1 , n 2 , . . . , n m }, then we also denote med(A) and zmed(A) by med(n 1 , n 2 , . . . , n m ) and zmed(n 1 , n 2 , . . . , n m ), respectively. Also, if m is odd, then zmed(A) = med(A).

(

  M1) Suppose that A, B are two multisets of integers both containing m 1 elements. Suppose that there exists an ordering a 1 , a 2 , . . . , a m of the elements of A and an ordering b 1 , b 2 , . . . , b m of the elements of B such that a i b i for all 1  i  m. Then med(A) med(B) and zmed(A) zmed(B). Proof. If med(A) med(B), then clearly zmed(A) zmed(B).

Acknowledgement All authors thank the Royal Society for its support.