Zhongyuan Xu

Scott D Stoller

Mining Attribute-Based Access Control Policies from Logs

Attribute-based access control (ABAC) provides a high level of flexibility that promotes security and information sharing. ABAC policy mining algorithms have potential to significantly reduce the cost of migration to ABAC, by partially automating the development of an ABAC policy from information about the existing access-control policy and attribute data. This paper presents an algorithm for mining ABAC policies from operation logs and attribute data. To the best of our knowledge, it is the first algorithm for this problem.

Introduction

ABAC is becoming increasingly important as security policies become more dynamic and more complex. In industry, more and more products support ABAC, using a standardized ABAC language such as XACML or a vendor-specific ABAC language. In government, the Federal Chief Information Officer Council called out ABAC as a recommended access control model [START_REF]Federal Identity Credential and Access Management (FICAM) Roadmap and Implementation Guidance[END_REF][START_REF] Hu | Guide to Attribute Based Access Control (ABAC) Definition and Considerations (Final Draft)[END_REF]. ABAC allows "an unprecedented amount of flexibility and security while promoting information sharing between diverse and often disparate organizations" [START_REF] Hu | Guide to Attribute Based Access Control (ABAC) Definition and Considerations (Final Draft)[END_REF]. ABAC overcomes some of the problems associated with RBAC, notably role explosion [START_REF] Hu | Guide to Attribute Based Access Control (ABAC) Definition and Considerations (Final Draft)[END_REF].

ABAC promises long-term cost savings through reduced management effort, but manual development of an initial policy can be difficult and expensive [START_REF] Hu | Guide to Attribute Based Access Control (ABAC) Definition and Considerations (Final Draft)[END_REF]. Policy mining algorithms promise to drastically reduce the cost of migrating to ABAC, by partially automating the process.

Role mining, i.e., mining of RBAC policies, is an active research area and a currently relatively small (about $70 million) but rapidly growing commercial market segment [START_REF] Hachana | Role mining to assist authorization governance: How far have we gone[END_REF]. In contrast, there is, so far, relatively little work on ABAC policy mining. We recently developed an algorithm to mine an ABAC policy from an ACL policy or RBAC policy [START_REF] Xu | Mining attribute-based access control policies[END_REF].

However, an ACL policy or RBAC policy might not be available, e.g., if the current access control policy is encoded in a program or is not enforced by a computerized access control mechanism. An alternative source of information about the current access control policy is operation logs, or "logs" for short. Many software systems produce logs, e.g., for auditing, accounting, and accountability purposes. Molloy, Park, and Chari proposed the idea of mining policies from logs and developed algorithms for mining RBAC policies from logs [START_REF] Molloy | Generative models for access control policies: applications to role mining over logs with attribution[END_REF].

The main challenge is that logs generally provide incomplete information about entitlements (i.e., granted permissions). Specifically, logs provide only a lower bound on the entitlements. Therefore, the generated policy should be allowed to include over-assignments, i.e., entitlements not reflected in the logs. This paper presents an algorithm for mining ABAC policies from logs and attribute data. To the best of our knowledge, it is the first algorithm for this problem. It is based on our algorithm for mining ABAC policies from ACLs [START_REF] Xu | Mining attribute-based access control policies[END_REF]. At a high level, the algorithm works as follows. It iterates over tuples in the user-permission relation extracted from the log, uses selected tuples as seeds for constructing candidate rules, and attempts to generalize each candidate rule to cover additional tuples in the user-permission relation by replacing conjuncts in attribute expressions with constraints. After constructing candidate rules that together cover the entire user-permission relation, it attempts to improve the policy by merging and simplifying candidate rules. Finally, it selects the highestquality candidate rules for inclusion in the generated policy.

Several changes are needed to our algorithm for mining ABAC policies from ACLs to adapt it to mining from logs. When the algorithm generalizes, merges, or simplifies rules, it discards candidate rules that are invalid, i.e., that produce over-assignments. We modify those parts of the algorithm to consider those candidate rules, because, as discussed above, over-assignments must be permitted. To evaluate those candidate rules, we introduce generalized notions of rule quality and policy quality that quantify a trade-off between the number of overassignments and other aspects of quality. We consider a metric that includes the normalized number of over-assignments in a weighted sum, a frequency-sensitive variant that assigns higher quality to rules that cover more frequently used entitlements, along the lines of [START_REF] Molloy | Generative models for access control policies: applications to role mining over logs with attribution[END_REF], and a metric based on a theory quality metric in inductive logic programming [START_REF] Muggleton | Inverse entailment and progol[END_REF][START_REF] Muggleton | CProgol4.4: a tutorial introduction[END_REF].

ABAC policy mining is similar to inductive logic programming (ILP), which learns logic-programming rules from facts. Mining ABAC policies from logs and attribute data is similar to ILP algorithms for learning from positive examples, because those algorithms allow the learned rules to imply more than the given facts (i.e., in our terminology, to have over-assignments). We implemented a translation from ABAC policy mining to Progol [START_REF] Muggleton | CProgol4.4: a tutorial introduction[END_REF], a well-known ILP system. We evaluated our algorithm and the ILP-based approach on some relatively small but non-trivial handwritten case studies and on synthetic ABAC policies. The results demonstrate our algorithm's effectiveness even when the log reflects only a fraction of the entitlements. Although the original (desired) ABAC policy is not reconstructed perfectly from the log, the mined policy is sufficiently similar to it that the mined policy would be very useful as a starting point for policy administrators tasked with developing that ABAC policy. This section presents the ABAC policy language used in our work. It is adopted from [START_REF] Xu | Mining attribute-based access control policies[END_REF]. We consider a specific ABAC policy language, but our approach is general and can be adapted to other ABAC policy languages. Our ABAC policy language contains the common ABAC policy language constructs, except arithmetic inequalities and negation, which are left for future work.

Given a set U of users and a set A u of user attributes, user attribute data is represented by a function d u such that d u (u, a) is the value of attribute a for user u. There is a distinguished user attribute uid that has a unique value for each user. Similarly, given a set R of resources and a set A r of resource attributes, resource attribute data is represented by a function d r such that d r (r, a) is the value of attribute a for resource r. There is a distinguished resource attribute rid that has a unique value for each resource. We assume the set A u of user attributes can be partitioned into a set A u,1 of single-valued user attributes which have atomic values, and a set A u,m of multi-valued user attributes whose values are sets of atomic values. Similarly, we assume the set A r of resource attributes can be partitioned into a set A r,1 of single-valued resource attributes and a set of A r,m of multi-valued resource attributes. We assume there is a distinguished atomic value ⊥ used to indicate that an attribute's value is unknown.

A user-attribute expression (UAE) is a function e such that, for each user attribute a, e(a) is either the special value , indicating that e imposes no constraint on the value of a, or a set (interpreted as a disjunction) of possible values of a excluding ⊥. We refer to e(a) as the conjunct for a. A UAE e uses attribute a if e(a) = . Let attr(e) denote the set of attributes used by e.

A user u satisfies a UAE e, denoted u |= e, iff (∀a ∈ A u,1 . e(a) = ∨ ∃v ∈ e(a). d u (u, a) = v) and (∀a ∈ A u,m . e(a) = ∨ ∃v ∈ e(a). d u (u, a) ⊇ v). For multi-valued attributes, we use the condition d u (u, a) ⊇ v instead of d u (u, a) = v because elements of a multi-valued user attribute typically represent some type of capabilities of a user, so using ⊇ expresses that the user has the specified capabilities and possibly more. For example, suppose A u,1 = {dept, position} and A u,m = {courses}. The function e 1 with e 1 (dept) = {CS} and e 1 (position) = {grad, ugrad} and e 1 (courses) = {{CS101, CS102}} is a user-attribute expression satisfied by users in the CS department who are either graduate or undergraduate students and whose courses include CS101 and CS102.

In examples, we may write attribute expressions with a logic-based syntax, for readability. For example, the above expression e 1 may be written as dept = CS ∧ position ∈ {ugrad, grad} ∧ courses ⊇ {CS101, CS102}. For an example that uses ⊇∈, the expression e 2 that is the same as e 1 except with e 2 (courses) = {{CS101}, {CS102}} may be written as dept = CS ∧ position ∈ {ugrad, grad} ∧ courses ⊇∈ {{CS101}, {CS102}}, and is satisfied by graduate or undergraduate students in the CS department whose courses include either CS101 or CS102.

The meaning of a user-attribute expression e, denoted [[e]] U , is the set of users in U that satisfy it. User attribute data is an implicit argument to [[e]] U . We say that e characterizes the set [[e]] U .

A resource-attribute expression (RAE) is defined similarly, except using the set A r of resource attributes instead of the set A u of user attributes. The semantics of RAEs is defined similarly to the semantics of UAEs, except simply using equality, not ⊇, in the condition for multi-valued attributes in the definition of "satisfies", because we do not interpret elements of multi-valued resource attributes specially (e.g., as capabilities).

Constraints express relationships between users and resources. An atomic constraint is a formula f of the form a u,m ⊇ a r,m , a u,m a r,1 , or a u,1 = a r,1 , where a u,1 ∈ A u,1 , a u,m ∈ A u,m , a r,1 ∈ A r,1 , and a r,m ∈ A r,m . The first two forms express that user attributes contain specified values. This is a common type of constraint, because user attributes typically represent some type of capabilities of a user. Let uAttr(f ) and rAttr(f ) refer to the user attribute and resource attribute, respectively, used in f . User u and resource r satisfy an atomic constraint f , denoted u, r |= f , if d u (u, uAttr(f )) = ⊥ and d r (u, rAttr(f )) = ⊥ and formula f holds when the values d u (u, uAttr(f )) and d r (u, rAttr(f )) are substituted in it.

A constraint is a set (interpreted as a conjunction) of atomic constraints. User u and resource r satisfy a constraint c, denoted u, r |= c, if they satisfy every atomic constraint in c. In examples, we write constraints as conjunctions instead of sets. For example, the constraint "specialties ⊇ topics ∧ teams treatingTeam" is satisfied by user u and resource r if the user's specialties include all of the topics associated with the resource, and the set of teams associated with the user contains the treatingTeam associated with the resource.

A user-permission tuple is a tuple u, r, o containing a user, a resource, and an operation. This tuple means that user u has permission to perform operation o on resource r. A user-permission relation is a set of such tuples.

A rule is a tuple e u , e r , O, c , where e u is a user-attribute expression, e r is a resource-attribute expression, O is a set of operations, and c is a constraint. For a rule ρ = e u , e r , O, c , let uae(ρ) = e u , rae(ρ) = e r , ops(ρ) = O, and con(ρ) = c. For example, the rule true, type=task ∧ proprietary=false, {read, request}, projects project ∧ expertise ⊇ expertise used in our project management case study can be interpreted as "A user working on a project can read and request to work on a non-proprietary task whose required areas of expertise are among his/her areas of expertise." User u, resource r, and operation o satisfy a rule ρ,

denoted u, r, o |= ρ, if u |= uae(ρ) ∧ r |= rae(ρ) ∧ o ∈ ops(ρ) ∧ u, r |= con(ρ).
An ABAC policy is a tuple U, R, Op, A u , A r , d u , d r , Rules , where U , R, A u , A r , d u , and d r are as described above, Op is a set of operations, and Rules is a set of rules. The user-permission relation induced by a policy π with the above form is

The user-permission relation induced by a rule

ρ is [[ρ]] = { u, r, o ∈ U × R × Op | u,
[[π]] = ρ∈Rules [[ρ]].
An operation log entry e is a tuple u, r, o, t where u ∈ U is a user, r ∈ R is a resource, o ∈ Op is an operation, and t is a timestamp. An operation log is a sequence of operation log entries. The user-permission relation induced by an

operation log L is UP (L) = { u, r, o | ∃t. u, r, o, t ∈ L}.
The input to the ABAC-from-logs policy mining problem is a tuple

I = U, R, Op, A u , A r , d u , d r , L , where U is a set of users, R is a set of resources,
Op is a set of operations, A u is a set of user attributes, A r is a set of resource attributes, d u is user attribute data, d r is resource attribute data, and L is an operation log, such that the users, resources, and operations that appear in L are subsets of U , R, and Op, respectively. The goal of the problem is to find a set of rules Rules such that the ABAC policy π = U, R, Op, A u , A r , d u , d r , Rules maximizes a suitable policy quality metric.

The policy quality metric should reflect the size and meaning of the policy. Size is measured by weighted structural complexity (WSC) [START_REF] Molloy | Mining roles with multiple objectives[END_REF], and smaller policies are considered to have higher quality. This is consistent with usability studies of access control rules, which conclude that more concise policies are more manageable. Informally, the WSC of an ABAC policy is a weighted sum of the number of elements in the policy. Specifically, the WSC of an attribute expression is the number of atomic values that appear in it, the WSC of an operation set is the number of operations in it, the WSC of a constraint is the number of atomic constraints in it, and the WSC of a rule is a weighted sum of the WSCs of its components, namely, WSC( e u , e r , O, c ) = w 1 WSC(e u ) + w 2 WSC(e r ) + w 3 WSC(O) + w 4 WSC(c), where the w i are user-specified weights. The WSC of a set of rules is the sum of the WSCs of its members.

The meaning [[π]] of the ABAC policy is taken into account by considering the differences from UP (L), which consist of over-assignments and underassignments. The over-assignments are [[π]] \ UP (L). The under-assignments are UP (L)\ [[π]]. Since logs provide only a lower-bound on the actual user-permission relation (a.k.a entitlements), it is necessary to allow some over-assignments, but not too many. Allowing under-assignments is beneficial if the logs might contain noise, in the form of log entries representing uses of permissions that should not be granted, because it reduces the amount of such noise that gets propagated into the policy, and it improves the stability of the generated policy. We define a policy quality metric that is a weighted sum of these aspects:

Q pol (π, L) = WSC(π) + w o | [[π]] \ UP (L)| / |U | (1)
where the policy over-assignment weight w o is a user-specified weight for overassignments, and for a set S of user-permission tuples, the frequency-weighted size of S with respect to log L is |S| L = u,r,o ∈S freq( u, r, o , L), where the relative frequency of a user-permission tuple in a log is given by the frequency function freq( u, r, o , L) = |{e ∈ L | userPerm(e) = u, r, o }| / |L|, where the user-permission part of a log entry is given by userPerm( u, r, o, t ) = u, r, o .

For simplicity, our presentation of the problem and algorithm assume that attribute data does not change during the time covered by the log. Accommo-dating changes to attribute data is not difficult. It mainly requires re-defining the notions of policy quality and rule quality (introduced in Section 4) to be based on the set of log entries covered by a rule, denoted

[[ρ]] LE , rather than [[ρ]]. The definition of [[ρ]] LE is similar to the definition of [[ρ]],
except that, when determining whether a log entry is in [[ρ]] LE , the attribute data in effect at the time of the log entry is used.

Algorithm

Our algorithm is based on the algorithm for mining ABAC policies from ACLs and attribute data in [START_REF] Xu | Mining attribute-based access control policies[END_REF]. Our algorithm does not take the order of log entries into account, so the log can be summarized by the user-permission relation UP 0 induced by the log and the frequency function freq, described in the penultimate paragraph of Section 3.

Top-level pseudocode appears in Figure 1. We refer to tuples selected in the first statement of the first while loop as seeds. The top-level pseudocode is explained by embedded comments. It calls several functions, described next. Function names hyperlink to pseudocode for the function, if it is included in the paper, otherwise to the description of the function.

The function addCandRule(s u , s r , s o , cc, uncovUP , Rules) in Figure 2 first calls computeUAE to compute a user-attribute expression e u that characterizes s u , and computeRAE to compute a resource-attribute expression e r that characterizes s r . It then calls generalizeRule(ρ, cc, uncovUP , Rules) to generalize rule ρ = e u , e r , s o , ∅ to ρ and adds ρ to candidate rule set Rules. The details of the functions called by addCandRule are described next.

The function computeUAE(s, U ) computes a user-attribute expression e u that characterizes the set s of users. Preference is given to attribute expressions that do not use uid, since attribute-based policies are generally preferable to identity-based policies, even when they have higher WSC, because attributebased generalize better. Similarly, computeRAE(s, R) computes a resource-attribute expression that characterizes the set s of resources. Pseudocode for computeUAE and computeRAE are omitted. The function candidateConstraint(r, u) returns a set containing all of the atomic constraints that hold between resource r and user u. Pseudocode for candidateConstraint is straightforward and omitted.

The function generalizeRule(ρ, cc, uncovUP , Rules) in Figure 3 attempts to generalize rule ρ by adding some of the atomic constraints in cc to ρ and eliminating the conjuncts of the user attribute expression and/or the resource attribute expression corresponding to the attributes used in those constraints, i.e., mapping those attributes to . We call a rule obtained in this way a generalization of ρ. Such a rule is more general than ρ in the sense that it refers to relationships instead of specific values. Also, the user-permission relation induced by a generalization of ρ is a superset of the user-permission relation induced by ρ. generalizeRule(ρ, cc, uncovUP , Rules) returns the generalization ρ of ρ with the best quality according to a given rule quality metric. Note that ρ may cover tuples that are already covered (i.e., are in UP ); in other words, our algorithm can generate policies containing rules whose meanings overlap.

A rule quality metric is a function Q rul (ρ, UP ) that maps a rule ρ to a totallyordered set, with the ordering chosen so that larger values indicate high quality. The second argument UP is a set of user-permission tuples. Our rule quality metric assigns higher quality to rules that cover more currently uncovered userpermission tuples and have smaller size, with an additional term that imposes a penalty for over-assignments, measured as a fraction of the number of userpermission tuples covered by the rule, and with a weight specified by a parameter w o , called the rule over-assignment weight.

Q rul (ρ, UP ) = | [[ρ]] ∩ UP | |ρ| × (1 - w o × |overAssign(ρ)| | [[ρ]] | ).
In generalizeRule, uncovUP is the second argument to Q rul , so [[ρ]] ∩ UP is the set of user-permission tuples in UP 0 that are covered by ρ and not covered by rules already in the policy. The loop over i near the end of the pseudocode for generalizeRule considers all possibilities for the first atomic constraint in cc that gets added to the constraint of ρ. The function calls itself recursively to determine the subsequent atomic constraints in c that get added to the constraint. We also developed a frequency-sensitive variant of this rule quality metric. Let Q freq rul denote the frequency-weighted variant of Q rul , obtained by weighting each user-permission tuple by its relative frequency (i.e., fraction of occurrences) in the log, similar to the definition of λ-distance in [START_REF] Molloy | Generative models for access control policies: applications to role mining over logs with attribution[END_REF]. Specifically, the definition of Q freq rul is obtained from the definition of

Q rul by replacing | [[ρ]] ∩ UP | with | [[ρ]] ∩ UP | L (recall that | • | L is defined in Section 3).
We also developed a rule quality metric Q ILP rul based closely on the theory quality metric for inductive logic programming described in [START_REF] Muggleton | Inverse entailment and progol[END_REF]. Details of the definition are omitted to save space.

The function mergeRules(Rules) in Figure 3 attempts to improve the quality of Rules by removing redundant rules and merging pairs of rules. A rule ρ in Rules is redundant if Rules contains another rule ρ such that every userpermission tuple in UP 0 that is in [[ρ]] is also in [[ρ ]]. Informally, rules ρ 1 and ρ 2 are merged by taking, for each attribute, the union of the conjuncts in ρ 1 and ρ 2 for that attribute. If adding the resulting rule ρ mrg to the policy and removing rules (including ρ 1 and ρ 2 ) that become redundant improves policy quality and does not introduce over-assignments where none existed before, then ρ mrg is added to Rules, and the redundant rules are removed from Rules. As optimizations (in the implementation, not reflected in the pseudocode), meanings of rules are cached, and policy quality is computed incrementally. mergeRules(Rules) updates its argument Rules in place, and it returns a Boolean indicating whether any rules were merged.

The function simplifyRules(Rules) attempts to simplify all of the rules in Rules. It updates its argument Rules in place, replacing rules in Rules with simplified versions when simplification succeeds. It returns a Boolean indicating whether any rules were simplified. It attempts to simplify each rule in several ways, including elimination of redundant sets using function elimRedundantSets, elimination of conjuncts, elimination of constraints, elimination of elements of sets in conjuncts for multi-valued user attributes, and elimination of overlap between rules. The detailed definition is similar to the one in [START_REF] Xu | Mining attribute-based access control policies[END_REF] and is omitted to save space.

Example

We illustrate the algorithm on a small fragment of our university case study (cf. Section 5.1). The fragment contains a single rule ρ 0 = true, type ∈ {gradebook}, {addScore, readScore}, crsTaught crs and all of the attribute data from the full case study, except attribute data for gradebooks for courses other than cs601. We consider an operation log L containing three entries: { csFac2, cs601gradebook, addScore, t 1 , csFac2, cs601gradebook, readScore, t 2 , csStu3, cs601gradebook, addScore, t 3 }. User csFac2 is a faculty in the computer science department who is teaching cs601; attributes are position = faculty, dept = cs, and crsTaught = {cs601}. csStu3 is a CS student who is a TA of cs601; attributes are position = student, dept = cs, and crsTaught = {cs601}. cs601gradebook is a resource with attributes type = gradebook, dept = cs, and crs = cs601.

Our algorithm selects user-permission tuple csFac2, cs601gradebook, addScore as the first seed, and calls function candidateConstraint to compute the set of atomic constraints that hold between csFac2 and cs601gradebook; the result is cc = {dept = dept, crsTaught crs}. addCandRule is called twice to compute candidate rules. The first call to addCandRule calls computeUAE to compute a UAE e u that characterizes the set s u containing users with permission addScore, cs601gradebook and with the same candidate constraint as csFac2 for cs601gradebook; the result is e u = {position ∈ {faculty, student} ∧ dept ∈ {cs}∧crsTaught ⊇ {{cs601}}}. addCandRule also calls computeRAE to compute a resource-attribute expression that characterizes {cs601gradebook}; the result is e r = {crs ∈ {cs601}∧dept ∈ {cs}∧type ∈ {gradebook}}. The set of operations considered in this call to addCandRule is simply s o = {addScore}. addCandRule then calls generalizeRule, which generates a candidate rule ρ 1 which initially has e u , e r and s o in the first three components, and then atomic constraints in cc are added to ρ 1 , and conjuncts in e u and e r for attributes used in cc are eliminated; the result is ρ 1 = position ∈ {faculty, student}, type ∈ {gradebook}, {addScore}, dept = dept ∧ crsTaught crs , which also covers the third log entry. Similarly, the second call to addCandRule generates a candidate rule ρ 2 = position ∈ {faculty}, type ∈ {gradebook}, {addScore, readScore}, dept = dept ∧ crsTaught crs , which also covers the second log entry.

All of UP (L) is covered, so our algorithm calls mergeRules, which attempts to merge ρ 1 and ρ 2 into rule ρ 3 = position ∈ {faculty, student}, type ∈ {gradebook}, {addScore, readScore}, dept = dept ∧ crsTaught crs . ρ 3 is discarded because it introduces an over-assignment while ρ 1 and ρ 2 do not. Next, simplifyRules is called, which first simplifies ρ 1 and ρ 2 to ρ 1 and ρ 2 , respectively, and then eliminates ρ 1 because it covers a subset of the tuples covered by ρ 2 . The final result is ρ 2 , which is identical to the rule ρ 0 in the original policy.

Evaluation Methodology

We evaluate our policy mining algorithms on synthetic operation logs generated from an ABAC policy (some handwritten and some synthetic) and probability distributions characterizing the frequency of actions. This allows us to evaluate the effectiveness of our algorithm by comparing the mined policies with the original ABAC policies. We are eager to also evaluate our algorithm on actual operation logs and actual attribute data, when we are able to obtain them.

ABAC Policies

Case Studies. We developed four case studies for use in evaluation of our algorithm, described briefly here. Details of the case studies, including all policy rules, various size metrics (number of users, number of resources, etc.), and some illustrative attribute data, appear in [START_REF] Xu | Mining attribute-based access control policies[END_REF].

Our university case study is a policy that controls access by students, instructors, teaching assistants, registrar officers, department chairs, and admissions officers to applications (for admission), gradebooks, transcripts, and course schedules. Our health care case study is a policy that controls access by nurses, doctors, patients, and agents (e.g., a patient's spouse) to electronic health records (HRs) and HR items (i.e., entries in health records). Our project management case study is a policy that controls access by department managers, project leaders, employees, contractors, auditors, accountants, and planners to budgets, schedules, and tasks associated with projects. Our online video case study is a policy that controls access to videos by users of an online video service.

The number of rules in the case studies is relatively small (10 ± 1 for the first three case studies, and 6 for online video), but they express non-trivial policies and exercise all the features of our policy language, including use of set membership and superset relations in attribute expressions and constraints. The manually written attribute dataset for each case study contains a small number of instances of each type of user and resource.

For the first three case studies, we generated a series of synthetic attribute datasets, parameterized by a number N , which is the number of departments for the university and project management case studies, and the number of wards for the health care case study. The generated attribute data for users and resources associated with each department or ward are similar to but more numerous than the attribute data in the manually written datasets. We did not bother creating synthetic data for the online video case study, because the rules are simpler. Synthetic Policies. We generated synthetic policies using the algorithm proposed by Xu and Stoller [START_REF] Xu | Mining attribute-based access control policies[END_REF]. Briefly, the policy synthesis algorithm first generates the rules and then uses the rules to guide generation of the attribute data; this allows control of the number of granted permissions. The algorithm takes N rule , the desired number of rules, as an input. The numbers of users and resources are proportional to the number of rules. Generation of rules and attribute data is based on several probability distributions, which are based loosely on the case studies or assumed to have a simple functional form (e.g., uniform distribution).

Log Generation

The inputs to the algorithm are an ABAC policy π, the desired completeness of the log, and several probability distributions. The completeness of a log, relative to an ABAC policy, is the fraction of user-permission tuples in the meaning of the policy that appear in at least one entry in the log. A straightforward log generation algorithm would generate each log entry by first selecting an ABAC rule, according to a probability distribution on rules, and then selecting a userpermission tuple that satisfies the rule, according to probability distributions on users, resources, and operations. This process would be repeated until the specified completeness is reached. This algorithm is inefficient when high completeness is desired. Therefore, we adopt a different approach that takes advantage of the fact that our policy mining algorithm is insensitive to the order of log entries and depends only on the frequency of each user-permission tuple in the log. In particular, instead of generating logs (which would contain many entries for popular user-permission tuples), our algorithm directly generates a log summary, which is a set of user-permission tuples with associated frequencies (equivalently, a set of user-permission tuples and a frequency function).

Probability Distributions. An important characteristic of the probability distributions used in synthetic log and log summary generation is the ratio between the most frequent (i.e., most likely) and least frequent items of each type (rule, user, etc.). For case studies with manually written attribute data, we manually created probability distributions in which this ratio ranges from about 3 to 6. For case studies with synthetic data and synthetic policies, we generated probability distributions in which this ratio is 25 for rules, 25 for resources, 3 for users, and 3 for operations (the ratio for operations has little impact, because it is relevant only when multiple operations appear in the same rule, which is uncommon).

Metrics

For each case study and each associated attribute dataset (manually written or synthetic), we generate a synthetic operation log using the algorithm in Section 5.2 and then run our ABAC policy mining algorithms. We evaluate the effectiveness of each algorithm by comparing the generated ABAC policy to the original ABAC policy, using the metrics described below. Syntactic Similarity. Jaccard similarity of sets is syn (e r , e r ), J(O, O ), and J(c, c ). The syntactic similarity of rule sets Rules and Rules is the average, over rules ρ in Rules, of the syntactic similarity between ρ and the most similar rule in Rules . The syntactic similarity of policies π and π is the maximum of the syntactic similarities of the sets of rules in the policies, considered in both orders (this makes the relation symmetric). Syntactic similarity ranges from 0 (completely different) to 1 (identical).

J(S 1 , S 2 ) = |S 1 ∩S 2 | / |S 1 ∪S 2 |.
Semantic Similarity. Semantic similarity measures the similarity of the entitlements granted by two policies. The semantic similarity of policies π and π is defined by J([[π]] , [[π ]]). Semantic similarity ranges from 0 (completely different) to 1 (identical).

Fractions of Under-Assignments and Over-Assignments. To characterize the semantic differences between an original ABAC policy π 0 and a mined policy π in a way that distinguishes under-assignments and over-assignments, we compute the fraction of over-assignments and the fraction of under-assignments, defined by

| [[π]] \ [[π 0 ]] | / | [[π]] | and | [[π 0 ]] \ [[π]] | / | [[π]] |, respectively.

Experimental Results

This section presents experimental results using an implementation of our algorithm in Java. The implementation, case studies, and synthetic policies used in the experiments are available at http://www.cs.stonybrook.edu/ ~stoller/.

Over-Assignment Weight. The optimal choice for the over-assignment weights w o and w o in the policy quality and rule quality metrics, respectively, depends on the log completeness. When log completeness is higher, fewer over-assignments are desired, and larger over-assignments weights give better results. In experiments, we take w o = 50c -15 and w o = w o /10, where c is log completeness. In a production setting, the exact log completeness would be unknown, but a rough estimate suffices, because our algorithm's results are robust to error in this estimate. For example, for case studies with manually written attribute data, when the actual log completeness is 80%, and the estimated completeness used to compute w o varies from 70% to 90%, the semantic similarity of the original and mined policies varies by 0.04, 0.02, and 0 for university, healthcare, and project management, respectively. Experimental Results. Figure 4 shows results from our algorithm. In each graph, curves are shown for the university, healthcare, and project management case studies with synthetic attribute data with N equal to 6, 10, and 10, respectively (average over results for 10 synthetic datasets, with 1 synthetic log per synthetic dataset), the online video case study with manually written attribute data (average over results for 10 synthetic logs), and synthetic policies with N rule = 20 (average over results for 10 synthetic policies, with 1 synthetic log per policy). Error bars show standard deviation. Running time is at most 12 sec for each problem instance in our experiments.

For log completeness 100%, all four case study policies are reconstructed exactly, and the semantics of synthetic policies is reconstructed almost exactly: the semantic similarity is 0.98. This is a non-trivial result, especially for the case studies: an algorithm could easily generate a policy with over-assignments or generate more complex rules. As expected, the results get worse as log completeness decreases. When evaluating the results, it is important to consider what levels of log completeness are likely to be encountered in practice. One datapoint comes from Molloy et al.'s work on role mining from real logs [START_REF] Molloy | Generative models for access control policies: applications to role mining over logs with attribution[END_REF]. For the experiments in [6, Tables 4 and6], the actual policy is not known, but their algorithm produces policies with 0.52% or fewer over-assignments relative to UP (L), and they interpret this as a good result, suggesting that they consider the log completeness to be near 99%. Based on this, we consider our experiments with log completeness below 90% to be severe stress tests, and results for log completeness 90% and higher to be more representative of typical results in practice.

Syntactic similarity for all four case studies is above 0.87 for log completeness 60% or higher, and is above 0.93 for log completeness 80% or higher. Syntactic similarity is lower for synthetic policies, but this is actually a good result. The synthetic policies tend to be unnecessarily complicated, and the mined policies are better in the sense that they have lower WSC. For example, for 100% log completeness, the mined policies have 0.98 semantic similarity to the synthetic policies (i.e., the meaning is almost the same), but the mined policies are simpler, with WSC 17% less than the original synthetic policies.

Semantic similarity is above 0.7 for log completeness 60% or higher, and above 0.89 for log completeness 80% or higher, for synthetic policies and for case studies other than healthcare. The semantic similarity is lower for healthcare, because the over-assignment weight given by the above formula is not optimal for this policy. In fact, if the optimal value of w o is used for each log completeness, the semantic similarity for healthcare is always above 0.99. Better automated tuning of w o is a direction for future work. The fractions of over-assignments and under-assignments are below 0.24 and 0.05, respectively, when log completeness is 80% or higher, for synthetic policies and for case studies other than healthcare. The fractions are higher for healthcare, because w o is not well chosen, as discussed above.

Comparison of Rule Quality Metrics. The above experiments use the first rule quality metric, Q rul , in Section 4. We also performed experiments using Q freq rul and Q ILP rul on case studies with manually written attribute data and synthetic policies. We found that there is no clear winner between Q rul and Q freq rul (sometimes one is better, sometimes the other is better), and Q ILP rul gives worse results overall.

Comparison with Inductive Logic Programming. To translate ABAC policy mining from logs to Progol [START_REF] Muggleton | CProgol4.4: a tutorial introduction[END_REF], we used the translation of ABAC policy mining from ACLs to Progol in [10, Sections 5.5, 16], except negative examples corresponding to absent user-permission tuples are omitted from the generated program, and the statement set(posonly)? is included, telling Progol to use its algorithm for learning from positive examples. For the four case studies with manually written attribute data (in contrast, Figure 4 uses synthetic attribute for three of the case studies), for log completeness 100%, semantic similarity of the original and Progol-mined policies ranges from 0.37 for project management and healthcare to 0.93 for online video, while our algorithm exactly reconstructs all four policies.

Related Work

We are not aware of prior work on ABAC mining from logs. The closest topics of related work are ABAC mining from ACLs and role mining from logs.

ABAC Policy Mining from ACLs

Our policy mining algorithm is based on our algorithm for ABAC policy mining from ACLs [START_REF] Xu | Mining attribute-based access control policies[END_REF]. The main differences are described in Section 1.

Ni et al. investigated the use of machine learning algorithms for security policy mining [START_REF] Ni | Automating role-based provisioning by learning from examples[END_REF]. In the most closely related part of their work, a supervised machine learning algorithm is used to learn classifiers (analogous to attribute expressions) that associate users with roles, given as input the users, the roles, user attribute data, and the user-role assignment. Perhaps the largest difference between their work and ABAC policy mining is that their approach needs to be given the roles and the role-permission or user-role assignment as training data; in contrast, ABAC policy mining algorithms do not require any part of the desired high-level policy to be given as input. Also, their work does not consider anything analogous to constraints and does not attempt to optimize the size or readability of the generated policy.

Association rule mining is another possible basis for ABAC policy mining. However, association rule mining algorithms are not well suited to ABAC mining, because they are designed to find rules that are probabilistic in nature and are supported by statistically strong evidence. They are not designed to produce a set of rules that are strictly satisfied, that completely cover the input data, and are minimum-sized among such sets of rules. Consequently, unlike our algorithm, they do not give preference to smaller rules or rules with less overlap.

Role Mining from Logs

Gal-Oz et al. [START_REF] Gal-Oz | Mining roles from web application usage patterns[END_REF] assume that logs record sets of permissions exercised together in one high-level operation. Their role mining algorithm introduces roles whose sets of assigned permissions are the sets of permissions in the log. Their algorithm introduces over-assignments by removing roles with few users or whose permission set occurs few times in the log and re-assigning their members to roles with more permissions. Their algorithm does not use attribute data.

Molloy et al. apply a machine learning algorithm that uses a statistical approach, based upon a generative model, to find the policy that is most likely to generate the behavior (usage of permissions) observed in the logs [START_REF] Molloy | Generative models for access control policies: applications to role mining over logs with attribution[END_REF]. They give an algorithm, based on Rosen-Zvi et al.'s algorithm for learning Author-Topic Models (ATMs), to mine meaningful roles from logs and attribute data, i.e., roles such that the user-role assignment is statistically correlated with user attributes. Their approach can be adapted to ABAC policy mining from logs, but its scalability in this context is questionable, because the adapted algorithm would enumerate and then rank all tuples containing a UAE, RAE and constraint (i.e., all tuples with the components of a candidate rule other than the operation set), and the number of such tuples is very large. In contrast, our algorithm never enumerates such candidates.

Zhang et al. use machine learning algorithms to improve the quality of a given role hierarchy based on users' access patterns as reflected in operation logs [START_REF] Zhang | Role prediction using electronic medical record system audits[END_REF][START_REF] Zhang | Evolving role definitions through permission invocation patterns[END_REF]. These papers do not consider improvement or mining of ABAC policies.

  r, o |= ρ}. Note that U , R, d u , and d r are implicit arguments to [[ρ]].

Fig. 1 .Fig. 2 .

 12 Fig. 1. Policy mining algorithm. The pseudocode starts in column 1 and continues in column 2. function addCandRule(su, sr, so, cc, uncovUP , Rules) // Construct a rule ρ that covers user-perm. tuples { u, r, o | u ∈ su ∧ r ∈ sr ∧ o ∈ so}. eu = computeUAE(su, U ); er = computeRAE(sr, R); ρ = eu, er, so, ∅ ρ = generalizeRule(ρ, cc, uncovUP , Rules); Rules.add(ρ ); uncovUP .removeAll([[ρ ]]) Fig. 2. Compute a candidate rule ρ and add ρ to candidate rule set Rules

Fig. 3 .

 3 Fig. 3. Left: Generalize rule ρ by adding some formulas from cc to its constraint and eliminating conjuncts for attributes used in those formulas. f [x → y] denotes a copy of function f modified so that f (x) = y. a[i..] denotes the suffix of array a starting at index i. Right: Merge pairs of rules in Rules, when possible, to reduce the WSC of Rules. (a, b) denotes an unordered pair with components a and b. The union e = e1 ∪ e2 of attribute expressions e1 and e2 over the same set A of attributes is defined by: for all attributes a in A, if e1(a) = or e2(a) = then e(a) = otherwise e(a) = e1(a) ∪ e2(a). noOA(ρ) holds if ρ has no over-assignments, i.e., [[ρ]] ⊆ UP 0.

  Syntactic similarity of UAEs is defined by S u syn (e, e ) = |A u | -1 a∈Au J(e(a), e (a)). Syntactic similarity of RAEs is defined by S r syn (e, e ) = |A r | -1 a∈Ar J(e(a), e (a)). The syntactic similarity of rules e u , e r , O, c and e u , e r , O , c is the average of the similarities of their components, specifically, the average of S u syn (e u , e u ), S r

Fig. 4 .

 4 Fig. 4. Top: Syntactic similarity and semantic similarity of original and mined ABAC policies, as a function of log completeness. Bottom: Fractions of over-assignments and under-assignments in mined ABAC policy, as a function of log completeness. The legend (omitted from some graphs to save space) is the same for all four graphs.

  Rules is the set of candidate rules Rules = ∅ // uncovUP contains user-permission tuples // in UP 0 that are not covered by Rules uncovUP = UP 0.copy() while ¬uncovUP .isEmpty() // Select an uncovered tuple as a "seed". u, r, o = some tuple in uncovUP cc = candidateConstraint(r, u) // su contains users with permission r, o // and that have the same candidate // constraint for r as u su = {u ∈ U | u , r, o ∈ UP 0 ∧ candidateConstraint(r, u ) = cc} addCandRule(su, {r}, {o}, cc, uncovUP , Rules) // so is set of operations that u can apply to r so = {o ∈ Op | u, r, o ∈ UP 0} addCandRule({u}, {r}, so, cc, uncovUP , Rules) Repeatedly move highest-quality rule from Rules to Rules until ρ∈Rules [[ρ]] ⊇ UP 0, using UP 0 \ [[Rules ]] as second argument to Q rul , and discarding a rule if it does not cover any tuples in UP 0 currently uncovered by Rules . return Rules

	// Repeatedly merge and simplify
	// rules, until this has no effect
	mergeRules(Rules)
	while simplifyRules(Rules)
	&& mergeRules(Rules)
	skip
	end while
	// Select high quality rules into Rules .
	Rules = ∅
	end while

//

  Find rules that become redundant // if merged rule ρmrg is added redun = {ρ ∈ Rules | [[ρ]] ⊆ [[ρmrg]]} // Add the merged rule and remove redun-// dant rules if this improves policy quality // and does not introduce over-assignments. // where none existed before.

	function generalizeRule(ρ, cc, uncovUP ,	function mergeRules(Rules)
	Rules)	// Remove redundant rules
	// ρ best is best generalization of ρ	redun = {ρ ∈ Rules | ∃ ρ ∈ Rules \ {ρ}.
	ρ best = ρ	[[ρ]] ∩ UP 0 ⊆ [[ρ ]] ∩ UP 0}
	// gen[i][j] is a generalization of ρ using	Rules.removeAll(redun)
	// cc [i]	// Merge rules
	gen = new Rule[cc.length][3]	workSet = {(ρ1, ρ2) | ρ1 ∈ Rules ∧ ρ2 ∈ Rules
	for i = 1 to cc.length	∧ ρ1 = ρ2 ∧ con(ρ1) = con(ρ2)}
	f = cc[i]	while not(workSet.empty())
	// generalize by adding f and eliminating	(ρ1, ρ2) = workSet.remove()
	// conjuncts for both attributes used in f .	ρmrg = uae(ρ1) ∪ uae(ρ2),
	gen[i][1] = uae(ρ)[uAttr(f ) → ],	rae(ρ1) ∪ rae(ρ2),
	rae(ρ)[rAttr(f ) → ],	ops(ρ1) ∪ ops(ρ2), con(ρ1)
	ops(ρ), con(ρ) ∪ {f } // generalize by adding f and eliminating // conjunct for user attribute used in f gen[i][2] = uae(ρ)[uAttr(f ) → ], rae(ρ), ops(ρ), con(ρ) ∪ {f } // generalize by adding f and eliminating // conjunct for resource attrib. used in f .	// Rules.add(ρmrg)
	uncovUP )	end if
	ρ best = ρ	end while
	end if	return true if any rules were merged
	end for
	return ρ best

gen[i]

[START_REF] Hachana | Role mining to assist authorization governance: How far have we gone[END_REF]

= uae(ρ), rae(ρ)[rAttr(f ) → ], ops(ρ), con(ρ) ∪ {f } end for for i = 1 to cc.length and j = 1 to 3 // try to further generalize gen

[i] ρ = generalizeRule(gen[i][j], cc[i+1 ..], uncovUP , Rules) if Q rul (ρ , uncovUP ) > Q rul (ρ best , if Q pol (Rules ∪ {ρmrg} \ redun) < Q pol (Rules) ∧ (noOA(ρ1) ∧ noOA(ρ2) ⇒ noOA(ρmrg)) Rules.removeAll(redun) workSet.removeAll({(ρ1, ρ2) ∈ workSet | ρ1 ∈ redun ∨ ρ2 ∈ redun}) workSet.addAll({(ρmrg, ρ) | ρ ∈ Rules

∧ con(ρ) = con(ρmrg)})

This material is based upon work supported in part by NSF under Grant CNS-0831298.


Emmanuel Hermellin
email: emmanuel.hermellin@lirmm.fr

Fabien Michel
email: fmichel@lirmm.fr

GPU Environmental Delegation of Agent Perceptions: Application to Reynolds's Boids

Keywords: Multi-Agent Based Simulation, Flocking, GPGPU, CUDA

Using Multi-Agent Based Simulation (MABS), computing resources requirements often limit the extent to which a model could be experimented with. Regarding this issue, some research works propose to use the General-Purpose Computing on Graphics Processing Units (GPGPU) technology. GPGPU allows to use the massively parallel architecture of graphic cards to perform general-purpose computing with huge speedups. Still, GPGPU requires the underlying program to be compliant with the specific architecture of GPU devices, which is very constraining. Especially, it turns out that doing MABS using GPGPU is very challenging because converting Agent Based Models (ABM) accordingly is a very difficult task. In this context, the GPU Environmental Delegation of Agent Perceptions principle has been proposed to ease the use of GPGPU for MABS. This principle consists in making a clear separation between the agent behaviors, managed by the CPU, and environmental dynamics, handled by the GPU. For now, this principle has shown good results, but only on one single case study. In this paper, we further trial this principle by testing its feasibility and genericness on a classic ABM, namely Reynolds's boids. To this end, we first review existing boids implementations to then propose our own benchmark model. The paper then shows that applying GPU delegation not only speeds up boids simulations but also produces an ABM which is easy to understand, thanks to a clear separation of concerns.

Introduction

Because Multi-Agent Based Simulation (MABS) can be composed of many interacting entities, studying their properties using digital simulation may require a lot of computing resources. To deal with this issue, the use of General-Purpose computing on Graphics Processing Units (GPGPU) can drastically speed up simulation runs for a cheap cost [START_REF] Lysenko | A Framework for Megascale Agent Based Model Simulations on Graphics Processing Units[END_REF]. GPGPU relies on using the massively parallel architectures of usual graphic cards to perform general-purpose computing. However, this technology implies a very specific programming scheme which requires advanced GPU (Graphics Processing Unit) programming skills [START_REF] Owens | A Survey of General-Purpose Computation on Graphics Hardware[END_REF].

Because there are many different MAS (Multi-Agent Systems) models, there is no generic way for implementing MAS using GPGPU. It is not about only changing of programming language. With GPGPU, many concepts which are present in sequential programming are no longer available. Especially, important features of object-oriented languages simply cannot be used (inheritance, composition, etc.). So, it is very difficult to adapt an Agent Based Model (ABM) so that it can be run on the GPU. Considering this issue, hybrid systems represent an attractive solution. Because the execution of the MAS is shared between the Central Processing Unit (CPU) and the GPU, it is thus possible to select only what is going to be translated and executed by the graphics card.

In this paper, we propose to challenge the feasibility and interest of the GPU Environmental Delegation of Agent Perceptions (GPU Delegation for short) principle which is based on an hybrid approach. This principle consists in identifying and delegating to the environment some of the computations made by the agents. A case study is presented in [START_REF] Michel | Translating Agent Perception Computations into Environmental Processes in Multi-Agent-Based Simulations: A means for Integrating Graphics Processing Unit Programming within Usual Agent-Based Simulation Platforms[END_REF] and shows good results in terms of performances, accessibility and reusability. We propose to trial this principle by using it on a classic ABM, namely Reynolds's boids [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF].

In Sect. 2 we review how Reynolds's Boids is implemented in several MABS platforms and then propose our own flocking model in Sect. [START_REF] Grignard | GAMA 1.6: Advancing the Art of Complex Agent-Based Modeling and Simulation[END_REF]. Section 4 presents the GPU Environmental Delegation of Agent Perceptions principle. In Sect. 5, we describe the implementation of our model and how we have applied GPU Delegation on it. In Sect. 6, we present and discuss the results of our tests. Finally, we conclude and present perspectives in Sect. 7.

Reynolds's Boids

Original Model Overview

Reynolds was interested in achieving a believable animation of a flock of artificial birds and remarked that it was not possible to use a scripted flock motion. That is why Reynolds proposed an ABM based on local individual rules, namely boids [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]. Reynolds's idea was that boids have to be influenced by the others to flock in a coherent manner: "Boid behavior is dependant not only on internal state but also on external state.".

Reynolds proposes that each agent is subjected to forces that make it move by taking into account the interactions with the others. So, each entity has to follow three behavior rules:

-R.1 Collision Avoidance: Avoid collisions with nearby flockmates -R.2 Flock Centering: Attempt to stay close to nearby flockmates -R.3 Velocity matching: Attempt to match velocity with nearby flockmates Reynolds's boids is recognized as one of the most representative ABM and many agent-based platforms integrate their own boids model.

Boids in Current MABS Platforms

In this section, we compare several implementations of Reynolds's boids that we can find in popular MABS platforms. Among the related works found, we only introduce models we were able to download and try with an open source code: NetLogo, StarLogo, Gama, Mason and Flame GPU. For each model, we describe how the three rules are implemented (Collision Avoidance (R.1), Flock Centering (R.2), Velocity matching(R.3)).

NetLogo In NetLogo1 [START_REF] Sklar | NetLogo, a Multi-agent Simulation Environment[END_REF], all the agents move and try to get closer to their peers. If the distance between them and the nearest neighbor is too small, the agent tries to get away (avoid collision (R.1)), otherwise the agent aligns with its neighbors (R.2). However, there is no speed management (R.3): All the agents have the same velocity during the entire simulation.

StarLogo In StarLogo2 [START_REF] Resnick | StarLogo: An Environment for Decentralized Modeling and Decentralized Thinking[END_REF], the agent searches for his closest neighbor. If the distance to his peer is too small, then the agent turns and gets away to avoid collision (R.1). Otherwise, it moves toward him and use his direction. The search for cohesion (R.2) is not explicitly expressed and the velocity of the agents is fixed throughout the simulation (R.3).

Gama In Gama3 [START_REF] Grignard | GAMA 1.6: Advancing the Art of Complex Agent-Based Modeling and Simulation[END_REF], agents first look for a virtual target to follow (a moving object in the environment that initiates the flocking behavior). Once the agents have a target, they move according to three functions that implement Reynolds's rules: A separation function to avoid collision (R.1), a cohesion function (R.2) and an alignment function for speed and direction (R.3). The model differs from Reynolds's because the agents need a target to actually make the flocking.

MasOn MasOn4 [START_REF] Luke | MASON: A Multiagent Simulation Environment[END_REF] uses the computation of several vectors to integrate R.1 and R.2. Each agent computes a motion vector composed of an avoidance vector (this is computed as the sum, over all neighbors, of a vector to get away from the neighbors (R.1)), a cohesion vector (this is computed as the sum, over all live neighbors, of a vector towards the "center of mass" of nearby flockers), a momentum vector (a vector in the direction the flocker went last time), a coherence vector (this is computed as the sum, over all live neighbors, of the direction of other flockers are going (R.2)), and a random vector. The velocity is not managed in this model (R.3).

Flame GPU Flame GPU5 [START_REF] Richmond | High performance cellular level agent-based simulation with FLAME for the GPU[END_REF] is the only GPGPU implementation that we were able to test. In this model, R.1 R.2 and R.3 are actually implemented into three independent functions. Summary Table 1 summarizes the implementations of Reynolds's rules, sets out the main features of the models and gives performance informations.

Performances

We evaluate for each model the average computation time in milliseconds for an iteration. The purpose of this evaluation is to give an idea of the possibilities of each implementation. So, we use as common parameter an environment of 512 x 512 containing 4000 agents. Our test configuration is composed of an Intel i7-4770 processor (Haswell generation, 3.40 GHz) and an Nvidia K4000 graphics card (768 CUDA cores).

It has to be noted that for StarLogo, we observed a computation time higher than a second from 400 simulated agents so that we did not push the tests further. Finally, for Flame GPU, it was not possible to modify the number of agents in the simulation which is of 2048.

Reynolds's Boids: Our Model and Implementation

From the previous study, we notice disparities between the various presented models. Indeed, Reynolds's rules allow a large variety of interpretations. For instance, we notice that the speed adaptation rule (R.3) is not always taken into account compared to R.1 and R.2 which are implemented in almost every model (except StarLogo). However, when R.3 is implemented, the collective behavior becomes much more convincing in terms of flocking dynamics and movement believability. Also, in some works, alignment and cohesion behaviors are merged.

The models clarifying the difference between this two behaviors offer more interesting movements.

The model that we propose takes into account the points observed previously: Overall, when the three rules are explicitly considered, the dynamics and the movement of the agents are more convincing. So, our model integrates R.1, R.2 and R.3 and also follows the KISS (Keep It Simple and Stupid) principle in the aim of creating a minimalist version (with as few parameters as possible). So the model focuses only on the speed and the orientation of the agent 6 .

Each entity has a global behavior which consists in moving while adapting its speed and direction. To this end, the proximity with the other agents is first tested and then Reynolds's rules are triggered accordingly. More specifically, every agent first looks in its vicinity. If no agent is present, then it continues to move in the same direction. Otherwise, the agent checks if the neighbors are not too close. Depending on the proximity between entities, agents separate (R.1), align with other entities or create cohesion (R.2). Then agents adapt their speed (R.3), move and restart the process. Figure 1 summarizes the global behavior process. -fieldOfView (agent's field of view); -minimalSeparationDistance (minimum distance between agents); -cohesionThreshold (necessary number of agents to begin cohesion); -maximumSpeed (maximum speed of the agent); -maximumRotation (maximum angle of rotation).

The attributes specific to each agent are the following ones:

heading (agent's heading); velocity (agent's speed); -nearestNeighborsList (the list containing nearest neighbors).

Separation Behavior R.1 When an agent is too close from another one, it separates (R.1). This behavior consists in retrieving the heading of both agents. If these two directions lead to a collision, agent rotates to avoid its neighbor (see Algorithm 1). its neighbors. If the agent has just executed the behavior of separation (R.1), it accelerates to get free more quickly. Otherwise, the agent adjusts its speed to make it correspond to that of its neighbors (in the limit authorized by the maximumSpeed constant).

Testing Our Model We have put online a set of videos that show our model in action 7 . On this page are also available the source codes of the mentioned models and the resources required to test our solution.

GPU Environmental Delegation of Agent Perceptions

MABS and GPGPU

GPGPU Basics For the purpose of understanding the basics of GPGPU programming, one has to have in mind that it is strongly connected to the underlying hardware architecture of GPU. In this respect, one of the main differences between a CPU and a GPU is the number of processing cores which is far more important in the GPU case.

Today, GPU are composed of hundreds or thousands of processing core (grouped into Streaming Multiprocessors, SM) forming a highly parallel structure able to perform more varied computing. GPGPU relies on using the SIMD (Single Instruction, Multiple Data) parallel model. Also called stream processing, the underlying programming approach consists in performing the same operation on multiple data points simultaneously. In other words, GPGPU relies on the simultaneous execution of a series of computations (kernels) on a data set (the flow -stream).

The related programming models rely on the following work flow: The CPU is called the host and plays the role of scheduler. The host manages data and triggers kernels, which are functions specifically designed to be executed by the GPU, which is called the device. The GPU part of the code really differs from sequential code and has to fit the underlying hardware architecture. More precisely, the GPU device is programmed to proceed the parallel execution of the same procedure, the kernel, by means of numerous threads. These threads are organized in blocks (the parameters blockDim.x, blockDim.y characterize the size of these blocks), which are themselves structured in a global grid of blocks. Each thread has unique 3D coordinates (threadIdx.x, threadIdx.y, threadIdx.z ) that specifies its location within a block. Similarly, each block also has three spatial coordinates (respectively blockIdx.x, blockIdx.y, blockIdx.z ) that localize it in the global grid. Figure 2 illustrates this organization for the 2D case. So, each thread works with the same kernel but uses different data according to its spatial location within the grid8 . Moreover, each block has a limited thread capacity according to the hardware in use. So, a multithreaded program is partitioned into blocks of threads that execute independently from each other. The distribution of blocks and threads on SM may be automatic and is provided by the runtime and drivers. For instance, in the GPGPU platform from Nvidia (Compute Unified Device Architecture, CUDA), a CUDA program can be executed on any number of multiprocessors as illustrated by Fig. 3, and only the runtime system needs to know the physical multiprocessor count.

Implementing MABS Using GPGPU There are two ways of implementing a model on GPU: (1) all-in-GPU, for which the simulation runs entirely on the graphics card and (2) hybrid, the execution of the simulation is shared between the CPU and the GPU. In the first case (1), it is not trivial to take an existing model and translate it to make it work on GPU. GPU are very restrictive in operations and programming and the hardware can only be used in certain ways that requires advanced GPU programming skills. The hybrid approach (2) allows to use jointly the CPU and GPU and thus has two major advantages. Firstly, it brings more flexibility because one can choose what is going to be executed on the GPU, thus providing greater accessibility to the developed tools (as clearly shown in [START_REF] Laville | Using GPU for Multi-agent Multi-scale Simulations[END_REF] [5], [START_REF] Sano | A Performance Optimization Support Framework for GPU-based Traffic Simulations with Negotiating Agents[END_REF], [START_REF] Vigueras | A GPU-Based Multi-agent System for Real-Time Simulations[END_REF]). Secondly, as hybrid systems are modular by design, they make it possible to use agents with complex and heterogeneous architectures. The GPU Environmental Delegation of Agent Perceptions principle relies on an hybrid approach.

Converting Agent Perceptions in Environmental Dynamics

The Principle GPU Environmental Delegation of Agent Perceptions principle was proposed in [START_REF] Michel | Translating Agent Perception Computations into Environmental Processes in Multi-Agent-Based Simulations: A means for Integrating Graphics Processing Unit Programming within Usual Agent-Based Simulation Platforms[END_REF]. This principle consists in making a clear separation between the agent behaviors, managed by the CPU, and environmental dynamics, handled by the GPU. The underlying idea is to identify in the behavior of the agents some computations which can be transformed into environmental dynamics. It has been first stated as follows: Any agent perception computation not involving the agents state could be translated to an endogeneous dynamic of the environment, and thus considered as a potential GPU environment module.

Related Works GPU delegation has to be related to other works which reify parts of the agents' computations in structures related to other concepts such as the interactions or the environment.

In the MABS context, the EASS (Environment As Active Support for Simulation) [START_REF] Badeig | A contextual environment approach for multiagent-based simulation[END_REF] approach aims at strengthening the role of the environment by delegat-ing to it the scheduling policy and adding a filtering system for the perceptions. IODA (Interaction Oriented Design of Agent simulations) [START_REF] Kubera | IODA: an interaction-oriented approach for multi-agent based simulations[END_REF] is centered on the notion of interaction and considers that agent behaviors can be described in a abstract way as a rule called interaction. [START_REF] Payet | Environment as support for simplification, reuse and integration of processes in spatial MAS[END_REF] proposes to reduce the complexity of the models by using an environment-centered approach: Some agent interaction patterns are modeled as environmental dynamics to ease the reusability and the integration of various agent processes.

GPU Delegation on a Case Study

The integration of GPU computations was performed in TurtleKit9 [START_REF] Michel | The TurtleKit Simulation Platform: Application to Complex Systems[END_REF]. TurtleKit is a generic spatial ABM, implemented with Java, wherein agents evolve in a 2D environment discretized in cells. The proposed hybrid approach integrated in TurtleKit focuses on modularity. In this context, this allows to achieve three objectives: (1) maintain accessibility in the agent model while using GPGPU, (2) to scale and work with a large number of agents on large environment sizes and (3) promote re-usability in the particular context of GPU programming.

GPU Delegation has been used only once on a model of multi-level emergence (MLE) [START_REF] Beurier | Model and Simulation of Multi-Level Emergence[END_REF] of complex structures in TurtleKit. This very simple model relies on a unique behavior which allows to generate complex structures which repeat in a fractale way. The agent behavior is extremely simple and is based on the perception, the spread and the reaction to pheromones. So, in these works, GPU modules dedicated to the perception and the spread of pheromones were proposed.

GPU Delegation for Boids

Applying GPU Delegation

With respect to the underlying hybrid approach, GPU Delegation is about identifying specific behaviors which can be turned into environmental dynamics. Especially, GPU Delegation states that agent perception computations that do not involve the agents state could be translated into environmental dynamics. For instance, in the previous case study (MLE), the computation related to the agent perceptions used to decide how the agents move according to pheromones (i.e. following gradients) is completely independent from the agents' state: Gradients are equals whatever the agents' states. So a GPU module (environmental dynamics) has been produced for computing pheromones gradients independently from the agents.

In our flocking model, it has not been possible to find a computation which is independent from the agents' attributes. However, we actually identified some computations that can be done without modifying the agent's state so that they can be thus translated into an environmental dynamics computed by the GPU. Indeed, the cohesion behavior consists in averaging the orientations of neighboring agents according to the selected FieldOfView10 . All the agents perform this computation in their own behavior and use the result to adapt their direction. The sequential implementation of this process is as follows: This loop is very costly when there is a large number of agents because they all perform this computation for each step of the simulation.

Designing the Average GPU Module

To achieve GPU translation for the previous computation, we extract information from agents' attributes (heading) and then delegate the associated computation (the loop) to the environment dynamics. To this end, for each simulation step, each agent put its heading value in a 2D array (headingArray (a grid matching the size of the environment) according to its position. This array is sent to a GPU module (average module) that simultaneously, for each cell within the FieldOfView, performs the average of the headings of the surrounding agents. More precisely, each thread computes the average for a cell depending on its location in the global GPU grid (its identifiers: i and j in Algorithm 5). The GPU translation thus consists in transforming the sequential computation previously done in the cohesion behavior of the agents into a parallel computation made on the GPU and managed by the environment. Once done, the average headings are available in every cells of the environment. So, the agents can access this data instantaneously with respect to their position (from the 2D array, flockCentering, returned by the GPU module) and then adapt their movement accordingly.

Algorithm 5 presents an implementation of the GPU average module: Once the coordinates i and j of the thread are initialized, the algorithm tests if the current thread 's coordinates do not exceed the size of the environment (represented here by the 2D array headingArray). Next, the sum of all the headings are assigned to sumOfheading, which is then divided by the number of agents taken into account. The module then returns the array flockCentering containing all the averages. Compared with the sequential version (Algorithm 4, the loop has disappeared. So, one of the main interest of the GPU version lies in the fact that the parallelization of the loop is realized thanks to the hardware architecture, not through code parallelization: Programming with GPU, parts of the code are in the structure.

Implementation and Integration of the GPU Average Module

The implementation of the GPU average module has been done with CUDA and JCuda 11 . Figure 4 illustrates the integration of the GPU average module in TurtleKit. The implementation was easy thanks to the independence between this module and the agent model.

Experimental Protocol

To trial our implementation of Reynolds's boids and the application of GPU delegation, we simulated several environment sizes while varying the number of agents. We execute successively the sequential version of the model (i.e. the average is computed in the agents' behavior) then the GPGPU version (using the GPU average module). To estimate the performances according to the criteria used in section 2, we compare the average computation time in milliseconds for an iteration.

Performance Tests

For those tests, the configuration is identical as the one used in Sect. 2 and is composed of an Intel i7-4770 processor (Haswell generation, 3.40 GHz) and an Nvidia K4000 graphics card (768 CUDA cores). Figure 5 presents the results obtained for various population sizes in an 256 x 256 environment (top) and then in an 512 x 512 environment (bottom). The use of the GPU module increases the performances by 25%. However, we notice that the performances is linked to the density of population. Indeed, when the density of the agents in the environment is lower, agents spend fewer time in cohesion and more to align itself and to separate. The density of the agents affects performance of the model when using the GPU module. The tipping point is clearly visible in the results, when the density of present agents exceeds 5% (respectively 1500 and 8000 entities), the joint use of the CPU and the GPU becomes more effective. So, the more the density of agents in the environment increases, more the observed gains of performances are important.

The performance gains are interesting considering the used hardware: Our Nvidia K4000 embeds 768 CUDA cores while the last Nvidia Tesla K40 card embeds 2880 CUDA cores and the Nvidia Tesla K10 card embeds 3072 cores (two GPU with 1536 cores on the same card). The fast evolution of GPGPU and graphics cards promise very significant gains of performances in the future.

Discussion

In addition to the observed performance gains, we noticed other benefits related to GPU Delegation principle: Translating perception computations done in the agent behavior into environmental dynamics allows to remove a part of the source code and thus simplify the understanding of the behavior. It is more readable because the agent does not have to deal with raw data. Indeed, the agent makes a direct perception in the environment instead of a sequential computation which can be rather heavy.

Another interesting aspect is that the created modules are independent from the considered ABM thanks to this approach. They are thus not limited to the context in which they were defined. That is why we will continue to apply GPU Delegation to create new GPU modules in order to incrementally build a generic GPU modules library. This GPU library will improve the accessibility of the approach and the use of the GPGPU in the MABS context with TurtleKit. This improvement in terms of genericness and accessibility is important because working with GPGPU often leads to implementation difficulties due to the specificity of this technology.

Moreover, GPU delegation is based on a simple criterion which is independent from the implementation. So, GPU delegation allows to convert the model and create the GPU module easily in a rather fast way. TurtleKit being still in alpha release, we are going to continue to work on its architecture in order to make the conversion of a model as simple as possible.

Conclusion and Perspectives

In this paper, we described how we used the GPU Environmental Delegation of Agent Perceptions principle to implement a classic ABM, namely Reynolds's Boids, using GPGPU. Our purpose was to challenge the genericness and the ease-of-use of GPU Delegation. To this end, we needed to evolve GPU delegation so that it can be applied to the boids model. Indeed, find a computation independent from agents' attributes was impossible, so we have identified in the cohesion behavior some computations independent of agent's behaviors. We thus translated these computations into a GPU module and made some tests to see the advantages brought by the GPU Delegation.

Our experiments show that, using GPU Delegation, it is possible to increase the size of the environments and the number of agents thanks to a speed up which can reach 25% according to the chosen parameters.

From a software engineering perspective, the use of GPU delegation allows to consider important aspects of MABS with respect to the GPGPU context. By promoting a clear separation between the agent behaviors (handled by the CPU) and environmental dynamics (managed by the GPU), GPU Delegation represents a design guideline which (1) allows to tackle the genericness issue and (2) promotes reusability of created tools. This essential criterion is often neglected in the GPGPU context [START_REF] Michel | Translating Agent Perception Computations into Environmental Processes in Multi-Agent-Based Simulations: A means for Integrating Graphics Processing Unit Programming within Usual Agent-Based Simulation Platforms[END_REF]. GPU delegation allows the creation of generic GPU modules which are independent from the agent models.

Both implementations of the delegation principle, realized with MLE in [START_REF] Michel | Translating Agent Perception Computations into Environmental Processes in Multi-Agent-Based Simulations: A means for Integrating Graphics Processing Unit Programming within Usual Agent-Based Simulation Platforms[END_REF] and flocking here, show that if the analysis of the model is made by keeping in mind the characteristics of the approach, the delegation of the computations and the creation of the GPU module could be very easy and fast, which is a valuable aspect of GPU Delegation, especially considering the technical difficulties related with the GPGPU context.

As GPU delegation still requires specific skills, we plan to apply to other models this principle in order to experiencing and continuing to generalize the approach. Then, as a long term perspective, our goal is to propose an explicit design methodology that would provide any MABS end user with a simple and efficient means for addressing scalability issues, without compromising reusability and accessibility which are major issues for the adoption of this technology in the MABS community.

Fig. 1 .

 1 Fig. 1. Flocking: Global behavior process

Fig. 2 .

 2 Fig. 2. Thread, blocks, grid organization

Fig. 3 .

 3 Fig. 3. Automatic Scalability (Source: Nvidia programming guide)

Algorithm 4 :

 4 Computing the average of surroundings agents' heading for bird in nearestN eighborsList do sumOf Heading+ = getHeading(bird); end neighborsAverageHeading = sumOf Heading/sizeOf (nearestN eighborsList) ;

Algorithm 5 :

 5 Average Kernel input : width, height, f ieldOf V iew, headingArray and nearestN eighborsList output: f lockCentering (the average of directions) 1 i = blockIdx.x * blockDim.x + threadIdx.x ; 2 j = blockIdx.y * blockDim.y + threadIdx.y ; 3 sumOf Heading, f lockCentering = 0 ; 4 if i < width and j < height then 5 sumOf Heading = getHeading(f ieldOf V iew, headingArray[i, j]); 6 end 7 f lockCentering[i, j] = sumOf Heading/sizeOf (nearestN eighborsList) ;

Fig. 4 .

 4 Fig. 4. Integrating the GPU Average module in TurtleKit

Fig. 5 .

 5 Fig. 5. Comparison of flocking simulations done with and without the GPU. Environment size: 256 (top) and 512 (bottom)

Table 1 .

 1 Boids in common MABS platforms

		Compliance with Reynolds's
	Platform		Model		Main characteristics	Performances
		Collision R.1 Cohesion R.2 Velocity R.3
	NetLogo	X	X		R.3 is not implemented: Velocity is fixed	214 ms (CPU / Logo)
					throughout the simulation
	StarLogo	X			A minimalist implementation of behavior	*1000 ms (CPU / Logo)
					rules (only the collision avoidance is im-
					plemented)
	Gama	X	X	X	Flocking behaviour when agents have a	375 ms (CPU / GAML)
					target to follow
	MasOn	X	X		The rules R.1 and R.2 are reinterpreted	45 ms (CPU / Java)
					into a global vector with addition of ran-
					dom components, no speed management
	Flame GPU	X	X	X	The three rules are explicitly implemented *82ms (GPU / C,XML)

  When an agent comes closer to other entities, it tries to align itself with them, by adjusting his direction according to its nearest neighbor (see Algorithm 2). When multiple agents are close to each other without having to separate, they have a cohesion behavior. Each agent retrieves the directions of its neighbors and adjusts its own direction based on the average direction found, thus strengthening the cohesion of the group (see Algorithm 3).

	Algorithm 3: Cohesion behavior
		input : myHeading, nearestN eighborsList
		output: myHeading (the new heading)
	1 sumOf Heading, neighborsAverageHeading = 0 ;
	2 foreach bird in nearestN eighborsList do
	3 Algorithm 1: Separate behavior sumOf Heading+ = getHeading(bird); 4 end
	input : myHeading, nearestBird, maximumRotation 5 neighborsAverageHeading =
		output: myHeading (the new heading) sumOf Heading/sizeOf (nearestN eighborsList) ;
	6 if myHeading isClose(neighborsAverageHeading) then 1 collisionHeading ← headingToward(nearestBird) ; 7 adaptHeading(myHeading); 2 if myHeading inTheInterval(collisionHeading, maximumRotation) then 3 8 end changeHeading(myHeading); 9 else 4 end 10 adaptHeading(myHeading, maximumRotation); 5 return myHeading 11 end
	12 return myHeading
	Align Behavior R.2 Algorithm 2: Alignment behavior
	3	adaptHeading(myHeading);
	4 end
	5 else
	6	adaptHeading(myHeading, maximumRotation);
	7 end
	8 return myHeading
	Cohesion Behaviors R.2 Speed Adaptation R.3 Before moving, the agents adapt their speed (R.3).
	During all the simulation, every agent modifies its speed according to that of

input : myHeading, nearestBird output: myHeading (the new heading)

1 nearestBirdHeading ← getHeading(nearestBird) ; 2 if myHeading isClose(nearestBirdHeading) then

https://ccl.northwestern.edu/netlogo/

http://education.mit.edu/starlogo/

https://code.google.com/p/gama-platform/

http://cs.gmu.edu/˜eclab/projects/mason/

http://www.flamegpu.com/

The orientation is an angle in degree (between 0 and 360) which gives the heading of the agent according to the landmark fixed in the environment.

www.lirmm.fr/∼hermellin/Website/Reynolds Boids With TurtleKit.html

In this context, Thread is similar to the concept of task: A thread may be considered as an instance of the kernel which is performed on a restricted portion of the data depending on its location in the global grid (its identifier)

http://www.turtlekit.org

In the context of TurtleKit, FieldOfView is the range which is used to select the cells around the agent.