Philippe Besnard

Véronique Masson

Admissible Generalizations of Examples as Rules

.

I. INTRODUCTION

Generalizing a given set of examples is essential in many machine learning techniques such as rule learning or pattern mining. Particularly, rule learning is a data mining task that consists in generating disjunctive sets of rules from a dataset of examples labeled by a class identifier. We are focusing on propositional rule induction [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF] where rules have the form "IF Conditions THEN class-label". Rule learning consists in finding individual rules [START_REF] Tom | Generalization as search[END_REF], each rule generalizes a subset of the dataset examples. Many algorithms achieve rule induction, from CN2 [START_REF] Clark | The CN2 induction algorithm[END_REF], Ripper [START_REF] William W Cohen | Fast effective rule induction[END_REF] to recent subgroup discovery algorithms [START_REF] Boley | Identifying consistent statements about numerical data with dispersion-corrected subgroup discovery[END_REF]. Usually each rule is evaluated by different measures using the number of positive and negative examples covered, i.e. generalized, by the rule. Numerous interestingness measures [START_REF] Geng | Interestingness measures for data mining: A survey[END_REF] on rules have been proposed. Some heuristic measures guide the machine learning algorithms and some of them are used in a post-processing step to select final rules.

Rule learning algorithms received recent attention in the machine learning community due to their interpretability. Explainability and interpretability of machine learning results is a hot topic [START_REF] Hugo Jair Escalante | Explainable and Interpretable Models in Computer Vision and Machine Learning[END_REF]. The logical structure of a rule can be easily interpreted by users not familiar with machine learning or data mining concepts. We feel that generalization of examples by machine learning algorithms impacts interpretability, particularly when this generalization is counter-intuitive.

Table I is an illustration of a dataset of house rental ads. Each row is a house rental ad and each column is an attribute. With a minimal coverage size of 2, CN2 extracts the following three rules predicting a value for the class-attribute C: Generalization of a metric attribute leads to the difficult question of defining boundary values. The π CN 2 2 rule uses a value for A 2 attribute (i.e., 2.5) which is not in the original dataset. The choice of this boundary is motivated by statistical reasons: with an hypothesis of uniform distribution of numerical attribute, it minimizes the generalization error. One can notice that it is less intuitive (although equivalent) than the rule:

• π CN 2 1 : A 5 = Downtown → C = expensive • π CN 2 2 : A 2 < 2.50 ∧ A 4 = Toulouse → C = low-priced • π CN
A 2 ≤ 2 ∧ A 4 = Toulouse → C = low-priced.
This small example illustrates that existing rule learning algorithms underestimate the effects that their underlying hypotheses about generalization can have on the value of extracted rules for a data scientist -some rules sometimes fail to capture an intuitive generalization of the examples.

We are wondering whether it is possible to highlight some general principles of intuitive generalization that would help to analyze or to qualify rules or rulesets extracted by rule learning algorithms. This means that we are interested in analyzing consequences of choices made by rule learning algorithm when generalizing examples.

There are different approaches to reach such an objective: scoring interestingness or quality measures [START_REF] José | Evaluation of association rule quality measures through feature extraction[END_REF] or analyzing results on the light of subjective criteria [START_REF] Stecher | Shorter rules are better, aren't they?[END_REF] (see related works for more details).

The purpose of this paper is to propose a topological formalization for generalization of examples which favours an analysis on the admissibility of the generalization by enabling to express different notions of admissibility. One objective is to make it possible to compare the outputs of rule learning algorithms with the theoretically admissible rules in order to shed light on some poorly interpretable outputs.

Importantly, our work is also original as it pays special attention to the values (mostly as boundaries) occurring in rules whereas work in the literature on improving rules or rulesets usually focus on the structure of rules or of rulesets, see e.g. [START_REF] Hills | BruteSuppression: a size reduction method for apriori rule sets[END_REF], [START_REF] Cano | An interpretable classification rule mining algorithm[END_REF]. The contributions of this work are:

S π S π S π . . . . . . S ••• π ••• (C) (A 1 ) (A 2 ) (A 3 ) (A 4 ) (A 5 ) (A 6 )
• we propose an abstract formalization of the rule learning process introducing the generalization of examples as a choice of a generalization rule π = S (for a set of examples S) among supersets of S, • we introduce the notion of admissibility, we derive two alternative versions of admissibility from Kuratowski's axioms and we give sufficient conditions on choice functions to induce admissible generalizations, • we instantiate admissibility in the specific case of metric attributes and we analyze some CN2 results in the light of our framework. Note that we do not have an immediate practical objective: our purpose is not to design a new rule learning algorithm but to set a general framework that may help to shed light on some aspects of existing, or future, rule learning algorithms. In particular, we illustrate that a well-known algorithm such as CN2 makes some counterintuitive choices of boundaries in rules with metric attributes.

II. GENERALIZATION OF DATA AS A RULE

This work focuses on the LearnOneRule step of the rule learning process [START_REF] Tom | Generalization as search[END_REF], [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF]. The LearnOneRule process is viewed as a two-step process, depicted in Figure 1: 1) Some subsets of data are selected. In Figure 1, φ selects possible subsets of data. 2) Each subset of data (both subset of columns and rows of the dataset) is assumed to be generalized by a single rule. A subset of data is generalized by a rule. For a data subset (A, S) (some examples restricted to some attributes) of the dataset, the idea of the "generalization" function f from (A, S) is to generate the rule π. Thus, a data subset is generalized by a single rule.

This work investigates the f function, i.e., how to generate a rule from a subset of data. We do not tackle the question of determining φ, i.e., how to select data subsets. It is assumed that rules are generated from all possible selected subsets.

A. Data and rules

Data consist of tuples of size n (for

n attributes A 1 , • • • , A n ).
It is assumed that each tuple is assigned a class value. The range of an attribute A i , denoted Rng A i , may, or may not, be ordered. For Table I, range of attributes and their structure are given in Table II. Values of attributes are of various types: floats (e.g., A 1 ), integers (A 2 ), discrete values either structured (e.g., A 6 can be partially ordered), or unstructured (e.g., A 4 ). A rule learning algorithm elicits rules of the form:

A π(1) (x) ∈ v 1 ∧ • • • ∧ A π(k) (x) ∈ v k → C(x) ∈ v 0 ( * )
where

1 ≤ k ≤ n, v i ⊆ Rng A π(i) for i = 1..k, v 0 ⊆ Rng C and {π(1), • • • , π(k)} ⊆ {1, • • • , n}.
Such a rule expresses that for an item x, if the value of each attribute A π(i) is one within v i then the class value of x is one within v 0 .

The value v i is a subset of the range of the attribute A π(i) (or class C). So, v i can be a singleton subset {u} of the range Rng A π(i) of the attribute i.e.

A π(i) (x) ∈ v i is A π(i) (x) = u. Or, v i can be a finite subset {u 1 , • • • , u ip } of Rng A π(i) hence A π(i) (x) ∈ v i is just the disjunctive condition A π(i) (x) = u 1 or A π(i) (x) = u 2 or . . . or A π(i) (x) = u ip .
Disjunctive conclusions are unusual in rule learning but they could be desired and they generalize the approach. Lastly, v i can be an arbitrary subset of the range Rng A π(i) . Structure over Rng A π(i) can be exploited, e.g. A π(i) (x) ≥ r is captured by setting v i to the interval [r, M ] (if M is the greatest element).

B. General form of rules

We can identify a rule with a sequence of values for some attributes among A 1 , • • • , A n as well as C thus resulting in the general form for a rule π

π = A π(1) (x) ∈ v π 1 ∧ • • • ∧ A π(kπ) (x) ∈ v π kπ → C(x) ∈ v π 0 ( †) with 1 ≤ k π ≤ n, v π i ⊆ Rng A π(i) for i = 1..k π , v π 0 ⊆ Rng C and {π(1), • • • , π(k π )} ⊆ {1, • • • , n}.
For the sake of simplicity, such a rule can be expressed as a member of

2 Rng C × 2 Rng A1 × • • • × 2 Rng An , i.e., a vector π = (v π 0 v π 1 v π 2 • • • v π n ) ( ‡)
where

for i = 1..n, v π i = Rng A i if A i ∈ {A π(1) , • • • , A π(kπ) }. A tuple (x 1 , • • • , x n ) which is assigned the class value c is said to be covered by the rule π above if c ∈ v π 0 and all x i ∈ v π i (for i ∈ {π(1), • • • , π(k π )}
). Notation: In the sequel, S i denotes the set of values that the attribute A i takes in the subset S of the data, i.e.,

S i def = {x i | (x 0 , x 1 , • • • , x n ) ∈ S}

C. Admissible rule generation

This work focuses on finding one rule, generalizing a subset of the dataset, which makes sense for the data scientist. Learning one rule aims at extending the set of values actually taken by the examples. Theoretically, any extra value, not covered by a counter-example, would work. However, some extended sets make more sense than others: we call this notion rule admissibility.

We do not consider how to find such a subset of the dataset but, given such a subset, we investigate the question of what is an admissible generalization of these examples for a user. Please note that we don't provide a definition for admissibility. What we provide is a framework to express different notions of "admissibility". Indeed, it depends upon application and users. The way we propose to analyze rule learning algorithms is to confront practical results with these different notions.

There is a sense in which a data subset determines a single rule. It is the view that the only rule generated by S is

A 1 (x) ∈ S 1 ∧ • • • ∧ A n (x) ∈ S n → C(x) ∈ S 0 ( §)
where X is the smallest rule admissible superset of X (for

X ⊆ Rng A i or X ⊆ Rng C).
Please note that this requires the assumption that attributes are independent for the purpose of rule admissibility. That S is a data subset under φ (see Figure 1) means that if S is to amount to a rule π then each tuple in S is covered by π. Therefore, such a rule ( §) is to be of the kind

A π(1) (x) ∈ v 1 ∧ • • • ∧ A π(k) (x) ∈ v k → C(x) ∈ v 0 ( * * ) where 1 ≤ k ≤ n, S π(i) ⊆ v i for i = 1, • • • , k and S 0 ⊆ v 0 (as usual, {π(1), • • • , π(k)} ⊆ {1, • • • , n}). What vector (v 0 v 1 v 2 • • • v n ) can count
as a rule for the purpose of capturing S? Since ( * * ) is meant to capture S, we are looking for a vector π

≥ (S 0 S 1 S 2 • • • S n ) (i.e., S i ⊆ v π i for i = 0, • • • , n) where every v π i is rule admissible.
Technically, the least 1 such π is the case that v i = S i for i = 0, • • • , n. As a rule, it does not fit. If S is to be viewed as a rule, the intuition is that a tuple close enough to some member(s) of S is expected to behave similarly to this member (or those members).

D. Properties of generalization as choice

The intuition we point out in the latter remark suggests that generalizing a set of values to a superset thereof amounts to applying a closure-like 2 operator • . For any attribute A i and data subset S, generalizing S i is identified with mapping S i to S i , with properties taken from the list of Kuratowski's axioms:

∅ = ∅ S ⊆ S ⊆ Rng A i S = S S ∪ S = S ∪ S (pre-closure)
Actually, we downgrade Kuratowski's axioms as follows (the Appendix reminds the definitions of related operators)

S ⊆ S whenever S ⊆ S (closure) S = S whenever S ⊆ S ⊆ S (cumulation) S ∪ S ⊆ S whenever S ⊆ S (capping)
We thus arrive at two classes of weaker operators that are worth exploring further: preclosure operators and capping operators, resp. realizing interpolation from single points and interpolation from pairs of points (with the view that rule generation encompasses interpolation of some kind).

This notion of rule admissibility is to be captured by a selection function, f , to fit the general view of Figure 1. Such a function (from a special class) determines an appropriate superset of S i given some subsets of the powerset of Rng A i . The intuition here is that rule admissible subsets of the range Rng A i of an attribute A i can be characterized as choices from the powerset of Rng A i . Depending on what principles underly the actual choice, a different kind of closure embodies rule generation through the rule generalization principle.

The next theorems (with Rng A i generalized to a set Z) specify two classes of selection functions that induce a closurelike operator over a powerset: preclosure and capping.

Theorem 1 (Selection functions inducing a preclosure operator):

Let Z be a set such that f : 2 2 Z → 2 Z is a function satisfying the three conditions below for all X ⊆ 2 Z such that X is upward closed and all Y ⊆ 2 Z : 1. f (2 Z ) = ∅ 2. f (X ) ∈ X 3. f (X ∩ Y) = f (X ) ∪ f (Y) whenever min(X ∩ Y) = min X ∪ min Y The mapping • : 2 Z → 2 Z such that X def = f ({Y | X ⊆ Y ⊆ Z})
is a preclosure operator on Z.

1 π ≤ π iff v π i ⊆ v π i for i = 0, • • • , n. 2 Closure-like operators are topological operators, cf Appendix.
Theorem 2 (Selection functions inducing a capping operator): Let Z be a set, f : 2 2 Z → 2 Z be a function obeying the next two conditions for all X ⊆ 2 Z s.t. X ∈ X and all Y ⊆ 2 Z :

1

. f (X ) ∈ X , 2. if Y ⊆ X and ∃H ∈ Y, H ⊆ f (X ) then f (Y) ⊆ f (X ). The mapping • : 2 Z → 2 Z such that X def = f ({Y | X ⊆ Y ⊆ Z})
is a capping operator on Z.

III. GENERATION OF RULES WITH METRIC ATTRIBUTES

Back to the idea of rule generation as interpolation, we are considering the simplest case of rules with a collection of items that all take the value u for metric attribute A i and that all are in class c. A rule for this case is

A i (x) = u → C(x) = c
i.e. c = f i (u) for some function f i . This rule is restrictive as it only applies for items that take exactly the value u for A i .

As items take a set of specific values {u 1 , u 2 , . . . , u n }, our idea is to generate rules that generalize them to an interval of values [v, w]. The main issue is to determine classes of selection functions that yield intuitive intervals of values.

The first approach is to propose a neighborhood principle. Since c = f i (u), it seems rather reasonable to still expect the class to be c for all values close enough to u. Assuming a notion of neighborhood, a rule exemplifying this would be

A i (x) ∈ [u -r, u + r] → C(x) = c.
This is developed in the next section where a class of selection functions is given that all induce a preclosure operator.

A drawback of the neighborhood approach is its predefined radius, r, which does not take into account the actual values distribution when it comes to finding intervals. Another section proposes a second approach that deals with interpolation from pairs (u, v) of values for an attribute A i . This captures the idea that an interval of values is made of elements that are close enough to each other. We show that this principle can be captured through a capping operator.

A. Neighborhoods

As an application, consider neighborhoods for real-valued data (i.e., Rng A i ⊆ IR). For a datum u ∈ IR, we look at a generalization for u in the form of the neighborhood centered at u of radius r, for a given r > 0. For r > 0 ∈ IR, let n r : 2 IR → 2 IR be the function:

n r (X) def = ∅ if X = ∅ u∈X [u -r, u + r] otherwise
It happens that n r is a preclosure operator, i.e., as presented in the Appendix, n r is a mapping c : 2 U → 2 U such that:

c(∅) = ∅ (null fixpoint) X ⊆ c(X) ⊆ U (extension) c(X ∪ Y ) = c(X) ∪ c(Y ) (preservation of binary unions)
Besides this independent evidence, we get the same conclusion from Theorem 1, giving an actual selection function f . Now, a useful abbreviation is ↑ {X}

def = {Y | X ⊆ Y ⊆ Z}.
For a subset S of IR, define f (↑ {S}) by:

f (↑ {S}) def = ∅ if S = ∅ x∈S [x -r, x + r] otherwise Extend f to all of 2 2 Z by taking f (X ) def = S ∈ min X f (↑ {S}).
(Since X denotes a collection of subsets of Z, min X denotes those sets in X that have no proper subset in X .) Then, f satisfies conditions 1-3 of Theorem 1.

B. Intervals

We look now at generalization from S i as interpolation of the kind: If u ∈ S i and v ∈ S i such that the distance between u and v is smaller than some threshold then generalize u and v to all values (in the range of A i ) between u and v. We again follow the idea that generalizing S i amounts to applying some kind of closure operator • , giving S i . We start with considering closure operators (see the Appendix), i.e., for all S ⊆ Rng A i and S ⊆ Rng A i , the following holds:

S ⊆ S ⊆ Rng A i , S = S, S ⊆ S whenever S ⊆ S .
Interestingly, for a data subset S, in order to determine the rule π induced by S, applying S = S means that if S i is rule admissible then it is enough to set v π i = S i and no further adjustment over π is needed regarding the attribute A i (further adjustements are likely for other attributes).

C. Example of • not being a closure operator

Imagine a principle that generalizes values (from IN) to small intervals over IN. For instance, let attribute A 2 be distance to townhall. Let the class attribute C be level of rent (understood as ranging over cheap, low-priced, . . . ). From the minimalistic S consisting of items 1 and 2 below: [START_REF] Hugo Jair Escalante | Explainable and Interpretable Models in Computer Vision and Machine Learning[END_REF][START_REF] Fürnkranz | On cognitive preferences and the plausability of rule-based models[END_REF]. This is a counterexample to closure because (isotony) fails: S 2 ⊆ S 2 but v π 2 ⊆ v π 2 . π says that rents of flats in the vicinity of the town hall are low and so are rents of flats in a 7 to 9 km ring from the town hall but no example confirm this for flats in the range 3 to 7 km. We can regard [1,3] ∪ [START_REF] Hugo Jair Escalante | Explainable and Interpretable Models in Computer Vision and Machine Learning[END_REF][START_REF] Fürnkranz | On cognitive preferences and the plausability of rule-based models[END_REF] as more admissible than the large [START_REF] José | Evaluation of association rule quality measures through feature extraction[END_REF][START_REF] Fürnkranz | On cognitive preferences and the plausability of rule-based models[END_REF].

Distance . . . Level A 1 to

D. Example of • not being a cumulation operator

Since • fails to be a closure operator, the next possibility is that • is a cumulation operator (every closure operator is a cumulation operator but the converse is untrue).

Again 5.5, 6.9]. Again, the idea is that the gap between two consecutive values is to be turned into an interval unless the gap is much greater than most of the other gaps in the series: the gap from 5.0 to 5.5 has length .5 but all other gaps here (from 4.1 to 4.2, . . . , from 6.8 to 6.9) have length at most .2.

It is a counterexample to cumulation because

S 2 ⊆ S 2 ⊆ v π 2 but v π 2 ⊆ v π 2 (still, v π 2 ⊆ v π 2 )
. All this suggests some kind of preservation principle:

If new items confirming a rule are added, generalization should not make the rule to be further generalized. It seems that such an approach to generalizing a set of values to a superset thereof amounts to applying a capping operator. The next section shows that such a view can be identified with using a selection function (from the special class specified in Theorem 2) to determine the appropriate superset eliciting the rule.

E. Capping operator: selection via power means

Let the special case that Z is totally ordered and f selects, among all supersets of S = x 1 , . . . , x m ,3 the union of the intervals over Z that have both endpoints in S and length (denoted by l) bounded by a threshold value ∆(S) as follows

ϕ S (x j ) def = [x j , x j+1 ] if l([x j , x j+1 ]) ≤ ∆(S) [x j , x j ] else (including j = m) (1)
where ∆ is a function on the increasing sequences over Z, i.e. S → ∆(S) for every increasing sequence S. For all finite S ⊆ Z, define

f (↑ {S}) def = x∈S ϕ S (x) (2)
where the ϕ S : S → 2 Z functions can be required to satisfy, for all x ∈ S and all finite S ⊆ Z, the following constraints

(i) x ∈ ϕ S (x), (ii) S ⊆ S ⊆ ϕ S (S) ⇒ ϕ S (S ) ⊆ ϕ S (S).
Extend f to all of 2 2 Z by taking

f (X ) def = X whenever X = ↑ {S} for all S ⊆ Z. ( 3
)
Proposition 1: If ϕ satisfies conditions (i) and (ii) then f as defined by (2)-( 3) enjoys conditions 1.-2. of Theorem 2.

We focus on intervals with endpoints in IR (hence S ⊆ IR) and length the absolute difference between both endpoints.

Proposition 2: Let ϕ be as in (1) with ∆ such that for all finite S and S , if

S ⊆ S ⊆ ϕ S (S) then ∆(S ) ≤ ∆(S). If ∆ is real-valued, if Z is IR and if l([x, y]) = |y -x| then ϕ satisfies (i)-(ii).
An almost direct application of Theorem 2 then implies that functions defined as in (1) induce capping operators. The following instances for ∆ functions give selection functions, as per (1)-( 3), generating admissible rules:

• Geometric mean: ∆(S) = m-1 i=1 (x i+1 -x i ) 1 m-1 • Higher power means: ∆(S) = p 1 m-1 m i=2 (x i -x i-1 ) p IV. RELATED WORK
Rule learning algorithms are a class of machine learning algorithms mainly developed in the 90's [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF] that drew recent interest due to the interpretable nature of its outputs [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF].

Prior works have proposed foundations for rule learning and many algorithms exist. A major reference is [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF] that broadly presents the concepts used in rule learning algorithms. It mainly focuses on practical aspects that enable the reader to understand a broad range of algorithms. Our framework aims at turning the rule learning formalization to a more conceptual level. We investigate in particular the LearnOneRule step of the rule learning process. A key issue in the LearnOneRule algorithm is how to evaluate and compare different rules [START_REF] Fürnkranz | Foundations of Rule Learning[END_REF] using several measures such as precision, information gain, correlation, m-estimate, etc. The basic principle underlying these measures is a simultaneous optimization of consistency and coverage. This optimization addresses the way of choosing a subset of examples covered by a rule but does not give any information on the interest of a generalization from a data scientist viewpoint. Our framework allows to address admissibility of generalizations and thus to define classes of generalizations able to catch empirical concepts of neighborhood for example.

This notion of admissibility contributes to a formalization of the interpretativeness of the outputs of rule learning algorithms. Similar questions have been addressed in previous works. To the best of our knowledge, none of them addressed the problem of the choice of the values in the rules. They take into consideration the structure of the rules (e.g. their size) or the rule set [START_REF] Cano | An interpretable classification rule mining algorithm[END_REF], [START_REF] Benites | Hierarchical interestingness measures for association rules with generalization on both antecedent and consequent sides[END_REF], [START_REF] Wang | Bayesian rule sets for interpretable classification[END_REF], [START_REF] Lakkaraju | Interpretable decision sets: A joint framework for description and prediction[END_REF], [START_REF] Boley | Identifying consistent statements about numerical data with dispersion-corrected subgroup discovery[END_REF]. Instances of the GUHA method to mining association rule [START_REF] Hájek | The GUHA method and its meaning for data mining[END_REF] fall under our approach if conclusions of such rules are to play the role of classes.

In [START_REF] José | Evaluation of association rule quality measures through feature extraction[END_REF], the proposed framework is based on a score for rule quality measures. It does not use quality measures that select intuitive rules, but the most accurate ones. [START_REF] Kliegr | A review of possible effects of cognitive biases on interpretation of rule-based machine learning models[END_REF] addressed the intuitiveness of rules through the effects of cognitive biases. They notice that a number of biases can be triggered by the lack of understanding of attributes or their values appearing in rules. In [START_REF] Fürnkranz | On cognitive preferences and the plausability of rule-based models[END_REF], the authors suggest that "longer explanations may be more convincing than shorter ones" (see [START_REF] Stecher | Shorter rules are better, aren't they?[END_REF], too) and evaluate this criterion using a crowd-sourcing study based on about 3.000 judgments.

Hence, one of our contributions is to relate generalization of examples to closure-like operators. Relationship with Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] then comes to mind. In [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF], the authors investigate the problem of mining numerical data with Formal Concept Analysis. This amounts to a way to generate some subsets of data. As we have shown that the operators at work In the upper histogram, the data distributions are simulated using uniform distributions. In the lower histogram, the data distributions are simulated using a mixture of two normal distributions per class. in generalizing by intervals are weaker than closure operators, no equivalence is expected. Even the idea that a subset (A, S) of the dataset is always a subset of a concept fails in general. For instance, let φ capture the idea of "contraries", in which case a selected subset of size two consists in two examples e 1 and e 2 such that A i (e 1 ) = A i (e 2 ) for all A i in A hence σ({e 1 , e 2 }) = ∅ which entails that no superset of {e 1 , e 2 } can be a concept with a non-empty set of attributes. In contrast, there exist selection functions that provide a subset of Rng A i as a generalization for {e 1 , e 2 }.

V. ILLUSTRATION WITH CN2 RULES

We illustrate some behaviours of CN2 [START_REF] Clark | The CN2 induction algorithm[END_REF] when facing artificial data distributions, to show that our proposed formalisation offers a framework for analyzing rule learning algorithms. We use a simulated dataset with a single numerical attribute, v, and two classes. The form of the generated rules is v ∈ [l, u] ⇒ C where [l, u] is an interval and C ∈ {blue, green}.

Remember, the abstract modeling of a rule learning process has two steps: selection of a subset of data and generalisation of this subset of data by a rule. This article is focused on the generalisation step. The simple case studies below make the assumption that each class of the dataset corresponds to a subset of examples to generalize. Then, our analysis assumes two subsets of data (and thus two rules): the subset of data labeled as blue and the ones labeled as green. These two subsets are for illustration purposes only, we make no claim that they are more sensible than other alternative subsets.

A. CN2 splits potentially interesting intervals

Here, we illustrate the fact that, despite the relative continuity of the attribute, the CN2 algorithm splits attribute intervals of a rule in some specific cases of overlapping values.

Figure 2 illustrates two data distributions for which we run the CN2 algorithm. The distribution of each class is dense from lower to higher value, i.e., the gaps between two consecutive examples of a class are bounded. It is desirable to have exactly one rule per class generalizing all examples. This would be the case if rule generalization were to follow the principles of neighborhoods or intervals applied on data subsets made of examples belonging to the same class. Yet, the CN2 algorithm splits the interval in several sub-intervals to improve its selection criteria based on accuracy.

The extracted rules in case of uniform distributions (top of Figure 2), resp., for normal distributions (bottom of Figure 2) are in the leftmost list, resp., in the rightmost list below: This illustrates the more general situation that an approach insensitive to density of examples over the choice of boundaries amounts to a cumulation operator:

• v ∈ [-∞, 10.03] ⇒ blue • v ∈ [-∞, 0.96] ⇒ blue • v ∈ [12
Theorem 3: Let Z be a set such that f : 2 2 Z → 2 Z is a function satisfying the two conditions below for all nonempty

X ⊆ 2 Z and Y ⊆ 2 Z : 1. f (X ) ∈ X , 2. f (X ∪ Y) ∈ X ⇒ f (X ∪ Y) = f (X ). The mapping • : 2 Z → 2 Z such that X def = f ({Y | X ⊆ Y ⊆ Z})
is a cumulation operator on Z. the same. Our experiments show that the gap length has no consequences on the rules. The very same rule is generated splitting examples by comparing their value with 0. We can conclude from this example that CN2 does not behave in the way described by preclosure operators.

C. Impact of example sparsity on boundaries choice

The two preceding experiments seem to show that rules are generated only from the extreme values of examples sets without considering the actual example distribution. Such a behaviour appears to be more constrained than the one of a capping operator. It amounts to a ∆ function that would not be decreasing. But these examples are specific cases of datasets with well-separated classes. In case of overlapping range of values (see Figure 2), the rule choices that have been made depend on example distributions.

VI. CONCLUSION AND PERSPECTIVES

Evaluation and comparison of rules in the rule learning task are currently based on optimization of consistency and coverage measures. In this article, we look at the notion of rule admissibility as the interest of a generalization from a data scientist viewpoint. We define a framework providing a formal approach to the generalization of examples in the attribute-value rule learning task and some foundations for the admissible generalizations of examples as rules. Our notion of admissibility is presented as a choice of one generalization among all supersets of examples. Distinguished notions of choice are shown to capture a closure-like operator (preclosure or capping). In the case of metric attributes, we offer actual selection functions that induce such operators.

These selection functions show how our framework supports the analysis of rule-learning evaluation. We have generated synthetic datasets to analyze the behaviour of CN2 in view of notions arising from our framework. Thus, we point out some counter-intuitive behaviours of this algorithm. Some novelty in our work lies with it focussing on the values occuring in rules, instead of, e.g., the structure of rules.

Since rule learning may involve non-numerical attributes, a short term perspective is to also give selection functions for attributes with weaker structure than enjoyed by numerical attributes (metric structure). Finally, this article does not address the issue of selection of data subsets. Future work is to focus on this part of the process to propose a more complete formal model for attribute-value rule learning.

2 3:

 2 A 1 > 36.00 ∧ A 3 = D → C = cheap § Corresponding author: Véronique Masson (veronique.masson@irisa.fr)

Fig. 2 .

 2 Fig. 2. Data distributions for classes blue (in blue) and green (in green).

Fig. 3 .

 3 Fig. 3. Balanced (on top) and unbalanced (on bottom) distributions of two classes examples. Classes are separated by a fixed distance.

Figure 4

 4 Figure 4 illustrates two datasets whose example distributions differ by the gaps between consecutive examples of the same class. In the first case, these gaps are small (average gap of 1 unit) w.r.t. the gap between the two classes (3 units). In such a case, we expect to generate a rule that gather all examples in a single interval. It is actually what happens with CN2. In the second case, gaps between consecutive examples are larger (average gap of 10 units), but the behaviour of CN2 remains

Fig. 4 .

 4 Fig. 4. Two datasets centered on 0 (each bar is one example). The gap between consecutive examples is 1 unit at the top and 10 units at the bottom.

TABLE I DATASET

 I OF HOUSE RENTAL ADS. BLANK CELLS ARE MISSING VALUES.

		(C)	(A 1 ) (A 2 )	(A 3 )	(A 4 )	(A 5 )	(A 6 )
		Price Area #Rooms Energy Town District Exposure
	1 low-priced 45	2	D	Toulouse Minimes
	2	cheap	75	4	D	Toulouse Rangueil
	3 expensive 65	3		Toulouse Downtown
	4 low-priced 32	2	D	Toulouse		SE
	5 mid-priced 65	2	D	Rennes		SW
	6 expensive 100	5	C	Rennes Downtown
	7	cheap	40	2	D	Betton		S

  Fig.1. Abstract modeling of the LearnOneRule process (see text for details). Grey cells illustrate selected rows and columns that may generate πCN 2

								f
								φ	f
		Price	Area #Rooms Energy	Town	District Exposure
	1 low-priced 45	2	D	Toulouse Minimes	φ
	2	cheap	75	4	D Toulouse Rangueil	φ	f
	3 expensive 65	3		Toulouse Downtown
	4 low-priced 32	2	D	Toulouse	SE
	5 mid-priced 65	2	D	Rennes	SW	φ
	6 expensive 100	5	C	Rennes Downtown
	7	cheap	40	2	D	Betton	S
								f

2

.

TABLE II RANGES

 II FOR THE ATTRIBUTES OF THE DATASET FROM TABLE I.

	Attr.	Range	Structure
	A 0 {cheap, low-priced, mid-priced, expensive} total order
	A 1	[1, 500]	metric
	A 2	{1, 2, 3, 4, 5, 6}	metric
	A 3	{A, B, C, D, E}	total order
	A 4	{Toulouse, Rennes, Betton}
	A 5	{Downtown, Rangueil, Minimes}
	A 6	{S, N, W, E, SE, SW, N E, N W }	partial order

  , think of some principle that generalizes values (from IN) to small intervals over IN. Here is a brief example (we use decimals of km to abbreviate hundreds of meters), with S consisting of items i 1 to i 9 below: Indeed, gaps between any two consecutive values among these nine values are of somewhat similar length and are turned into intervals. Now, from S consisting of items i 1 to i 20 below:

				then the same principle can make S (items i 1 to i 20 ) to give a rule with v π 2 = [4.1, 5] ∪ [
	Distance A 1 to townhall	. . .	Level of rent
	item 1 . . .	4.1 km	. . .	cheap
	item 2 . . .	4.4 km	. . .	cheap
	item 3 . . .	4.8 km	. . .	cheap
	item 4 . . .	5 km	. . .	cheap
	item 5 . . .	5.5 km	. . .	cheap
	item 6 . . .	5.8 km	. . .	cheap
	item 7 . . .	6.1 km	. . .	cheap
	item 8 . . .	6.6 km	. . .	cheap
	item 9 . . .	6.9 km	. . .
	Distance A 1 to townhall	. . .	Level of rent
	item i 1 . . .	4.1 km	. . .	cheap
	item i 2 . . .	4.2 km	. . .	cheap
	item i 3 . . .	4.3 km	. . .	cheap
	item i 4 . . .	4.4 km	. . .	cheap
	item i 5 . . .	4.6 km	. . .	cheap
	item i 6 . . .	4.7 km	. . .	cheap
	item i 7 . . .	4.8 km	. . .	cheap
	item i 8 . . .	6.6 km	. . .	cheap
	item i 9 . . .	6.9 km	. . .	cheap
	item i 10 . . .	4.1 km	. . .	cheap
	item i 11 . . .	4.1 km	. . .	cheap
	item i 12 . . .	4.4 km	. . .	cheap
	item i 13 . . .	4.8 km	. . .	cheap
	item i 14 . . .	5 km	. . .	cheap
	item i 15 . . .	5.5 km	. . .	cheap
	item i 16 . . .	5.8 km	. . .	cheap
	item i 17 . . .	6.1 km	. . .	cheap
	item i 18 . . .	6.6 km	. . .	cheap
	item i 19 . . .	6.8 km	. . .	cheap
	item i 20 . . .	6.9 km	. . .	cheap

cheap

Then, such a principle could make S (the above 9 items) to generate a rule with v π 2 = [4.1, 6.9].

  .73, 14.83] ⇒ blue • v ∈ [0.97, 2.57] ⇒ blue • v ∈ [10.65, 12.81] ⇒ green • v ∈ [3.09, 10.04] ⇒ blue • v ∈ [15.01, ∞] ⇒ green • v ∈ [3.50, 7.18] ⇒ green • v ∈ [11.55, 13.14] ⇒ green • v ∈ [13.15, ∞] ⇒ greenIn the case of the uniform distributions, the intervals of rules with different decision classes may overlap. CN2 thus allows for intervals occurring in different rules to overlap.B. Impact of example density on boundaries choiceFigure 3 illustrates the case of two (single-attribute) datasets whose class distributions are similar: uniform distribution with the same bounds, but different intensities. Example-classes are balanced in the first dataset but not in the second.

	0 2 4 6 8 10 12	0	1	2	3	4	5	6	7
	0 2 4 6 8 10 12 14 16	0	1	2	3	4	5	6	7

Here, S is identified with its enumeration in increasing order since this simplifies the formulation in[START_REF] José | Evaluation of association rule quality measures through feature extraction[END_REF].

Capping originates in logic where it is called Restricted Cut as it captures the principle that intermediate conclusions can be freely removed from the premises with no loss among conclusions.

Given a set U, a Kuratowki closure operator [START_REF] Kuratowski | Topology[END_REF] is a mapping c : 2 U → 2 U such that for all X ⊆ 2 U and all

preservation of binary unions)

A first direction to weaken Kuratowki closure operators is to drop (idempotence), resulting in preclosure operators

Another direction amounts to dropping (null fixpoint) and replacing (preservation of binary unions) by a weaker axiom with all this giving abstract closure operators

These, in turn, can be weakened (various axioms weaker than (isotony) are detailed in [START_REF] Makinson | General patterns in nonmonotonic reasoning[END_REF]) to cumulation operators

which can themselves be weakened to capping operators 4

For cumulation and capping operators, (idempotence) holds as it is actually a consequence of the other two axioms.

SKETCH OF PROOFS

Proof: [Theorem 1] (Preservation of binary unions) For X = ↑ {X} and Y = ↑ {Y }, the proviso for condition 3. is


Loc The

Anne Nguyen
email: loc.nguyen@lirmm.fr

Sylvie Laurent
email: laurent@lirmm.fr

François Rapior

Raphaël Carbonnel

Gérard Trouillet

Gregory Bourrel

Ninot

Defining a Collaborative Ontology for Non-Pharmacological Interventions

Keywords:

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

-WebProtégé and BioPortal make the ontology development easier and more effective.

-NPIs data is shared and linked in humanreadable and machine-interpretable forms.

-The ontology allows to improve data retrieval and data crossing for better understanding NPIs and better defining advanced digital tools. The first version of NPIs ontology at: http://purl.bioontology.org/ontology/NPI/ -is a wildly used way to represent complex information and interrelationships.

-use URI to share and link to other resources available on the Web of Data need to share results cross data. However, no solutions are designed to this aim.

Defining a shared ontology of

Building an ontology:

-is an iterative process -is a complex task -requires a considerable amount of human effort.

Which tools?

Collaborative approach + for sharing the ontology for developing the ontology View publication stats View publication stats

-

  The collaborative ontology for NPIs is being built.

  URI: http://purl.bioontology.org/ontology/NPI/Mycelium URI: http://purl.bioontology.org/ontology/NPI/Physiotherapy


Clément Elbaz
email: clement.elbaz@inria.fr

Louis Rilling
email: louis.rilling@irisa.fr

Christine Morin
email: christine.morin@inria.fr

Towards Automated Risk Analysis of "One-day" Vulnerabilities

Keywords: Security, Cloud, CVE, CPE, TF-IDF

Common Vulnerabilities and Exposures (CVE) databases such as Mitre's CVE List and NIST's NVD database identify every disclosed vulnerability affecting any public software. However, during the early hours of a vulnerability disclosure, the metadata associated with these vulnerabilities is either missing, wrong, or at best sparse. This creates a challenge for robust automated analysis of new vulnerabilities. We present a new technique based on TF-IDF to map newly disclosed vulnerabilities to the most probably affected software products, formulated as an ordered list of relevant entries in the Common Platform Enumeration (CPE) database. For doing so we rely only on the human readable description of the vulnerability without any need for metadata.

I. INTRODUCTION

The disclosure of a vulnerability is the most critical part of its life cycle. As a confidential zero-day, a vulnerability is a high value asset used sparingly to attack high value targets. On the other hand, well known public vulnerabilities can be mitigated using standard security practices such as applying software updates diligently, or using a signaturebased intrusion detection system (IDS). Bilge et al [START_REF] Bilge | Before We Knew It: An Empirical Study of Zero-day Attacks in the Real World[END_REF] showed that during the disclosure, the usage of exploits of the vulnerability in the wild increase as high as five orders of magnitude while transitioning from a zero-day to a public vulnerability. A software patch is sometimes already available, but its adoption may not be widespread. At this early stage the vulnerability is not understood well enough to author a proper signature rule for an IDS. All these factors contribute in making the disclosure a dangerous time, since a lot of systems are vulnerable in practice.

In a nod to the well known zero-day term, we call one-day these newly disclosed vulnerabilities that are still in the critical part of their life cycle. One-day should not be taken literally here: a vulnerability disclosure can be 72 hours old and still be at its most threatening.

The vulnerability disclosure process is coordinated by the Common Vulnerabilities and Exposures (CVE) system overseen by Mitre's Corporation [START_REF]Common Vulnerabilities and Exposures (CVE)[END_REF]. Newly disclosed vulnerabilities are first published by the CVE List managed by Mitre. They are then forwarded to other security databases, such as NIST's NVD database [START_REF]National Vulnerability Database[END_REF] or SCAP data feeds [START_REF]Security Content Automation Protocol[END_REF], where they will eventually be annotated by multiple security experts. These annotations include metadata such as the affected software, as described by an entry from the Common Platform Enumeration (CPE) [START_REF]NVD -CPE[END_REF]. It also includes a Common Vulnerability Scoring System (CVSS) score and vector [START_REF]Common Vulnerability Scoring System[END_REF].

None of these steps are instantaneous: at any given time the NVD database is approximately 24 hours behind Mitre's CVE List, and NIST security experts take at least a few more days to analyze and annotate a vulnerability. As of writing this article, we can trivially find six-days-old vulnerabilities that are still not analyzed by NVD (for example CVE-2019-3908, disclosed by CVE List on 2019/18/01, has no NVD analysis as of 2019/24/01).

These delays mean that in order to reliably analyze one-day vulnerabilities, one should not rely on enriched databases such as NVD at all. Instead one should focus on Mitre's CVE List, which only provides three elements: a unique CVE identifier, a free-form human readable description, and at least one public reference [START_REF]CVE and NVD Relationship[END_REF].

Our end-goal is to propose an automated system that uses free-form descriptions of one-day vulnerabilities to infer a preliminary threat level for a given vulnerability, in the context of a specific information system (IS). Our approach is twofold: first we intend to design a robust similarity metric between vulnerabilities, so that we can quickly associate new vulnerabilities to older, better understood ones. Second, we want to let the IS administrator annotate a set of past vulnerabilities to assess their relevance to the IS to be protected. By measuring the similarity between new and previously annotated vulnerabilities, the system can act as a first layer of analysis against new vulnerabilities, deciding in real time if an urgent action is required.

In this paper, we present a first contribution towards this end-goal: a new automated mapping technique that associates CVE vulnerabilities to CPE software entries, quickly pointing out the most probable affected software. To the best of our knowledge this is the first attempt at doing so while only relying on the free-form description of the vulnerability without any metadata help. In Section II we discuss related work and the real world challenges of such a mapping. In Section III we present the architecture of our solution. In Section IV we evaluate the accuracy of our proposed mapping technique. We conclude in Section V.

II. RELATED WORK AND OPEN PROBLEMS

Extracting information and insights from the CVE corpus is not a new idea. Multiple works [START_REF] Frei | Large-scale Vulnerability Analysis[END_REF], [START_REF] Clark | Familiarity Breeds Contempt: The Honeymoon Effect and the Role of Legacy Code in Zero-day Vulnerabilities[END_REF], [START_REF] Elbaz | Mesurer et prévenir l'évolution de la menace dans un cloud d'infrastructure[END_REF] brought meaningful insights using statistical analyses of historical vulnerabilities in the NVD database.

Frei et al [START_REF] Frei | Large-scale Vulnerability Analysis[END_REF] found a statistical correlation between the availability of exploits and patches and the number of days since disclosure.

Clark et al [START_REF] Clark | Familiarity Breeds Contempt: The Honeymoon Effect and the Role of Legacy Code in Zero-day Vulnerabilities[END_REF] brought to light a "honeymoon effect" where more recent software is less subject to new vulnerabilities than older software, all else being equal.

In our own previous work [START_REF] Elbaz | Mesurer et prévenir l'évolution de la menace dans un cloud d'infrastructure[END_REF] we showed that cloud providers could exploit the predictability in the vulnerabilities life cycle to design new and profitable Service-Level Agreements about improving the security of their clients.

The closest work to ours is by Ganz et al [START_REF] Glanz | A Vulnerability's Lifetime: Enhancing Version Information in CVE Databases[END_REF]. They attempted to automatically enrich the quality of the metadata in NVD, by blending the existing metadata with textual analysis of the description. However their technique still requires the availability of existing metadata, while ours does not.

All of these studies point out inconsistent metadata as a major difficulty when working with the corpus. By being a theoretical database authored manually by security experts, CPE can not map perfectly to actual software binaries and packages in a production system [START_REF] Dulaunoy | The Myth of Software and Hardware Vulnerability Management[END_REF], [START_REF] Sanguino | Software Vulnerability Analysis Using CPE and CVE[END_REF]. This situation creates a lot of discrepancies when doing analysis, such as associating a CVE vulnerability to a CPE entries with an incorrect version or name.

Moreover, even if this situation was solved and it was possible to fully map CVE to CPE, and CPE to actual software, this mapping would still be done manually by security experts. This is however impractical when dealing with oneday vulnerabilities because the analysis arrives too late in the vulnerability life cycle.

III. OUR APPROACH

We consider the explainability of automated decisionmaking as a paramount quality of security systems. Therefore we deliberately choose to avoid elaborated machine learning methods when their accuracy comes at the expense of explainability. We evaluated several approaches for this work which we detail below, from the most simple to the most accurate.

The simplest possible approach we could think of is exact pattern matching.

We view the CPE database as a highly dimensional space (one dimension per CPE entry, the CPE database having 175 200 entries as of 2019/23/01), and the CVE mapping as a vector in this space. With exact pattern matching, the components of the vector are binary: if a CPE entry title is exactly present in the description, we consider it a match and we put the scalar component to 1. Otherwise, we leave it to 0.

We found this approach to fail in practice, as most CVE do not spell exact CPE entries explicitly. For instance We then tried partial pattern matching, by tokenizing every CVE and CPE entry into individual words, and incrementing the associated scalar component of the CVE vector for each individual word match (case insensitive). We can then identify the most probable CPE as the one associated with the highest component of the vector. We can also compare two CVE vectors using a standard distance metric such as the euclidean distance. However this naive approach proved to be too noisy.

If we look again at table I, we can see that although correct entries are matched, many irrelevant entries are also matched as false positives.

This high number of false positive makes partial pattern matching unworkable in practice. Entries such as "IBM Tivoli Service Request Manager" have a partial match with any CVE description that uses the word "request" or "service"! We improved the results by using weighted partial pattern matching. We still increment the scalar component of the CVE vector for each word match, but instead of incrementing it by a fixed amount we add the term frequency-inverse document frequency (TF-IDF) [START_REF] Jones | A statistical interpretation of term specificity and its application in retrieval[END_REF] value of the word, in the context of the CVE corpus.

TF-IDF is a numerical statistic reflecting the importance of a word to a document, in the context of a corpus. In our context, we consider a CVE description as an individual document, and the set of the descriptions of all past vulnerabilities as a corpus. TF-IDF is formally defined in Equation 1:

TFIDF(t, d, D) = TF(t, d) × IDF(t, D), (1)
where t is a word and d is a document belonging to a corpus of documents D. TF is defined as the number of occurrences of the word t in document d. IDF is defined in Equation 2:

IDF(t, D) = log |D| |d ∈ D : t ∈ d| , (2)
where |D| is the number of documents in the corpus, and |d ∈ D : t ∈ d| is the number of documents of the corpus containing the word t. TF-IDF therefore allows more specific words to have a bigger impact on the mapping than common words. As an intuitive example, if we look back at CVE-2016-5181, the word "54.0.2840.59" is much more specific than "remote". Therefore the matching score should be higher for "Google Chrome 54.0.2840.59" than "Juniper Remote Security Client".

We evaluate the results of this approach in the next section.

IV. EVALUATION We used the CVE corpus for the year 2016 as an evaluation dataset. It includes 8068 actual (non-rejected) vulnerabilities. We mapped it to the CPE dictionary in version 2.3, extracted in December 2017. As mentioned in section II, the corpus metadata proved to be too inconsistent to be used as a reliable ground truth. We found that more than 20% of vulnerabilities had CPE references pointing to nonexistent CPE entries, and more than 10% did not have any CPE reference at all. Therefore instead of relying on metadata, we evaluated our results manually. We randomly sampled 229 vulnerabilities from the CVE corpus, applied our mapping, and annotated manually the correctness of the proposed CPE entries.

We chose a broad definition of correctness: we consider the top three CPE entries proposed by the mapping. If at least one of them is a software affected by the vulnerability, we consider the vulnerability as correctly classified. Also we do not require the version to be correct.

With this definition of correctness, we found 151 correctly classified vulnerabilities out of 229, a 65.94% correctness rate.

As we outlined in section II we did not find any comparable result in the literature : past research focused on analyzing and enriching present metadata instead of limiting the reliance on it. To provide some context, the version of the CPE dictionary we used for this experiment describes 124681 CPE entries related to 17631 unique pieces of software (CPE entries relates to a specific version of a piece of software). Therefore our result is far better than a random choice (three random picks in a set of 17631 elements).

On the other hand, we acknowledge that our technique is giving incorrect results one third of the time, which makes many potential applications impractical at this stage.

Regarding performance, a full mapping of the 2016 corpus took under 2mn30 on a commodity laptop with 16 Gb of RAM and an Intel Core i7-7600U CPU @ 2.80GHz. We released all our experiment code under AGPL licence [16].

V. CONCLUSION

We introduced a method to automatically propose the most probable CPE software entry for a CVE vulnerability, relying only on its human readable description.

Our results are promising, as a quite simple technique already brings quite accurate results. However there is room for improvement, and we believe a better accuracy can be achieved in the future using more elaborated techniques, while still preserving the explainability of the decision.

So far we considered CPE entries to be completely independent from each other, as we treated them as different dimensions of an euclidean space. However, they are actually not independent. Two vulnerabilities matching respectively the CPE entry "Google Chrome 54.0.2840.59" and the CPE entry "Google Chrome 54.0.2840.85" are definitely closer to each other than two vulnerabilities matching respectively "Oracle HTML DB" and "Apache Tomcat 8.0.21". This is not currently reflected in the algorithm.

Also, we would like to introduce a "confidence" metric to the prediction, allowing the mapping to express a confidence score about the accuracy of the selected CPE entries for a CVE vulnerability.

In the future we hope to use our mapping technique to create a high quality similarity metric for vulnerabilities. This metric would allow us to quickly compare newly disclosed vulnerabilities to older ones, providing an immediate automated risk analysis mechanism for one-day vulnerabilities.

  Table I details the matching results of a randomly chosen vulnerability, CVE-2016-5181 [14], with a sample of entries from CVE-2016-5181 Blink in Google Chrome prior to 54.0.2840.59 for Windows, Mac, and Linux; 54.0.2840.85 for Android permitted execution of v8 microtasks while the DOM was in an inconsistent state, which allowed a remote attacker to inject arbitrary scripts or HTML (UXSS) via crafted HTML pages.

	CPE entry	Exact matching	Partial matching
	Linux Kernel 4.10.14	N	1
	Linux Kernel 4.10.15	N	1
	Google Chrome 54.0.2840.59	N	3
	Google Chrome 54.0.2840.85	N	3
	Google Chrome 53.0.2785.143	N	2
	Microsoft Windows 10 64-bits	N	1
	Juniper Remote Security Client	N	1
	Oracle HTML DB	N	1
	Apache Tomcat 8.0.21	N	0
		TABLE I
	Matching results using exact and partial pattern matching for
	CVE-2016-5181.
	the CPE database. CVE-2016-5181 is an actual vulnerability
	affecting Google Chrome. We notice that the description refer
	to "Google Chrome prior to 54.0.2840.59 for Windows, Mac,
	and Linux" instead of spelling every affected version and every
	affected platform. This kind of shortened enumerations are
	common enough to prevent naive exact pattern matching to
	work.