Zheng Cheng
email: zheng.cheng@icam.fr

Jean-Claude Royer
email: jean-claude.royer@imt-atlantique.fr

Massimo Tisi
email: massimo.tisi@imt-atlantique.fr

Removing Problems in Rule-Based Policies

Keywords: Conflict, Inconsistency, Policy, Problem, Removing, Rule

Analyzing and fixing problems of complex rule-based policies, like inconsistencies and conflicts, is a well-known topic in security. In this paper, by leveraging previous work on enumerating all the problematic requests for an inconsistent system, we define an operation on the policy that removes these problems. While the final fix remains a typically manual activity, removing conflicts allows the user to work on unambiguous policies, produced automatically. We prove the main properties of the problem removal operation on rule-based systems in firstorder logic. We propose an optimized process to automatically perform problem removal by reducing time and size of the policy updates. Finally we apply it to an administrative role-based access control (ARBAC) policy and an attribute-based access control (ABAC) policy, to illustrate its use and performance.

Introduction

Analyzing inconsistent and conflicting situations in security policies is an important area of research and many proposals exist. Several approaches are focused on detecting specific kinds of problems [7,[START_REF] Montangero | Logic-based conflict detection for distributed policies[END_REF][START_REF] Ni | Privacy-aware role-based access control[END_REF][START_REF] Neri | Conflict detection in security policies using semantic web technology[END_REF][START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF], while others are interested in fixing these problems [START_REF] Monperrus | Automatic software repair: A bibliography[END_REF][START_REF] Garcia-Alfaro | Management of stateful firewall misconfiguration[END_REF][START_REF] Wu | Finding achievable features and constraint conflicts for inconsistent metamodels[END_REF][START_REF] Hu | Discovery and resolution of anomalies in web access control policies[END_REF][START_REF] Son | Fix me up: Repairing access-control bugs in web applications[END_REF]. We consider inconsistencies, or conflicts, or undefined requests, called problems here, as they lead to bugs or security leaks. Fixing these problems is difficult because of the policy size, the number of problems, their complexity and often the right fix needs human expertise. Our purpose in this paper is to suggest a new method in order to assist specifiers in fixing discovered problems in their policies. To make the conflicts explicit, we reuse a general and logical method defined in [START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF]. This method, in addition to revealing the problems, provides some information which can be exploited to cure those problems. In our current work we focus on removing some problems in the specification. Removing the problem means modifying the policy so that the problem disappears and no new problems are added. Of course we need to preserve, as far as possible, the original behavior of the policy while minimizing the time and the size of the policy update. While the final fix (i.e. obtaining

Related Work

Our work is under the umbrella of automatic software/system repair, which aims at automatically finding a solution to software/system bugs without human intervention. There exists extensive work under this broad topic, and we refer to [START_REF] Monperrus | Automatic software repair: A bibliography[END_REF] for a review. In this section, we discuss some of related work on automatic repairing of bugs in rule-based systems. Researchers try to find automatic fixes for various kinds of bugs, e.g. redundancies [START_REF] Hu | Discovery and resolution of anomalies in web access control policies[END_REF], misconfigurations [START_REF] Garcia-Alfaro | Management of stateful firewall misconfiguration[END_REF]. In this work we focus on conflicts and inconsistencies in rule-based systems. These problems may lead to runtime failures in the sense that sending a request to the system, may return several incompatible replies. This separates our work from efforts that address other kinds of bugs. Meta-rules are one of the most common ways to handle conflicts in rule-based systems. The general idea is that when conflicts occur, pre-defined meta-rules (e.g. first-applicable, prioritization [START_REF] Cuppens | Handling stateful firewall anomalies[END_REF]) will govern rule applications to have compatible replies. However, the problem persists to resolve potential conflicts in meta-rules. Hu et al. propose a grid-based visualization approach to identify dependency among conflicts, which aims to guide user in defining conflict-free meta-rules [START_REF] Hu | Discovery and resolution of anomalies in web access control policies[END_REF]. Son et al. [START_REF] Son | Fix me up: Repairing access-control bugs in web applications[END_REF] repair access-control policies in web applications. They first reverse engineer access control rules by examining user-defined annotations and static analysis. Then, they encapsulate domain specific knowledge into their tool to find and fix security-sensitive operations that are not protected by appropriate access-control logic. Wu focuses on detecting inconsistency bugs among invariant rules enforced on UML mod-els [START_REF] Wu | Finding achievable features and constraint conflicts for inconsistent metamodels[END_REF]. The author presents a reduction from problem domain to MaxSMT, and then proposes a way to fix bugs by solving the set cover problem. Our approach is specific in targeting FOL rule systems and providing an automatic without considering additional information fix, while minimizing the time to proceed, the size of the modifications.

Background

In this section, we introduce concepts/notations that will be consistently used in the rest of the paper. To facilitate our introduction, we illustrate on a variation of an ARBAC policy given by [START_REF] Stoller | Efficient policy analysis for administrative role based access control[END_REF] 3 . This is a middle size example with roles and a hierarchy of roles, role exclusivity constraints, permissions assignment and revocation. The original example contains 61 rules. In this work, we rewrite them in FOL, and modularize them into 4 modules, and parametrize appropriate rules with one integer for discrete time. The four modules are: roles, hierarchy and exclusion rules (11 rules), permissions (24 rules), assignment (13 rules) and assignment revocation (13 rules). In this section, we show only the role module for illustration purpose in Listing 1.1.

Listing 1.1. Rules of roles for an administrative RBAC policies And ( Patient (T , X ) , PrimaryDoctor (T , X )) = > False % first rule And ( Receptionist (T , X ) , Doctor (T , X )) = > False And ( Nurse (T , X ) , Doctor (T , X )) = > False Nurse (T , X ) = > Employee (T , X ) % 4 th rule Doctor (T , X ) = > Employee (T , X ) Receptionist (T , X ) = > Employee (T , X ) Medi calMana ger (T , X ) = > Employee (T , X ) Manager (T , X ) = > Employee (T , X ) Patient (T , X ) = > Patie ntWithTP C (T , X ) Doctor (T , X ) = > R eferred Doctor (T , X ) Doctor (T , X ) = > PrimaryDoctor (T , X ) % last rule

A rule is a logical implication, taking the form of D => C, with D being the condition and C the conclusion of the rule, expressed in a logical language (in our case FOL). For example, line 4 specifies that at any given time T, if X is a nurse, it is also an employee. A rule system (R) is simply a conjunction of rules.

Requests are FOL expressions. When they are sent to a rule system at runtime, they will be evaluated against all rules in that system to generate replies (which are also FOL expressions). For example, when a request Nurse(1, Jane) is sent to the system shown in Listing 1.1, Employee(1, Jane) is implied as a reply. A request is called undefined request, if it is satisfiable by itself, but unsatisfiable when in conjunction with R. The phenomenon caused by an undefined request is that when it is evaluated, R would give contradictory/unsatisfiable replies, therefore making the system unrealizable. We previously propose in [START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF] an optimized method to enumerate and classify all undefined requests in a rule system. The method translates the original rule system into an equivalent system made of exclusive rules. Each exclusive rule abstracts what kind of replies will be generated, provided that a certain set of rules in the original rule system is applied. We call 1-undefined request a request which, in conjunction with one rule alone, is unsatisfiable. One result of our approach is that any undefined request is a union of 1-undefined requests associated to exclusive rules. The exclusive rules we generate are analyzed by the Z3 SMT solver 4 . Based on the result from the solver, we separate exclusive rules into two categories:

-Unsafe exclusive rules. These are exclusive rules that under request will always return unsat by the solver. They abstract undefined requests that are certain to cause conflicts. -Not unsafe exclusive rules. These are exclusive rules that under request return sat or unknown by the solver. Therefore, undefined requests, that are abstracted by not unsafe exclusive rules, are uncertain to cause conflicts (conservatively, we also pick them up to rise developer's attention).

A special representation called binary characteristic links each (not) unsafe exclusive rule to the original rule system. Each binary characteristic is a list of values, where the position i represents a rule at the corresponding position in the original system. Values have enumeration type with three possibilities, i.e. 0/1/-1, indicating that the condition of the rule is negatively/positively/not presented in the exclusive rule. We call a binary characteristic complete if it does not contain -1, and has the length equal to the total number of rules in the original system (incomplete otherwise). -----------UNSAFE --------------[0 , 0 , 0 , 1 , 1 , 1 , -1 , -1 , -1 , -1 , -1] And ( Not ( Nurse (T , X )) , Doctor (T , X ) , Not ( PrimaryDoctor (T , X )) , Not ( Receptionist (T , X )) , Patient (T , X )

Listing 1.2. The roles module analysis

) = > False [1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1]
And ( Patient (T , X ) , PrimaryDoctor (T , X )) = > False ... another 2 unsafe exclusive rules -----------NOT UNSAFE --------------[0 , 0 , 0 , 1 , 0 , 0 , 1 , -1 , -1 , -1 , -1] And ( Nurse (T , X ) , Not ( Doctor (T , X )) , Patient (T , X ) , Not ( PrimaryDoctor (T , X ))) = > And ( Patie ntWithTP C (T , X ) , Employee (T , X )) ... another 9 not unsafe exclusive rules Applying the method given in [START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF] on the example shown in Listing 1.1, a total of 4 unsafe and 10 not unsafe exclusive rules are generated. Listing 1.2 shows a snippet of these rules. The shown rules are three typical kinds of exclusive rules, that in our experience, help in identifying problems in a rule system:

-Implicit unsafe rules, which are not contained in the original system, are the primary source of problems. They usually imply some overlapping condition that would cause conflicts. For example, from lines 2 to 5, the unsafe rule points out a problem, as several undefined requests. For instance in the original system Doctor(T, X) implies PrimaryDoctor(T, X) (last rule 11) which clashes with Patient(T, X) by rule 1. Interestingly, this problem is not mentioned under the radar of [START_REF] Stoller | Efficient policy analysis for administrative role based access control[END_REF].

-Explicit unsafe rules (e.g. lines 6 and 7), are unsafe rules contained in the original system and whose conclusion is unsatisfiable. -Not unsafe rules. As discussed before, they are uncertain sources of problems.

It is a problem if the request implies the conjunction of the condition and the negation of the conclusion else it is an admissible request.

The Removing Process

Undefined requests detected by our optimized enumeration method may identify problems in the original rule system. However, fixing all identified undefined requests is not desirable, since it would result in a tautological and rather useless rule system: the system would not be able to infer new facts from the logical context. Also fixing a subset of the undefined requests is not trivial. It is difficult to guarantee that the iterative fixing process terminates, since it is hard to tell that there will be no new undefined requests after a fix. Therefore, we propose an alternative solution, which is similar to the "quick fix" feature that appears in most of integrated develop environments. First, by analyzing the result of our enumeration method, the rule developers select a set of critical undefined requests to fix. Next, our solution performs a "quick fix" to remove the selected undefined requests. In the process, we strive to pinpoint a minimal set of rules in the original system for removing the selected undefined requests. By doing so, we minimize modifications that need to be made, and preserve the semantic of the original rule system as much as possible. Another important property of our solution is that it is effective. It means that regardless of choosing which undefined requests to fix first, applying our solution on each iteration will completely remove the selected undefined requests while not introducing new problems.

For example, let us consider the removal of the undefined requests characterized by the unsafe rule shown on lines 2 and 5 of Listing 1.2. Our approach takes its binary characteristic as input, and produces Listing 1.3 as output. The output states that one rule (i.e. the 11th rule) in the original system needs to be changed, and what it should be changed to (lines 2 and 5). Identified problems are existentially quantified (that explains the Exists quantifier) and composed by union with the selected rule conclusion.

Listing 1.3. Removing the Problem Target rule : [START_REF] Ni | Privacy-aware role-based access control[END_REF] , Suggested fix : Doctor (T , X ) = > Or ( PrimaryDoctor (T , X ) , Exists ([ T , X ] , And ( Not ( Nurse (T , X )) , Doctor (T , X ) , Not ( PrimaryDoctor (T , X )) , Not ( Receptionist (T , X )) , Patient (T , X ))))

Once the change has been made, applying our optimized enumeration method again will result in 10 not unsafe rules as before, but the selected unsafe rule has been removed and only the 3 explicit unsafe rules remain. At this stage, rule developers can choose once again undefined requests to remove, or stop if the rule system satisfied their expectation. In our final version of this module we simply forget this rule (the 11th) as it seems an error in the roles specification.

In what follows, we present an overview of our removing process (Section 4.1), and its main properties (Section 4.2).

Overview of Removing Process

Let U be the undefined request (represented by exclusive rules) that rule developer choose to fix. One way to remove U is by adding a new rule in the original rule system, which takes the shape of U => False. It explicitly alerts the rule developer on some undefined cases. However, this rule is redundant and the resulting system contains more and more rules when fixes iterate, which compromises understandability and maintainability. Another way is to globally restrict the set of input requests by adding a condition to all the defined requests. But this condition is far from readable in case we have several problems in the rule system. Therefore, for understandability and maintainability, we design a removing process that aims at automatically modifying a selected set of rules in the original system without the need to understand the real nature of the problem to fix. The principle of our removing process is to exclude U from the original rule system, i.e. ¬U => R which is equivalent to

∀ * 1≤i≤n (D i => (C i ∨ U )) (1)
All free variables in (1) are denoted by *, and i is the index of a rule in the rule system of size n. Moreover, U is the selected problem to fix, and represented by a FOL existential expression without free variables. Obviously modifying all the rules is not always required, and sometimes the modification of one rule alone D => (C ∨ U ) could be sufficient. Thus we will consider how to do optimal modifications rather than modifying all the rules, that is to modify F , a subset of all the rules. We denote R/F/U the system resulting by this modification.

Properties

We have illustrated how to remove selected undefined requests by pinpointing a minimal set of rules in the original system to modify. In this section, we discuss the effectiveness and semantics preservation of this approach. Effectiveness. By effectiveness, we mean that removing the problem U does not add new problems. From now on, all represents the set of all the rules in R.

We know that we have

R => R/F/U => R/all/U , and R/all/U = (R ∨ U ). It is easy to see that R/F/U = R ∨ (U ∧ R ¬F )
, where R ¬F is the subsystem of the rules in R which are not modified. We should note that if U is a problem at least one rule should be fixed and we know that fixing all the rules may be required (if U is 1-undefined for all the rules in R). If we fixed a problem U in R and get R/F/U , we expect that U is not a problem of R/F/U and also this does not add new problems. But if U => ¬R/F/U we know that ¬R/F/U = (¬R ∧ ¬U ) ∨ ¬R F => ¬R. Thus it means that U was not a new problem but an already existing one for R. Note also that we do not have ¬R => ¬R/F/U to be valid meaning that we have strictly less problems after removing U . This shows that the removing process is effective whatever the removing ordering is. Behaviour preservation. What behaviours of the original rule system could rule developers expect to preserve after the removing process applied. Let a given request req = (req ∧¬R)∨(req ∧R), applying it to R we get req ∧R . But applied to R/F/U we get

(req ∧ R) ∨ (req ∧ U ∧ R ¬F ). Thus preserving is equivalent to req ∧ U ∧ R ¬F => req ∧ R which is equivalent to req ∧ U ∧ R ¬F unsatisfiable.
If req intersects both R and its negation we get (req ∧ R) ∨ (req ∧ U ∧ R ¬F ) meaning that the new reply widens the original reply. Behaviour preservation is not possible for all requests.

Property 1 (Behaviour Preservation). Let req a satisfiable request thus

req => ¬U ∨ ¬R ¬F is equivalent to req ∧ R = req ∧ R/F/U .
The above property states that behaviour is strictly preserved after removing U if and only if the request satisfies req => ¬U ∨ ¬R ¬F . If req => ¬U the behaviour is preserved for any selection F and if req => R the behaviour is preserved for any problems and any selection. The next section explain how to make the process more efficient by pinpointing a minimal set of rules in the original system for removing the selected undefined requests (Section 5).

Finding the Minimal Selection

Let U be a problem and R a set of rules, our goal is to modify R in order to make the requests in U defined. The challenge is to do that efficiently and minimizing the modifications in the rule system. We will get a new system R/F/U where the rules in F are modified in order to avoid U to be undefined. The fixing principle is either to add ¬U in the selected rule conditions or to add U in the rule conclusions. Modifying conclusions is simpler since we have the same enumerative decomposition for R and R/F/U only the conclusions are different.

Definition 1 (Correct Fix of a Rule System). Let R, F , U be a closed and satisfiable sentence, F is not empty, R/F/U is a correct fix for R with F and U if each rule in F has its conclusion enlarged with U and U is not a problem for R/F/U .

A simple fact to observe is: If F is a correct fix then any G such that F ⊂ G is also a correct fix. Then our challenge is to find a selected set F to fix, smaller than all the rules. Thus we need to show that if U is a problem for R it is defined for R/F/U . It means that a direct, called here naive, solution is to check this property with a SAT solver.

Definition 2 (Naive Check). R/F/U is a correct fix if and only if U ∧ R ¬F is satisfiable.

This comes from the fact that U is a problem, R/F/U = R ∨ (U ∧ R ¬F ) and the definition of a correct fix.

It is easy to see that if U is a problem for R with a set of conditions D 1≤i≤n then U => j∈J ∃ * D j , where J is a subset of 1 ≤ i ≤ n. Exclusive rules as built by the enumerative method have some interesting properties, particularly because U => (∀ * D j ) means that only one rule (the j th ) applies. A single problem is associated to a complete binary characteristic, while a complex problem has an incomplete binary characteristic. From [START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF] we know that any undefined request U satisfies U => ∃ * ( i∈I1 D i j∈I0 ¬D j ), where I 1 (respectively I 0 ) is the set of positive (respectively negative) rules in the binary characteristic.

Property 2 (Application to Exclusive Rules). Let R an exclusive rule system if

U => ∃ * D j then R ∧ U is equivalent to (U ∧ (∀ * D j ∧ C j )) ∨ (U ∧ (∃ * D j ∧ ∃ * ¬D j )) ∧ R.
In this paper we omit the full proofs, they can be found in the full version of the paper on our repository https://github.com/atlanmod/ACP-FIX. The proof relies on the fact that the universally quantified part triggers only one exclusive rule. We show with Property 3 that any problem found by the enumerative method can be split into disjoint parts called, respectively, universal and existential parts.

Property 3 (Universal and Existential Parts

). Let U a satisfiable problem such that U => ∃ * ( i∈I1 D i j∈I0 ¬D j ) then U = U ∧ (∀ * ( i∈I1 D i j∈I0 ¬D j ) ∨ U ∧ (∃ * ( i∈I1 ¬D i j∈I0 D j ).
This property results from the partition of U related to the universally quantified part and its negation. Exploiting the information given by the enumerative method we expect to optimize the definedness checking for problems found by this method. We analyze now two cases: single or complex problem in order to expect to optimize the naive approach.

Property 4 (Definedness of Single Problem). Let R a rule system and a single problem

U => ∃ * ( i∈I1 D i j∈I0 ¬D j ) with a complete binary characteristic, if U ∧ ∀ * ( i∈I1 D i j∈I0 ¬D j i∈I1 C i ) is satisfiable then U is defined for R.
From R we can build an equivalent exclusive system using the enumerative method and thus we use Property 2. We consider the universal part of the problem, that is U ∧ ∀ * i∈I1 D i j∈I0 ¬D j . With these conditions only one rule applies and others do not apply, they lead to the universal part and then the result of R ∧ U comes from a single enumerative rule for R and gives U ∧ ∀ * ( i∈I1 D i j∈I0 ¬D j i∈I1 C i ). We now consider the enumerative process but for R/F/U since we need to prove that U is defined for it. Computing the enumerative process for R/F/U gives new rules of the form:

∀ * ( i∈I1 D i j∈I0 ¬D j ) => (( i∈I1∧¬F C i ) i∈I1∧F (C i ∨ U ))
). We start by analyzing the case of a single problem with a complete binary characteristic.

Property 5 (Removing Criterion for Single Problem). Let U a single problem with positive rules

I 1 thus R/F/U is a correct fix if either I 1 ⊂ F or I 1 ∩ F = ∅ and U ∧ ∀ * ( i∈I1 D i j∈I0 ¬D j i∈I1∩¬F C i ) is satisfiable.
In this case there is a unique enumerative rule which applies and we use Property 4 for R/F/U . This is only a sufficient condition as we only check the universal part of the problem.

In case of a complex problem U with an incomplete binary characteristic we can obtain a set of complete binary characteristics adding digits not already in the incomplete binary characteristic. A completion G 1 ∪ G 0 is a subset of {1..n}\(I 1 ∪ I 0 ) with positive and negative rules.

Property 6 (Removing Criterion for a Complex Problem

). Let U a complex prob- lem, R/F/U is a correct fix if ¬F ⊂ I 0 or F ∩ ¬I 0 and U ∧∀ * ( i∈I1 D i j∈I0 ¬D j i∈I1∩¬F C i ) g∈¬I1∩¬I0∩¬F ((∀ * D g ∀ * C g )∨∀ * ¬D g ) is satisfiable.
This criterion generalizes the previous one for single problem.

In the previous cases we defined a sufficient condition to remove a single or a complex problem. From the previous criterion and the decomposition into a universal and an existential part we have: If U is a problem for R then U is defined for R/F/U if and only if the criterion for complex problem is satisfied

or if U ∧ (∃ * ( i∈I1 ¬D i j∈I0 D j ) ∧ R ¬F is satisfied.
Property 7 (CNS for complex problem). If U is a complex problem, R/F/U is a correct fix if and only if the universal or the existential part is defined for R/F/U .

Looking for Minimal Size

This subsection discusses how to find a set of rules to modify but with a minimal size. We can define a top-down and a bottom-up process to find a minimal solution. Both ways have a worst complexity which is exponential in the number of satisfiability checks. But the bottom up approach is preferable since it stops once the solution is found. Instead the top down approach, once the solution of size m is found, must prove the minimality of it by checking all the smaller combinations of size m -1. The naive approach consists in modifying a subset of rules and checking the satisfiability of the new system in conjunction with the problem to remove. Minimal core satisfiability techniques cannot be used here (for instance [START_REF] Wu | Finding achievable features and constraint conflicts for inconsistent metamodels[END_REF]), since they do not respect the structure of the rule system.

Using our criteria we optimize this search. We know that the set of all rules is a solution but in case of a single or complex problem it is also true if we take F as all the positive rules in the binary and its completion. Indeed, if we are looking for minimal solutions it is sufficient to look inside these positive rules. The reason is that if the criterion is satisfied with I ∩ F the part of F not in I does not matter and can be forgotten. Given a problem we defined a lookup_complex algorithm which looks for a minimal set of rules. It simply starts with the least possible solution (that is a single rule) and checks the criterion an all the combinations until reaching a minimal solution.

There are two critical points in the time performances of our two solutions: the number of rule combinations to test and the size of the expression to check for satisfiability. Both these aspects have an exponential nature in general. Exploiting the binary information the lookup_complex algorithm looks for less combinations than the naive algorithm. Regarding the satisfiability checking we expect to gain but the size of the formula is not a reliable indicator here. The informal reason lies in the form of the universal formula which is closed to CNF (Conjunctive Normal Form) which is at the heart of most of the solvers. To justify it we consider a problem associated to an unsafe rule. We also assume that our rule system contains only free variables and rules with a conjunction of predicates as condition and a disjunction of predicates as conclusion. If K = 1 the maximal number of predicates in a condition or a conclusion, the universal part can be seen as a 2-SAT CNF which satisfiability time is polynomial. If K ≥ 2 we get CNF in the NP complete case but our optimisation relies on the transition phase phenomenon [START_REF] Achlioptas | Rigorous location of phase transitions in hard optimization problems[END_REF]. Analysing the CNF transformation we get a 2 * K-SAT CNF and we estimate the maximal number of clauses M ≤ 2 * K * n while the total number of literals in the clauses is N ≥ (2 * K + n -1). Thus the ratio α = M/N is below the threshold 2 2 * K * ln(2) -2 * K, (as soon as K ≥ 2), the area where the universal part is probably satisfiable in a small amount of time.

Application Examples

The purpose of this section is to show that our removing approach succeeds on middle-size examples. We will focus on removing problems coming from unsafe rules in these examples.

Our first specification is compound of the four previous modules introduced in Section 3. The permissions module is rather straightforward, assignment and revocation need to manage discrete time changes. In the assignment of permissions we choose to set the effect at next time. One example is And(Doctor(T, X), Doctor(T, Y), assign(T, X, Y)) => ReferredDoctor(T+1, Y). In this specification the effect of a permission assignment is done at T+1 which is a simple solution avoiding clashes with the roles module. The revocation module has similar rules to the assignment of permissions. However, we need more complex conditions because before to revoke an assignment it should have been previously done. The corresponding example for revocation of the above rule is And(Doctor(T, X), revoke(T, X, Y), (P < T), assign(P, X, Y), Not(assign(T, X, Y))) => Not(ReferredDoctor(T+1, Y))). An assign and a revocation are not possible at the same time instant because of inconsistency. We already analyzed the roles module and it was easy to process the three new ones in isolation since they have no unsafe rule. One interesting fact is that their composition does not generate new unsafe rules, indeed we get the three explicit unsafe rules coming from the roles module (see Section 4).

A Second Specification

An alternative solution for the specification of the assignment module is to write rules without changing the time instant in the conclusion. In this new specification our example above becomes: And(Doctor(T, X), Doctor(T, Y), assign(T, X, Y)) => ReferredDoctor(T, Y). It generates unexpected conflicts we will solve now. Our analysis shows that we get 91 not unsafe rules and three unsafe rules in nearly 8s. Thus using our lookup_complex procedure we find that these problems are all removed by modifying the rule: [START_REF] Garcia-Alfaro | Management of stateful firewall misconfiguration[END_REF]. The enumerative computation of the new system shows that it has no more unsafe rule. Now these modifications could produce new interactions with the other modules. In fact only the roles module has new unsafe rules with the assignment module, indeed there are 3 new unsafe rules. These unsafe rules are coming from the negation of the 11 th rule in assignment and the lookup_complex shows that the 4 th rule is the minimal fix for all these problems. Fixing these three problems we compute the enumerative solution for the 4 modules together and we do not get new unexpected unsafe rules. The result was computed in nearly 5200s and generates 20817 not unsafe rules and the three explicit unsafe rules from the roles module. This example shows that we can select some problems and remove them from the specification while minimizing the impact on the rule system. We compare the naive and our lookup_complex algorithms and compute several measures which are summarized in the table 1. We consider 123 unsafe problems occurring before the final fix in the composition of the four modules. Note that in this setting our example is not simply variable free because we fix two rules adding some complex existential expressions. We compute5 the following measures in Table 1: for the naive approach the mean of minimal size (NS), mean of time (NT), the same for the lookup method with LS, LT and in addition the mean of positive rules in each problem (PR), the maximum of differences between size of the selection (DS) and the mean of the ratio: naive time divided by lookup time (factor time TF). But this example is specific on one point: the problems are not so numerous and related to some specific rules in the assignment module. Thus most of the problems (but the first three) are related to the 4 th rule of the assignment module.

The ContinueA Example

To consolidate our results we consider the ContinueA policy6 we already analyzed in [START_REF] Cheng | Efficiently characterizing the undefined requests of a rule-based system[END_REF] and which was the study of several previous work [START_REF] Fisler | Verification and change-impact analysis of access-control policies[END_REF][START_REF] Hu | Discovery and resolution of anomalies in web access control policies[END_REF]. This policy has 47 rules, which are pure first-order with at most two parameters. The original example is in XACML which forces the conflict resolution using combining algorithms. To stress our algorithms we do not consider ordering or meta-rules but a pure logical version of the rules. The result is that we have a great amount of problems amongst them 530 unsafe rules while the number of not unsafe rules is 302 (computed in 97 seconds). We process all the unsafe problems that is 530, see Table 1. The following observations confirm what was observed on the healthcare example, except that now we have many more problems to analyze. First we observed that the minimal set of fixing rules is generally low (between 1 and 5 rules) and this shows that finding it is relevant to minimize the modifications in the rule system. Another point is that due to the combinatorial explosion it is really costly to go up to more than 4 rules (see Table 2). The second point is that the lookup algorithm does not deviate from the naive one regarding the size of the minimal set. We do not get exactly the same selection set in 33% of the cases, due to the different ordering in the search for minimal, but the minimal sizes are always the same. Regarding the time to proceed, the lookup outperforms the naive one by a factor between 60% and 5000% with a median of nearly 800%. For this example we also compute the distribution per selection size, and the mean time for each algorithms.

Discussion

Regarding the healthcare example, we defined two versions which have finally only three explicit unsafe rules and we remove only few problems. For the Con-tinueA example removing all the unsafe problems can be done modifying all the 47 rules with an increase in size of 24910 * U S, where U S is the median size of the problems. Using the minimal selection of rules the increase in size is 796 * U S.

The naive algorithm needs nearly 17 hours to compute the minimal selections while the lookup takes 4.6 hours. Our experiments also confirm that our time improvement is twofold: the restricted space to search for a minimal selection and checking first the universal part. We do not detail this here but the picture appears in our repository (https://github.com/atlanmod/ACP-FIX) as well as the source of the prototype, the examples and some measures. It is not relevant to expect to remove all the problems. Furthermore we should also cope with the set of real requests which will decrease the amount of such undefined requests. Nevertheless an assistance should be provided to identify what are the critical problems. This is a tricky issue. The presented technique is also correct for 1-undefined problems arising in not unsafe rules. We also process some of these problems: for the 320 problems in ContinueA we get a mean for T F = 120% while with 3000 problems (nearly 10% of the problems) of the healthcare we get a mean of 800%. Thus our technique is generally useful for any kinds of problems and furthermore the reader may note that our examples after fixing are not longer simply variable free. This is the case when we fixed the role and assign modules of the healthcare example since we add existentially quantified expressions. However, the performances were similar and we need more experiments and analysis to precisely understand the applicability of the proposed method.

Fixing a problem means to associate to U a single reply rather than inconsistent replies. This is similar to removing the problem but in addition we need to choose a reply which in general cannot be automatic. In this case the fixing principle is to change the rule (D => C) into (D => (C ∨ U )) ∧ (U => OK) where OK stands for the correct reply to U . We did not yet investigate it but our current work is a good basis to solve this more complex problem.

Conclusion

Automatically removing problems in a policy is important to sanitize it. Sometimes there are too many problems and they are difficult to understand at least for non experts of the system. Getting simplified problems can help in solving them, however it is a complex and costly issue. Our work demonstrates that, under the conditions of the satisfiability decision and the time to proceed, we can automatically remove a selection of problems. Furthermore, we are able to minimize the size of the modifications as well as improving the time to proceed. We demonstrate it on two policies of middle size: an ARBAC and an ABAC.

This work leaves open many questions, first is about checking the existential part while getting a minimal size close to the exact minimal size. However, it seems tricky because most of our attempts to relax the existential part lead to an unsatisfiable expression. Second, we can benefit by more case studies from related work (e.g. [START_REF] Son | Fix me up: Repairing access-control bugs in web applications[END_REF][START_REF] Hu | Discovery and resolution of anomalies in web access control policies[END_REF][START_REF] Wu | Finding achievable features and constraint conflicts for inconsistent metamodels[END_REF]) to statistically justify that we can get a low minimum in real cases, or we can synergize with related works. The main problem is how to faithfully encode the complete case studies (e.g. encoding explicit/implicit UML semantics plus invariants as rules in our system). The third track is to explore the benefit of checking the universal part only.

A Proof of the Universal Criteria

Below is a proof of the Property 2. Note that if R is exclusive it is equivalent to ∀ * 1≤i≤n (D i ∧C i )∨ 1≤i≤n (¬D i )) which can be proved by recurrence on n. We split U in two parts related to ∀ * D j and its negation. Since we do not have free variables in these parts we can distribute them under the scope of the outside universal quantifier. For the first part, let R ∧ U ∧ (∀ * D j ), the conjunction with each (D i ∧ C i ) if i = j it is unsatisfiable as well as the conjunction with the last term. For i = j corresponding to the application of the j rule, its application is

U ∧ ∀ * ((∀ * D j ) ∧ D i ∧ C j ), and equivalent to U ∧ ∀ * (D j ∧ C j ).
Proof of the Property 5. We analyze the case of a single problem noted U s with a complete binary characteristic. There are three exclusive cases for the rule to apply. If I 1 ⊂ F the result is U s satisfiable, since the rule conclusion is ( i∈I1 C i ) ∨ U . If I 1 ⊂ ¬F the result is unsatisfiable, since the rule conclusion is i∈I1 C i and U is a problem. In the remaining case, U s is an undefined request thus U s = U s ∧ ∃ * ( i∈I1 D i j∈I0 ¬D j ) ∧ ¬( i∈I1 C i ), where I 1 is the set of positive rules. Thus we can apply the Property 4 for R/F/U , the result is

U s ∧ ∀ * ( i∈I1 D i j∈I0 ¬D j ∧ ∀ * (( i∈I1∧¬F C i )(( i∈I1∧F C i )∨U )) equivalent to U s ∧ ∀ * ( i∈I1 D i j∈I0 ¬D j ) ∧ ∀ * ( i∈I1∧¬F C i ) which should be satisfiable.
The proof of the Criterion 6 is based on the binary completion and the use of the criterion for the single problems. The first step is to compute R/F/U using the enumerative method which leads to rules ∀ * ( i∈I1 D i j∈I0 ¬D j i∈G1 D i j∈G0 ¬D j ) => (( i∈(I1∪G1)∩F (C i ∨ U )) i∈(I1∪G1)∩¬F C i ), where G 1 , G 0 represent the completion of I 1 , I 0 . For the conclusion there are three cases which lead respectively to true, false, and to check a complex expression. The first case is if ¬F ⊂ I 0 then F ⊂ I 1 ∪ G 1 and the conclusion of each rule contains U thus the conjunction contains U and the conjunction with it is satisfiable. In the second case, if F ⊂ I 0 , there is no positive rules fixed and U is unsatisfiable with ∀ * i∈I1∪G1 C i then the conjunction with U ∧ R/F/U is unsatisfiable. Thus we now assume that F and ¬F intersect the complement of I 0 which is I 1 ∪ G 1 ∪ G 0 and any enumerative rule is like this: ∀ * ( i∈I1 D i j∈I0 ¬D j i∈G1 D i j∈G0 ¬D j ) => (( i∈I1∪G1 C i ) ∨ (U ∧ i∈(I1∪G1)∩¬F C i )). Thus U is equivalent to U ∧ ∃ * ( i∈I1 D i j∈I0 ¬D j )( G∈G ∃ * ( i∈G1 D i j∈G0 ¬D j ). Then we distribute each part on R/F/U and since we have complete characteristics only the rules matching it applies as in the Property 4. Thus we get a union G∈G U ∧∀ * ( i∈I1∪G1 D i j∈I0∪G0 ¬D j ) ∀ * (( i∈I1∪G1 C i )∨(U ∧ i∈(I1∪G1)∩¬F C i )) which implies U ∧ R/F/U . But U is a problem and thus in conjunction with ∀ * i∈I1∪G1 C i it is unsatisfiable. We also factorize U ∧∀ * i∈I1 D i j∈I0 ¬D j i∈I1∩¬F C i . This leads to U ∧ ∀ * i∈I1 D i j∈I0 ¬D j i∈I1∩¬F C i ∧ ( G∈G ∀ * ( i∈G1 D i j∈G0 ¬D j i∈G1∩¬F C i )). Let G 1 ∩ ¬F we can factorize every expression containing it getting i∈G1∩¬F C i i∈G1∩¬F D i j∈G0 ¬D j ∧ ( G∈GF D G ) where GF is the completion for rules in ¬I 1 ∩ ¬I 0 ∩ F . It simplifies in i∈G1∩¬F C i i∈G1∩¬F D i j∈G0 ¬D j and the union becomes ( G∈G/F ∀ * ( i∈G1 D i j∈G0 ¬D j i∈G1∩¬F C i )), where G/F is the subsets of rules in ¬I 1 ∩ ¬I 0 ∩ ¬F . We remark that h∈G∩¬F (D h ∧ C h ) ∨ ¬D h = G∈G/F ( i∈G1 D i j∈G0 ¬D j i∈G1∩¬F C i )). Then a final factorization produces U ∧ ∀ * ( i∈G1 D i j∈G0 ¬D j i∈I1∩¬F C i ) ∧ ( g∈G∩¬F ((∀ * D g ∧ ∀ * C g ) ∨ (∀ * ¬D g )).

B Additional Results

The fact that the minimal selection has a small size can surely be founded by a statistic or probabilitic analysis. A consequence of it is that in the naive approach there is no significative difference between checking U ∧R and U ∧R ¬F . To confirm that our time improvement is twofolds we did some complementary experiments, see Figure 1 for results in the case of the ContinueA policy and the unsafe problems. We also observed that evaluating only the universal part gives results close to the real minimum while the time performance was not significantly different from evaluating also the existential part. We test three different algorithms:

-A: The naive approach -B: The naive approach with a selection based on the binary characteristic -C: The lookup with the selection and checking the universal then the existential formula.

In this figure we report the time factors of the comparaison between A-B, B-C and A-C. In average both features have an impact on the time factor but the benefits are reversed: the benefit of testing the universal part decreases with the binary characteristic size while it is the opposite for the selection.

Table 1 .

 1 Measures for two Policies

	Usecase	Naive algorithm Lookup algorithm Additional measures
		NS	NT	LS	LT	PR DS	TF
	Healthcare Policy 1	1.01s	1	0.2s	10.1 0	509%
	ContinueA Policy 1.53	115s	1.53	31s	3.9 0	794%

Table 2 .

 2 Selection Distribution

	Selection size Frequency Naive mean time Lookup mean time Time factor
	1	63%	0.33s	0.04s	800%
	2	27%	6.6s	1.15s	573%
	3	8%	124s	24s	517%
	4	3%	1573s	281s	560%
	5	0.5 %	88890	3433	256%

The original example with comments is available at http://www3.cs.stonybrook. edu/ ~stoller/ccs2007/

The Z3 Theorem Prover. https://github.com/Z3Prover/z3

These results were computed with 10 runs when it was sensible in time, that is all cases except three (amongst 530) for the ContinueA policy.

http://cs.brown.edu/research/plt/software/margrave/versions/01-01/ examples/


Dr Nazan Kaloğlu

Dr Mathieu Achard

Dr Christian Bruneau

Dr İsmail Özdemir
email: ismail.ozdemir@inonu.edu.tr

Ruthenium(II)-(arene)-N-Heterocyclic Carbene Complexes: Efficient and Selective Catalysts for the N-Alkylation of Aromatic Amines with Alcohols

Keywords: N-Heterocyclic carbene, ruthenium catalyst, aromatic amines, N-alkylation, borrowing hydrogen strategy

A series of unsymmetrical 1,3-disubstituted benzimidazolium chlorides were synthesized as N-heterocyclic carbene (NHC) precursors. These compounds were used for synthesis of the new ruthenium(II) complexes of the type [RuCl2(arene)(NHC)], (arene = η 6 -p-cymene). The structures of all compounds were characterized by 1 H NMR, 13 C NMR and FT-IR spectroscopy techniques. The catalytic activity of the ruthenium complexes has been evaluated with respect to the mono-Nalkylation reactions of aromatic amines with various alcohol derivatives under solvent-free conditions at 120 o C using the borrowing hydrogen strategy.

Introduction

Amines are an important class of compounds that are widely found in bioactive molecules, pharmaceuticals and natural products, due to their diverse biological and pharmacological properties [START_REF]The Organic Chemistry of Aliphatic Nitrogen Compounds[END_REF][START_REF] Lawrence | Amines: Synthesis, Properties, and Applications[END_REF][START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]. Considering structural diversity and biological properties of amines, it is clear that they are an important component in medicinal applications [4]. As selected examples of benzyl-substituted amines, Tripelennamine (marketed as Pyribenzamine ® ) is a drug that is used as an antipruritic and first-generation antihistamine, Bepridil (marketed as Vascor ® ) is is an amine calcium channel blocker once used to treat angina and Zafuleptine (proposed brand name Thymeon) is an antidepressant drug, developed in the 1970s but never marketed (Figure 1).

Conventional methods to access amines include the nucleophilic substitution of halides [START_REF] Smith | March's Advanced Organic Chemistry[END_REF] as well as reductive alkylation processes [START_REF] Gribble | [END_REF]. However, these conventional methods suffer disadvantages as follows; [START_REF]The Organic Chemistry of Aliphatic Nitrogen Compounds[END_REF] the use of alkyl halides or strong reducing reagents is undesirable from an environmental point of view and (2) these reactions generate equimolar amounts of wasteful salts as co-products [7][START_REF] Dunn | Sustainable Catalysis: Challenges and Practices for the Pharmaceutical and Fine Chemical Industries[END_REF][9]. Therefore, the development of improved synthetic methodologies for the preparation of the alkylated amines continue to be of significant interest to organic chemists. Recently, several papers briefly reported the transition metal-catalyzed N-alkylation of amines with alcohols following the so-called "hydrogen borrowing" or "hydrogen auto-transfer" methodology, has attracted much attention (Figure 2) [10][11][12]. It is a new, efficient and alternative method for the synthesis of alkylamines. The use of alcohols instead of alkyl halides to achieve the alkylated amines is an attractive method, because, it does not generate any harmful and/or wasteful by-products (only H2O as by-product). In addition, alcohols are more readily available than alkyl halides and related alkylating agents in many cases, and if the reaction proceeds efficiently by the employment of equimolar amounts of starting materials, extremely high atom economical system can be realized [13]. In borrowing hydrogen strategy, firstly, metal takes the hydrogen from the alcohol. The short-term removal of the hydrogen in the alcohol converts it into the aldehyde and forms a metal hydride.

Then, aldehyde can react with an amine to to give the imine upon removal of water, and finally, the transition-metal catalyst returns the borrowed hydrogen to the imine to form the secondary amine, (tertiary amine if the starting material is a secondary amine) [14]. Pioneering works in this field have been done independently by the groups of Grigg [15], Watanabe [16] and Murahashi [17] in the presence of rhodium and ruthenium catalysts at the beginning of the 1980s. These first reports demonstrated that noble metals such as rhodium and ruthenium could catalyse borrowing hydrogen reactions. But due to the lack of selectivity, both secondary and tertiary amines were formed, due to the harsh catalytic conditions. Then, new catalysts were developed to carry out this reaction under milder conditions [18].

Recently, great contributions have also been made the groups of Beller [19], Williams [20],Milstein [21], Zhao [22], Fujita [23] and Bruneau [24]. In most of the cases, ruthenium or iridium complexes have been used as catalysts to achieve efficient Nalkylation of a variety of amines with alcohols. Recently, important progress in borrowing hydrogen strategy was achieved with Au and Zr as the catalysts with excellent results [25]. In addition, these strategy has been performed using biocatalysts for the preparation of enantiopure amines via biocatalytic hydrogen methodology [26].

Over the last two decades, N-heterocyclic carbenes (NHCs) have emerged as a highly versatile class of ligands for a broad range of transition metals. Transition-metal complexes of NHCs have been widely used in organometallic chemistry as an alternative to well-known phosphine ligands for the synthesis of homogeneous catalysts. Many types of N-alkyl, N-aryl and Nbenzyl (benz)imidazolylidene carbene ligands have been used in transition-metal catalysis and medical applications, and many research groups have provided a large number of 28]. To date, NHC complexes of ruthenium and iridium have been reported to be active catalysts for the hydrogen borrowing reactions involving alcohols. In particular, N-alkylation of primary amines with alcohols via hydrogen borrowing processes have been carried out with (arene)ruthenium-and (Cp*)iridium-carbene complexes. As an early example, Cp*-functionalized iridium-carbene complexes have been reported by Peris for the N-alkylation of aniline and βalkylation of secondary alcohols [29]. Crabtree have reported the use of [IrCp*] complex as a catalyst for the N-alkylation of amines [30]. Valerga reported the N-alkylation of both aromatic and non-aromatic amines using ruthenium(II)-picolyl-NHC complex as a catalyst [31]. Recently, Huynh and Seayad have reported the N-alkylation of amines with alcohols and diols using [RuCl2(p-cymene)(NHC)] complex [32]. More recently, our research group [RuCl2(arene)(NHC)] complexes (Figure 3,A)

have also been used for the formation of tertiary amines from cyclic secondary amines and primary benzylic alcohols (or aldehydes) [33a, 34b,c,e]. We have also previously shown that the half-sandwich ruthenium complexes (Figure 3

Results and Discussion

Preparation of Benzimidazolium Chlorides

The all benzimidazolium chlorides (1a-1e) were synthesized as we previously described in the literature [28g,m] by the reaction of N- (3-methoxybenzyl)

Preparation of Ruthenium-(arene)-NHC Complexes

The new ruthenium complexes 2a-2e were obtained in 54-82% yields by transmetalation of the corresponding silver-NHC All compounds were prepared according to general reaction pathway depicted in Scheme 1. The analytical data are in good agreement with the compositions proposed for all the new ruthenium complexes we prepared, and are summarized in Table 1.

Scheme 1. Synthesis of benzimidazolium chlorides (1a-1e) and their ruthenium(II) complexes (2a-2e).

Accepted Manuscript

Optimization of the Reaction Conditions for N-Alkylation of

Aniline with Benzyl Alcohol

The catalytic activity of the ruthenium complexes 2a-2e for alcohol activation towards N-alkylation was investigated by taking the coupling between benzyl alcohol and aniline as a standard reaction (Table 2). Catalyst 2a was selected for initial optimization of the reaction conditions. To find the best base, different bases ( t BuOK, Cs2CO3, K2CO3, KOH) were tested under solvent-free conditions at 120 o C for 24 h (Table 2, entries 1-4). [a] Reaction conditions: Aniline (1.0 mmol), benzyl alcohol (1.5 mmol), base (1.5 mmol). [b] Yields (%) were calculated according to aniline by GC-MS analysis using dodecane as an internal standard. [c] Selectivities (%) of 3aa and 3ba were calculated by GC and GC-MS analysis. [d] Only [RuCl2(p-cymene)]2 complex was used as catalyst. [e] Without any ruthenium catalyst. [f] In situ generated catalytic system with 1a carbene precursor and [RuCl2(p-cymene)]2 was used.

When a base of t BuOK was used, a good yield of Nbenzylaniline (3aa) was obtained (Table 2, entry 1). When the amount of catalyst is reduced from 4 mol% to 2 mol% and from 2 mol% to 1.5 mol%, no noticeable effect on the yield and selectivity was observed (Table 2, entries 5,6), but when the amount of catalyst was reduced from 1.5 mol% to 1 mol%, the yield dropped to 74% and the selectivity of 3aa decreased from 94% to 65%. (Table 2, entry 7). Thus, the most suitable amount of catalyst was determined as 1.5 mol% in this reaction.

Decreasing the reaction temperature from 120 °C to 100 °C had detrimental effect on the yield ( When in situ generated catalytic system with 3 mol% of 1a carbene precursor and 1.5 mol% of [RuCl2(p-cymene)]2 was used, 59% yield was observed (Table 2, entry 13).

N-Alkylation of Aromatic Amines with Various Alcohols

The optimized conditions were applied to N-alkylation of aniline with benzyl alcohol using the ruthenium complexes (2a-2e) under solvent-free conditions at 120 o C for 20 h (Table 2). As shown in Table 3 aniline and produced the N-alkylation products with high selectivity (Table 3, entries 1-20). The selectivity was in high ratio toward to amine. Among the tested complexes, 2a is highly efficient in the N-alkylation of aniline (Table 3, entries [START_REF]The Organic Chemistry of Aliphatic Nitrogen Compounds[END_REF][START_REF] Gribble | [END_REF]11,16).

When the reaction of aniline with benzyl alcohol was performed by the complexes 2a-2e, N-benzylaniline (3aa) was obtained as a major product (selectivity of 3aa, 90-94%), ( C, 20 h. [b] Yields (%) were calculated according to aniline by GC-MS analysis using dodecane as an internal standard. [c] Selectivities (%) of 3a and 3b were calculated by GC and GC-MS analysis.

When the reaction of p-methylaniline with alcohol derivatives such as benzyl alcohol, p-isopropylbenzyl alcohol and citronellol was investigated, the yields were at between 80-90%, 75-85% and 63-75%, respectively (Table 4, entries [START_REF]The Organic Chemistry of Aliphatic Nitrogen Compounds[END_REF][START_REF] Lawrence | Amines: Synthesis, Properties, and Applications[END_REF][START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF][4][START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF][7][START_REF] Dunn | Sustainable Catalysis: Challenges and Practices for the Pharmaceutical and Fine Chemical Industries[END_REF][9][10][11][12][13][14][15].

N-(Benzyl)-p-methylaniline (4aa) and N-(p-isopropylbenzyl)-p-

methylaniline (4ab) were obtained in excellent yields (selectivity Accepted Manuscript of 4aa, 95-100% and selectivity of 4ab, 93-100%), (Table 4, entries 6-10). The N-alkylation of citronellol with p-methylaniline proceeds nicely. The citronellol was also a good substrate to afford the corresponding products N- (3,7-dimethyloct-6-en-1-yl)p-methylaniline (4ac) with high yields (Table 4, entries 6-10). In general, N-alkylation of benzyl alcohol and p-isopropylbenzyl exhibited more good yields than the citronellol with pmethylaniline. Also, because of similar nature of 2a-2e complexes, they had a no significant effect on the overall yield of the reaction. C, 20 h. [b] Yields (%) were calculated according to p-methylaniline by GC-MS analysis using dodecane as an internal standard. [c] Selectivities (%) of 4a and 4b were calculated by GC and GC-MS analysis.

When 2,4-dimethylaniline was used as substrate, the reaction became more difficult and yields of N-(benzyl)-2,4dimethylaniline (5aa) 69-77% only could be obtained with benzyl alcohol as respective partners after 20 h (Table 5, entries 1-5).

2,4-Dimethylaniline reacted also with 4-methoxybenzyl alcohol to give the N-(4-methoxybenzyl)-2,4-dimethylaniline (5ab) in 73-80% yields (Table 5, entries 6-10). The results obtained show that the steric hindrance in the ortho-position of the aniline substrate partially inhibits the reaction.

With ruthenium catalysts, only a few examples of alkylation of 2-aminopyridine with alcohols have been recently reported with ruthenium complexes featuring tridentate (C,N,N) ligand [35], and cationic ruthenium(arene) complex equipped with a chelating pyridine-carbene ligand [36]. In the presence of our optimized catalytic systembased on 2a-2e catalysts, the primary heteroaromatic 2-aminopyridine reacted readily with various alcohols to selectively give the N-mono-alkylated secondary amines (6a), (Table 6). Benzyl alcohol and p-isopropylbenzyl alcohol gave excellent yields of N-alkylated 2-aminopyridines (6aa and 6ab) (Table 6, entries 1-10). Alkylation with the purely aliphatic alcohol derivative 1-hexanol was also possible in satisfactory yield (6ac) (Table 6, entries [11][12][13][14][15]. When Table 6 is examined, it is observed that alcohols with aromatic rings give higher yields of N-alkylated product than 1-hexanol. Only the amine products (6a) were observed in all reactions. C, 20 h. [b] Yields (%) were calculated according to 2,4-dimethylaniline by GC-MS analysis using dodecane as an internal standard. [c] Selectivities (%) of 5a and 5b were calculated by GC and GC-MS analysis. C, 20 h. [b] Yields (%) were calculated according to 2-aminopyridine by GC-MS analysis using dodecane as an internal standard. [c] Selectivities (%) of 6a and 6b were calculated by GC and GC-MS analysis. loading without additional base [32]. The presence of the functionalized benzyl and alkyl group in our NHC precursors does not seem to be essential in terms of reactivity, but contributes to promote the formation of amines rather than imines or amides. This is very important in terms of selectivity.

Accepted Manuscript

FULL PAPER

All these results show that the nature of the NHC ligand is crucial for the ruthenium-catalyzed selective alkylation of anilines by alcohols with hydrogen borrowing processes.

Accepted Manuscript

FULL PAPER

However, at the moment, the most efficient catalytic systems for alkylation of aromatic amines operating under really mild conditions are based on iridium catalysts. They include reactions carried out in diglyme at 70 °C in the presence of t BuOK [38], a few examples at 50 °C in toluene/CH2Cl2 as solvent in the absence of an extra base [39], and even some scarce examples at room temperature in the presence of t BuOK under solvent-free conditions with 1 mol% catalyst loading [40].

Conclusions

In summary, we prepared a library of five new well-defined Nheterocyclic carbene based ruthenium(p-cymene) complexes.

These complexes were characterized using different spectroscopic and analytical techniques. Ruthenium complexes were used as the efficient and selective catalysts in the synthesis of N-alkylaromatic amines using N-alkylation reaction between the aromatic amines and alcohol derivatives under solvent-free conditions and mild conditions. When the catalytic studies were evaluated, it was found that all of the ruthenium complexes were suitable for the N-alkylation reaction of aromatic amines with alcohols by borrowing hydrogen strategy. Since the ruthenium complexes are structurally similar, it is clear that, there is no significant difference between the complexes on the catalytic activity of N-alkylation of aromatic amines with alcohols, and the selectivity of the reaction strongly depends on the nature of the alcohols.

Experimental Section

General Methods: The synthesis of NHC precursors and their ruthenium complexes were carried out under argon using standard Schlenk line techniques. Melting points were measures in open capillary tubes with an Electrothermal-9200 melting points apparatus. FT-IR spectra were recorded on ATR unit in the range of 450-4000 cm -1 with a Perkin Elmer Spectrum 100 Spectrophotometer. 1 H NMR and 13 C NMR spectra were recorded using a Bruker Avance AMX and a Bruker Avance III spectrometer operating at 300, 400 and 500 MHz ( 1 H NMR) and at 75, arom. CHs, CH3C6H4(CH(CH3)2)-4); 8H,arom. CHs,. 13 8, 83.4, 85.2, 87.1 (arom. Cs of CH3C6H4(CH(CH3)2)-4); 99. 1, 109.5, 110.0, 111.2, 111.9, 112.4, 118.0, 123.1, 123.3, 130.0, 135.3, 135.9, 139.5, 160. 5.10, 5.34 and 5.52 (m, 4H, arom. CHs, CH3C6H4(CH(CH3)2)-4); 8H,arom. CHs,NC6H4N and

Accepted Manuscript

FULL PAPER

58.9 (CH2CH2OCH3); 72.0 (CH2CH2OCH3); 83.4, 84.7, 85.3, 86.5 (arom. Cs of CH3C6H4(CH(CH3)2)-4); 98. 1, 108.4, 111.3, 111.6, 111.7, 111.9, 112.4, 118.0, 123.1, 123.2, 130.0, 135.2, 135.5, 139.2, 139.3, 160 1, 107.7, 109.9, 110.6, 111.0, 111.5, 113.5, 117.1, 119.7, 122.0, 122.1, 128.5, 128.9, 134.0, 134.8, 138.3, 157. 6, 111.6, 111.7, 111.8, 112.7, 118.0, 123.1, 125.5, 125.8, 130.1, 134.4, 135.5, 135.6, 139.2, 150.5, 160.1 ( [START_REF]The Organic Chemistry of Aliphatic Nitrogen Compounds[END_REF][START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]4,[START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF]; 22.4 (CH3C6H4(CH(CH3)2)-4); 22.7 (CH3C6H4(CH(CH3)2)-4); 31,0 (CH3C6H4(CH(CH3)2)-4); 52.6 (CH2C6(CH3) [START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]4,[START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF]; 53.0 (CH2C6H4(OCH3)-3); 55.3 (CH2C6H4(OCH3)-3); 84. 6, 85.1, 85.5, 86.6 (arom. Cs of CH3C6H4(CH(CH3)2)-4); 96. 2, 107.4, 111.1, 111.7, 112.0, 112.5, 112.8, 122.4, 122.6, 129.3, 130.0, 135.4, 135.5, 135.6, 139.5, 160.2 (arom. Cs of NC6H4N, CH2C6H4(OCH3)-3 and CH2C6(CH3) [START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]4,[START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF]; Ru-Ccarbene: 190.3. Supporting Information (see footnote on the first page of this article):

General

Full 1 H NMR, 13 C NMR and FT-IR spectra for the benzimidazolium chlorides (1a-1e), ruthenium-(arene)-NHC complexes (2a-2e) and all catalytic products (3a-6a).

Figure 1 .

 1 Figure 1. Examples of biologically active benzyl-substituted amines.

Figure 2 .

 2 Figure 2. General mechanism of the "borrowing hydrogen" strategy.

  , B), bearing a chelating NHC-sulfonate ligand [33b], and the chelating ruthenium-NHC-arene complexes (Figure 3, C) were efficient catalysts for the N-alkylation of aniline and secondary cyclic amines by benzylic and aliphatic alcohols, and the regioselective C3-alkylation of N-protected secondary amines by aldehydes [34].

Figure 3 .

 3 Figure 3. Our previously published ruthenium-NHC complexes for the hydrogen borrowing reactions. Herein, we now describe the synthesis and characterization of the five novel ruthenium(II) complexes of the general formula [RuCl2(η 6 -p-cymene)(NHC)] (NHC = benzimidazol-2-ylidene), 2a-2e. These complexes were characterized by 1 H NMR, 13 C NMR, FT-IR spectroscopy techniques. Next, we examined the catalytic activity of all ruthenium complexes in the N-alkylation of aromatic amines with different alcohol derivatives under solvent-free conditions using the borrowing hydrogen strategy.

  adducts and [RuCl2(p-cymene)]2. The air and moisture-stable ruthenium complexes are brown in colour and soluble in common chlorinated organic solvents such as chloroform and dichloromethane. They are found to be diamagnetic and they were fully characterised by 1 H NMR, 13 C NMR and FT-IR spectroscopy. Their FT-IR data each show a band at 1453-1480 cm -1 (ν(NCN)) and their 13 C NMR spectra each display a singlet in the range 188., two evidences of the formation of a Ru-carbene bond. These spectroscopic values are in line with those found for other [RuCl2(p-cymene)(NHC)] complexes of the literature[33a,b,d]. For the 1 H NMR, 13 C NMR and FT-IR spectrums of the new ruthenium complexes 2a-2e see SI, pp. S11-S20.

  )imidazolylidene)] featuring aryl substituents directly connected to the nitrogen atoms of the carbene is known to catalyze the formation of amides from alcohols and primary aliphatic amines including aniline at a lower extend, in the presence of 15 mol% of t BuOK[37]. Recently, ruthenium complexes such as (N,N-bis(benzyl)benzimidazolylidene)-and (N,N-bis(isopropyl)benzimidazolylidene)-RuCl2(p-cymene) equipped with N-alkyl or/and N-benzyl NHC ligands with no chelating or hemilabile group on the NHC have revealed good catalytic properties for the alkylation of anilines with various alcohols under neat conditions at 130 °C with 5 mol% catalyst

100 and 125

 125 MHz ( 13 C NMR) in CDCl3. The NMR studies were carried out in high-quality 5 mm NMR tubes. The chemical shifts (δ) are reported in ppm relative to CDCl3. Coupling constants (J values) are given in hertz. NMR multiplicities are abbreviated as follows: s = singlet, d = doublet, t = triplet, pent = pentet, hext = hextet, m = multiplet. 1 H NMR spectra are referenced to residual protiated solvents (δ = 7.26 ppm for CDCl3), 13 C chemical shifts are reported relative to deuterated solvents (δ = 77.16 ppm for CDCl3). All catalytic reactions were monitored on an Agilent 6890N GC and a Schimadzu 2010 Plus GC-MS system by GC-FID with an HP-5 column of 30 m length, 0.32 mm diameter, and 0.25 μm film thickness. General Procedure for the Preparation of Benzimidazolium Chlorides (1a-1e): N-(3-Methoxybenzyl)benzimidazole (1.0 g; 4.2 mmol) was dissolved in degassed DMF (3 mL) and alkyl chloride (4.2 mmol) was added at room temperature. The reaction mixture was stirred at 80 °C for 36 h under argon. After completion of the reaction, the solvent was removed by vacuum and diethyl ether (15 mL) was added to obtain a white crystalline solid, which was filtered off. The solid was washed with diethyl ether (3×10 mL) and dried under vacuum. The crude product was recrystallized from ethanol/diethyl ether mixture (1:3, v/v) at room temperature and, completely dried under vacuum. All benzimidazolium chlorides (1a-1e) were isolated as air-and moisture-stable white solids in accordance with the literature [28g,m].General Procedure for the Preparation of Ruthenium-(arene)-NHCComplexes (2a-2e): For the preparation of ruthenium complexes, a solution of benzimidazolium chloride (1.0 mmol), Ag2O (0.5 mmol) and activated 4 Å molecular sieves in anhydrous dichloromethane(10 mL) was stirred at room temperature for 24 h in the dark conditions. The reaction mixture was then filtered through Celite and the solvent was removed under reduced pressure. The prepared crude silver-NHC complex was reacted with [RuCl2(p-cymene)]2 dimer (0.5 mmol) in anhydrous dichloromethane (10 mL), and the mixture was allowed to stirred for 24 h at room temperature. The solution was filtered through Celite and the solvent was removed under reduced vacuum to afford the product as a red-brown powder. The crude product was recrystallized from CH2Cl2/n-pentane(1:3, v/v).

  C NMR (100 MHz, CDCl3, 25 o C): δ (ppm) = 18.7 (CH3C6H4(CH(CH3)2)-4); 22.3 (CH3C6H4(CH(CH3)2)-4); 30.7 (CH3C6H4(CH(CH3)2)-4); 36.9 (CH3); 52.1 (CH2C6H4(OCH3)-3); 55.3 (CH2C6H4(OCH3)-3); 81.

  CH2C6H4(OCH3)-3); 13 C NMR (100 MHz, CDCl3, 25 o C): δ (ppm) = 18.3 (CH3C6H4(CH(CH3)2)-4); 22.5 (CH3C6H4(CH(CH3)2)-4); 30.6 (CH3C6H4(CH(CH3)2)-4); 50.4 (CH2CH2OCH3); 52.5 (CH2C6H4(OCH3)-3); 55.3 (CH2C6H4(OCH3)-3);

2 (

 2 (s, 3H, CH2C6H4(OCH3)-3); 5.09-5.12 and 5.33-5.38 (m, 4H, arom. CHs, CH3C6H4(CH(CH3)2)-4); 5.70-5.75 (m, 2H, CH2C6H4(OCH3)-3); 6.60-6.64 (m, 2H, CH2C6H4(C(CH3)3)-4);6.66-6.71, 6.82-6.84 and 7.01- 7.37 (m, 12H, arom. CHs, NC6H4N, CH2C6H4(OCH3)-3 and CH2C6H4(C(CH3)3)-4).13 C NMR (100 MHz, CDCl3, 25 o C): δ (ppm) = 18.Cs of CH3C6H4(CH(CH3)2)-4); 97.0, 107.

  arom. Cs of NC6H4N, CH2C6H4(OCH3)(400 MHz, CDCl3, 25 o C): δ (ppm) = 1.21 (d, J = 4.8 Hz, 6H, CH3C6H4(CH(CH3)2)-4); 2.01 (s, 3H, CH3C6H4(CH(CH3)2)-4); 2.17

and 2 .

 2 24 (s, 15H, CH2C6(CH3)[START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]4,[START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF]; 2.83 (h, J = 6.9 Hz, 1H, CH3C6H4(CH(CH3)2)-4); 3.69 (s, 3H, CH2C6H4(OCH3)-3); 5.23 (s, 2H, CH2C6H4(OCH3)-3); 5.43 (s, 2H, CH2C6(CH3)[START_REF]Amino Group Chemistry: From Synthesis to the Life Sciences[END_REF]4,[START_REF] Smith | March's Advanced Organic Chemistry[END_REF][START_REF] Gribble | [END_REF]; 5.51-6.56(m, 4H, arom. CH, CH3C6H4(CH(CH3)2)-4); 6.68-7.19 (m, 8H, arom. CH, NC6H4N, CH2C6H4(OCH3)-3).13 C NMR (100 MHz, CDCl3, 25 o C): δ (ppm) = 14.

  Procedure for the N-Alkylation of Aromatic Amines withAlcohols: Aromatic amine derivative (1.0 mmol), alcohol derivative (1.5 mmol), t BuOK (1.5 mmol), ruthenium complex (2a-2e) (0.015 mmol, 1.5 mol%) were added to a 10 mL Schlenk tube under argon atmosphere.The mixture was stirred at 120 °C for 20 h. The reaction was cooled room temperature and filtered through a short pad of SiO2. CH2Cl2 (2 mL) was then added to the crude mixture. This solution was used for GC and GC-MS analysis, and the resulting N-alkylated amines were purified and isolated by column chromatography (eluent: CHCl3/MeOH). Yields (%) were calculated according to aromatic amine derivative using dodecane as an internal standard. The chemical characterizations of the catalytic products were made by NMR spectroscopy.The catalytic products N-benzylaniline(3aa) [32c, 18p,v], N-(pisopropylbenzyl)aniline (3ab) [32c, 18y], N-(4methoxybenzyl)aniline (3ac) [32c, 18v], N-(3,7-dimethyloct-6-en-1-yl)aniline (3ad) [32c, 24c], N-(benzyl)-p-methylaniline (4aa) [32c, 18v], N-(p-isopropylbenzyl)-pmethylaniline (4ab) [32c, 18z], N-(3,7-dimethyloct-6-en-1-yl)-pmethylaniline (4ac) [32c], N-(benzyl)-2,4-dimethylaniline (5aa) [32c], N-) [32c, 18v], N-(p-isopropylbenzyl)-2-aminopyridine (6ab) [32c] and N-(hexan-1-yl)-2-aminopyridine (6ac) [32c] are known in the literature. For the 1 H NMR and 13 C NMR spectrums of the all catalytic products see SI, pp. S21-S32.

Table 1 .

 1 Physical and spectroscopic properties of new ruthenium complexes (2a-2e).

	Compound	Molecular formula	Isolated yield (%)	M.p. ( o C)	v(CN) (cm -1 )	C(2) (ppm) 13 C NMR
	2a	C26H30Cl2N2ORu	82	115-116	1458	190.3
	2b	C28H34Cl2N2O2Ru	75	148-149	1453	191.5
	2c	C35H40Cl2N2O2Ru	78	190-191	1465	188.8
	2d	C36H42Cl2N2ORu	65	201-202	1480	191.5
	2e	C37H44Cl2N2ORu	54	153-154	1454	190.3

Table 2 .

 2 Optimization of the reaction conditions for ruthenium catalyzed N-alkylation of aniline with benzyl alcohol.

	[a]

Table 2

 2

	reaction time was reduced from 24 h to 20 h at 120 °C, no
	noticeable effect on the yield was observed (Table 2, entry 9),
	but when the reaction time was reduced from 20 h to 16 h, the
	yield and selectivity dropped (Table 2, entry 10). As a result of
	the optimization experiments, a very good yield (97%) and
	selectivity (3aa/3ba, 94/6) was obtained with t BuOK as base and
	under solvent-free conditions, at 120 °C for 20 h (Table 2, entry
	9). It is known that in the absence of any additional ligand,
	[RuCl2(p-cymene)]2 alone does not catalyze efficiently the N-
	alkylation by primary alcohols even in refluxing toluene [20b].
	, entry 8). When the

Indeed, in the absence of any ligand only 15% yield was Accepted Manuscript observed (

Table 2 ,

 2 entry 11), and we checked that without any ruthenium precursor no reaction took place (Table2, entry 12).

Table 3

 3

	, entries 1-

Table 3 .

 3 Ruthenium-catalyzed N-alkylation of aniline with alcohols.

	[a]

Table 4 .

 4 Ruthenium-catalyzed N-alkylation of p-methylaniline with alcohols.

	[a]

[a]

Reaction conditions: [Ru] (2a-2e) (0.015 mmol, 1.5 mol%), p-methylaniline (1.0 mmol), alcohol (1.5 mmol), t BuOK (1.5 mmol), 120 o

Table 5 .

 5 Ruthenium-catalyzed N-alkylation of 2,4-dimethylaniline with alcohols.

	[a]

t BuOK (1.5 mmol), 120 o

Table 6 .

 6 Ruthenium-catalyzed N-alkylation of 2-aminopyridine with alcohols.

	[a]

t BuOK (1.5 mmol), 120 o

Accepted Manuscript

FULL PAPER

Five new ruthenium(II) complexes with the general molecular formula [RuCl2(NHC)(η 6 -p-cymene)], (NHC = N-heterocyclic carbene) were synthesized.

The obtained complexes were fully characterized by 1 H NMR, 13 C NMR and FT-IR spectroscopy techniques. The catalytic activity of the all ruthenium complexes have been evaluated in the N-alkylation of anilines with alcohol derivatives using the borrowing hydrogen strategy.

Ruthenium(II)-(arene)-N-Heterocyclic