Keywords: Décisions de groupe, Rangement de compromis, Ordres prudents Group decisions, Compromise ranking, Prudent orders

Supporting the search for a group ranking with robust conclusions on prudent orders

Claude Lamboray

Résumé

Nous analysons le problème où des rangements, fournis par exemple par des évaluateurs, doivent être agrégés en un rangement de compromis. Dans ce contexte, Arrow et Raynaud suggèrent que le rangement de compromis soit un ordre prudent. En général, un ordre prudent n'est pas unique. C'est pourquoi nous proposons de construire des conclusions robustes sur ces ordres prudents afin de gérer la possible multiplicité des solutions de compromis. Cette approche va permettre de progressivement raffiner le modèle d'aide à la décision. Nous illustrons notre approche sur un exemple de rangement de priorités de recherche par un groupe de jeunes chercheurs.

Introduction

Often decision problems that arise in companies or organizations involve a group of individuals. In particular we will focus on the problem where the judgment of different experts, evaluators or decision makers has to be taken into account in order to rank a set of alternatives from the best to the worst. This is typically the case in situations where a group of experts has to agree on a priority list. In the example that we will present at the end of this paper, a group of junior researchers was asked by a scientific funding agency to rank a set of research domains that should be developed in the medium and long term.

Although the group members all pursue a global goal, that is to take a good decision for their company or their organization, they can have a different opinion about how to rank the alternatives. In fact, they may have a different perspective on the problem or they may play a different role within the organization. Inevitably, conflicting preferences will emerge. In such a case, a group decision then consists in reducing the individual preferences into a collective preference (see Jelassi [START_REF] Jelassi | An introduction to group decision and negotiation support[END_REF]).

This problem be approached in a variety of ways, ranging from a simple ranking solely based on, let's say, cost to complex multicriteria group ranking techniques. De Keyser [START_REF] Dekeyser | Another way of looking at group decision making opens new perspectives[END_REF] differentiates between four types of multicriteria multidecision maker models. The last of these four types consists of an approach where, first, each group member explicitly states his individual ranking. In a second stage, mechanisms and tools are then needed that aggregate or combine this multi-dimensional ordinal data into a new, so-called compromise or group ranking. In this paper we are going to adopt such an approach. As argued by De Keyser [START_REF] Dekeyser | Another way of looking at group decision making opens new perspectives[END_REF], this consequently leaves a large amount of freedom to each group member on how to perform his evaluation and construct his personal ranking.

Many ordinal ranking rules have been proposed since more than 200 years. Borda [START_REF] Borda | Mémoire sur les élections au scrutin[END_REF] is one of the first who examined the problem. His rule consists in ranking the alternatives according to the sum of ranks. Some other rules have been proposed where the score of each alternative naturally defines a weak order, such as for instance the rules proposed by Copeland [START_REF] Copeland | A 'reasonable' social welfare function[END_REF] or Simpson [START_REF] Simpson | On defining areas of voter choice: Professor Tullock on stable voting[END_REF]. The Maximize agreement heuristic proposed by Beck and Lin [START_REF] Beck | Some heuristics for the consensus ranking problem[END_REF] is slightly different since it follows a ranking by choosing scheme. From a different perspective, many ranking rules have been modeled as optimization problems. The compromise ranking is a linear order that optimizes a certain objective function. The most known such rule has been proposed by Kemeny [START_REF] Kemeny | Mathematics without numbers[END_REF], but let us also mention the rules proposed by Slater [START_REF] Slater | Inconsistencies in a schedule of paired comparisons[END_REF], Bernardo [START_REF] Bernardo | An assignment approach to choosing R&D experiments[END_REF], Blin [START_REF] Blin | A linear assignement formulation fo the multiattribute decision problem[END_REF] and Cook and Seiford [START_REF] Cook | Priority ranking and consensus formation[END_REF].

In this paper, we will present an approach to support the search for a compromise ranking using the concept of prudent orders. In fact, when working in an "industrial" or "business-like" situation, then Arrow and Raynaud [START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF] suggested that the compromise ranking should be a prudent order. Intuitively, a prudent order is a compromise ranking such that the strongest opposition against this solution is minimal.

Throughout the paper, we will assume that the input data will consist of linear orders. This can be criticized, especially from an operational point of view. However, this assumption will simplify the underlying aggregation problem. This paper can also be seen as a first step toward designing a similar decision aid tool which would allow for more complex preference structures. Prudent orders will be presented in section 2. The methodological framework of our approach will be motivated more in depth in section 3. In section 4, we will compute robust conclusions on these prudent orders. We will discuss an adaptation step in section 5. The concepts introduced are illustrated on an example in section 6. We end this paper with a conclusion. All the proofs can be found in the appendix.

Prudent orders

Let us suppose that a set of alternative has been clearly established and that this set will remain stable during the whole decision process. We will assume that each group member will propose a linear order (antisymmetric, complete and transitive binary relation). These linear orders have then to be aggregated into a group ranking.

Formally, let O denote the set of all linear orders over a finite set of n alternatives A = {a 1 , a 2 , . . . , a n }. Let u = (O 1 , O 2 , . . . O q ) ∈ O q be a profile of q linear orders of the q group members. A valued relation S counts the number of rankings that prefer a i over a j :

S ij = |{k ∈ {1, . . . , q} : (a i , a j ) ∈ O k }|
Since the relations O k are linear orders, it is easy to see that for i = j we have S ij + S ji = q. This is called the constant sum property.

Let λ ∈ {0, . . . , q}. Let R ≥λ (R >λ ) be a cut-relation of S defined as follows:

S ij ≥ λ ⇒ (a i , a j ) ∈ R ≥λ and S ij > λ ⇒ (a i , a j ) ∈ R >λ .
When λ = 0, R ≥λ contains all the ordered pairs. By increasing the value of λ, less pairs of alternatives will belong to the cut-relation. At one point, it will no longer be possible that R ≥λ contains a linear order. In particular we are interested in the largest possible value of λ such that R ≥λ still contains a linear order. α = max{λ ∈ {0, . . . , q} : R ≥λ contains a linear order } When λ = q, then R >λ is empty. In particular, the relation R >λ does not contain any cycles. By decreasing the value of λ, the relation R >λ will contain a cycle at some point. We are interested in the smallest value of λ such that the corresponding strict cut-relation is acyclic. β = min{λ ∈ {0, . . . , q} : R >λ is cycle-free }

The following theorems establish the links between these two relations.

Theorem 1 [START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF] [START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF] (page 93) If the constant sum property holds, then any linear order O containing R >β is contained in R ≥α and any linear order contained in R ≥α also contains R >β . Furthermore, α + β = q.

Arrow and Raynaud [START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF] (see axiom V' page 95) thus proposed that the compromise ranking should be a prudent order.

Definition 1 A prudent order O is a linear order that contains R >β and is contained in R ≥α : R >β ⊆ O ⊆ R ≥α .
We will denote by PO = {O ∈ O : R >β ⊆ O ⊆ R ≥α } the set of all prudent orders. The authors justify this approach to be prudent by the fact that ordered pairs of alternatives that belong to the relation R >β are pairs with no contradiction and a high support. If these pairs would not belong to the final compromise ranking, there would be a large and non-divided coalition against such a ranking. On the other hand, a group ranking which is not contained in R ≥α has at least one ordered pair of alternatives (a i , a j ) such that S ij is strictly smaller than α. That is why such a group ranking should be discarded.

Let us remind the reader that the transitive closure of a relation R, denoted by t(R), is the smallest relation that is transitive and that contains R. Furthermore, a linear extension of a relation R is a linear order O ∈ O that contains this relation: R ⊆ O.

Proposition 1

Let O be a linear order. The following statements are equivalent.

1. O is a prudent order 2. O is an optimal solution of max O∈O min (a i ,a j )∈O S ij 3. O is an optimal solution of min O∈O max (a i ,a j ) ∈O S ij

4. t(R >β ) ⊆ O
Point 2 states that a prudent order is a ranking that maximizes the weakest link. Equivalently, point 3 states that a prudent order is a ranking that minimizes the strongest opposition. Let us note that these results are only valid when the constant-sum property is satisfied.

One can show that the transitive closure of a cycle-free relation is a partial order (reflexive, transitive and antisymmetric relation). Since R >β is cycle-free, then, following point 4 of proposition 1 PO can be seen as the set of linear extensions of the partial order t(R >β ). This equivalence between linear extensions of a partial order and prudent orders will be useful, from a practical point of view, to perform the computations introduced in the next sections.

The properties of prudent orders have been analyzed by Debord [START_REF] Debord | Axiomatisation de procédures d'agrégation de préférences[END_REF] (chapter 6) and by Lansdowne [START_REF] Lansdowne | Ordinal ranking methods for multicriterion decision making[END_REF]. Let us point out that prudent orders verify unanimity: if an alternative a i is preferred to another alternative a j in all the rankings, then a i will also be preferred to a j in all the prudent orders. Another important characteristic of prudent orders is that they are Condorcet-consistent: in case the majority relation1 is a linear order, this will be the unique prudent order. Let us also refer the interested reader to the axiomatic characterization of the prudent order preference function presented in [START_REF] Lamboray | An axiomatic characterization of the prudent order preference function[END_REF].

Prudent orders are interesting because they synthesize the profile not necessarily into one but into a whole range of possible compromise rankings. Hence they do not completely act as an aggregation operator on the profile, but rather tend to reformulate the information contained in the initial rankings.

If there are more contradictions in the initial orders, then cycles may appear more easily. This means that β will be larger and, consequently, α will be smaller. As the two relations R >β and R ≥α drift further apart, the number of prudent orders will increase, until the trivial case where every linear order on A is a prudent order (see for instance [START_REF] Lansdowne | Outranking methods for multicriterion decision-making : Arrow's and Raynaud's conjecture[END_REF] for such an example). In fact, a direct corollary of point 4 of proposition 1 is that the size of PO is equal to the number of linear extensions of the partial order t(R >β ). This number can increase dramatically as the number of incomparable pairs in the partial order increases. In that context, let us mention Debord [START_REF] Debord | Axiomatisation de procédures d'agrégation de préférences[END_REF] (chapter 6), who performed simulations to estimate the number of prudent orders for small profiles. For instance, the

S a b c d min a . 3 2 1 1 b 2 . 3 2 2 c 3 2 . 3 2 d 4 3 2 . 2 S a b c min a . 3 2 2 b 2 . 3 2 c 3 2 . 2 S a b min a . 3 3 b 2 .
2

Figure 1: Obtaining the prudent order dcab with Kohler's rule.

average number of prudent orders of profiles with 7 alternatives and 10 rankings is 134.

One way of finding a prudent order is to use Kohler's ranking rule [START_REF] Kohler | Choix multicritère et analyse algébrique de données ordinales[END_REF], since every solution found by this rule must be a prudent order ( [START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF], page 103). This rule can be seen as a sequential maxmin rule: at step r, identify the minimum along each row of S. Select the row such that the minimum is maximum. If there are ties, choose one arbitrarily. This row corresponds to the alternative that will be put at rank r in the ranking. Delete the row and the column corresponding to the selected alternative. Furthermore, one can show ( [START_REF] Kohler | Choix multicritère et analyse algébrique de données ordinales[END_REF][START_REF] Arrow | Social Choice and Multicriterion Decision-Making[END_REF]) that the smallest of these successive maxima corresponds to α.

However, Kohler's rule is not sufficient to find the whole set of prudent orders (see Lansdowne [START_REF] Lansdowne | Outranking methods for multicriterion decision-making : Arrow's and Raynaud's conjecture[END_REF] for a counter example). A straightforward algorithm to enumerate all the prudent orders is as follows: apply Kohler's rule once. Find the value of β = qα. Compute R >β and t(R >β ). Apply an algorithm that enumerates all the linear extensions of a partial order. For instance, Pruesse and Ruskey [START_REF] Pruesse | Generating linear extensions fast[END_REF] proposed an algorithm that generates all the linear extensions in constant amortized time, which means in O(|PO|).

In figure 1, we illustrate this on the profile u = (abcd, bcda, cdab, dabc, dcba). For instance, the prudent order dcab will be obtained using Kohler's rule. The smallest of the coefficients selected is min{2, 2, 3, 2} = 2. Hence, α = 2 and β = qα = 5 -2 = 3. The set of prudent orders thus corresponds to all the linear extensions of the t(R >3 ) = R >3 = {(d, a)}. These 12 prudent orders are listed in figure 2.

Although we do not want, a priori, to discard any prudent order, it can sometimes be useful to select a few "good" prudent orders. In order to discriminate between the prudent orders, different approaches can be considered:

• Evaluate each prudent order O ∈ PO according to the sum of the outranking coefficients (a i ,a j )∈O S ij and select the prudent orders with the largest evaluation. Let us note that, if the Kemeny order [START_REF] Kemeny | Mathematics without numbers[END_REF] is also a prudent order, this approach will select a Kemeny-optimal order. However, by adopting a sum-operator, the ordinal aspect of the model of prudent orders will be lost.

• Among all the linear orders, prudent orders are those that maximize the weakest link. Among all the prudent orders, select the ones that maximize the second weakest link. Among, these, select the ones that maximize the third weakest link. Repeat the procedure n(n-1)

2

times or until there is only one linear order left. This procedure comes down to refining prudent orders, which are min-optimal solutions, by so-called leximin-optimal solutions (see for instance Fishburn [START_REF] Fishburn | Lexicographic orders, utilities and decision rules: A survey[END_REF] for a formal definition of the lexicographic criterion). The interest of this procedure is its complete ordinal character. It simply follows the prudent logic to its end. This is illustrated in figure 2. In the second column of this table, a vector

(S i 1 i 2 , S i 1 i 3 , . . . , S i 1 in , S i 2 i 3 , . . . , S i n-1 in )
corresponding to the prudent order O = a i 1 a i 2 . . . a in is indicated. In the third column, this vector is ordered. One can see that the ranking cdab is both optimal under a sumoperator and under the lexicographic rule.

A robust framework for using prudent orders

The basic assumption in this work is that the group agrees on the fact that the solution should be a prudent order. Although prudent orders are, in general, not unique, they will however depict a whole range of possible, potentially interesting, compromise solutions. Paradoxically, prudent orders have rarely been considered as an interesting aggregation mechanism, especially because of this multiplicity (see Debord [START_REF] Debord | Axiomatisation de procédures d'agrégation de préférences[END_REF], page 108 ). It will be this potential diversity of prudent orders that will be at the core of our approach.

The use in a decision aid context of ambiguous ranking rules, i.e. rules that possibly lead to more than one compromise ranking, has been addressed by Roy and Bouyssou [START_REF] Roy | Aide multicritère à la décision: méthodes et cas[END_REF] (pages 359-360) in the context of a ranking at minimal distance. First of all, the authors note that allowing multiple solutions does not really solve the problem of what ranking rule to use. Furthermore, such rules can favor ambiguities and misinterpretations, since the various ranking solutions can possibly be very contradictory. In the end, it is not a solution to our problem, since the aim is to construct one unique compromise ranking.

Although prudent orders may be appropriate in our setting, the choice of an ambiguous rule is still not an obvious task and can only be justified by a sound theoretic understanding of the ranking rule. However, in case a group actually accepts to use an ambiguous ranking rule (i.e. in our case prudent orders), then we feel that there is a need to actually exploit the existence of multiple compromise rankings and to support the group in selecting the "right" compromise ranking.

More particularly, we will suggest that the possible diversity of prudent orders will be handled by computing so-called robust conclusions, which, in the end, will support the group to select one prudent order. Following the terminology of Roy [START_REF] Roy | A missing link in operational research decision aiding: robustness analysis[END_REF], a robust conclusion will be an assertion valid for all the prudent orders. This scheme is illustrated in figure 3.

Initially, the concept of robustness has been presented as a way to handle decision problems with imprecise, uncertain, ill-defined and generally badly known parameters (see Bisdorff [START_REF] Bisdorff | Concordant outranking with multiple criteria of ordinal significance. a contribution to robust multicriteria aid for decision[END_REF] and Dias [START_REF] Dias | On computing ELECTRE's credibility indices under partial information[END_REF][START_REF] Dias | ELECTRE TRI for groups with imprecise information on parameter values[END_REF][START_REF] Dias | Dealing with imprecise information in group multicriteria decisions: a methodology and a GDSS architecture[END_REF]). In our setting however, the robustness issue arises conceptually because of the non-uniqueness of a compromise ranking, which can be seen as a consequence of the difficulty and ambiguity of aggregating ordinal data.

More generally, Dias [START_REF] Dias | An note one the role of robustness analysis in decision-aiding processes[END_REF] distinguishes between three roles of robustness in decision aid. A first approach sees robustness as an ex-ante concern, where a robustness criterion, such as for instance the maxmin criterion, is defined and optimized. In a second approach, robustness is seen as an ex-post concern, where the various solutions that can be obtained from the various versions of the decision aid problem are analyzed, but not aggregated anymore. This is in line with the ideas of robust conclusions of Bernard Roy. Finally, in a third approach, robustness is used as a tool to progress in a decision aid process, for instance by helping to refine some parameters of the decision model. This work can be seen as a contribution that combines the last two roles and uses robustness both as an ex-post exploitation procedure and as a refinement tool in a decision aid process.

Concerning the ex-post exploitation, we will compute the intersection of the prudent orders, the best and worst rank that an alternative can occupy in all the prudent orders and the maximal (or minimal) rank differences between any two alternatives.

One potential benefit of this approach relies in the fact that the information contained in the set of prudent orders will be captured while reducing the cognitive load. The solutions will be explicitly delimited, which can help the group to better understand the possibilities of comprise solutions.

Furthermore, the fact that different prudent orders can be contradictory will not be perceived as a problem anymore. The quality of the robust conclusions obtained will be inversely proportional to the degree of contradictions contained in the initial profile. Incomparabilities in the intersection, different best and worst ranks and large maximal rank differences and will point out problematic alternatives or parts of the compromise ranking. Hence, the group has to concentrate on these parts in order to reach a final compromise ranking.

Following the ideas of Dias, the robustness concept will also be used as a tool to progressively refine a decision model. In fact, by agreeing on some parts and by adapting accordingly their individual rankings, the group will gradually move toward a compromise ranking. The following four steps can thus be considered:

Data collection step

First every decision maker proposes his individual ranking. This ranking can be obtained, for instance, by a multicriteria method of his choice.

Aggregation step

The profile given by the group will define a set of prudent orders. If requested, within this set of rankings, an automatic procedure can select the "best" one, according to some predefined criteria, such as for instance the lexicographic criterion or the sum criterion introduced in the previous section. This ranking is then proposed to the group. Either the group accepts this solution, and the procedure stops, or the group proceeds to the next step.

Analysis and discussion step

The set of prudent orders can be described and analyzed by various robust conclusions. Such information will help the group to understand the current possible compromise solutions.

Adaptation step

Through the information learned from the previous step, each decision maker has the possibility to adapt his individual ranking in order to converge toward one compromise ranking. The group then proceeds back to step 1.

It is important to note that during the whole process, no solution will be imposed to the group. The robust conclusions that will be presented to the group can be considered as a guidance.

Since the number of prudent orders can increase dramatically as the number of alternatives increases and as the contradictions in the profile increases, complete enumeration will soon become infeasible, from a computational point of view. Fortunately, for all the conclusions that we will present, no complete enumeration of all the prudent orders will be necessary. This means that the robust conclusions can be directly deduced from the profile (see figure 3). In fact, the computations will be solely based on the equivalence between prudent orders and linear extensions.

Although we are mainly concerned with prudent orders, the proposed robust methodology can be extended to any other set of potentially interesting compromise rankings.

For instance, an ad-hoc solution that is used in practice is to consider all the solutions obtained by a set of different popular ranking rules (see for instance Colson [8]). In a way, a new rule is defined by combining existing rules. The idea behind this is to achieve either a confirmation of the results or to highlight at least different types of possible results since each ranking rule has its own logic and consequently treats the data from its own perspective. Such a more pragmatic approach thus also fits well into our robust scheme.

Computing robust conclusions

Instead of explicitly considering the prudent orders belonging to PO, we are going to describe them by their intersection (section 4.1), by the possible ranks that an alternative can occupy (section 4.2) and by the maximal rank differences between two alternatives (section 4.3). Although rank ranges and rank differences can be easily understood by a group, their cardinal character should be handled with care, especially in view of the ordinal character of the prudent order model.

Intersection

A natural robust conclusion is to state that an alternative a i is preferred to an alternative a j in all the prudent orders of PO:

(a i , a j ) ∈ O ∀O ∈ PO
This is equivalent to stating that (a i , a j ) belongs to the intersection of all the prudent orders. We know from point 4 in proposition 1 that the set PO is equivalent to all the linear extensions of the partial order P = t(R >β ). Since the intersection of all the linear extensions of a partial order is the partial order itself (see Dushnik and Miller [18]), we have :

O∈PO O = t(R >β ) = P
Hence, we do not need to explicitly enumerate all the prudent orders of PO in order to know their intersection. Instead it suffices to compute one transitive closure. The transitive closure can be computed by using for example Roy and Warschall's algorithm [START_REF] Warschall | A theorem on boolean matrices[END_REF].

Reciprocally, given P , every linear extension of this partial order is a prudent order. One may show that ∀(a i , a j ) ∈ R >β , S ij > q 2 . However, it can happen that a i will be preferred to a j in all the prudent orders although S ij is less than q 2 (but always larger than α = qβ), since (a i , a j ) has been added to R >β by transitivity.

Let us note that the P relation can be interpreted as the minimal compromise that can be reached with a given profile. In case, the group members are willing to achieve a stronger compromise, they should bring closer their individual rankings with this P relation. This issue will be further addressed in section 5.

Rank range

Let us now concentrate on the possible ranks of an alternative in the compromise ranking. By convention, if an alternative is ranked first in a linear order O, it has rank 1, if it is ranked second, it has rank 2 and so on. We denote by ρ O (a i ) the rank of alternative a i in the linear order O. Let ρ + i and ρ - i be the best and the worst rank a given alternative a i occupies :

ρ + i = min O∈PO ρ O (a i ) and ρ - i = max O∈PO ρ O (a i ).
Maximal and minimal ranks in an aggregation procedure have already been suggested by Guénoche [START_REF] Guénoche | Vainqueurs de Kemeny et tournois difficiles[END_REF] in the context of determing median orders of difficult valued tournaments. However his motivation was rather algorithmic than conceptual.

Since the set PO consists of all the linear extensions of the partial order t(R >β ), one can show that (see for instance [START_REF] Bruggemann | Applying the concept of partially ordered sets on ranking of near shore sediments by a battery of tests[END_REF]) the best rank and the worst rank can be computed as follows:

ρ + i = |N + i | where N + i = {a j : (a j , a i ) ∈ t(R >β )} (1) ρ - i = n + 1 -|N - i | where N - i = {a j : (a i , a j ) ∈ t(R >β )} (2)
Once ρ + i and ρ - i are computed, a robust conclusion would be to state that the rank of alternative a i is higher or equal than ρ + i and smaller or equal than ρ - i . Furthermore, for each r such that ρ + i ≤ r ≤ ρ - i , we know that there exists at least one prudent order where alternative a i has rank r. Hence, apart from extreme rank values, the whole rank range is covered.The difference ρ - iρ + i , which is called the variability of a i by Bruggemann [START_REF] Bruggemann | Applying the concept of partially ordered sets on ranking of near shore sediments by a battery of tests[END_REF], gives an indication about the degree of contradictions or uncertainties concerning the alternative a i . In fact, the bigger this difference is, the more unclear it is assigning a rank in the compromise ranking to a i .

Maximal rank differences

We are interested in the largest possible rank difference between alternative a j and alternative a i . This difference quantifies the possible advantage of an alternative a i over an alternative a j .

Formally, we would like to compute:

∆ max ij = max O∈PO (ρ O (a j ) -ρ O (a i ))
More precisely, if ∆ max ij ≥ 0, then this means that, at best, alternative a i is ranked ∆ max ij positions ahead of alternative a j . If ∆ max ij < 0, then this means that a i will always be at least ∆ max ij ranks below a j .

These quantities can be computed as follows:

Proposition 2

∆ max ij = n + 1 -(|N - j | + |N + i |) if (a j , a i ) ∈ t(R >β ) |N - i ∩ N + j | -1 if (a j , a i ) ∈ t(R >β )

Adaptation step

Let us suppose that the rankings u = (O 1 , O 2 , . . . , O q ) provided by the experts have been aggregated into the set of prudent orders PO. Let us note that a unique final compromise ranking has not been reached so far. The robust information introduced in the previous section should help the group to understand the current the current possibilities of compromise. We then consider the following two possibilities:

1. Several or all the group members agree to adapt their rankings. This new profile will lead to a completely new set of prudent orders. The analysis explained in the previous section can then be reapplied to that new set of prudent orders.

2. The group can agree on an ordered block partition of the alternatives. For instance, the group agrees on the fact that a and b occupy the first two positions of the compromise ranking, whereas the remaining alternatives have at least rank 3. This is an example of a 2-block partition, but, more generally, we can consider any ordered block partition B 1 , B 2 , . . . B r of A. Each block can then be reexamined separately.

We will now analyze the possible convergence of the set of prudent orders in this two possibilities. To do so, let us denote by

u new = (O new 1 , O new 2 , . . . , O new q
) the new rankings of the group members. Let us recall that P is the intersection of all the prudent orders of the initial profile. This relation P will be crucial when analyzing the possible convergence of the compromise.

We say that the adaptation from O i into O new i is not against the compromise if:

∀a i , a j : (a i , a j ) ∈ O new ∧ (a i , a j ) ∈ O ⇒ (a i , a j ) ∈ P. Proposition 3 If the adaptation from O i into O new i is not against the compromise ∀i = 1, . . . , q, then PO(u new ) ⊆ PO(u).
Hence if the adaptations of all the group members are in favor of the compromise, then convergence is ensured. Hence it is reasonable to encourage the group to agree with P as much as possible. However, the group should not be obliged to stick to this type of adaptations and the possibility should be given to slightly shift the focus of the set of prudent orders. Hence, it may happen that, after adapting individually, the new rankings

(O new 1 , O new 2 , . . . , O new q
) together may yield new contradictions and cycles, avoiding thus a clear convergence.

Second, let us suppose that the group applies the ordered block partition approach. Let B 1 , . . . , B r be an ordered block partition of the alternatives. We say that this partition is compatible with the compromise if:

∀a i , a j s.t.a i ∈ B k a j ∈ B l k < l ⇒ (a j , a i ) ∈ P
When examining the blocks separately, the next proposition says that the set of compromise rankings can possibly converge. Let u B be the profile restricted to the alternatives belonging to a block B i . PO(u B i ) thus corresponds to the prudent orders of that restricted profile. Furthermore, let (PO(u)) B i be the set of prudent orders of the profile u, but restricted to the alternatives of block B i . Proposition 4 Let B 1 , B 2 , . . . , B r be an ordered block partition compatible with the compromise. Then

∀B i : PO(u B i ) ⊆ (PO(u)) B i .

Example

In order to illustrate our approach, we present an example where a group of junior researchers, mainly working in the field of information technologies in various research institutions in Luxembourg, were asked to rank a set of research domains. The problem took place in the framework of the Foresight exercise [11] organized by the Luxembourg FNR (Fonds National de la Recherche). The aim of this project is to identify socioeconomic needs in order to decide on scientific research domains for Luxembourg in the medium and long term.

To achieve this goal, stakeholders were involved and, in particular, a one day workshop was organized for a group of junior researchers. During that day, 40 different research domains were put forward, amongst which 11 were finally selected as the most pertinent by the group of participants. They are listed in figure 1. The actual workshop ended at this stage.

The participants were asked after the workshop to rank these research domains. This ranking should represent their view on the prioritization of the different research domains. Let us stress that this is not an application, but only an illustration of the methodology presented in this paper. After having submitted their individual rankings, the researchers were not confronted with the results presented in this section.

Since it can be difficult for a participant of the workshop to quantify the difference of importance between two research domains, it is reasonable to use an ordinal scale. Furthermore, working with rankings as input avoids to fix a common evaluation method for the whole group.

The rankings of the 10 researchers are represented in table 2. This profile of 10 linear orders with 11 alternatives will lead to 1350 prudent orders, which means that 1350 11! = 0.0034% of all the linear orders on 11 alternatives are prudent orders. A straightforward choice of one prudent order seems to be practically impossible. In order to go on with the decision process, several robust informations will be computed.

First of all, the intersection of all the prudent orders is represented in figure 4 (the transitivity arcs are omitted). We can learn from this figure that, for instance, a 4 (Electronic cooperation networks) is preferred to a 7 (Finance and Banking sector) in all the prudent orders.

The rank ranges are depicted in table 3. For instance the rank of a 4 (Electronic co- Table 3: The rank ranges operation networks) will be either 1 or 2. On the other hand, the rank of a 6 (Innovative materials) seems to be unclear since, at best this alternative has rank 4 but at worst it is ranked last.

a 1 Knowledge management technology a 2 E-Government a 3 IT
Finally, the maximal rank differences are depicted in table 4. For instance, at best, a 1 (Knowledge management technology) can be six ranks ahead of a 2 (E-Government), whereas a 2 can only be, at best, one rank ahead of a 1 . There are also negative maximal rank differences. For instance, a 11 (Artificial Intelligence) will always be at least 3 ranks below a 1 .

Among the 1350 prudent orders, there are 18 orders which are optimal under the lexicographic rule. One of these rankings, could be automatically proposed to the group. Another possibility is to perform robust conclusions on these 18 rankings. For instance, the best and worst rank of each alternative in all these rankings are indicated in table 5. This information is of course consistent with the information in table 3, since lexicographic orders are a refinement of prudent orders. However, unlike for prudent orders, the extreme ranks of lexicographic optimal orders do not determine rank ranges: for instance, we know that there exists at least one lexicographic order where a 6 has rank 7 and at least one where a 6 has rank 11, but we do not have any guarantee that there also exists at least one lexicographic order where a 6 has rank 8, 9 or 10.

When analyzing the rank ranges of prudent orders, apart from the more problematic alternative a 6 (Innovative materials), let us assume that the group agrees to adopt the block partition approach in order to move toward a compromise. Let us suppose that does not really belong to the first block. Taking a closer look at the rank differences of a 6 , the group may agree on the fact that a 6 belongs also to the middle block. In fact, its ability to be much higher ranked than a 9 , a 10 and a 11 does not make it a very bad alternative neither. Consequently, a 6 fits best in the middle part of the global ranking. Let us note that this 3 block partition is compatible with the P relation.

Given the 3 block partition, the new rankings of the 10 participants can be found in table 6. We then compute the set of prudent orders separately in each block. Given this new data, the intersection of all the prudent orders can be found in figure 4 (the transitivity arcs are omitted). The final ranking is now almost complete. In fact, the still incomparable pairs are pairs that are completely indetermined in the sense that there are always five group members who prefer the first over the second alternative and five group members who prefer the second over the first alternative. In order to achieve a complete ranking, the group now has to concentrate on these pairs. As a conclusion, the 10 group members can agree on the following compromise ranking. The most important research domains are Knowledge management technologies and Electronic cooperation networks. These two domains are then followed by Mobile Communications and IT security. Although E-Government is perceived as more important than Innovative materials, the precise rank of Finance remains unclear in the middle of the ranking. It follows Business Improvement research. Finally, Artificial Intelligence followed by Human-Machine interface research can be found at the bottom of the compromise ranking. The final position of Image processing has still to be discussed in this

Conclusion

In this paper, we suggest to better exploit the multiplicity of solutions when working with ambiguous ranking rules, and in particular with prudent orders. Instead of imposing one final compromise ranking, potentially interesting compromise rankings are described with robust conclusions, which allows the group to progressively refine the decision model and progress toward a compromise ranking in an interactive way.

In our approach, we suppose that the group has to agree on some parts of the ranking and consequently each group member has to adapt his ranking. A future research direction is to develop tools that suggests to the group "good" block. A tool may also be needed to support the group members in adapting their ranking. Another research direction is to quantify and detect the conflict (in the prudent order sense) within the group.

We presented an example with 11 alternatives and 10 group members. Although from a computational point of view, the approach seems widely applicable, a question that needs further investigation is to determine for what type of problems (number of alternatives, size of the group, degree of conflict) this prudent and robust approach actually presents the most benefits from a decision aid point of view.

Finally, a potentially useful direction of further research is to develop a decision aid tool which follows the philosophy presented in this paper, but which could handle both on the input side (i.e the ordinal data received from the group members) and on the output side (i.e. the compromise solutions) more complex preference structures than just linear orders.

∆ max ij ≤ n + 1 -(|N - j | + |N + i |
). We will prove that there exists one linear order O ∈ PO (i.e. one linear extension of t(R >β )) such that this upper bound can be reached.

A linear extension of a partial order can be constructed sequentially as follows: remove any maximal element from the partial order and rank it below the already ranked alternatives in the linear extension; stop the procedure when all the alternatives have been ranked. In our case, this procedure can be applied to the partial order t(R >β ). Let N + i and N - j be defined as in 1 and 2 and let Nij = A\(N + i ∪N - j ). First, we will rank all the alternatives belonging to N + i (ranking a i last ), then we will rank all the alternatives from Nij and finally we will rank all the alternatives belonging to N - j ( ranking a j first). One can show that at each step it is possible to find a maximal element in the relevant subset of alternatives. Let us also note that N + i ∩ N - j = ∅, because otherwise there would exist an alternative a t such that (a t , a i ) ∈ t(R >β ) and (a j , a t ) ∈ t(R >β ), which contradicts the fact that (a j , a i ) ∈ t(R >β ). Consequently, the rank of a i in this order is |N + i |, the rank of a j is n + 1 -|N - j | and so the rank difference between a i and a j will be n + 1

-(|N - j | + |N + i |). • (a j , a i ) ∈ t(R >β )
Since (a j , a i ) ∈ t(R >β ) implies that a j is always above a i in all the prudent orders of PO. Consequently we want a i to be as close as possible to a j . Since the alternatives of N - i ∩ N + j have to be anyway between a j and a i , we must have that ∆ max ij ≤ |N - i ∩ N + j | -1. We will prove that there exists one linear order O ∈ PO (i.e. one linear extension of t(R >β )) such that this upper bound can be reached by using the procedure described in the previous paragraph. First, we will rank the alternatives belonging to N + j \ N - i , then we will rank the alternatives belonging to N - i ∩N + j (ranking a i first and ranking a j last) and finally we will rank the remaining alternatives.

Proof of proposition 3:

Proof:

Let R >λ be the cut-relation at level λ and β be the optimal cut-value for profile u. Let R new >λ be the cut-relation at level λ and β new be the optimal cut-value for profile u new . Since the transformation from O i into O new i ∀i is not against the compromise, we have that:

R >β ⊆ R new >β ⊆ R >β ∪ {(a i , a j ) : (a i , a j ) ∈ O new k ∧ (a i , a j ) ∈ O k } ⇒ R >β ⊆ R new >β ⊆ R >β ∪ {(a i , a j ) : (a i , a j ) ∈ t(R >β )} ⇒ R >β ⊆ R new >β ⊆ t(R >β )
Since t(R >β ) is acyclic, R new >β is acyclic, which implies that β new ≤ β. Hence :

R ′ >β ′ ⊆ R ′ >β ⊆ R >β
This means that PO(u new ) ⊆ PO(u).

Proof of proposition 4:

Proof: Let O be a linear order on A.Then:

O ∈ PO(u) ⇐⇒ R >β ⊆ O
Let O ′ be a linear order on B and let (R >β ) B i be the cut relation of S at level β restricted to B i . Since B i belongs to an ordered partition which is compatible with P , we can show that:

O ′ ∈ (PO(u)) B i ⇐⇒ (R >β ) B i ⊆ O ′
Let β ′ be the smallest value such that the strict cut relation of S restricted to B i is acyclic.

Since (R >β ) B i is acyclic, β ≥ β ′ . Hence (R >β ) B i ⊆ (R >β ′ ) B i .
In total we have :

O ∈ PO(u B i ) ⇒ (R >β ′ ) B i ⊆ O ⇒ (R >β ) B i ⊆ O ⇒ O ∈ (PO(u)) B i

Figure 2 :

 2 Figure 2: The 12 prudent orders.

Figure 3 :

 3 Figure 3: Computing robust conclusions.

Figure 4 :

 4 Figure 4: The intersection of all the prudent orders before (left) and after (right) the adaptation.

a 1 a

 1 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 a

Table 1 :

 1 security a 4 Electronic cooperation networks a 5 Mobile Communications a 6 Innovative materials and techniques in construction a 7 Finance and Banking sector a 8 Business Improvement research a 9 Image processing a 10 Human-Machine interface a 11 Artificial Intelligence, multi-agent systems The 11 research domains uni1 a 4 a 5 a 3 a 2 a 8 a 7 a 1 a 11 a 10 a 9 a 6uni2 a 3 a 9 a 4 a 5 a 2 a 1 a 6 a 11 a 7 a 8 a 10 uni3 a 4 a 5 a 2 a 3 a 1 a 6 a 7 a 8 a 11 a 10 a 9 uni4 a 1 a 6 a 8 a 7 a 11 a 10 a 3 a 2 a 5 a 9 a 4 uni5 a 11 a 1 a 9 a 5 a 7 a 10 a 6 a 4 a 3 a 2 a 8 iee a 6 a 5 a 7 a 4 a 2 a 3 a 8 a 1 a 9 a 11 a 10 cvce a 1 a 10 a 3 a 4 a 5 a 2 a 8 a 7 a 11 a 9 a 6 tud1 a 1 a 4 a 5 a 8 a 7 a 3 a 2 a 9 a 10 a 11 a 6 tud2 a 7 a 8 a 1 a 4 a 3 a 9 a 10 a 11 a 5 a 6 a 2 lip a 4 a 1 a 2 a 5 a 6 a 7 a 10 a 9 a 3 a 11 a 8

Table 2 :

 2 The rankings of the 10 researchers

Table 4 :

 4 Maximal rank differences.

	alt. ρ + ρ -
	a 1	1	2
	a 2	6	6
	a 3	5	5
	a 4	1	2
	a 5	3	3
	a 6	7 11
	a 7	4	4
	a 8	7	8
	a 9	8 11
	a 10 9 11
	a 11 8 10

Table 5 :

 5 Best and worst rank of the lexicographic rankings. a 1 , a 3 , a 4 , a 5 a 2 , a 6 , a 7 , a 8 a 9 , a 10 a 11 uni1 a 4 a 5 a 3 a 1 a 2 a 8 a 7 a 6 a 11 a 10 a 9 uni2 a 3 a 4 a 5 a 1 a 2 a 6 a 7 a 8 a 9 a 11 a 10 uni3 a 4 a 5 a 3 a 1 a 2 a 6 a 7 a 8 a 11 a 10 a 9 uni4 a 1 a 3 a 5 a 4 a 6 a 8 a 7 a 2 a 11 a 10 a 9 uni5 a 1 a 5 a 4 a 3 a 7 a 6 a 2 a 8 a 11 a 9 a 10 iee a 5 a 4 a 3 a 1 a 6 a 7 a 2 a 8 a 9 a 11 a 10 cvce a 1 a 3 a 4 a 5 a 2 a 8 a 7 a 6 a 10 a 11 a 9 tud1 a 1 a 4 a 5 a 3 a 8 a 7 a 2 a 6 a 9 a 10 a 11 tud2 a 1 a 4 a 3 a 5 a 7 a 8 a 6 a 2 a 9 a 10 a 11 lip a 4 a 1 a 5 a 3 a 2 a 6 a 7 a 8 a 10 a 9 a 11

Table 6 :

 6 The adapted rankings of the 10 researchers three blocks will be identified. A first block could contain a 1 , a 3 , a 4 and a 5 , a second block could contain a 2 , a 7 and a 8 and a third block could contain a 9 , a 10 and a 11 . Furthermore, since, the best rank of a 6 is 4, a 6

The majority relation M is a binary relation defined as follows: (a i , a j ) ∈ M ⇐⇒ S ij > q

.

Acknowledgements

The author wants to thank Luis Dias for his valuable comments and suggestions around this work. His remarks have significantly improved the presentation of this paper.

Appendix

Proof of proposition 1: Proof:

• Equivalence between 1 and 3 Following theorem 1, O is a prudent order if and only if R >β ⊆ O.

Let us show that β = min O∈O max (a i ,a j ) ∈O S ij . Let us suppose by contradiction that there exists

Hence there exists β ′ < β such that R >β ′ is acyclic. This contradicts the definition of β.

This is equivalent to O optimal for arg min O∈O max (a i ,a j ) ∈O S ij , since β = min O∈O max (a i ,a j ) ∈O S ij .

• Equivalence between 1 and 4

Proof of proposition 2: Proof:

i and since (a j , a i ) ∈ t(R >β ) implies that there exists at least one prudent order where a i is above a j , we know that


Gossa Lô

Victor De Boer
email: v.de.boer@vu.nl

Stefan Schlobach
email: k.s.schlobach@vu.nl

Gayo Diallo
email: gayo.diallo@u-bordeaux.fr

Linking African Traditional Medicine Knowledge

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Traditional medicine (TM) denotes a heterogeneous set of diagnostic-and therapeutic practices that uses scientifically often unvalidated knowledge, orally passed on through generations. Its aim is to prevent, diagnose and treat physical and mental illnesses. The World Health Organization notes that African Traditional Medicine (ATM) plays a crucial role in Sub-Saharan Africa where it is the first line of treatment for ca. 80% of the population [START_REF] Antwi-Baffour | The place of traditional medicine in the african society[END_REF], thanks to its accessibility, affordability and embeddedness in the traditional belief systems [START_REF]World Health Organization: Traditional medicine strategy 2002-2005[END_REF].

As the use and availability of plants differs per region, lack of formalization not only raises safety concerns, but also risks the loss of critical knowledge [START_REF] Firenzuoli | Herbal medicine today: clinical and research issues[END_REF]. Formalizing TM knowledge can benefit the determination of medical effects of plants in terms of diseases and symptoms [START_REF] Kamsu-Foguem | Conceptual graph-based knowledge representation for supporting reasoning in african traditional medicine[END_REF]. Furthermore, bridging the gap between ATM and CM by integrating the former into formal health care systems can result in a deeper understanding of pathology and medical knowledge.

This paper presents a proof of concept on how Semantic Web technologies can contribute to the preservation and formalization of ATM, and its integration with CM. This is demonstrated by converting ATM datasets into machine-readable data and by connecting them to Linked Data knowledge graphs on the Web. Finally, the benefits of the presented concept will be shown by validating the use cases formulated below with the use of queries.

An illustration of how Web technologies can contribute to the representation of TM is the Traditional Chinese Medicine (TCM) Database System 3 . It has been maintained since 1984 by the Institute of Information on TCM, and contains over 1,100,000 items of data, divided over 40 categories. Furthermore, a semantic eScience infrastructure was established, in response to the sheer volume and diversity of TCM information and services that affect its interoperability [START_REF] Chen | Towards semantic e-science for traditional chinese medicine[END_REF].

The Linking Open Drug Data (LODD) project aggregated and added biomedical data (e.g. about drugs, TCM, diseases, etc.) to the Linked Data Cloud. Their focus is to facilitate the obtaining of new insights and finding unforeseen associations between entities. The data sets contain over 8.4 million RDF triples and 388,000 RDF links to external data sources [START_REF] Jentzsch | Linking open drug data[END_REF][START_REF] Samwald | Linked open drug data for pharmaceutical research and development[END_REF].

Case study and methods

We investigate the potential of Semantic Web technologies for the preservation and formalization of ATM knowledge through two use cases. The first concerns the difference in treatment in two regions in Madagascar. Both the availability of plant species in a region and the knowledge about treatment methods that is passed on in a community influence treatment practice. Formalizing these methods prevents loss of knowledge and can help ATM practitioners in rural regions to exchange knowledge and find new treatments. The second use case focuses on investigating differences between ATM practice in Senegal and Madagascar. This exchange of knowledge not only benefits ATM practitioners, but could also be a valuable contribution to drug discovery and pharmacology on a global scale.

Keur Massar Traditional Hospital. One dataset used was provided by Hôpital Traditionnel de Keur Massar4 in Senegal founded in 1980 by Professor Yvette Parès5 , who had years of experience working with traditional practitioners from different ethnic groups in Senegal. This hospital has a strong focus on phytotherapy along ATM traditions and produces medicinal plant preparations (about 1,000 products and recipes) from their botanical garden.

Datasets. Besides this dataset, two datasets on ATM practice in Madagascar were used. The first contains data on medicinal plants used to treat the six most frequent diseases in the Ambalabe rural community in Madagascar [START_REF] Rakotoarivelo | Medicinal plants used to treat the most frequent diseases encountered in ambalabe rural community, eastern madagascar[END_REF]. The second dataset contains data on the most used medicinal plants by communities in Mahaboboka, Amboronabo, Mikoboka, in Southern Madagascar [START_REF] Randrianarivony | The most used medicinal plants by communities in mahaboboka, amboronabo, mikoboka, southwestern madagascar[END_REF]. The most relevant attributes that were stored are: the hierarchy of plant names, plant parts, in addition to diseases, ailments and preparation & administration modes.

We then linked the plant-and disease data in our datasets to resources on BioPortal 6 and DBpedia 7 . The BioPortal REST API was used to search for URIs for terms across ontologies, such as the Human Disease Ontology 8 , the Symptom Ontology9 and SNOMEDCT10 . If no URI is found, a synonym of the term is entered or linked to a proper resource on DBpedia.

Dataset conversion and linking. Our three datasets (.CSV) were translated into RDF and linked to the target datasets. First, columns from the original tabular data are stored in a dictionary as values, and assigned to a new key object name: 'set2 99': [u'Emilia humifusa DC. Rakotoarivelo', u'Asteraceae', u'Infected wound', u'L', u'Angea', u'Cataplasm on wound', u'400', 0.02, u'ID', 25L] A new data model was created that does not use existing ontologies, with converted triples of the form atmData:set2 99 atmVocab:familyName dbpg:Asteraceae.

Results. The result of this conversion is a total of 13,028 triples, of 672 plant types that treat 1,799 health conditions. The data is available at a public GIT repository at https://github.com/biktorrr/linkedatmdata. For live browsing and querying, we provide a triple store endpoint at http://semanticweb. cs.vu.nl/linkedatm/home. The 672 set objects all have the same structure as the below RDF Turtle snippet shows.

atmData : s e t 2 9 9 atmVocab : a i l m e n t atmData : I n f e c t e d w o u n d ; atmVocab : binomialName atmData : E m i l i a h u m i f u s a DC. R a k o t o a r i v e l o ; atmVocab : familyName dbpg : A s t e r a c e a e ; atmVocab : p l a n t P a r t s "L"ˆˆxsd : s t r i n g ; atmVocab : p r e p a r a t i o n A d m i n i s t r a t i o n " Cataplasm on wound"@en .

New and existing prefixes are used to simplify SPARQL queries with: SELECT ? a i l m e n t ? f a m i l y ? binomialName ? p a r t s ? p r e p a r a t i o n WHERE { ? s atmVocab : familyName ? f a m i l y . ? s atmVocab : binomialName ? binomialName . ? binomialName r d f s : l a b e l ? b i n o m i a l . ? s atmVocab : genusType ? genusType . ? s atmVocab : a i l m e n t | atmVocab : d i s e a s e T r e a t e d ? a i l m e n t . ? a i l m e n t r d f s : l a b e l ? a i l m e n t L a b e l . ? s atmVocab : p l a n t P a r t s ? p a r t s . ? s atmVocab : p r e p a r a t i o n | atmVocab : p r e p a r a t i o n A d m i n i s t r a t i o n ? p r e p a r a t i o n . FILTER ( ? a i l m e n t L a b e l = " M a l a r i a "@en ) } GROUP BY ? a i l m e n t ? f a m i l y ? binomialName ? p a r t s ? p r e p a r a t i o n LIMIT 6

As Fig. 1 shows, differences in plant use and treatment of malaria occur even between neighboring regions. While the Ambalabe community uses several parts, the other regions predominantly use the leaves. Thus, LinkedATM could both contribute to collaborative knowledge sharing between communities, and preserve critical knowledge for future generations. The second case focuses on the difference in use of a specific plant species between Senegal and Madagascar.The Sclerocarya birrea tree grows in both Southern and West Africa. However, the treatment purposes differ per country. The following query shows its use in Senegal: The family of the tree (i.e. Anacardiaceae) is unknown and is identified by linking the known genus type to DBpedia. Fig. 2 shows that the tree is used to treat hypoglycemia, as an anti-infective, an antivenin or an astringent for the skin. The aforementioned communities in Southern Madagascar on the other hand, use this tree to treat malaria, in prenatal care, postpartum recovery, dizziness during pregnancy, fever and caries, as shown in Fig. 3.

Conclusion

This paper stipulates that formalizing ATM, and linking it to conventional medicine, can yield innovative knowledge benefiting both ATM practitioners and researchers on the usage of plant components in conventional pharmacology. Our proof of concept focuses on two concrete use cases, using data from an ATM hospital in Senegal and the results from earlier use cases in Madagascar. This has resulted in a dataset of 13,028 RDF triples, which describe 672 plant types and 1,799 health conditions. The data has been linked to knowledge on the Web (BioPortal & DBpedia), and shown to be of interest in the use cases. Further steps are required, including obtaining more comprehensive and varied data, linked to pharmaceutical ontologies for comparison with conventional medicinal substances. Making the data accessible to ATM practitioners in rural areas in Africa would require the development of an offline and voice-based version. Semantic Web techniques can, without a doubt, contribute to Linked ATM. To achieve this, there are challenges to overcome. However, as was demonstrated in this proof on concept paper, the first step has been taken.

p r e f

  i x dbr : <h t t p : / / d b p e d i a . o r g / r e s o u r c e /> p r e f i x dbo : <h t t p : / / d b p e d i a . o r g / o n t o l o g y /> p r e f i x atmData : <h t t p : / / semanticweb . c s . vu . n l / l i n k e d a t m / r e s o u r c e > p r e f i x atmVocab : <h t t p : / / semanticweb . c s . vu . n l / l i n k e d a t m / vocab/> p r e f i x p r l : <h t t p : / / p u r l . o b o l i b r a r y . o r g / obo/> p r e f i x snmd : <h t t p : / / p u r l . b i o o n t o l o g y . o r g / o n t o l o g y /SNOMEDCT/> 3 Validating By querying possible outcomes of the use cases, the proof of concept is validated. Consider the following use case: How does Malaria treatment differs in two different regions in Madagascar?

Fig. 1 .

 1 Fig. 1. Difference in treatment of malaria in distinct communities in Madagascar

  SELECT DISTINCT ? f a m i l y ? genusType ? binomialName ? i n d i c a t i o n WHERE { ? s e t atmVocab : nomGenre ? genusType . SERVICE <h t t p : / / d b p e d i a . o r g / s p a r q l > { ? genusType dbo : f a m i l y ? f a m i l y } . ? s e t atmVocab : nomBinomial ? binomialName . ? s e t atmVocab : i n d i c a t i o n ? i n d i c a t i o n . ? i n d i c a t i o n r d f s : l a b e l ? i n d i c a t i o n L a b e l . FILTER ( ? genusType = dbr : S c l e r o c a r y a ) . FILTER ( ? binomialName = atmData : S c l e r o c a r y a b i r r e a ) . } GROUP BY ? f a m i l y ? genusType ? binomialName ? i n d i c a t i o n

Fig. 2 .

 2 Fig. 2. Sclerocarya birrea in Senegal -query result

Fig. 3 .

 3 Fig. 3. Sclerocarya birrea in Madagascar -query result

http://cowork.cintcm.com/engine/windex1.jsp, accessed 2017-07-5

http://www.hopitalkeurmassar.com/

Head of the department of Plant Biology at Cheikh Anta Diop University in Dakar

http://bioportal.bioontology.org/

http://www.dbpedia.org

https://bioportal.bioontology.org/ontologies/DOID

https://bioportal.bioontology.org/ontologies/SYMP

https://bioportal.bioontology.org/ontologies/SNOMEDCT

Acknowledgements. This work was supported by ANR ( Grant nANR-16-MRSE-0019-01), IDEX University of Bordeaux and W4RA (http://w4ra.org). We thank Hospital Traditional Keur Massar, Djibril Bâ and Geneviève Baumann.


Luuk Hendriks
email: luuk.hendriks@utwente.nl

Petr Velan
email: petr.velan@cesnet.cz

Ricardo De O Schmidt
email: r.schmidt@utwente.nl

Pieter-Tjerk De Boer
email: p.t.deboer@utwente.nl

Aiko Pras
email: a.pras@utwente.nl

Flow-based Detection of IPv6-specific Network Layer Attacks

With a vastly different header format, IPv6 introduces new vulnerabilities not possible in IPv4, potentially requiring new detection algorithms. While many attacks specific to IPv6 have proven to be possible and are described in the literature, no detection solutions for these attacks have been proposed. In this study we identify and characterise IPv6-specific attacks that can be detected using flow monitoring. By constructing flow-based signatures, detection can be performed using available technologies such as NetFlow and IPFIX. To validate our approach, we implemented these signatures in a prototype, monitoring two production networks and injecting attacks into the production traffic.

Introduction

Monitoring network traffic is an essential aspect in today's Internet. With the ever-growing collection of possible network-based threats, security officers need to stay up to date and be aware of what is possibly coming towards their networks and services. Intrusion Detection Systems (IDSs) play a critical role in this scenario, offering the first insight into malicious traffic, e.g. brute-force attacks on SSH daemons [START_REF] Hofstede | SSH compromise detection using NetFlow/IPFIX[END_REF], or large numbers of DNS responses caused by a Distributed Denial of Service (DDoS) attack. Currently, the adoption and deployment of IPv6 in the Internet is increasing: 16.4% of users of Google's services have IPv6 connectivity. North-America and Germany feature an adoption of around 30%, and Belgium is almost at 50%. With the increasing amount of IPv6 traffic in mind, we want to know whether the flow-based detection approaches from IPv4 are applicable, and moreover, fully covering the spectrum of IPv6 attacks.

In this paper, we ask ourselves 1. which new threats are introduced by these changes in the network layer; 2. how fundamental these threats are; and 3. how flow-based monitoring solutions should be adapted in order to enable detection of these new attacks.

We focus on a subset of threats: we inquire the literature, and select ( § 2.1) the vulnerabilities that are expected to be a long-term threat not easily mitigated. With the selection of threats at hand, we analyze ( § 2.2) their packet-based forms, to construct flow-based signatures. The signatures are implemented and tested on flows collected on two production networks: (1) the National Research and Educational Network (NREN) CESNET, with 8 vantage points, totalling 2.5G of flows (87G packets, 81.2Ti bytes); and (2) the campus network UTNET, with a single vantage point, with 2.2G of flows (158.6G packets, 140.7Ti bytes).

Threat selection process

The comprehensive overview in [START_REF] Ullrich | IPv6 Security: Attacks and Countermeasures in a Nutshell[END_REF] functions as a starting point in our selection process. In that paper, Table II and III list Security Vulnerabilities and Privacy Vulnerabilities, respectively, indicating the origin of each threat. Step 1: We only consider threats originating from the design of IPv6, and not any threats based on implementation or configuration mistakes. We continue by looking at Table V of that same paper, which is a matrix linking threats to detective, preventative and/or reactive countermeasures. Step 2: We only consider threats that have either no forms of countermeasure, or only a reactive countermeasure, as our goal is detection of attacks. Lastly, we rule out threats that are not actually in IPv6 itself, but merely in other (supporting) protocols. Step 3: Dismiss threats based on DNS and ICMP6.

Threat analysis process

For each threat, the following steps are carried out:

1. At the packet-level, pinpoint the protocol fields and their respective values that make up the essence of the vulnerability. 2. Determine if the essential features found in the previous step are still available in the aggregated form (flow level). N.B.: availability of these features depends on which Information Elements are exported by the flow exporter. Furthermore, the flow cache should in some cases use these fields in its cache key, in order to distinguish and export separate flow records. More details on this follow in § 3. 3. If an attack is not distinguishable based on information of a single flow, determine the relationship between malicious flows, as well as the relationship between the malicious and benign flows. 4. Formalize a signature based on the previous two steps, resulting in a perattack detection approach.

Our selection process described in § 2.1 yields six attacks (Table 2), categorized as covert channels (exfiltration of information), DoS attacks (aiming to overload and impair functioning of systems) and middlebox evasion (getting around e.g. firewalls). The constructed signatures, along with their formal explanation, are listed in Table 1. Note that we describe signatures from the perspective of the collector, not aggregation by the flow cache on the exporter. The Denial of Service (DoS) signatures have two variants: the multi-flow kind describes an attack where a large number of destination addresses is generated randomly, as opposed to the kind where a single destination address is used. Naturally, different destination addresses lead to different flow records, and therefore different signatures. An overview of requirements for flow exporters is presented in Table 2. These requirements include certain fields to be incorporated in the flow cache key (distinguishing flows on those fields), and a new IPFIX Information Element to be implemented. Note that not all IANA assigned fields are exported per se. The proposed signatures are evaluated on real production traffic, in which we inject generated attacks. As the DoS attacks could harm the routers, a safe number of packets is used, likely lower than a real attack but still allowing verification of our signatures. We describe the generated attacks, and discuss the performance of the signatures with respect to both these attacks and the production traffic, below. The approach based on fragMinOffset marks all our injected attacks. The lowest value observed in the production traffic was 64, so no positives other than our injected attacks were marked.

Flow Label Covert Channel #({FL, 5t}|FL > 0, ppf = 1) -#{5t} > τ f low dif f Traffic Class Covert Channel #({TC , 5t}|TC > 0, ppf = 1) -#{5t} > τ f low dif f Multi-

Conclusions

IPv6 comes with a plethora of threats specific to this new version of the IP protocol. By systematically characterising threats described in literature, we found six of these threats to be fundamental, i.e. based on the protocol specification and without detection approaches for attacks as of yet. In this study, we proposed flow-based signatures to perform such detection. By implementing a prototype, we proved the validity and limitations of these signatures, and defined the requirements for flow measurement equipment to allow for applying detection of attacks based on these signatures. These requirements show adaptations to flow equipment are necessary to enable for detection of these new attacks. By deploying our prototype on two production networks and injecting attacks into the production traffic, we showed our signatures are able to successfully distinguish the attacks from benign traffic without any false negatives. We provide both the detection prototype as well as the code used for generation of attacks as free and open source software [START_REF]IPv6 L3 Threat Detection[END_REF].

  flow Flow Label DoS S = ({src ip}|FL > 0, ppf = 1) , pps(S) > τpps Multi-flow Fragmentation ID DoS S = ({src ip}|pr44, ppf = 1) , pps(S) > τpps Multi-flow Hop-by-Hop DoS S = ({src ip}|pr0, ppf = 1) , pps(S) > τpps Flow Label DoS #{F L, 5t} -#{5t} > τ f low dif f Fragmentation ID DoS S = ({5t}|pr44, ppf > τ ppf ) , pps(S) > τpps Hop-by-Hop DoS S = ({5t}|pr0, ppf > τ ppf ) , pps(S) > τpps Fragmentation Overlap {5t|0 < fragMinOffset ≤ 20}

Table 1 .

 1 Signatures & notation explanation fi Field in packet, e.g. Source Address 5t Shorthand for the 5-tuple flow-key {f1, . . . fn} Flow-key based on fields f1 . . . fn

	FL Flow Label (IPv6 header field)

(FK|F+)

Set of flows aggregated on FK filtered on one or more filters F F Selection filter, e.g. ppf = 1 for flows with a single packet, or pr0 for Protocol 0

Table 2 .

 2 Flow record requirements for implementation of signatures

	Threat	Flow key	IANA New IE
	Flow Label CC	{FL, 5t}	id31
	Traffic Class CC	{TC, 5t}	id5
	Flow Label DoS	{FL, 5t}	id31
	Fragmentation ID DoS	{5t} id4 , id54
	Hop-by-Hop Option DoS	{5t}	id4
	Fragmentation Overlap	{5t}	id4 minFragOffset

  The flow records related to the covert channel are successfully distinguished, using a threshold of τ pkt = 50. No other positives were found in the dataset, meaning the signature has a low false positive rate but possibly a non-zero false negative rate. Traffic Class Covert Channel: The Traffic Class can hold different values within a single flow, and we do observe this in production traffic. Most commonly, these are a zero and a non-zero value: including the TC-field in the aggregation thus results in two flows. Using τ f l = 10, i.e. marking flows with 10 or more different Traffic Class values as attacks, the signature distinguishes all the injected attacks from the production traffic. Similar to the Flow label Covert channel, no other positives where marked, pointing out a low false positive rate but a possible non-zero false negative rate. Flow Label Flood: Detection of a Flow Label flood to a single destination address is similar to detecting a Flow Label covert channel, thus results are equivalent. Distinguishing the covert channel from the DoS attack is challenging. Multi-flow signature has a false positive rate, albeit because it marks other threats and not benign traffic. For example, a SYN scan has, on the flow level, vast similarities when compared to the flow label flood attack: a large number of end hosts is being connected to from a single source address, with every initiated connection having a new (thus different) Flow Label. Hop-by-hop Flood: As the Hop-by-Hop Options are not widely used (most of it is link local traffic, with only one or two packets per flow), simplistic thresholds for detection work: τ ppf = 10 suffices. This means scalable detection without the need for extra Information Elements or extra processing at the exporter is trivial. A possible form of false positives exists however, as we observed two times on the NREN: ping sweeps with Hop-by-Hop Options match this signature. Marking the spread version of the attack is successful, without any other positives. Fragmentation Flood: Detection of flooding based on the Fragmentation ID has several caveats. By definition, a flow with fragmented packets consists of more than one packet, but an exception of this characteristic are the atomic fragments. Signatures based on fragmented but single packet flows therefore yield false positives. As the sending rate and number of sent packets are crucial in the success of a flooding attack, we can choose thresholds that eliminate these false positives: τ pps = 5000/s , τ ppf = 200. Our attacks are identified without any other flows being marked, again pointing out a low false positive rate but a possible false negative rate. The case where destination addresses were generated and the flooding attack was hidden in a large number of different 5-tuple flows, is successfully detected. Fragmentation Overlap:

	Generated attacks:
	Flow Label and Traffic Class Covert Channels: Sending 100, 500, 1000 packets,
	within a 5 minute time-frame, towards a single host.
	Flow Label, Fragmentation ID, Hop-by-Hop Option DoS: Sending 500 packets
	at line rate, towards a single host; Sending 500 packets at line rate, towards
	randomly generated hosts in a /64 network.
	Fragmentation Overlap: Sending flows of 2, 10, 20 packets, with second packet
	offsets of 1, 4, 10, 20 towards a single host.
	Performance:
	Flow Label Covert Channel:

Acknowledgments: This work has been supported by the project Reg. No. CZ.02.1.01/0.0/0.0/16 013/0001797 co-funded by the Ministry of Education, Youth and Sports of the Czech Republic and European Regional Development Fund, and the Ministry of the Interior of the Czech Republic under project no. VI20162019029.


Martin Laštovička
email: lastovicka@ics.muni.cz

Pavel Čeleda
email: celeda@ics.muni.cz

Situational Awareness

Keywords: Detecting Critical Dependencies and Devices in a Network Martin Laštovička, Pavel situational awareness, cybersecurity, device importance evaluation, threat impact estimation, graph theory, network monitoring

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The impacts of cyber threats became more serious with organisations increasing dependency on computer infrastructure. To defend against such threats, system administrators must build situational awareness which allows them to understand and orient in the complex networks [START_REF] Kott | Cyber Defense and Situational Awareness[END_REF]. The aim of this PhD thesis is to find new ways to automatically build situational awareness to help administrators understand possible impacts of a cyber threat.

Situational awareness means the knowledge and understanding of the current situation. It is possible for a system administrator to know what is going on in a small network, but with the growing number of connected devices, this becomes more and more difficult. A basic solution is to manually create a list of all devices in the network. But it is impossible to maintain such list throughout time and keep it updated with the dynamic changes of the network. Moreover, the trend of nowadays networks, containing mobile devices or IoT (Internet of Things), and cloud environments goes directly against the idea of device list and makes it useless in practice An automated approach is needed to deal with the constantly changing environment [START_REF] Kott | Cyber Defense and Situational Awareness[END_REF].

The current approach for device and service identification focus on very specific networks, e. g., industrial control systems, or selected subset of services [START_REF] Callado | A Survey on Internet Traffic Identification[END_REF][START_REF] Franke | Cyber Situational Awareness -a Systematic Review of the Literature[END_REF] which reduces their value in modern networks described above. Manual evaluation by security expert is still prevalent in the field of dependency detection and importance estimation. These risk assessment methods are not automated [START_REF] Kim | Determining Asset Criticality for Cyber Defense[END_REF] or need active cooperation of the devices [START_REF] Weintraub | Continuous Monitoring System Based on Systems's Environment[END_REF].

In our work, we intend to find new methods of building situational awareness based on data from network monitoring that will not depend on a specific type of network. We will define a computer network model containing information about devices and services, their dependencies and importance for the organisation. The importance of a device can then be expressed as how the device outage or compromise would impact other devices and goals of the host organisation. The nature of continuous information gathering from the network also overcomes the ever-changing nature of large networks and allows us to evaluate the data throughout time.

Research Questions

This research aims to discover new ways of threat impact estimation with respect to current situation, devices and services. To achieve this goal we attempt to answer following research questions:

1. How can device and its services be identified in a complex network using passive network monitoring? Many devices are not willing (end-user devices) or not able to (IoT) provide information about themselves in large networks. But every device communication over network could be analysed [START_REF] Hofstede | Flow Monitoring Explained: From Packet Capture to Data Analysis with NetFlow and IPFIX[END_REF] and used to identify the type of the device, its operating system and provided services. However, current trends in modern networks, e. g., encrypted communication, port obfuscation, high transfer rate, make such identification hard. We plan to investigate those issues and propose methods to handle them.

How can device dependencies be detected in a network?

To understand the situation in a network, it is not enough to know only what a device is and what services it provides. It is important to know which devices it depends on and how many devices depend on it. To answer this research question, we will study relationships between devices in internal network and propose new methods for their detection from network monitoring data.

How can device importance be estimated from the perspective of reaction to cyber threats?

The importance of a particular device for organisation mission differs according to the provided services and the number of clients depending on the device. We plan to take these factors into account to build a model for importance estimation and we will find new ways of automatic importance evaluation based on traffic monitoring.

Proposed Approach

Our first step towards the building of situational awareness will be the definition of a network model. The natural representation of a computer network is a graph, where each node stands for a device in the network. Edges between nodes represent device communication, while another type of edge can represent dependencies or the presence of a cyber threat. This model allows us to separate the mostly static nature of what device is from its dynamic behaviour on the network.

Identification of Devices and Services

The knowledge of what a device is and what services it provides is a fundamental part of understanding the network. The goal of this part is to research methods of processing network traffic data to identify the type of the device (server, workstation, mobile, IoT), its operating system (Windows, Linux) and its services (web, mail, database).

Easiest way to determine a device type and services is to simply ask it. To do it in an organised way, many Service Discovery Protocols have been implemented [START_REF] Meshkova | A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks[END_REF] and deployed. They build a directory of all devices and their services, as an example, we can name well-known protocols such as BitTorrent or UPnP. However, this approach require active cooperation of the devices and hence we will not focus on them. Another way is to use active scanning. Our plan is to focus on passive methods only, yet we can use outputs of network scanning projects, e. g., Shodan, Censys, as a verification or an enhancement of our methods.

To achieve passive classification described above a sophisticated method must be used. Simple methods using protocol and port numbers currently falls short in classifying services with a dynamic port assignment or port obfuscation, e. g., hiding behind TCP port 80 [START_REF] Zander | Automated Traffic Classification and Application Identification Using Machine Learning[END_REF]. To overcome these issues, more characteristics need to be taken into consideration.

The current trend of traffic encryption makes the analysis of its content hard, but on the other hand, it opens new ways of host identification. A client needs to send a lot of data to establish encrypted communication. For example, supported ciphersuites can be used to identify communicating clients during TLS (Transport Layer Security) handshake [START_REF] Husák | HTTPS Traffic Analysis and Client Identification Using Passive SSL/TLS Fingerprinting[END_REF]. Similarly, we plan to investigate other properties of encrypted communication to identify the client device.

The most promising service identification method nowadays is the use of machine learning algorithms to classify the network traffic. Current methods perform well in a controlled environment where every application is known in advance, but cannot efficiently handle unknown traffic. Zhang et al. [START_REF] Zhang | Robust Network Traffic Identification with Unknown Applications[END_REF] presented an iterative method to improve identification accuracy, yet this field is still not fully explored. The two challenges we plan to address are the accuracy of identification in real network and performance of such algorithms when processing large amounts of data continuously coming from the monitored network.

Dependency Detection and Importance Estimation of a Device

The problem of asset criticality evaluation is known as vital for proper decision making during cyber-attacks but is difficult to achieve [START_REF] Kim | Determining Asset Criticality for Cyber Defense[END_REF]. Research in this area is mainly focused on finding ways how a group of security experts can determine criticality by following prepared guidelines just like in risk assessment. But this approach is very time-consuming and cannot be repeated very often which leads to the data being outdated.

On the contrary, automatic evaluation is able to run continuously and can provide results when needed. We are aware that some important services or dependencies can be discovered only during exceptional operations or back-up servers become active only after failure of the main one. Automatic detections can still provide good staring point for risk assessment and save resources. Moreover, automatic system can identify operations that the administrators do not know about as presented in [START_REF] Zand | Know Your Achilles' Heel: Automatic Detection of Network Critical Services[END_REF]. We propose three components to combine in order to estimate the device importance:

1. Traffic Statistics -Analysis of ongoing traffic in the network can point out the most used services in the terms of connected clients and data transfer volume. We will link these volumetric statistics to identified services to give them the dynamic context for importance evaluation, e. g., heavily loaded web server will be set as more important than another one scarcely visited. Our research will focus on real-time statistics computations so that it will be possible to dynamically adjust the evaluation as the network usage changes in time. 2. Dependency detection -Based on the identification of device type and traffic statistics, the basic dependency between client and server will be modelled. Using graph centrality algorithms we can then estimate the servers importance and the impact of its outage as the number of affected clients weighted by their own criticality. More complex dependencies can be discovered by clique detection. Dependencies forming a clique between servers can indicate strong relationship and exploitation of one will affect the whole group. The first steps towards automatic dependency detection using graph algorithms were made in [START_REF] Zand | Know Your Achilles' Heel: Automatic Detection of Network Critical Services[END_REF], but they rely on active probing (i. e., Nagios system) to discover effects of service failure and backup detections, whereas we plan to achieve the same with passive network monitoring. 3. Attacks Statistics -Network attack is a manifestation of a cyber threat.

The understanding of attack targets and discovery of most attacked devices should lead to raising the protection level of those devices. Our assumption is that parts of critical infrastructure will be targeted by attackers more often than user stations. Moreover, the type of the attack should differ and these differences could help to identify the most important devices. However, such assumption needs to be carefully verified before using in the criticality calculations. For example, attackers could target the most vulnerable device instead of critical infrastructure. In that case, such observation should be used as an advisory for the administrator rather than for criticality estimation.

Conclusion

In this research, we focus on building situational awareness from passive network observation without the necessity of active device probing. From those data, we intend to determine what a device is, what services it provides, what are its dependencies and how important it is for the network. Our methods will evaluate the situation continuously in order to follow changes in network and will be designed to be autonomic to minimise the need for human administrator assistance.

Achieving our goals will help system administrators to better understand the situation in their network and to perceive the possible impacts of cyber threats.

Acknowledgement

This research was supported by the Security Research Programme of the Czech Republic 2015 -2020 (BV III / 1 VS) granted by the Ministry of the Interior of the Czech Republic under No. VI20172020070 Research of Tools for Cyber Situation Awareness and Decision Support of CSIRT Teams in the Protection of Critical Infrastructure. Martin Laštovička is Brno Ph.D. Talent Scholarship Holder -Funded by the Brno City Municipality.


Robert Müller

Marcel Waldvogel

Corinna Schmitt
email: schmitt@ifi.uzh.ch

MoDeNA: Enhancing User Security for Devices in Wireless Personal and Local Area Networks

Today most used devices are connected with each other building the Internet of Things (IoT). A variety of protocols are used depending on the underlying network infrastructure, application (e.g., Smart City, eHealth), and device capability. The judgment of the security feeling of the data sharing depends on personal settings (e.g., easy to use, encrypted transmission, anonymization support). MoDeNA -a Mobile Device Network Assistant -was developed offering an opportunity for understanding the judgment of security by bringing the user's concerns and their technology understanding of used devices and protocols into relation. MoDeNA provides a transparent overview over the used wireless security of the user's device giving concrete advices for improving the connection security and usability of mobile device security.

Motivation

The Internet of Things (IoT) not only includes servers, computers, and routers anymore, but also personal "smart" devices that everyone uses frequently, such as smartphone, sensors, tags, and tablets. All devices collect many data in different application areas and are connected to share the data [START_REF] Greengard | The Internet of Things[END_REF]2]. It is envisioned that the variety of devices will grow in the future as well as the number of participating devices in the IoT [3]. Usually, a user is just a user of the device or the application, trusting in the pre-installed security mechanisms.

In order to allow a judgment of the used security, MoDeNA -our Mobile Device Network Assistant -was developed addressing the aforementioned views of the users abilities and the deployed network infrastructure in a smart city environment. MoDeNA is an operating system independent application based on a classification algorithm taking into account all available security information from user's device and used infrastructure to make the security setting transparent to the user. Further it recommends the user updates of security settings to improve the mobile device security for the current situation without requiring in-depth know-how. The overall goal of MoDeNA is to raise the user's awareness of security lacks when using WPANs and WLANs to provide countermeasures to avoid data theft.

While there are calls for novel security challenges for the services of the IoT like encryption and authentication [4], proposals for securing the IoT with protocols like Lithe [5], TinyDTLS [6,7] are available. Additionally, analyzes exist that investigate the technical challenges and limitations of the IP-based IoT [8,9], though the aspect of involving the user in the security of the connection between IoT devices is not considered. To our knowledge there is no known approach to involve the user in the wireless network security, particularly not for IoT devices.

Work in the field of discovering network topology without network assistance is described in [10]. A user study analyzing security and privacy habits as well as willingness to apply countermeasures is provided by [11]. Another interesting approach is investigated in [START_REF]The Internet of Things[END_REF] by moving privacy-sensitive tasks to remote security servers which offer higher protection capabilities than smartphones.

MoDeNA's Security Classification Algorithm

Based on the presented challenges in Section 2 with existing solutions, the following goals were set for MoDeNA to build a security classification scheme:

(1) Central Overview of connected IoT devices, (2) Automatic Identification of applied security requirements, (3) User Interaction support when no automatic identification happens, and (4) Control Wireless Radio Connections to keep track of own IoT devices.

In order to address the first goal the connected IoT devices are classified according to the security standard required by the data transmitted. Reading device specific information, such as shared services for communication, applications used, and identifying device classes can achieve this without user interaction required for an automatic identification. Additional information provided by the user about the pairing process, if available, is used for a more precise identification of security requirements.

The classification itself is a process that needs to be adopted for the various available device types and WPAN/WLAN protocols. Therefore, existing parameters for classification were used building the "static input (e.g., device identifiers, announced services, Universally Unique Identifier UUID) and if necessary "dynamic input" based on the user's manual input. The general security classification algorithm is illustrated in a flow diagram in Figure 1.

The MoDeNA classification algorithm takes the protocol type, device type and application of the device to be connected with as input values. They are obtained automatically by the WPAN/WLAN network sensors and connection information published in the network (e.g. via network service) by the device. If there is input regarding connection purpose available from the user ("Dynamic Information"), this information is considered for a dynamic risk level calculation. Otherwise a static risk level calculation without additional user input is applied. Afterwards the newly established connection is displayed together with its security classification. If new user input becomes available (i.e. the user confirms a security improvement measure within the application) a new dynamic risk level calculation is executed. Otherwise the algorithm terminates.

Four levels for application security requirements are distinguished: (1) High (green) -key exchange mechanism with no design flaws and transmission encryption, (2) Acceptable (yellow) -key exchange mechanism with design flaws and transmission encryption, (3) Low (red) -insufficient data security, and (4) Undetermined (grey) -by default accepted. This grading can be seen in the Overview Screen shown in the shown in the upper part of Figure 2. It presents the user with an Security classification state per connected smart device. Clicking on a row opens the device's Detail View Screen shown in the lower part of Figure 2. It advises the user with practical security hints and asks for input of environmental parameters to improve classification. The application back-end provides adapter implementations for the supported physical network interfaces and listens asynchronously for connected devices available. First, it identifies whether a device was previously connected. For new detected devices, the MoD-eNA application collects the protocol-and device specific information and creates a new entry in the devices database. Previously known devices can be recognized and the security classification is based on the available device history. For each device the database stores a dataset consisting of: device name, type, address, last security classification, performed security improvements by the user and used application. Based on this information, the MoDeNA algorithm is applied to determine the security requirements and obtain the security classification. This is then used to provide the user with recommendations for each specific combination of device type and security requirement (e.g., Smart watch + WiFi and/or Bluetooth indicating High security, wireless mouse + WiFi or Bluetooth indicating Acceptable security, hearing aid + Bluetooth indicating Low security). An example for improving the security of a connection is shown for the WLAN "kerrigan-2.4". The WLAN is automatically detected by the smartphone with activated Wi-Fi service as someones private network,which does not require authentication and the smartphone connects to it automatically. When a user of MoDeNA application detects it in the Overview Screen, it is listed as a network interfaced with. Since there is no authentication provided, it is rated not secure by the MoDeNA application. The three bullets indicator is used to show the maximum possible grading available. If the user now clicks on the list entry, he/she is brought to the detail view, which shows the reason for this security classification (red indicator) and what measures can be applied to improve connection security with "kerrigan-2.4" by adopting them. Settings and measurements made for known networks can be saved automatically by MoDeNA. Further information about the security risk of using specific wireless technologies is provided with links to useful web pages that provide background information and educate the user.

User Study

A prototype of the application MoDeNA is realized on the Android OS platform, since it is the most widely used operating system to date for smartphones.

We conducted a two-part user study to analyze usage of IoT devices connected to smartphones via WPAN/WLAN and to rate the use of our application. The participants were asked to fill in a questionnaire with 23 questions while using the application MoDeNA for the second part of the study. For the evaluation, we used a mock-up of our proposed application without the implementation of the classification of the real network connections.

(1) Wireless Network Smartphone Security 48% of our participants have a technical background (work or education). The interest rate in understanding wireless smartphone communication is 91% for non-technical and 67% for technical users. 87% of participants would rate data on their smartphones as private data. 70% know about security concerns of data stored on smartphones but they accept the possible risks. 87% of the participants ask for more protection of their personal data stored on their smartphone. Asking the users if they turn off unused wireless protocols showed that 65% do turn off radio, but for reasons like battery, radiation and others, only 22% of them do it also because of security concerns. 83% of participants state that they would apply security measures, if their smartphone recommended them to do so.

(2) "Application Specific Wireless Security" The users were requested to play around and evaluate our prototype implementation of the application MoDeNA. Thus, this received feedback was user-specific and highly influenced by individual knowhow.74% of participants state that they gained insight in the security of wireless smartphone communication. The same percentage of participants also claimed, that they think the application MoDeNA would improve the security when used. 87% expect MoDeNA would improve the WPAN/WLAN security of their smartphones.

We present MoDeNA, a framework for detection and classification of WPAN/ WLAN connection security and a prototype smartphone application for Android OS to (semi-)automatically rate the security of connected WPAN/WLAN devices and provide advices to the user. In our user study with 23 participants we observed that 70% of participants are generally aware of security risks when transmitting data wirelessly from a smartphone to any other device but nevertheless use the functionality. 78% of our participants have heard or know about security risks for WPAN/WLAN protocols. MoDeNA is rated by 90% of our user study participants to be helpful to feel more secure with smart devices in WPAN/WLAN.

Fig. 1 .

 1 Fig. 1. Classification algorithm Fig. 2. MoDeNA Views